Kvrocks 設計與實現

「Kvrocks: 一款開源的企業級磁盤 KV 存儲服務」對 Kvrocks 進行了整體性的介紹，本文從關鍵設計和內部實現來分析，希望對於想知道如何實現磁盤類型 Redis，以及想熟悉 Kvorcks 設計和實現的人帶來一些幫助。

內部設計

Kvrocks 在內部設計上主要拆分成幾個部分:

Redis 協議接收和解析模塊，負責解析網絡請求和解析 Redis 協議，相比 Redis 來說，Kvrocks 在 IO 處理以及命令執行都是多線程模型；
數據結構轉換模塊，負責將 Redis 複雜類型轉爲 RocksDB 可處理的簡單 KV，不同類型在設計上會有一些小差異；
數據存儲模塊，Kvrocks 底層使用 RocksDB 並對其做了不少針對性的性能優化，文章「Kvrocks 在 RocksDB 上的優化實踐」進行了詳細說明，感興趣的同學可以前往閱讀；
主從複製模塊，類似 Redis 的異步複製的方式，每個從庫都會創建一個對應的複製線程。在實現方面，使用 RocksDB CheckPoint + WAL 來實現全量和增量同步；
集羣模塊，包含 Redis 集羣協議兼容以及在線遷移的功能。這部分沒有在上面的架構圖中體現，感興趣可以參考: 「Kvrocks 集羣方案簡介」。

下圖爲 Kvrocks 的整體設計示意圖:

除此之外，代碼裏面還有一些後臺線程 (Compaction Checker) 、任務的線程池以及統計功能由於篇幅關係沒有體現。

Redis 協議解析

Kvrocks 目前支持的還是 RESP 2 的協議，請求協議解析的相關代碼都在 src/redis_request.cc 這個代碼文件裏面。相比於 Redis 的實現，Kvrocks 並沒有自己實現接收和發送網絡包邏輯，而直接使用比較成熟 Libevent 網絡庫，主要的原因多線程場景下，Libevent 的性能已經足夠好，瓶頸主要在磁盤 IO, 沒必要自己再造輪子。

解析請求的核心代碼只是一個幾十行代碼的狀態機，簡化後的代碼如下:

Status Request::Tokenize(evbuffer *input) {
  ...
  while (true) {
    switch (state_) {
      case ArrayLen: // 讀取協議的元素個數
        line = evbuffer_readln(input, &len, EVBUFFER_EOL_CRLF_STRICT);
        if (line[0] == '*') {
          multi_bulk_len_ = std::stoull(std::string(line + 1, len-1));
          state_ = BulkLen;
        }
        ...
        break;
      
      case BulkLen: // 讀取元素長度
        line = evbuffer_readln(input, &len, EVBUFFER_EOL_CRLF_STRICT);
        bulk_len_ = std::stoull(std::string(line + 1, len-1));
        state_ = BulkData;
        break;
     
      case BulkData: // 讀取元素數據
        char *data = evbuffer_pullup(input, bulk_len_ + 2);
        if (--multi_bulk_len_ == 0) {
          state_ = ArrayLen;
          ...
        }
        state_ = BulkLen;
        break;
    }
  }
}

協議解析的初始化狀態是要讀取到單個請求的長度，預期是以 * 字符開頭，後面跟着請求的元素個數。以 GET test_key 爲例，那麼第一行數據是 *2\r\n 表示該請求有兩個元素。接着，第一個元素 GET 是 3 個字符，表示爲 Bulk String 則爲 $3\r\nGET\r\n, $ 開頭爲元素的長度。同理，test_key 則是 $8\r\ntest_key\r\n, 那麼完整的請求變成 Redis 協議則是: *2\r\n$3\r\nGET\r\n$8\r\ntest_key\r\n。

src/redis_reply.cc 裏面跟請求協議解析過程剛好相反，實現的功能則是把返回給客戶端的數據轉爲 Redis 的協議格式。

數據編碼

由於底層存儲引擎是 RocksDB，只提供簡單的 Get/Set/Delete 以及 Scan 接口。在接收到請求之後，Kvrocks 需要對 Hash/List/Set/ZSet/Bitmap 等複雜數據結構的請求進行編碼，轉爲簡單 RocksDB KV 來進行讀寫。目前大部分數據都存儲在以下兩個 Column Family 裏面:

Metadata Column Family，用來存儲 Key 的元數據信息。以 Hash 爲例，每個 Hash 都會在這個 Metadata Column Family 存儲一個元數據的 KV，Key 就是用戶請求的 Hash Key，Value 包含：數據類型，版本號，過期時間以及 Hash 的子元素個數
Subkey Column Famliy, 用來存儲 Hash 對應的子元素和對應的值，這個 Column Family 的 Key 組成是: Hash Key + 版本號 + 子字段的 Key，Value 是子元素對應的具體值

整體示意圖如下:

