本地缓存BigCache

BigCache的作者做了详细的阐述,尽在这里:Writing a very fast cache service with millions of entries in Go。不得不说,作者的表述非常完美,给它点赞。GitHub地址在:github.com/allegro/bigcacheUsage非常简单。

Omitting GC

map中存储过百万的object时,Go语言自身的GC甚至会影响不相关的请求,即使是对一个空对象做Marsh操作,响应时间也可能在1s以上。所以,如何避免Go默认对map做的Garbage Collector至关重要。

  1. GC回收heap中对象,所以我们不把对象创建在heap中就可以避过垃圾回收。查阅offheap
  2. 使用freecache.
  3. map结构的keyvalue中不存储pointer,这样便可以将map创建在堆上,同时忽略GC的影响。这来源于Go优化.

Concurrency

为了避免加锁成为系统的瓶颈,BigTable采用了Shared的方式来解决,确实也有点Redis单线程的感觉。将一块大的数据划分成多块小的数据,为小数据块加锁,确实很好的缓解了加锁的瓶颈。这体现出了拆分的思想,突然想到了曾经被面试的问题:“请将2G的数据进行排序”。

我比较好奇它的Hash方法,客户端的key转换为实际存储的hashedKey的过程。请看通过hashedKey获取shard的部分,作者没有使用%取余来实现,而是使用了&与运算来替代,确实很注重细节啊!

说到与运算:0&0=0; 0&1=0; 1&0=0; 1&1=1;,所以,最终拆分个数完全取决与二进制中1的数量。如果shardMask等于3,那就可以拆分成4份,如果等于4,那结果就是2份,以此类推。

//通过客户端的key获取实际存储的key
// Sum64 gets the string and returns its uint64 hash value.
func (f fnv64a) Sum64(key string) uint64 {
	var hash uint64 = offset64
	for i := 0; i < len(key); i++ {
		hash ^= uint64(key[i])
		hash *= prime64
	}

	return hash
}


//通过实际存储的key获取shard块,使用与运算。
func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) {
	return c.shards[hashedKey&c.shardMask]
}

Entry中存储的数据

这也是我特别好奇的地方。因为作者只简单介绍了它是模拟queue实现的,而且在map的结构中,它存储的仅仅是offset。那么,它是如何通过一个offset来获取到完整的数据信息的?

如代码所示,每个entry由5部分组成,分别是时间戳(8byte)、keyhash值(8byte)、key的长度(2byte)、key的值本身以及value的值本身。这里通过小端字节序来存储,所以后续的反编译也应该指定这种模式。从PutUint64PutUint16也可以对应到字节的大小。

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]
}

queue存储

queue中每个元素都由2部分组成,前4个byte是数据的长度,后面是数据的值本身。其中PutUint32变需要4byte。所以queue中每个元素最下的长度应该是4,而它的值部分只能是0了。

func (q *BytesQueue) push(data []byte, len int) {
	binary.LittleEndian.PutUint32(q.headerBuffer, uint32(len))
	q.copy(q.headerBuffer, headerEntrySize)

	q.copy(data, len)

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

	q.count++
}

关于rightMargin,用于标识队列中最后一个元素的位置,是一个绝对位置。所以,当队列需要扩容时,会copy该坐标之前的所有元素,如下面的示例代码。对于最正常的情况,该值跟tail相等。

copy(q.array, oldArray[:q.rightMargin])

关于headtail是一个相对的坐标,而且跟严格意义上队列的两个属性不一致。在queue中存储的元素有timestamp的部分,而head所指向的元素不一定是最早插入队列的元素,同理,tail指向的元素也不是最晚插入队列的元素。它们会因为循环而相互变动,只要的作用便是:推断是否可以合理的插入新的元素。

if q.tail < q.head {
	emptyBlobLen := q.head - q.tail - headerEntrySize
	q.push(make([]byte, emptyBlobLen), emptyBlobLen)
	q.head = leftMarginIndex
	//absoulate position to right margin
	q.tail = q.rightMargin
}

关于leftMarginIndex声明成一个常量,而且head默认从1开始。为什么要这样处理,注释给出的解释:

// Bytes before left margin are not used. Zero index means element does not exist in queue,
//useful while reading slice from index

关于申请新的空间,引入了minimumEmptyBlobSize,它占用36个byte。它其实占用了一个比实际需要大的多的空间。

minimumEmptyBlobSize = 32 + headerEntrySize

tailhead间的空隙,不足以容纳当前要插入的元素的时候,期间需要插入一个空的元素,具体到下面的代码:

emptyBlobLen := q.head - q.tail - headerEntrySize
q.push(make([]byte, emptyBlobLen), emptyBlobLen)

这个赋值的意义在这行代码才体现出来,当申请空间的时候,需要一个默认的值来标识:是否可以申请空间了。那么availableSpaceBeforeHead是可能产生负数的。

func (q *BytesQueue) availableSpaceBeforeHead() int {
	if q.tail >= q.head {
		//leftMarginIndex mean
		return q.head - leftMarginIndex - minimumEmptyBlobSize
	}
	return q.head - q.tail - minimumEmptyBlobSize
}