B站這個分散式KV儲存設計，我一鍵三連了

叢集的拓撲結構包含了幾個概念，分別是Pool、Zone、Node、Table、Shard 與Replica。

• Pool 為資源池連通域，包含多個可用區。也可用於業務資源隔離域。

• Zone 為可用區，同一個pool內部的zone是網路聯通並且故障隔離的。通常為一個機房或者一個交換機

• Node 為實際的物理主機節點，負責具體的資料儲存邏輯與資料持久化。

• Table 對應到具體的業務表，類似MySQL裡的表。

• Shard 為邏輯分片，通過將table分為多個shard將資料打散分佈。

• Replica 為shard的副本，同一個shard的不同副本不能分佈在同一個zone，必須保證故障隔離。每一個replica包含一個engine，engine儲存全量的業務資料。engine的實現包含rocksdb和sparrowdb。其中sparrowdb是針對大value寫放大的優化實現。

由於LSM tree的寫入特性，資料需要被不斷的compaction到更底層的level。在compaction時，如果該key還有效，那麼會被寫入到更底層的level裡，如果該key已經被刪除，那麼會判斷當前level是否是最底層的，一條被刪除的key，會被標記為刪除，直到被compaction到最底層level的時候才會被真正刪除。compaction的時候會帶來額外的寫放大，尤其當value比較大的時候，會造成巨大的頻寬浪費。為了降低寫放大，我們參考了Bitcask實現了kv分離的儲存引擎sparrowdb.

1）sparrowdb 介紹

用 戶寫入的時候，value通過append only的方式寫入data檔案，然後更新索引資訊，索引的value包含實際資料所在的data檔案id，value大小以及position資訊，同時data檔案也會包含索引資訊。 與原始的bitcask實現不一樣的是，我們將索引資訊儲存在 rocksdb。

更新寫入的時候，只需要更新對應的索引即可。compaction的時候，只需將索引寫入底層的level，而無需進行data的拷貝寫入。對於已經失效的data，通過後臺執行緒進行檢查，當發現data檔案裡的索引與rocksdb儲存的索引不一致的時候，說明該data已經被刪除或更新，資料可以被回收淘汰。

使用kv儲存分離降低了寫放大的問題，但是由於kv分離儲存，會導致讀的時候多了一次io，讀請求需要先根據key讀到索引資訊，再根據索引資訊去對應的檔案讀取data資料。為了降低讀訪問的開銷，我們針對value比較小的資料進行了inline，只有當value超過一定閾值的時候才會被分離儲存到data檔案。通過inline以及kv分離獲取讀效能與寫放大之間的平衡。

在分散式系統中，負載均衡是繞不過去的問題。一個好的負載均衡策略可以防止機器資源的空閒浪費。同時通過負載均衡，可以防止流量傾斜導致部分節點負載過高從而影響請求質量。對於儲存系統，負載均衡不僅涉及到磁碟的空間，也涉及到機器的記憶體、cpu、磁碟io等。同時由於使用raft進行主從選主，保證主節點儘可能的打散也是均衡需要考慮的問題。

1）副本均衡

由於設計上我們會盡量保證每個副本的大小盡量相等，因此對於空間的負載其實可以等價為每塊磁碟的副本數。建立副本時，會從可用的zone中尋找包含副本數最少的節點進行建立。同時考慮到不同業務型別的副本讀寫吞吐可能不一樣導致CPU負載不一致，在挑選副本的時候會進一步檢查當前節點的負載情況，如果當前節點負載超過閾值，則跳過該節點繼續選擇其他合適的節點。目前基於最少副本數以及負載校驗基本可以做到叢集內部的節點負載均衡。

當出現負載傾斜時，則從負載較高的節點選擇副本進行遷出，從叢集中尋找負載最低的節點作為待遷入節點。當出現節點故障下線以及新機器資源加入的時候，也是基於均值計算待遷出以及遷入節點進行均衡。

2）主從均衡

雖然通過最少副本數策略保證了節點副本數的均衡，但是由於raft選主的性質，可能出現主節點都集中在部分少數節點的情況。由於只有主節點對外提供寫入，主節點的傾斜也會導致負載的不均衡。為了保證主節點的均衡，Node節點會定期向metaserver上報當前節點上副本的主從資訊。

