日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

Rocksdb?Memtable數據結構源碼解析_Android

作者：開務數據庫 ? 更新時間： 2022-12-14 編程語言

一、什么是 Memtable？

Memtable 是 Rocksdb 在內存中保存數據的一種數據結構，一個 Memtable 的容量是固定的，在 Memtable 寫滿后，會轉換為 Immutable Memtable，Immutable Memtable 中的數據會 Flush 到 SST File 中。

Memtable 和 Immutable Memtable 的唯一區別是 Memtable 可讀可寫，而 Immutable Memtable 是只讀且不允許寫入。Rocksdb 引入了 Column Family 的概念，在一個 Column Family 中只有一個 Memtable，但允許存在多個 Immutable Memtable。Rocksdb 支持創建多數據結構類型的 Memtable，默認的是 SkipList，即跳躍表。

二、Memtable 的數據結構

Rocksdb 中 Memtable 有多種實現方式 (SkipList / HashSkipList / HashLinkList / Vector)，其中默認的實現方式為 SkipList。

一個 Memtable 中維護了兩個 SkipList，其中范圍刪除插入 range_del_table_，其余的操作寫入 table_。

Memtable 定義的操作接口 Add () 如下：

bool MemTable::Add(SequenceNumber s, ValueType type,
                   const Slice& key, /* user key */
                   const Slice& value, bool allow_concurrent,
                   MemTablePostProcessInfo* post_process_info) {
  // 一條key-value Entry的數據格式
  //  key_size     : varint32 of internal_key.size()
  //  key bytes    : char[internal_key.size()]
  //  value_size   : varint32 of value.size()
  //  value bytes  : char[value.size()]
  uint32_t key_size = static_cast<uint32_t>(key.size());
  uint32_t val_size = static_cast<uint32_t>(value.size());
  uint32_t internal_key_size = key_size + 8;
  const uint32_t encoded_len = VarintLength(internal_key_size) +
                               internal_key_size + VarintLength(val_size) +
                               val_size;
  char* buf = nullptr;
  // 通過判斷key-value的類型來選擇memtable, 范圍刪除的kv插入range_del_table_
  std::unique_ptr<MemTableRep>& table =
      type == kTypeRangeDeletion ? range_del_table_ : table_;
  KeyHandle handle = table->Allocate(encoded_len, &buf);
  //...
  // 是否允許并發插入
  if (!allow_concurrent) {
    // 是否制定了函數提取key的前綴
    if (insert_with_hint_prefix_extractor_ != nullptr &&
        insert_with_hint_prefix_extractor_->InDomain(key_slice)) {
      // ...
      bool res = table->InsertWithHint(handle, &insert_hints_[prefix]);
    } else {
      // 插入key-value pair
      bool res = table->Insert(handle);
      if (UNLIKELY(!res)) {
        return res;
      }
    }
  } else {
    // 插入key-value pair
bool res = table->InsertConcurrently(handle);
    if (UNLIKELY(!res)) {
      return res;
    }
  }
  return true;
}

Add () 函數將用戶的 key 和 value 封裝成一個 buf，然后根據不同的條件調用 table->Insert () 插入至 Memtable。table 就是 Memtable 的工廠類實現，默認 SkiplistRep, 即通過調用 SkipList 的 Insert () 完成 key 的插入。

Memtable 定義的操作接口 Get () 如下：

