總結和整合¶

回顧一下資料庫和衍生資料最後再整合起來。

HackMD 報告文本

總結¶

這裡我們總結一下資料庫相關知識，包括分散式資料庫和衍生資料系統。

資料庫基礎¶

根據商務邏輯選擇資料模型，可能有 關聯式、文件式、圖像式 等等，其他不常見的模型就會根據特殊需求設計，例如基因資料庫。

根據不同資料模型會使用不同搜尋語言，常見的 SQL 是 宣告式（宣告要什麼抽象的結果）的語言，其他還有像程式碼一樣擁有高彈性的 命命式（一步一步命令資料庫做什麼事跟不常見但是在特殊情況非常好用的 邏輯式（不寫行為而是寫邏輯）。

邏輯式的使用場景

在圖像式資料庫中搜尋「出生在台北但是搬去台南的使用者」，我們可以透過告訴資料庫「什麼是住在台北」（告知邏輯而非命令，edge=born 不等於 if (edge=born) return true;）還有「什麼是搬去台南」（edge=migration, node=Tainan）讓資料庫可以找到我們想要的資料。

為什麼上述例子會使用 圖像式 和 邏輯式 搜尋？

由於地理關係不能簡單用 關聯式 資料庫表示（例如某地包含於某市等等，這種關係在 關聯式 中會讓資料容易冗長），所以用圖像式。而 圖像式 的搜尋又常常有商務邏輯在其中，所以做成 宣告式 沒那麼方便。

接著我們把焦點從應用程式放到資料庫中，當資料庫要從檔案系統中拿資料時，他怎麼辦到快速在茫茫資料海中找到指定資料的？透過索引。我們先從 散列式索引 了解如何透過 key-value 組合建構強大的記憶體索引，依此延伸的 排序字串表 則是利用附加進日誌的方式把資料存進檔案系統。利用硬體天生適合附加的特性和背景執行的緊壓（compaction），保持排序且緊密的日誌可以讓他同時適合寫入和讀取。最後再提常見的 b-tree 和其與排序字串表的比較。

了解資料庫怎麼快速拿取指定資料之後，我們來看看另一種索引，行式索引。有些搜尋不是指定資料，而是範圍資料，例如這個月的註冊者數量，這種搜尋我們稱為 OLAP。這段我們提了很多資料庫怎麼和底層 OS 和硬體溝通，並優化這一系列的過程。

了解應用程式和資料庫的運作基礎之後，我們再來看看資料庫怎麼和應用程式或本地主機溝通：編碼。常見的 JSON/CSV/XML 不太適合用來做資料庫的編碼，因為效率低落、資料肥大和不易演進。隨著應用程式的邏輯改變，資料庫的綱目會被改變，這之中的編碼需要適應演進。這之中提了幾個有趣的編碼，值得注意的是 Apache Avro 如何適應演進和無綱目的架構。

容錯機制¶

並行的請求會讓資料庫狀態出錯，例如同時有人訂票。在單台資料庫中，聰明的開法者嘗試把可能發生的問題都透過交易機制來避免。交易機制提供兩項保證：

原子性：讓所有相關的請求都被包裝成單一程序，當一系列請求中有任一請求發生錯誤，就讓資料庫回到一系列請求前的狀態。
隔離性：交易和交易之間不會互相影響，例如交易 A 看不到交易 B 交易尚未提交前的狀態。

要注意的是只有隔離性能避免競賽狀況，至於原子性只是提供資料庫容錯的機制也就是發生任何問題都不會把問題殘留在狀態中，而是回到最一開始正常的狀態。

隔離性的等級¶

隔離性（isolation）的世界非常複雜，不只是因為實作時需要注意的眉眉角角更是因為市面上有非常非常多的資料庫，而每個資料庫對於隔離性的定義都不太一樣。越強的隔離性通常代表資料庫擁有越強的一致性（consistency）：

使用提交後的資料（no-dirty-read + no-dirty-write）：一般來說是隔離性中最弱的，透過加鎖（只加寫入的）讓兩個交易間不會互相影響，並在提交交易後才整合進資料庫避免交易間看到彼此尚未提交的狀態。