主從均衡基於表維度進行操作。metaserver會根據表在Node的分佈資訊進行副本數的計算。主副本的數量基於最樸素簡單的數學期望進行計算: 主副本期望值 = 節點副本數 / 分片副本數。下面為一個簡單的例子:

假設表a包含10個shard，每個shard 3個replica。在節點A、B、C、D的分佈為 10、5、6、9. 那麼A、B、C、D的主副本數期望值應該為 3、1、2、3. 如果節點數實際的主副本數少於期望值，那麼被放入待遷入區，如果大於期望值，那麼被放入待遷出區。同時通過新增誤差值來避免頻繁的遷入遷出。只要節點的實際主副本數處於 [x-δx,x+δx] 則表示主副本數處於穩定期間，x、δx 分別表示期望值和誤差值。

需要注意的是，當對raft進行主從切換的時候，從節點需要追上所有已提交的日誌以後才能成功選為主，如果有節點落後的時候進行主從切換，那麼可能導致由於追資料產生的一段時間無主的情況。因此在做主從切換的時候必須要檢查主從的日誌複製狀態，當存在慢節點的時候禁止進行切換。

一個小概率的事件，隨著規模的變大，也會變成大概率的事件。分散式系統下，隨著叢集規模的變大，機器的故障將變得愈發頻繁。因此如何對故障進行自動檢測容災修復也是分散式系統的核心問題。故障的容災主要通過多副本raft來保證，那麼如何進行故障的自動發現與修復呢。

1）健康監測

metaserver會定期向node節點發送心跳檢查node的健康狀態，如果node出現故障不可達，那麼metaserver會將node標記為故障狀態並剔除，同時將node上原來的replica遷移到其他健康的節點。

為了防止部分node和metaserver之間部分網路隔離的情況下node節點被誤剔除，我們添加了心跳轉發的功能。上圖中三個node節點對於客戶端都是正常的，但是node3由於網路隔離與metaserver不可達了，如果metaserver此時直接剔除node3會造成節點無必要的剔除操作。通過node2轉發心跳探測node3的狀態避免了誤剔除操作。

除了對節點的狀態進行檢測外，node節點本身還會檢查磁碟資訊並進行上報，當出現磁碟異常時上報異常磁碟資訊並進行踢盤。磁碟的異常主要通過dmesg日誌進行採集分析。

2）故障修復

當出現磁碟節點故障時，需要將原有故障裝置的replica遷移到其他健康節點，metaserver根據負載均衡策略選擇合適的node並建立新replica， 新建立的replica會被加入原有shard的raft group並從leader複製快照資料，複製完快照以後成功加入raft group完成故障replica的修復。

故障的修復主要涉及快照的複製。每一個replica會定期建立快照刪除舊的raftlog，快照資訊為完整的rocksdb checkpoint。通過快照進行修復時，只需要拷貝checkpoint下的所有檔案即可。通過直接拷貝檔案可以大幅減少快照修復的時間。需要注意的是快照拷貝也需要進行io限速，防止檔案拷貝影響線上io.

1）過期資料淘汰

在很多業務場景中，業務的資料只需要儲存一段時間，過期後資料即可以自動刪除清理，為了支援這個功能，我們通過在value上新增額外的ttl資訊，並在compaction的時候通過compaction_filter進行過期資料的淘汰。level之間的容量呈指數增長，因此rocksdb越底層能容納越多的資料，隨著時間的推移，很多資料都會被移動到底層，但是由於底層的容量比較大，很難觸發compaction，這就導致很多已經過期的資料沒法被及時淘汰從而導致了空間放大。與此同時，大量的過期資料也會對scan的效能造成影響。這個問題可以通過設定periodic_compaction_seconds 來解決，通過設定週期性的compaction來觸發過期資料的回收。

2）scan慢查詢

