golang BigCache源码解析

July 5, 2024

golang的本地缓存方案有不少，如freecache、bigcache、groupcache等。很久前看过groupcache的源码，对其singleflight的机制印象挺深的，但是印象中没有对gc做特殊的优化。最近刚好看到了了bigcache的介绍，其内部实现重点考虑了gc对于性能的影响。所以翻出其代码快速阅读了一遍其核心思路，特此记录。

网上相关的介绍已经不少了，这里重点介绍几个核心设计点。

github.com

https://github.com/allegro/bigcache

背景

bigcache的设计背景可以见原团队的这篇文章。

blog.allegro.tech

https://blog.allegro.tech/2016/03/writing-fast-cache-service-in-go.html

简单总结其需求，要求实现以下几点：

高性能。
支持并发访问。
支持淘汰，包括过期淘汰和空间慢时的老数据清理。

所以在设计方案上做了如下考虑：

提供lib集成：不考虑外部缓存方案，如redis、memcached等。而是采用lib的方式可以集成到服务自身。减少网络IO等带来的延迟。仓库内部也提供了一个简单的server实现。
数据分区：支持并行访问，数据存储上做了分区。高效的缓存基本都是基于hash，hash表的并发写操作都是要加锁的。为支持并发，所以存储拆分为多个区块。根据key的hash值将数据打散(shard)到多个区块中,减少锁的影响。而在每一个区块中，都维护了一个map来作为核心hash表，shard内对hash表的写操作仍需要加锁。
淘汰策略：最常见的方案就是采用类似memcached的LRU方案，在内存中维护一个LUR的双向链表。每次访问都修会改item中对应的双向链表的指针，将其位置放到链表最前端。淘汰时优先从链表尾部开始删除item。而BigCache采用FIFO的方式，不允许每个key指定不同的过期时间。

淘汰会带来gc的问题，在内存分配、释放频率高的情况下会出现gc pause。缓解、优化的方法有很多，比如修改gc频率、使用sync.Pool等，zero采用最直接的办法去掉gc，即Zero GC。具体实现：

索引：使用map[uint64]uint64方式存储，避免gc。其中key、value分别为原始key的hash值和在数据存储buf中的偏移量。
数据：使用类似FIFO方式数据结构。从尾部append数据，从头部evict数据。当尾部空间写满时从头部开始复用存储空间。删除数据时仅设置标记位，不真正清除。

核心设计点

BigCache

BigCache为最外层的存储服务对象，其内部维护多个数据存储的分片。

[go]

type BigCache struct {
	shards     []*cacheShard
	lifeWindow uint64
	clock      clock
	hash       Hasher
	config     Config
	shardMask  uint64
	close      chan struct{}
}
// 初始化存储对象 
func newBigCache(ctx context.Context, config Config, clock clock) (*BigCache, error) {
	// 去掉多余代码
	cache := &BigCache{
		shards:     make([]*cacheShard, config.Shards), // Shards可配置，默认1024.
		lifeWindow: lifeWindowSeconds, // 过期时间（统一的淘汰时间，bigcache数据采用FIFO的方式淘汰，所以所有key的淘汰时长是统一的）
		clock:      clock,
		hash:       config.Hasher, // hash算法
		config:     config,
		shardMask:  uint64(config.Shards - 1), // 用于&位运算，快速定位shard使用
		close:      make(chan struct{}),
	}
	return cache, nil
}

初始化时根据配置创建多个（默认1024）分片。在初始化过程中还会创建一个用于定期淘汰数据的goroutine，定期去各个shard中删除已过期的数据。

Shard

分片（Shard）为核心数据机构，负责实际的数据存储，数据结构如下：

[go]

type cacheShard struct {
	// 仅保留核心数据结构
	hashmap     map[uint64]uint64
	entries     queue.BytesQueue // 数据存储
	lock        sync.RWMutex
}

entries：实际的数据存储空间，底层为一大块连续的[]byte 。细节在BytesQueue部分介绍。
hashmap：即hash表，用于快速定位key所在entries的位置（偏移）。

存储时首先会将首先会将用户写入的数据（key+value）打包（Pack/Encode）到一块连续的内存（代码中称为 Entry ），为了查找、遍历等操作，里面包含了key、value数据外还有部分元数据。

