Block Cache

RocksDB使用Block cache作為讀cache。用戶可以指定Block cache使用LRUCache，并可以指定cache的大小。
Block cache分為兩個，一個是用來緩存未被壓縮的block數(shù)據(jù)，另一個用來緩存壓縮的block數(shù)據(jù)。
處理讀請求時，先查找未壓縮的block cache，再查找壓縮的block cache。壓縮的block cache可以替換操作系統(tǒng)的page cache。
用法如下

std::shared_ptr<Cache> cache = NewLRUCache(capacity);
BlockBasedTableOptions table_options;
table_options.block_cache = cache;
Options options;
options.table_factory.reset(new BlockBasedTableFactory(table_options));
table_options.block_cache_compressed = another_cache;

LRUCache

默認(rèn)RocksDB會創(chuàng)建一個容量為8M的LRUCache。
LRUCache內(nèi)部對可以使用的容量進(jìn)行了分片（Shard，下面習(xí)慣性地稱之為分桶），每個桶都維護(hù)了自己的LRU list和用于查找的hash table。
用戶可以指定幾個參數(shù)

• capacity: cache的總?cè)萘?/li>
• num_shard_bits：2^num_shard_bits為指定的分桶數(shù)量。如果不指定，則會計算得到一個分桶數(shù)，最大分桶數(shù)為64個。

默認(rèn)計算分桶數(shù)量的方法
指定的capacity / min_shard_size，其中min_shard_size為每個shard最小的大小，為512KB

• strict_capacity_limit：有一些場景，block cache的大小會大于指定的cache 容量，比如cache中的block都因為外部有讀或者Iterator引用而無法被淘汰，這些無法淘汰的block總大小超過了總?cè)萘?。這種情況下，如果strict_capacity_limit為false，后續(xù)的讀操作仍然可以將數(shù)據(jù)插入到cache中?？赡茉斐蓱?yīng)用程序OOM。

該選項是限制每個分桶的大小，不是cache的總體使用大小。

• high_pri_pool_ratio：LRUCache提供了優(yōu)先級的功能，該選項可以指定高優(yōu)先級的block在每個桶中可以占的比例。

類圖

LRUCache類圖

類圖展示了各個類中的主要成員和一些操作。

• Cache
  定義了Cache的接口，包括Insert, Lookup, Release等操作。
• ShardedCache
  支持對Cache進(jìn)行分桶，分桶數(shù)量為2^num_shard_bits，每個桶的容量相等。
  分桶的依據(jù)是取key的hash值的高num_shard_bits位

(num_shard_bits_ > 0) ? (hash >> (32 - num_shard_bits_)) : 0;

• LRUCache
  維護(hù)了一個shard數(shù)組，每個shard，即每個桶，都是一個LRUCacheShard用來cache分過來的key value。
• CacheShard
  定義了一個桶的接口，包括Insert, Lookup, Release等操作，Cache的相關(guān)調(diào)用經(jīng)過分桶處理后，都會調(diào)用指定桶的對應(yīng)操作。
• LRUCacheShard
  維護(hù)了一個LRU list和hash table，用來實現(xiàn)LRU策略，他們的成員類型都是LRUHandle。
• LRUHandleTable
  hash table的實現(xiàn)，根據(jù)key再次做了分組處理，并且盡量保證每個桶中只有一個元素，元素類型為LRUHandle。提供了Lookup, Insert, Remove操作。
• LRUHandle
  保存key和value的單元，并且包含前向和后續(xù)指針，可以組成雙向循環(huán)鏈表作為LRU list。
  保存了引用計數(shù)和是否在cache中的標(biāo)志位。詳細(xì)說明如下

LRUHandle can be in these states:

1. Referenced externally AND in hash table.
   In that case the entry is not in the LRU. (refs > 1 && in_cache == true)
2. Not referenced externally and in hash table. In that case the entry is
   in the LRU and can be freed. (refs == 1 && in_cache == true)
3. Referenced externally and not in hash table. In that case the entry is
   in not on LRU and not in table. (refs >= 1 && in_cache == false)

All newly created LRUHandles are in state 1. If you call LRUCacheShard::Release on entry in state 1, it will go into state 2.
To move from state 1 to state 3, either call LRUCacheShard::Erase or LRUCacheShard::Insert with the same key.
To move from state 2 to state 1, use LRUCacheShard::Lookup.
Before destruction, make sure that no handles are in state 1. This means that any successful LRUCacheShard::Lookup/LRUCacheShard::Insert have a matching RUCache::Release (to move into state 2) or LRUCacheShard::Erase (for state 3)

LRUCache結(jié)構(gòu)如下

LRUCache結(jié)構(gòu)

Insert的實現(xiàn)

從上到下逐層分析LRUCache的Insert實現(xiàn)。
RocksDB中，通過一個選項指定所使用的Cache大小，在open的時候傳給DB。

  auto cache = NewLRUCache(1 * 1024 * 1024 * 1024);
  BlockBasedTableOptions bbt_opts;
  bbt_opts.block_cache = cache;

