LevelDB源码分析之十一:cache - 21IC中国电子网

Cache LRUCache

LevelDB源码分析之十一:cache

2019-10-09
418次浏览
Cache为接口类。ShardedLRUCache继承自Cache,实现了Cache中的缓存操作方法。
ShardedLRUCache封装了16个LRUCache缓存片,每次对缓存的读取、插入、查找、删除操作都是调用某个缓存片LRUCache中的相应方法完成。
LRUCache为一个循环双向链表,与标准实现一致。其“头结点”lru_的prev始终指向最新结点,next始终指向最久未用节点,其对象容器为HashTable(哈希表),用于为LRUCache提供快速的查找操作。

LRUHandle为结点类。其next_hash指针用于HashTable中的bucket单向链表 。next和prev指针用于LRUCache循环双向链表的后继和前驱。

他们之间的关系如下图所示:


关于HashTable可以参考:哈希表(Hash Table)

关于LRUCache可以参考:LRU Cache原理和实现

一.Cache接口类

class Cache;

// 创建Cache的全局方法,capacity为容量大小
extern Cache* NewLRUCache(size_t capacity);

class Cache {
 public:
  Cache() { }

  virtual ~Cache();

  // 表示结点的结构体
  struct Handle { };

  // 插入键值对,并指定占用的缓存大小(charge),返回被插入的结点。
  // 如果插入的键值对用不到了,传给deleter函数。
  // 如果返回值用不到了,记得调用this->Release(handle)释放。
  virtual Handle* Insert(const Slice& key, void* value, size_t charge,
                         void (*deleter)(const Slice& key, void* value)) = 0;

  // 如果没找到结点,返回NULL。否则返回找到的结点。
  // 如果返回值用不到了,记得调用this->Release(handle)释放。
  virtual Handle* Lookup(const Slice& key) = 0;

  // 释放结点,注意不要重复释放。
  virtual void Release(Handle* handle) = 0;

  // 返回结点handle中的Value值,注意判断handle的有效性。
  virtual void* Value(Handle* handle) = 0;

  // 删除包含key的结点
  virtual void Erase(const Slice& key) = 0;

  // 返回数字ID,用于处理多线程同时访问缓存时的同步
  virtual uint64_t NewId() = 0;

 private:
  void LRU_Remove(Handle* e);
  void LRU_Append(Handle* e);
  void Unref(Handle* e);

  struct Rep;
  Rep* rep_;

  // No copying allowed
  Cache(const Cache&);
  void operator=(const Cache&);
};
二.LRUHandle
struct LRUHandle {
  void* value;
  void (*deleter)(const Slice&, void* value);//删除器。当refs == 0时,调用deleter完成value对象释放。
  LRUHandle* next_hash; // 作为HashTable中的节点,指向hash值相同的节点(解决hash冲突采用链地址法)
  LRUHandle* next;      // 作为LRUCache中的节点,指向后继
  LRUHandle* prev;      // 作为LRUCache中的节点,指向前驱
  size_t charge;        // 用户指定占用缓存的大小
  size_t key_length;    // key长度
  uint32_t refs;        // 引用计数
  uint32_t hash;        // 哈希值
  char key_data[1];     // key内容的起始位置

  Slice key() const {
    // For cheaper lookups, we allow a temporary Handle object
    // to store a pointer to a key in "value".
    if (next == this) {
      return *(reinterpret_cast(value));
    } else {
      return Slice(key_data, key_length);
    }
  }
};
一个LRUHandle就是一个结点,这个结构体设计的巧妙之处在于,它既可以作为HashTable中的结点,也可以作为LRUCache中的结点。
关于char key_data[1],在LevelDB源码分析之五:skiplist(1)这篇博客中又类似用法。key_data位于结构体的最后面,可在申请内存时,申请足够多的空间。 

往下面看会看到这句:

  LRUHandle* e = reinterpret_cast(
      malloc(sizeof(LRUHandle)-1 + key.size()));
