分佈式存儲的七方面問題

動機

爲什麼是 7 方面的問題？雖說 7 面只比 6 面多了一面，又比 8 面少了 1 面；然而並非刻意爲之。存儲領域內的很多知識，可以歸結於 7 個方面： 複製、存儲引擎、事務、分析、多核、計算和編譯。

分佈式存儲

什麼是分佈式存儲呢？如果一個存儲系統，不管是對象、塊、文件、kv、log、olap、oltp，只要對所管理的數據做了 Partitioning&Replication，不管姿勢對不對，其實都可以歸納於分佈式存儲。分佈式存儲就是：Partitioning 以多機 scale，Replication 以災備容錯。

1. 複製

複製是解決可用性，可擴展性和高性能的關鍵。爲了災備，數據需要冗餘存儲；爲了高可用，服務需要 hot standby。缺乏災備的系統難以在生產環境使用。元數據和數據的維護均離不開復制，複製可轉移而不可消除。複製引出了多副本一致性問題，而一致性保證需要考慮各種軟件和硬件故障，以及誤操作。共識算法和複製日誌是解決複製問題的核心，具體涉及：

1. 故障檢查，租約協議；

2. 選主算法，primary uniqueness invariant，網絡隔離，腦裂，雙主，拜占庭故障，failfast/failstop，failover；

3. 日誌複製，RSM；

4. membership change，或者 config change，主機上下線管理，擴縮容；

5. 數據複製，data rebalancing，data recovery；

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

7. primary 和 backup 之間如何 fence？

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

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

10. 分佈式日誌，active-standby 架構，active-active 架構；

11. ……

12. 存儲引擎

此處的引擎是指本地的持久化存儲引擎，持久化存儲引擎要考慮 CPU 和 memory 系統和持久化設備之間的速度和帶寬差異，可以總結爲 1-3-5。

1-3-5

• 1 是指 fsync 的調用，以及和 fsync 地位等同的函數的調用。調用次數，調用頻率，在多少數據上施加調用等。設備的帶寬和利用率是否合理，fsync 的調用怎麼均攤到更多 io 次數和吞吐之上呢？

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

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

• 處於 prepare point 和 commit point 之間的數據需要 group commit；

• 處於 apply point 和 commit point 點之間的提交數據需要 apply 到內存的數據結構之上以後對讀可見；

• 內存數據結構需要以一定的調度策略存檔於持久化設備, checkpoint 就是存檔點；

• recover from crash 需要從最近的 checkpoint 點恢復到 commit point；

• 而一段 checkpoint 完成，則截止該 checkpoint 的日誌可以截斷，因此存在一個不大於 checkpoint 的點，是爲 prune point，截止改點的日誌和老的 on-disk 鏡像可以安全刪除。

• 因此這 5 個點始終保持一條約束：它們之間存在全序關係。

數據結構和算法

內存和磁盤數據的管理，需要用到豐富的數據結構和算法。此外解壓縮和編解碼算法用於降低數據的 size，也很有意思。

3. 事務

事務是指 ACID，很多存儲系統，其實可以用事務做 baseline 進行分析，看這個系統在原子性，一致性，隔離性和持久化四個方面的設計究竟走多遠。其實事務反應了正確性和併發性的折中。作爲事務的使用方，理論上（實踐上未必），併發訪問存儲系統時，不需要擔心結果不正確的問題。假如這種擔憂存在，一定是事務處理上，犧牲了某些正確性，偏向了併發性，將錯誤處理和選擇權交給了使用方處理，使用方需要額外花費心智在客戶代碼中插入 fence 代碼和做容錯處理。

存儲引擎部分，其實已經或多或少地涉及到了事務處理的提交協議，提交協議主要解決事務的 A 和 D。事務處理的核心是併發控制（concurrency control）協議。併發控制主要解決這樣的問題：

• 兩個併發事務衝突（讀寫，寫讀，寫寫），應該怎麼處理呢？加鎖等待還是檢測到衝突主動夭折呢？

