原文：
分布式場景下的數(shù)據(jù)復制究竟怎么做 - 知乎 (zhihu.com)

主從復制

集群中有一個主節(jié)點，寫操作都必須經(jīng)過主節(jié)點完成，讀操作主從節(jié)點都可以處理。

image.png

同步復制

數(shù)據(jù)在副本上落盤才返回。

• 優(yōu)點：保證在副本上的數(shù)據(jù)是最新數(shù)據(jù)。
• 缺點：延遲高，響應慢。

異步復制

數(shù)據(jù)不保證在副本上落盤。

• 優(yōu)點：延遲低
• 缺點：不能保證在副本上的數(shù)據(jù)最新。

不能把集群中所有節(jié)點設置為同步節(jié)點，因為這樣的話任何一個節(jié)點的停滯都會導致整個集群的不可用。像Paxos、Raft算法，都要求集群中大多數(shù)節(jié)點返回就可以了。部分同步、部分異步的集群配置成為半同步（semi-sync）的集群配置。

新增從節(jié)點

• 主節(jié)點生成快照數(shù)據(jù)
• 主節(jié)點將快照數(shù)據(jù)發(fā)送到從節(jié)點。
• 從節(jié)點請求主節(jié)點快照數(shù)據(jù)之后的數(shù)據(jù)。
• 重復上面三步直到從節(jié)點追上主節(jié)點的進度。

處理節(jié)點失效

從節(jié)點失效

從節(jié)點崩潰恢復之后按照前面新增新的從節(jié)點的步驟來追上主節(jié)點的數(shù)據(jù)進度。

主節(jié)點失效

• 主節(jié)點失敗時需要提升某個從節(jié)點為新的主節(jié)點，同時需要通知客戶端新的主節(jié)點。
• 自動切換主節(jié)點的步驟通常如下：
• 確認主節(jié)點失效。大部分系統(tǒng)采用基于超時的機制，主從節(jié)點直接發(fā)送心跳消息，主節(jié)點在某個時間內都沒有響應，則認為主節(jié)點已經(jīng)失效。
• 選舉新的主節(jié)點。通過選舉的方式（超過半數(shù)以上的從節(jié)點達成共識）來選舉新的主節(jié)點，新的主節(jié)點是與舊的主節(jié)點數(shù)據(jù)差異最小的一個，最小化數(shù)據(jù)丟失的風險。
• 重新配置使新的主節(jié)點上線。

除了以上步驟之外，還有以下問題需要考慮：

• 如果使用異步復制機制，而且在失效之前，新的主節(jié)點并沒有收到舊的主節(jié)點的所有數(shù)據(jù)，那么在舊的主節(jié)點重新上線之后，未完成復制的數(shù)據(jù)將被丟棄。
• 可能會出現(xiàn)集群同時存在兩個主節(jié)點的情況，也就是所謂的腦裂（split brain）現(xiàn)象，此時兩個主節(jié)點都認為自己是主節(jié)點并且都能接收客戶端的寫數(shù)據(jù)請求，會導致數(shù)據(jù)丟失或者破壞。
• 如何設置合理的超時時間來判斷主節(jié)點失效？如果太大意味著總體恢復時間長，如果太小意味著某些情況下可能主節(jié)點并未失效但是被誤判為失效了，比如網(wǎng)絡峰值導致延遲高等原因，這樣會導致很多不必要的主節(jié)點切換。

上述的問題，包括節(jié)點失效、網(wǎng)絡不可靠、副本一致性、持久性、可用性與延遲之間的各種細微的權衡，正是分布式系統(tǒng)核心的基本問題。

復制日志的實現(xiàn)

• 基于語句的復制

主節(jié)點記錄所執(zhí)行的每個寫請求并將該語句做為日志發(fā)送給從節(jié)點。但是有些場景并不適合這么做，比如：

• 調用任何非確定函數(shù)的語句，比如NOW()獲得當前時間，RAND()返回一個隨機數(shù)。

• 語句中使用了自增列，或者依賴于當前數(shù)據(jù)庫的數(shù)據(jù)。

• 有副作用的語句，在每個副本上面執(zhí)行的效果不一樣。

