[Day 26] Batch Processing (3-2) - MapReduce Map-Side Joins

續 Day 25

Map-Side Joins

昨天講的 join 是在 reducer 端完成，所以也稱為 reduce-side joins，這個 join 方法的優點就是你不用對輸入資料做出任何假設，你只要知道關鍵資料就好了，而缺點就是所有的排序、複製到 reducer 和 reducer 合併所有輸入的操作都是昂貴的，端看你分配的硬體資源有多少，資料可能在 MapReduce 的階段中多次寫入到硬碟裡。

換個方向說，如果你能對輸入資料做出某些假設，它是有可能讓 join 變快速，稱之為 map-side join，這個方法使用縮減的 MapReduce Job，意味者 map-side join 未使用 reducer 和排序，每一個 mapper 就只讀取輸入資料，然後輸出，搞定！

Broadcast hash joins

執行 map-side join 的最簡單方法適用於大量數據集 join 小量數據集，精確一點的說，小量數據集需要小到能在每個 mapper 的記憶體中存一份。

一樣舉昨天圖 10-2 分析 user 活動事件的例子，將 user 的生日 join 到活動事件。

若 User 資料庫小到能存進記憶體中，當 mapper 啟動時，mapper 就能把 User 資料庫存成 hash table，爾後 mapper 開始掃描 user 活動事件時，就能快速從 hash table 查找 user 的生日年份了。

這簡單但有效的算法稱之為 broadcast hash join，廣播 (broadcast) 代表每個 mapper 皆有小量數據集，hash 代表使用 hash table；此 join 在 Pig (叫做 replicated join) 和 Hive (叫做 MapJoin) 皆有支援。

Partitioned hash joins

如果 map-site join 所有用到的輸入資料都是用一樣的方法做 分區 (parition) 的話，你就能更進一步的縮小載入記憶體中的數據集大小，一樣用上圖 10-2 的例子，你可以安排所有的活動事件和 user 資料庫皆以 user ID 的個位數數字做分區，所以 mapper 3 就會載入所有 ID 尾數為 3 的資料，然後完成 join。

Partitioned hash joins 在 Hive 也被稱為 bucketed map joins 。

Map-side merge joins

另一個 map-side join 的變體是，不只所有輸入資料分區策略相同，還是以相同 key 排序過的資料。

在這個狀況下，小量數據集能否存進記憶體就不重要了，因為 mapper 也能執行相同的合併操作（這通常由 reducer 完成），漸進的讀取 join 2 邊的資料，然後完成 join。

若 map-side merge join 可以作業，它的輸入十之八九是由其他 MapReduce Job 的輸出產生，雖然大多情況下會像昨天那樣，由 reduce-side 搞定 join，然而，若該資料集可能會被其他的 join 用到，就很值得先做好分區 & 排好序，然後使用 map-side merge join 完成 join 作業。

Join 小結

在優化 join 策略時，不只是要知道編碼或資料夾命名為何，更重要的是要了解分散式檔案系統裡相關數據集的物理佈局，知道檔案怎麼儲存，用什麼 key 當做分區策略等等。

了解這些過後，才能幫助你選擇一個適合的 join 策略。