• 已經提交的事務對數據庫的影響，怎麼對當前 outstanding 事務的讀操作可見呢？

這兩個問題本質是隔離性和一致性，衝突事務加以同步，前置的提交事務對後置 outstanding 事務可見。

理想的正確性是這樣子的：所有的事務，不管是否存在衝突，都一個一個串行執行，時間上沒有任何重疊。理想的併發性是這樣子的：所有事務都沒有衝突，可以以最佳的並行度同時執行。但現實是衝突始終存在，解決衝突，意味着在並行執行的某個環節插入了同步點，需要判斷和仲裁是否有衝突。

衝突等待，是 lock-based CC 協議；衝突夭折重試，是 timestamp ordering CC 協議。前者就是所謂的悲觀事務，後者則爲樂觀事務。事務處理在 Jim Gray 的書中和知名教材裏其實已經講得很清楚了。這裏只提一下樂觀事務的衝突檢查的直觀性的簡單的理解：兩個事務存在兩種定序方法，一種是由 TSO 分配的時間戳確定的順序，一種是由數據依賴（WAW，RAW，WAR）確定順序。如果這兩種順序破壞事務之間的偏序關係，那麼這兩個事務必然衝突，可以選擇讓一個事務夭折並且重試。

定序是一個比較關鍵的問題，比如樂觀事務的 begin 和 commit 的時間戳分配，悲觀事務的基於時間戳的死鎖預防也會用到時間戳的分配。

存儲系統自身做了 partitioning 之後，單個 partition 的事務處理可下沉於本地存儲引擎，然而如果一個操作涉及對多個 partition 的修改，則需要考慮跨 partition 的事務處理能力。其實分佈式事務並沒有一個清晰的定義，但蘊含了 “跨（across）” 的意思，不管是提交協議還是 CC 協議，都依賴於分佈式存儲系統的實現或者單機事務的實現。雖然有很多文獻中反覆用到 2PC 和 3PC，但有時候是指提交協議，有時候是指 CC 協議，有時候是指提交協議和 CC 協議的混合體。

事務給存儲系統的行爲做出了明確的定義和保證，從事務的角度可推測系統的實現，比如加鎖的粒度，多版本的管理，全局同步點，怎麼處理 write-too-late 問題。

4. 分析

分析處理涵蓋的東西太多了。從一個角度看，是怎麼實現 SQL 語言；從另一個角度看，是怎麼實現一個分佈式系統由 SQL 驅動起來工作。一條文本的 SQL 語句，歷經分詞，語法分析，訪問 catalog 和語意分析，關係代數的等價變化，形成邏輯的查詢計劃，然後根據數據的分佈，算子自身特點和計算資源狀況，生成物理執行計劃。

一條 SQL 可以對應多個邏輯執行計劃，一個邏輯執行計劃，對應多個物理執行計劃。比如 join 的順序，join 的算子的實現。謂詞過濾時謂詞的順序，謂詞是否下沉。一個關係代數的算子，有多種的不同實現算法，而多個關係算子，不同的計算順序也會有不同的執行效率。根據先驗知識，使用啓發式的策略；或者利用數據分佈的統計信息，採用某種 cost 估算模型；又或者根據已有執行經驗，自適應地調整到最優或者次優的執行計劃。

在計算層，通過三大優化策略 parallelism，pipelining 和 batch 加速處理。比如數據經過 parititioning 形成多個 partition，放置於多機上，採用 MPP 的方式，做多機的並行處理。計算的過程可以看成是把關係作爲輸入，流經執行樹的葉子節點，匯聚於根節點，每個節點的對應算子的具體算法實現所輸入數據進行處理後輸出。從計算模型的角度看，有這麼幾種情況：

• tuple-at-a-time：採用了迭代器的模式，當前迭代器執行 get_next 時，調用 child 算子對應迭代器的 get_next 獲取計算所需的輸入 tuple，然後執行一段計算代碼，產生一個輸出 tuple，發射 parent 算子。

• full materialization：每個算子接收到全部的輸入數據，計算出輸出結果，交給下一個算子計算。這種方式類似於批處理。

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

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