• 基于預寫日志(WAL)

將對數(shù)據(jù)庫的操作寫入日志，傳送到從節(jié)點上然后執(zhí)行，得到與主節(jié)點相同的數(shù)據(jù)副本。

• 基于行的邏輯日志復制

所謂的邏輯日志，就是復制與存儲引擎采用不同的日志格式，這樣復制與存儲邏輯剝離，這種日志稱為邏輯日志，與物理存儲引擎的數(shù)據(jù)區(qū)分開。由于邏輯日志與存儲引擎邏輯上解耦，因此可以更好的向后兼容，也更好的能被外部程序解析。

對于關系型數(shù)據(jù)庫，其邏輯日志是一系列用來描述數(shù)據(jù)表行級別的寫請求：

• 插入行：日志包括所有相關列的新值。
• 刪除行：日志中保證要有足夠的信息來唯一標識待刪除的行，通常是主鍵。
• 更新行：日志中保證要有足夠的信息來唯一標識待更新的行，同時也有所有列的新值。

多主節(jié)點復制

適用場景

• 多數(shù)據(jù)中心

為了容忍整個數(shù)據(jù)中心級別故障或更接近用戶，可以把數(shù)據(jù)庫的副本橫跨多個數(shù)據(jù)中心。在每個數(shù)據(jù)中心內，采用常規(guī)的主從復制方案；而在數(shù)據(jù)中心之間，由各個數(shù)據(jù)中心的主節(jié)點來負責同其他數(shù)據(jù)中心的主節(jié)點進行數(shù)據(jù)的交換、更新。

image

主從復制的優(yōu)缺點：

優(yōu)點

• 性能：每個寫操作可以在本地數(shù)據(jù)中心就近快速響應，采用異步復制方式將變化同步到其他數(shù)據(jù)中心。
• 容忍數(shù)據(jù)中心失敗：單個數(shù)據(jù)中心失敗，不影響其他數(shù)據(jù)中心的繼續(xù)運行。
• 容忍網(wǎng)絡問題：主從復制模型中寫操作是同步操作，對數(shù)據(jù)中心之間的網(wǎng)絡性能和穩(wěn)定性等要求更高。多主節(jié)點模型采用異步復制，可以更好的容忍這類問題。

缺點：多個數(shù)據(jù)中心可能同時修改同一份數(shù)據(jù)，造成寫沖突。

• 離線客戶端操作

每個客戶端可以認為是一個獨立的數(shù)據(jù)中心，這樣用戶就可以在離線的狀態(tài)下使用客戶端，而在網(wǎng)絡恢復之后再將數(shù)據(jù)同步到服務器。

• 協(xié)作編輯

允許多個用戶同時編輯文檔，如google docs。這樣每個用戶就是一個獨立的數(shù)據(jù)中心了。

處理寫沖突

多主復制最大的問題就是要解決寫沖突，如下圖所示。

image.png

兩個用戶同時編輯wiki頁面，發(fā)生了寫沖突。

• 同步與異步?jīng)_突檢測

如果是主從復制數(shù)據(jù)庫，第二個寫請求會被阻塞到第一個寫請求完成。而在多主從復制模型下，兩個寫請求都是成功的，并且只有在之后才能檢測到寫沖突，而那時候要用戶來解決沖突已經(jīng)為時已晚了。

如果要多主從復制模型來做到同步檢測沖突，又失去了多主節(jié)點的優(yōu)勢：允許每個主節(jié)點接受寫請求。

因此如果確實想要做到同步檢測寫沖突，應該考慮使用單主節(jié)點的模型而不是多主從節(jié)點模型。

• 避免沖突

如果應用層能保證針對特定的一條記錄，每次修改都經(jīng)過同一個主節(jié)點，就能避免寫沖突問題。

但是，在數(shù)據(jù)中心發(fā)生故障，不得不路由請求到另外的數(shù)據(jù)中心，或者用戶漫游到了另一個位置，更靠近另一個數(shù)據(jù)中心等場景下，沖突避免不再有效。

• 收斂于一致狀態(tài)

