讀書筆記：Distributed Systems for Fun and Profit

分布式系統是一個寬泛的研究領域。

我們常常會聽到一些關于分布式的很多技術、系統之類的名詞但又不太清楚它們真正的内涵，比如說Hadoop、Spark、Paxos、Raft之類。對于分布式系統的初學者來說，更好入門的方法可能是快速了解分布式領域的一些已解決或未解決的問題、較為經典的一些方法和定理以及它們之間的關系。

在此推薦一個知乎的話題“學習分布式系統需要怎樣的知識”，裡面@馬超Terminal的回答很好的概括了初學者需要了解的分布式系統領域的全貌。另外就是别人推薦給我的一本由六個章節組成的書，其實是大神Mikito Takada撰寫的部落格“Distributed Systems for Fun and Profit”。這本書揭示了分布式系統的冰山一角，它不細糾一些算法的細節，重在梳理分布式系統覆寫的東西，可讀性很強。此處附上原文：

http://book.mixu.net/distsys/

下面是我自己讀該部落格的一些總結。

Introduction

大多數分布式程式設計都是在解決兩個“分布式”導緻的後果：

1. 以光速傳播的資訊
2. 沒有成功獨立的獨立事件

更通俗地說，分布式程式設計的核心在于處理“距離”，和它所帶來的一些其他的限制。這些限制決定了系統設計的可能性。希望我們在閱讀完整篇文章之後，更好地了解“距離”、“時間”和一緻性模型如何互相作用。

Chapter 1: Distributed systems at a high level

"分布式程式設計是解決您可以在使用多台計算機的單台計算機上解決的相同問題的藝術。"

第一章通過介紹一些重要的術語和概念，從高層次上介紹了分布式系統。

既然分布式系統會帶來各種問題，那為什麼我們還要使用分布式系統？

原因在于——“問題規模”，規模的增加使得我們已經無法使用單個節點去解決了，要麼是成本太大，要麼是硬體資源的瓶頸。

總的來說，我們需要分布式系統的原因在于：

• Storage:擴充存儲能力
• Computation:擴充計算能力

1. 目标

Scalability可擴充性：

系統（包括網絡、程序任務等）能夠處理越來越多工作的能力。包括一下三個次元：

• Size scalability大小（數量）可擴充性：添加更多節點應該使系統線性更快​​; 增長資料集不應該增加延遲。
• Geographic scalability地理（位置）可擴充性：應該可以使用多個資料中心來減少響應使用者查詢所需的時間，同時以一種合理的方式處理跨資料中心延遲。
• Administrative scalability管理可擴充性：添加更多節點不應增加系統的管理成本（例如管理者與機器的比率）。

Performance(and latency)性能和延遲：

系統完成的有用工作量與所用時間和資源的比。

具體可以以下面的一個或多個項來進行度量：

• Short response time/Low latency for a given piece of work：即延遲。
• High throughput(rate of processing work)：吞吐量。
• Low utilization of computing resources：資源使用率。

Availabilty可用性：

系統處于運作狀态的時間比例。如果使用者無法通路系統，則稱其不可用。

公式上可以表示為：Availability = uptime / (uptime + downtime)

技術上來說，可用性的關鍵在于容錯。

從某種意義上說，可用性是一個比正常運作時間更廣泛的概念，因為影響服務的可用性也可能是網絡中斷等外部因素。

Fault tolerance容錯性：

一旦發生故障，系統仍然能夠以明确定義的方式處理已考慮到的故障的能力。

需要明确的是，容錯的“錯”是系統設計時已考慮到的錯誤，若是沒有考慮過的故障，系統顯然無法相容。

1. 限制

分布式系統受兩個實體因素的限制：

• 節點數（随着所需的存儲和計算能力而增加）
• 節點之間的距離（資訊傳播，最快是以光速傳播）

在這些限制将會導緻

• 獨立節點數量的增加會增加系統故障的可能性（降低可用性并增加管理成本）
• 獨立節點數量的增加可能會增加節點之間通信的需求（随着規模的增加而降低性能）
• 地理距離的增加會增加遠端節點之間通信的最小延遲（降低某些操作的性能）

1. 抽象與模型