列存，向量化執行引擎，MPP 是現代分析性數據庫的關鍵技術。

5. 多核

從編程實現的角度看，多核 scale，CC 協議，共識算法是計算機中比較有挑戰，並且是純自然的問題。即便技術上不深入接觸數據庫，也對這三個問題相當地癡迷，被數據庫技術的吸引加入這個領域，或多或少和這三個問題相關。

爲什麼多核如此重要呢？

假設摩爾定律，沒有功率牆的限制，世界會怎樣呢？顯然我們不需要修改老代碼，只要增加單核晶體管數量，老代碼自然而然會提升。我們撞到了功率牆後，發現需要增加核數以提升計算速度。現在問題來了，我們的代碼已經寫成了多線程執行，那麼隨着核數增長，修改 worker 線程池的大小，老代碼的計算能力會隨着核數增加而持續增加嗎？顯然不是這樣，因爲多核上的 scale 受到阿姆達爾定律的制約，當代碼中串行執行的部分佔比 1% 時，256 核機器只能最多加速到 72 倍，如果是 10%，只能最多加速到 10 倍。顯然修改線程池的大小，並不是一個好方法，減少代碼中 contention 纔是關鍵。

這種情況下，speedup 想要隨着核數而 scale，發現很多算法，數據結構，CC 協議和分析處理的算子實現，需要 case-by-case 重構以減少 contention，重構方式是採用 lockfree 算法。但是這還不是事實的全部，當面對多核 scale 時，其實我們面對的是一個新的分佈式系統，這個新的分佈式系統是以 interconnect 爲網絡，以核爲計算資源，並且還需要考慮屏蔽內存體系的延遲。如果說原來的分佈式系統中，我們傾向於每個機器各幹各的，數據做到均衡，計算資源就可以充分利用。對於多核編程同樣有這個問題，怎麼將原來的任務均勻地拆成多個子任務，然後多個子任務可以齊頭並進，幾乎同時衝線結束。顯然數據拆分不均衡，跨核通信等因素都會造成快核等慢核的問題。同時，多核處理時，傾向於協作完成一個共同的任務，而非各幹各的，這種情況下，將任務均勻拆分成子任務的的調度代碼，共享的數據結構的訪問代碼，多核彼此之間等待本身就是同步點，即 contention，總之，contention 怎麼降低呢？

現實中，lockfree 算法，怎麼描述和驗證正確性呢？我們對比其他兩個問題的思路，或許有解法。比如共識算法中，採用 invariant 描述算法；而 CC 協議中，採用反例（anormaly）攻擊算法。或許這兩種方法相互結合，能夠幫助我們研究 lockfree 算法。

多核 scale 的挑戰性很大，但這可以讓具有優勢的傳統數據庫和數據庫的新進入者，處於賽道的同一起跑線，比拼誰的代碼 case-by-case 優化做得好。

也有不少團隊，在思考異構計算加速數據處理，這同樣充滿機會。但是，依靠程序員的心智構造精巧而高質量的代碼，費時費力。或許的確應該通過編譯器的後端技術一勞永逸解決這類問題，現在做不到，不代表未來也做不到。到時候，有人看着前人寫得如此複雜的代碼，就好比我們現在看到泥板書和帶孔的卡片。

6. 計算

計算主要講執行引擎， 執行引擎是一個很大的 scope，目前 roadmap 已經建立，但是缺乏 baseline，待兩者都 ready 之後，會補充。

7. 編譯

編譯對數據庫的滲透是全方位的：比如計算引擎在向量化之外可採用編譯技術優化性能。數據庫中很多 case-by-case 的性能優化，需要深入研究體系結構，異構計算加速處理也需要使用編譯技術。流批 DSL 腳本使用現有的 SQL 執行引擎做計算，UDF 擴充等。目前動機已經明瞭，但 roadmap 和 baseline 尚未建立，兩者 ready 之後，也會補充進來。

原文鏈接：https://zhuanlan.zhihu.com/p/369581725

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