分布式存儲的7個特征

動機(jī)

為什么是7方面的問題？雖說7面只比6面多了一面，又比8面少了1面；然而并非刻意為之。存儲領(lǐng)域內(nèi)的很多知識，可以歸結(jié)于7個方面：復(fù)制、存儲引擎、事務(wù)、分析、多核、計算和編譯。

分布式存儲

什么是分布式存儲呢？如果一個存儲系統(tǒng)，不管是對象、塊、文件、kv、log、olap、oltp，只要對所管理的數(shù)據(jù)做了Partitioning&Replication，不管姿勢對不對，其實(shí)都可以歸納于分布式存儲。分布式存儲就是：Partitioning以多機(jī)scale，Replication以災(zāi)備容錯。

1. 復(fù)制

復(fù)制是解決可用性，可擴(kuò)展性和高性能的關(guān)鍵。為了災(zāi)備，數(shù)據(jù)需要冗余存儲；為了高可用，服務(wù)需要hot standby。缺乏災(zāi)備的系統(tǒng)難以在生產(chǎn)環(huán)境使用。元數(shù)據(jù)和數(shù)據(jù)的維護(hù)均離不開復(fù)制，復(fù)制可轉(zhuǎn)移而不可消除。復(fù)制引出了多副本一致性問題，而一致性保證需要考慮各種軟件和硬件故障，以及誤操作。共識算法和復(fù)制日志是解決復(fù)制問題的核心，具體涉及：

故障檢查，租約協(xié)議；

選主算法，primary uniqueness invariant，網(wǎng)絡(luò)隔離，腦裂，雙主，拜占庭故障，failfast/failstop，failover；

日志復(fù)制，RSM；

membership change，或者config change，主機(jī)上下線管理，擴(kuò)縮容；

數(shù)據(jù)復(fù)制，data rebalancing，data recovery；

副本放置邏輯和副本路由邏輯；

primary和backup之間如何fence？

外部一致性，線性一致性；

pipeline，fanout，primary-backup，quorum-based，gossip；

分布式日志，active-standby架構(gòu)，active-active架構(gòu)；

……

2. 存儲引擎

此處的引擎是指本地的持久化存儲引擎，持久化存儲引擎要考慮CPU和memory系統(tǒng)和持久化設(shè)備之間的速度和帶寬差異，可以總結(jié)為1-3-5。

1-3-5

1是指fsync的調(diào)用，以及和fsync地位等同的函數(shù)的調(diào)用。調(diào)用次數(shù)，調(diào)用頻率，在多少數(shù)據(jù)上施加調(diào)用等。設(shè)備的帶寬和利用率是否合理，fsync的調(diào)用怎么均攤到更多io次數(shù)和吞吐之上呢？

3是指讀/寫/空間的放大。怎么tradeoff，犧牲一個保住其他兩個呢？

5是指WAL的5個LSN，分別為prepare point，commit point，apply point，checkpoint，prune point。

處于prepare point和commit point之間的數(shù)據(jù)需要group commit；

處于apply point和commit point點(diǎn)之間的提交數(shù)據(jù)需要apply到內(nèi)存的數(shù)據(jù)結(jié)構(gòu)之上以后對讀可見；

內(nèi)存數(shù)據(jù)結(jié)構(gòu)需要以一定的調(diào)度策略存檔于持久化設(shè)備, checkpoint就是存檔點(diǎn)；

recover from crash需要從最近的checkpoint點(diǎn)恢復(fù)到commit point；

而一段checkpoint完成，則截止該checkpoint的日志可以截斷，因此存在一個不大于checkpoint的點(diǎn)，是為prune point，截止改點(diǎn)的日志和老的on-disk鏡像可以安全刪除。

因此這5個點(diǎn)始終保持一條約束：它們之間存在全序關(guān)系。

數(shù)據(jù)結(jié)構(gòu)和算法

內(nèi)存和磁盤數(shù)據(jù)的管理，需要用到豐富的數(shù)據(jù)結(jié)構(gòu)和算法。此外解壓縮和編解碼算法用于降低數(shù)據(jù)的size，也很有意思。

3. 事務(wù)

