MapReduce (1): 如何用 MapReduce 找最大值？

這道題非常經典，是理解 MapReduce 思想的敲門磚。

問題背景 ：想象一下，我們有 100 個文件，每個文件里都寫滿了數字，一行一個。我們的任務是找出這所有數字里的最大值。

解讀

MapReduce 的核心思想是“分而治之”。

1. map 階段 ：map 函數就像是“地方海選賽”。每個 map 任務會分配到一個或多個文件。它的工作很簡單：就在自己負責的這堆數里，找出那個最大的“地方冠軍”。然后，它會輸出一個鍵值對，比如 ( "max", 12345 )，其中 12345 就是它找到的那個局部最大值。這里用一個固定的 key (比如空字符串 "" 或者 "max") 是個小技巧，目的是確保所有這些“地方冠軍”都能被送到同一個 reduce 任務那里去進行“總決賽”。
2. reduce 階段 ：reduce 函數就是“全國總決賽”。因為前面所有的 map 任務都用了同一個 key，所以 MapReduce 框架會把所有 map 的輸出（也就是所有“地方冠軍”的數值）都集合起來，然后交給一個 reduce 任務。這個 reduce 任務的工作就更簡單了：在這些“地方冠軍”里，選出那個唯一的“全國總冠軍”，也就是全局最大值。

reduce 函數會被調用幾次？

只會有 1 次。因為我們巧妙地設計了讓所有 map 的輸出都使用同一個 key，所以這些數據只會被匯集到一個 reduce 任務中處理。

MapReduce (2): 為什么寫入中間文件需要“先寫臨時文件再重命名”？

問題背景 ：有個同學叫 Alyssa，她在實現 MapReduce 的 worker 時偷懶了。她直接用 os.Create() 來創建中間結果文件，而不是遵循“先寫到一個臨時文件，寫完后再用 os.Rename() 重命名”這個最佳實踐。這會出什么問題？

解讀

這個問題觸及了分布式系統中一個非常重要的概念：處理“慢節點”和任務的原子性。

在 MapReduce 中，master 有一個叫做 投機執行 (speculative execution) 的機制。如果它發現某個 map 任務運行得特別慢，它可能會在另一臺機器上重新啟動一個一模一樣的任務，誰先跑完就用誰的結果。

現在，我們來想象一個災難場景：

1. master 派任務 M 給 worker W1。W1 由于網絡、CPU 等原因，運行得非常慢。
2. master 等得不耐煩了，啟動了投機執行，把同樣的任務 M 又派給了 worker W2。W2 身強力壯，很快就完成了計算，并用 os.Create("mr-M-R") 創建并寫好了中間文件。
3. master 收到 W2 的捷報，于是啟動了對應的 reduce 任務，這個 reduce 任務開始讀取 W2 生成的那個 mr-M-R 文件。
4. 就在此時，慢吞吞的 W1 終于也完成了它的計算。它也執行了 os.Create("mr-M-R")。
5. 關鍵點來了：os.Create() 在文件已存在時，會直接清空它！于是，W2 辛辛苦苦生成的、reduce 任務正在讀取的文件，瞬間被 W1 清空了。
6. reduce 任務讀著讀著發現文件變空了，最終得出了錯誤的結果。

正確的做法是什么呢？

原子性的“寫入臨時文件后重命名”。W1 和 W2 都先寫入各自的臨時文件（比如 mr-M-R-temp-W1），寫完后，再用 os.Rename() 這個原子操作去搶占最終的文件名。這樣就能保證，無論誰快誰慢，reduce 任務讀到的文件一定是某個 worker 完整寫入的結果，而不是一個被中途清空的文件。

GFS: 同時讀同一個 GFS 文件，內容一定相同嗎？

問題背景 ：兩個客戶端，在沒有任何寫入操作的情況下，同時從頭到尾讀取 GFS 上的同一個文件。它們讀到的內容保證會一樣嗎？

解讀

不保證。 GFS 在設計上為了性能和可用性，在某些一致性上做了妥協。