Entry 打包过程如下：

[go]

const (
	timestampSizeInBytes = 8                                                       // Number of bytes used for timestamp
	hashSizeInBytes      = 8                                                       // Number of bytes used for hash
	keySizeInBytes       = 2                                                       // Number of bytes used for size of entry key
	headersSizeInBytes   = timestampSizeInBytes + hashSizeInBytes + keySizeInBytes // Number of bytes used for all headers
)

func wrapEntry(timestamp uint64, hash uint64, key string, entry []byte, buffer *[]byte) []byte {
	keyLength := len(key)
	blobLength := len(entry) + headersSizeInBytes + keyLength

	if blobLength > len(*buffer) {
		*buffer = make([]byte, blobLength)
	}
	blob := *buffer

	binary.LittleEndian.PutUint64(blob, timestamp)
	binary.LittleEndian.PutUint64(blob[timestampSizeInBytes:], hash)
	binary.LittleEndian.PutUint16(blob[timestampSizeInBytes+hashSizeInBytes:], uint16(keyLength))
	copy(blob[headersSizeInBytes:], key)
	copy(blob[headersSizeInBytes+keyLength:], entry)

	return blob[:blobLength]
}

Entry由以下几部分组成：

元数据
- timestamp(8)：用于判断过期
- hash(8)：key的hash值，同时也承担起标识位的功能（删除时置0）。
key: len(2) + key string(不定长)：类似TLV（Type Length Value）结构，先存储key长度，再存储实际key string。
entry：即value。这里没有记录value的长度，因为Entry在写入shard之前还会有一个字段（类似protobuf的varint编码），记录Entry的总长。

Entry 构建好后会被写入存储BytesQueue中，同时也会将 hashkey 和 BytesQueue中的位置记录到hashmap中。

写操作的整体流程如下：

[go]

func (s *cacheShard) set(key string, hashedKey uint64, entry []byte) error {
	currentTimestamp := uint64(s.clock.Epoch())

  // shard写操作需要加锁
	s.lock.Lock()

	// 判断hashedKey是否已经存在于s.hashmap中。如果已存在需要先删除
	if previousIndex := s.hashmap[hashedKey]; previousIndex != 0 {
		if previousEntry, err := s.entries.Get(int(previousIndex)); err == nil {
			resetHashFromEntry(previousEntry)
			delete(s.hashmap, hashedKey)
		}
	}

	// 尝试检查是否需要驱逐最旧的条目
	if !s.cleanEnabled {
		if oldestEntry, err := s.entries.Peek(); err == nil {
			s.onEvict(oldestEntry, currentTimestamp, s.removeOldestEntry)
		}
	}

  // key、value打包为Entry
	w := wrapEntry(currentTimestamp, hashedKey, key, entry, &s.entryBuffer)

	for {
		// 写入entry成功，则将hashedKey和对应的索引添加到s.hashmap中，解锁并返回nil
		if index, err := s.entries.Push(w); err == nil {
			s.hashmap[hashedKey] = uint64(index)
			s.lock.Unlock()
			return nil
		}
		// 如果s.entries已满，则调用s.removeOldestEntry(NoSpace)来驱逐最旧的条目，并重新尝试。
		if s.removeOldestEntry(NoSpace) != nil {
			s.lock.Unlock()
			return errors.New("entry is bigger than max shard size")
		}
	}
}

设计要点：

由于使用 map[uint64]uint64 的方式存储索引，没有使用开链或者开放地址等方法来解决hash冲突的问题，所以当遇到hash冲突时只能先清理老节点，然后插入新节点。
除了定时器删除外，插入过程中也会尝试清理部分数据。尽可能保存较高的内存利用率。在redis、memcached等中间件中也有类似操作，将耗时较长的逻辑（比如hash扩容&迁移）打散到各个API中调度，避免一次长时间的阻塞。
写入失败时（空间不足）一定会删除老数据，底层为FIFO，所以被清理的节点为最早写入的数据。

读取和删除的流程就比较简单了。

读：先根据hashmap定位Entry在BytesQueue中的位置，然后比较key，解析value即可。
删：BytesQueue中的Entry会被打上删除标识（hash设置为0）。索引hashmap中的值会被删除，但是不会导致gc。

