ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 数据库 > 数据库开发技术 > leveldb代码精读 lru cache

leveldb代码精读 lru cache

原创 数据库开发技术 作者：liiinuuux 时间：2015-11-20 15:23:27 0 删除 编辑
文件
cache.h
cache.cc


LRUCache的最基本的单位是struct LRUHandle，用来存放数据和一系列指针。
LRUCache里有一个LRUHandle组成的LRU链表和一个LRUHandle组成的HandleTable对象存放数据。



先看handle
  1. struct LRUHandle {
  2.   void* value; // 存放数据
  3.   void (*deleter)(const Slice&, void* value); // 用于删除数据的回调函数
  4.   LRUHandle* next_hash; // 哈希捅内的下一个handle
  5.   LRUHandle* next; // 当handle作为lru链表的节点时使用
  6.   LRUHandle* prev; // 当handle作为lru链表的节点时使用
  7.   size_t charge; // TODO(opt): Only allow uint32_t? // 调用者指定的，清理cache时用到。
  8.   size_t key_length;
  9.   uint32_t refs; // 引用计数
  10.   uint32_t hash; // 哈希值 // Hash of key(); used for fast sharding and comparisons
  11.   char key_data[1]; // 这个和key_length一起组成leveldb自己实现的字符串Slice类 // Beginning of key

  13.   // 将key_data, key_length组成leveldb自己实现的字符串Slice类，作为key返回
  14.   // 当链表里只有自己，也就是只把LRUHandle当一个简单的数据容器时，就返回value。
  15.   Slice key() const {
  16.     // For cheaper lookups, we allow a temporary Handle object
  17.     // to store a pointer to a key in "value".
  18.     if (next == this) {
  19.       return *(reinterpret_cast<Slice*>(value));
  20.     } else {
  21.       return Slice(key_data, key_length);
  22.     }
  23.   }
  24. };


cache不直接保存LRUHandle，而是将LRUHandle组成HandleTable来保存
HandleTable主要功能就是维护LRUHandle组成的哈希表。
私有成员变量：
  1. private:
  2.   // The table consists of an array of buckets where each bucket is
  3.   // a linked list of cache entries that hash into the bucket.
  4.   uint32_t length_; // 哈希捅的个数
  5.   uint32_t elems_; // 总的handle个数
  6.   LRUHandle** list_; // 指向若干handle的指针数组，每handle是一个链表，俗称哈希桶，hash bucket。


下面看这个哈希表怎么实现的
  1. /*
  2. 三个私有成员变量置空，函数内容只有一句 Resize()，这个是给哈希表扩容用的。
  3. 根据内部逻辑，现在elems_是0，就直接将list_初始化一个长度为4的指针数组。
  4. */
  5. HandleTable() : length_(0), elems_(0), list_(NULL) { Resize(); }

看查找操作最能体现哈希表的结构
  1. LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
  2.     /*
  3.     首先创建一个临时的指针，根据要查找哈希值定位哈希捅，也就是指针数组list_的一个元素。
  4.     通过哈希值和list_元素数(length_ - 1)进行"与"运算，可以随机得到一个小于等于(length_ - 1)的整数，这样可以高效定位哈希桶。
  5.     所以说在没有哈希碰撞的情况下，哈希表的查找效率非常高。
  6.     由于list_是指针数组，每个元素都是一个指针。list_[hash & (length_ - 1)]本身就是一个指针。
  7.     为了能在函数外面直接通过ptr维护list_，需要将ptr定义为一个二级指针指向list_中某个指针的地址。
  8.     */
  9.     LRUHandle** ptr = &list_[hash & (length_ - 1)];

  11.     /*
  12.     每一个哈希桶是一个链表
  13.     定位到第哈希表的某一个链表之后，在这一个链表里查找，找到哈希值和具key值都一样的，指针就不再移动了。
  14.     这里分两组情况
  15.     1 链表的第一个handle就是要找的，指针不需要移动，这时ptr是执行这个handle指针的指针。
  16.     2 ptr需要在链表里移动，那么最终ptr会定位到链表里某个handle的next_hash这个指针。
  17.       这里又有两种情况，就是如果next_hash指向的handle就是要找的handle，另一种情况是没有找到，这时next_hash执行的是NULL。
  18.     但不管怎样，将来对(*ptr)的赋值操作，就是改变handle或者handle->next_hash这两个指针的指向。
  19.     */
  20.     while (*ptr != NULL &&
  21.            ((*ptr)->hash != hash || key != (*ptr)->key())) {
  22.       ptr = &(*ptr)->next_hash; // next_hash执行的就是哈希值相同的下一个handle，也就是这一行的下一个。
  23.     }
  24.     return ptr; // 返回二级指针ptr，让函数外面可以通过操作ptr来操作哈希表的数据。
  25.   }


