Derek解读-Bytom源码分析-持久化存储LevelDB(二)-cache缓存

发表于

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实现过程如下：

  1. 执行GetBlock函数
  2. 从block cache中查询，如果命中缓存则返回
  3. block cache中未命中则执行fillFn回调函数从磁盘中获取并缓存block cache中，然后返回

blockCache分析

blockCache结构

database/leveldb/cache.go 

1
2
3
4
5
6
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 

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
29
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）算法根据数据的历史访问记录来进行淘汰数据，如果数据最近被访问过，那么缓存被命中的几率也更高。

logo

  1. 新的数据插入到链表头部
  2. 每当缓存命中，则将数据移到链表头部
  3. 当链表满的时候，将链表尾部的数据丢弃

LRU算法实现

LRU一般使用hash map和doubly linked list双向链表实现

实例化LRU CACHE

vendor/github.com/golang/groupcache/lru/lru.go 

1
2
3
4
5
6
7
func New(maxEntries int) *Cache {
	return &Cache{
		MaxEntries: maxEntries,
		ll:         list.New(),
		cache:      make(map[interface{}]*list.Element),
	}
}

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

LRU查询元素

1
2
3
4
5
6
7
8
9
10
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添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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添加元素有三步操作：

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