BytesQueue

BytesQueue 的设计为bigcache中稍复杂的部分了，但其整体思路还是很简单的，整体思路采用类似ringbuf的FIFO数据结构，其逻辑结构大致如下：

BytesQueue 由一块 []byte 组成，用于连续存储一系列的数据节点。分别有两个指针head、tail用于指向链表的逻辑头尾节点。而leftMarginIndex、rightMarginIndex指向ringBuf在[]byte 中的物理开始、结束位置，即记录存储实际占用的空间范围。

每个节点存储的是一个varint编码的Entry长度和Entry数据，所以每节点长度是变长的。Entry在 []byte 中的起始位置（偏移量）即为hashmap中的value。
新数据节点会被Append到tail节点，空间不足、过期淘汰时优先淘汰head节点数据。
head和tail之间的节点也有可能被用户主动删除，由于是一块连续的 []byte ，所以空间不会被释放，而是设置删除标志位。

数据结构定义：

[go]

type BytesQueue struct {
	full         bool // 是否
	array        []byte // 指向array的指针
	capacity     int
	maxCapacity  int
	head         int //逻辑头部（也可以理解为，当前最老的数据的位置，删除的逻辑从这个位置开始）
	tail         int // 逻辑尾部
	count        int // 当前已经插入的 item 的数量
	rightMargin  int // 最右侧的节点
	headerBuffer []byte  // 临时缓存
	verbose      bool
}

full：是否已满。已满时需要扩容，扩容大小超过最大限制时无法写入。
array：使用make分配的存储空间。即实际数据的引用[]byte
capacity、maxCapacity：当前、最大容量。存储空间按当前*2倍大小扩容。注意不会缩容。
head：Ringbuf链表逻辑头部节点，优先从此节点开始淘汰。
tail：Ringbuf逻辑尾部节点，新增的节点会被追加自此。
rightMargin：Ringbuf中最右侧的节点。用于标识Ringbuf空间的物理尾部。

因为head淘汰后的空间是可以被重复利用的，所以Ringbuf会存在三种状态：

head < tail：此时head和tail之间是连续的。head ~ tail之间为有效数据（可能含delete节点），header之前为已过期，tail之后为剩余空间。
head > tail：表明head和tail之间非连续，数据物理上被拆分成了两块，即[tail, rightMargin]之间和 [leftMarginIndex, tail]之间。
head = tail：可能有两种情况。节点为0表示为空。也可能刚好存储完最后一个节点，空间已满。

所以插入和删除的操作的重点就是copy数据本身和移动head、tail指针位置。理解其思路之后，再看代码就简单了。

写逻辑：

[go]

func (q *BytesQueue) Push(data []byte) (int, error) {
	// item的大小：varint(1~5) + item内容(Entry大小)
	neededSize := getNeededSize(len(data))

	// 尾部空间不足时的处理，则需要申请更多空间或者调整。允许追加到队列尾部有两种情况：
	// 1. tail >= head，此时tail和head之间是连续的，且尾部剩余空间(capacity - tail)大于等于need
	// 2. tail < head，此时tail和head之间是断开状态，剩余空间(head - tail)等于need 或者 大于等于need + minimumHeaderSize
	if !q.canInsertAfterTail(neededSize) {
		// 头部是否有足够的空间：
		// 1. tail >= head，此时tail和head之间是连续的，且head剩余空间(head - leftMarginIndex)等于need 或者是 大于等于need + minimumHeaderSize
		// 2. tail < head，此时tail和head之间是断开状态，head剩余空间(head - tail)等于need 或者 大于等于need + minimumHeaderSize 【此种情况不可能，因为前面已经判断过了。回绕时尾部的剩余空间既是头部的前面剩余空间】
		if q.canInsertBeforeHead(neededSize) {
			q.tail = leftMarginIndex // 尾部没有足够空间，但是头部有。则将tail移动到leftMarginIndex，即头部位置。表示下次从头部插入。【只有可能是连续情况】
		} else if q.capacity+neededSize >= q.maxCapacity && q.maxCapacity > 0 {
			return -1, &queueError{"Full queue. Maximum size limit reached."}
		} else {
			// 如果申请空间的大小仍然不够呢
			q.allocateAdditionalMemory(neededSize)
		}
	}

	// 记录当前的 tail 索引到 index 变量中。然后，调用 push 方法（也没有在提供的代码段中定义）来实际插入数据。
	index := q.tail

	q.push(data, neededSize)

	// 返回插入前位置
	return index, nil
}


