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

Omitting GC

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

1. GC回收heap中对象，所以我们不把对象创建在heap中就可以避过垃圾回收。查阅offheap。
2. 使用freecache.
3. 在map结构的key和value中不存储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)、key的hash值(8byte)、key的长度(2byte)、key的值本身以及value的值本身。这里通过小端字节序来存储，所以后续的反编译也应该指定这种模式。从PutUint64、PutUint16也可以对应到字节的大小。

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

关于head和tail是一个相对的坐标，而且跟严格意义上队列的两个属性不一致。在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

当tail和head间的空隙，不足以容纳当前要插入的元素的时候，期间需要插入一个空的元素，具体到下面的代码：

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
}