動機
把大計算分給多部機器,只有在結果能重組成預期答案時才有用。分塊大小不等時,平均各塊均值會錯;把重試算兩次,即使各機器的局部計算正確,數據也已改變;浮點總和則可能隨合併樹改變。這些是三個不同問題,增加工作節點不會同時解決它們。
我們先研究精確直方圖,因為其代數清楚:固定類別數給出有界摘要,合併就是逐分量相加。再用此例分析依賴、通訊與負載不均。最後回到浮點求和,同一棵樹既組織計算,也改變捨入誤差。目的是提供可核查的框架中立參考計算,不指定某產品,也不把本機示範冒充硬件基準測試。
MapReduce 的觀點,是對獨立分區作映射,再歸約其摘要;它本身沒有指定作業系統或容錯協議。以下程式在本機串行執行。依賴圖指出在指定資源假設下哪些節點可以平行,但並未量度真正分散式系統的速度。這個界線讓我們能把代數正確性與實際效能分開討論。
定義
以下反覆出現三類對象:被合併的摘要、規定合併哪些摘要的規約,以及量度平行時間的成本模型。
定義 5.1.1
(直方圖摘要與合併)
記錄類別屬於 ,。有限多重集 的直方圖是 ,第 分量是類別 的出現次數。合併為 ,單位元是零向量。
同一類別可有多筆不同觀測;重複處理同一預期觀測,則是數據處理錯誤,除非目標本來就容許複製。
定義 5.1.2
(恰好一次的分區規約)
分區識別碼標示固定輸入版本中互不重疊的片段。歸約規約要求每個預期識別碼恰好有一份獲接納摘要,其他識別碼則一份也沒有。確定的合併樹另外固定每個內部節點配對哪些摘要。
葉節點正確與算術可重現是獨立性質:完全可重現的樹也可以穩定地計算錯誤數據。
定義 5.1.3
(工作量、跨度與清單排程)
工作量是各節點的總算術量;跨度是在無限可用處理器模型下,計算圖中最長的相依鏈。排程模型中,每個作業在 個相同工作節點的任一個上成本為正數 ;清單排程在節點空閒時派發下一個等待作業,作業不被中斷。
有限系統的時間至少是工作量除以處理器數,亦至少是跨度,還可能包括輸入、通訊及等待。 等計數採單位成本算術;任意大的精確整數需要更多位元操作,不能忽略字長模型。排程模型不包括網絡競爭或同時執行造成的速度改變,所以所得上界不是共享連線系統的實際秒數保證。
定理 / 命題
定理 5.1.4
(精確摘要與分區獨立性)
若 是互不重疊分區,則 。任何以它們為葉節點的二元合併樹,在精確整數算術下均得同一摘要。各節點可用 工作、 摘要空間逐筆計數,無須保留原記錄。
定理 5.1.5
(顯示負載偏斜的清單排程界)
令 、。清單排程的完成時間滿足
任何排程都有下界 。上界假設作業開始時已可派發,且有等待作業可執行時,空閒節點不會故意等待。
命題 5.1.6
(浮點樹形求和的誤差界)
設每次加法滿足 、,並無使模型失效的溢出或下溢。高度為 的二叉樹,在 時給出
個葉節點的平衡樹高度為 ,串行鏈可達 。此界是絕對誤差界;精確總和近乎相消時,不保證小相對誤差。
證明思路
證明
(分區獨立性的證明)
對每種類別,互不重疊聯集中的次數等於各塊次數之和,所以逐分量證得合併恆等式。對樹歸納,每個內部節點便代表其後代的聯集。結合律、交換律與零單位元容許改分組、重排及空分區,卻不容許刪去葉節點或把重試當成額外葉節點。局部映射對其 筆記錄各處理一次,並初始化 個計數器,由此得到工作量與儲存界。
互不重疊是代數本身無法提供的唯一假設。
反例模式
重疊片段會重複計數
聲稱:只要片段合起來覆蓋全部輸入,把它們的直方圖相加便得整體直方圖。取記錄 (類別 )和 (類別 ),真正的直方圖是 。一次重試產生片段 與 ,兩者覆蓋輸入卻互相重疊。其直方圖為 和 ,和為 :雖然每個節點都正確計算了自己的片段,記錄 仍被計了兩次。修正後的敘述要求分成互不重疊的片段,而這正是恰好一次規約所強制的。
證明
(清單排程界的證明)
看最後完成、成本為 的作業。若它在時間 開始,它在 期間一直等待;清單排程下有作業等待時不會有節點空閒,所以 個節點在整段 都忙於其他作業,故 。因此 ,再以最大成本 代入 。所有工作終須完成,最大的不可分作業也必須由一個節點完成,故兩個下界都成立。把其他作業切小,不能令這個大作業憑空消失。
證明
(樹形求和界的證明)
從樹根向葉展開計算結果:每個 乘上路徑上的捨入因子,至多 個。其乘積偏離一不多於 ,因為 ,而 。短路徑可補上因子一。減去精確和,再用三角不等式便得上界。這是求和的證明,不能當作所有非線性摘要合併的通用誤差定理。
最後一個證明把關於整棵樹的敘述,化為關於各個葉節點的敘述。
證明透視
樹同時有代數意義與數值高度
捨入模型在每個內部節點用一次:每次計算的加法,等於兩個計算輸入的精確和乘以一個因子 ,其中 。關鍵一步是展開整棵樹,使計算結果成為每個輸入乘以其自身根至葉路徑上各因子之積的總和。樹形只透過路徑長度進入,所以控制上界的是高度而非葉數;令樹形不影響數學直方圖的精確結合律,在這裏不起作用。假設 使每個乘積的界有限。論證以三角不等式收結,也正是在此成為以大小總和表示的絕對界。固定樹消除一種數值變動來源,平衡樹限制路徑長度,但兩者都不能證明病態的相消問題有小相對誤差。
例題詳解
例題 5.1.7
(可執行的映射及平衡歸約)
程式先產生小型數據,按連續區間計數,拒絕重複識別碼,核查缺漏,再按固定二叉樹合併。為了易讀,示例保存輸入清單;局部映射本身卻只需計數陣列,可直接消耗串流迭代器。
def map_counts(values, q):
counts = [0] * q
for value in values:
if not isinstance(value, int) or not 0 <= value < q:
raise ValueError("invalid category")
counts[value] += 1
return counts
def merge(a, b):
return [x + y for x, y in zip(a, b)]
def reduce_once(messages, expected_ids, q):
by_id = {}
for pid, summary in messages:
if pid not in expected_ids or pid in by_id:
raise ValueError("unexpected or repeated partition")
if len(summary) != q or any(not isinstance(x, int) or x < 0
for x in summary):
raise ValueError("invalid summary")
by_id[pid] = summary
if set(by_id) != set(expected_ids):
raise ValueError("missing partition")
level = [by_id[pid] for pid in sorted(expected_ids)]
if not level:
return [0] * q
while len(level) > 1:
level = [merge(level[i], level[i + 1])
if i + 1 < len(level) else level[i]
for i in range(0, len(level), 2)]
return level[0]
values = [(7 * i + 3) % 5 for i in range(37)]
blocks = [values[i:i + 7] for i in range(0, len(values), 7)]
messages = [(pid, map_counts(block, 5))
for pid, block in enumerate(blocks)]
answer = reduce_once(messages, set(range(len(blocks))), 5)
assert answer == map_counts(values, 5)
assert sum(answer) == 37
print(answer)
結果是 [8, 7, 7, 8, 7]。這個本機歸約器保存 個摘要欄位。分散式樹可逐層搬移摘要,但仍須實作相同識別碼與輸入版本規約。檢查形狀及非負整數,不能證明工作節點真的讀了正確分區;那是另一個數據來源合約。
例題 5.1.8
(相同工作量,不同完成時間)
三個節點處理一個成本八的作業及九個成本一的作業,總工作十七。若先派九個小作業,它們令全部節點忙到時間三,最後大作業要到十一才完。若大作業先派,它佔一個節點,其餘兩個在時間五前完成九個小作業,總時間八,達到最大作業下界。
定理上界為 ,所以容許兩種結果,並在第一種次序取等。以下模擬器只計排程,不等待或量度真實機器:
import heapq
def completion(costs, workers):
free = [(0, worker) for worker in range(workers)]
heapq.heapify(free)
for cost in costs:
start, worker = heapq.heappop(free)
heapq.heappush(free, (start + cost, worker))
return max(time for time, worker in free)
assert completion([1] * 9 + [8], 3) == 11
assert completion([8] + [1] * 9, 3) == 8
平均記錄數不等於平均計算成本;有些記錄可能需要昂貴處理。細分作業可改善平衡,卻增加排程及通訊開銷。沒有成本模型,工作量定理不會自動選出最佳分區大小。
例題 5.1.9
(確定的浮點總和可以穩定地漏掉一)
對 binary64 數值 ,由左至右先加兩項會把一捨掉,最後得零;先把兩個大相反數相加則得一,亦即精確實數和。固定樹可以重現較差答案。Python 的 math.fsum([1e16, 1.0, -1e16]) 在此亦回傳一,使用更謹慎求和,但此個案不證明任何函數庫都對所有數據精確。
非負輸入的求和條件數為一,因此總和為正時,絕對界亦給相對界。混合正負時, 可以任意大。報告工作節點數及可重現性時,也應另外說明相消與條件數。
常見錯誤
合併必須符合狀態。合併識別碼互相重疊的摘要,或在沒有推導前先作非線性後處理,都會改變問題。識別碼也必須對應固定輸入版本;同碼但內容改變,不是原本同一分區。
常見錯誤
(忽略筆數平均各分區均值)
片段 與 的均值分別為 和 ,平均為 ;全部四筆記錄的均值卻是 。均值本身不是可合併的摘要。(筆數,總和)這一對,即 和 ,以加法合併為 ,便得回正確均值。
概念視角結構
可合併的摘要就是么半群同態
第一個定理說, 把多重集的不相交聯集變成向量加法,並把空輸入變成 :它是交換么半群之間的同態,單憑這一點,每棵合併樹都正確。平均值則根本不存在這樣的合併規則,而不只是規則不同。輸入 與 的平均值同為 ,但併入片段 後,平均值分別是 和 ;兩個片段平均值的任何函數都不能同時給出這兩個結果。(個數,總和)這對量是同態,平均值只在最後由它算出。
通訊亦有數學大小。 筆記錄映射成 個稠密直方圖,要傳 個欄位;類別宇宙太大時,稠密摘要可能昂貴。局部出現類別少,可用稀疏摘要;但幾乎處處出現的熱門鍵,仍可能造成重負載路徑。深度、位元組數、延遲、工作記憶體及最大分區各是不同瓶頸。
例如假設傳送 個欄位需 時間,其中前者是固定延遲,後者是每個欄位的傳輸時間。在無競爭連線的示意模型下,平衡樹有約 個相依通訊回合;單一串行入口則可能花 級別時間。這不是所有網絡的預言。批次減少延遲支付次數,卻增大訊息並延後首批結果。把熱門鍵拆成多個局部和可分散映射工作,但它們最終仍須相遇,依賴只是搬了位置。
常見錯誤
(把固定樹當作跨環境的逐位元保證)
固定樹只在算術選擇受控時支持逐位元重現。精度、編譯重排、局部加法次序及獲接納葉節點改變,仍可改變結果。實數答案確定,與跨環境逐位元相同,是不同強度的主張。
總結
分區正確性要求預期的互不重疊片段恰好各一次。精確合併代數容許改分組,工作量及排程界則描述不同的平行限制。浮點求和在明確模型下,額外帶有可按樹高限制的誤差。本機參考程式使這些區分可核查,並不冒稱測量了分散式系統。
練習
快速檢查
(類別為零、一、二,映射 及 ,合併摘要,並解釋空塊為何不改變結果。)
逐塊數出每個類別。
解答 · 答案
兩個摘要為 、,合計 ,總數五。空摘要 是加法單位元,不改變結果。每一座標都直接表示次數,所以結論不依賴合併分組。
快速檢查
(兩個節點分別按 與 次序處理作業。求兩種完成時間及清單排程上界。)
模擬兩種次序,再用 與 計算上界。
解答 · 答案
第一種先在時間三完成兩個小作業,大作業再到十三才完。第二種一個節點處理十,另一個在六完成兩個三,所以時間十。總工作十六、最大成本十,上界 ,第一種取等。
快速檢查
(輸入 的求和條件數是多少?為何小的絕對樹形求和界不必代表小相對誤差?)
比較 與 。
解答 · 答案
精確和為 ,大小和為 ,比值是 。把絕對估計 除以微小的精確和,會把 放大這麼多倍。短樹減少捨入階段,不能消除數據本身的相消條件數。
快速檢查
(歸約器預期識別碼零至三,只收到零、一、三,但報告筆數剛好合計正確。應否接納?若改為一出現兩次,又應如何?)
檢查恰好一次規約,而非總數。
解答 · 答案
應拒絕,因為缺少分區二。筆數偶然吻合,不證明預期記錄已處理;同樣地,重複的一也不應當成獨立葉節點再接納。這些檢查保護輸入身份,但不代替對每份摘要內容的數學驗證。