将分布式系統的設計抽象化的号出在于——消除與所要解決問題無關的現實條件，使事情更易于管理。而模型則以精确的方式描述分布式系統的關鍵屬性。模型的分類有：

• System model (asynchronous / synchronous)
• Failure model (crash-fail, partitions, Byzantine)
• Consistency model (strong, eventual)

良好的抽象使得使用系統更容易了解。

在存在許多節點的現實狀況與我們對“像單個系統一樣工作”的系統的需求之間存在着緊張關系。通常，最熟悉簡單的模型（例如，在分布式系統上實作共享記憶體抽象）太昂貴了。

此處有這樣的關系：

系統内部細節	人對系統的了解	系統性能
暴露更多	更難	更高
暴露更少	更容易	更低

CAP定理就是對分布式系統各個方面性能取舍關系的著名理論。

一個最為理想的系統必須既滿足開發程式員的需求（幹淨舒服易了解的語義和設計）和業務需求（可用性、一緻性、延遲）。

1. 系統設計的常用技術——Partition and Replicate(分區和複制)

資料集在多個節點之間配置設定的方式非常重要。為了進行任何計算，我們需要定位資料然後對其進行操作。有兩種基本技術可以應用于資料集：

• Partition分區：将資料集分割為多個節點以允許更多并行處理。
• replication複制：将資料集複制或緩存在不同的節點上，以減少用戶端和伺服器之間的距離，并提高容錯能力。

分區提高了系統的性能（限制分區中的資料量）和可用性（對于分區資料中某個節點的失敗但不會影響系統其他分區資料）。複制同樣提高了系統的性能以及可用性，同時提升了系統的容錯性。害怕丢失可用性或降低性能？複制資料以避免瓶頸或單點故障。計算慢？在多個系統上複制計算。慢I / O？将資料複制到本地緩存以減少延遲，或将資料複制到多台計算機上以提高吞吐量。但這裡值得一提的是，複制同時也引起了一緻性的問題。

有許多算法實作複制和分區，每個算法都有不同的限制和優點，需要根據您的設計目标進行評估。

Chapter 2: Up and down the level of abstraction

一個好的抽象，能平衡“可了解”和“高效”之間的關系

1. 系統模型——“保留必不可少的東西，但卻能廣泛使用。”(System model)

分布式系統的關鍵屬性是分布。更具體地說，分布式系統中的程式：

• 在獨立節點上并發運作。
• 存在非确定性和因網絡問題導緻的資訊丢失。
• 沒有共享記憶體或共享時鐘。

系統模型是為了抽象分布式系統環境和實作的一組假設，包括節點及它們之間通信鍊路的方式、關于時間和順序的假設等。

一個強大的系統模型是做出最弱假設的模型：為這樣的系統編寫的任何算法都能夠很好地容忍不同的環境，因為它隻做很少和非常弱的假設前提。

1. 系統模型中的節點(Nodes)

節點指的是參與運算和存儲任務的主機。它們的任務包括執行程式、存儲資料、維護一個時鐘（不一定是準确的）。

節點運作确定性算法：節點執行計算任務後的本地狀态以及發送的消息由接收到的消息和接收消息時的本地狀态唯一确定。

節點的故障模型：

• Crash-recovery崩潰恢複故障模型：節點隻能通過崩潰後停止工作，并且可能在之後恢複工作。
• Byzantine fault tolerance拜占庭容錯：節點可以能以任意方式發生故障，其容錯過于複雜昂貴，現實中很少處理。

1. 節點的通信連結(Communication links)

通信鍊路将各個節點互相連接配接，并允許以任一方向發送消息。

讨論分布式算法的許多書籍假設每對節點之間存在單獨的連結，連結為消息提供FIFO（先進先出）順序，它們隻能傳遞已發送的消息，并且發送的消息可以是丢失。

一般來說，最好将網絡視為不可靠并受到消息丢失和延遲的影響。

當網絡出現故障而節點本身仍然可操作時，會發生網絡分區。發生這種情況時，消息可能會丢失或延遲，直到修複網絡分區。某些用戶端可以通路分區節點，是以必須與崩潰節點差別對待。

1. 關于時間/順序的假設(Time/Order)

