iT邦幫忙

2021 iThome 鐵人賽

DAY 26
0
AI & Data

資料工程師修煉之路 Part II系列 第 26

Batch Processing (3-2) - MapReduce Map-Side Joins

[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 策略。


上一篇
Batch Processing (3-1) - MapReduce Reduce-Side Joins and Grouping
下一篇
Batch Processing (4) - Materialization of Intermediate State
系列文
資料工程師修煉之路 Part II30

尚未有邦友留言

立即登入留言