一致性：（consistency）
一致性: 在多機備份（repliaction）的場景下，數(shù)據(jù)節(jié)點之間復制數(shù)據(jù)，數(shù)據(jù)系統(tǒng)（數(shù)據(jù)庫）能夠在一定的條件下讀取相同的數(shù)據(jù)。
repliaction 的主要架構方式：
-
主從結構：有一個單一節(jié)點作為leader，寫入請求發(fā)送給這個leader，leader 同步或異步地向其余節(jié)點發(fā)送更新消息，讀取可以從各個節(jié)點讀取。
單leader節(jié)點.png -
多主結構：
有多個主節(jié)點，寫入請求發(fā)送個其中任何一個leader，由各個leader 進行同步。這種結構多用于多數(shù)據(jù)中心的備份。
-
無主結構：
沒有具體的leader節(jié)點，每個節(jié)點都是平等的，寫入請求可以發(fā)送到任何節(jié)點，讀取請求也可以發(fā)送到任何節(jié)點。
由于篇幅有限這里我們主要介紹單主結構下的一致性問題。
可線性化的一致性(強一致性)：linearizability，即同一時間讀任何個備份 總是能夠獲得同樣的數(shù)據(jù)，就好像數(shù)據(jù)只有一份。
什么時候需要強一致性：
邏輯上的約束性，全局唯一性 因果關系 （這里需要舉例說明）
多個消息通道導致的非一致性。（一致性是解決這些問題的一種方法，但是并不是唯一的一種方法）
強一致性的最簡單實現(xiàn)：
點節(jié)點結構，發(fā)送消息給各個數(shù)據(jù)點，并且返回。
最終一致性：最終一致性是最低要求的一致性的保證，當我們停下對數(shù)據(jù)庫的修改，經過一段時間之后能夠在各個節(jié)點上讀取到相同的數(shù)據(jù)結果。
但是最終一致性對于應用開發(fā)者是一個很困難處理的問題。加大了應用系統(tǒng)的復雜度。
一致性的強度變化
-
讀自己寫（能夠讀到自己寫的東西）：
簡單實現(xiàn)方式：- 如果一份數(shù)據(jù)可能被用戶修改過，就從leader 讀取，否則從follower 讀取
- 通過最后修改時間判斷，在最后修改“一分鐘”之內的數(shù)據(jù)，從leader讀取，否則從follower讀取
-
單調讀（在讀到新的數(shù)據(jù)之后，就不會再讀到老數(shù)據(jù)）：
- 簡單的實現(xiàn)方式：使用戶一直從同一個備份節(jié)點讀取
-
一致性前綴讀 （因果讀寫）：
如果一系列的寫入操作有一個確定的寫入順序，則任何讀取的人會發(fā)現(xiàn)同樣的寫入順序（舉例）
- 任何具有因果關系的寫入，需要寫入同一個partition.
- 單主情況下的數(shù)據(jù)請求都走主節(jié)點。
-
全序列廣播：
保證在主節(jié)點上的消息在所有的節(jié)點上都有，并且在各個節(jié)點順序上保證一致。
滿足特定使用情況下能夠達到 “可線性化”。將讀取作為一個操作，寫入到日志，等待日志更新提交成功的返回。（這個不好理解，可能需要講完一致性協(xié)議再考慮）
如何實現(xiàn)全局順序廣播：
使用節(jié)點間的共識
- 對于順序達成一致
- 對于數(shù)據(jù)達成一致
- 對于是否可接收達成一致
共識（consensus）
共識是指多個節(jié)點能夠對一些事情達成一致
consensus means getting several nodes to agree on something
常用的模式是指：一個或多個節(jié)點提出提議，一致性算法決定采納哪個提議。
The consensus problem is normally formalized as follows: one or more nodes may propose values, and the consensus algorithm decides on one of those values.
如何達成共識：
使用一個節(jié)點作為唯一的裁決者，由裁決者節(jié)點決每個提議。
如何在任意一個節(jié)點可能存錯誤的情況下達成共識，這個節(jié)點可能失敗后永遠不會恢復過來。
以主從結構分布式系統(tǒng)為例：如果主節(jié)點發(fā)生失敗，整個集群就不可用，雖然可以通過從節(jié)點變成主節(jié)點來實現(xiàn)，但是可能會發(fā)生腦裂，即集群中出現(xiàn)多個節(jié)點都認為自己是leader，依然可能破壞共識而造成不一致。這個邏輯鏈條就變成我希望達成一致性，需要一個裁決的節(jié)點，但是為了獲取一個裁決節(jié)點我又需要一個共識算法。
面對任意節(jié)點可能會失敗的情況，通過單一節(jié)點去達成一個集群的共識是不可能的。
使用多數(shù)裁決的方式是可以達到集群裁決的一致性。只要半數(shù)（指定個數(shù)）的節(jié)點能夠工作，就能夠達到一致性。
主從節(jié)點的結構裁決算法，為了解決腦裂的問題引入了一個叫做周期序列號的。其不追求永遠的共識，但是最求保證在一個周期內的共識（下個周期這個共識可能就會改變）。
當選舉一個新的leader 的時候，需要提一個新的周期序列號，通過全局投票的方式，決定在這個序列號所代表的周期內誰是主節(jié)點。這個序列號是單調遞增的。每個節(jié)點達成主節(jié)點的前提是，其問訊集群中的所有成員只有多數(shù)達到了一致才能認為自己是主節(jié)點。
Raft 協(xié)議就是一個這樣使用可容錯的一致性算法達來達到全局廣播一致性的算法。
raft 一致性協(xié)議的原理
- raft選主
在任意的時間，每一個服務器一定會處于以下三種狀態(tài)中的一個：領導人、候選人、追隨者。一個集群內只有一個領導者。追隨者們是被動的：他們不會發(fā)送任何請求，只是響應來自領導人和候選人的請求。領導人來處理所有來自客戶端的請求，滿足一定提交下一個節(jié)點會成為候選人狀態(tài)，可以參與競選成為一個新的領導人的。（如下圖）
Raft 服務器間的通訊僅需要 2 種 RPC。RequestVote RPC 是候選人在選舉過程中觸發(fā)的，AppendEntries RPC 是領導人觸發(fā)的，為的是復制日志條目并且提供一種心跳（heartbeat）機制。主節(jié)點正常的時候會向所有追隨者周期性發(fā)送心跳（heartbeat，不帶有任何日志條目的 AppendEntries RPC）來保證它們的領導人地位。如果一個追隨者在一個周期內沒有收到心跳信息，就叫做選舉超時（election timeout）, 然后它就會假定沒有可用的領導人并且開始一次選舉來選出一個新的領導人（并發(fā)RequestVote給所有集群中節(jié)點）。收到大多數(shù)節(jié)點投票的候選人會成為新的領導人。一旦有一個候選人贏得了選舉成為領導人，它會像其他服務器發(fā)送心跳信息來建立自己的領導地位并且組織新的選舉。
因此時間被分為一個個的任期（term），每一個任期的開始都是領導人選舉。在成功選舉之后，一個領導人會在任期內管理整個集群直到下次新的選舉。
term 的使用原則
由于通訊延時或者異常的問題，有的節(jié)點認為自己處于term1，有的節(jié)點認為自己處于term2。
在服務器之間進行通信時，會互相交換當前任期號；如果一臺服務器的當前任期號比其它服務器的小，則更新為較大的任期號。如果一個候選人或者領導人意識到它的任期號過時了，它會立刻轉換為追隨者狀態(tài)。如果一臺服務器收到的請求的任期號是過時的，那么它會拒絕此次請求。
- 2 日志復制
一旦選出了領導人，它就開始接收客戶端的請求。每一個客戶端請求都包含一條需要被復制的執(zhí)行的命令。領導人把這條命令作為新的日志條目加入到它的日志中去，然后并行的向其他服務器發(fā)起 AppendEntries RPC ，要求其它服務器復制這個條目。當這個條目被安全的復制之后，領導人會將這個條目應用到它的狀態(tài)機中并且會向客戶端返回執(zhí)行結果。如果追隨者崩潰了或者運行緩慢或者是網(wǎng)絡丟包了，領導人會無限的重試 AppendEntries RPC直到所有的追隨者最終存儲了所有的日志條目。
日志由有序編號的日志條目組成。每個日志條目包含它被創(chuàng)建時的任期號（每個方塊中的數(shù)字），并且包含用于狀態(tài)機執(zhí)行的命令。每個日志條目存儲著一條被狀態(tài)機執(zhí)行的命令和當這條日志條目被領導人接收時的任期號，每個日志條目也包含一個整數(shù)索引來表示它在日志中的位置。
領導人決定什么時候將日志條目應用到狀態(tài)機是安全的；這種條目被稱為可被提交（commited）。Raft 保證可被提交（commited）的日志條目是持久化的并且最終會被所有可用的狀態(tài)機執(zhí)行。一旦被領導人創(chuàng)建的條目已經復制到了大多數(shù)的服務器上，這個條目就稱為可被提交的領導人日志中之前的條目都是可被提交的（commited）。領導人跟蹤記錄它所知道的被提交條目的最大索引值，并且這個索引值會包含在之后的 AppendEntries RPC 中（包括心跳 heartbeat 中），為的是讓其他服務器都知道這條條目已經提交。一旦一個追隨者知道了一個日志條目已經被提交，它會將該條目應用至本地的狀態(tài)機。
-
領導人的變更：
但是當領導人崩潰（重新選舉）會導致日志不一致，比如領導人還在復制日志的時候，發(fā)生奔潰造成日志復制的缺失或者是從節(jié)點之間日志不一致。
為解決這個問題，新的領導者需要保證追隨者的日志同自己的一致，即領導人需要找到追隨者同它的日志一致的地方，然后刪除追隨者在該位置之后的條目，然后將自己在該位置之后的條目發(fā)送給追隨者。
日志可提交
同時為了保證已經被提交的日志的數(shù)據(jù)安全，raft算法還需要提供兩個額外的選主限制來保證已提交的日志的安全性。
Raft 使用投票的方式來阻止沒有包含全部日志條目的服務器贏得選舉。RequestVote RPC 提交的時候會包含候選人的日志信息，如果它自己的日志比候選人的日志要新，那么它會拒絕候選人的投票請求。Raft 通過比較日志中最后一個條目的索引和任期號來決定兩個日志哪一個更新。如果兩個日志的任期號不同，任期號大的更新；如果任期號相同，更長的日志更新
Raft 從來不會通過計算復制的數(shù)目來提交之前人氣的日志條目。領導人只會提交自己任期內的新增日志。但是領導人依然會復制前任的日志給各個從節(jié)點，但是不會直接提交，只是會在自己任期內有日志產生的時候才把前一個日志一起提交，所以之前任期內的日志條目是被間接的提交。
不能直接提交上個任期日志的原因可以看下圖：
如圖的時間序列說明了為什么領導人不能通過之前任期的日志條目判斷它的提交狀態(tài)。（a）中的 S1 是領導人并且部分復制了索引 2 上的日志條目。（b）中 S1 崩潰了；S5 通過 S3，S4 和自己的選票贏得了選舉，并且在索引 2 上接收了另一條日志條目。（c）中 S5 崩潰了，S1 重啟了，通過 S2，S3 和自己的選票贏得了選舉，并且繼續(xù)索引 2 處的復制，這時任期 2 的日志條目已經在大部分服務器上完成了復制，但是還并沒有提交。如果在（d）時刻 S1 崩潰了，S5 會通過 S2，S3，S4 的選票成為領導人，然后用它自己在任期 3 的日志條目覆蓋掉其他服務器的日志條目。然而，如果在崩潰之前，S1 在它的當前任期在大多數(shù)服務器上復制了一條日志條目，就像在（e）中那樣，那么這條條目就會被提交（S5 就不會贏得選舉）。在這時，之前的日志條目就會正常被提交。
實踐中會有很多別的方法來實現(xiàn)上個任期日志的盡早提交，比如選舉完成后領導者模擬一個空的日志條目提交的流程，以達到間接提交上個周期日志的的目的。或者是和集群內的大多數(shù)節(jié)點做一次rpc 通訊（其實就是為了證明當前自己還是集群最新的leader），如果成功就提交上一個任期內的日志。
集群成員變化
截止到目前，我們都假定集群的配置（加入到一致性算法的服務器集合）是固定的。在實際中，我們會經常更改配置，（添加/摘除額外的節(jié)點）
為了讓配置修改機制能夠安全，那么在轉換的過程中在任何時間點兩個領導人不能再同一個任期被同時選為領導人。不幸的是，服務器集群從舊的配置直接升級到新的配置的任何方法都是不安全的，一次性自動的轉換所有服務器是不可能的，所以集群可以在轉換的過程中劃分成兩個單獨的組（如 圖 -10 所示）。
通過一致性算法統(tǒng)一更新配置
領導人首先在它的日志中創(chuàng)建 C(old,new)， C(old,new) 是指即包含new 的所有節(jié)點，又包含old 所有節(jié)點 配置條目并且將它提交到 C(old,new)。然后它創(chuàng)建 C(new) 配置條目并且將它提交到使用新配置的大部分機器上。如果在 C(old,new)的過程中主節(jié)點掛了，新選舉出來的領導者必然是有 C(old,new) 這條日志的。
raft 協(xié)議 （主從結構共識協(xié)議）的限制
所有的寫入請求必須經過leader, 每次請求這個leader和至少半數(shù)的節(jié)點通訊，leader 就成為了這個系統(tǒng)的性能瓶頸。在單leader節(jié)點的邊界，由于吞吐量的瓶頸，整個系統(tǒng)可能會頻繁的選主，易造成雪崩效應。
廣播順序一致性如何變成強一致性
對于強一致性，要求當前讀取任意一個節(jié)點就能獲取當前集群最新的狀態(tài)。類似raft這種日志廣播分發(fā)的算法，直接讀取從節(jié)點，只能保證日志順序，并不能獲取到整個集群最新的已提交的日志。一般的解決思路是從主節(jié)點讀取，但是當讀取主節(jié)點的時候，并不一定也是最新提交的日志，因為在讀取的時候所謂的主節(jié)點可能已經不是集群當前的主節(jié)點了（可能恰巧這個時候發(fā)生了新的選主）。解決的辦法是提交一個讀取的請求，即將一個讀請求變成一個寫請求。當這個讀請求變成commited 狀態(tài)時則表示，當前系統(tǒng)的最新狀態(tài)就是這個讀commit所對應的狀態(tài)。（即這個讀請求在集群里面走了一圈，達成共識當前最新的數(shù)據(jù)狀態(tài)是怎么樣子的）這個也是滿足cap原理的。