調(diào)用Insert的一例如下

// 從option選項中獲取bock cache的指針
Cache* block_cache = rep->table_options.block_cache.get();
// ...
  if (block_cache != nullptr && block->value->cachable()) {
    s = block_cache->Insert(
        block_cache_key,
        block->value,
        block->value->usable_size(),
        &DeleteCachedEntry<Block>,
        &(block->cache_handle),
        priority);
...

LRUCache的Insert實現(xiàn)在它的基類ShardedCache中，先對key做hash，hash的方法類似murmur hash，然后根據(jù)hash值確定存入到哪一個桶（Shard）中?？梢哉J(rèn)為一個桶就是一個獨立的LRUCache，其類型是LRUCacheShard。

// util/sharded_cache.cc
Status ShardedCache::Insert(const Slice& key, void* value, size_t charge,
                            void (*deleter)(const Slice& key, void* value),
                            Handle** handle, Priority priority) {
  uint32_t hash = HashSlice(key);
  return GetShard(Shard(hash))
      ->Insert(key, hash, value, charge, deleter, handle, priority);
}

通過key確定分桶后，調(diào)用對應(yīng)LRUCacheShard的Insert方法。

Status LRUCacheShard::Insert(const Slice& key, uint32_t hash, void* value,
                             size_t charge,
                             void (*deleter)(const Slice& key, void* value),
                             Cache::Handle** handle, Cache::Priority priority);

LRUCacheShard的三個主要的成員變量，Insert主要是對這三個成員變量的操作。

class LRUCacheShard : public CacheShard {
...
private:
  LRUHandle lru_;  // 鏈表的頭結(jié)點
  LRUHandle* lru_low_pri_; // 指向低優(yōu)先級部分的頭結(jié)點
  LRUHandleTable table_; // 自己實現(xiàn)的一個hash table
};

一個LRUCache的底層實現(xiàn)，是依賴一個鏈表和一個HashTable，鏈表用來維護(hù)成員的淘汰的順序和高低優(yōu)先級，HashTable用來進(jìn)行快速的查找。他們的成員類型是LRUHandle*。后面會詳細(xì)了解他們的功能，下面分析一下Insert的實現(xiàn)，分為下面幾步：

1. 根據(jù)key value等參數(shù)構(gòu)造LRUHandle
2. 加shard級別鎖，開始對LRUCacheShard做修改
3. 根據(jù)LRU策略和空間使用情況進(jìn)行成員淘汰
4. 根據(jù)容量選擇是否插入

• 如果計算發(fā)現(xiàn)，插入后的總的使用量仍然大于cache的容量，并且傳入了需要嚴(yán)格限制flag，則不進(jìn)行插入操作。這里有一個小點是，參數(shù)中handle是一個輸出參數(shù)，插入成功后，賦值為指向cache中的LRUHandle成員的指針。如果用戶傳入的handle為null，說明用戶不需要返回指向成員的handle指針，雖然插入失敗，但是不報錯；否則將handle賦值為null后報錯。
• 如果釋放了足夠的空間，或者不需要嚴(yán)格限制空間使用，則開始進(jìn)行插入操作。首先插入到hash table中，如果已經(jīng)存在key對應(yīng)的entry，則置換出來后，進(jìn)行釋放。

插入后，如果handle為null，說明插入后沒人有持有對這個元素的引用，插入到LRU list中等待被淘汰。否則，暫時不將該元素插入到LRU list中，而是賦值給handle，等調(diào)用者釋放了對該元素的引用，再插入到LRU list中

5. 釋放被淘汰的元素和插入失敗的元素。

Status LRUCacheShard::Insert(const Slice& key, uint32_t hash, void* value,
                             size_t charge,
                             void (*deleter)(const Slice& key, void* value),
                             Cache::Handle** handle, Cache::Priority priority) {
  LRUHandle* e = reinterpret_cast<LRUHandle*>(
      new char[sizeof(LRUHandle) - 1 + key.size()]);
  ... // 填充e
  autovector<LRUHandle*> last_reference_list; //  保存被淘汰的成員
  {
    MutexLock l(&mutex_);
    // 對LRU list進(jìn)行成員淘汰
    EvictFromLRU(charge, &last_reference_list);

    if (usage_ - lru_usage_ + charge > capacity_ &&
        (strict_capacity_limit_ || handle == nullptr)) {
      if (handle == nullptr) {
        // Don't insert the entry but still return ok, as if the entry inserted
        // into cache and get evicted immediately.
        last_reference_list.push_back(e);
      } else {
        delete[] reinterpret_cast<char*>(e); // 沒搞清楚這里為什么立刻刪除，而不是像上面那樣加到last_reference_list中稍后一起刪除
        *handle = nullptr;
        s = Status::Incomplete("Insert failed due to LRU cache being full.");
      }
    } else {
      LRUHandle* old = table_.Insert(e);
      usage_ += e->charge;
      if (old != nullptr) {
        old->SetInCache(false);
        if (Unref(old)) {
          usage_ -= old->charge;
          // old is on LRU because it's in cache and its reference count
          // was just 1 (Unref returned 0)
          LRU_Remove(old);
          last_reference_list.push_back(old);
        }
      }
      if (handle == nullptr) {
        LRU_Insert(e);
      } else {
        // 當(dāng)調(diào)用者調(diào)用Release方法后，會調(diào)用LRU_Insert方法，將該元素插入到LRU list中
        *handle = reinterpret_cast<Cache::Handle*>(e);
      }
      s = Status::OK();
    }
  }
  // 釋放被淘汰的元素
  for (auto entry : last_reference_list) {
    entry->Free();
  }

  return s;
}

上面的流程中，有兩次插入，分別是hash table的插入和鏈表的插入。

LRUHandleTable

• LRUHandleTable內(nèi)部根據(jù)LRUHandle元素中的hash值分桶
• 每個桶是一個鏈表
• 插入時插入到鏈表的尾部。
• 如果元素數(shù)量大于桶的數(shù)量，則對桶的數(shù)量調(diào)整為之前的兩倍，為的是讓一個桶的鏈表長度盡量小于等于1.

class LRUHandleTable {
 public:
  ...
  LRUHandle* Insert(LRUHandle* h);
  ...
private:
  ...
  uint32_t length_;  // 桶的數(shù)量，默認(rèn)數(shù)量為16
  uint32_t elems_;  // 元素總數(shù)
  LRUHandle** list_; // 一維數(shù)組，數(shù)組的成員為每個鏈表的頭指針
};

hash table的Insert實現(xiàn)：

1. 根據(jù)key和hash值，找到對應(yīng)的桶，在桶中沿著鏈表找到key和hash值對應(yīng)的節(jié)點
2. 如果key和hash值對應(yīng)的節(jié)點已經(jīng)存在，則用新的節(jié)點替換老的節(jié)點，將老節(jié)點返回
3. 如果key和hash值對應(yīng)的節(jié)點不存在，則插入到鏈表結(jié)尾，并且判斷是否需要對hash table擴(kuò)容

LRUHandle* LRUHandleTable::Insert(LRUHandle* h) {
  LRUHandle** ptr = FindPointer(h->key(), h->hash);
  LRUHandle* old = *ptr;
  // 如果key已經(jīng)存在，則替換老的元素
  h->next_hash = (old == nullptr ? nullptr : old->next_hash);
  *ptr = h;
  // 如果key不存在，則判斷元素總數(shù)和桶的數(shù)量是否需要擴(kuò)容
  if (old == nullptr) {
    ++elems_;
    if (elems_ > length_) {
      Resize();
    }
  }
  return old;
}

LRUHandle** LRUHandleTable::FindPointer(const Slice& key, uint32_t hash) {
  LRUHandle** ptr = &list_[hash & (length_ - 1)]; // 根據(jù)hash值找到對應(yīng)的桶
  // 沿著鏈表比較key和hash值，直到鏈表尾部
  while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
    ptr = &(*ptr)->next_hash;
  }
  return ptr;
}