事務(wù)是指ACID，很多存儲系統(tǒng)，其實(shí)可以用事務(wù)做baseline進(jìn)行分析，看這個系統(tǒng)在原子性，一致性，隔離性和持久化四個方面的設(shè)計究竟走多遠(yuǎn)。其實(shí)事務(wù)反應(yīng)了正確性和并發(fā)性的折中。作為事務(wù)的使用方，理論上（實(shí)踐上未必），并發(fā)訪問存儲系統(tǒng)時，不需要擔(dān)心結(jié)果不正確的問題。假如這種擔(dān)憂存在，一定是事務(wù)處理上，犧牲了某些正確性，偏向了并發(fā)性，將錯誤處理和選擇權(quán)交給了使用方處理，使用方需要額外花費(fèi)心智在客戶代碼中插入fence代碼和做容錯處理。

存儲引擎部分，其實(shí)已經(jīng)或多或少地涉及到了事務(wù)處理的提交協(xié)議，提交協(xié)議主要解決事務(wù)的A和D。事務(wù)處理的核心是并發(fā)控制（concurrency control）協(xié)議。并發(fā)控制主要解決這樣的問題：

兩個并發(fā)事務(wù)沖突（讀寫，寫讀，寫寫），應(yīng)該怎么處理呢？加鎖等待還是檢測到?jīng)_突主動夭折呢？

已經(jīng)提交的事務(wù)對數(shù)據(jù)庫的影響，怎么對當(dāng)前outstanding事務(wù)的讀操作可見呢？

這兩個問題本質(zhì)是隔離性和一致性，沖突事務(wù)加以同步，前置的提交事務(wù)對后置outstanding事務(wù)可見。

理想的正確性是這樣子的：所有的事務(wù)，不管是否存在沖突，都一個一個串行執(zhí)行，時間上沒有任何重疊。理想的并發(fā)性是這樣子的：所有事務(wù)都沒有沖突，可以以最佳的并行度同時執(zhí)行。但現(xiàn)實(shí)是沖突始終存在，解決沖突，意味著在并行執(zhí)行的某個環(huán)節(jié)插入了同步點(diǎn)，需要判斷和仲裁是否有沖突。

沖突等待，是lock-based CC協(xié)議；沖突夭折重試，是timestamp ordering CC協(xié)議。前者就是所謂的悲觀事務(wù)，后者則為樂觀事務(wù)。事務(wù)處理在Jim Gray的書中和知名教材里其實(shí)已經(jīng)講得很清楚了。這里只提一下樂觀事務(wù)的沖突檢查的直觀性的簡單的理解：兩個事務(wù)存在兩種定序方法，一種是由TSO分配的時間戳確定的順序，一種是由數(shù)據(jù)依賴（WAW，RAW，WAR）確定順序。如果這兩種順序破壞事務(wù)之間的偏序關(guān)系，那么這兩個事務(wù)必然沖突，可以選擇讓一個事務(wù)夭折并且重試。

定序是一個比較關(guān)鍵的問題，比如樂觀事務(wù)的begin和commit的時間戳分配，悲觀事務(wù)的基于時間戳的死鎖預(yù)防也會用到時間戳的分配。

存儲系統(tǒng)自身做了partitioning之后，單個partition的事務(wù)處理可下沉于本地存儲引擎，然而如果一個操作涉及對多個partition的修改，則需要考慮跨partition的事務(wù)處理能力。其實(shí)分布式事務(wù)并沒有一個清晰的定義，但蘊(yùn)含了“跨（across）”的意思，不管是提交協(xié)議還是CC協(xié)議，都依賴于分布式存儲系統(tǒng)的實(shí)現(xiàn)或者單機(jī)事務(wù)的實(shí)現(xiàn)。雖然有很多文獻(xiàn)中反復(fù)用到2PC和3PC，但有時候是指提交協(xié)議，有時候是指CC協(xié)議，有時候是指提交協(xié)議和CC協(xié)議的混合體。

事務(wù)給存儲系統(tǒng)的行為做出了明確的定義和保證，從事務(wù)的角度可推測系統(tǒng)的實(shí)現(xiàn)，比如加鎖的粒度，多版本的管理，全局同步點(diǎn)，怎么處理write-too-late問題。

4. 分析

分析處理涵蓋的東西太多了。從一個角度看，是怎么實(shí)現(xiàn)SQL語言；從另一個角度看，是怎么實(shí)現(xiàn)一個分布式系統(tǒng)由SQL驅(qū)動起來工作。一條文本的SQL語句，歷經(jīng)分詞，語法分析，訪問catalog和語意分析，關(guān)系代數(shù)的等價變化，形成邏輯的查詢計劃，然后根據(jù)數(shù)據(jù)的分布，算子自身特點(diǎn)和計算資源狀況，生成物理執(zhí)行計劃。

