分佈式系統設計模式

1、布隆過濾器

Bloom 過濾器是一種節省空間的概率數據結構，用於測試元素是否爲某集合的成員。它用於我們只需要檢查元素是否屬於對象的場景。

在 BigTable（和 Cassandra）中，任何讀取操作都必須從組成 Tablet 的 SSTable 中讀取。如果這些 SSTable 不在內存中，則讀取操作可能最終會執行許多磁盤訪問以便讀取所需的 SSTable。爲了減少磁盤訪問次數，BigTable 使用 Bloom 過濾器。

2、一致性哈希

一致的哈希允許您輕鬆擴展，從而允許以有效的方式複製數據，從而實現更好的可用性和容錯能力。

通過對數據項的鍵進行哈希處理以產生其在環上的位置，然後順時針遍歷環以查找位置大於該項位置的第一個節點，將每個由鍵標識的數據項分配給節點。與節點關聯的節點是數據項的位置。

一致散列的主要優點是增量穩定性；節點離開或到達集羣僅影響其直接鄰居，其他節點不受影響。

3、Quorum

在分佈式環境中，quorum 是在確認操作成功之前需要成功執行此分佈式操作的最小服務器數。

Cassandra，爲了確保數據一致性，每個寫入請求都可以配置爲僅當數據已寫入至少一個 quorum（或大多數）副本節點時才成功。

對於領導者選舉，Chubby 使用 Paxos，它使用 quorum 來確保強大的一致性。

Dynamo 將寫入複製到系統中其他節點的草率 quorum，而不是像 Paxos 那樣的嚴格多數 quorum。所有讀 / 寫操作都在首選項列表中的第一個 NN 正常節點上執行，該節點可能並不總是在遍歷一致哈希環時遇到的第一個 NN 節點。

4、領導者（Leader）和追隨者（Follower）

爲了在管理數據的系統中實現容錯，需要在多個服務器上覆制數據。

在集羣中選擇一個服務器作爲領導者。領導者負責代表整個集羣做出決策，並將決策傳播到所有其他服務器。

三到五個節點的集羣，就像在實現共識的系統中一樣，領導者選舉可以在數據集羣本身內實施，而不依賴於任何外部系統。領導者選舉在服務器啓動時進行。每個服務器在啓動時都會啓動領導者選舉，並嘗試選舉領導者。除非選出領導者，否則系統不接受任何客戶端請求。

5、心跳

心跳機制用於檢測現有領導者是否失敗，以便可以啓動新的領導者選舉。

6、Fencing

在領導者 - 追隨者模式中，當領導者失敗時，不可能確定領導者已停止工作。例如，慢速網絡或網絡分區可能會觸發新的領導者選舉，即使前一個領導者仍在運行並認爲它仍然是活動的領導者。

屏蔽是指在以前處於活動狀態的領導者周圍設置圍欄，使其無法訪問集羣資源，從而停止爲任何讀 / 寫請求提供服務。

使用以下兩種技術：

7、WAL（預寫日誌 Write-ahead Log）

預寫日誌記錄是解決操作系統中文件系統不一致的問題的高級解決方案。受數據庫管理系統的啓發，此方法首先將要執行的操作的摘要記入 “日誌” 中，然後再將其實際寫入磁盤。在發生崩潰的情況下，操作系統只需檢查此日誌並從中斷的位置繼續。

8、分段日誌

將日誌拆分爲多個較小的文件，而不是單個大文件，以便於操作。

單個日誌文件在啓動時讀取時可能會增長併成爲性能瓶頸。較舊的日誌會定期清理，並且很難對單個大文件執行清理操作。

單個日誌拆分爲多個段。日誌文件在指定的大小限制後滾動。使用日誌分段，需要有一種將邏輯日誌偏移量（或日誌序列號）映射到日誌段文件的簡單方法。

9、高水位線（High-Water mark）

跟蹤領導者上的最後一個日誌條目，該條目已成功複製到追隨者的 quorum。日誌中此條目的索引稱爲高水位線索引。領導者僅公開到高水位線索引的數據。

Kafka：爲了處理非可重複讀取並確保數據一致性，Kafka broker 會跟蹤高水位線，這是特定分區的最大偏移量。使用者只能看到高水位線之前的消息。

10、租約（Lease）

租約就像一個鎖，但即使客戶端離開，它也能工作。客戶端請求有限期限的租約，之後租約到期。如果客戶端想要延長租約，它可以在租約到期之前續訂租約。

Chubby 客戶端與領導者保持有時限的會話租約。在此時間間隔內，領導者保證不會單方面終止會話。

11、Gossip 協議

Gossip 協議是點對點通信機制，其中節點定期交換有關自己和他們所知道的其他節點的狀態信息。

每個節點每秒啓動一輪 Gossip 回合，以與另一個隨機節點交換有關自己和其他節點的狀態信息。

12、Phi 累計故障檢測（Phi Accrual Failure Detection）

