從LevelDB SnapShot到記憶體快照的思考

文章目錄

• ​​引言​​

• ​​LevelDB SnapShot​​
• ​​MVCC的啟發​​
• ​​可復原資料結構​​
• ​​COW與ROW​​
• ​​Cgroup​​

• ​​總結​​

引言

SnapShot技術在資料庫領域的重要性不言而喻，這種記錄整個資料庫某一時間點全部視圖并快速恢複的能力非常重要，這相當于是一顆後悔藥。存儲網絡行業協會SNIA（StorageNetworking Industry Association）對于Snapshot的定義是：

A point in time copy of a defined collection of data.

而維基對SnapShot的定義是：

a snapshot is the state of a system at a particular point in time.

我們可以看出Snapshot本身是什麼并不重要，可以是其所表示的資料的一個副本，也可以是資料的一個複制品，重要的是其記錄了系統某一個時間點的狀态，這其實類似與Git，LevelDB中的Version以及容器分層的概念，其實就是一個版本控制而已。但是上面術語中定義的SnapShot本身的粒度可能與Git更為類似，因為這兩者的版本概念更為具體，這裡的版本是我們可以直接恢複到的某一個手動執行SnapShot的時間點。

而LevelDB中Version的概念是去辨別SSTable結構的變動，資訊存儲在 MANIFEST 檔案中，這裡的粒度就更細了，當然粒度更細的就是所謂的PITR（Point-in-time recovery）了，可以恢複至任意時間點的資料庫狀态。

扯了一大堆，其實我真正想談的其實是SnapShot本身的開銷問題，不管是Raft算法的SnapShot也好，還是Redis的RDB也罷，本身的開銷其實是不小的，尤其是Redis的RDB，會直接Fork目前主程序，然後會序列化目前的記憶體狀态，當記憶體資料多了以後這顯然是一個既消耗CPU又消耗磁盤帶寬的行為，雖然有ROW。經典的Fork分為兩步，Fork時資源複制時複制頁表項并且将其都設定為隻讀，缺頁異常中識别COW引發的錯誤并實際配置設定資源實作位址空間隔離。父程序記憶體占用過大的時候開始頁表項和vma内容雖然共享，但是本身對象的複制開銷也非常大[10]（好文），其他私有資料也需要拷貝，後面缺頁時還是需要拷貝[8][9].

Raft的Snapshot就不提了，雖然TiKV對Snapshot做了特殊的處理，但是這個處理其實隻是在收發的時候引入SnapChunk，利用了gRPC的Stream發送來防止把SnapShot一次載入記憶體的情況，其實在進行SnapShot的時候還是比較慢，畢竟需要把日志資料存入磁盤，序列化本身的的CPU消耗以及磁盤IO都是需要考慮的。

本質上的問題來源于大量的磁盤IO以及對于CPU資源的消耗，這些都可能會影響到工作線程進而使得服務時延出現毛刺，你可能會說都已經使用了SnapShot了，這種開銷顯然無法避免啊，其實是可以的。首先簡單思考，需要dump到磁盤的原因是因為我們磁盤上沒有存儲已有資料，假如已經有的話我們是否可以利用呢？

顯然在現代資料庫資料庫中MVCC和LSM Tree的出現頻率已經非常高了，我們能否基于這兩個機制的備援資料做到零開銷的記憶體快照呢？其實LevelDB中的SnapShot我個人認為實作的非常優秀，其可以幾乎零開銷的生成一個SnapShot（配置設定一個SSequenceNumber而已），雖然這個快照是隻讀的。

LevelDB SnapShot

我們來看一看LevelDB的SnapShot是如何實作的，首先前置知識是SSTable中Block的資料被組織為這樣：

其中的key會被壓縮，但是每分隔16個就會全量存儲，後面restarts記錄的是這些全量存儲的offset。

其中key的資料被組織為這樣：

// klength varint32

// userkey char[klength]

// tag (sequence + type) uint64

也就是所有的key其實都帶着一個sequence。

然後我們再來看看​

​InternalKeyComparator::Compare​

​：

int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
  // 首先根據user key按升序排列
  // 然後根據sequence number按降序排列
  // 最後根據value type按降序排列
  int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
  if (r == 0) {
    const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
    const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
    if (anum > bnum) {
      r = -1;
    } else if (anum < bnum) {
      r = +1;
    }
  }
  return r;
}      

LevelDB擷取SnapShot的接口為​

​Snapshot* GetSnapshot()​

​，我們來看看其實作：

typedef uint64_t SequenceNumber;

class SnapshotImpl : public Snapshot {
 public:
  SnapshotImpl(SequenceNumber sequence_number)
      : sequence_number_(sequence_number) {}

  SequenceNumber sequence_number() const { return sequence_number_; }

 private:
  friend class SnapshotList;

  // SnapshotImpl is kept in a doubly-linked circular list. The SnapshotList
  // implementation operates on the next/previous fields direcly.
  SnapshotImpl* prev_;
  SnapshotImpl* next_;

  const SequenceNumber sequence_number_;

#if !defined(NDEBUG)
  SnapshotList* list_ = nullptr;
#endif  // !defined(NDEBUG)
};      

可以看到其實隻有1個uin64_t類型的成員，根據這個SequenceNumber和上面的比較運算符，我們就可以在Get的時候拼接出一個帶着某個SnapShot的SequenceNumber的key，然後去取資料了，這部分代碼我們在​

