核心概念#

Google 雲計算中最重要的 MapReduce 工具，其根本原理就是計算機算法中常見的分治算法（Divide-and-Conquer），作者稱之為「各個擊破」法——將複雜的大問題分解成很多小問題分別求解，然後再把小問題的解合併成原始問題的解。

分治算法的原理#

• 分治算法的基本原理：將一個複雜的問題分成若干個簡單的子問題進行解決，然後對子問題的結果進行合併
• 歸併排序（Merge Sort）是經典例子：
  • 冒泡排序的複雜度是 $O(N^2)$，對大數組不可行
  • 分治法將大數組一分為二，各自排序後合併，合併只需 1/4 的比較量
  • 可以繼續遞歸拆分，直到子數組只有兩個元素
  • 複雜度從 $O(N^2)$ 簡化為 $O(N \cdot \log N)$，百萬級數據可縮短一萬倍

從分治算法到 MapReduce#

• 以矩陣乘積 $C = A \times B$ 為例說明分治法如何擴展到多台服務器
• 將矩陣 $A$ 按行拆成 10 個小矩陣 $A_1, A_2, …, A_{10}$，分別在 10 台服務器上計算與 $B$ 的乘積，計算時間縮短為 1/10
• 若需要進一步分解，可將 $A$ 按行、$B$ 按列同時切分，用 100 台服務器完成更大的任務
• 若只需要計算 $C$ 中某個特定元素 $c_{nm}$，也可以通過分治法用 10 台機器縮短計算時間

這就是 MapReduce 的根本原理：將大任務拆分成小的子任務（Map），並且完成子任務的計算，將中間結果合併成最終結果（Reduce）。自動拆分、負載均衡、合併返回值都是 MapReduce 在工程上所做的事情。

• 在 Google 開發 MapReduce 之前，作者在約翰·霍普金斯大學訓練最大熵模型時就已經用了類似思想——手工將大矩陣拆開推送到約 20 台服務器上
• MapReduce 與手工方式唯一的差別是：所有的調度工作都是自動完成的

本章小結#

MapReduce 的原理原來這麼簡單——將複雜的大問題分解成很多小問題分別求解，然後再把小問題的解合併成原始問題的解。在生活中大量用到的、真正有用的方法往往簡單而又樸實。