bool MemTable::Get(const LookupKey& key, std::string* value, Status* s,
                   MergeContext* merge_context,
                   RangeDelAggregator* range_del_agg, SequenceNumber* seq,
                   const ReadOptions& read_opts, ReadCallback* callback,
                   bool* is_blob_index) {
  // 在range_del_table_上初始化一個迭代器
  std::unique_ptr<InternalIterator> range_del_iter(
      NewRangeTombstoneIterator(read_opts));
  Status status = range_del_agg->AddTombstones(std::move(range_del_iter));
  if (!status.ok()) {
    *s = status;
    return false;
  }
  Slice user_key = key.user_key();
  // 利用前綴提取過濾判斷key是否存在
  bool const may_contain =
      nullptr == prefix_bloom_

Memtable 的 Get () 調用了 SkipListRep 的 Get () 接口，最終是通過 SkipList 的 FindGreaterOrEqual () 來查找。查找出來的 key 會被傳入的回調函數 SaveValu 并 e () 根據 type 處理，例如 ktypeDeletion 就返回 NotFound ()。

三、什么是 SkipList？

SkipList 即跳躍表，在普通單向鏈表的基礎上增加了一些索引，而且這些索引是分層的，從而可以快速地查到數據。如下是一個典型的跳躍表構建過程：

初始我們有個帶頭結點的有序鏈表 a，而后每相鄰兩個節點增加一個指針，讓指針指向下下個節點，得到表 b。這樣所有新增指針連成了一個新的鏈表，但它包含的節點個數只有原來的一半。其后我們對第二層鏈表再次進行此操作，得到表 c。重復這個過程，直到采樣出的節點只剩一個，如圖 d。這樣便完成了跳躍表的構建。跳躍表查找過程如下：

從 head 開始，head 的 level 為 4，判斷 head 后繼節點值小于 <12，此時當前節點變為 6，繼續查找；

節點 6 的 level 為 3，判斷后繼節點值為 NIL，因此 level 降低到 2；

判斷 x -> forward [2] -> key (25) > 17，繼續降低 level 到 1；

判斷 x -> forward [1] -> key (9) < 17，此時 x 變為 x ->forward [1]，x 成為節點 9；

節點 9 的判斷 x -> forward [1] -> key 為 17，因此找到節點，直接返回。

跳躍表插入過程如下：

我們以上圖為例，list -> leve=4，如果要插入節點 17，首先確定搜索路徑，與之前步驟類似。

創建新節點 Node (17)，并為其生成 level (隨機)，該 level 可能值為 [1, MaxLevel]，此時需要對比，如果 level < list -> level，需要先將突出部分從 header 指向它，這里新生成的節點 Node (17) 的 level 為 5，超過了 list 當前的最大 level，于是將 update [4] 設置為 header，后續直接將 Node (17) 作為 header 的后繼。

最后是設置搜索路徑上每個節點的后繼關系，這樣我們便完成了節點的插入。我們來看一下 SkipList 的具體代碼實現：

InlineSkipList 數據結構 >>

class InlineSkipList {
 private:
  struct Node;
  struct Splice;
 public:
  using DecodedKey = \
    typename std::remove_reference<Comparator>::type::DecodedType;
…
  Allocator* const allocator_; 
  Comparator const compare_;
  Node* const head_;
  std::atomic<int> max_height_;  
  Splice* seq_splice_;
};

Node 的數據結構 >>

template <class Comparator>
struct InlineSkipList<Comparator>::Node {
 private:
  // 存放該節點的next_節點的數組
  // 數組大小為該節點的height，當調用NewNode()分配內存初始化整個數組
  std::atomic<Node*> next_[1];
};

Node 的數據結構如圖，它將 key 和鏈表每層的指針連續存儲，通過 next_[-n] 這種方式來訪問每層的 next 指針，此外在 new 新節點時會把該節點高度寫在 next_[0] 的前 4 個字節處，當完成插入后，next_[0] 會恢復成指向同層的下一個節點的指針。

四、InlineSkipList 插入

Memtable 的 Add () 通過 SkipList 的 Insert () 來查找，下面是 Insert () 的具體實現：

bool InlineSkipList<Comparator>::Insert(const char* key, Splice* splice,
                                        bool allow_partial_splice_fix) {
  Node* x = reinterpret_cast<Node*>(const_cast<char*>(key)) - 1; // x即為next_[0]
  const DecodedKey key_decoded = compare_.decode_key(key);
  int height = x->UnstashHeight();
  assert(height >= 1 && height <= kMaxHeight_);
  int max_height = max_height_.load(std::memory_order_relaxed);
  // 更新max_height
  while (height > max_height) {
    if (max_height_.compare_exchange_weak(max_height, height)) {
      // successfully updated it
      max_height = height;
      break;
    }
    // 否則重試，可能因為其他人增加了它而退出循環
  }
  assert(max_height <= kMaxPossibleHeight);
  // 插入節點的時候，需要借助一個Splice對象，該對象主要保存著最近一次插入的節點快照
  // 它保存著一個prev和next的節點指針數組，由Level可以索引到對應Level的節點
  int recompute_height = 0;
  if (splice->height_ < max_height) {
    // 當重置splice
    splice->prev_[max_height] = head_;
    splice->next_[max_height] = nullptr;
    splice->height_ = max_height;
    recompute_height = max_height;
  } else {
    while (recompute_height < max_height) {
      if (splice->prev_[recompute_height]->Next(recompute_height) !=
          splice->next_[recompute_height]) { //判斷該層的splice是否緊密，即prev_->Next是否等于next_
        ++recompute_height;
      } else if (splice->prev_[recompute_height] != head_ &&
                 !KeyIsAfterNode(key_decoded,
                                 splice->prev_[recompute_height])) { //小于splice當前層的prev_
        // ...
      } else if (KeyIsAfterNode(key_decoded,
                                splice->next_[recompute_height])) { //大于splice當前層的prev_
        // ...
      } else {
        // 找到了合適的level
        break;
      }
    }
  }
  assert(recompute_height <= max_height);
  if (recompute_height > 0) {//計算splice
    RecomputeSpliceLevels(key_decoded, splice, recompute_height); // 找到要插入的key合適的splice
  }
  bool splice_is_valid = true;
  if (UseCAS) {//CAS無鎖機制
    //...
  } else {
    for (int i = 0; i < height; ++i) {
      if (i >= recompute_height &&
          splice->prev_[i]->Next(i) != splice->next_[i]) { // 確保splice此Level有效，如果無效的話再查找一次
        FindSpliceForLevel<false>(key_decoded, splice->prev_[i], nullptr, i,
                                  &splice->prev_[i], &splice->next_[i]);
      }
      // Checking for duplicate keys on the level 0 is sufficient
      if (UNLIKELY(i == 0 && splice->next_[i] != nullptr &&
                   compare_(x->Key(), splice->next_[i]->Key()) >= 0)) {
        // duplicate key
        return false;
      }
      if (UNLIKELY(i == 0 && splice->prev_[i] != head_ &&
                   compare_(splice->prev_[i]->Key(), x->Key()) >= 0)) {
        // duplicate key
        return false;
      }
      //…
      x->NoBarrier_SetNext(i, splice->next_[i]); //將新節點next指向對應的next節點
      splice->prev_[i]->SetNext(i, x); //將splice的prev節點的next指向新節點
    }
  }
  if (splice_is_valid) {//將新節點Height下的prev節點都設置為該節點，因為原先的prev和next之間已經不連續了。
    for (int i = 0; i < height; ++i) {
      splice->prev_[i] = x;
    }
    //...
  } else {
    splice->height_ = 0;
  }
  return true;
}

五、InlineSkipList 查找

Memtable 的 Get () 通過 SkipList 的 FindGreaterOrEqual () 來查找，下面是 FindGreaterOrEqual () 的具體實現：

InlineSkipList<Comparator>::FindGreaterOrEqual(const char* key) const {
  Node* x = head_;
  int level = GetMaxHeight() - 1;//從最高層開始查找
  Node* last_bigger = nullptr;
  const DecodedKey key_decoded = compare_.decode_key(key);
  while (true) {
    Node* next = x->Next(level); 
    if (next != nullptr) {
      PREFETCH(next->Next(level), 0, 1);
    }
    // Make sure the lists are sorted
    assert(x == head_ || next == nullptr || KeyIsAfterNode(next->Key(), x));
    // Make sure we haven't overshot during our search
    assert(x == head_ || KeyIsAfterNode(key_decoded, x));
    int cmp = (next == nullptr || next == last_bigger)
                  ? 1
                  : compare_(next->Key(), key_decoded);
    if (cmp == 0 || (cmp > 0 && level == 0)) { // 找到相等的key或者查找的key不在此范圍內
      return next;
    } else if (cmp < 0) { //待查找 key 比 next 大，則在該層繼續查找
      x = next;
    } else { // 待查找 key 不大于 next，且沒到底，則繼續往下層查找
      // Switch to next list, reuse compare_() result
      last_bigger = next;
      level--;
    }
  }
}

原文鏈接：https://juejin.cn/post/7166510918048677895

欄目分類
最近更新