1. 背景
RocksDB是由Facebook公司開源的一款高性能Key Value存儲引擎，目前被廣泛應用于業(yè)界各大公司的存儲產(chǎn)品中衩椒，其中就包括58存儲團隊自研的分布式KV存儲產(chǎn)品WTable斤蔓。
RocksDB基于LSM Tree存儲數(shù)據(jù)恒水，它的寫入都是采用即時寫WAL + Memtable培愁，后臺Compaction的方式進行监氢。當寫入量大時悬襟，Compaction所占用的IO資源以及對其讀寫的影響不容忽視衅码。而對于一個分布式存儲系統(tǒng)來說，擴展性尤為重要脊岳，但是在擴展的過程中逝段，又不可避免地會涉及到大量的數(shù)據(jù)遷移垛玻、寫入。
本篇文章將會著重介紹WTable是如何利用RocksDB的特性對擴容流程進行設計以及迭代的奶躯。
2. 數(shù)據(jù)分布
WTable為了實現(xiàn)集群的可擴展性帚桩，將數(shù)據(jù)劃分成了多個Slot，一個Slot既是數(shù)據(jù)遷移的最小單位嘹黔。當集群的硬盤空間不足或?qū)懶阅苄枰獢U展時账嚎，運維人員就可以添加一些機器資源，并將部分Slot遷移到新機器上儡蔓。這就實現(xiàn)了數(shù)據(jù)分片郭蕉，也就是擴容。
具體哪些數(shù)據(jù)被分到哪個Slot上喂江，這是通過對Key做Hash算法得到的召锈，偽算法如下：
SlotId = Hash(Key)/N 其中的N就是Slot的總量，這個是一個預設的固定值获询。
另外烟勋，為了讓同一個Slot中所有Key的數(shù)據(jù)在物理上能夠存儲在一起，底層實際存儲的Key都會在用戶Key的前面加上一個前綴：該Key對應的SlotId筐付。具體方式是將SlotId以大端法轉(zhuǎn)換成2個字節(jié)，填充到Key字節(jié)數(shù)組的前面阻肿。
在RocksDB中瓦戚，除了level 0外，其余l(xiāng)evel中的sst文件丛塌，以及sst文件內(nèi)部都是有序存儲的较解。這樣一來，WTable也就實現(xiàn)了單個Slot內(nèi)數(shù)據(jù)的連續(xù)存儲赴邻，以及所有Slot整體的有序性印衔。
3. 初始擴容方式
WTable初始的擴容方式如下：
- 添加一個或多個機器資源，并搭建存儲服務節(jié)點姥敛。
- 制定遷移計劃奸焙，得到需要遷移的Slot及其節(jié)點信息的列表。
- 循環(huán)遷移每個Slot彤敛，遷移每個Slot的流程如下圖：
如上圖所示与帆，遷移一個Slot可以分成3個階段：全量遷移、增量遷移墨榄、路由信息切換玄糟。
其中全量遷移會在該Slot所在的老節(jié)點上創(chuàng)建一個RocksDB的Iterator，它相當于創(chuàng)建了一份數(shù)據(jù)快照袄秩，同時Iterator提供了seek阵翎、next等方法逢并，可以通過遍歷Iterator有序地獲取一定范圍內(nèi)的數(shù)據(jù)。對應到這里郭卫，就是一個Slot在某一時刻的全量快照數(shù)據(jù)砍聊。老節(jié)點通過遍歷Slot數(shù)據(jù)，將每個Key箱沦，Value傳輸?shù)叫鹿?jié)點辩恼，新節(jié)點寫入到自己的RocksDB中。
增量遷移則會利用老WTable節(jié)點記錄的Binlog谓形，將全量遷移過程中新的寫入或更新灶伊，傳輸?shù)叫碌墓?jié)點，新節(jié)點將其應用到RocksDB寒跳。
最后聘萨，當發(fā)現(xiàn)新老節(jié)點上待遷移Slot的數(shù)據(jù)已經(jīng)追平之后，則在ETCD上修改該Slot對應的節(jié)點信息童太，也就是路由信息切換米辐。從此以后，該Slot中數(shù)據(jù)的線上服務就由新節(jié)點提供了书释。
4. 存在問題
然而翘贮，上述的擴容方式在線上運行過程中存在一個問題：當數(shù)據(jù)遷移速度較高（如30MB/s）時，會影響到新節(jié)點上的線上服務爆惧。
深究其具體原因狸页，則是由于一次擴容會串行遷移多個Slot，率先遷移完成的Slot在新節(jié)點上已經(jīng)提供線上服務扯再，而遷移后續(xù)的Slot還是會進行全量數(shù)據(jù)芍耘、增量數(shù)據(jù)的遷移。
通過上個章節(jié)的描述熄阻，我們可以得知斋竞，全量數(shù)據(jù)是用RocksDB Iterator遍歷產(chǎn)生，對于一個Slot來說秃殉，是一份有序的數(shù)據(jù)坝初。而增量數(shù)據(jù)則是線上實時寫入的數(shù)據(jù)，肯定是無序的數(shù)據(jù)复濒。所以當新節(jié)點同時寫入這兩種數(shù)據(jù)時脖卖，從整體上就變成了無序的數(shù)據(jù)寫入。
在RocksDB中巧颈，如果某一個level N中的文件總大小超過一定閾值畦木，則會進行Compaction，Compaction所做的就是：將level N中的多個sst文件與這些文件在level N+1中Key范圍有重疊的文件進行合并砸泛，最終生成多個新文件放入level N+1中十籍。合并的方式可以簡單表述為：如果多個文件中的Key確實有交集蛆封，則按照規(guī)則進行歸并排序，去重勾栗，按大小生成多個新sst文件惨篱；如果Key沒有交集（說明這次合并，就沒有l(wèi)evel N+1中的文件參與）围俘，則直接將level N中的文件move到levelN+1砸讳。
這樣我們就可以看出，當大量的整體無序的數(shù)據(jù)寫入遷移新節(jié)點時界牡，各level之間的sst文件Key的范圍難免會重疊簿寂，而其上的RocksDB則會頻繁進行大量的，需要歸并排序宿亡、去重的Compaction（而不是簡單的move）常遂。這勢必會占用大量的IO，進而影響讀挽荠、寫性能克胳。
另外，Compaction過多圈匆、過重造成level 0層的文件無法快速沉淀到level 1漠另，而同時數(shù)據(jù)遷移使得新節(jié)點RocksDB的寫入速度又很快，這就導致level 0中的文件個數(shù)很容易就超過閾值level0_stop_writes_trigger跃赚，這時則會發(fā)生write stall酗钞，也就是停寫，這時就會嚴重影響寫服務来累。
5. 擴容方式演進
根據(jù)前面的問題描述，我們深入分析了RocksDB Compaction的特點窘奏，提出了兩點改進思路：
擴容過程中嘹锁，所有待遷移Slot的全量數(shù)據(jù)和增量數(shù)據(jù)要分開傳輸。
當大量的有序數(shù)據(jù)寫入RocksDB時着裹，由于多個sst文件之間领猾，完全不會出現(xiàn)Key存在交集的情況，所以其進行的Compaction只是move到下一個level骇扇，這個速度很快摔竿，而且占用IO極少。所以我們利用這一點少孝，選擇把所有Slot的全量數(shù)據(jù)放在一起遷移继低，這期間不會有增量數(shù)據(jù)的打擾，在整體上可以看做是有序的數(shù)據(jù)稍走。這就使得在遷移速度很快的時候袁翁，也不會占用大量的IO柴底。而增量數(shù)據(jù)畢竟是少數(shù)，這個過程可以在全量數(shù)據(jù)傳輸完成后粱胜，以較慢的速度來傳輸柄驻。考慮到大量數(shù)據(jù)傳輸可能會影響線上的服務質(zhì)量，所以我們決定不再采取每一個Slot數(shù)據(jù)傳輸完成后就使其提供線上服務的方案焙压，而是等所有Slot數(shù)據(jù)都遷移完成之后鸿脓，再統(tǒng)一提供服務。
根據(jù)以上分析涯曲，我們最終將擴容分為了3個大的階段：
- 全量數(shù)據(jù)遷移野哭；
- 增量數(shù)據(jù)遷移；
- 路由信息統(tǒng)一切換掀抹。
整體流程如下圖所示：
經(jīng)過上述擴容方式的改進虐拓，目前線上WTable集群已經(jīng)可以進行較高速的擴容，比如50~100MB/s傲武，并且在整個流程中不會對線上服務有任何影響蓉驹。
6. 其他
在制定方案之初，我們也調(diào)研過其他的方案揪利，比如老節(jié)點傳輸sst文件給新節(jié)點态兴，后者通過IngestExternalFile的方式將sst文件導入RocksDB。
但是WTable的主備同步是通過Binlog進行的疟位，而當主機通過IngestExternalFile的方式導入數(shù)據(jù)時瞻润，并不會有Binlog產(chǎn)生，也就無法通過正常流程同步數(shù)據(jù)給備機甜刻。因此如果以此方式實現(xiàn)數(shù)據(jù)遷移绍撞，需要增加新的主備同步方式，這對原有流程是一個破壞得院，另外也需要比較大的工作量傻铣，效率方面也無法保證。
因此我們最終利用RocksDB Compaction的特點設計了適合WTable的快速擴容方案祥绞，解決了這個痛點非洲。
