Cache為接口類。ShardedLRUCache繼承自Cache，實現(xiàn)了Cache中的緩存操作方法。
ShardedLRUCache封裝了16個LRUCache緩存片，每次對緩存的讀取、插入、查找、刪除操作都是調(diào)用某個緩存片LRUCache中的相應(yīng)方法完成。
LRUCache為一個循環(huán)雙向鏈表，與標(biāo)準(zhǔn)實現(xiàn)一致。其“頭結(jié)點(diǎn)”lru_的prev始終指向最新結(jié)點(diǎn)，next始終指向最久未用節(jié)點(diǎn)，其對象容器為HashTable（哈希表），用于為LRUCache提供快速的查找操作。

LRUHandle為結(jié)點(diǎn)類。其next_hash指針用于HashTable中的bucket單向鏈表 。next和prev指針用于LRUCache循環(huán)雙向鏈表的后繼和前驅(qū)。

他們之間的關(guān)系如下圖所示：

關(guān)于HashTable可以參考：哈希表（Hash Table）

關(guān)于LRUCache可以參考：LRU Cache原理和實現(xiàn)

一.Cache接口類

class Cache;

// 創(chuàng)建Cache的全局方法，capacity為容量大小
extern Cache* NewLRUCache(size_t capacity);

class Cache {
 public:
  Cache() { }

  virtual ~Cache();

  // 表示結(jié)點(diǎn)的結(jié)構(gòu)體
  struct Handle { };

  // 插入鍵值對，并指定占用的緩存大小（charge），返回被插入的結(jié)點(diǎn)。
  // 如果插入的鍵值對用不到了，傳給deleter函數(shù)。
  // 如果返回值用不到了，記得調(diào)用this->Release(handle)釋放。
  virtual Handle* Insert(const Slice& key, void* value, size_t charge,
                         void (*deleter)(const Slice& key, void* value)) = 0;

  // 如果沒找到結(jié)點(diǎn)，返回NULL。否則返回找到的結(jié)點(diǎn)。
  // 如果返回值用不到了，記得調(diào)用this->Release(handle)釋放。
  virtual Handle* Lookup(const Slice& key) = 0;

  // 釋放結(jié)點(diǎn)，注意不要重復(fù)釋放。
  virtual void Release(Handle* handle) = 0;

  // 返回結(jié)點(diǎn)handle中的Value值，注意判斷handle的有效性。
  virtual void* Value(Handle* handle) = 0;

  // 刪除包含key的結(jié)點(diǎn)
  virtual void Erase(const Slice& key) = 0;