快照隔離：當 交易A 開始執行後，交易B 完成提交，進而影響 交易A 的判斷（因為 交易B 完成提交會讓新的狀態通過 使用提交後的資料 的檢查），這時可以使用 MVCC，替每個交易開始當下建立資料版本，避免讀到錯誤狀態

序列化隔離：有些資料庫透過單一執行序（例如 Redis）來達成序列化的一致性，但是其他使用檔案系統的資料庫無法用這種方式，否則效能會嚴重受到硬碟讀取的影響，2PL 透過讓讀取的請求也加上鎖來提供序列化隔離，但是 OLTP 的請求大部分都是讀取請求，所以這方法會嚴重影響效能。快照序列化隔離（SSI）可以保證效率又能提供隔離性，但是方法較新，待時間的考驗讓這演算法較穩定。

分散式資料庫¶

隨著資料和流量的成長，我們需要分區和複製的幫忙。

複製幫助我們提高整個系統的可用性，當一台資料庫因為任何原因無法回應請求時，其他資料庫就可以幫忙。同時透過把流量平均分配於各個複製中，就能達到非常有效的負載平衡。但是因為不同資料庫可能不是完全一樣的所以會有狀態不一致的狀況。越是要求不同資料庫的狀態一致性，通常就會犧牲複製的效能。

分區幫助我們舒解資料越長越大，單台節點無法負荷的狀況，同時在部分狀況下，也能做到負載平衡的效果，當資料庫處理指定資料（例如使用者 1234 的資訊）的請求時，就可以把請求送到擁有該資料的分區，但是如果處理的請求需要多個分區的資料（例如使用者的平均年齡）時，就會提高回應時間和錯誤發生的機率。所以分區會面臨資料連續性和資料分區平衡的權衡，越高的連續性代表可以做到越好的範圍搜尋，越高的平衡（資料平均打散到分區）代表能做到越好的負載平衡。

複製¶

要做到複製主要有三種方式：

單一領袖，一群節點中有一個領袖負責服務異動請求，其他節點負責服務讀取請求，領袖透過傳遞複製日誌給其他節點達成一致性。
多領袖，一群節點有多個領袖，這時不僅可以分散異動請求也能把多個叢集放在不同地理區域的資料中心，達到國際化的低潛時服務。
無領袖，透過外部協調者把請求分配到所有（或者說多數）節點，可以解決單一領袖的低可用又能解決多領袖的異動衝突。

單一領袖因為高度依賴唯一的領袖，當領袖失能時重選領袖的機制必須要謹慎設計否則容易造成複權（split brain）的問題，除此之外因為受限於單一領袖的地理位置，不好做到多資料中心的結構。單一領袖最大優勢在於所有異動都在領袖完成，不會有兩個異動衝突的狀況。

多領袖因為允許多個節點執行異動，當異動間造成衝突就需要透過一些演算法解衝突，這讓多領袖的叢集較少被實現。

無領袖和直觀上很好理解的領袖類型叢集不同，且是近幾年才又重新受到關注的複製方式。透過應用程式和資料庫中間的協調者（協調者是無狀態，所以可以像應用程式般很容易達到高可用）來幫助請求送到所有資料庫。透過 鴿巢原理 可以保證資料的一致性，並允許部分的異步來達成高可用性。。當有節點沒收到請求時（因為是使用異步的方式，所以沒辦法保證節點收到資料）就透過背景定期整併（anti-entropy process）和讀取時復原（read repair）來維持一致性。

複製日誌¶

在領袖類型的資料叢集中，透過在資料庫間傳遞複製日誌來達成一致性。主要是使用邏輯日誌，因為他介於語法日誌和 WAL 中間，不會過於抽象導致實際資料會產生差異（例如 UPDATE user 1234 updated_at = now()）， MySQL 的 binlog 和 PostgreSQL 的 logical-decoding 就是這種東西。

分散式資料庫的容錯¶

