Citus 總結：分佈式事務及死鎖檢測

  1. 基礎理論

1.1 ACID 原則

1.2 CAP 理論

在分佈式數據庫場景下，還要結合分佈式系統的 CAP 理論，定義如下：

CAP 理論表明，在存在網絡分區的情況下，一致性和可用性必須二選一。而在沒有發生網絡故障時，即分佈式系統正常運行時，一致性和可用性是可以同時被滿足的。但是，對於分佈式數據庫來說，網絡故障是不可避免的，可用性是必須要保證的，所以只有捨棄一致性來保證服務的 AP。但是對於一些金融相關行業，它有很多場景需要確保一致性，這種情況通常會權衡 CA 和 CP 模型，CA 模型網絡故障時完全不可用，CP 模型具備部分可用性。

1.3 BASE 理論

分佈式數據庫一般採用 2PC（兩階段提交）來提供跨越多個數據庫分片的 ACID 保證。但是引入 2PC 的直接影響就是可用性下降。假設數據分佈在兩個數據庫實例上，每個數據庫實例的可用性是 99.9%，那麼數據庫分片後可用性爲 99.8%。作爲商用軟件，可用性下降是不可容忍的。

BASE 理論就是對 CAP 理論中的一致性和可用性權衡的結果，核心思想是即使無法做到強一致性（Strong consistency），但每個應用都可以根據自身的業務特點，採用適當的方式來使系統達到最終一致性（Eventual consistency）。

BASE 理論定義如下：

  1. Citus 的分佈式事務方案

2.1 執行步驟

如上圖所示，由 Coordinator 節點負責協調分佈式事務的執行，各 Worker 節點作爲參與者參與分佈式事務的執行：

2.2 故障處理

分佈式事務執行過程中，可能會碰到節點或網絡異常，2PC 協議爲了保證數據的強一致，實際上選擇的是 CAP 理論中的 CA 部分，不能容忍網絡分區異常，實際上降低了分佈式系統的可用性。爲了解決這個問題，Citus 建議針對 Coordinator 和 Worker 節點，都採用 Streaming Replication 的方式保證節點的高可用，當一個節點故障時，可以快速由另外一個 Standby 節點接管並繼續推進事務的執行。

還有一種故障場景，2PC 不能很好的解決，就是當所有 Worker 節點都做出反饋後（可以是提交或回滾），Coordinator 節點故障，此時接管的 Coordinator 節點不知道該如何進一步推進事務（不知道之前的投票結果）。爲了解決這個問題，Citus 使用了類似 3PC 的解決思路，當 Coordinator 節點收到所有 Worker 節點都投票可以提交時，在本地pg_dist_xact表中記錄該全局事務可以提交，同時還增加定時檢測機制，將可以提交但尚未成功提交的事務繼續推進執行，直到成功提交後，刪除pg_dist_xact表中對應記錄。

2.3 數據一致性

雖然 Citus 採用 2PC 協議，保證了在同一個分佈式事務中操作的多條記錄的原子性更新。但從客戶端讀取的視角來看，可能會讀到中間態的數據（Base 中的軟狀態），是最終一致性的模型。

原因在於 Citus 並沒有引入集羣級的全局授時機制，對於只讀事務，無法獲取集羣級的全局一致性快照，而是由各 Worker 節點自己進行可見性判斷，當一個分佈式事務正在提交時，在不同的 Worker 節點提交存在時間差，在這個時間間隙內發起的查詢事務，就會在已經提交的 Worker 節點看到已提交數據，在尚未完成提交的 Worker 節點看不到同一個事務寫入的數據，等所有 Worker 節點都完成提交後，再次查詢又能看到最新一致的數據，因此嚴格說 Citus 提供的是最終一致性模型。

2.4 隔離級別

因爲沒有集羣級全局一致性快照的原因，Citus 提供的隔離級別只有 Read Commited，不管客戶端是如何設置的。

  1. 死鎖檢測

3.1 發生死鎖的場景

在 PostgreSQL 中，當事務更新一行時，需要獲取該行的鎖並一直持有到事務提交爲止，如果有需要獲取相同鎖集的併發事務，但獲取鎖的順序不同，那麼就會出現死鎖。