問題的根源在于 GFS 的一種特殊寫操作：記錄追加 (record append)。當一個客戶端執行追加操作時，primary 副本會確定一個偏移量，然后通知所有 secondary 副本也寫入。但如果某個 secondary 副本當時正好網絡不通或者掛了，它可能就收不到這個寫入指令。GFS 的 primary 不會死等所有副本都成功，它只會把錯誤報告給客戶端。

這就導致了一個后果：同一個數據塊的不同副本（chunk replica），可能內容不一樣了。一個副本有這次追加的數據，另一個沒有。

所以，當那兩個客戶端來讀取文件時，如果它們不幸地連接到了持有不同數據副本的 chunkserver 上，它們讀到的內容自然也就不一樣了。

Raft (1): currentTerm 必須持久化嗎？

問題背景 ：Ben 同學覺得每次都持久化 currentTerm 太麻煩，他想了個“聰明”的辦法：當一個節點重啟時，不從持久化存儲里讀 currentTerm，而是直接讀取它日志里最后一條記錄的任期號，并把它作為自己的 currentTerm。這會出什么問題？

解讀

Ben 的這個改動會破壞 Raft 協議的根基——投票的正確性，從而可能導致“腦裂”（即同一任期出現兩個 leader）。

currentTerm 和 votedFor 這兩個狀態，是 Raft 節點在選舉中的“記憶”。它們必須被持久化，以確保節點在崩潰重啟后不會“失憶”并做出矛盾的決定。

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

1. 一個集群，節點 P1 的日志里最后一條記錄的任期是 10。所以它當前的 currentTerm 也是 10。
2. 候選人 P2 發起了 term 11 的選舉。P1 收到投票請求，它一看任期比自己的高，于是投票給了 P2。同時，P1 把自己的（內存中的）currentTerm 更新為 11，并持久化 votedFor = P2。
3. 在 P1 還來不及持久化 currentTerm = 11 的時候，它突然崩潰了。
4. P1 重啟。按照 Ben 的邏輯，它會讀取日志，發現最后一條記錄的任期是 10，于是它把自己的 currentTerm 初始化為 10。
5. 這時，另一個候選人 P3 也發起了 term 11 的選舉。P3 的投票請求到達了 P1。P1 檢查后發現，請求的任期 11 比自己的當前任期 10 要高，并且（假設它沒持久化 votedFor 或者 votedFor 邏輯也有問題）它認為自己還沒在 term 11 里投過票。于是，它又投票給了 P3！

災難發生了 ：P1 在同一個任期 11 里，先后為 P2 和 P3 兩個不同的候選人投了票。這嚴重違反了 Raft 的選舉安全規則，完全可能導致 P2 和 P3 都分別獲得足夠選票成為 leader，系統出現“雙主”，狀態機將執行不同的指令，數據一致性被破壞。

Raft (2): AppendEntries 時直接覆蓋日志行不行？

問題背景 ：Bob 同學為了簡化代碼，修改了 AppendEntries RPC 的處理邏輯。他不再檢查日志沖突，而是簡單粗暴地直接用 leader 發來的日志覆蓋本地日志。這為什么是錯的？

解讀

這個改動破壞了 Raft 的日志匹配屬性 (Log Matching Property)，這是確保安全性的核心。直接覆蓋會導致一個已提交的日志條目被錯誤地更改。

看這個例子：

1. 有三個節點 S1, S2, S3。S1 是 term 1 的 leader。
2. S1 在 index 1 追加了日志 A，在 index 2 追加了日志 B。它把 [A, B] 發給了 S2 和 S3。
3. S2 成功收到了 [A, B]。S1 和 S2 構成了多數派，所以 A 和 B 在 S1 上被提交了。S3 可能因為網絡延遲只收到了 A。
4. 現在，一個 之前 從 S1 發出的、但被網絡延遲了的 AppendEntries RPC（這個 RPC 只包含 A）終于到達了 S2。
5. 按照 Bob 的錯誤邏輯，S2 不做沖突檢查，直接用這個 RPC 的內容來更新自己的日志。它會把自己的日志從 [A, B] 截斷回 [A]。
6. S1 掛了。S3 發起 term 2 的選舉。S3 的日志是 [A]，S2 的日志現在也是 [A]，所以 S2 會投票給 S3。
7. S3 成為 term 2 的新 leader。它在 index 2 寫入了一個 不同 的日志 C。
8. S3 把 C 復制給了 S2，并且它們倆構成了多數派，提交了 C。