在多個節點要達成一致性會有如上圖的三種方式，值得注意的是無論是哪一種，目前的研究都會回歸到單一節點的通量來達成全域順序廣播，也就是效能會受到單一節點的天花板限制。

共識演算法的高可用和負載平衡

共識演算法讓多個節點共同擁有一個全域順序，並提供給外部使用者來幫助達成線性或序列化的執行序。

然而共識演算法沒辦法做到負載平衡，全部節點都要參與新的順序的選舉，透過只需要多數（多數決）節點的存活來保證可用性。不過我們可以透過讀寫分離來幫助降低選舉人的負擔，例如 Paxos 的 Learner 節點。

衍生資料系統¶

在介紹資料庫的時候，我們提到了很多種應用，都是透過原始資料重新轉譯成另一種面貌讓其他應用程式讀取，不管是次索引還是快取等等。在這之中，有一種計算方式稱為批次處理，他的哲學在於不異動資料來源，直接把想要的結果算出來放到檔案系統，再讓其他程序計算其他結果。

這樣的哲學和我們在 Linux 上的 GNU Coreutils 工具非常相像，透過不異動資料源來滿足冪等的（idempotent）。只是這裡的批次處理不再只是單一節點而是分散式的，其中的 Unix 的檔案描述符對應到分散式系統就是 HDFS，而 Coreutils 就是 MapReduce/Spark/Flink 等框架提供的程式庫或者自己客制的商務邏輯。

批次處理透過分散式運算和不異動來源所形成的容錯性，在很多場景中都能有貢獻，例如單台節點你除了可以跑線上服務，透過賦予批次處理的程序較低的優先程度讓機器在低流量時仍能保持一定的運算量。

串流處理和批次處理很像，都是用於產生衍生資料。但是串流處理很重要的一點是儲存的不再是「狀態」而是形成狀態的「事件」。

這點和資料庫有很大的差別，前面提的資料庫都透過開發者對於商務邏輯去設計綱目，讓資料庫儲存符合需求的狀態。但是應用程式是會成長的，當現有的綱目不夠支援新的應用時，勢必就會有異動，這時新的狀態很可能就需要等待使用者去輸入，或者透過背景運算把資料補進去，不論哪一種都不是很好的方法，尤其不小心改錯了東西要復原時就更困難了。

透過儲存原始的事件，當我有需要新的綱目時，我就可以透過歷史的事件重新形塑出全新的狀態。除此之外，當發現現有狀態有錯時，我可以透過歷史事件重新計算狀態並檢查哪一個事件導致狀態異常。

CDC（Change Data Capture）就是資料庫把每次的異動輸出成事件。

整合¶

接下來就要談談怎麼做到一個可以滿足高容錯、高可用和高複雜度的架構。

為什麼要整合¶

我們從前面已經知道選擇不同資料庫（例如選擇 MySQL v.s. Redis）其實就是在不同面向作權衡，舉例來說：

索引中不同資料庫可能會使用 排序字串表 或 B-Tree，這兩者分別有不同的優劣勢。
分散式複製時選擇 單一領袖、多領袖 或 無領袖。

每個資料庫會努力宣稱其優勢，但是通過前幾章的學習，我們應該具備了能用寬闊的視野去查看這些文件，我們能在內心回答自己：當他提供這項優勢時犧牲了什麼？

正因為沒有一個工具能夠應付各種狀況，我們無可避免地要整合這些不同用途的資料系統。但是該怎麼整合？常見的做法就是透過應用程式整合：

當應用程式開始整合了，你就需要一個清楚的概觀知道資料以何種格式從哪邊輸入，又以何種格式會輸出到何處，這些都不是容易的事情，無關你是不是工程師。除此之外透過應用程式很容易就會遇到邊際狀況，因為我們沒辦法有效的在開發當下了解各種可能的狀況，例如快取造成的狀態不一致。

如果沒有一個清楚的概觀會發生什麼事？以全文索引為例：