一條SQL可以對應(yīng)多個邏輯執(zhí)行計劃，一個邏輯執(zhí)行計劃，對應(yīng)多個物理執(zhí)行計劃。比如join的順序，join的算子的實(shí)現(xiàn)。謂詞過濾時謂詞的順序，謂詞是否下沉。一個關(guān)系代數(shù)的算子，有多種的不同實(shí)現(xiàn)算法，而多個關(guān)系算子，不同的計算順序也會有不同的執(zhí)行效率。根據(jù)先驗(yàn)知識，使用啟發(fā)式的策略；或者利用數(shù)據(jù)分布的統(tǒng)計信息，采用某種cost估算模型；又或者根據(jù)已有執(zhí)行經(jīng)驗(yàn)，自適應(yīng)地調(diào)整到最優(yōu)或者次優(yōu)的執(zhí)行計劃。

在計算層，通過三大優(yōu)化策略parallelism，pipelining和batch加速處理。比如數(shù)據(jù)經(jīng)過parititioning形成多個partition，放置于多機(jī)上，采用MPP的方式，做多機(jī)的并行處理。計算的過程可以看成是把關(guān)系作為輸入，流經(jīng)執(zhí)行樹的葉子節(jié)點(diǎn)，匯聚于根節(jié)點(diǎn)，每個節(jié)點(diǎn)的對應(yīng)算子的具體算法實(shí)現(xiàn)所輸入數(shù)據(jù)進(jìn)行處理后輸出。從計算模型的角度看，有這么幾種情況：

tuple-at-a-time：采用了迭代器的模式，當(dāng)前迭代器執(zhí)行g(shù)et_next時，調(diào)用child算子對應(yīng)迭代器的get_next獲取計算所需的輸入tuple，然后執(zhí)行一段計算代碼，產(chǎn)生一個輸出tuple，發(fā)射parent算子。

full materialization：每個算子接收到全部的輸入數(shù)據(jù)，計算出輸出結(jié)果，交給下一個算子計算。這種方式類似于批處理。

vectorized execution：數(shù)據(jù)在內(nèi)存中按列存儲，以數(shù)組表示。選擇數(shù)組的大小，讓其可以在L1 data cache中裝得下，然后執(zhí)行樹的每個算子執(zhí)行tight for-loop按數(shù)組處理數(shù)據(jù)。這樣即避免了full materialization過多的資源索取，又能避免tuple-at-a-time的處理單個tuple的overhead，同時對cache更加友好，減少spurious invalidation，提升speculative cache missing的產(chǎn)生。同時簡單tight for-loop，編譯器能更好點(diǎn)編譯成高效執(zhí)行指令，同時也能更好地填充CPU的指令流水，充分利用CPU的multiple issue的功能加速簡單指令的處理。

在存儲層，數(shù)據(jù)采用列式存儲，可獲得很好的編碼效率，降低讀放大和空間放大，訪問持久化存儲的帶寬被高效利用，CPU和Memory的帶寬增速相對于持久化存儲帶寬增速表現(xiàn)出了顯著的差異，使用CPU的計算交換磁盤帶寬，提升了數(shù)據(jù)的處理能力。

列存，向量化執(zhí)行引擎，MPP是現(xiàn)代分析性數(shù)據(jù)庫的關(guān)鍵技術(shù)。

5. 多核

從編程實(shí)現(xiàn)的角度看，多核scale，CC協(xié)議，共識算法是計算機(jī)中比較有挑戰(zhàn)，并且是純自然的問題。即便技術(shù)上不深入接觸數(shù)據(jù)庫，也對這三個問題相當(dāng)?shù)匕V迷，被數(shù)據(jù)庫技術(shù)的吸引加入這個領(lǐng)域，或多或少和這三個問題相關(guān)。

為什么多核如此重要呢？