最終結果 ：在 index 2 這個位置，S1 提交的日志是 B，而 S2 和 S3 提交的卻是 C。不同的節點在同一個日志索引上提交了不同的命令，狀態機不再一致，Raft 的安全性被徹底打破。

MIT 6.824 2020 年期末考試解析

事務與可串行化 (Transactions and Serializability)

問題背景 ：有三個并發事務 T1, T2, T3。初始時，數據庫里的變量 x, y, z 都是 0。

T1:       T2:         T3:
begin()   begin()     begin()
put(y, 2) put(x, 99)  tmpx = get(x)
end()     put(y, 99)  tmpy = get(y)
          put(z, 99)  tmpz = get(z)
          end()       print tmpx, tmpy, tmpz
                      end()

問題 1：如果 T3 打印出 99, 2, 99，這個結果是可串行化的嗎？

解讀

是的，這是可串行化的。

可串行化 (Serializable) 的意思是，盡管事務是并發執行的，但其最終結果必須等同于這些事務按照 某一個 串行順序執行的結果。我們的任務就是去找到這個串行順序。

我們來試試 T2 -> T1 -> T3 這個順序：

1. 先執行 T2：x 變成 99，y 變成 99，z 變成 99。
2. 接著執行 T1：y 被更新為 2。現在狀態是 x=99, y=2, z=99。
3. 最后執行 T3：讀取 x 得到 99，讀取 y 得到 2，讀取 z 得到 99。打印結果 99, 2, 99。

完全匹配！既然我們找到了一個能產生同樣結果的串行順序，那么這個結果就是可串行化的。

問題 2：如果 T3 打印出 0, 2, 99，這個結果是可串行化的嗎？

解讀

不，這不是可串行化的。

這次我們無法找到任何一個合法的串行執行順序。我們可以用依賴關系來分析：

• T3 讀到了 x = 0。而 T2 會把 x 改成 99。為了能讀到 0，T3 的 get(x) 必須發生在 T2 的 put(x, 99) 之前。所以，在任何等價的串行順序中，必然有 T3 在 T2 之前。
• T3 讀到了 z = 99。z 的初始值是 0，只有 T2 會把它改成 99。為了能讀到 99，T3 的 get(z) 必須發生在 T2 的 put(z, 99) 之后。所以，在任何等價的串行順序中，必然有 T2 在 T3 之前。

這里就出現了致命的矛盾：T3 必須在 T2 之前，同時 T2 又必須在 T3 之前。這是不可能的。這種依賴環路意味著不存在任何一個串行順序能產生這個結果，因此它不是可串行化的。

兩階段提交 (Two-Phase Commit)

問題背景 ：在兩階段提交 (Two-Phase Commit, 2PC) 協議中，worker 在投票 PREPARE 成功后，需要一直持有鎖，直到收到最終的 COMMIT 或 ABORT 消息。如果我們改動一下，讓 worker 在回復 PREPARE 后就立即釋放鎖，會發生什么？

解讀

這么做會徹底破壞事務的原子性和隔離性。PREPARE 階段結束后，worker 處于一個“不確定”的狀態，它并不知道事務最終是會成功還是失敗。在這個節骨眼上釋放鎖，會引發兩種嚴重的問題：