如果全文索引原本透過資料庫的 CDC 來獲得資料，並依此保證其和資料庫的狀態一致性，但是如果今天有個應用程式不知道這個狀況，再額外補上一些輸入給搜尋索引，這時就會出想兩者狀態不一致的狀況。

這種情況會隨著架構複雜的提升變得越來越隱晦。

怎麼有效整合¶

其實上面這個狀況代表著好的應用程式架構就是在解決：怎麼有效整合異質間的狀態？

分散式交易架構（例如 XA）：他能讓異質間的應用保持線性關係，也就是讀到的資訊就是最新的資訊。

XA 的缺點就是低效能低可用性，另一種方式是透過事件來源，利用事件是冪等的（idempotent）和決定性的（deterministic）來保持一致，也就是每次執行相同的事件都會得到相同的結果，但是會有「複製延遲」的問題（異於線性關係）。

冪等 v.s. 決定性

冪等代表重複執行該行為時不會造成額外的影響，例如刪除檔案，當你重複刪除該檔案時，不會有其他影響。 決定性 代表每次輸入都會有相同的輸出，例如統計指定字串長度，不會第二次得到的答案和第一次不一樣，同時不會有其他外部影響，例如開新檔案。

決定性 的要求比冪等高。差異詳見於此

根據你的應用程式和環境的要求，選擇不同的方式：

分散式交易架構：低效能和低容錯
事件來源：高效能和高可用，但僅能保持最終一致性

當低效率和低容錯不能被容忍，事件來源就變成唯一的選擇了。接下來討論的重點就是：事件來源怎麼整合異質應用？提供了哪些好壞處？有沒有除了最終一致性之外的選擇？

Google Sheet 的高度相似

事件來源的架構和 Google Sheet 很像，當原始資料改變，外面的程式會自動感知並修正產出的值。

事件來源¶

異步
決定性
- 原子性的轉嫁
因果

透過事件來源天生異步的處理方式，讓兩個異質應用可以彼此獨立不再依賴彼此（輸出事件時不用等到回應）達到高容錯和高效率。

除此之外，前面在批次處理中提的 決定性 也能提升容錯性，舉例來說，批次處理中如果計算過程中出錯（網路中斷等等）就重新拿輸入做一次計算，而這計算不會因為第二次運算而有不同輸出。決定性不僅方便容錯也有利於幫助我們整合異質間的應用，例如我們就可以透過確保資料庫的 CDC 是決定性之後，追蹤者的失能都可以透過重新計算來滿足需要的資料面向。

前面資料庫透過原子性讓計算可以捨棄計算後重新執行計算，但是當使用前面提的「冪等」和「決定性」時，就需要應用程式自己去注意這些事件是否有該特性，另外還有不同事件間的「因果」也需要盡量獨立。一般來說應用程式有幾種選擇：

在發送有因果關係的事件時透過單一節點的邏輯時鐘來賦予事件額外的資訊。也就是增加事件的 metadata。
讓讀取也變成事件，有點像是 stream-table join，讀取事件是串流的，而其他相關資訊的「狀態」則被儲存進記憶體中，例如購物車的狀態。
自動處理衝突的演算法，但有時當感知到衝突時已經來不及了（例如送出郵件）

因果的隱晦性

有時兩個事件的因果是很隱晦的例如分手後的情侶在社交軟體互相封鎖，其中一個人在分手後發貼文大爆料，這之中的兩個事件「封鎖」和「發文」其實是有因果的。

看看例子¶

我們以次索引為例，如果在分散式的資料庫中要維持次索引，我們會需要在各個分區中同步這些資料（無論是本地索引或者全域索引），但是這會增加寫入資料時的工作。

如果把這樣的次索引透過事件來源的機制讓其他應用去維持這個新的資料庫面向，這時就不需要犧牲寫入或讀取的效能了，也因為這樣讓資料庫擁有更高的可用性。

再舉一個綱目演進的例子，在討論綱目時，我們談了很多機制幫助維運這個會隨著應用程式成長一直改變的東西。但是透過事件來源，我們甚至可以建立兩個完全不同綱目的資料庫，再透過 A/B 測試導流特定使用者到新的綱目上，運行一陣子之後確保資料沒有異常就可以完整切換。