有以下方式解決沖突的收斂：

• 給每個寫入分配唯一的ID，如時間戳、足夠長的隨機數(shù)、UUID等，規(guī)定只有高ID的寫入做為勝利者。如果是基于時間戳的對比，這種技術被稱為后寫入者獲勝（last write win），但是很容易造成數(shù)據(jù)丟失。
• 給每個副本分配一個唯一的ID，并制定規(guī)則比如最高ID的副本寫入成功，這種方式也會導致數(shù)據(jù)丟失。
• 以某種方式將這些值合并在一起。
• 使用預定義的格式將這些沖突的值返回給應用層，由應用層來解決。
• 自定義沖突解決邏輯

解決沖突最合適的方式還是依靠應用層，可以在寫入或者讀取時執(zhí)行。例如多機房場景下，寫入的業(yè)務層針對數(shù)據(jù)一致性發(fā)起仲裁判斷，最終將結果合并修改寫入的方式。

無主節(jié)點復制

放棄主節(jié)點，允許所有節(jié)點處理來自客戶端的寫請求，如Dynamo、Riak等。

節(jié)點失效時寫入數(shù)據(jù)庫

對于無主節(jié)點復制的集群而言，當向有三個副本的集群寫入數(shù)據(jù)時，只要其中有兩個副本寫入完成則認為寫入成功，而可以容忍其中一個節(jié)點的失效。那么當這個失效節(jié)點重新上線時，則可能讀到已經(jīng)過期的數(shù)據(jù)。為了解決這個問題，當客戶端從集群中讀取數(shù)據(jù)時，并不是只向一個副本發(fā)起請求，而是并行地發(fā)送到多個副本，客戶端可以根據(jù)數(shù)據(jù)版本號來確定哪個數(shù)據(jù)最新。

讀寫quorum

在有三個副本的情況下，如果有兩個副本寫入成功，那么意味著最多有一個副本可能包含舊的值，此時如果向至少兩個副本發(fā)起讀請求，通過版本號可以確定至少有一個包含新的值。

推而廣之，如果有n個副本，寫入需要w個節(jié)點確認，讀取必須至少查詢r個節(jié)點，則只需要w+r>n，那么讀取的節(jié)點中一定包含新值。

上述參數(shù)通常是可以配置，比如n取奇數(shù)值，而r、w取(n+1)/2。也可以根據(jù)業(yè)務需求靈活配置，比如對于讀多寫少的業(yè)務，設置w=n或者r=1，這樣讀取速度更快，但是只要一個節(jié)點的寫入失敗而導致quorum寫入失敗。

檢測并發(fā)寫

請求在不同節(jié)點上可能會呈現(xiàn)出不同的順序，如下圖所示：

image

客戶端A和B同時發(fā)起向主鍵X的寫請求：

節(jié)點1收到客戶端A的寫請求，但是由于節(jié)點緊接著就失效了，沒有收到客戶端B的寫請求。

節(jié)點2首先收到A的寫請求，接著才收到B的寫請求。

節(jié)點3與2相反，先收到B再收到A的寫請求。

如果處理方式僅僅是每次收到新的寫請求就簡單覆蓋原來的值，那么這些節(jié)點永遠也無法達成一致。

所以需要一種更合理的方式來解決并發(fā)寫沖突。

• 最后寫入者勝出（Last Write Win，簡稱LWW）

為每個寫請求附件一個時間戳，然后選擇最新即最大的時間戳，丟棄較早時間戳的寫入，這種方案稱為Last Write Win。

這種方案的問題在于：物理時間本身就不可信任，一個機器上的時間到了另一個機器上并不就精準。另外，犧牲了部分的寫入數(shù)據(jù)，比如某客戶端寫入時返回成功，但是會被后面并發(fā)寫入但是被認為更晚時間的寫入給覆蓋掉，這樣這部分認為寫入成功的數(shù)據(jù)就丟失了。

要確保LWW無副作用的唯一辦法是：之寫入一次然后寫入值視為不可變。這樣就能避免對同一個主鍵的覆蓋。例如，cassandra的推薦使用方式是使用UUID做為主鍵，這樣每個寫操作都針對不同的、系統(tǒng)唯一的主鍵。