插入操作
  1. LRUHandle* Insert(LRUHandle* h) {
  2.     /*
  3.     先查找，可以定位到相同数据的已有handle。
  4.     这里返回的是二级指针，指向了指向list_里某个哈希桶的第一个handle指针的指针，或者是指向这个哈希桶里某个handle的next_hash的指针。
  5.     如果哈希表里没有相同handle，ptr会指向这个哈希桶最后一个handle的next_hash这个指针本身。
  6.     因此操作*ptr就是操作哈希桶本身。
  7.     */
  8.     LRUHandle** ptr = FindPointer(h->key(), h->hash);

  10.     /*
  11.     ptr是二级指针，因此*ptr是找到的handle的前一个handle的next_hash这个指针。
  12.     因此old被赋值后，就是找到的handle
  13.     */
  14.     LRUHandle* old = *ptr;
  15.     /*
  16.     leveldb里的容器有一个特点，就是不允许重复值
  17.     old->next_hash指的是找到的handle的next_hash
  18.     让h->next_hash指向old的next_hash，再让*ptr指向h，其实是把找到的handle从链表里摘掉了，用h替换old。
  19.     *ptr是已有handle的next_hash。*ptr = h的操作实际上是让已有handle的上一个handle的next_hash指向h.
  20.     */
  21.     h->next_hash = (old == NULL ? NULL : old->next_hash);
  22.     *ptr = h;

  24.     // 如果没找到重复值，就新建一个handle，并且按需要对哈希表扩容
  25.     if (old == NULL) {
  26.       ++elems_;
  27.       /*
  28.       每次插入后，判断handle数是否大于行数。
  29.       如果handle数大于哈希桶数，则调用resize函数对哈希表进行扩容，扩充哈希桶数，保证每个哈希桶最多一条记录。
  30.       */
  31.       if (elems_ > length_) {
  32.         // Since each cache entry is fairly large, we aim for a small
  33.         // average linked list length (<= 1).
  34.         Resize();
  35.       }
  36.     }
  37.     // 将old返回很重要，因为这个被摘到的handle需要在函数外面销毁。
  38.     return old;
  39.   }


删除和插入操作原理类似，很简单
  1. LRUHandle* Remove(const Slice& key, uint32_t hash) {
  2.     LRUHandle** ptr = FindPointer(key, hash);
  3.     LRUHandle* result = *ptr;
  4.     if (result != NULL) {
  5.       *ptr = result->next_hash;
  6.       --elems_;
  7.     }
  8.     return result;
  9.   }


对哈希表的扩容，就是新建一个哈希桶数更多的list_，将所有handle重新排布到更多的哈希桶里。
  1. void Resize() {
  2.     // 初始化时是4个哈希桶
  3.     uint32_t new_length = 4;
  4.     //重新决定哈希桶的数量
  5.     while (new_length < elems_) {
  6.       new_length *= 2;
  7.     }
  8.     LRUHandle** new_list = new LRUHandle*[new_length];
  9.     memset(new_list, 0, sizeof(new_list[0]) * new_length);
  10.     uint32_t count = 0;
  11.     for (uint32_t i = 0; i < length_; i++) {
  12.       LRUHandle* h = list_[i];
  13.       while (h != NULL) {
  14.         LRUHandle* next = h->next_hash;
  15.         uint32_t hash = h->hash;
  16.         // 很据先有handle的哈希值定位新的哈希桶
  17.         LRUHandle** ptr = &new_list[hash & (new_length - 1)];
  18.         /*
  19.         下面是二级指针操作
  20.         1 哈希桶是空的的时候，*ptr指向NULL，让h->next_hash指向NULL
  21.         2 当哈希桶里有东西的时候，*ptr指向哈希桶里第一个handle，在这个函数里就是上一次循环的h
  22.             让h->next_hash指向哈希桶第一个handle
  23.             让指向哈希桶第一个handle的指针指向h
  24.         */
  25.         h->next_hash = *ptr;
  26.         *ptr = h;

  28.         // h在老哈希桶里向后移动
  29.         h = next;
  30.         count++; // 新哈希表里的handle数加1
  31.       }
  32.     }
  33.     assert(elems_ == count);

  35.     删除老的指针数组，将list_指向新的。
  36.     delete[] list_;
  37.     list_ = new_list;
  38.     length_ = new_length;
  39.   }
  40. };


