關于LRU Cache

1. http://blog.csdn.net/huntinux/article/details/39290833

2. http://www.cnblogs.com/liuhao/archive/2012/11/29/2795455.html

3. http://blog.itpub.net/26239116/viewspace-1842049/ （重點參考）

4. http://mingxinglai.com/cn/2013/01/leveldb-cache/ (重要參考，建議移步這裡)

引文1中給出了LRU cache 的一種實作方式是：雙向連結清單 + hashtable。由于cache中的移動操作頻繁，是以使用雙向連結清單。為了彌補雙向連結清單查找性能缺陷，引入hashtable。讀者可以了解了引文1中的簡單實作再繼續往下看。

LRUHandle

用來表示哈希表中的元素

// An entry is a variable length heap-allocated structure.  Entries
// are kept in a circular doubly linked list ordered by access time.
struct LRUHandle {
  void* value;
  void (*deleter)(const Slice&, void* value);
  LRUHandle* next_hash; // 作為Hash表中的節點，指向hash值相同的節點（解決hash沖突采用鍊位址法）
  LRUHandle* next; // 作為Cache中的節點，指向後繼
  LRUHandle* prev; // 作為Cache中的節點，指向前驅
  size_t charge;      // TODO(opt): Only allow uint32_t?
  size_t key_length; // key的長度
  uint32_t refs; // 引用計數
  uint32_t hash;      // 哈希值，Hash of key(); used for fast sharding and comparisons
  char key_data[];   // 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);
    }
  }
};

其中比較有意思的是

char key_data[1];

，會有這樣的疑問：為什麼不直接定義成指針呢？

定義成指針将會占用4位元組（32位機器）或8位元組（64位機器）的空間，而這樣定義隻占用1位元組空間。而且key_data位于結構體的最後面，可在申請記憶體時，申請足夠多的空間。

往下面看會看到這句：

LRUHandle* e = reinterpret_cast<LRUHandle*>(
      malloc(sizeof(LRUHandle)- + key.size()));

注意在使用malloc申請空間時，

sizeof(LRUHandle)-1

。其中減去的1就是key_data[1]，然後根據key.size()動态申請空間。最後，key_data還是指向這塊空間的。看來key_data[1]隻是一個占位符。（個人了解, ps，這種用法叫做“彈性指針”？）

哈希表 HandleTable

bucket：桶，哈希表當中有若幹bucket，而每個bucket是一個連結清單，用來存放hash值相同的元素。（是以這裡使用的解決“hash沖突”的方法是連結清單法）

HandleTable中：

length_ : hash表桶（bucket）的數量

elems_ : 放入哈希表中元素的個數

當元素個數大于桶的個數時（elems_ > length_ ），就重新hash（rehash），這樣hash表平均查找效率為O(1)。（可以與Redis中哈希表的rehash對比一下。）

list_ : 是一個數組，數組中的每個元素是一個指針，構成連結清單存儲hash值相同的元素。在這裡，每個元素的類型是 LRUHandle *

構造函數

構造函數的初始化清單将桶個數和元素個數設定為0，然後在函數體中進行Resize()，Resize函數對哈希表大小進行調整，然後對所有元素進行rehash。經過resize，哈希表的初始大小為4。

查找

查找一個元素是否在哈希表中。首先根據該元素的hash值定位到某個hash bucket（是一個連結清單），然後在連結清單中順序查找。最後，如果找到了就傳回一個指向該元素的指針。否則傳回該桶的最後一個位置的指針。

注意該函數的傳回值是一個二級指針，調用這可以使用該指針對其進行修改。

此外，hash值是如何與數組下标聯系起來的呢？通過 hash & (length -1) ，length為數組大小，并且length是4的倍數（見Resize函數）那麼length-1相當于一個mask，與hash做與操作就計算出了該元素在哪個桶了。

// 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.
  LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
    // 通過hash定位到某個桶
    LRUHandle** ptr = &list_[hash & (length_ - )];
    // 在連結清單中順序查找（比對key）
    while (*ptr != NULL &&
           ((*ptr)->hash != hash || key != (*ptr)->key())) {
      ptr = &(*ptr)->next_hash;
    }
    // 傳回查找結果
    return ptr;
  }

插入操作

這是将一個元素插入到哈希表的接口。

LRUHandle* Insert(LRUHandle* h) {
    // 在連結清單中查找是否有該元素
    LRUHandle** ptr = FindPointer(h->key(), h->hash);
    LRUHandle* old = *ptr;
    // old==NULL表示沒有找到，執行插入操作
    // 否則表示找到了相同元素，那麼也要用新的代替舊的
    h->next_hash = (old == NULL ? NULL : old->next_hash);
    *ptr = h;
    if (old == NULL) {
      ++elems_; // 元素個數加1
      if (elems_ > length_) {
        // 必要時，調整哈希表大小
        Resize();
      }
    }
    // 傳回舊節點，舊節點在外面被釋放
    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;
  }

Resize (Rehash)

該函數保證桶的個數大于元素的個數。

void Resize() {
    uint32_t new_length = ;
    while (new_length < elems_) {
      new_length *= ;
    }
    // 分派新的桶數組，初始化每個桶為空
    LRUHandle** new_list = new LRUHandle*[new_length];
    memset(new_list, , sizeof(new_list[]) * new_length);
    uint32_t count = ;

    // 對每個元素，重新計算在新的表中的位置
    for (uint32_t i = ; 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 - )];
        h->next_hash = *ptr;
        *ptr = h;
        h = next;
        count++;
      }
    }

    assert(elems_ == count); // 確定所有元素都被重新放入了新表中
    delete[] list_; // 删除舊的桶數組
    list_ = new_list; // 讓list_指向新的桶數組
    length_ = new_length; // 更新length_
  }
};

