ZooKeeper: 為什么讀到舊數據也不會錯誤地拿到鎖？

問題背景 ：我們知道 ZooKeeper 的讀操作在某些情況下可能會返回“陳舊”的數據。在使用 ZooKeeper 實現分布式鎖時，客戶端 C2 會調用 getChildren() 來檢查自己創建的節點是不是序號最小的那個。那么，有沒有可能因為 getChildren() 讀到了舊數據，沒看到當前鎖持有者 C1 的節點，從而錯誤地以為自己獲得了鎖呢？答案是：不可能。為什么？

解讀

這個問題的關鍵在于 ZooKeeper 提供的一個重要保證，叫做 客戶端順序保證 (client order guarantee) 。

雖然一個客戶端的讀操作，可能讀到比系統中最新狀態要舊的數據，但 ZooKeeper 承諾，對于 同一個客戶端 的會話，它的操作是按順序執行的。也就是說，如果你先執行了一個寫操作，那么你后續的讀操作，一定能看到這個寫操作（或更晚的寫操作）之后的狀態。

我們來分析一下獲取鎖的流程：

1. 客戶端 C2 想要獲取鎖，它首先會執行一個 create() 操作，在鎖目錄下創建一個代表自己的、帶序列號的臨時節點，比如 /lock/node-002。
2. 然后，C2 在同一個會話中，執行 getChildren() 操作，獲取鎖目錄下的所有節點列表。
3. 根據“客戶端順序保證”，C2 的這次 getChildren() 操作，看到的數據狀態 至少 和它自己剛剛 create() 操作成功后的狀態一樣新。
4. 而當前的鎖持有者 C1，它創建自己的鎖節點 /lock/node-001 的時間點，必然比 C2 創建 /lock/node-002 更早。
5. 因此，C2 的 getChildren() 看到的視圖，既然新到足以包含自己剛剛創建的 /lock/node-002，那么它也 必然 會包含更早之前就已存在的 /lock/node-001 。

所以，C2 絕不會“看不見” C1 的節點，也就不會錯誤地認為自己是序號最小的那個。

CRAQ: 為什么不能直接返回“臟”數據？

問題背景 ：CRAQ (Chain Replication with Apportioned Queries) 是一個鏈式復制系統。當一個寫請求到達鏈頭，數據在被最終提交（即到達鏈尾）之前，在鏈頭和中間節點上處于“臟” (dirty) 狀態。CRAQ 的論文規定，如果一個節點收到了對臟數據的讀請求，它應該去問鏈尾，獲取最新的已提交版本號。如果我們修改這個規則，允許節點直接返回它本地最新的、即便是“臟”的版本，會如何破壞系統的 強一致性 (strong consistency)？

解讀

直接返回臟數據會破壞系統的 線性一致性 (linearizability) ，這是強一致性的一種具體體現。線性一致性要求，所有操作看起來都像是在某個單一的時間點上以原子的方式瞬間完成的。一個重要的推論是：如果操作 A 在操作 B 開始前就已經完成，那么 B 必須能看到 A 操作的結果。

我們來看一個具體的失敗場景：

1. 假設鏈上有三個服務器 S1 (鏈頭) -> S2 -> S3 (鏈尾)。變量 X 的初始值為 1。
2. 客戶端 C1 發起一個寫操作，要將 X 設置為 2。這個寫請求到達了鏈頭 S1?，F在，S1 上 X 的值是 2（臟數據），而 S2 和 S3 上 X 的值仍然是 1（已提交的舊數據）。
3. 客戶端 C2 向 S1 發起讀請求。按照我們修改后的錯誤邏輯，S1 直接返回了臟數據 2 。
4. C2 收到了 2 這個值，這個讀操作完成了。 緊接著 ，C2 又向鏈尾 S3 發起了對 X 的讀請求。
5. S3 上只有已提交的數據，所以它返回了 1 。
6. 現在，從 C2 的視角來看，它先讀到了 X=2，后讀到了 X=1。它觀察到系統的狀態從 2 變回了 1，仿佛時間倒流了。這顯然無法用任何一個統一的、串行的操作歷史來解釋，因此線性一致性被打破。

Frangipani: 如何保證緩存一致性？

問題背景 ：Frangipani 是一個分布式文件系統。同事 Aviva 和 Chetty 都在用它。Chetty 讀取了一個文件，文件內容被緩存在她的本地工作站。然后 Aviva 修改了同一個文件，并朝 Chetty 喊了一聲“我改完啦！”。當 Chetty 再次讀取文件時，Frangipani 如何保證她能看到 Aviva 的最新修改，而不是讀到自己緩存里的舊數據？

解讀

這背后是一套由 分布式鎖服務 驅動的、優雅的緩存一致性協議。