1. 讀到“臟數據” (Dirty Reads) ：如果 worker 釋放了鎖，并且讓其他事務能夠看到它本地“預提交”的修改（比如 T1 修改了 x 的值）。此時，另一個事務 T_other 進來讀到了這個新值。但萬一 T1 的協調者最終決定 ABORT 整個事務，那么 T_other 就相當于讀到了一個從未真實存在過的數據，后續的所有計算都是基于這個“幻影”數據，后果不堪設想。
2. 破壞可串行化 ：另一種情況是，worker 釋放了鎖，但很“聰明”地把修改先隱藏起來，不讓別的事務看見。但即使這樣，另一個事務 T_other 還是可以進來獲取 T1 剛剛釋放的鎖。T_other 可能會讀取一些 T1 沒有修改過的數據（這是舊值），然后 T1 的 COMMIT 消息到達，T1 的修改被應用。之后，T_other 又讀取了 T1 修改過的數據（這是新值）。這樣一來，T_other 在一個事務里，既看到了過去，又看到了未來，看到了一個數據不一致的“混合快照”，這同樣破壞了可串行化。

結論 ：鎖必須持有到事務的最終狀態（COMMIT 或 ABORT）被確定為止，這是 2PC 保證隔離性的關鍵。

Spanner: 為什么所有寫操作要用同一個時間戳？

問題背景 ：在 Spanner 中，一個讀寫事務里的所有寫操作，都會被賦予一個相同的提交時間戳。如果我們把它改成：每次客戶端調用寫操作時，就用當時的 TT.now().latest 作為這個寫操作的時間戳。這樣，一個事務內的不同寫操作就會有不同的時間戳。這會破壞什么？

解讀

這會破壞只讀事務的可串行化保證。

Spanner 的一個核心特性是它能提供嚴格可串行化的只讀事務。它通過給只讀事務選擇一個時間戳 s_read，然后讀取在 s_read 時刻的數據庫快照來實現的。

在原版 Spanner 中，一個讀寫事務 T_rw 的所有寫操作共享一個提交時間戳 s_write。這樣一來，對于任何只讀事務，要么它的 s_read < s_write（完全看不到 T_rw 的修改），要么 s_read > s_write（能看到 T_rw 所有的修改）。這保證了原子性，T_rw 的修改對于只讀事務來說是“要么全有，要么全無”的。

但如果按照問題中的修改，T_rw 的多個寫操作 W1, W2, W3 會有各自不同的時間戳 ts1, ts2, ts3。這時，一個只讀事務的時間戳 s_read 就可能恰好落在這些寫操作之間，比如 ts1 < s_read < ts2。這意味著這個只讀事務會看到 W1 的修改，但看不到 W2 和 W3 的修改。它看到了一個“半成品”狀態的 T_rw，事務的原子性被打破，自然也就不再是可串行化的了。

Spark: for 循環為什么執行那么快？

問題背景 ：Ben 在用 Spark 跑 PageRank，他發現代碼里的那個 for 循環，每次迭代都只花幾毫秒，整個循環跑完不到一秒。但整個 Spark 作業卻要跑好幾個小時。這是為什么？

解讀

這是因為 Spark 的惰性求值 (lazy evaluation) 機制。

在 Spark 中，操作被分為兩類：

• 轉換 (Transformation) ：比如 map, filter, join 等。這些操作并不會立即執行計算。它們只是在構建一個叫做 有向無環圖 (DAG) 的計算藍圖。你可以想象成你在畫一張建筑圖紙，而不是真的在蓋房子。
• 動作 (Action) ：比如 count, collect, saveAsTextFile 等。只有當一個 action 被調用時，Spark 才會根據之前構建好的 DAG 圖，真正地開始分發任務、讀取數據、執行計算。

PageRank 的那個 for 循環里，全都是 transformation 操作，比如 join 和 map。每次循環，Spark 只是在圖紙上又加了幾筆，擴展了一下 DAG。這個過程當然非常快，因為沒有涉及任何大規模的數據計算。真正耗時的計算，是在循環結束后，當某個 action（比如 collect() 或者把結果寫入文件）被調用時，才一次性觸發的。那幾個小時，就是花在了執行這張龐大的計算圖紙上。