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限制则移除链表最末尾的元素