整個過程像一場精心編排的舞蹈：

1. Aviva 請求寫入 ：當 Aviva 的工作站 (我們稱之為 WA) 想要修改文件時，它不能直接動手。它必須先向中央鎖服務請求獲得該文件的 獨占寫鎖 (exclusive write lock)。
2. 鎖服務協調 ：鎖服務發現 Chetty 的工作站 (WC) 正持有該文件的共享讀鎖。為了把獨占鎖授予 WA，鎖服務會向 WC 發送一個 鎖吊銷 (lock revocation) 請求。
3. Chetty 清理緩存 (關鍵步驟!) ：WC 收到鎖吊銷請求后，在它真正釋放讀鎖之前，它被協議 強制要求 必須清理掉自己本地緩存里所有受該鎖保護的數據。因此，Chetty 緩存的舊文件內容就在這一刻被刪除了。
4. Aviva 完成修改 ：WC 釋放鎖后，WA 成功獲得了獨占寫鎖，現在它可以安全地修改文件了。修改完成后，當 WA 釋放鎖時，會將更新的內容寫入后端的共享存儲系統 Petal 。
5. Chetty 再次讀取 ：當 Chetty 在 Aviva 喊完后再次讀取文件時，它的工作站 WC 會發現本地緩存是空的（因為之前被清掉了）。WC 就會像第一次讀一樣，先去獲取一個讀鎖，然后從共享存儲 Petal 中讀取文件內容。此時，它讀到的自然就是 Aviva 寫入的最新版本了。

MIT 6.824 2020 年期末考試解析

FaRM (1): 兩個相同事務同時執行會怎樣？

問題背景 ：在 FaRM 系統上，兩個客戶端在兩臺不同的機器上，同時發起一個完全相同的事務。初始時 x=0, y=0 。

begin()
if x > y:
  y = y + 1
else:
  x = x + 1
end()

最終結果會是什么？FaRM 的提交協議是如何導致這個結果的？

解讀

最終結果是： 一個事務提交，另一個事務中止 。數據庫的最終狀態將是 x=1, y=0 。

這是由 FaRM 的樂觀并發控制協議決定的：

1. 讀取階段 ：兩個事務（我們叫 T_A 和 T_B）同時開始。它們都讀取到 x=0 和 y=0 。
2. 邏輯判斷 ：因為 x > y (0 > 0) 為假，所以兩個事務都進入了 else 分支，都打算將 x 的值加 1 。
3. 鎖定階段 (LOCK) ：事務準備提交時，它們都需要為自己將要寫入的對象請求鎖。在這里，T_A 和 T_B 都會向負責對象 x 的服務器發送 LOCK 請求。
4. 鎖競爭 ：管理 x 的服務器幾乎同時收到了兩個 LOCK 請求。它會以一個確定的順序來處理它們（比如按網絡包到達的先后順序）。假設它先處理了 T_A 的請求。
5. 一成一敗 ：T_A 成功獲得了 x 的鎖。接著，當服務器處理 T_B 的請求時，它發現 x 已經被鎖定了，于是它會拒絕 T_B 的請求，并返回一個失敗消息。
6. 最終結局 ：T_A 順利完成提交，將 x 的值更新為 1。而 T_B 因為鎖請求失敗，整個事務被中止。所以最后的結果是 x=1, y=0。

FaRM (2): 把 VALIDATE 和 LOCK 順序顛倒會怎樣？

問題背景 ：Ben 同學覺得如果把 FaRM 提交協議中的 VALIDATE 階段放到 LOCK 階段之前，也許能讓事務跑得更快。事實證明，這會破壞可串行化。請給出一個反例。

解讀

這個改動會引入一種叫做 寫偏斜 (write skew) 的異常。VALIDATE 的作用是檢查你讀取的數據在你執行事務期間是否被別人修改了。把它提前，你就無法發現那些在你驗證之后、加鎖之前發生的并發修改。

來看這個經典的轉賬/約束檢查反例：

// 初始狀態: x = 0, y = 0
T1:              T2:
if x == 0:       if y == 0:
  y = 1            x = 1

我們來模擬一下 Ben 修改后的錯誤流程：

1. 讀取 ：T1 和 T2 同時開始。T1 讀取 x=0，T2 讀取 y=0。
2. VALIDATE 階段 (新) ：T1 和 T2 同時發起驗證。T1 驗證 x 的版本號沒變（仍然是 0），成功！T2 驗證 y 的版本號沒變（仍然是 0），也成功！
3. LOCK 階段 (新) ：現在兩個事務都認為自己可以安全提交了。T1 請求 y 的鎖，T2 請求 x 的鎖。因為它們鎖定的是不同的對象，所以兩個請求都成功了！
4. 提交 ：兩個事務都提交了。T1 將 y 寫入 1，T2 將 x 寫入 1。最終數據庫狀態變為 x=1, y=1 。