獨立寫入和整合讀取¶

透過這些例子我們就會發現，整合異質間的應用其實就是把原本單一資料庫做的事分給其他應用去做。也就是讓資料庫內部運作原來分散給各個獨立的應用程式叢集，就好像現在常用的微服務（micro service），也有人稱其為 database-inside-out（把資料庫裡的邏輯拿出來）。這麼做就會讓各個服務擁有高可用性，同時又能透過事件機制滿足彼此的一致性。

這時除了寫入，我們也要考慮如何透過單一介面讀取這些異質的資料，例如 PostgreSQL 的 foreign data wrapper 就符合這種需求，有點像是 MPP 裡面他在多個分區執行整合搜尋。

然而整合這些不同的應用時，我們會需要仔細的思考當某節點失能時，會發生什麼事？然後整合時之間的服務發現要怎麼做？讓應用程式不需考慮身為追蹤者需要注意的事情的抽象介面等等都是要仔細思考的問題。目前市面上並沒有針對這些結構的服務出現，但是有相關的研究，例如 differential dataflow。

上面兩張圖來源是 Samza 報告簡報，分別是 54 頁和 57 頁。

怎麼做到高一致性¶

怎麼做到高一致性？整理出三個方法，依次討論之。

把使用者納進叢集¶

一般的網路應用都會等待使用者透過瀏覽去或者手機應用送出請求後得到回應，這時如果後端服務的狀態是透過事件來源時，我們是可能會得到不是最即時的資料。但是現在的技術讓我們不必再等使用者主動去重新整理或者發送請求來得到最新資料，我們也可以透過後端主動發送新資料給使用者。

若不再把使用者當成服務外的端點而是服務內的端點，我們就可以透過先前在日誌型中介者提到的 偏移量 來記錄每個線上使用者當下他距離最新狀態多遠。當有任何新事件就發送給使用者，這樣對使用者來說就能得到最短暫的狀態不一致，這樣又何嘗不是我們一開始最期望的嗎？

但是這個東西的困難點在於，我們太習慣請求／回應這種模式，所以不只是應用程式／相關套件需要有新的介面，開發人員也需要在這種新型態的架構中取得思想上的改進。

點對點的防護¶

TCP 和 HTTP 的關係就好像資料庫和應用程式的關係。TCP 提供很多的容錯機制：避免封包重複寄送／接收、當一部份的封包遺失時捨棄請求、Timeout 等等，但是應用程式還是得做一些容錯機制：Retry、Timeout 等等。

這種應用程式兩端的容錯稱為點對點的防護機制。

TCP 就好像資料庫一樣，提供了很多保護機制：交易、WAL 等等，但是對於應用程式來說，還是得做一定的容錯機制。舉例來說：

```sql title="當重複寄送請求時，交易機制無法避免重複的運算" BEGIN TRANSACTION; UPDATE accounts SET balance = balance + 21 WHERE account_id = 1234; UPDATE accounts SET balance = balance - 21 WHERE account_id = 4321; COMMIT


以上述的程式碼為例，即使用該方式包裝請求，還是會遇到你錯誤重複寄送請求（例如使用者按了兩次按鈕）導致的狀態錯誤。

```sql title="建立唯一的 request_id 來避免重複執行"
ALTER TABLE requests ADD UNIQUE (request_id);

BEGIN TRANSACTION;

INSERT INTO requests (request_id, from_account, to_account, amount) VALUES ('some-unique-id', 4321, 1234, 21)

UPDATE accounts SET balance = balance + 21 WHERE account_id = 1234;
UPDATE accounts SET balance = balance - 21 WHERE account_id = 4321;
COMMIT

如果要避免這狀況，你可以透過添加編號（可能是所有資訊的雜湊）到請求中，並使用資料庫的 Unique Constraint 來避免。