注意在使用malloc申请空间时,sizeof(LRUHandle)-1,其中减去的1就是key_data[1],然后根据key.size()动态申请空间。最后,key_data还是指向这块空间的。

三.HashTable

LRUCache的实现并为用C++标准库内置的哈希表,用的是自己实现的哈希表。

class HandleTable {
 public:
  HandleTable() : length_(0), elems_(0), list_(NULL) { Resize(); }
  ~HandleTable() { delete[] list_; }

  LRUHandle* Lookup(const Slice& key, uint32_t hash) {
    return *FindPointer(key, hash);
  }

  LRUHandle* Insert(LRUHandle* h) {
    LRUHandle** ptr = FindPointer(h->key(), h->hash);
    LRUHandle* old = *ptr;
    h->next_hash = (old == NULL ? NULL : old->next_hash);
    // 不管找没找到h结点,都是可以直接将h替换到*ptr的。
    // 1.如果找到了,因为key相同,直接替换相当于替换结点中的value
    // 2.如果没找到,直接替换是理所当然的了
    *ptr = h;
	//如果没找到,相当于要添加了一个新的结点,此时结点总数elems_加1
    if (old == NULL) {
      ++elems_;
      if (elems_ > length_) {
        // Since each cache entry is fairly large, we aim for a small
        // average linked list length (<= 1).
	// 当elems_ > length_时进行扩容,这样可以保证在大部分情况下,所有以哈希地址为头的
	// 链表平均最多只有一个结点。因为结点比较大,扩容后能保证查找的时间复制度为O(1)。
        Resize();
      }
    }
    // 将old返回很重要,因为这个被摘到的handle需要在函数外面销毁。
    return old;
  }
  // 删除结点,比较简单
  LRUHandle* Remove(const Slice& key, uint32_t hash) {
    LRUHandle** ptr = FindPointer(key, hash);
    LRUHandle* result = *ptr;
    if (result != NULL) {
      *ptr = result->next_hash;
      --elems_;
    }
    return result;
  }

 private:
  // The table consists of an array of buckets where each bucket is
  // a linked list of cache entries that hash into the bucket.
  uint32_t length_;  //哈希地址数组的长度
  uint32_t elems_;   //哈希表中所有结点的总数
  LRUHandle** list_; //哈希地址数组的二级指针

  // Return a pointer to slot that points to a cache entry that
  // matches key/hash.  If there is no such cache entry, return a
  // pointer to the trailing slot in the corresponding linked list.
  // 如果找到了结点,返回该结点的二级指针。
  // 如果没找到结点,分两种情况:
  // 1.根据哈希值求出的哈希地址是空的,也就是说以该哈希地址(哈希桶)为头的单链表
  //   还没有结点。hash & (length_ - 1)的取值范围是0—(length_-1)。此时返回
  //   哈希地址的二级指针,*ptr=NULL 。  
  // 2.查找到了以某哈希地址为头的单链表的尾部,也没找到该结点。此时返回
  //   尾部结点next_hash域的二级指针,*ptr=NULL 。
  LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
    LRUHandle** ptr = &list_[hash & (length_ - 1)];
    while (*ptr != NULL &&
           ((*ptr)->hash != hash || key != (*ptr)->key())) {
      ptr = &(*ptr)->next_hash;
    }
    return ptr;
  }
  // 哈希表扩容
  // HandleTable内部维护了一个LRUHandle*的数组,默认大小为4。随着插入数据的增多,
  // 该数组会自动增长一倍,并将原数组中的数据重新分配到新的数组中。
  void Resize() {
    uint32_t new_length = 4;
    while (new_length < elems_) {
      new_length *= 2;
    }
    LRUHandle** new_list = new LRUHandle*[new_length];
    memset(new_list, 0, sizeof(new_list[0]) * new_length);
    uint32_t count = 0;
    // 需要注意的是,从新分配结点的时候,结点都往每个链表的头部插入的。
    // 而正常的Insert操作,相同hash值的结点是插入到链表的尾部
    for (uint32_t i = 0; i < length_; i++) {
      LRUHandle* h = list_[i];
      while (h != NULL) {
        LRUHandle* next = h->next_hash;
        Slice key = h->key();
        uint32_t hash = h->hash;
        LRUHandle** ptr = &new_list[hash & (new_length - 1)];
        h->next_hash = *ptr;
        *ptr = h;
        h = next;
        count++;
      }
    }
    assert(elems_ == count);
    delete[] list_;
    list_ = new_list;
    length_ = new_length;
  }
};
HandleTable是哈希表,但比较奇怪的是,查找、插入、删除动作除了传入key外,还要自备hash值。这样做是因为,hash值除了HandleTable中使用,在外部做多级缓存时也需要,后面会提到。