下面是一個發生死鎖的例子：

S1:  UPDATE table SET value = 1 WHERE key = 'hello'; A takes 'hello’ lockS2:  UPDATE table SET value = 2 WHERE key = 'world'; B takes 'world’ lockS1:  UPDATE table SET value = 1 WHERE key = 'world'; wait for 'hello’ lock held by 2S2:  UPDATE table SET value = 2 WHERE key = 'hello'; wait for 'world’ lock held by 1

爲了檢測並解決死鎖的問題，數據庫都會提供定期死鎖檢測機制，如果會話等待鎖持續一段時間，PostgreSQL 依賴 Depedency Graph 技術檢查進程間是否在鎖上形成循環依賴。如果是這種情況，將強制終止其中部分事務，直到死鎖問題解除。

3.2 分佈式死鎖檢測

上面的例子，如果發生在 Citus 分佈式數據庫場景下，則會變成這樣：

-- 在Worker A節點執行：
S1:  UPDATE table_123 SET value = 5 WHERE key = 'hello';
S2:  UPDATE table_123 SET value = 6 WHERE key = 'hello'; waits for 'hello’ lock held by 1
-- 在Worker B節點執行：
S1:  UPDATE table_234 SET value = 6 WHERE key = 'world';
S2:  UPDATE table_234 SET value = 5 WHERE key = 'world'; waits for 'world’ lock held by 2

如上圖所示，從每個 Worker 節點來看，都不知道已經發生死鎖情況，但在集羣層面，Session1 和 Session2 處於相互阻塞等待狀態，且不能自行解除，已經發生分佈式死鎖現象。

爲了解決分佈式死鎖問題，Citus 在 Coordiantor 節點運行分佈式死鎖檢測後臺任務來負責分佈式死鎖檢測：Coordinator 定期檢測各個 Worker 節點是否存在長時間（1s）等鎖的現象，如果存在，則從所有 Worker 節點蒐集鎖表信息，並在 Coordinator 節點構建事務間的 Dependency Graph，檢測是否存在相互依賴並形成死鎖，如果存在，則按照策略取消部分事務來解鎖。

3.3 如何避免死鎖發生

一旦死鎖現象發生，不只是相應的事務無法推進執行，還會因爲持有鎖進一步阻塞更多的事務執行，進而產生類似交通擁塞的現象，嚴重影響數據庫的性能。因此，除了死鎖檢測技術外，還會結合降低死鎖概率甚至避免死鎖的技術，以獲得更好的性能。

3.3.1 Predicate Locks 謂詞鎖

針對 Update 語句的謂詞進行加鎖，這樣可以避免可能會產生死鎖的事務並行執行，例如：

UPDATE ... WHERE key = `hello`

針對key='hello'加謂詞鎖，可以避免其他按照同樣謂詞條件（key='hello'）的 UPDATE 事務並行執行，也就避免了可能產生的死鎖現象。

在 Coordinator 節點加謂詞鎖，同樣還可以起到死鎖檢測的效果，在多個 Worker 節點形成分佈式死鎖現象前，Coordiantor 節點會先在謂詞鎖上形成死鎖並被提前檢測出來。

Spanner/F1 系統就採用了謂詞鎖技術來降低死鎖現象的發生。

3.3.2 Wait-Die or Wound-Wait

給事務定義優先級的思路，可以認爲先發起的事務（較小的事務 ID）擁有較高的優先級，後發起的事務（較大的事務 ID）擁有較低的優先級。當事務執行過程中，發生了先發起的事務被後發起的事務阻塞現象稱爲優先級反轉，可以採用兩種策略中的一種主動解鎖：

一般來說，先發起的事務會更早的獲取鎖，因此發生優先級反轉的概率不高，Wound-Wait 策略的效率會更好些。

Spanner/F1 系統採用的是 Wound-Wait 策略。

參考

https://dzone.com/articles/how-citus-executes-distributed-transactions-on-pos

https://www.citusdata.com/blog/2017/08/31/databases-and-distributed-deadlocks-a-faq/

https://zhuanlan.zhihu.com/p/143504602

http://matt33.com/2018/07/08/distribute-system-consistency-protocol/

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

猜你喜歡