leveldb - cache


预览

cache.h

cache.h是一个只提供了接口的虚基类。

cache.cc

先来看cache节点的结构struct LRUHandle
struct LRUHandle {
  void* value;
  void (*deleter)(const Slice&, void* value);
  LRUHandle* next_hash;
  LRUHandle* next;
  LRUHandle* prev;
  size_t charge;      // TODO(opt): Only allow uint32_t?
  size_t key_length;
  uint32_t refs;
  uint32_t hash;      // Hash of key(); used for fast sharding and comparisons
  char key_data[1];   // Beginning of 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<Slice*>(value));
    } else {
      return Slice(key_data, key_length);
    }
  }
};

把这个结构单独拿出说是有原因的!

  1. 存放value的指针而非存放内容会比较快
  2. 其中有3个LRUHandle*,其中nextprev是在循环双链表中使用的,next_hash是在哈希表中使用的
  3. 提供了一个删除器的函数指针
  4. 使用引用计数refs
  5. UNKNOWN
  • 使用char key_data[1] + memcpy(key_data, key->data(), key->size())而非const char* key_data + key_data = key->data()
  • if(next == this) return *(reinterpret_cast<Slice*>(value));又是什么鬼?为什么返回value而不是key?
下面是hash表的实现
构造和析构函数
class HandleTable {
 public:
  HandleTable() : length_(0), elems_(0), list_(NULL) { Resize(); }
  ~HandleTable() { delete[] list_; }
// something omitted

从头开始看,在构造函数中有一个Resize(),这个函数的出现是为了在插入节点之前分配一小块空间。发现在析构函数中只是简单的释放了list_占用的内存,这是因为在LRUHandle中使用了引用计数refs节点所占用的内存会在class HandleTable的一个包装类class LRUCache中通过Unref()检查引用计数会决定是否释放。

查找
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;
}

这个类对外提供的三个公有函数都需要这个查找函数。
list_是一块固定大小的连续内存,里面存放着LRUHandle*,可通过下标来访问。
如果*ptr == NULL说明

  • 没有进入循环 => 没有此入口
  • 进入循环 => 在此入口的那条链上也没有找到

如果*ptr != NULL说明

  • 没有进入循环 => 节点在入口上
  • 进入循环 => 节点在这个入口的那条链上的某个位置(hash collision)

不管找没有找到,返回ptr
问题:&list_[hash & (length_ - 1)]; 保证不越界? 是的,保证不越界!因为length的长度保证大于0,所以hash & (length_ - 1)总是小于或等于length_ - 1

插入
LRUHandle* Insert(LRUHandle* h) {
  LRUHandle** ptr = FindPointer(h->key(), h->hash);
  LRUHandle* old = *ptr;
  h->next_hash = (old == NULL ? NULL : old->next_hash);
  *ptr = h;
  if (old == NULL) {
    ++elems_;
    if (elems_ > length_) {
      // Since each cache entry is fairly large, we aim for a small
      // average linked list length (<= 1).
      Resize();
    }
  }
  return old;
}

首先在list_中查找入口,令old = *ptr

  • 如果old == NULL
    • 此入口未指向任何节点,将要插入的节点的next_hash指向NULL,然后*ptr = h将此入口指向要插入的节点
    • 此入口的这条链上没有相同的key,然后将要插入的节点插入到这条链的尾部
  • 如果old != NULL(hash collision)
    • 说明此入口已指向某个节点(key相同,value可能相同可能不同),于是将这个要插入的节点插入(头插法)到这条链的头部

接下来,如果old == NULL则在插入节点后,节点的数量会增加(++elems_),当elems_ > length_时需要重新调整list_的大小来减少碰撞,即hash & (length_ - 1)的范围更大。

最后,返回old来指示是否更新(key相同,value不同)。

注意

char* tmp = "this";
char** ptr = &tmp;
char* old = ptr;

*ptr = "that";

最后,ptr指向"that"old仍然只想"this"

删除
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;
}

同样是先查找,如果找到就释放这个节点同时减小节点计数elems_,返回的result指示是否找到。