四.LRUCache

LRUCache::LRUCache()
    : usage_(0),
      last_id_(0) {
  // Make empty circular linked list
  // 创建空的循环链表
  lru_.next = &lru_;
  lru_.prev = &lru_;
}

LRUCache::~LRUCache() {
  for (LRUHandle* e = lru_.next; e != &lru_; ) {
    LRUHandle* next = e->next;
	// 如果不为1,说明LRUCache的使用者并未主动调用Release或Erase方法。
	// 因为初始的引用计数为2,调用Release或Erase时,引用计数会减一。
    assert(e->refs == 1);  
    Unref(e);
    e = next;
  }
}
// 引用计数减一。引用计数变为0时,调用删除器deleter。
void LRUCache::Unref(LRUHandle* e) {
  assert(e->refs > 0);
  e->refs--;
  if (e->refs <= 0) {
    usage_ -= e->charge;
    (*e->deleter)(e->key(), e->value);
    free(e);
  }
}

void LRUCache::LRU_Remove(LRUHandle* e) {
  e->next->prev = e->prev;
  e->prev->next = e->next;
}

void LRUCache::LRU_Append(LRUHandle* e) {
  // Make "e" newest entry by inserting just before lru_
  e->next = &lru_;
  e->prev = lru_.prev;
  e->prev->next = e;
  e->next->prev = e;
}
// 根据LRUCache规则,被访问的结点要移动到双向链表的lru_结点之前
// 移动只是改变了结点前驱指针和后继指针的指向,结点的存储位置并没变化
// 返回被找到的结点,如果没找到,返回NULL
Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  LRUHandle* e = table_.Lookup(key, hash);
  if (e != NULL) {
    e->refs++;// 这里为何要加一,后面会说到
    LRU_Remove(e);
    LRU_Append(e);
  }
  // 如果返回值不为NULL且用不到了,记得调用Relese或Erase释放。
  return reinterpret_cast(e);
}
// 释放结点
void LRUCache::Release(Cache::Handle* handle) {
  MutexLock l(&mutex_);
  Unref(reinterpret_cast(handle));
}