  // 返回數(shù)字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);//刪除器。當(dāng)refs == 0時，調(diào)用deleter完成value對象釋放。
  LRUHandle* next_hash; // 作為HashTable中的節(jié)點(diǎn)，指向hash值相同的節(jié)點(diǎn)（解決hash沖突采用鏈地址法）
  LRUHandle* next;      // 作為LRUCache中的節(jié)點(diǎn)，指向后繼
  LRUHandle* prev;      // 作為LRUCache中的節(jié)點(diǎn)，指向前驅(qū)
  size_t charge;        // 用戶指定占用緩存的大小
  size_t key_length;    // key長度
  uint32_t refs;        // 引用計數(shù)
  uint32_t hash;        // 哈希值
  char key_data[1];     // key內(nèi)容的起始位置

  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就是一個結(jié)點(diǎn)，這個結(jié)構(gòu)體設(shè)計的巧妙之處在于，它既可以作為HashTable中的結(jié)點(diǎn)，也可以作為LRUCache中的結(jié)點(diǎn)。
關(guān)于char key_data[1]，在LevelDB源碼分析之五：skiplist（1）這篇博客中又類似用法。key_data位于結(jié)構(gòu)體的最后面，可在申請內(nèi)存時，申請足夠多的空間。?

往下面看會看到這句：

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

注意在使用malloc申請空間時，sizeof(LRUHandle)-1，其中減去的1就是key_data[1]，然后根據(jù)key.size()動態(tài)申請空間。最后，key_data還是指向這塊空間的。

三.HashTable

LRUCache的實現(xiàn)并為用C++標(biāo)準(zhǔn)庫內(nèi)置的哈希表，用的是自己實現(xiàn)的哈希表。

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結(jié)點(diǎn)，都是可以直接將h替換到*ptr的。
    // 1.如果找到了，因為key相同，直接替換相當(dāng)于替換結(jié)點(diǎn)中的value
    // 2.如果沒找到，直接替換是理所當(dāng)然的了
    *ptr = h;
	//如果沒找到，相當(dāng)于要添加了一個新的結(jié)點(diǎn)，此時結(jié)點(diǎn)總數(shù)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).
	// 當(dāng)elems_ > length_時進(jìn)行擴(kuò)容，這樣可以保證在大部分情況下，所有以哈希地址為頭的
	// 鏈表平均最多只有一個結(jié)點(diǎn)。因為結(jié)點(diǎn)比較大，擴(kuò)容后能保證查找的時間復(fù)制度為O(1)。
        Resize();
      }
    }
    // 將old返回很重要，因為這個被摘到的handle需要在函數(shù)外面銷毀。
    return old;
  }
  // 刪除結(jié)點(diǎn)，比較簡單
  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_;  //哈希地址數(shù)組的長度
  uint32_t elems_;   //哈希表中所有結(jié)點(diǎn)的總數(shù)
  LRUHandle** list_; //哈希地址數(shù)組的二級指針

  // 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.
  // 如果找到了結(jié)點(diǎn)，返回該結(jié)點(diǎn)的二級指針。
  // 如果沒找到結(jié)點(diǎn)，分兩種情況:
  // 1.根據(jù)哈希值求出的哈希地址是空的，也就是說以該哈希地址（哈希桶）為頭的單鏈表
  //   還沒有結(jié)點(diǎn)。hash & (length_ - 1)的取值范圍是0—（length_-1）。此時返回
  //   哈希地址的二級指針，*ptr=NULL 。  
  // 2.查找到了以某哈希地址為頭的單鏈表的尾部，也沒找到該結(jié)點(diǎn)。此時返回
  //   尾部結(jié)點(diǎn)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;
  }
  // 哈希表擴(kuò)容
  // HandleTable內(nèi)部維護(hù)了一個LRUHandle*的數(shù)組，默認(rèn)大小為4。隨著插入數(shù)據(jù)的增多，
  // 該數(shù)組會自動增長一倍，并將原數(shù)組中的數(shù)據(jù)重新分配到新的數(shù)組中。
  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;
    // 需要注意的是，從新分配結(jié)點(diǎn)的時候，結(jié)點(diǎn)都往每個鏈表的頭部插入的。
    // 而正常的Insert操作，相同hash值的結(jié)點(diǎn)是插入到鏈表的尾部
    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
  // 創(chuàng)建空的循環(huán)鏈表
  lru_.next = &lru_;
  lru_.prev = &lru_;
}