调整大小 (2016-03-23 21:50 更新)
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;
  for (uint32_t i = 0; i < length_; i++) {
    LRUHandle* h = list_[i];
    while (h != NULL) {
      LRUHandle* next = h->next_hash;
      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;
}

调整大小这个函数其实也很简单

  • 第一次调用,预先分配sizeof(LRUHandle*) * 4的内存
  • 随后的调用,将旧的list_复制(指针指向)到新的new_list上,再用新的替换旧的

注意
复制所用的方法和插入(Insert)所用的方法是一样的。

类LRUCache

先了解下什么是LRUCache

Least Recently Used (LRU) is a family of caching algorithms, which discards the least recently used items first. This algorithm requires keeping track of when the item was used, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping "age bits" for cache-lines and track the "Least Recently Used" cache-line based on age-bits.
注:age bits在这里是LEUHandle里面的uint32_t refs

了解基本概念之后来看看类LRUCache,先来看私有成员变量

  • capacity 缓存容量
  • mutex 这里提到过,是一个用POSIX互斥量实现的scope lock,注意mutable关键字,可以在const成员函数中修改它哦!
  • usage_ 这是一个LRUHandle::charge的计数,至于charge是什么暂时还看不出来
  • lru_ 链表的头节点,用于存放最新和最旧的LRUHandle
  • table_ 放缓存的哈希表

再来看私有成员函数
remove

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

很简单,将e后面一个节点的prev指向e的前一个节点,再将e的前一个节点的next指针指向e的后面一个节点,这样e就从双链表中剔除了。(同样,由于引用计数refs,没有释放e所占的内存)
appand

void LRUCache::LRU_Append(LRUHandle* e) {
  // Make "e" newest entry by inserting just before lru_
  e->next = &lru_;       // 1 
  e->prev = lru_.prev;   // 2
  e->prev->next = e;     // 3 lru_.next = e (first time)
  e->next->prev = e;     // 4 lru_.prev = e (first time)
}

提一下,在构造函数中

LRUCache::LRUCache()
    : usage_(0) {
  // Make empty circular linked list
  lru_.next = &lru_;
  lru_.prev = &lru_;
}

明显形成了两个环。对于首次插入节点可以用下图描述
leveldb-cache
unref

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);
  }
}

这就更简单了,先减小引用计数,如果小于等于0就带用删除器函数释放键值对再释放这个节点占用的内存。。。(usage_先不管)

接着来看公有成员函数 (2016-03-27 10:30 更新)
析构函数

LRUCache::~LRUCache() {
  for (LRUHandle* e = lru_.next; e != &lru_; ) {
    LRUHandle* next = e->next;
    assert(e->refs == 1);  // Error if caller has an unreleased handle
    Unref(e);
    e = next;
  }
}

循环一下链表,并释放内存。
Insert

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<LRUHandle*>(
      malloc(sizeof(LRUHandle)-1 + key.size()));
  e->value = value;
  e->deleter = deleter;
  e->charge = charge;
  e->key_length = key.size();
  e->hash = hash;
  e->refs = 2;  // One from LRUCache, one for the returned handle
  memcpy(e->key_data, key.data(), key.size());
  LRU_Append(e);
  usage_ += charge;

  LRUHandle* old = table_.Insert(e);
  if (old != NULL) {
    LRU_Remove(old);
    Unref(old);	// delete old if no refs
  }

  while (usage_ > capacity_ && lru_.next != &lru_) {
    LRUHandle* old = lru_.next;
    LRU_Remove(old);
    table_.Remove(old->key(), old->hash);
    Unref(old);	// delete old if no refs
  }

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

这个函数可分为以下几部分

  • 使用互斥锁保护以下操作
  • 创建一个LRUHandle对象,将传入参数赋值给这个对象,将其插入到双链表中(头插)
  • 然后,将其插入到哈系表中(头插),返回的是在这个入口在插入之前的LRU节点,然后按照LRU定义忽略它(LRU_Remove(old)在双链表中删除它,并解除引用)
  • 当缓存容量达到上限(capacity)循环链表并删除其节点并在哈希表中删除此节点然后解引用直到小于容量上限(可能删除刚添加的节点)
  • 返回一个Cache::Handle*

Erase
略(太简单)

Lookup

Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  LRUHandle* e = table_.Lookup(key, hash);
  if (e != NULL) {
    e->refs++;
		// exchange elements
    LRU_Remove(e);
    LRU_Append(e);
  }
  return reinterpret_cast<Cache::Handle*>(e);
}