Cache::Handle* LRUCache::Insert(
    const Slice& key, uint32_t hash, void* value, size_t charge,
    void (*deleter)(const Slice& key, void* value)) {
  MutexLock l(&mutex_);

  LRUHandle* e = reinterpret_cast(
      malloc(sizeof(LRUHandle)-1 + key.size()));
  e->value = value;
  e->deleter = deleter;
  e->charge = charge;
  e->key_length = key.size();
  e->hash = hash;
  // 初始设为2,一个是给LRUCache自身析构时用,一个是给外部调用Release或Erase时用。
  e->refs = 2;  
  memcpy(e->key_data, key.data(), key.size());
  LRU_Append(e);
  usage_ += charge;
  // 当哈希表中已存在hash值相同的结点时,将原有的结点从双向链表中移除,
  // 并释放该结点。
  // 这里不需要调用哈希表的Remove方法将该结点从哈希表中移除,因为Insert
  // 的时候实际上已经移除了。
  // 这段代码也可以看出为何哈希表的Insert方法要返回旧结点?因为不返回旧
  // 结点,后续就无法对该结点进行LRU_Remove操作了。
  LRUHandle* old = table_.Insert(e);
  if (old != NULL) {
    LRU_Remove(old);
    Unref(old);
  }
  // 如果已用容量超过了总容量且头结点lru_还有后继。
  // 删除lru_的后继结点,根据LRUCache规则,这个结点最近用的最少。
  // 该结点既要从哈希表中移除,也要从双向链表中移除,然后再释放。
  while (usage_ > capacity_ && lru_.next != &lru_) {
    LRUHandle* old = lru_.next;
    LRU_Remove(old);
    table_.Remove(old->key(), old->hash);
    Unref(old);
  }
  // 返回新插入的结点,LRUCache的使用者需要主动调用该结点的Relese或Erase方法来释放结点。
  return reinterpret_cast(e);
}
// 删除结点,注意和Release方法的不同。删除结点先将结点从哈希表和
// 双向链表中移除,然后再释放该结点。
void LRUCache::Erase(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  LRUHandle* e = table_.Remove(key, hash);
  if (e != NULL) {
    LRU_Remove(e);
    Unref(e);
  }
}
1.为何要维护引用计数?

在Insert时,引用计数初始化为2,一个是给LRUCache自身析构时用,一个是给外部调用Release或Erase时用。Insert时,返回的是新插入的结点,插入完成后,需要调用该结点Release或Erase方法将引用计数减1,那么此时该结点的引用计数就是1了。在LRUCache析构时,会先将结点的引用计数再减1,如果此时引用计数为0,则调用deleter,并将该结点彻底从内存中free。

在Lookup时,如果查找接结点存在,此时引用计数会加1,也即是变成了3。此时,在用户持有该结点的期间,该缓存可能被删除(多种原因,如:超过缓存容量触发回收、具有相同key的新缓存插入、整个缓存被析构等),导致用户访问到非法内存,程序崩溃。因此,需要使用引用计数要加1来维护结点的生命周期。因为Lookup返回的是找到的结点,用户在查找完成后,要主动调用该结点的Release或Erase来使引用计数从新变成2。

2.LRUHandle为什么会被同时置于哈希表和双向链表之中?
注意看LookUp的实现,如果单纯使用链表,则仅能提供O(n)的查询效率,所以在查询时,利用了哈希表实现O(1)的查询。
那么,如果单纯使用哈希表呢?虽然可以实现O(1)的查询,但却无法更新缓存节点的访问时间。这是因为链表可以按照固定的顺序被遍历,而哈希表中的节点无法提供固定的遍历顺序(考虑Resize前后)。
那么,可不可以将访问时间记录在Handle中,然后仅用哈希表,这样既可以实现O(1)的查询,又可以方便地更新缓存记录的访问时间,岂不美哉?但是,如果没有按访问时间排序的链表,当触发缓存回收时,我们如何快速定位到哪些缓存记录要被回收呢?

链表O(n)的查询效率、哈希表不支持排序,两种数据结构单独都无法满足这里的需求。作者大神巧妙地将二者结合,取长补短,利用哈希表实现O(1)的查询,利用链表维持对缓存记录按访问时间排序

  查询 插入 删除 排序 链表 O(n) O(1) O(1) 支持 哈希表 O(1) O(1) O(1) 不支持

注1:哈希表实现O(1)操作的前提是:平均每哈希桶元素数 <= 1
注2:为了保持平均哈希桶元素数,必要时必须Resize,而Resize后,原有顺序将被打破

五.ShardedLRUCache

static const int kNumShardBits = 4;
static const int kNumShards = 1 << kNumShardBits;