為什么這是錯的？ 我們來看一下正確的串行執行結果：

• T1 -> T2 : T1 執行，x==0 成立，y 變為 1。然后 T2 執行，y==0 不成立，什么也不做。最終結果：x=0, y=1。
• T2 -> T1 : T2 執行，y==0 成立，x 變為 1。然后 T1 執行，x==0 不成立，什么也不做。最終結果：x=1, y=0。

可見，x=1, y=1 這個結果在任何串行順序下都是不可能出現的。因此，Ben 的改動破壞了可串行化。

Spark: 為什么在循環里 persist() RDD 沒用？

問題背景 ：在 Spark PageRank 的迭代代碼中，ranks RDD 在循環中被反復使用。Ben 認為在每次給 ranks 賦值后都調用 ranks.persist() 來緩存它，可以加速計算。但他發現，加了之后運行時間沒變化。為什么？

解讀

原因是 RDD 的不可變性 (immutability) 。

在 Spark 的 for 循環里，每一次迭代都會根據前一次迭代的 ranks RDD，通過一系列轉換 (join, map 等)，生成一個 全新的ranks RDD。

讓我們把循環展開看：

• 迭代 i：ranks_i = ranks_{i-1}.join(...).map(...)
• 迭代 i+1：ranks_{i+1} = ranks_i.join(...).map(...)

當 Ben 在第 i 次迭代的末尾調用 ranks_i.persist() 時，他確實把 ranks_i 這個 RDD 標記為需要緩存。然而，這個 ranks_i RDD 的生命周期里，它只被 使用了一次 ——就是在第 i+1 次迭代中，作為計算 ranks_{i+1} 的輸入。

緩存一個只用一次的東西是毫無意義的。這就好比你為了明天早上喝一杯牛奶，今天就把牛奶倒在杯子里放進冰箱，這沒有任何加速作用。persist() 的真正威力在于，當你需要對 同一個 RDD 執行 多個action 操作時，緩存它才能避免重復計算。

Memcache: 為什么簡單的“寫數據庫再寫緩存”會出錯？

問題背景 ：Ben 設計了一個簡單的緩存系統：寫操作總是先更新 MySQL 數據庫，再更新 Memcached 緩存。他認為，這樣只有在寫數據庫和寫緩存之間的那個短暫瞬間，數據會不一致。為什么他錯了？

解讀

Ben 的錯誤在于，他忽略了 并發 和 網絡延遲 這兩個分布式系統中的“幽靈”。他想當然地認為，操作的順序會和他代碼里寫的順序一樣，但這在分布式環境中完全不是一回事。

問題出在 競態條件 (race condition) 上。我們想象一個場景：

1. 兩個客戶端 C1 和 C2，幾乎在同一時間，都要對同一個鍵 K 進行寫入。C1 想寫 val1，C2 想寫 val2。
2. 在數據庫端 ：由于網絡路徑和服務器處理時間的細微差別，C1 的更新請求先到達數據庫，然后是 C2 的。數據庫先將 K 更新為 val1，再更新為 val2。最終，數據庫里存的是 val2 。這是正確的。
3. 在 Memcached 端 ：同樣由于網絡延遲的隨機性，這次 C2 的更新請求先到達了 Memcached，K 的值被設為 val2。緊接著，C1 的請求到達了，又將 K 的值覆蓋為了 val1 。

災難性的后果 ：現在，數據庫里 K 的值是 val2，而緩存里 K 的值是 val1。兩者出現了永久性的不一致！這種不一致會一直持續下去，直到下一次對 K 的寫入發生，這期間所有讀緩存的請求都會得到錯誤的數據。

COPS: 因果一致性下的讀操作

問題背景 ：在 COPS 系統（非事務性的 COPS-GT）中，有四個客戶端在不同數據中心并發執行操作，初始值 x,y,z 均為 0 。

C1: put(x, 1); put(y, 2)
C2: tmp_y = get(y); put(z, 100 + tmp_y)
C3: get(x); get(y); get(z); print ...  // 讀序 x, y, z
C4: get(z); get(y); get(x); print ...  // 讀序 z, y, x

C3 可能的輸出是什么？

解讀

[ ] x=1 y=2 z=102
[ ] x=1 y=0 z=102
[ ] x=0 y=2 z=102
[ ] x=1 y=2 z=0
[ ] x=1 y=0 z=0
[ ] x=0 y=2 z=0

答案是所有六個選項都有可能。

