Derek解读-Bytom源码分析-持久化存储LevelDB(二)-cache缓存
简介
https://github.com/Bytom/bytom
本章介绍Derek解读-Bytom源码分析-持久化存储LevelDB(二)-cache缓存
作者使用MacOS操作系统，其他平台也大同小异
Golang Version: 1.8
block cache缓存介绍
上一篇《Derek解读-Bytom源码分析-持久化存储LevelDB》文章介绍了比原链数据持久化到磁盘。当执行读取数据时从cache中得到，实现快速访问。
比原链的block cache主要实现有两个部分：
- lru: 缓存淘汰算法
- fillFn: 回调函数
比原链的block cache实现过程如下：
- 执行GetBlock函数
- 从block cache中查询，如果命中缓存则返回
- block cache中未命中则执行fillFn回调函数从磁盘中获取并缓存block cache中，然后返回
blockCache分析
blockCache结构
database/leveldb/cache.go
1 | type blockCache struct { |
- mu: 互斥锁，保证共享数据操作的一致性
- lru: 缓存淘汰算法
- fillFn: 回调函数
- single: 回调函数的调用机制，同一时间保证只有一个回调函数在执行。
缓存命中和不命中的操作
database/leveldb/cache.go 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29func (c *blockCache) lookup(hash *bc.Hash) (*types.Block, error) {
if b, ok := c.get(hash); ok {
return b, nil
}
block, err := c.single.Do(hash.String(), func() (interface{}, error) {
b := c.fillFn(hash)
if b == nil {
return nil, fmt.Errorf("There are no block with given hash %s", hash.String())
}
c.add(b)
return b, nil
})
if err != nil {
return nil, err
}
return block.(*types.Block), nil
}
func (c *blockCache) get(hash *bc.Hash) (*types.Block, bool) {
c.mu.Lock()
block, ok := c.lru.Get(*hash)
c.mu.Unlock()
if block == nil {
return nil, ok
}
return block.(*types.Block), ok
}
lookup函数从block cache中查询，如果命中缓存则返回。如果block cache未命中则single.Do执行fillFn回调函数从磁盘中获取并缓存block cache中，然后返回
LRU缓存淘汰算法
LRU（Least recently used）算法根据数据的历史访问记录来进行淘汰数据，如果数据最近被访问过，那么缓存被命中的几率也更高。
- 新的数据插入到链表头部
- 每当缓存命中，则将数据移到链表头部
- 当链表满的时候，将链表尾部的数据丢弃
LRU算法实现
LRU一般使用hash map和doubly linked list双向链表实现
实例化LRU CACHE
vendor/github.com/golang/groupcache/lru/lru.go 1
2
3
4
5
6
7func New(maxEntries int) *Cache {
return &Cache{
MaxEntries: maxEntries,
ll: list.New(),
cache: make(map[interface{}]*list.Element),
}
}
- MaxEntries:最大缓存条目数，如果为0则表示无限制
- ll: 双向链表数据结构
LRU查询元素
1 | func (c *Cache) Get(key Key) (value interface{}, ok bool) { |
Get获取元素，如果元素命中则将元素移至链表头部，保持最新的访问
LRU添加元素
1 | func (c *Cache) Add(key Key, value interface{}) { |
Add添加元素有三步操作：
- 如果当前缓存中存在该元素则将元素移至链表头并返回
- 如果缓存中不存在该元素则将元素插入链表头部
- 如果缓存的元素超过MaxEntries限制则移除链表最末尾的元素