LRUCache
最重要的两个私有变量
  1. // 由handle组成的lru链表，最近访问的数据在最前端。
  2.   LRUHandle lru_;
  3.   // 用哈希表存放数据
  4.   HandleTable table_;


查找操作非常简单，就是调table_.Lookup，而table_.Lookup只是对FindPointer的简单调用
  1. Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
  2.   MutexLock l(&mutex_);
  3.   LRUHandle* e = table_.Lookup(key, hash);

  5.   // cache的查找比哈希表多两点，一个是更新handle的引用计数，另一个是将handle从lru摘除，加到最近访问的顶端。
  6.   if (e != NULL) {
  7.     e->refs++;
  8.     LRU_Remove(e);
  9.     LRU_Append(e);
  10.   }
  11.   return reinterpret_cast<Cache::Handle*>(e);
  12. }


LRU_Remove和LRU_Append都是简单的指针操作
下面是LRU_Append。leveldb的lru是循环链表，规则是：表头的next是最冷端，表头的priv是最近访问的。
  1. void LRUCache::LRU_Append(LRUHandle* e) {
  2.   // Make "e" newest entry by inserting just before lru_
  3.   e->next = &lru_;
  4.   e->prev = lru_.prev;
  5.   e->prev->next = e;
  6.   e->next->prev = e;
  7. }



LRUCache里值得一看的是insert操作。
  1. Cache::Handle* LRUCache::Insert(
  2.     const Slice& key, uint32_t hash, void* value, size_t charge,
  3.     void (*deleter)(const Slice& key, void* value)) {
  4.   MutexLock l(&mutex_); // 保证线程安全，先获取mutex

  6.   // 将参数封装成handle对象。
  7.   LRUHandle* e = reinterpret_cast<LRUHandle*>(
  8.       malloc(sizeof(LRUHandle)-1 + key.size()));
  9.   e->value = value;
  10.   e->deleter = deleter;
  11.   e->charge = charge;
  12.   e->key_length = key.size();
  13.   e->hash = hash;
  14.   e->refs = 2; // One from LRUCache, one for the returned handle
  15.   memcpy(e->key_data, key.data(), key.size());

  17.   // 新handle加到lru顶端
  18.   LRU_Append(e);
  19.   usage_ += charge;

  21.   LRUHandle* old = table_.Insert(e);
  22.   // table_.insert 用e替换老的old，old需要手动销毁。
  23.   if (old != NULL) {
  24.     LRU_Remove(old);
  25.     Unref(old);
  26.   }

  28.   /*
  29.   下面这段是LRUCache的关键
  30.   lru链表的结构比较特殊，lru_.next永远指向最冷，最长时间没人访问的handle
  31.   每次插入新handle前，调用者会手工指定charge。
  32.   插入时usage_会+=handle的charge，
  33.   当usage_超过调用者定义的容量（capacity_）时就要从冷端开始清理数据
  34.   这个机制可以让调用者通过控制capacity_和新handle的charge来调整lru链表的清理行为
  35.   */
  36.   while (usage_ > capacity_ && lru_.next != &lru_) {
  37.     LRUHandle* old = lru_.next;
  38.     LRU_Remove(old);
  39.     table_.Remove(old->key(), old->hash);
  40.     Unref(old);
  41.   }

  43.   return reinterpret_cast<Cache::Handle*>(e);
  44. }










来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/26239116/viewspace-1842049/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： leveldb代码精读 skiplist
下一篇： leveldb代码精读 数据库启动和初始化
请登录后发表评论 登录
全部评论
liiinuuux

注册时间：2012-11-12

  • 博文量
    94
  • 访问量
    353439

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593