請求級平行與 MapReduce

第三種平行

上一篇導覽把資料中心重新框定為一台倉儲級電腦——一台機箱恰好是一整棟建築的機器。現在我們問這台機器存在就是為了回答的問題：它跑的是什麼工作，那工作又如何平行？在前面幾級，我們在一顆晶片裡見過兩種口味的平行。指令級平行在管線裡讓指令重疊；資料級平行（SIMD 與 GPU）一次對許多資料元素跑同一個運算。倉儲又加上了第三種、更粗粒度的口味，它住在機器之間，而它正是付這棟建築電費的那一種。

把它叫做請求級平行（RLP）。當你打一次搜尋、載入一則動態、或送出一則訊息，你產生了一個請求，它在那一瞬間幾乎完全獨立於別人的請求。十億名使用者打向一個服務，產生十億個大致無關的工作單元，而倉儲只是把每一個交給任何一台空著的機器。沒有指令要重疊，也沒有向量要加寬——平行就明明白白地坐在工作負載裡，早已被使用者自己剁成了片。那份獨立性，正是讓倉儲級運算變得可處理的禮物。

當資料對一個機箱來說太大

服侍即時請求只是倉儲工作的一半。另一半是批次工作：嚼穿一個大到沒有任何單一機器裝得下、更別說在合理時間內處理完的資料集——對整個網路建立搜尋索引、跨數十億份文件數字數、在一座日誌山上做訓練。這又是資料級平行，只是放大到了建築尺度：同一個運算施加在一個龐大的資料集上，只不過資料現在攤在數千顆磁碟上，而不是坐在一個核心的向量暫存器裡。

天真的計畫——把所有資料複製到一台強力電腦上——會兩頭落空。資料裝不下，而把數 PB 搬過網路要花上好幾天。致勝的一招把幾何翻轉過來：與其把資料帶到程式碼那裡，你把程式碼運送到資料早已所在之處。每台機器讀取坐在它自己本地磁碟上的那一片資料，只對那一片跑你的計算，然後只有那一小份結果穿過資料中心網路。這條「搬運計算，而非搬運資料」的原則，正是我們即將見到的整套程式設計模型的種子。

MapReduce：兩個函式加一次洗牌

MapReduce 是一個美麗地小巧的想法，它讓橫跨數千台機器的批次工作變得連普通程式設計師也寫得出來。你只要提供兩個函式。Map（映射）接受一筆輸入記錄，吐出若干個 (鍵, 值) 對——它在每一片資料上平行地施行，就在早已持有那些片的機器上。Reduce（歸併）接受一個鍵，連同任何一個 map 為那個鍵產出的所有值，把它們摺疊成一個最終答案。在兩者之間，系統執行一次洗牌（shuffle）：它把每個值搬到負責它那個鍵的機器上，於是每個 reducer 都看見一個完整的群組。Map 與 reduce 是你寫的部分；洗牌、排程與故障處理則是框架免費給你的。

經典的例子是跨數十億份文件數字數，它寫在一張餐巾紙上就放得下。map 函式讀一份文件，對它看見的每一個字，吐出一對 (字, 1)。洗牌把比方說「cat」這個字的所有 1 全聚到一個 reducer 上。「cat」的 reduce 函式只是把它那串 1 加起來，吐出 (cat, 總數)。讓一千台機器同時跑 map，每台跑它自己本地的文件，唯一的網路流量就是那道精簡的部分計數串流——正是上一節那個「搬運程式碼，而非搬運資料」的幾何。

WORD COUNT in MapReduce (pseudocode + tiny trace)

  map(docID, text):
      for each word w in text:
          emit(w, 1)

  reduce(word, list_of_counts):
      emit(word, sum(list_of_counts))

Trace on 2 input slices (run on 2 machines in parallel):

  slice A = "the cat sat"      slice B = "the cat ran"
  map A -> (the,1)(cat,1)(sat,1)
  map B -> (the,1)(cat,1)(ran,1)

  --- shuffle: group every value by its key ---
  the -> [1, 1]     cat -> [1, 1]
  sat -> [1]        ran -> [1]

  reduce -> (the,2) (cat,2) (sat,1) (ran,1)

Only the small (key,partial) pairs cross the network --
not the documents themselves.

整套分散式數字數：兩行 map、兩行 reduce，加上框架替你跑的一次洗牌。程式設計師從不寫一行關於哪台機器做什麼、或某台死掉時該怎麼辦的程式。

切分：框架把輸入資料集切成許多片，每一片的大小剛好坐得進一台機器的本地磁碟。
平行映射：它把你的 map 函式運送到持有各片的機器上，全部一次跑起來，在本地吐出 (鍵, 值) 對。
洗牌：它把那些對排序並跨網路繞送，使得某個鍵的每一個值都落到同一台 reducer 機器上。
平行歸併：每個 reducer 把它那個鍵的值清單摺疊成最終結果，框架再把輸出寫回去。

從 MapReduce 到 Spark，以及什麼始終成立

MapReduce 是第一個被廣泛使用的模型，但它有個實在的代價：在每一個 map 與 reduce 階段之間，它把中間結果一路寫到磁碟上，這很安全，但當一個計算有許多階段時就很慢——想想一個迴圈幾十次的迭代演算法。像 Spark 這樣較新的系統保留了同樣的「先映射、再洗牌、再歸併」骨架，卻試著把中間資料跨階段留在記憶體裡，並讓你把多個運算串成一條更豐富的管線，而不是逼一切恰好擠進一個 map 與一個 reduce。在這個入門層次，要帶走的不是 API 的差異，而是那個共有的形狀：把資料切分、在本地計算、依鍵洗牌、再合併。

注意這多麼乾淨地呼應了較低幾級的想法，只是換到了新的尺度。洗牌是一個穿著網路球衣的記憶體牆問題：搬資料很貴，所以你設計成盡量少搬，並讓計算待在它的資料附近——正是快取與區域性背後的同一種直覺，只是現在以機架與交換器為單位來量，而不是以奈米。而那個 (鍵, 值) 的分群，不過是建立一張依鍵索引的表的一個巨大、分散式的版本。倉儲不發明新原則；它只是把你已經知道的那些，橫跨一整棟建築地拉長。

誠實的極限：Amdahl、洗牌與落隊者

人很容易相信，有一千台機器，一件工作就跑快一千倍。它不會，而原因是一位老朋友：Amdahl 定律，我們最早在多核心晶片那裡見過它，而它原封不動地放大上來。工作裡任何無法平行化的部分——讀取最開頭的那筆輸入、那個必須看見全部資料的最後歸併、框架自己的協調——都為執行時間設下一個下限，再多機器也突破不了。如果哪怕只有 1% 的工作本質上是序列的，那麼不管你丟幾千個節點上去，你的加速都被封在 100 倍附近。

洗牌是另一道硬極限，而它正屬於這個尺度。映射與歸併壯麗地平行，但夾在它們之間的，是一個可能把一大部分中間資料搬過網路的步驟——而網路的頻寬是有限的，還由所有人共用。在許多真實工作上，最慢的階段是洗牌，而不是計算，這正是為什麼下一篇導覽要讓網路與它的延遲當主角。這個教訓和加速器那一級的屋頂線想法押韻：過了某個點，你就不是受計算所限，而是受通訊所限。