假設(shè)摩爾定律，沒有功率墻的限制，世界會怎樣呢？顯然我們不需要修改老代碼，只要增加單核晶體管數(shù)量，老代碼自然而然會提升。我們撞到了功率墻后，發(fā)現(xiàn)需要增加核數(shù)以提升計算速度?，F(xiàn)在問題來了，我們的代碼已經(jīng)寫成了多線程執(zhí)行，那么隨著核數(shù)增長，修改worker線程池的大小，老代碼的計算能力會隨著核數(shù)增加而持續(xù)增加嗎？顯然不是這樣，因?yàn)槎嗪松系膕cale受到阿姆達(dá)爾定律的制約，當(dāng)代碼中串行執(zhí)行的部分占比1%時，256核機(jī)器只能最多加速到72倍，如果是10%，只能最多加速到10倍。顯然修改線程池的大小，并不是一個好方法，減少代碼中contention才是關(guān)鍵。

這種情況下，speedup想要隨著核數(shù)而scale，發(fā)現(xiàn)很多算法，數(shù)據(jù)結(jié)構(gòu)，CC協(xié)議和分析處理的算子實(shí)現(xiàn)，需要case-by-case重構(gòu)以減少contention，重構(gòu)方式是采用lockfree算法。但是這還不是事實(shí)的全部，當(dāng)面對多核scale時，其實(shí)我們面對的是一個新的分布式系統(tǒng)，這個新的分布式系統(tǒng)是以interconnect為網(wǎng)絡(luò)，以核為計算資源，并且還需要考慮屏蔽內(nèi)存體系的延遲。如果說原來的分布式系統(tǒng)中，我們傾向于每個機(jī)器各干各的，數(shù)據(jù)做到均衡，計算資源就可以充分利用。對于多核編程同樣有這個問題，怎么將原來的任務(wù)均勻地拆成多個子任務(wù)，然后多個子任務(wù)可以齊頭并進(jìn)，幾乎同時沖線結(jié)束。顯然數(shù)據(jù)拆分不均衡，跨核通信等因素都會造成快核等慢核的問題。同時，多核處理時，傾向于協(xié)作完成一個共同的任務(wù)，而非各干各的，這種情況下，將任務(wù)均勻拆分成子任務(wù)的的調(diào)度代碼，共享的數(shù)據(jù)結(jié)構(gòu)的訪問代碼，多核彼此之間等待本身就是同步點(diǎn)，即contention，總之，contention怎么降低呢？

現(xiàn)實(shí)中，lockfree算法，怎么描述和驗(yàn)證正確性呢？我們對比其他兩個問題的思路，或許有解法。比如共識算法中，采用invariant描述算法；而CC協(xié)議中，采用反例（anormaly）攻擊算法?；蛟S這兩種方法相互結(jié)合，能夠幫助我們研究lockfree算法。

多核scale的挑戰(zhàn)性很大，但這可以讓具有優(yōu)勢的傳統(tǒng)數(shù)據(jù)庫和數(shù)據(jù)庫的新進(jìn)入者，處于賽道的同一起跑線，比拼誰的代碼case-by-case優(yōu)化做得好。

也有不少團(tuán)隊，在思考異構(gòu)計算加速數(shù)據(jù)處理，這同樣充滿機(jī)會。但是，依靠程序員的心智構(gòu)造精巧而高質(zhì)量的代碼，費(fèi)時費(fèi)力?；蛟S的確應(yīng)該通過編譯器的后端技術(shù)一勞永逸解決這類問題，現(xiàn)在做不到，不代表未來也做不到。到時候，有人看著前人寫得如此復(fù)雜的代碼，就好比我們現(xiàn)在看到泥板書和帶孔的卡片。

6. 計算

計算主要講執(zhí)行引擎， 執(zhí)行引擎是一個很大的scope，目前roadmap已經(jīng)建立，但是缺乏baseline，待兩者都ready之后，會補(bǔ)充。

7. 編譯

編譯對數(shù)據(jù)庫的滲透是全方位的：比如計算引擎在向量化之外可采用編譯技術(shù)優(yōu)化性能。數(shù)據(jù)庫中很多case-by-case的性能優(yōu)化，需要深入研究體系結(jié)構(gòu)，異構(gòu)計算加速處理也需要使用編譯技術(shù)。流批DSL腳本使用現(xiàn)有的SQL執(zhí)行引擎做計算，UDF擴(kuò)充等。目前動機(jī)已經(jīng)明了，但roadmap和baseline尚未建立，兩者ready之后，也會補(bǔ)充進(jìn)來。

編輯：黃飛