第九章：學習要點

[kylemocode]

• 線性一致性本質上意味著 “表現得好像只有一個數據副本，而且所有的操作都是原子的”
• 單主複製（可能線性一致）, 共識演算法（線性一致）, 多主複製（非線性一致）, 無主複製（也許不是線性一致的）

[0x171-0]

線性一致

• What is Linearizability?
  • 新鲜度保证 recency guarantee
  • 創造表象 "只有一个数据副本，而且所有的操作都是原子的"
  • 線性一致的代價是性能
• 線性一致與可串行化的差異
  • 可串行化 Serializability ：隔離層級，保障多個對象的串行執行
  • 線性一致 Linearizability：單一對象的新鮮度保證
• 線性一致性 實現的方法
  • 自動排序併發請求到合理的順序
  • 任何一個讀取返回新值後，後續讀取也都必須返回新值
• 透過線性一致性實現的功能：
  • 領導者鎖
  • 唯一性
  • 跨信道時序依賴
• 單主複製、多主複製、無主複製、共識機制中，只有共識機制符合線性一致
• CAP 更好的表述成：在分區時要麼選擇一致，要麼選擇可用

排序

• 全序 vs 偏續
  • 全序：大小排序固定
  • 偏序：無法排序
    • 數學集合
    • 因果
  • 排序事件的方法：
    • 序列號：
      • 不同的節點可以運用 分奇偶數、預留節點號、預先分配區塊好錯開
    • 時間戳
      • Lamport 時間戳
      • $(counter, node ID)$
• 全序廣播
  • 需要滿足
    • 可靠交付
    • 全序交付

2PC

• 以性能為代價的 原子提交
• 由協調者 coordinator、參與者 participants構成
• 步驟：
  1. 參與者向協調者申請 全局唯一的事務 ID
  2. 參與者向協調者申請提交
  3. 協調者向所有參與者發起 帶上全局事務 ID 的 "準備" 請求 （要嫁給我嗎？）
  4. 參與者確保可以提交，並承諾 "OK" （我願意！）
  5. 協調者收到所有參與者的 OK 承諾，把事務內容寫入事務日誌當中，這也稱作 提交點 commit point（登記結婚！）
  6. 發送請求給所有參與者，若失敗或超時就會永遠重新嘗試

[Parkerhiphop]

線性一致性（一種流行的一致性模型）：其目標是使多副本資料看起來好像只有一個副本一樣，並使其上所有操作都原子性地生效。

因果性，因果性對系統中的事件施加了順序（什麼發生在什麼之前，基於因與果）。

• 較弱的一致性模型：某些事件可以是 併發 的
• 因果一致性沒有線性一致性的協調開銷，而且對網路問題的敏感性要低得多

為何需要共識？

• 如果一個節點要透過註冊，則需要知道其他的節點沒有在併發搶注同一使用者名稱的過程中
  • ex: 使用者名稱註冊問題

共識：所有節點一致同意所做決定，且這一決定不可撤銷

• 達成共識須解決的等價問題
  1. 線性一致性的 CAS 暫存器
  2. 原子事務提交
  3. 全序廣播
  4. 鎖和租約
  5. 成員 / 協調服務
  6. 唯一性約束

如果你只有一個節點，或者你願意將決策的權能分配給單個節點，所有這些事都很簡單。

• 如果該領導者失效，或者如果網路中斷導致領導者不可達，這樣的系統就無法取得任何進展
• 解法：「等待領導者恢復」、「人工」、「演算決定」

但變更領導者的共識演算法仍然必須 -> 使用「容錯的共識演算法與容錯的共識系統」

• ex: ZooKeeper 提供了 “外包” 的共識、故障檢測和成員服務

[at7211]

• 大多數複製的資料庫至少提供了 **最終一致性，**但這提供了比較弱的保證
  → 更強一致性模型，線性一致性

• 順序一致性(****Sequential Consistency)****中 process 只關心大家認同的順序一樣就行，不需要與全局時鐘一致，線性(Linearizability consistency)就更嚴格，從這種偏序（partial order）要達到全序（total order）

  要求是：

  1.任何一次讀都能讀到某個數據的最近一次寫的數據。
  2.系統中的所有 process，看到的操作順序，都與全局時鐘下的順序一致。

• 如果只有一個節點，或者願意將決策的權能分配給單個節點，所有這些事都很簡單。能夠提供線性一致的操作，唯一性約束，完全有序的複製日誌，以及更多。
  —→若需要解決共識的問題，可以找類似 ZooKeeper 的工具解決

[jxiu0129]

• 線性一制性
  • 線性一制性：新鮮度保證，不會將操作組合為事務，因此它也不會阻止寫入偏差等問題
  • 可序列化：確保事務的行為，與它們按照 某種 順序依次執行的結果相同
• 順序保證
  • 全序廣播
• 容錯共識

[taco0929]

一致性與共識

構建容錯系統的最好方法，是找到一些帶有實用保證的通用抽象，實現一次，然後讓應用依賴這些保證。
i.e.: 事務

一致性保證

複製延遲問題
收斂為弱保證：不能及時解決複製延遲問題

線性一致性

新鮮度保證：系統保障讀取到的值為最新的值
寄存器
應用：
鎖定和領導選舉
約束和唯一性保證
跨信道的時序依賴 (i.e.圖片上傳與發送)
複製方法與線性一致性
單主複製 — 可能線性一致
共識算法 — 線性一致
多主複製 — 非線性一致
無主複製 — 取決於法定人數配置與異步網路延遲
代價
i.e. 網路中斷的可能性造成單主複製無法寫入
CAP定理：分布式系統不可能同時滿足以下三點
一致性
可用性
分區容錯性