LRUCache::~LRUCache() {
  for (LRUHandle* e = lru_.next; e != &lru_; ) {
    LRUHandle* next = e->next;
	// 如果不為1，說明LRUCache的使用者并未主動調(diào)用Release或Erase方法。
	// 因為初始的引用計數(shù)為2，調(diào)用Release或Erase時，引用計數(shù)會減一。
    assert(e->refs == 1);  
    Unref(e);
    e = next;
  }
}
// 引用計數(shù)減一。引用計數(shù)變?yōu)?時，調(diào)用刪除器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;
}
// 根據(jù)LRUCache規(guī)則，被訪問的結(jié)點(diǎn)要移動到雙向鏈表的lru_結(jié)點(diǎn)之前
// 移動只是改變了結(jié)點(diǎn)前驅(qū)指針和后繼指針的指向，結(jié)點(diǎn)的存儲位置并沒變化
// 返回被找到的結(jié)點(diǎn)，如果沒找到，返回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且用不到了，記得調(diào)用Relese或Erase釋放。
? return reinterpret_cast(e);
}
// 釋放結(jié)點(diǎn)
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;
  // 初始設(shè)為2，一個是給LRUCache自身析構(gòu)時用，一個是給外部調(diào)用Release或Erase時用。
  e->refs = 2;  
  memcpy(e->key_data, key.data(), key.size());
  LRU_Append(e);
  usage_ += charge;
  // 當(dāng)哈希表中已存在hash值相同的結(jié)點(diǎn)時，將原有的結(jié)點(diǎn)從雙向鏈表中移除，
  // 并釋放該結(jié)點(diǎn)。
  // 這里不需要調(diào)用哈希表的Remove方法將該結(jié)點(diǎn)從哈希表中移除，因為Insert
  // 的時候?qū)嶋H上已經(jīng)移除了。
  // 這段代碼也可以看出為何哈希表的Insert方法要返回舊結(jié)點(diǎn)？因為不返回舊
  // 結(jié)點(diǎn)，后續(xù)就無法對該結(jié)點(diǎn)進(jìn)行LRU_Remove操作了。
  LRUHandle* old = table_.Insert(e);
  if (old != NULL) {
    LRU_Remove(old);
    Unref(old);
  }
  // 如果已用容量超過了總?cè)萘壳翌^結(jié)點(diǎn)lru_還有后繼。
  // 刪除lru_的后繼結(jié)點(diǎn)，根據(jù)LRUCache規(guī)則，這個結(jié)點(diǎn)最近用的最少。
  // 該結(jié)點(diǎn)既要從哈希表中移除，也要從雙向鏈表中移除，然后再釋放。
  while (usage_ > capacity_ && lru_.next != &lru_) {
    LRUHandle* old = lru_.next;
    LRU_Remove(old);
    table_.Remove(old->key(), old->hash);
    Unref(old);
  }
  // 返回新插入的結(jié)點(diǎn)，LRUCache的使用者需要主動調(diào)用該結(jié)點(diǎn)的Relese或Erase方法來釋放結(jié)點(diǎn)。
  return reinterpret_cast(e);
}
// 刪除結(jié)點(diǎn)，注意和Release方法的不同。刪除結(jié)點(diǎn)先將結(jié)點(diǎn)從哈希表和
// 雙向鏈表中移除，然后再釋放該結(jié)點(diǎn)。
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.為何要維護(hù)引用計數(shù)？

在Insert時，引用計數(shù)初始化為2，一個是給LRUCache自身析構(gòu)時用，一個是給外部調(diào)用Release或Erase時用。Insert時，返回的是新插入的結(jié)點(diǎn)，插入完成后，需要調(diào)用該結(jié)點(diǎn)Release或Erase方法將引用計數(shù)減1，那么此時該結(jié)點(diǎn)的引用計數(shù)就是1了。在LRUCache析構(gòu)時，會先將結(jié)點(diǎn)的引用計數(shù)再減1，如果此時引用計數(shù)為0，則調(diào)用deleter，并將該結(jié)點(diǎn)徹底從內(nèi)存中free。

在Lookup時，如果查找接結(jié)點(diǎn)存在，此時引用計數(shù)會加1，也即是變成了3。此時，在用戶持有該結(jié)點(diǎn)的期間，該緩存可能被刪除（多種原因，如：超過緩存容量觸發(fā)回收、具有相同key的新緩存插入、整個緩存被析構(gòu)等），導(dǎo)致用戶訪問到非法內(nèi)存，程序崩潰。因此，需要使用引用計數(shù)要加1來維護(hù)結(jié)點(diǎn)的生命周期。因為Lookup返回的是找到的結(jié)點(diǎn)，用戶在查找完成后，要主動調(diào)用該結(jié)點(diǎn)的Release或Erase來使引用計數(shù)從新變成2。

2.LRUHandle為什么會被同時置于哈希表和雙向鏈表之中？
注意看LookUp的實現(xiàn)，如果單純使用鏈表，則僅能提供O(n)的查詢效率，所以在查詢時，利用了哈希表實現(xiàn)O(1)的查詢。
那么，如果單純使用哈希表呢？雖然可以實現(xiàn)O(1)的查詢，但卻無法更新緩存節(jié)點(diǎn)的訪問時間。這是因為鏈表可以按照固定的順序被遍歷，而哈希表中的節(jié)點(diǎn)無法提供固定的遍歷順序（考慮Resize前后）。
那么，可不可以將訪問時間記錄在Handle中，然后僅用哈希表，這樣既可以實現(xiàn)O(1)的查詢，又可以方便地更新緩存記錄的訪問時間，豈不美哉？但是，如果沒有按訪問時間排序的鏈表，當(dāng)觸發(fā)緩存回收時，我們?nèi)绾慰焖俣ㄎ坏侥男┚彺嬗涗浺换厥漳兀?br />