除了上面提到的存在大批過期資料的時候可能導致的scan慢查詢，如果業務存在大批量的刪除，也可能導致scan的時候出現慢查詢。因為delete對於rocksdb本質也是一條append操作，delete寫入會被新增刪除標記，只有等到該記錄被compaction移動到最底層後該標記才會被真正刪除。帶來的一個問題是如果使用者scan的資料區間剛好存在大量的delete標記，那麼iterator需要迭代過濾這些標記直到找到有效資料從而導致慢查詢。該問題可以通過新增CompactOnDeletionCollector 來解決。當memtable flush或者sst compaction的時候，collector會統計當前key被刪除的比例，通過設定合理的 deletion_trigger ，當發現被delete的key數量超過閾值的時候主動觸發compaction。

3）delay compaction

通過設定 CompactOnDeletionCollector 解決了delete導致的慢查詢問題。但是對於某些業務場景，卻會到來嚴重的寫放大。當L0被compaction到L1時候，由於閾值超過deletion_trigger ,會導致L1被新增到compaction佇列，由於業務的資料特性，L1和L2存在大量重疊的資料區間，導致每次L1的compaction會同時帶上大量的L2檔案造成巨大的寫放大。為了解決這個問題，我們對這種特性的業務資料禁用了CompactOnDeletionCollector 。通過設定表級別引數來控制表級別的compaction策略。後續會考慮優化delete trigger的時機，通過只在指定層級觸發來避免大量的io放大。

4）compaction限速

由於rocksdb的compaction會造成大量的io讀寫，如果不對compaction的io進行限速，那麼很可能影響到線上的寫入。但是限速具體配置多少比較合適其實很難確定，配置大了影響線上業務，配置小了又會導致低峰期頻寬浪費。基於此rocksdb 在5.9以後為 NewGenericRateLimiter 添加了 auto_tuned 引數，可以根據當前負載自適應調整限速。需要注意的是，該函式還有一個引數 RateLimiter::Mode 用來限制操作型別，預設值為 kWritesOnly,通常情況該模式不會有問題，但是如果業務存在大量被刪除的資料，只限制寫可能會導致compaction的時候造成大量的讀io。

5）關閉WAL

由於raft log本身已經可以保證資料的可靠性，因此寫入rocksdb的時候可以關閉wal減少磁碟io，節點重啟的時候根據rocksdb裡儲存的last_apply_id從raft log進行狀態機回放即可。

1）降副本容災

對於三副本的raft group，單副本故障並不會影響服務的可用性，即使是主節點故障了剩餘的兩個節點也會快速選出主並對外提供讀寫服務。但是考慮到極端情況，假設同時出現兩個副本故障呢？這時只剩一個副本無法完成選主服務將完全不可用。根據墨菲定律，可能發生的一定會發生。服務的可用性一方面是穩定提供服務的能力，另一方面是故障時快速恢復的能力。那麼假設出現這種故障的時候我們應該如何快速恢復服務的可用呢。

如果通過建立新的副本進行修復，新副本需要等到完成快照拷貝以後才能加入raft group進行選舉，期間服務還是不可用的。那麼我們可以通過強制將分片降為單副本模式，此時剩餘的單個健康副本可以獨自完成選主，後續再通過變更副本數的方式進行修復。

2）RaftLog 聚合提交

對於寫入吞吐非常高的場景，可以通過犧牲一定的延時來提升寫入吞吐，通過log聚合來減少請求放大。對於SSD盤，每一次寫入都是4k刷盤，value比較小的時候會造成磁碟頻寬的浪費。我們設定了每5ms或者每聚合4k進行批量提交。該引數可以根據業務場景進行動態配置修改。

3）非同步刷盤

有些對於資料一致性要求不是非常高的場景，服務故障的時候允許部分資料丟失。對於該場景，可以關閉fsync通過作業系統進行非同步刷盤。但是如果寫入吞吐非常高導致page cache的大小超過了 vm.diry_ratio ,那麼即便不是fsync也會導致io等待，該場景往往會導致io抖動。為了避免核心pdflush大量刷盤造成的io抖動，我們支援對raftlog進行非同步刷盤。

• 透明多級儲存，和快取結合，自動冷熱分離，通過將冷資料自動搬遷到kv降低記憶體使用成本。

• 新硬體場景接入，使用SPDK 進行IO提速，使用PMEM進行訪問加速。