動機

為什么是7方面的問題?雖說7面只比6面多了一面，又比8面少了1面;然而并非刻意為之。存儲領域內的很多知識，可以歸結于7個方面： 復制、存儲引擎、事務、分析、多核、計算和編譯。

分布式存儲

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

[[399749]]

1. 復制

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

• 故障檢查，租約協議;
• 選主算法，primary uniqueness invariant，網絡隔離，腦裂，雙主，拜占庭故障，failfast/failstop，failover;
• 日志復制，RSM;
• membership change，或者config change，主機上下線管理，擴縮容;
• 數據復制，data rebalancing，data recovery;
• 副本放置邏輯和副本路由邏輯;
• primary和backup之間如何fence?
• 外部一致性，線性一致性;
• pipeline，fanout，primary-backup，quorum-based，gossip;
• 分布式日志，active-standby架構，active-active架構;
• ……

2. 存儲引擎

此處的引擎是指本地的持久化存儲引擎，持久化存儲引擎要考慮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之后，也會補充進來。