鏈表O(n)的查詢效率、哈希表不支持排序，兩種數(shù)據(jù)結(jié)構(gòu)單獨(dú)都無法滿足這里的需求。作者大神巧妙地將二者結(jié)合，取長補(bǔ)短，利用哈希表實現(xiàn)O(1)的查詢，利用鏈表維持對緩存記錄按訪問時間排序

? 查詢 插入 刪除 排序 鏈表 O(n) O(1) O(1) 支持 哈希表 O(1) O(1) O(1) 不支持

注1：哈希表實現(xiàn)O(1)操作的前提是：平均每哈希桶元素數(shù) <= 1
注2：為了保持平均哈希桶元素數(shù)，必要時必須Resize，而Resize后，原有順序?qū)⒈淮蚱?br />

五.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_;
? // 使用哈希函數(shù)求出哈希值
? 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結(jié)點(diǎn)的value值
? virtual void* Value(Handle* handle) {
? ? return reinterpret_cast(handle)->value;
? }
? // 返回數(shù)字ID，用于處理多線程同時訪問緩存時的同步
? virtual uint64_t NewId() {
? ? MutexLock l(&id_mutex_);
? ? return ++(last_id_);
? }
};

SharedLRUCache到底是什么呢？我們?yōu)槭裁葱枰?？這是因為levelDB是多線程的，每個線程訪問緩沖區(qū)的時候都會將緩沖區(qū)鎖住，為了多線程訪問，盡可能快速，減少鎖開銷，ShardedLRUCache內(nèi)部有16個LRUCache，查找Key時首先計算key屬于哪一個分片，分片的計算方法是取32位hash值的高4位，然后在相應(yīng)的LRUCache中進(jìn)行查找，這樣就大大減少了多線程的訪問鎖的開銷。這種設(shè)計思路，非常值得我輩學(xué)習(xí)，致敬大神。

六.cache的使用

為了加快查找速度，LevelDB在內(nèi)存中采用Cache的方式，在table中采用bloom filter的方式，盡最大可能加快隨機(jī)讀操作。LevelDB的Cache分為兩種，分別是table cache和block cache。
1.table cache
table cache緩存的是table的索引數(shù)據(jù)，類似于文件系統(tǒng)中對inode的緩存。table cache默認(rèn)大小是1000，注意此處緩存的是1000個table文件的索引信息，而不是1000個字節(jié)。table cache的大小由options.max_open_files確定，其最小值為20-10，最大值為50000－10。
2.block cache
block cache是緩存的block數(shù)據(jù)，block是table文件內(nèi)組織數(shù)據(jù)的單位，也是從持久化存儲中讀取和寫入的單位。由于table是按照key有序分布的，因此一個block內(nèi)的數(shù)據(jù)也是按照key緊鄰排布的（有序依照使用者傳入的比較函數(shù)，默認(rèn)按照字典序），類似于Linux中的page cache。
block默認(rèn)大小為4k，由LevelDB調(diào)用open函數(shù)打開數(shù)據(jù)庫時時傳入的options.block_size參數(shù)指定。LevelDB的代碼中限制的block最小大小為1k，最大大小為4M。對于頻繁做scan操作的應(yīng)用，可適當(dāng)調(diào)大此參數(shù)，對大量小value隨機(jī)讀取的應(yīng)用，也可嘗試調(diào)小該參數(shù)。
block cache默認(rèn)實現(xiàn)是一個8M大小的ShardedLRUCache，此參數(shù)由options.block_cache設(shè)定。當(dāng)然也可根據(jù)應(yīng)用需求，提供自定義的緩存策略。注意，此處的大小是未壓縮的block大小。

參考鏈接：https://www.jianshu.com/p/9e7773432772

參考鏈接：http://www.360doc.com/content/14/0325/16/15064667_363619144.shtml