func (q *BytesQueue) push(data []byte, len int) {
	headerEntrySize := binary.PutUvarint(q.headerBuffer, uint64(len))
	q.copy(q.headerBuffer, headerEntrySize)

	q.copy(data, len-headerEntrySize)

	// tail 大于 head了，右移rightMargin
	if q.tail > q.head {
		q.rightMargin = q.tail
	}
	// 满了
	if q.tail == q.head {
		q.full = true
	}

	q.count++
}

删逻辑：查找Entry节点，然后设置标记位。代码略。

清理逻辑：从header节点清理，同时右移head地址。当移动到物理最尾部的节点时又调整回物理头部节点leftMarginIndex。

[go]

func (q *BytesQueue) Pop() ([]byte, error) {
	data, blockSize, err := q.peek(q.head)
	if err != nil {
		return nil, err
	}

	// 移动head指针
	q.head += blockSize
	q.count--

	if q.head == q.rightMargin {
		q.head = leftMarginIndex
		if q.tail == q.rightMargin {
			q.tail = leftMarginIndex
		}
		q.rightMargin = q.tail
	}

	q.full = false

	return data, nil
}

扩容

索引使用map，所以不用考虑。主要考虑BytesQueue的扩容。当tail节点之后的剩余空间不足，而且head之前的空间也不足时（数据没有删除、也没有evict）时需要扩容。

💡

这里不排查head和tail之间已经有部分节点被用户主动删除了，但是这里没有类似malloc的buddy allocator回收机制，所以此部分空间当前只能浪费，形成一些内存碎片。只有当evict的逻辑移动到此节点时这部分内存才会被回收。

扩容的逻辑也比较简单，就是按capacity的倍速来扩容。但是需要考虑当前存储的数据的迁移，除了直接将老的Ringbuf数据copy过去之外，还需要考虑一种特殊情况：

tail > head，即逻辑tail节点位于head之前。此时tail ~ head之间的空间是不足以存储下一个节点的，而新增节点时一定会追加到tail节点之后的，所以如果不做调整，那么扩容出来的空间仍然无法使用。

这里有两种解决方案：

将老Ringbuf中的两段数据按序分别copy到新的Ringbuf，这样可以保障在新Ringbuf中还是会严格按照FIFO的逻辑执行清理逻辑。问题是会有两次copy。
bigcache中实际采用的方法比较粗暴，将tail ~ head之间的空间浪费掉，塞入一个空间点。然后一次性copy到新的ringbuf种，并将head调整为起始位置，tail调整为rightMargin。显然这里会导致Ringbuf中扩容后copy过去的数据不再是严格按照FIFO的方式排列了，但是减少了一次copy。

[go]

func (q *BytesQueue) allocateAdditionalMemory(minimum int) {
	start := time.Now() // 应仅在verbose模式下使用；可以优化时间获取方式

	if q.capacity < minimum {
		q.capacity += minimum
	}
	// 按两倍扩容
	q.capacity = q.capacity * 2
	if q.capacity > q.maxCapacity && q.maxCapacity > 0 {
		q.capacity = q.maxCapacity // 不大于最大容量
	}

	oldArray := q.array
	q.array = make([]byte, q.capacity)

	if leftMarginIndex != q.rightMargin {
		copy(q.array, oldArray[:q.rightMargin])

		// 如果tail在head之前，则tail和head之间是断开状态
		if q.tail <= q.head {
			if q.tail != q.head {
				// 只是为了确保head和tail之间是连续的，填入了一段空数据 .
				// created slice is slightly larger than need but this is fine after only the needed bytes are copied
				q.push(make([]byte, q.head-q.tail), q.head-q.tail)
			}

			q.head = leftMarginIndex
			q.tail = q.rightMargin
		}
	}

	q.full = false

	if q.verbose {
		log.Printf("Allocated new queue in %s; Capacity: %d \n", time.Since(start), q.capacity)
	}
}

BenchMark

本地（M1机器）跑了下benchmark，对比golang各种存储lib的压测性能数据如下：