這說明，在非事務性的 COPS 中，單個的 get 操作之間沒有同步。C3 連續執行三個 get，但每一個 get 都可能從本地數據中心的存儲中讀到不同“時間點”的數據。由于網絡復制的延遲，C3 的本地數據中心可能只看到了 C1 的部分寫入，或者看到了 C2 的寫入但 C1 的寫入還沒到。因此，各種看似奇怪的組合都可能出現。

C4 可能的輸出是什么？

解讀

答案是只有 x=1 y=2 z=102, x=1 y=2 z=0, x=1 y=0 z=0 這三個。

為什么 C4 的可能性就變少了？關鍵在于 讀的順序 和 COPS 的 因果一致性 (causal consistency) 保證。

我們先梳理一下因果鏈：

• C1 的 put(x,1)因果上先于put(y,2)。
• 如果 C2 讀到了 y=2，那么 C2 的 put(z,102) 就 因果上依賴于C1 的 put(y,2)。
• 所以，我們有一個潛在的因果長鏈：put(x,1) -> put(y,2) -> put(z,102)。

COPS 的核心保證是：如果你看到了一個結果，你必須能看到導致這個結果的所有原因。

現在來看 C4 的 get(z); get(y); get(x); 流程：

情況一：get(z) 返回 102

C4 看到了 z=102 這個結果。根據 COPS 的保證，它所在的本地數據中心必須也已經穩定地接收到了導致 z=102 的所有原因，也就是 put(y,2) 和 put(x,1)。因此，C4 接下來執行 get(y) 和 get(x) 時， 必然 會讀到 2 和 1。所以 x=1, y=2, z=102 是可能的。

情況二：get(z) 返回 0

C4 沒有看到 C2 寫入的結果。因此，z 沒有提供任何因果信息。C4 接下來讀 y 和 x，會看到什么取決于 C1 的寫入傳播了多少。但 C1 內部的因果關系 (put(x,1) -> put(y,2)) 依然要被遵守。

• 可能 C1 的兩個寫都到了：看到 y=2, x=1。組合成 x=1, y=2, z=0。
• 可能只有 C1 的第一個寫到了：看到 y=0, x=1。組合成 x=1, y=0, z=0。
• 不可能只看到 C1 的第二個寫（y=2）而沒看到第一個（x=0），因為這違反了 C1 內部的因果性。

這就是 C4 結果受限的原因，它的第一個 get(z) 操作“錨定”了一個因果歷史。

Lab 3 Raft (1): 為什么 Follower 不能直接響應 Get 請求？

解讀

很簡單，因為會導致 陳舊讀 (stale reads) 。

Raft 的核心是通過 leader 將所有寫操作記錄在日志里，并復制給 follower。但這個復制過程不是瞬時的，follower 的狀態很可能落后于 leader。

如果一個客戶端剛通過 leader 執行了一個 Put("k", "v2")，成功地把值從 v1 改成了 v2。然后它馬上發起一個 Get("k") 請求，但不巧這個請求被發給了一個還沒收到最新日志的 follower。這個 follower 就會從自己的（過時的）狀態機里讀出 v1 并返回給客戶端?？蛻舳司蜁吹揭粋€剛剛被自己修改過的值又變了回去，這破壞了線性一致性。

Lab 3 Raft (2): 如何用 TrueTime 讓 Follower 安全地響應 Get ？

解讀

這個設計巧妙地把 Spanner 的核心思想嫁接到了 Raft 上，目標是在 follower 上實現線性一致性的讀。

核心思路是： 確保 follower 的狀態足夠新，能夠滿足讀請求發起時刻的一致性要求。

1. 客戶端標記請求 ：客戶端在發起 Get 請求前，先用 req_ts = TT.now() 獲取一個 請求時間戳 。這個時間戳是一個 [earliest, latest] 的區間，代表了請求發起的真實時間。客戶端將 req_ts 連同請求一起發送。
2. Leader 標記寫入 ：leader 在處理 Put/Append 等寫操作時，也會在將命令寫入 Raft 日志前，用 op_ts = TT.now() 給這條日志條目打上一個 操作時間戳 。這個時間戳會隨著日志一起被復制給所有 follower。
3. Follower 等待并響應 ：當一個 follower 收到一個帶有 req_ts 的 Get 請求時，它不能立即響應。它必須等待，直到它本地的狀態機已經應用了某條日志，而這條日志的操作時間戳 op_ts明確晚于 讀請求的時間戳。
4. 這個判斷的精確條件是 op_ts.earliest > req_ts.latest 。這個不等式一旦成立，就意味著 follower 知道，它當前的狀態所反映的真實時間點，一定是在客戶端發起讀請求之后。
5. 一旦條件滿足，follower 就可以安全地從自己的本地狀態機里讀取數據并返回給客戶端了，因為它知道自己的數據“足夠新”，足以保證這次讀的線性一致性。