​DBImpl::Get​

​也可以找到：

;
  if (options.snapshot != nullptr) {
    snapshot =
        static_cast<const SnapshotImpl*>(options.snapshot)->sequence_number();
  } else {
    snapshot = versions_->LastSequence();
  }      

當然最大的問題在于Compaction的時候可能會把某些老舊的key删除掉，這個問題很好解決，代碼在​

​DoCompactionWork​

​中，也就是在compaction中判斷哪些key需要丢棄的時候引入對于snapshot的判斷：

// 是否可以丢掉目前kv對，預設是否
    bool drop = false;
    if (!ParseInternalKey(key, &ikey)) {
      // Do not hide error keys
      current_user_key.clear();
      has_current_user_key = false;
      last_sequence_for_key = kMaxSequenceNumber;
    } else {
      if (!has_current_user_key ||
          user_comparator()->Compare(ikey.user_key, Slice(current_user_key)) !=
              0) {
        // 該user_key是第一次出現
        current_user_key.assign(ikey.user_key.data(), ikey.user_key.size());
        has_current_user_key = true;
        //因為第一次出現的user_key不允許删除，所有将last_sequence_for_key設為最大值
        last_sequence_for_key = kMaxSequenceNumber;
      }

      if (last_sequence_for_key <= compact->smallest_snapshot) {
        // 已經有相同user_key出現了，并且上一個user_key的sequenceNumber還小于等于
        // compact->smallest_snapshot,注意直到遇到第二個user_key的sequenceNumber
        // 小于等于smallest_snapshot才能丢棄
        drop = true;  // (A)
      } else if (ikey.type == kTypeDeletion &&
                 ikey.sequence <= compact->smallest_snapshot &&
                 // 在下面的層級中這個key不存在了
                 compact->compaction->IsBaseLevelForKey(ikey.user_key)) {
        //目前kv是距離最小版本smallest_snapshot最近的user_key,但因為它是條删除操作，并且
        //沒有已經比它還老的user_key了。所有可以丢棄掉。
        //對于已經存在的key在第一個條件中已經被删除了
        // For this user key:
        // (1) there is no data in higher levels
        // (2) data in lower levels will have larger sequence numbers
        // (3) data in layers that are being compacted here and have
        //     smaller sequence numbers will be dropped in the next
        //     few iterations of this loop (by rule (A) above).
        // Therefore this deletion marker is obsolete and can be dropped.
        drop = true;
      }

      last_sequence_for_key = ikey.sequence;
    }      

這樣即可保證Snapshot存在時比其SequenceNumber小的資料中最新的那一個不會被删，進而保證SnapShot可以讀到最新的資料。

MVCC的啟發

這裡其實給了我新的想法，這種方法能否利用在MVCC中呢，因為MVCC中也有備援資料，我們完全可以基于時間來做SnapShot，不過這要求MVCC的垃圾回收需要重新設計，因為其需要考慮到已有的Snapshot，如果做的好，這項工作可以使得基于MVCC的資料庫都可以立馬擁有完美的零開銷的記憶體快照功能。

這其實很好了解，因為處于RR隔離級别來看，事務眼中确實就是一個不可變的視圖，為什麼我們不能把這看作一個SnapShot呢。

我認為這是一個很有價值的思考，我想後續可以找機會調研下這項工作。

可復原資料結構

第一次學習到這個概念實在學習HAMT(Hash Array Mapped Trie)時了解到的[4]，具體可以參考[5]進行學習，這其實也是一種forkless的思路。

COW與ROW

COW（Copy-On-Write）與ROW（Redirect-on-write）是經典的SnapShot的實作方案，感覺上就是以Page為機關去做SnapShot了，這其實資料抽象（也就是如何用到我們的代碼中）也需要一些時間，但是确實是很有用的，因為把一次很大的資源消耗均攤到多次操作中了，基本上就是一種惰性的思路，具體可以參考[2][6]。

在[6]的評論區提到NetApp有一種很優秀的SnapShot的實作方案，但是看了[7]以後，覺得原理類似與ROW類似。

當然Redis的RDB本質上就是一種COW的實作，在Fork以後直接在子程序執行資料的RDB操作，代碼在rdb.c中可以看到。

Cgroup

前面提到Fork的方案會帶來一些問題，如果我們已有的代碼無法支援我們像是LevelDB一樣做這種輕量級的快照，我們怎麼才能保證快照的過程不影響工作線程呢，顯然資源隔離的方案是一個看起來不錯的實作，我們可以起一個程序，對其隔離資源，然後通過工作線程的LOG去做SnapShot，顯然這也是一種可行的做法。

總結

1. ​​TiKV 源碼解析系列文章（十）Snapshot 的發送和接收​​
2. ​​揭秘：存儲快照的實作​​
3. ​​Snapshot (computer storage) wiki​​
4. ​​抛棄哈希表？持久化資料結構HAMT探究​​
5. ​​Functional Go: 持久化資料結構簡介​​
6. ​​存儲系統的快照技術​​
7. ​​NetApp Snapshot Technology​​
8. ​​Linux 系統調用 —— fork()核心源碼剖析​​
9. ​​linux fork COW機制分析​​
10. ​​Linux fork那些隐藏的開銷​​