順序保證

因果順序不是全序 — 不能比較兩者之間的因果順序
完全線性一致性系統中沒有併發
線性一致性強於因果一致性，但因果一致性較線性一致性能保證更好的性能
全序廣播
可靠交付：消息不會被丟失
全序交付：消息以相同的順序傳遞給節點
i.e. 設定追加日誌

分佈式系統的共識

節點能達成共識仰賴：領導選舉、原子提交
兩階段提交：跨多節點的事物提交 — 仰賴協調者
XA事務：使用XA API查詢操作是否為分布式事務的一部份
懷疑時持有鎖

容錯共識

一致同意 — 沒有兩個節點的決定為不同
完整性 — 沒有節點可以決定兩次
終止 — 尤為崩潰的節點決定最終值

[AK4codee]

一致性保證

事務隔離主要是為了 避免由於同時執行事務而導致的競爭狀態，而分散式一致性主要關於 在面對延遲和故障時如何協調副本間的狀態。

線性一致性(原子一致性、強一致性)

• 一個系統看起來好像只有一個數據副本，而且所有的操作都是原子性的。
• 新鮮度保證（recency guarantee）: 系統應保障讀到的值是最近的、最新的，而不是來自陳舊的快取或副本。
• 線性一致資料庫中同時讀寫相同的鍵 x。在分散式系統文獻中，x 被稱為 暫存器（register），例如，它可以是鍵值儲存中的一個 鍵，關係資料庫中的一 行，或文件資料庫中的一個 文件。

依賴線性一致性

• 鎖定和領導選舉
  • 一個使用單主複製的系統，需要確保領導者真的只有一個，而不是幾個（腦裂）。
  • 一種選擇領導者的方法是使用鎖：每個節點在啟動時嘗試獲取鎖，成功者成為領導者。
• 約束和唯一性保證
  • 使用者名稱或電子郵件地址必須唯一標識一個使用者，而在檔案儲存服務中，不能有兩個具有相同路徑和檔名的檔案。
• 跨通道的時序依賴
  • 訊息佇列可能比儲存服務內部的複製（replication）更快。因為 Web 伺服器和縮放器之間存在兩個不同的通道：檔案儲存與訊息佇列。

實現線性一致的系統

• 單主複製（可能線性一致）
• 共識演算法（線性一致）
• 多主複製（非線性一致）
• 無主複製（也許不是線性一致的）

順序保證

• 領導者在單主複製中的主要目的就是，在複製日誌中確定 寫入順序（order of write）
• 可序列化，是關於事務表現的像按 某種先後順序（some sequential order） 執行的保證。它可以字面意義上地以 序列順序（serial order） 執行事務來實現，或者允許並行執行，但同時防止序列化衝突來實現（透過鎖或中止事務）。
• 分散式系統中使用時間戳和時鐘是另一種將順序引入無序世界的嘗試，例如，確定兩個寫入操作哪一個更晚發生。
• 序列號順序: 使用 序列號（sequence nunber） 或 時間戳（timestamp） 來排序事件。
• 蘭伯特時間戳 : 每個節點都有一個唯一識別符號，和一個儲存自己執行運算元量的計數器。

全序廣播

• 可靠交付（reliable delivery）: 沒有訊息丟失，如果訊息被傳遞到一個節點，它將被傳遞到所有節點。
• 全序交付（totally ordered delivery）: 訊息以相同的順序傳遞給每個節點。

分散式事務與共識

原子提交與兩階段提交

當應用準備提交時，協調者開始階段 1 ：它傳送一個 準備（prepare） 請求到每個節點，詢問它們是否能夠提交。

• 如果所有參與者都回答 “是”，表示它們已經準備好提交，那麼協調者在階段 2 發出 提交（commit） 請求，然後提交真正發生。
• 如果任意一個參與者回覆了 “否”，則協調者在階段 2 中向所有節點發送 中止（abort） 請求。

容錯共識

• 一致同意（Uniform agreement）: 沒有兩個節點的決定不同。
• 完整性（Integrity）: 沒有節點決定兩次。
• 有效性（Validity）: 如果一個節點決定了值 v ，則 v 由某個節點所提議。
• 終止（Termination）: 由所有未崩潰的節點來最終決定值。

[samwu4166]

一致性保證

• 收斂（convergence)
  因為我們預計所有的副本最終會收斂到相同的值，這是一個非常弱的保證 —— 它並沒有說什麼時候副本會收斂

• 線性一致性
  基本的想法是讓一個系統看起來好像只有一個數據副本，而且所有的操作都是原子性的。有了這個保證，即使實際中可能有多個副本，應用也不需要擔心它們。

NOTE:

• 可序列化（Serializability) - 事務的隔離屬性
• 線性一致性（Linearizability) - 是讀取和寫入暫存器（單個物件）的 新鮮度保證

顺序一致性中进程只关心大家认同的顺序一样就行，不需要与全局时钟一致，线性就更严格，从这种偏序（partial order）要达到全序（total order）

約束和唯一性保證

使用者名稱或電子郵件地址必須唯一標識一個使用者

不同的複製方法達成線性一致的比較:

• 單主複製（可能線性一致）
• 共識演算法（線性一致） - Zookeeper 【21】和 etcd 【22】就是這樣工作的。
• 多主複製（非線性一致）
• 無主複製（也許不是線性一致的）

蘭伯特時間戳
（計數器，節點 ID）$(counter, node ID)$。兩個節點有時可能具有相同的計數器值，但透過在時間戳中包含節點 ID，每個時間戳都是唯一的。