LRUCache

一個LRUCache的實作，成員變量介紹：

// Initialized before use.
  size_t capacity_; // cache的容量

  // mutex_ protects the following state.
  mutable port::Mutex mutex_;
  size_t usage_; // cache已經使用的容量

  // Dummy head of LRU list.
  // lru.prev is newest entry, lru.next is oldest entry.
  LRUHandle lru_; // LRU連結清單（雙向循環連結清單），按照通路先後進行排序，表頭的prev是最近通路的

  HandleTable table_; // 存放節點的哈希表，用于快讀查找

可以看到，LRUCache就是是通過雙向連結清單 + hashtable 實作的（理由在最上面）。

查找

查找操作就是調用前面介紹的哈希表的查找函數。

Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  // 在哈希表中查找
  LRUHandle* e = table_.Lookup(key, hash);
  if (e != NULL) {
    e->refs++; // 增加引用計數
    // 從cache中移動到最前面（現remove再append）
    LRU_Remove(e); 
    LRU_Append(e);
  }
  return reinterpret_cast<Cache::Handle*>(e);
}

// remove和append隻是關于雙向連結清單的操作，比較簡單
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;
}

// 引用計數減一。引用計數變為0時，調用删除器deleter。
void LRUCache::Unref(LRUHandle* e) {
  assert(e->refs > );
  e->refs--;
  if (e->refs <= ) {
    usage_ -= e->charge;
    (*e->deleter)(e->key(), e->value);
    free(e);
  }
}

插入

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

  // 由key、hash、value等建立一個新的元素，将被插入到cache中
  LRUHandle* e = reinterpret_cast<LRUHandle*>(
      malloc(sizeof(LRUHandle)- + key.size()));
  e->value = value;
  e->deleter = deleter;
  e->charge = charge;
  e->key_length = key.size();
  e->hash = hash;
  e->refs = ;  // One from LRUCache, one for the returned handle
  memcpy(e->key_data, key.data(), key.size());
  LRU_Append(e);
  usage_ += charge;

  // 哈希表的Insert函數在插入時如果發現有相同元素，則将舊的傳回，将新的替換舊的
  // 然後将舊的進行釋放
  LRUHandle* old = table_.Insert(e);
  if (old != NULL) {
    LRU_Remove(old);
    Unref(old);
  }

  // 當cache滿了，需要移除oldest的元素
  while (usage_ > capacity_ && lru_.next != &lru_) {
    LRUHandle* old = lru_.next;
    LRU_Remove(old);
    table_.Remove(old->key(), old->hash);
    Unref(old);
  }

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

設定cache的容量

// Separate from constructor so caller can easily make an array of LRUCache
  void SetCapacity(size_t capacity) { capacity_ = capacity; }

此外，Erase将清空cache，而Prune會移除引用計數為1的元素（即外部沒有使用）

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

void LRUCache::Prune() {
  MutexLock l(&mutex_);
  for (LRUHandle* e = lru_.next; e != &lru_; ) {
    LRUHandle* next = e->next;
    if (e->refs == ) {
      table_.Remove(e->key(), e->hash);
      LRU_Remove(e);
      Unref(e);
    }
    e = next;
  }
}

SharedLRUCache

不錯的分析：http://mingxinglai.com/cn/2013/01/leveldb-cache/

SharedLRUCache中有一個LRUCache的數組，SharedLRUCache做的工作就是計算出元素的hash值，然後根據hash值的高4位确定使用哪一個LRUCache，這麼做的理由(摘自上面的引文)：

這是因為levelDB是多線程的，每個線程通路緩沖區的時候都會将緩沖區鎖住，為了多線程通路，盡可能快速，減少鎖開銷，ShardedLRUCache内部有16個LRUCache，查找Key時首先計算key屬于哪一個分片，分片的計算方法是取32位hash值的高4位，然後在相應的LRUCache中進行查找，這樣就大大減少了多線程的通路鎖的開銷。

最後，引用引文4中的圖作為總結。

LevelDB : LRU CacheLRUHandle哈希表 HandleTableLRUCacheSharedLRUCache

LevelDB : LRU CacheLRUHandle哈希表 HandleTableLRUCacheSharedLRUCache

LRUHandle

哈希表 HandleTable

構造函數

查找

插入操作

删除

Resize (Rehash)

LRUCache

查找

插入

SharedLRUCache

繼續閱讀

在netbeans下編譯leveldb源碼

安裝leveldb-1.21

leveldb介紹leveldb

多種方式配置ActiveMQ叢集ActiveMQ靜态網絡配置基于LevelDB+Zookeeper建構ActiveMQ叢集基于kahadb建構ActiveMQ叢集

leveldb源碼分析之log檔案結構理論基礎

leveldb源碼分析之log 寫檔案代碼

leveldb源碼分析之log 讀檔案代碼

log::Writer-levelDB源碼解析

levelDB源碼分析-SSTable：Block

leveldb之使用筆記

leveldb之log寫操作

leveldb學習之初識

leveldb源碼分析--SSTable之block

leveldb之Mem Table

caffe學習筆記1：轉化自己的資料為（leveldb/lmdb）檔案

Leveldb BloomFliter 解析