• 同步系統模型：程序以鎖步執行，消息傳輸延遲有一個已知的上限; 每個過程都有一個準确的時鐘。
• 異步系統模型：沒有時間假設。例如，流程以獨立的速率執行；消息傳輸延遲沒有限制；無時鐘依賴。

解決同步系統模型中的問題更容易，因為關于執行速度，最大消息傳輸延遲和時鐘精度的假設都有助于解決問題，因為您可以根據這些假設進行推斷，并通過假設它們永遠不會發生來排除不友善的故障情況。但假設同步系統模型不是特别現實，真實世界的系統最多是部分同步的：它們偶爾可以正常工作并提供一些上限，但有時會無限期地延遲消息并且時鐘不同步。

1. 共識問題(Consensus)

如果幾個計算機（或節點）都同意某個值，那麼它們就會達成共識。更正式地說：

• Agreement協定：所有正确的節點程序對某個值達成共識。
• Integrity完整性：每個正确的節點程序最多承認一個值。
• Termination終止：所有正确的節點程序最終都會同意某個值。
• Validity有效性：如果所有正确的節點程序提出相同的值V，那麼所有正确的節點程序達成一緻，承認值V。

共識問題是許多商業分布式系統的核心，解決共識問題可以解決幾個相關的、更進階的問題，如原子廣播和原子送出。

1. 兩個不可能理論(FLP/CAP)

FLP與設計分布式算法的人特别相關。

CAP與從業者更相關的相關結果， 需要在不同系統設計之間進行選擇。

The FLP impossibility result:

不存在一個完全滿足一緻性的異步算法。即使該異步系統隻考慮節點的failure，并且消息沒有在通信中丢失，而且最多一個程序失敗。

這裡需要提到我們判斷分布式算法是否正确的三個标準：

• Termination終止性：非失敗程序最終可以做出選擇。即算法必須在有限時間内結束，不能無限循環。
• Agreement一緻性：所有程序必須做出相同的決議。
• Validity合法性：程序的決議值必須是其他程序送出的請求值。排除程序初始值對自身的幹擾。

進一步地說，FLP不可能定理意思是不存在滿足完全一緻性且滿足上訴三個标準的異步算法。

The CAP theorem:

該定理說明了這三個屬性：

• Consistency一緻性：所有節點在同一時刻擁有同一個值。
• Availability可用性：節點故障不會阻止系統（其他節點）繼續運作。
• Partition tolerance:分區容錯性：盡管由于網絡或節點故障導緻消息丢失，系統仍繼續運作。

最多隻可能有兩個屬性同時滿足。

三種不同的系統類型：

• CA：包括完全嚴格的仲裁協定，例如2PC。
• CP：包括多數仲裁協定，例如Paxos、Raft。
• AP：包括使用沖突解決的協定，例如Dynamo、Gossip。

現實的分布式體系中，常常需要保證分區容錯性，是以大多數情況下我們都需要在一緻性和可用性中作抉擇。

一緻性模型的總結：

Strong consistency models (capable of maintaining a single copy)

• Linearizable consistency
• Sequential consistency

Weak consistency models (not strong)

• Client-centric consistency models
• Causal consistency: strongest model available
• Eventual consistency models

Chapter 3: Time and order

Order：系統完成一個任務的操作順序。存在partial order和total order。

Time：時間，a source of order。三種不同的解釋：事件順序、時間戳、持續時間。

“各個節點時間相同？”，對此問題使用不同的時鐘假設是不同的：

• Global clock全局時鐘：相同（同步系統模型，但存在通信會延遲）
• Local clock本地時鐘：不同（部分同步系統模型，本地有序，而全局無序）
• No clock不使用時鐘：不同（異步系統模型，本地有序，遠端通過互動也可以确定順序）

Order和Time在分布式系統中至關重要。Order可以確定操作順序，即保證了程序算法的正确性，同時也可以利用在資源争奪的先後問題中；Time除了可以用來判斷Order之外，還可以判斷是否有網絡延遲，制作成故障檢測器。

邏輯時鐘：

由于實體時鐘的使用存在着延遲限制，是以我們更喜歡使用邏輯時鐘。

Lamport clock:

系統維護一個計數器counter

• 隻要程序有效，counter + 1
• 每當程序發送消息時帶上count
• 收到消息時，将計數器設定為 max(local_counter, received_counter) + 1