class ShardedLRUCache : public Cache {
 private:
  // 16片LRUCache缓存
  LRUCache shard_[kNumShards];
  port::Mutex id_mutex_;
  uint64_t last_id_;
  // 使用哈希函数求出哈希值
  static inline uint32_t HashSlice(const Slice& s) {
    return Hash(s.data(), s.size(), 0);
  }
  // 取哈希值的高四位来定位使用那片LRUCache缓存
  static uint32_t Shard(uint32_t hash) {
    return hash >> (32 - kNumShardBits);
  }


 public:
  // capacity是Cache大小,其单位可以自行指定(如table cache,一个sstable文件的索引信息是一个单位,
  // 而block cache,一个byte是一个单位)
  explicit ShardedLRUCache(size_t capacity)
      : last_id_(0) {
    const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
    for (int s = 0; s < kNumShards; s++) {
      shard_[s].SetCapacity(per_shard);
    }
  }
  virtual ~ShardedLRUCache() { }
  virtual Handle* Insert(const Slice& key, void* value, size_t charge,
                         void (*deleter)(const Slice& key, void* value)) {
    const uint32_t hash = HashSlice(key);
    return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
  }
  virtual Handle* Lookup(const Slice& key) {
    const uint32_t hash = HashSlice(key);
    return shard_[Shard(hash)].Lookup(key, hash);
  }
  virtual void Release(Handle* handle) {
    LRUHandle* h = reinterpret_cast(handle);
    shard_[Shard(h->hash)].Release(handle);
  }
  virtual void Erase(const Slice& key) {
    const uint32_t hash = HashSlice(key);
    shard_[Shard(hash)].Erase(key, hash);
  }
  // 返回handle结点的value值
  virtual void* Value(Handle* handle) {
    return reinterpret_cast(handle)->value;
  }
  // 返回数字ID,用于处理多线程同时访问缓存时的同步
  virtual uint64_t NewId() {
    MutexLock l(&id_mutex_);
    return ++(last_id_);
  }
};

SharedLRUCache到底是什么呢?我们为什么需要它?这是因为levelDB是多线程的,每个线程访问缓冲区的时候都会将缓冲区锁住,为了多线程访问,尽可能快速,减少锁开销,ShardedLRUCache内部有16个LRUCache,查找Key时首先计算key属于哪一个分片,分片的计算方法是取32位hash值的高4位,然后在相应的LRUCache中进行查找,这样就大大减少了多线程的访问锁的开销。这种设计思路,非常值得我辈学习,致敬大神。

六.cache的使用

为了加快查找速度,LevelDB在内存中采用Cache的方式,在table中采用bloom filter的方式,尽最大可能加快随机读操作。LevelDB的Cache分为两种,分别是table cache和block cache。
1.table cache
table cache缓存的是table的索引数据,类似于文件系统中对inode的缓存。table cache默认大小是1000,注意此处缓存的是1000个table文件的索引信息,而不是1000个字节。table cache的大小由options.max_open_files确定,其最小值为20-10,最大值为50000-10。
2.block cache
block cache是缓存的block数据,block是table文件内组织数据的单位,也是从持久化存储中读取和写入的单位。由于table是按照key有序分布的,因此一个block内的数据也是按照key紧邻排布的(有序依照使用者传入的比较函数,默认按照字典序),类似于Linux中的page cache。
block默认大小为4k,由LevelDB调用open函数打开数据库时时传入的options.block_size参数指定。LevelDB的代码中限制的block最小大小为1k,最大大小为4M。对于频繁做scan操作的应用,可适当调大此参数,对大量小value随机读取的应用,也可尝试调小该参数。
block cache默认实现是一个8M大小的ShardedLRUCache,此参数由options.block_cache设定。当然也可根据应用需求,提供自定义的缓存策略。注意,此处的大小是未压缩的block大小。



参考链接:https://www.jianshu.com/p/9e7773432772

参考链接:http://www.360doc.com/content/14/0325/16/15064667_363619144.shtml

我要点评

评论暂时关闭。