LRU list

LRU list按優(yōu)先級分為兩個區(qū)，高優(yōu)先級區(qū)和低優(yōu)先級區(qū)

• lru_為鏈表頭，也是高優(yōu)先級的表頭
• lru_low_pri_為低優(yōu)先級的表頭
• 當(dāng)high_pri_pool_ratio_為0時，表示不分優(yōu)先級，則高優(yōu)先級和低優(yōu)先級的表頭都是LRU list的表頭

插入時，不論是高優(yōu)先級插入還是低優(yōu)先級插入，都插入到表頭位置。
Insert實現(xiàn)如下

void LRUCacheShard::LRU_Insert(LRUHandle* e) {
  assert(e->next == nullptr);
  assert(e->prev == nullptr);
  if (high_pri_pool_ratio_ > 0 && e->IsHighPri()) {
    // Inset "e" to head of LRU list.
    e->next = &lru_;
    e->prev = lru_.prev;
    e->prev->next = e;
    e->next->prev = e;
    e->SetInHighPriPool(true);
    high_pri_pool_usage_ += e->charge;
    MaintainPoolSize();
  } else {
    // Insert "e" to the head of low-pri pool. Note that when
    // high_pri_pool_ratio is 0, head of low-pri pool is also head of LRU list.
    e->next = lru_low_pri_->next;
    e->prev = lru_low_pri_;
    e->prev->next = e;
    e->next->prev = e;
    e->SetInHighPriPool(false);
    lru_low_pri_ = e;
  }
  lru_usage_ += e->charge;
}

以上就是LRUCache的插入流程。

寫的比較匆忙, 很多細(xì)節(jié)也沒有提到, 有寫的不對或者不明確的地方, 請指正, 謝謝!

參考資料：
https://github.com/facebook/rocksdb/wiki/Block-Cache