Vector clock:

每個節點維護一個計數器清單，每個節點一個。

故障檢測器：

心跳消息+定時器

Chapter 4: Replication: preventing divergence

兩種複制模型：

• Synchronous replication同步複制：接受到用戶端的請求之後，各節點先同步并且傳回到此節點之後，再響應用戶端。
• Asynchronous replication異步複制：接受到用戶端的請求之後，先響應用戶端，再進行各節點先同步并且傳回到此節點。

兩種複制技術：

• Replication methods that prevent divergence (single copy systems)

  防止分歧的複制方法（單拷貝系統）

• Replication methods that risk divergence (multi-master systems)

  分歧冒險的複制方法（多主系統）

第一組方法具有“行為類似于單個系統”的屬性。特别是，當發生部分故障時，系統確定隻有一個系統副本處于活動狀态。此外，系統確定副本始終一緻。這被稱為共識問題。mutual exclusion, leader election, multicast, atomic broadcast都是更普遍的共識問題的執行個體。

Single copy consistency單拷貝一緻性複制算法：

• 1n messages (asynchronous primary/backup)
• 2n messages (synchronous primary/backup)
• 4n messages (2-phase commit, Multi-Paxos)
• 6n messages (3-phase commit, Paxos with repeated leader election)

這些算法的容錯性不同，根據執行期間消息交換數來進行分類。都保證了單拷貝一緻性。

Primary/backup Replication

最常用的複制算法，也最基本的複制算法。也稱“主/從複制”、“日志傳送複制”。

所有更新操作都在主節點上進行，記錄檔log通過網絡傳送到其他節點副本中。分為同步和異步兩種類型，同步則需要兩條消息（“更新”+“确認”），而異步隻需要運作一條消息（“更新”）。

例子：MySQL（異步）、MongoDB（帶有故障轉移）

不足：隻提供盡力而為的保證。在各個過程中存在各種發生故障的可能

Two phase commit (2PC)

防止上述P/B複制算法的不足，需要增加一此消息傳遞，是以需要兩次。兩個階段：

• Voting投票：coordinator給所有participants發送請求，participants若同意則先臨時更新，并傳回給coordinator确認資訊。
• Decision決定：coordinator決定是否真的commit，并且通知所有participants，participants永久更新。

第二個階段允許系統在節點失敗時復原更新，保證了副本的收斂性。

2PC在性能和容錯之間取得了不錯的平衡。

不足：保證了CA ，但它不是分區容忍的。

Partition tolerant consensus algorithms

單拷貝一緻性算法中，分區容錯是我們希望做到的，而上述的算法都沒有做到。

分區容忍一緻性算法有：

• Paxos：在編寫強一緻的分區容錯複制系統時，Paxos是最重要的算法之一。它在Google的許多系統中使用，包括BigTable / Megastore使用的Chubby鎖管理器，Google檔案系統以及Spanner。整個過程可以總結為：

  Majority vote;

  Dynamic master;

  Robust to n/2-1 simultaneous failures as part of protocol;

  Less sensitive to tail latency.

• Raft：它的設計比Paxos更容易教學，同時提供相同的保證。
• ZAB：Zookeeper atomic broadcast，Zookeeper是一個為分布式系統提供協調原語的系統，并被許多以Hadoop為中心的分布式系統用于協調（例如HBase，Storm，Kafka）。

Chapter 5: Replication: accepting divergence

第四章描述的是強制執行單拷貝一緻性的協定，即強一緻性協定。

第五章我們允許出現多個不同的副本，但是我們需要保證它們最終趨向一緻——最終一緻性模型。包括

• Eventual consistency with probabilistic guarantees.機率保證的最終一緻性(Dynamo)
• Eventual consistency with strong guarantees.強保證的最終一緻性

Amazon Dynamo的系統設計：

• Consistent Hashing一緻的散列來确定資料的關鍵位置
• NWR Model讀寫仲裁模型
• Vector Clock矢量時鐘的沖突檢測和讀取修複
• Gossip複制算法用于保證（新）節點的複制同步

Chapter 6: Further reading and appendix

感謝了一些大神；推薦了一些分布式系統經典的書籍、論文還有系統。略。