值得提一下的是其中的LRU_RemoveLRU_Append操作,这两个操作使得e成为newest entry(即lru_.prev)。

Release
释放引用

Prune

// remove all elements whose refs equal 1 (i.e., they are not `latest recently used`)
void LRUCache::Prune() {
  MutexLock l(&mutex_);
  for (LRUHandle* e = lru_.next; e != &lru_; ) {
    LRUHandle* next = e->next;
    if (e->refs == 1) {
      table_.Remove(e->key(), e->hash);
      LRU_Remove(e);
      Unref(e);
    }
    e = next;
  }
}

以上注释已解释。

SharedLRUCache

看头文件发现只是一个提供了接口的虚基类,再看实现想想会有派生类继承才对,现在终于找到Cache的派生类了。
然而这个类所使用的东西在上面均已说明,所以没什么可以解释的。

总结

单从cache.h和cache.cc不能看出LRUHandel::chargeLRUCache::usage_以及SharedLRUCache::last_id_是什么用途。另外,缓存算法还有很多种,请看这篇翻译(由于原文链接打不开了,所以放了这篇翻译) 下面贴出部分此翻译


缓存算法

没有人能说清哪种缓存算法优于其他的缓存算法

Least Frequently Used(LFU):

大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率。我会把最不常用的缓存对象踢走。

Least Recently User(LRU):

我是 LRU 缓存算法,我把最近最少使用的缓存对象给踢走。

我总是需要去了解在什么时候,用了哪个缓存对象。如果有人想要了解我为什么总能把最近最少使用的对象踢掉,是非常困难的。

浏览器就是使用了我(LRU)作为缓存算法。新的对象会被放在缓存的顶部,当缓存达到了容量极限,我会把底部的对象踢走,而技巧就是:我会把最新被访问的缓存对象,放到缓存池的顶部。

所以,经常被读取的缓存对象就会一直呆在缓存池中。有两种方法可以实现我,array 或者是 linked list。

我的速度很快,我也可以被数据访问模式适配。我有一个大家庭,他们都可以完善我,甚至做的比我更好(我确实有时会嫉妒,但是没关系)。我家庭的一些成员包括 LRU2 和 2Q,他们就是为了完善 LRU 而存在的。

Least Recently Used 2(LRU2):

我是 Least Recently Used 2,有人叫我最近最少使用 twice,我更喜欢这个叫法。我会把被两次访问过的对象放入缓存池,当缓存池满了之后,我会把有两次最少使用的缓存对象踢走。因为需要跟踪对象2次,访问负载就会随着缓存池的增加而增加。如果把我用在大容量的缓存池中,就会有问题。另外,我还需要跟踪那么不在缓存的对象,因为他们还没有被第二次读取。我比LRU好,而且是 adoptive to access 模式 。

Two Queues(2Q):

我是 Two Queues;我把被访问的数据放到 LRU 的缓存中,如果这个对象再一次被访问,我就把他转移到第二个、更大的 LRU 缓存。

我踢走缓存对象是为了保持第一个缓存池是第二个缓存池的1/3。当缓存的访问负载是固定的时候,把 LRU 换成 LRU2,就比增加缓存的容量更好。这种机制使得我比 LRU2 更好,我也是 LRU 家族中的一员,而且是 adoptive to access 模式 。

Adaptive Replacement Cache(ARC):

我是 ARC,有人说我是介于 LRU 和 LFU 之间,为了提高效果,我是由2个 LRU 组成,第一个,也就是 L1,包含的条目是最近只被使用过一次的,而第二个 LRU,也就是 L2,包含的是最近被使用过两次的条目。因此, L1 放的是新的对象,而 L2 放的是常用的对象。所以,别人才会认为我是介于 LRU 和 LFU 之间的,不过没关系,我不介意。

我被认为是性能最好的缓存算法之一,能够自调,并且是低负载的。我也保存着历史对象,这样,我就可以记住那些被移除的对象,同时,也让我可以看到被移除的对象是否可以留下,取而代之的是踢走别的对象。我的记忆力很差,但是我很快,适用性也强。

Most Recently Used(MRU):

我是 MRU,和 LRU 是对应的。我会移除最近最多被使用的对象,你一定会问我为什么。好吧,让我告诉你,当一次访问过来的时候,有些事情是无法预测的,并且在缓存系统中找出最少最近使用的对象是一项时间复杂度非常高的运算,这就是为什么我是最好的选择。

