來源：58架構師
1. 背景
RocksDB是由Facebook公司開源的一款高性能Key Value存儲引擎，目前被廣泛應用于業界各大公司的存儲產品中，其中就包括58存儲團隊自研的分布式KV存儲產品WTable。
RocksDB基于LSM Tree存儲數據，它的寫入都是采用即時寫WAL + Memtable，后臺Compaction的方式進行。 當寫入量大時，Compaction所占用的IO資源以及對其讀寫的影響不容忽視。 而對于一個分布式存儲系統來說，擴展性尤為重要，但是在擴展的過程中，又不可避免地會涉及到大量的數據遷移、寫入。
本篇文章將會著重介紹WTable是如何利用RocksDB的特性對擴容流程進行設計以及迭代的。
2. 數據分布
WTable為了實現集群的可擴展性，將數據劃分成了多個Slot，一個Slot既是數據遷移的最小單位。 當集群的硬盤空間不足或寫性能需要擴展時，運維人員就可以添加一些機器資源，并將部分Slot遷移到新機器上。 這就實現了數據分片，也就是擴容。
具體哪些數據被分到哪個Slot上，這是通過對Key做Hash算法得到的，偽算法如下：
SlotId = Hash(Key)/N 其中的N就是Slot的總量，這個是一個預設的固定值。
另外，為了讓同一個Slot中所有Key的數據在物理上能夠存儲在一起，底層實際存儲的Key都會在用戶Key的前面加上一個前綴： 該Key對應的SlotId。 具體方式是將SlotId以大端法轉換成2個字節，填充到Key字節數組的前面。
在RocksDB中，除了level 0外，其余level中的sst文件，以及sst文件內部都是有序存儲的。 這樣一來，WTable也就實現了單個Slot內數據的連續存儲，以及所有Slot整體的有序性。
3. 初始擴容方式
WTable初始的擴容方式如下：
1. 添加一個或多個機器資源，并搭建存儲服務節點。
2. 制定遷移計劃，得到需要遷移的Slot及其節點信息的列表。
3. 循環遷移每個Slot，遷移每個Slot的流程如下圖：
如上圖所示，遷移一個Slot可以分成3個階段： 全量遷移、增量遷移、路由信息切換。
其中全量遷移會在該Slot所在的老節點上創建一個RocksDB的Iterator，它相當于創建了一份數據快照，同時Iterator提供了seek、next等方法，可以通過遍歷Iterator有序地獲取一定范圍內的數據。 對應到這里，就是一個Slot在某一時刻的全量快照數據。 老節點通過遍歷Slot數據，將每個Key，Value傳輸到新節點，新節點寫入到自己的RocksDB中。
增量遷移則會利用老WTable節點記錄的Binlog，將全量遷移過程中新的寫入或更新，傳輸到新的節點，新節點將其應用到RocksDB。
最后，當發現新老節點上待遷移Slot的數據已經追平之后，則在ETCD上修改該Slot對應的節點信息，也就是路由信息切換。 從此以后，該Slot中數據的線上服務就由新節點提供了。
4. 存在問題
然而，上述的擴容方式在線上運行過程中存在一個問題： 當數據遷移速度較高（如30MB/s）時，會影響到新節點上的線上服務。
深究其具體原因，則是由于一次擴容會串行遷移多個Slot，率先遷移完成的Slot在新節點上已經提供線上服務，而遷移后續的Slot還是會進行全量數據、增量數據的遷移。
通過上個章節的描述，我們可以得知，全量數據是用RocksDB Iterator遍歷產生，對于一個Slot來說，是一份有序的數據。 而增量數據則是線上實時寫入的數據，肯定是無序的數據。 所以當新節點同時寫入這兩種數據時，從整體上就變成了無序的數據寫入。
在RocksDB中，如果某一個level N中的文件總大小超過一定閾值，則會進行Compaction，Compaction所做的就是： 將level N中的多個sst文件與這些文件在level N+1中Key范圍有重疊的文件進行合并，最終生成多個新文件放入level N+1中。 合并的方式可以簡單表述為： 如果多個文件中的Key確實有交集，則按照規則進行歸并排序，去重，按大小生成多個新sst文件； 如果Key沒有交集（說明這次合并，就沒有level N+1中的文件參與），則直接將level N中的文件move到levelN+1。
這樣我們就可以看出，當大量的整體無序的數據寫入遷移新節點時，各level之間的sst文件Key的范圍難免會重疊，而其上的RocksDB則會頻繁進行大量的，需要歸并排序、去重的Compaction（而不是簡單的move）。 這勢必會占用大量的IO，進而影響讀、寫性能。
另外，Compaction過多、過重造成level 0層的文件無法快速沉淀到level 1，而同時數據遷移使得新節點RocksDB的寫入速度又很快，這就導致level 0中的文件個數很容易就超過閾值level0_stop_writes_trigger，這時則會發生write stall，也就是停寫，這時就會嚴重影響寫服務。
5. 擴容方式演進
根據前面的問題描述，我們深入分析了RocksDB Compaction的特點，提出了兩點改進思路：
1. 擴容過程中，所有待遷移Slot的全量數據和增量數據要分開傳輸。
當大量的有序數據寫入RocksDB時，由于多個sst文件之間，完全不會出現Key存在交集的情況，所以其進行的Compaction只是move到下一個level，這個速度很快，而且占用IO極少。 所以我們利用這一點，選擇把所有Slot的全量數據放在一起遷移，這期間不會有增量數據的打擾，在整體上可以看做是有序的數據。 這就使得在遷移速度很快的時候，也不會占用大量的IO。 而增量數據畢竟是少數，這個過程可以在全量數據傳輸完成后，以較慢的速度來傳輸。
2. 考慮到大量數據傳輸可能會影響線上的服務質量，所以我們決定不再采取每一個Slot數據傳輸完成后就使其提供線上服務的方案，而是等所有Slot數據都遷移完成之后，再統一提供服務。
根據以上分析，我們最終將擴容分為了3個大的階段：
1. 全量數據遷移；
2. 增量數據遷移；
3. 路由信息統一切換。
整體流程如下圖所示：
經過上述擴容方式的改進，目前線上WTable集群已經可以進行較高速的擴容，比如50~100MB/s，并且在整個流程中不會對線上服務有任何影響。
6. 其他
在制定方案之初，我們也調研過其他的方案，比如老節點傳輸sst文件給新節點，后者通過IngestExternalFile的方式將sst文件導入RocksDB。
但是WTable的主備同步是通過Binlog進行的，而當主機通過IngestExternalFile的方式導入數據時，并不會有Binlog產生，也就無法通過正常流程同步數據給備機。 因此如果以此方式實現數據遷移，需要增加新的主備同步方式，這對原有流程是一個破壞，另外也需要比較大的工作量，效率方面也無法保證。
因此我們最終利用RocksDB Compaction的特點設計了適合WTable的快速擴容方案，解決了這個痛點。