• Happen-before關系與并發(fā)

兩件事情A、B只有三種可能存在的關系：

• A在B之前發(fā)生。
• B在A之前發(fā)生。
• A、B并發(fā)進行。

一件事情在另一件事情之前發(fā)生，說明兩者之間存在依賴關系。比如A說了一句話，而B需要對這句話進行回應，回應這個事件就依賴于A說話這個事件，此時B的回應依賴于A的話，因此B的回應肯定發(fā)生A說話之后。

如果兩件事情之間沒有依賴關系，那么先后順序是無所謂的，即并發(fā)進行。

來看一個實際的例子，兩個客戶端同時向一個購物車添加物品：

image

流程如下：

• 客戶端1首先將牛奶放入購物車，服務器分配版本號1，將值與版本號一起返回給客戶端。
• 客戶端2將雞蛋放入購物車，因為此時客戶端2并不知道客戶端1已經(jīng)放入了牛奶，因此認為雞蛋是購物車中的唯一物品。服務器寫入并分配版本號2，將雞蛋和牛奶存儲為兩個單獨的值，最后將版本號2和值返回給客戶端2。
• 同理，客戶端1再次寫入時也沒有意識到2已經(jīng)修改了購物車，此時它想繼續(xù)添加免費，認為此時購物車的內容應該是[牛奶,面粉]，因此將這個值與版本號1一起發(fā)給服務器。服務器收到之后，意識到是針對版本號1做的修改，即將[牛奶]修改成[牛奶面粉]，但是另一個值[雞蛋]則是新的并發(fā)操作。因此，服務器分配了一個新的版本號3，版本號3的值[牛奶,面粉]覆蓋版本1的[牛奶]，同時保留版本號2的值[雞蛋]，一起返回給客戶端1。
• 客戶端2想加入火腿，而它也不知道客戶端1添加了面粉。其收到的最后一個響應中服務器給的值是[牛奶]和[雞蛋]，因此進行了合并并且加入自己要添加的火腿，向服務器發(fā)送了版本號2以及新的值[雞蛋,牛奶,火腿]。服務器檢測到版本號2將覆蓋原來的值[雞蛋]，但是與[牛奶,面粉]是同時發(fā)生，所以設置了版本號4并將這些值一起返回給客戶端2。
• 最后，客戶端1想添加培根，在以前的版本3中從服務器收到了值[牛奶,面粉]和[雞蛋]，所以進行了合并，將添加了培根以及合并之后的值[牛奶,面粉,雞蛋,培根]和版本號3來覆蓋[牛奶,面粉]，但是由于與[雞蛋，牛奶，火腿]并發(fā)，所以服務器會保留這些值。

服務器判斷操作是否并發(fā)的依據(jù)主要依靠版本號：

• 服務器為每個主鍵維護一個版本號，每當主鍵新值寫入時遞增版本號，并將新版本號與寫入的值一起保存。
• 當客戶端讀取主鍵時，服務器將返回所有（未被覆蓋）當前值以及最新的版本號，且要求寫入之前，客戶端必須先發(fā)送讀請求。
• 客戶端寫主鍵，寫請求必須包含之前讀到的版本號、讀到的值和新值合并后的集合。寫請求的響應可以像讀請求一樣，返回所有值，這樣就可以像購物車例子那樣一步步鏈接起多個寫入的值。
• 當服務器收到帶有特定版本的寫入時，覆蓋該版本號或更低版本的所有值（因為知道這些值已經(jīng)被合并到新傳入的值集合中），但必須保留更高版本號的所有值（因為這些值與當前的寫操作屬于并發(fā)）。

這種方案不會讓寫入的值丟失，但是需要在客戶端做合并操作，將多個寫入的值進行合并。

復制滯后（replication lag）問題

如果一個應用正好從一個異步復制的從節(jié)點上讀取數(shù)據(jù)，則可能讀取不到最新的數(shù)據(jù)，這是因為主從節(jié)點的數(shù)據(jù)不一致導致的。理論上不一致狀態(tài)在時間上并沒有上限。以下描述幾個復制滯后導致的問題。