[go]

» go version
go version go1.22.2 darwin/arm64

» go test -bench=. -benchmem -benchtime=4s ./... -timeout 30m
goos: darwin
goarch: arm64

Set

Cache Type	Operation	Iterations	ns/op	B/op	allocs/op
Map	SetForStruct	3844	1061894	697047	19746
SyncMap	SetForStruct	1605	3049876	1852003	69778
OracamanMap	SetForStruct	2865	1773481	1226940	20195
FreeCache	SetForStruct	1291	3669389	6984541	40290
BigCache	SetForStruct	1460	3221069	3768975	42460
Map	SetForBytes	3327	1495231	2096561	29749
SyncMap	SetForBytes	1395	3501797	3134407	80034
OracamanMap	SetForBytes	2234	2211788	2989552	30277
FreeCache	SetForBytes	1603	3452192	7865272	30540
BigCache	SetForBytes	1510	2774104	4650031	32713

结论：

非并发场景下BigCache相对于原生的Map要差（50%+），与SyncMap差不多。因为有锁操作。Struct操作对比更明显，因为BigCache需要将其序列化后存储。
alloc的次数相差不大。虽然bigcache中BytesQueue对内存有一定的预分配，但是此处效果不明显。而且相对Map应该也有锁操作的影响。

Get

Cache Type	Key Type	Iterations	ns/op	B/op	allocs/op
Map	Struct	42625320	115.5	23	1
Map	Bytes	42207109	125.4	23	1
SyncMap	Struct	37394498	127.9	23	1
SyncMap	Bytes	36241047	128.8	23	1
OracamanMap	Struct	34276094	142.7	23	1
OracamanMap	Bytes	33538933	145.0	23	1
FreeCache	Struct	9026136	521.4	263	7
FreeCache	Bytes	20102252	240.1	135	2
BigCache	Struct	9558199	493.2	279	8
BigCache	Bytes	24627061	198.7	151	3

结论：

非并发场景下BigCache相对于原生的Map要差（50%-），比SyncMap也要差。应该主要受序列化的影响。

SetParallel

Cache Type	Key Type	Iterations	ns/op	B/op	allocs/op
SyncMap	Struct	8729923	479.6	70	5
OracamanMap	Struct	47110821	109.4	30	2
FreeCache	Struct	37602955	131.7	54	4
BigCache	Struct	42386787	99.24	179	4
SyncMap	Bytes	8266707	604.9	198	6
OracamanMap	Bytes	41447361	116.9	141	3
FreeCache	Bytes	34734166	135.0	141	3
BigCache	Bytes	40498724	147.0	646	3

结论：

写并发场景下BigCache相对于SyncMap性能要优（400%+）。因为存在分片的缘故。

GetParallel

Cache Type	Key Type	Iterations	ns/op	B/op	allocs/op
SyncMap	Struct	121969327	34.86	23	1
OracamanMap	Struct	100000000	43.17	23	1
FreeCache	Struct	30949936	157.2	263	7
BigCache	Struct	31723624	149.3	279	8
SyncMap	Bytes	143515130	31.83	23	1
OracamanMap	Bytes	100000000	47.13	23	1
FreeCache	Bytes	50028662	95.23	135	2
BigCache	Bytes	62721355	73.63	151	3

结论：

读并发场景下BigCache相对于SyncMap性能要差（50%），Struct存在序列化时差距效果更明显。猜测是因为仅有读锁的情况下二者的逻辑差别不大。

结语

bigCache的特点非常明显，优势和劣势总结如下：

优势

数据分片+读写锁，支持并行写入
性能高效，无GC
支持自动扩容

劣势

不支持LRU淘汰。这个对热点数据比较明显的场景会是个大问题。热点数据淘汰可能会导致cache命中率严重拉低。
无法自动缩容。
如果有频繁的delete，而evict执行速度跟不上，可能会导致内存漏洞较多。内存利用率不高。

其他可优化点：看代码的过程中，也看到了一些可以优化的点。

减少copy：写入BytesQueue时多次用到临时存储，先拼装buf然后写入，这里可以优化为一次写入，减少cpu损耗。
get场景减少内存分配，或者使用sync.Pool。内存分配方式应该由上层决定。

参考

See all posts