但是上述機制到了分散式時就代表你只能在單一領袖的叢集有效，因為多領袖就可能發生兩個請求送到不同領袖去處理，那這樣多領袖該怎麼辦呢？

除了複製之外（也就是不管使用哪種複製方式），如果叢集有使用分區，這時就可能兩個帳號的請求 ID 在不同分區就會讓這個交易實作變得很複雜（因為需要跨分區確保 Unique Constraint），這時就代表你需要全域順序廣播來避免邊際狀況。

事件來源的點對點防護¶

以使用者註冊帳號為例，應用程式希望使用者只會申請同一個帳號名稱。我們可以利用日誌型中介者和一組追蹤者，並透過中介者的分區機制，把不同帳號（可能加個雜湊）的申請事件放在不同的分區，讓追蹤者追蹤這些事件並維持狀態，再把申請事件的成功與否輸出成另一個主題，這樣就可以做到擴展性又能保持一致性。

整理一下透過事件來源做高一致性的邏輯和順序：

包裝所有異動到單一事件
- 在所有事件中添加唯一的編號，賦予之後每一次的計算都是冪等的
- 儲存的事件是不變的
使用決定性的衍生函示追蹤想要的事件
衍生新面貌

監控健康狀況¶

監控機制可以幫助了解資料叢集的健康（一致性）程度，這種監控技術一直很貧脊，但是如果有了這個東西，可以讓我們對於目前擁有的資料狀況有足夠的信心和說服力。

如果使用事件來源，在發現叢集有健康程度低落的強況時，就可以從原始（或快照）狀態利用歷史事件重新建立狀態來滿足一致性。

簽證透明化

簽證透明化（Certificate Transparency）是一種讓憑證機構（CA）可以公開其簽發的憑證的機制，透過日誌形式只附加每次新簽的憑證。一年可簽發的憑證可能幾十億個，要怎麼做到每次新增憑證自動重新產出這個日誌的簽名？

如果可以做到，那麼這點是不是就可以透過替兩個資料庫產出各自的雜湊值，並用來檢查兩個資料庫的狀態是否一致？

而這個東西是不是就是監控機制？

高一致性重要嗎¶

對於外部觀察者來說，當他送出請求後另外一個裝置可能看不到剛剛的異動，但是我們在大部分情況都不需要這麼嚴謹的一致性，通常我們在意的是異動的正確性，只要最終結果是正確，讓使用者等個幾分鐘又何仿，例如，信用卡交易、訂票、網購等等。我們也可以透過一些前端提示來說明狀態可能不是最即時或者先顯示結果再通知是否正確異動。

以減少道歉為最終目的的話

你也可以這樣想：高一致性避免我們因為錯誤狀態要向使用者道歉的機會，但是卻提高了因為降低效能、可用性所需要向使用者道歉的機會。既然如此，何不最一開始就準備好道歉的機制並使用這種高可用且高容錯的機制，並在發生錯誤狀態時手動修復。

其他東西¶

Lambda Architecture 整合批次處理和串流處理，缺點和處理缺點的一些機制。
利用聯合（join）不同串流處理的輸出，來解決跨分區的搜尋，類似 MPP，只是是用事件來源的基礎
定期搬遷資料避免硬體的損壞
要做對的事：隱私權和自我規範

結語¶

講了這麼多不是要否定強一致性的資料叢集，而是把視野拓寬，把這些資料庫當成全公司資料系統的一小部分工具，而這工具只是衍生資料的一環並適用於那些需要非常嚴謹處理資料的應用程式。

目前市面上已經有調度容器化的應用程式的工具，例如 Kubernetes，這讓開發者能對於部署環境擁有更高的控制能力。但是這僅限於自己的應用程式，當跨團隊需要交換資料時，我們仍然需要使用既有的機制：查看文件。

有沒有一個公開的地方讓我們直接查看這些資料？透過一個概觀的資料流圖，我們可以快速知道哪些資料屬於哪些團隊，這些資料又有哪些應用程式使用，而這個概略圖就是透過中央的事件管理者或者「事件調度工具」去建立。