此算法使用歷史檢測信號信息使閾值自適應。通用的應計故障檢測器不會判斷服務器是否處於活動狀態，而是輸出有關服務器的可疑級別。

Cassandra 使用 Phi 應計故障檢測器算法來確定羣集中節點的狀態。

13、腦裂

分佈式系統具有兩個或多個活動領導者的場景稱爲腦裂。

通過使用生成時鐘（Generation Clock）可以解決腦裂問題，生成時鐘只是一個單調遞增的數字，用於指示服務器的生成。

每次選出新領導者時，時鐘數字（generation number）都會增加。這意味着，如果舊領導者的時鐘數爲 “1”，則新領導人的時鐘數將爲 “2”。此時鐘號包含在從領導發送到其他節點的每個請求中。通過這種方式，節點現在可以通過簡單地信任具有最高數字的領導者來輕鬆區分真正的領導者。

Kafka：爲了處理腦裂（我們可以有多個 active controller broker），Kafka 使用 “紀元數”（Epoch number），這只是一個單調增加的數字來表示服務器的代次（generation）。

HDFS：ZooKeeper 用於確保任何時候只有一個 NameNode 處於活動狀態。epoch 編號作爲每個事務 ID 的一部分進行維護，以反映 NameNode 的代次。

14、校驗和（checksum）

在分佈式系統中，在組件之間移動數據時，從節點獲取的數據可能會損壞。

計算校驗和並將其與數據一起存儲。

要計算校驗和，請使用 MD5、SHA-1、SHA-256 或 SHA-512 等加密哈希函數。哈希函數獲取輸入數據並生成固定長度的字符串（包含字母和數字）；此字符串稱爲校驗和。

當系統存儲某些數據時，它會計算數據的校驗和，並將校驗和與數據一起存儲。當客戶端檢索數據時，它會驗證從服務器接收的數據是否與存儲的校驗和匹配。如果沒有，則客戶端可以選擇從另一個副本檢索該數據。

HDFS 和 Chubby 將每個文件的校驗和與數據一起存儲。

15、CAP 定理

CAP 定理指出，分佈式系統不可能同時提供以下所有三個理想屬性：

一致性（C）、可用性（A）和分區容差（P）。

根據 CAP 定理，任何分佈式系統都需要從三個屬性中選擇兩個。這三個選項是 CA、CP 和 AP。

Dynamo：在 CAP 定理術語中，Dynamo 屬於 AP 系統的類別，旨在犧牲強一致性爲代價實現高可用性。

BigTable：就 CAP 定理而言，BigTable 是一個 CP 系統，即它具有嚴格一致的讀取和寫入。

16、PACELEC 定理

PACELC 定理指出，在複製數據的系統中：

定理（PAC）的第一部分與 CAP 定理相同，ELC 是擴展。整個論點假設我們通過複製來保持高可用性。因此，當失敗時，CAP 定理佔上風。但如果沒有，我們仍然必須考慮複製系統的一致性和延遲之間的權衡。

17、提示交接（Hinted Handoff）

如果節點關閉，系統會保留它們錯過的所有請求的提示（或註釋）。故障節點恢復後，將根據存儲的提示將請求轉發給它們。

當節點關閉時，領導者會在本地磁盤上的文本文件中寫入提示。此提示包含數據及其所屬的節點信息。當領導者意識到它爲其保留提示的節點已恢復時，它會將每個提示的寫入請求轉發到該節點。

18、讀取時修復

在分佈式系統中，數據跨多個節點複製，某些節點最終可能會擁有過時的數據。

在讀取操作期間修復過時的數據，因爲此時，我們可以從多個節點讀取數據以進行比較並找到具有過時數據的節點。此機制稱爲讀取修復。一旦已知具有舊數據的節點，讀取修復操作就會將較新版本的數據推送到具有較舊版本的節點。

Cassandra 和 Dynamo 使用 “讀取修復” 將最新版本的數據推送到具有舊版本的節點。

19、默克爾樹（Merkle Trees）

“讀取修復” 可在處理讀取請求時消除衝突。但是，如果某個副本明顯落後於其他副本，則可能需要很長時間才能解決衝突。

副本可以包含大量數據。單純地拆分整個範圍來計算校驗和進行比較並不是很可行；有太多的數據需要傳輸。相反，我們可以使用 Merkle 樹來比較一個範圍的副本。

Merkle 樹是哈希的二叉樹，其中每個內部節點是其兩個子節點的哈希，每個葉節點是原始數據一部分的哈希。

比較 Merkle 樹在概念上很簡單：

爲了實現反熵和在後臺解決衝突，Dynamo 使用 Merkle 樹。

分佈式實驗室 關注分佈式相關的開源項目和基礎架構，致力於分析並報道這些新技術是如何以及將會怎樣影響企業的軟件構建方式。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/60OyxNnRswZexH8TyyXO2A

猜你喜歡