我是数据库内存缓存中是多么的常见!每当一次缓存记录的使用,我会把它放到栈的顶端。当栈满了的时候,你猜怎么着?我会把栈顶的对象给换成新进来的对象!

First in First out(FIFO):

我是先进先出,我是一个低负载的算法,并且对缓存对象的管理要求不高。我通过一个队列去跟踪所有的缓存对象,最近最常用的缓存对象放在后面,而更早的缓存对象放在前面,当缓存容量满时,排在前面的缓存对象会被踢走,然后把新的缓存对象加进去。我很快,但是我并不适用。

Second Chance:

大家好,我是 second chance,我是通过 FIFO 修改而来的,被大家叫做 second chance 缓存算法,我比 FIFO 好的地方是我改善了 FIFO 的成本。我是 FIFO 一样也是在观察队列的前端,但是很FIFO的立刻踢出不同,我会检查即将要被踢出的对象有没有之前被使用过的标志(1一个 bit 表示),没有没有被使用过,我就把他踢出;否则,我会把这个标志位清除,然后把这个缓存对象当做新增缓存对象加入队列。你可以想象就这就像一个环队列。当我再一次在队头碰到这个对象时,由于他已经没有这个标志位了,所以我立刻就把他踢开了。我在速度上比 FIFO 快。

CLock:

我是 Clock,一个更好的 FIFO,也比 second chance 更好。因为我不会像 second chance 那样把有标志的缓存对象放到队列的尾部,但是也可以达到 second chance 的效果。

我持有一个装有缓存对象的环形列表,头指针指向列表中最老的缓存对象。当缓存 miss 发生并且没有新的缓存空间时,我会问问指针指向的缓存对象的标志位去决定我应该怎么做。如果标志是0,我会直接用新的缓存对象替代这个缓存对象;如果标志位是1,我会把头指针递增,然后重复这个过程,知道新的缓存对象能够被放入。我比 second chance 更快。

Simple time-based:

我是 simple time-based 缓存算法,我通过绝对的时间周期去失效那些缓存对象。对于新增的对象,我会保存特定的时间。我很快,但是我并不适用。

Extended time-based expiration:

我是 extended time-based expiration 缓存算法,我是通过相对时间去失效缓存对象的;对于新增的缓存对象,我会保存特定的时间,比如是每5分钟,每天的12点。

Sliding time-based expiration:

我是 sliding time-based expiration,与前面不同的是,被我管理的缓存对象的生命起点是在这个缓存的最后被访问时间算起的。我很快,但是我也不太适用。

其他的缓存算法还考虑到了下面几点:

成本:如果缓存对象有不同的成本,应该把那些难以获得的对象保存下来。

容量:如果缓存对象有不同的大小,应该把那些大的缓存对象清除,这样就可以让更多的小缓存对象进来了。

时间:一些缓存还保存着缓存的过期时间。电脑会失效他们,因为他们已经过期了。

根据缓存对象的大小而不管其他的缓存算法可能是有必要的。

电子邮件!

在读完这篇文章之后,programmer one 想了一会儿,然后决定给作者发封邮件,他感觉作者的名字在哪听过,但是已经想不起来了。不管怎样,他还是把邮件发送出来了,他询问了作者在分布式环境中,缓存是怎么样工作的。

文章的作者收到了邮件,具有讽刺意味的是,这个作者就是面试 programmer one 的人 ,作者回复了……

在这一部分中,我们来看看如何实现这些著名的缓存算法。以下的代码只是示例用的,如果你想自己实现缓存算法,可能自己还得加上一些额外的工作。

LeftOver 机制

在 programmer one 阅读了文章之后,他接着看了文章的评论,其中有一篇评论提到了 leftover 机制——random cache。

Random Cache

我是随机缓存,我随意的替换缓存实体,没人敢抱怨。你可以说那个被替换的实体很倒霉。通过这些行为,我随意的去处缓存实体。我比 FIFO 机制好,在某些情况下,我甚至比 LRU 好,但是,通常LRU都会比我好。


此文很有可能存在理解上的错误!



转载请注明:Serenity » leveldb - cache

上一篇

下一篇