bigcache

BigCache是如何做到高性能的？

加速并发访问

在BigCache中，缓存使用了分段（shard）存储，每一个shard有一个lock，减小了lock的粒度。

避免GC开销

map非指针优化是指: 如果在map的键和值中使用没有指针, 那么GC将忽略它。BigCache使用map[uint64]uint32，其中键是散列的，值是entries(某条数据)的偏移量。

entries被全部保存在[]byte中，因此海量的缓存数据只给GC增加了1个对象，进一步降低了GC的负担。 由于[]byte除了自身对象并不包含其他指针数据，所以GC对所有的BigCache对象的标记时间是O(1)的。

BigCache的原理

type BigCache struct {
	shards     []*cacheShard  // 缓存分片数据
	lifeWindow uint64
	clock      clock
	hash       Hasher
	config     Config
	shardMask  uint64
	close      chan struct{}
}
type cacheShard struct {
	hashmap     map[uint64]uint32  // 索引，对应KEY在entries中的位置和长度
	entries     queue.BytesQueue  // 实际数据存储
	lock        sync.RWMutex
	entryBuffer []byte
	onRemove    onRemoveCallback

	isVerbose    bool
	statsEnabled bool
	logger       Logger
	clock        clock
	lifeWindow   uint64

	hashmapStats map[uint64]uint32
	stats        Stats
}
type BytesQueue struct {
	full         bool
	array        []byte  // 实际数据存储
	capacity     int
	maxCapacity  int
	head         int
	tail         int  // 下次可以插入的位置
	count        int
	rightMargin  int
	headerBuffer []byte
	verbose      bool
}

设计思想： 根据key可以计算出hash，即可锁定key所属的shard分片， shard分片的hashmap字段用于存储key对应在entries的index（位置和长度）， 写入数据时结合value需要的[]byte长度和value在entries中新增插入的位置，这2个信息共同组成index信息写入hashmap(键是key的hash，值是在entries的index)， 那么在查询时就可以拿key的hash在hashmap中查找存储在entries中的位置和长度了，取出即可。

过期策略

BigCache只能在全局的Config中做配置，每一个key的过期时间窗口都是相同的，过期删除策略维护的是最近的时间窗口，Set同一个key会刷新它的过期时间。

一个例子

func TestBigCache(t *testing.T) {
	config := bigcache.Config{
		Shards: 1024,
		LifeWindow: 5 * time.Second,
		CleanWindow: 10 * time.Second,
		// 最大存储对象数量,是所有分片的可存储总和
		MaxEntriesInWindow: 1000 * 10 * 60,
		// 单个缓存的最大长度(字节数)，只用于entry初始化的大小参数，缓存对象是可以大于设置的值的
		MaxEntrySize: 500,
		// 详细模式 打印有关新内存分配的信息
		Verbose: true,
        // 占用内存的最大值，单位MB，如果达到了设置的上限，那么最老的记录会被最新的覆盖
        // 设置为0代表不限制内存占用
		HardMaxCacheSize: 8192,
        // 设置的删除回调函数，当key因为调用了delete方法或达到过期时间或者空间不足被删除时触发
		OnRemove: nil,
		OnRemoveWithReason: nil,
	}

	cache, initErr := bigcache.NewBigCache(config)
	if initErr != nil {
		log.Fatal(initErr)
	}

	err := cache.Set("my-key", []byte("1"))
	assert.Nil(t, err)
	time.Sleep(time.Second * 11)
	_, err = cache.Get("my-key")
	assert.Equal(t, bigcache.ErrEntryNotFound, err)
	err = cache.Set("my-key", []byte("1"))
	assert.Nil(t, err)
	for i := 0; i < 20; i++ {
		entry, err := cache.Get("my-key")
		assert.Nil(t, err)
		assert.Equal(t, []byte("1"), entry)
		time.Sleep(time.Second)
		err = cache.Set("my-key", []byte("1"))
		assert.Nil(t, err)
	}
}

LifeWindow & CleanWindow

一条数据在Set之后，经历LifeWindow时间之后会被标记为可清除状态（在它被删除之前仍然可以Get到它）。

全局的清理协程每CleanWindow执行一次清理，删除被标记为可清除状态的数据。