Etcd與Raft算法
Raft保證讀請求Linearizability的方法:
- 1.Leader把每次讀請求作為一條日志記錄，以日志復制的形式提交，并應用到狀態機后，讀取狀態機中的數據返回(一次RTT、一次磁盤寫)
- 2.使用Leader Lease，保證整個集群只有一個Leader，Leader接收到請求后，記錄下當前的commit index為read index,當apply index大于等于read index后，則可以讀取狀態機中的數據返回(0次RTT、0次磁盤寫)
- 3.不適用Leader Lease，而是當Leader通過以下兩點保證整個集群中只有其一個正常工作的Leader:
3.1 在每個Term開始時，由于新選出的leader可能不知道上一個Term的commit index，所以需要先在當前新的Term提交一條空操作的日志；
3.2 Leader每次接到讀請求后，向多數節點發送心跳確認自己的Leader身份。之后的讀流程與Leader Lease的做法相同。(一次RTT、0次磁盤寫) - 4.從Follower節點讀:Follower先向Leader詢問read index，Leader收到Follower的請求后依然要通過2或3中的方法確認自己Leader的身份，然后返回當前的commit index作為read index，Follower拿到read index后，等待本地的apply index大于等于read index后，即可讀取狀態機中的數據返回(2次或1次RTT、0次磁盤寫)
Linearizability和Serializability
Serializability是數據庫領域的概念，而Lineaizability是分布式系統、并發編程領域的東西，在這個分布式SQL時代，自然Linearizability和Serializability會經常一起出現。
- 1.Serializability:數據庫領域的ACID中的I.數據庫的四種隔離級別，由弱到強分別是Read Uncommited, Read Committed(RC)，Repeatable Read(RR)和Serializability
Serializability的含義是:對并發事務包含的操作進行調度后的結果和某種把這些事務一個接一個的執行之后的結果一樣。最簡單的一種調度實現就是真的把所有的事務進行排隊，一個個的執行，顯然這滿足Serializability，問題就是性能。可以看出Serializability是與數據庫事務相關的一個概念，一個事務包含多個讀、寫操作，這些操作又涉及到多個數據對象。 - 1.Linearizability:針對單個操作，單個數據對象而說的，屬于CAP中C這個范疇。一個數據被更新后，能夠立馬被后續的讀操作讀到
- 2.Strict Serializability:同時滿足Serializability和Linearizability
舉個最簡單的例子:兩個事務T1,T2，T1先開始，更新數據對象o,T1提交。接著T2開始，讀數據對象o,提交。以下兩種調度:
- 1.T1,T2,滿足Serializability，也滿足Linearizability
- 2.T2,T1,滿足Serializability，不滿足Linearizability,因為T1之前更新的數據T2讀不到
因果一致性Causal Consistency
因果一致性，屬于弱一致性，因為在Causal Consistency中，只對有因果關系的事件有順序要求。
沒有因果一致性時會發生如下情形:
- 1.夏侯鐵柱在朋友圈發表狀態:“我戒指丟了”
- 2.夏侯鐵柱在同一條狀態下評論"我找到了"
- 3.諸葛建國在同一條狀態下評論"太棒了"
- 4.遠在美國的鍵盤俠看到"我戒指丟了" “太棒了”，開始噴諸葛建國
- 5.遠在美國的鍵盤俠看到"我戒指丟了" “我找到啦” “太棒了”，意識到噴錯人了。
所以很多系統采用因果一致性系統來避免這種問題，例如微信的朋友圈就采用了因果一致性
最終一致性Eventual Consistency.
最終一致性這個詞大家聽到的次數應該是最多的，也是弱一致性，不過因為大多數場景下用戶可以接受，應用也就比較廣泛。
理念:不保證在任意時刻任意節點上的同一份數據都是相同的，但是隨者事件的遷移，不同節點上的同一份數據總是在向趨同的方向變化。
簡單說，就是在一段時間后，節點間的數據會最終達到一致狀態。不過最終一致性的要求非常低，除了向Gossip這樣明確以最終一致性為賣點的協議外，包括Redis主備、MongoDB、乃至MySQL熱備都可以算是最終一致性，甚至如果我記錄操作日志，然后在副本故障了100天之后手動在副本上執行日志以達成一致，也算是符合最終一致性的定義。有人說最終一致性就是沒有一致性，因為沒人可以知道什么時候算是最終。
上面提到的因果一致性可以理解為是最終一致性的變種，如果進程A通知進程B它已經更新了一個數據項，那么進程B的后續訪問將返回更新后的值，并且寫操作將被保證取代前一次寫入。和進程A沒有因果關系的C的訪問將遵循正常的最終一致性規則。
最終一致性其實分支很多，以下都是它的變種:
- 1.Causal Consistency(因果一致性)
- 2.Read-your-writes Consistency(讀自己所寫一致性)
- 3.Session Consistency(會話一致性)
- 4.Monotonic Read Consistency(單調讀一致性)
- 5.Monotonic Write Consistency(單調寫一致性)
后面要提到的BASE理論中的E，就是Eventual Consistency最終一致
ACID理論
ACID是處理事務的原則，一般特指數據庫的一致性約束，ACID一致性完全與數據庫規則相關，包括約束，級聯，觸發器等。在事務開始之前和事務結束以后，都必須遵守這些不變量，保證數據庫的完整性不被破壞，因此ACID中的C表示數據庫執行事務前后狀態的一致性，防止非法事務導致數據庫被破壞。比如銀行系統A和B兩個賬戶的余額總和為100，那么無論A,B之間怎么轉換，這個余額和是不變的，前后一致的.
這里的C代表的一致性：事務必須遵循數據庫的已定義規則和約束，例如約束、級聯和觸發器。因此，任何寫入數據的數據都必須有效，并且完成的任何事務都會該筆那數據庫的狀態。沒有事務可以創建無效的數據狀態。注意，這與CAP定理中定義的一致性是不同的。
ACID可以翻譯為酸，相對應得是堿，也就是BASE.不過提BASE之前要先說下CAP，畢竟，BASE是基于CAP理論提出的折中理論
CAP理論
CAP理論中的C也就是我們常說的分布式系統中的一致性，更確切地說，指的是分布式一致性中地一種:也就是前面說地線性一致性(Linearizability)也叫做原子一致性(Atomic Consistency).
CAP理論也是個被濫用地詞匯，很多時候我們會用CAP模型去評估一個分布式系統，但是CAP模型卻有一定的局限性。因為按照CAP理論，很多系統MongoDB、ZooKeeper既不滿足(線性一致性)，也不滿足可用性(任意一個工作中的節點都要可以處理請求)，但這并不意味著它們不是優秀的系統，而是CAP定理本身的局限性(沒有考慮處理延遲，容錯等)
BASE理論
正因為CAP中的一致性和可用性是強一致行和高可用，后來又有人基于CAP理論提出了BASE理論，即基本可用(Basicly Available)、軟狀態(Soft State)、最終一致性(Eventual Consistency).BASE的核心思想是即使無法做到強一致性，但每個應用都可以根據自身的業務特點，采用適當的方法來使系統達到最終一致性。顯然最終一致性弱于CAP中的線性一致性。很多分布式系統都是基于BASE中的"基本可用"和"最終一致性"來實現的，比如MySQL/PostgreSQL Replication異步復制
ACID一致性與CAP一致性的區別.
ACID一致性使有關數據庫規則，如果數據表結構定義一個字段值是唯一的，那么一致性系統將解決所有操作中導致這個字段值非唯一的情況，如果帶有一個外鍵的一行記錄被刪除，那么其外鍵相關記錄也應該被刪除，這就是ACID一致性的意思。
CAP理論的一致性是保證同樣一個數據在所有不同服務器上的拷貝i都是相同的，這是一種邏輯保證，而不是物理，因為光速限制，在不同服務器上這種復制是需要時間的，集群通過阻止客戶端查看不同節點上還未同步的數據維持邏輯視圖。
當跨分布式系統提供ACID是，這兩個概念會混淆在一起，Google’s Spanner System能夠提供分布式系統的ACID，其包含ACID+CAP涉及，也就是兩階段提交2PC+多副本復制機制
ACID/2PC/3PC/TCC/Paxos關系
ACID是處理事務的原則，限定了原子性、一致性、隔離性、持久性。ACID、CAP、BASE這些都只是理論，只是在實現時的目標或者折中，ACID專注于分布式事務，CAP和BASE是分布式通用理論。
解決分布式事務有2PC、3PC、TCC等方式，通過增加協調者來進行協商，里面也有最終一致的思想。
而Paxos協議與分布式事務并不是同一層面的東西，Paxos用于解決多個副本之間的一致性問題。比如日志同步，保證各個節點的日志一致性，選主的唯一性。簡而言之，2PC用于保證多個數據分片上事務的原子性，Paxos協議用于保證同一個數據分片在多個副本的一致性，所以兩者可以是互補的關系，不是替代關系。對于2PC協調者單點問題，可以利用Paxos協議解決，當協調者出現問題時，選一個新的協調者繼續提供服務，原理上Paxos和2PC相似，但目的上是不同的，etcd中也有事務的操作，比如迷你事務
)