版本號是根據當前時間自動創建一個隨機遞增的數值，目的是爲了實現快速刪除，避免刪除大 Hash 時產生慢請求。比如，第一次寫入版本號爲 V1，包含 N 個元素，在刪除或者過期之後再重新寫入則會產生新的版本號 V2，由於查找時需要先找到當前活躍版本號，再拼接成子元素的 Key 再查找對應的值。相當於老版本的子元素都變成不可見，這些數據會在後臺 Compaction 時自動回收，變相實現了異步刪除。

假設寫入的 hash_key 裏面有兩個元素 field1 和 field2，那麼 Metadata Column Family 裏面會寫入一條 hash_key 對應的元數據，值會包含幾個字段:

Flags 會標識這個類型爲 Hash
Expired 如果沒有過期時間該值爲 0，否則就是對應的過期時間絕對值
Version 每次創建會自動創建的隨機遞增數值，用來標識當前活躍的版本號
Size 爲當前 Hash 的元素個數

查找時，根據 Hash Key 先在 Metadata Column Family 找到對應的元數據，然後通過 Hash Key + 元數據的版本號 + 子元素的 Key 拼接成爲查找的 Key 後從 SubKey Column Family 找到元素值，其他操作也是同理。

更多編碼結構可以參考文檔: Design Complex Structure On RocksDB[1], 具體代碼實現都在 redis_hash.cc 裏面，其他數據結構也是同理。其中 Bitmap 爲了減少寫放大也做了設計上的優化，具體請參考: 「如何基於磁盤 KV 實現 Bitmap」

Lua 和事務

Kvrocks 是目前開源磁盤 Redis 裏面同時支持 Lua 和事務的選型，同時在命令支持上也是比較完善。爲了簡化實現複雜度，Lua 和事務相關命令執行時會限制爲類似 Redis 的單線程執行。實現方式是在 Lua 和事務相關執行命令加上全局鎖，代碼如下:

if (attributes->is_exclusive()) {   // 是否爲互斥執行命令
 exclusivity = svr_->WorkExclusivityGuard();
} else {
   concurrency = svr_->WorkConcurrencyGuard();
}

全局鎖會導致 Lua 和事務的性能退化爲單線程性能，但就如「Spanner: Google’s Globally-Distributed Database[2]」所說，業務解決性能問題會比解決功能缺失更加簡單得多，性能問題業務總有辦法去繞過而功能則很難。所以相比於功能完整性來說，少數命令的性能衰退是可接受的。

在 Lua 實現上，爲了和 Redis 行爲保持一致，Kvrocks 也是選擇 Lua 5.1 版本。但實現上有一些差異，Redis 當前版本的 Lua 腳本做不會持久化，重啓之後會丟失，而 Kvrocks 會持久化到磁盤且自動同步到從庫，具體實現見: PR 363[3] 和 PR 369[4]。此外，在後續計劃中，我們會支持設置 Lua 腳本名字的功能並按名字進行調用，類似數據庫的存儲過程功能，具體討論見: Issue 485[10]

在事務方面，Kvrocks 目前支持 Multi/Exec 命令，實現也是跟 Redis 類型，對於 Multi 和 Exec 之間的命令先緩存在內存中，收到 Exec 命令之後纔開始執行這行命令。目前實現上存在一個小問題是，雖然執行過程中可以保證單線程但寫 Batch 不是原子，所以可能在極端場景下，寫到一半服務掛了則可能部分 Batch 成功的情況，具體討論見: Transaction can't guarantee atomicity[5]，目前社區也在跟進和解決這個問題。

存儲

除了將複雜數據結構轉爲簡單 KV 的設計之外，需要在存儲層面也有很多優化細節需要去做。Kvrocks 底層的單機存儲引擎使用的是 RocksDB，相比於 LevelDB 除了性能方面有比較大提升之外，在特性方面也是存儲引擎裏面最爲豐富的，包含 Backup、CheckPoint 以及 Compact Filter 等功能。當然，RocksDB 除了豐富的特性之外，在配置方面也比 LevelDB 複雜不少，需要針對不同業務場景來提供最佳配置也是比較大的挑戰。文章「Kvrocks 在 RocksDB 上的優化實踐」對於 RocksDB 參數優化進行了詳細的說明。除此之外，Kvrocks 在 Compaction 以及 Profiling 部分也做了一些優化:

增量 Compaction，之前除了 RocksDB 的自動 Compaction 之外，允許通過配置 compact-cron 來配置全量 Compaction 的時機。一般配置在每天流量低峯做一次，這種方式對於小實例問題不大，而對於大實例則對磁盤 IO 會有比較長時間的影響。後面通過支持增量檢查 SST 的方式實現增量 Compaction，同時也允許配置檢查的時間段，只在低峯時段做增量 Compaction。具體見: compaction-checker-range 配置，實現: PR 98[6]
動態 Profiling 開關，線上最常見的問題是遇到 RocksDB 有慢請求，如果在非 IO 性能瓶頸的場景很難定位到問題。Kvrocks 支持通過在線配置 profiling 採樣的方式來做性能分析，目前支持幾個選項:
profiling-sample-ratio，默認值爲 0，不開啓採樣，取值範圍 0-100
profiling-sample-record-max-len，默認值 256，只保留最近 N 條採樣記錄
profiling-sample-record-threshold-ms，默認 100ms，只保留超過 100ms 的採樣記錄
profiling-sample-commands，默認爲空，* 表示全部命令都採樣，也可以配置多個命令，使用逗號分割
動態調整 SST 大小，之前遇到性能毛刺點問題基本都是由於 SST 過大，讀取 Filter/Index 過慢導致請求，通過支持根據一段時間寫入 KV 大小調整 SST 文件可以有效的緩解該問題。在 2.0.5 版本引入了 Partition Index 功能，不再有類似問題，所以動態調整功能也隨之下線