讀自己的寫（reading your own writes）

用戶在寫入數(shù)據(jù)不久就馬上查看數(shù)據(jù)，而新數(shù)據(jù)并未到達從節(jié)點，這樣在用戶看來可能讀到了舊的數(shù)據(jù)。這樣情況需要“寫后讀一致性（read-after-write consistency）”，該機制保證每次用戶讀到的都是自己最近的更新數(shù)據(jù)，但是對其他用戶則沒有任何保證。

image

在上圖中，用戶1234首先向主節(jié)點寫入數(shù)據(jù)，SQL執(zhí)行成功之后返回，而此時用戶再次向從節(jié)點2發(fā)起讀剛才寫入數(shù)據(jù)的請求，但是卻讀到了舊的數(shù)據(jù)。

有以下方案實現(xiàn)寫后讀一致性。

• 如果用戶訪問可能會被修改的內容，從主節(jié)點讀取。比如社交網(wǎng)絡的本用戶首頁信息只會被本人修改，訪問用戶自己的首頁信息通過主節(jié)點，而訪問其他用戶的首頁信息則走的從節(jié)點。
• 如果應用大部分內容都可能被所有用戶修改，則上述方法不太適用。此時需要其他機制來判斷哪些請求需要走主節(jié)點，比如更新后一分鐘之內的請求都走的主節(jié)點。
• 客戶端可以記住自己最近更新數(shù)據(jù)的時間戳，在請求數(shù)據(jù)時帶上時間戳，如果副本上沒有至少包含該時間戳的數(shù)據(jù)則轉發(fā)給其他副本處理，直到能處理為止。但是在這里，“時間戳”可以是邏輯時鐘（比如用來指示寫入數(shù)據(jù)的日志序列號）或者實際系統(tǒng)時鐘（而使用系統(tǒng)時間又將時間同步變成了一個關鍵點）。
• 如果副本分布在多數(shù)據(jù)中心，必須將請求路由到主節(jié)點所在的數(shù)據(jù)中心。

單調讀（monotonic reads）

單調讀一致性保證不會發(fā)生多次讀同一條數(shù)據(jù)出現(xiàn)回滾（moving backward）的現(xiàn)象。這個是比強一致性弱，但是比最終一致性強的保證。

image

在上圖中，用戶2345發(fā)起了兩次讀請求，第一次向從節(jié)點1發(fā)起的請求拿到了最新的數(shù)據(jù)，但是第二次向從節(jié)點2發(fā)起的請求得到了舊的數(shù)據(jù)，這在用戶看來，數(shù)據(jù)發(fā)生了“回滾”。

單調讀一致性可以確保不會發(fā)生這種異常。當讀取數(shù)據(jù)時，單調讀保證：如果某個用戶進行多次讀取，則絕對不會看到數(shù)據(jù)回滾現(xiàn)象，即在讀取到新值之后又發(fā)生讀取到舊值的情況。

實現(xiàn)單調讀一致性的一種方式每個用戶的每次讀取都從固定的同一副本上進行讀取。

前綴一致讀（consistent prefix reads）

前綴一致性讀保證，對于一系列按照某個順序發(fā)生的寫請求，讀取這些內容時也會按照當時寫入的順序來。

例如，正常情況下，是如下的對話：

poons先生：cake小姐，您能看見多遠的未來？

cacke小姐：通常約10秒，poons先生。

image

但是在上圖中，從觀察者角度，數(shù)據(jù)的先后順序發(fā)生了混淆，導致了邏輯上的混亂。

這種問題是分區(qū)情況下出現(xiàn)的特殊問題，在分布式數(shù)據(jù)庫中，不同的分區(qū)獨立運行，因此不存在全局寫入順序，這就導致用戶從數(shù)據(jù)庫中讀取數(shù)據(jù)時，可能看到數(shù)據(jù)庫某部分的舊值和一部分的新值。

實現(xiàn)前綴一致性的一種方案是確保任何具有因果順序關系的寫入都交給一個分區(qū)來完成，但是該方案真實實現(xiàn)起來效率不高。