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

type blockCache struct {
	mu     sync.Mutex
	lru    *lru.Cache
	fillFn func(hash *bc.Hash) *types.Block
	single singleflight.Group
}

mu: 互斥锁，保证共享数据操作的一致性
lru: 缓存淘汰算法
fillFn: 回调函数
single: 回调函数的调用机制，同一时间保证只有一个回调函数在执行。

缓存命中和不命中的操作

database/leveldb/cache.go

func (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

func New(maxEntries int) *Cache {
	return &Cache{
		MaxEntries: maxEntries,
		ll:         list.New(),
		cache:      make(map[interface{}]*list.Element),
	}
}

MaxEntries:最大缓存条目数，如果为0则表示无限制
ll: 双向链表数据结构

LRU查询元素

func (c *Cache) Get(key Key) (value interface{}, ok bool) {
	if c.cache == nil {
		return
	}
	if ele, hit := c.cache[key]; hit {
		c.ll.MoveToFront(ele)
		return ele.Value.(*entry).value, true
	}
	return
}

Get获取元素，如果元素命中则将元素移至链表头部，保持最新的访问

LRU添加元素

func (c *Cache) Add(key Key, value interface{}) {
	if c.cache == nil {
		c.cache = make(map[interface{}]*list.Element)
		c.ll = list.New()
	}
	if ee, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ee)
		ee.Value.(*entry).value = value
		return
	}
	ele := c.ll.PushFront(&entry{key, value})
	c.cache[key] = ele
	if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries {
		c.RemoveOldest()
	}
}

Add添加元素有三步操作：

如果当前缓存中存在该元素则将元素移至链表头并返回
如果缓存中不存在该元素则将元素插入链表头部
如果缓存的元素超过MaxEntries限制则移除链表最末尾的元素

转载链接：https://shanhuhai5739.github.io/2018/08/23/Derek%E8%A7%A3%E8%AF%BB-Bytom%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90-%E6%8C%81%E4%B9%85%E5%8C%96%E5%AD%98%E5%82%A8LevelDB-%E4%BA%8C-cache%E7%BC%93%E5%AD%98/