其他比較經常被提到的問題是: 「Kvrocks 過期或者刪除數據如何回收？」，這個是通過 RocksDB 支持 Compact Filter 特性，在 Compaction 階段對這些過期或者刪除數據進行回收。

主從複製

上面內容主要是關於如何實現單機版本的磁盤 Redis，而對於分佈式服務來說，Kvrocks 另外兩個很重要的功能特性是: 集羣和複製。由於集羣有其他文章專門分享，這裏只關注複製部分。在 2.0 版本之前 Kvrocks 使用 RocksDB Backup + WAL 來做全量和增量複製，創建 Backup 時需要拷貝全部的 DB 文件，導致全量同步時磁盤 IO 持續變高，從而影響服務的響應延時。在 2.0 開始使用 CheckPoint 替換 Backup，CheckPoint 在同步目錄和 DB 目錄在同一個文件系統時會使用硬連接而不是拷貝，所以全量同步創建 CheckPoint 對磁盤 IO 幾乎沒有影響，同時整個過程的耗時也比創建 Backup 低很多。

整體流程如下:

從庫啓動時，先檢查 Auth 和 DB Name 是否正確，DB Name 主要是爲了防止從庫連錯主庫而導致數據被覆蓋；
接着從庫發送當前 DB 的 Sequence Number，主庫根據 Sequence Number 確認是否可以進行增量同步；
如果 Sequence Number 在當前保留的 WAL 範圍之內，則允許增量同步，使用 RocksDB 的 GetUpdateSince API 將 Sequence 之後的寫入批量同步到從庫。否則，進入全量同步 (Full Sync) 流程；
全量同步過程中，從庫先發送 Fetch Meta 來獲取 Meta 數據，主庫會先創建 CheckPoint，併發送全量同步的 Meta 信息到從庫（Meta 主要包含了需要拉取的文件列表）。
從庫根據 Meta 信息主動批量拉取 CheckPoint 文件，如果已經在從庫存在的文件則會跳過。同時，從庫拉取文件可能佔用比較多的帶寬，可以通過配置 max-replication-mb 來限制拉取的帶寬，默認是不限制；
全量同步成功之後回到 Step 2，重新嘗試增量同步，以此循環直到成功爲止。

總結

不管從功能設計還是行爲上，Kvrocks 始終以和 Redis 保持一致爲目標，致力讓用戶在體驗上和 Redsis 做到完全無縫，但 Kvrocks 也不會受限於 Redis，我們也會根據 Kvrocks 磁盤存儲的特性，對部分 Redis 行爲進行改進和優化。演進方向上，2021 年已經完成的 Milestone 2.0[7] 是 Kvrocks 功能上的重大里程碑，而 2022 年的 Milestone 3.0[8] 則是在雲原生的重要里程碑。我們努力讓 Kvrocks 在雲上使用、性能以及運維都能夠變得更友好。

另外，作爲純開源社區和組織，目標達成完全靠社區貢獻者的不懈努力和無私付出，希望有更多人使用、反饋和參與開源社區的建設。而對於我們能做的是如 Code Of Conductor 所提及，保持透明、尊重和友好的社區交流，讓每個 PR 都能在社區找到上下文，讓每個人都能輕鬆地參與到社區討論和貢獻，也讓每個人的貢獻都能被看見。

參考資料

[1] Design Complex Structure On RocksDB: https://github.com/KvrocksLabs/kvrocks/blob/unstable/docs/metadata-design.md

[2] Spanner: Google’s Globally-Distributed Database: https://static.googleusercontent.com/media/research.google.com/en//archive/spanner-osdi2012.pdf

[3] PR 363: https://github.com/KvrocksLabs/kvrocks/pull/363

[4] PR 369: https://github.com/KvrocksLabs/kvrocks/pull/369

[5] Transaction can't guarantee atomicity: https://github.com/KvrocksLabs/kvrocks/issues/487

[6] PR 98: https://github.com/KvrocksLabs/kvrocks/pull/98

[7] 2.0: https://github.com/KvrocksLabs/kvrocks/projects/1

[8] 3.0: https://github.com/KvrocksLabs/kvrocks/projects/2

[9] Code Of Conductor: https://github.com/KvrocksLabs/kvrocks/blob/unstable/CODE_OF_CONDUCT.md

[10] Issue 485: https://github.com/KvrocksLabs/kvrocks/issues/485

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/fbpKGXDhM1ouRdAuRLCCpQ