Raft / 事務(wù)與可串行化 / 兩階段提交 / Spanner ...
MapReduce (1): 如何用 MapReduce 找最大值？
這道題非常經(jīng)典，是理解 MapReduce 思想的敲門磚。
問題背景 ：想象一下，我們有 100 個(gè)文件，每個(gè)文件里都寫滿了數(shù)字，一行一個(gè)。我們的任務(wù)是找出這所有數(shù)字里的最大值。
解讀
MapReduce 的核心思想是“分而治之”。
map階段 ：map函數(shù)就像是“地方海選賽”。每個(gè)map任務(wù)會(huì)分配到一個(gè)或多個(gè)文件。它的工作很簡單：就在自己負(fù)責(zé)的這堆數(shù)里，找出那個(gè)最大的“地方冠軍”。然后，它會(huì)輸出一個(gè)鍵值對(duì)，比如( "max", 12345 )，其中12345就是它找到的那個(gè)局部最大值。這里用一個(gè)固定的key(比如空字符串""或者"max") 是個(gè)小技巧，目的是確保所有這些“地方冠軍”都能被送到同一個(gè)reduce任務(wù)那里去進(jìn)行“總決賽”。reduce階段 ：reduce函數(shù)就是“全國總決賽”。因?yàn)榍懊嫠械?nbsp;map任務(wù)都用了同一個(gè)key，所以 MapReduce 框架會(huì)把所有map的輸出（也就是所有“地方冠軍”的數(shù)值）都集合起來，然后交給一個(gè)reduce任務(wù)。這個(gè)reduce任務(wù)的工作就更簡單了：在這些“地方冠軍”里，選出那個(gè)唯一的“全國總冠軍”，也就是全局最大值。
reduce 函數(shù)會(huì)被調(diào)用幾次？
只會(huì)有 1 次。因?yàn)槲覀兦擅畹卦O(shè)計(jì)了讓所有 map 的輸出都使用同一個(gè) key，所以這些數(shù)據(jù)只會(huì)被匯集到一個(gè) reduce 任務(wù)中處理。
MapReduce (2): 為什么寫入中間文件需要“先寫臨時(shí)文件再重命名”？
問題背景 ：有個(gè)同學(xué)叫 Alyssa，她在實(shí)現(xiàn) MapReduce 的 worker 時(shí)偷懶了。她直接用 os.Create() 來創(chuàng)建中間結(jié)果文件，而不是遵循“先寫到一個(gè)臨時(shí)文件，寫完后再用 os.Rename() 重命名”這個(gè)最佳實(shí)踐。這會(huì)出什么問題？
解讀
這個(gè)問題觸及了分布式系統(tǒng)中一個(gè)非常重要的概念：處理“慢節(jié)點(diǎn)”和任務(wù)的原子性。
在 MapReduce 中，master 有一個(gè)叫做 投機(jī)執(zhí)行 (speculative execution) 的機(jī)制。如果它發(fā)現(xiàn)某個(gè) map 任務(wù)運(yùn)行得特別慢，它可能會(huì)在另一臺(tái)機(jī)器上重新啟動(dòng)一個(gè)一模一樣的任務(wù)，誰先跑完就用誰的結(jié)果。
現(xiàn)在，我們來想象一個(gè)災(zāi)難場景：
master派任務(wù)M給worker W1。W1由于網(wǎng)絡(luò)、CPU 等原因，運(yùn)行得非常慢。master等得不耐煩了，啟動(dòng)了投機(jī)執(zhí)行，把同樣的任務(wù)M又派給了worker W2。W2身強(qiáng)力壯，很快就完成了計(jì)算，并用os.Create("mr-M-R")創(chuàng)建并寫好了中間文件。master收到W2的捷報(bào)，于是啟動(dòng)了對(duì)應(yīng)的reduce任務(wù)，這個(gè)reduce任務(wù)開始讀取W2生成的那個(gè)mr-M-R文件。- 就在此時(shí)，慢吞吞的
W1終于也完成了它的計(jì)算。它也執(zhí)行了os.Create("mr-M-R")。 - 關(guān)鍵點(diǎn)來了：
os.Create()在文件已存在時(shí)，會(huì)直接清空它！于是，W2辛辛苦苦生成的、reduce任務(wù)正在讀取的文件，瞬間被W1清空了。 reduce任務(wù)讀著讀著發(fā)現(xiàn)文件變空了，最終得出了錯(cuò)誤的結(jié)果。
正確的做法是什么呢？
原子性的“寫入臨時(shí)文件后重命名”。W1 和 W2 都先寫入各自的臨時(shí)文件（比如 mr-M-R-temp-W1），寫完后，再用 os.Rename() 這個(gè)原子操作去搶占最終的文件名。這樣就能保證，無論誰快誰慢，reduce 任務(wù)讀到的文件一定是某個(gè) worker 完整寫入的結(jié)果，而不是一個(gè)被中途清空的文件。
GFS: 同時(shí)讀同一個(gè) GFS 文件，內(nèi)容一定相同嗎？
問題背景 ：兩個(gè)客戶端，在沒有任何寫入操作的情況下，同時(shí)從頭到尾讀取 GFS 上的同一個(gè)文件。它們讀到的內(nèi)容保證會(huì)一樣嗎？
解讀
不保證。 GFS 在設(shè)計(jì)上為了性能和可用性，在某些一致性上做了妥協(xié)。
問題的根源在于 GFS 的一種特殊寫操作：記錄追加 (record append)。當(dāng)一個(gè)客戶端執(zhí)行追加操作時(shí)，primary 副本會(huì)確定一個(gè)偏移量，然后通知所有 secondary 副本也寫入。但如果某個(gè) secondary 副本當(dāng)時(shí)正好網(wǎng)絡(luò)不通或者掛了，它可能就收不到這個(gè)寫入指令。GFS 的 primary 不會(huì)死等所有副本都成功，它只會(huì)把錯(cuò)誤報(bào)告給客戶端。
這就導(dǎo)致了一個(gè)后果：同一個(gè)數(shù)據(jù)塊的不同副本（chunk replica），可能內(nèi)容不一樣了。一個(gè)副本有這次追加的數(shù)據(jù)，另一個(gè)沒有。
所以，當(dāng)那兩個(gè)客戶端來讀取文件時(shí)，如果它們不幸地連接到了持有不同數(shù)據(jù)副本的 chunkserver 上，它們讀到的內(nèi)容自然也就不一樣了。
Raft (1): currentTerm 必須持久化嗎？
問題背景 ：Ben 同學(xué)覺得每次都持久化 currentTerm 太麻煩，他想了個(gè)“聰明”的辦法：當(dāng)一個(gè)節(jié)點(diǎn)重啟時(shí)，不從持久化存儲(chǔ)里讀 currentTerm，而是直接讀取它日志里最后一條記錄的任期號(hào)，并把它作為自己的 currentTerm。這會(huì)出什么問題？
解讀
Ben 的這個(gè)改動(dòng)會(huì)破壞 Raft 協(xié)議的根基——投票的正確性，從而可能導(dǎo)致“腦裂”（即同一任期出現(xiàn)兩個(gè) leader）。
currentTerm 和 votedFor 這兩個(gè)狀態(tài)，是 Raft 節(jié)點(diǎn)在選舉中的“記憶”。它們必須被持久化，以確保節(jié)點(diǎn)在崩潰重啟后不會(huì)“失憶”并做出矛盾的決定。
我們來看一個(gè)具體的失敗場景：
- 一個(gè)集群，節(jié)點(diǎn)
P1的日志里最后一條記錄的任期是 10。所以它當(dāng)前的currentTerm也是 10。 - 候選人
P2發(fā)起了 term 11 的選舉。P1收到投票請(qǐng)求，它一看任期比自己的高，于是投票給了P2。同時(shí)，P1把自己的（內(nèi)存中的）currentTerm更新為 11，并持久化votedFor = P2。 - 在
P1還來不及持久化currentTerm = 11的時(shí)候，它突然崩潰了。 P1重啟。按照 Ben 的邏輯，它會(huì)讀取日志，發(fā)現(xiàn)最后一條記錄的任期是 10，于是它把自己的currentTerm初始化為 10。- 這時(shí)，另一個(gè)候選人
P3也發(fā)起了 term 11 的選舉。P3的投票請(qǐng)求到達(dá)了P1。P1檢查后發(fā)現(xiàn)，請(qǐng)求的任期 11 比自己的當(dāng)前任期 10 要高，并且（假設(shè)它沒持久化votedFor或者votedFor邏輯也有問題）它認(rèn)為自己還沒在 term 11 里投過票。于是，它又投票給了P3！
災(zāi)難發(fā)生了 ：P1 在同一個(gè)任期 11 里，先后為 P2 和 P3 兩個(gè)不同的候選人投了票。這嚴(yán)重違反了 Raft 的選舉安全規(guī)則，完全可能導(dǎo)致 P2 和 P3 都分別獲得足夠選票成為 leader，系統(tǒng)出現(xiàn)“雙主”，狀態(tài)機(jī)將執(zhí)行不同的指令，數(shù)據(jù)一致性被破壞。
Raft (2): AppendEntries 時(shí)直接覆蓋日志行不行？
問題背景 ：Bob 同學(xué)為了簡化代碼，修改了 AppendEntries RPC 的處理邏輯。他不再檢查日志沖突，而是簡單粗暴地直接用 leader 發(fā)來的日志覆蓋本地日志。這為什么是錯(cuò)的？
解讀
這個(gè)改動(dòng)破壞了 Raft 的日志匹配屬性 (Log Matching Property)，這是確保安全性的核心。直接覆蓋會(huì)導(dǎo)致一個(gè)已提交的日志條目被錯(cuò)誤地更改。
看這個(gè)例子：
- 有三個(gè)節(jié)點(diǎn)
S1,S2,S3。S1是 term 1 的leader。 S1在 index 1 追加了日志A，在 index 2 追加了日志B。它把[A, B]發(fā)給了S2和S3。S2成功收到了[A, B]。S1和S2構(gòu)成了多數(shù)派，所以A和B在S1上被提交了。S3可能因?yàn)榫W(wǎng)絡(luò)延遲只收到了A。- 現(xiàn)在，一個(gè) 之前 從
S1發(fā)出的、但被網(wǎng)絡(luò)延遲了的AppendEntriesRPC（這個(gè) RPC 只包含A）終于到達(dá)了S2。 - 按照 Bob 的錯(cuò)誤邏輯，
S2不做沖突檢查，直接用這個(gè) RPC 的內(nèi)容來更新自己的日志。它會(huì)把自己的日志從[A, B]截?cái)嗷?nbsp;[A]。 S1掛了。S3發(fā)起 term 2 的選舉。S3的日志是[A]，S2的日志現(xiàn)在也是[A]，所以S2會(huì)投票給S3。S3成為 term 2 的新leader。它在 index 2 寫入了一個(gè) 不同 的日志C。S3把C復(fù)制給了S2，并且它們倆構(gòu)成了多數(shù)派，提交了C。
最終結(jié)果 ：在 index 2 這個(gè)位置，S1 提交的日志是 B，而 S2 和 S3 提交的卻是 C。不同的節(jié)點(diǎn)在同一個(gè)日志索引上提交了不同的命令，狀態(tài)機(jī)不再一致，Raft 的安全性被徹底打破。
MIT 6.824 2020 年期末考試解析
事務(wù)與可串行化 (Transactions and Serializability)
問題背景 ：有三個(gè)并發(fā)事務(wù) T1, T2, T3。初始時(shí)，數(shù)據(jù)庫里的變量 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，這個(gè)結(jié)果是可串行化的嗎？
解讀
是的，這是可串行化的。
可串行化 (Serializable) 的意思是，盡管事務(wù)是并發(fā)執(zhí)行的，但其最終結(jié)果必須等同于這些事務(wù)按照 某一個(gè) 串行順序執(zhí)行的結(jié)果。我們的任務(wù)就是去找到這個(gè)串行順序。
我們來試試 T2 -> T1 -> T3 這個(gè)順序：
- 先執(zhí)行
T2：x變成 99，y變成 99，z變成 99。 - 接著執(zhí)行
T1：y被更新為 2。現(xiàn)在狀態(tài)是x=99, y=2, z=99。 - 最后執(zhí)行
T3：讀取x得到 99，讀取y得到 2，讀取z得到 99。打印結(jié)果99, 2, 99。
完全匹配！既然我們找到了一個(gè)能產(chǎn)生同樣結(jié)果的串行順序，那么這個(gè)結(jié)果就是可串行化的。
問題 2：如果 T3 打印出 0, 2, 99，這個(gè)結(jié)果是可串行化的嗎？
解讀
不，這不是可串行化的。
這次我們無法找到任何一個(gè)合法的串行執(zhí)行順序。我們可以用依賴關(guān)系來分析：
T3讀到了x = 0。而T2會(huì)把x改成 99。為了能讀到 0，T3的get(x)必須發(fā)生在T2的put(x, 99)之前。所以，在任何等價(jià)的串行順序中，必然有T3在T2之前。T3讀到了z = 99。z的初始值是 0，只有T2會(huì)把它改成 99。為了能讀到 99，T3的get(z)必須發(fā)生在T2的put(z, 99)之后。所以，在任何等價(jià)的串行順序中，必然有T2在T3之前。
這里就出現(xiàn)了致命的矛盾：T3 必須在 T2 之前，同時(shí) T2 又必須在 T3 之前。這是不可能的。這種依賴環(huán)路意味著不存在任何一個(gè)串行順序能產(chǎn)生這個(gè)結(jié)果，因此它不是可串行化的。
兩階段提交 (Two-Phase Commit)
問題背景 ：在兩階段提交 (Two-Phase Commit, 2PC) 協(xié)議中，worker 在投票 PREPARE 成功后，需要一直持有鎖，直到收到最終的 COMMIT 或 ABORT 消息。如果我們改動(dòng)一下，讓 worker 在回復(fù) PREPARE 后就立即釋放鎖，會(huì)發(fā)生什么？
解讀
這么做會(huì)徹底破壞事務(wù)的原子性和隔離性。PREPARE 階段結(jié)束后，worker 處于一個(gè)“不確定”的狀態(tài)，它并不知道事務(wù)最終是會(huì)成功還是失敗。在這個(gè)節(jié)骨眼上釋放鎖，會(huì)引發(fā)兩種嚴(yán)重的問題：
- 讀到“臟數(shù)據(jù)” (Dirty Reads) ：如果
worker釋放了鎖，并且讓其他事務(wù)能夠看到它本地“預(yù)提交”的修改（比如T1修改了x的值）。此時(shí)，另一個(gè)事務(wù)T_other進(jìn)來讀到了這個(gè)新值。但萬一T1的協(xié)調(diào)者最終決定ABORT整個(gè)事務(wù)，那么T_other就相當(dāng)于讀到了一個(gè)從未真實(shí)存在過的數(shù)據(jù)，后續(xù)的所有計(jì)算都是基于這個(gè)“幻影”數(shù)據(jù)，后果不堪設(shè)想。 - 破壞可串行化 ：另一種情況是，
worker釋放了鎖，但很“聰明”地把修改先隱藏起來，不讓別的事務(wù)看見。但即使這樣，另一個(gè)事務(wù)T_other還是可以進(jìn)來獲取T1剛剛釋放的鎖。T_other可能會(huì)讀取一些T1沒有修改過的數(shù)據(jù)（這是舊值），然后T1的COMMIT消息到達(dá)，T1的修改被應(yīng)用。之后，T_other又讀取了T1修改過的數(shù)據(jù)（這是新值）。這樣一來，T_other在一個(gè)事務(wù)里，既看到了過去，又看到了未來，看到了一個(gè)數(shù)據(jù)不一致的“混合快照”，這同樣破壞了可串行化。
結(jié)論 ：鎖必須持有到事務(wù)的最終狀態(tài)（COMMIT 或 ABORT）被確定為止，這是 2PC 保證隔離性的關(guān)鍵。
Spanner: 為什么所有寫操作要用同一個(gè)時(shí)間戳？
問題背景 ：在 Spanner 中，一個(gè)讀寫事務(wù)里的所有寫操作，都會(huì)被賦予一個(gè)相同的提交時(shí)間戳。如果我們把它改成：每次客戶端調(diào)用寫操作時(shí)，就用當(dāng)時(shí)的 TT.now().latest 作為這個(gè)寫操作的時(shí)間戳。這樣，一個(gè)事務(wù)內(nèi)的不同寫操作就會(huì)有不同的時(shí)間戳。這會(huì)破壞什么？
解讀
這會(huì)破壞只讀事務(wù)的可串行化保證。
Spanner 的一個(gè)核心特性是它能提供嚴(yán)格可串行化的只讀事務(wù)。它通過給只讀事務(wù)選擇一個(gè)時(shí)間戳 s_read，然后讀取在 s_read 時(shí)刻的數(shù)據(jù)庫快照來實(shí)現(xiàn)的。
在原版 Spanner 中，一個(gè)讀寫事務(wù) T_rw 的所有寫操作共享一個(gè)提交時(shí)間戳 s_write。這樣一來，對(duì)于任何只讀事務(wù)，要么它的 s_read < s_write（完全看不到 T_rw 的修改），要么 s_read > s_write（能看到 T_rw 所有的修改）。這保證了原子性，T_rw 的修改對(duì)于只讀事務(wù)來說是“要么全有，要么全無”的。
但如果按照問題中的修改，T_rw 的多個(gè)寫操作 W1, W2, W3 會(huì)有各自不同的時(shí)間戳 ts1, ts2, ts3。這時(shí)，一個(gè)只讀事務(wù)的時(shí)間戳 s_read 就可能恰好落在這些寫操作之間，比如 ts1 < s_read < ts2。這意味著這個(gè)只讀事務(wù)會(huì)看到 W1 的修改，但看不到 W2 和 W3 的修改。它看到了一個(gè)“半成品”狀態(tài)的 T_rw，事務(wù)的原子性被打破，自然也就不再是可串行化的了。
Spark: for 循環(huán)為什么執(zhí)行那么快？
問題背景 ：Ben 在用 Spark 跑 PageRank，他發(fā)現(xiàn)代碼里的那個(gè) for 循環(huán)，每次迭代都只花幾毫秒，整個(gè)循環(huán)跑完不到一秒。但整個(gè) Spark 作業(yè)卻要跑好幾個(gè)小時(shí)。這是為什么？
解讀
這是因?yàn)?Spark 的惰性求值 (lazy evaluation) 機(jī)制。
在 Spark 中，操作被分為兩類：
- 轉(zhuǎn)換 (Transformation) ：比如
map,filter,join等。這些操作并不會(huì)立即執(zhí)行計(jì)算。它們只是在構(gòu)建一個(gè)叫做 有向無環(huán)圖 (DAG) 的計(jì)算藍(lán)圖。你可以想象成你在畫一張建筑圖紙，而不是真的在蓋房子。 - 動(dòng)作 (Action) ：比如
count,collect,saveAsTextFile等。只有當(dāng)一個(gè)action被調(diào)用時(shí)，Spark 才會(huì)根據(jù)之前構(gòu)建好的 DAG 圖，真正地開始分發(fā)任務(wù)、讀取數(shù)據(jù)、執(zhí)行計(jì)算。
PageRank 的那個(gè) for 循環(huán)里，全都是 transformation 操作，比如 join 和 map。每次循環(huán)，Spark 只是在圖紙上又加了幾筆，擴(kuò)展了一下 DAG。這個(gè)過程當(dāng)然非?？欤?yàn)闆]有涉及任何大規(guī)模的數(shù)據(jù)計(jì)算。真正耗時(shí)的計(jì)算，是在循環(huán)結(jié)束后，當(dāng)某個(gè) action（比如 collect() 或者把結(jié)果寫入文件）被調(diào)用時(shí)，才一次性觸發(fā)的。那幾個(gè)小時(shí)，就是花在了執(zhí)行這張龐大的計(jì)算圖紙上。
