MapReduce คืออะไร เข้าใจที่มา Hadoop และในด้าน Distributed Computing

Published in

Mils’ Blog

3 min readOct 22, 2022

พอเราได้ลองเขียนเรื่อง Spark คืออะไร เกิดขึ้นมาได้ยังไง หัวข้อที่ Data Engineer ต้องรู้ ก็เจอหัวข้อที่น่าสนใจที่คิดว่าน่าลองหยิบมาเล่าเหมือนกัน นั่นคือ MapReduce

โดยบทความนี้เราจะอธิบาย MapReduce ในคอนเซปทั่วไปที่ไม่ได้เจาะจงเฉพาะของ Hadoop

MapReduce คืออะไร

MapReduce เป็น programming model หนึ่งที่ไม่ผูกติดกับภาษาไหนหรือ platform ไหน และเป็นหนึ่งในหัวใจด้าน Big Data และ NoSQL ซึ่งถึงแม้ตอนนี้ MapReduce จะมี abstraction ที่ออกมาหลายรูปแบบ เช่น Spark SQL และ Hive ที่ทำให้เรา process ข้อมูลได้โดยไม่ต้องเขียน map หรือ reduce functions เอง แต่การเข้าใจ MapReduce จะทำให้เราเข้าใจคอนเซปของ distributed programming และการ process ข้อมูลใน Spark ด้วย

จุดเริ่มต้นของ MapReduce

จุดเริ่มต้นของ MapReduce จริงๆยังถูกถกเถียงกันมาว่ามาจากไหน แต่หลักฐานที่จับต้องได้มากที่สุดคือ white paper จาก Google เรื่อง “MapReduce: Simplified Data Processing on Large Clusters” ออกมาในปี 2004 ซึ่งเล่าแบบ high-level ว่า Google นั้นทำ indexing กับ ranking ข้อมูล text ขนาดใหญ่ สำหรับ search-engine ยังไง

ทั้งๆที่ paper นั้นไม่มี source code มอบให้แต่ภายหลังถูก reimplement เป็นระบบต่างๆไม่รู้กี่ครั้ง ไม่ว่าจะ standalone system อย่าง Hadoop, Disco, Amazon Elastic MapReduce

หรือนำมาเป็น query language ภายในระบบอีกที เช่น MongoDB, Greenplum DB, Aster Data

จึงเห็นได้ว่าเวลาเราเสิร์ชคำว่า MapReduce จะเจอชื่อ service พวกนี้เต็มไปหมด โดยเฉพาะ Hadoop MapReduce ซึ่งสำหรับ MapReduce ใน Hadoop แล้ว ถือเป็น processing framework หนึ่งใน Hadoop เลย

จุดเริ่มต้นของ MapReduce จึงเริ่มจาก paper จาก Google ในปี 2004 จนถูกนำมาใช้แพร่หลายใน industry ในพาร์ทของ distributed data processing ภายในปี 2012

เกิดเป็น Hadoop ขึ้น

หลังจากที่ Google ได้ปล่อย paper มา จนไปเข้าตา Doug Cutting และ Mike Cafarella เข้า ซึ่งทั้งสองคนเล็งเห็นว่า มันน่าจะเอาไปช่วย Lucene

Lucene เป็น open-source ที่ใช้สำหรับทำ search indexer โดยนำ MapReduce ไปช่วย Lucene ในการจัดการการ search ข้อมูลขนาดใหญ่ได้

(ในบางตำราก็บอกว่านำไปช่วย Nutch ซึ่งจริงๆมันก็คล้ายๆก็ เพราะ Nutch build on top of Lucene และคนสร้างเดียวกัน)

ต่อมาพวกเขาทั้งสองก็ได้สร้าง Hadoop framework ขึ้นมา โดยใช้ MapReduce ช่วยในการรันข้อมูลใน cluster ขนาดใหญ่ ตอนนั้น Cutting เองเป็นพนักงานของ Yahoo! (Yahoo! ก็เป็นอีก search engine provider หนึ่ง) ที่เขาได้พัฒนา Hadoop แบบ full-time จนท้ายที่สุด project นี้ก็ได้กลายเป็น Apache Hadoop ที่ผู้คนมากมายสามารถเข้ามาช่วย contribute ได้แล้ว

การทำงานของ MapReduce

MapReduce จะแบ่งเป็น 2 processing phase ซึ่งก็คือ Map กับ Reduce

ถ้าเล่าแบบสรุปคือ

user ระบุฟังก์ชัน map เพื่อที่จะนำ key/value pair มาสร้าง intermediate key/value pair แล้วใช้ฟังก์ชัน reduce ในการ merge ข้อมูลด้วย intermediate key/value นี้

เราลองมาดูแต่ละ phase แบบละเอียดๆกัน

Map Phase

เป็น phase แรกที่จะ apply ฟังก์ชันกับแต่ละคู่ key-value ภายในแต่ละชุดของ input dataset ซึ่ง input dataset จะแบ่งเป็น n blocks ซึ่งจะกลายเป็น n Map tasks (อีกชื่อคือ Mappers)

หากดูจากในรูป เรามี input datasets 3 blocks โดยแต่ละ block ก็จะถูกหั่นเป็น record ที่จะถูกรัน map() function (ตัว M) อีกจนได้ค่าคู่ key-value มา ที่เราเรียกว่า intermediate data

ถัดไปคือ Partitioning Function ที่จะเป็นคนช่วยให้แต่ละ key ถูก pass ไปยัง 1 Reducer

Map(k1,v1) → list(k2,v2)

Shuffle phase

phase นี้ทำหน้าที่กระจาย Map task มายัง Reduce task (Reducer) ผ่าน partitioning function ซึ่งขั้นตอนนี้ถือว่ากินพลังงานในการส่งข้อมูลข้าม node, network I/O, และ bandwidth

Note: ใน MapReduce จะเรียกว่า Shuffle Phase เฉยๆแต่หากเป็นพาร์ท MapReduce ใน Hadoop จะเรียกว่า Shuffle and Sort phase

Reduce Phase

ใน reduce phase ก็จะรัน reduce() กับ intermediate keys และ list ของ intermediate values ผลที่ได้ก็จะเป็นค่า O หรือ key value pairs เป็น final output ออกมา

Reduce(k2, list (v2)) → list((k3, v3))

ตัวอย่าง MapReduce: นับ M&M

สมมติสถานการณ์ว่าเรามี M&M จำนวนเยอะมากๆ และเราอยากนับจำนวนสี M&M ทั้งหมด 4 สี: แดง, นำ้เงิน, เขียว, น้ำตาล (จริงๆมีเยอะกว่านั้นแต่ขี้เกียจวาด)

ใน Map phase ก็จะมีเครื่องนับ M&M ซึ่งแต่ละเครื่องก็จะนับได้ intermediate output มาประมาณนี้

Red: 233
Blue: 2498
Green: 325
Brown: 975

จากนั้นก็จะถูก shuffle มายัง Reducer โดย Reducer ก็จะยุบ M&M แต่ละสี จนสุดท้ายก็ได้แค่รวมของแต่ละสีทั้งหมด

ตัวอย่าง MapReduce: นับคะแนนเสียงเลือกตั้ง

ลองจินตนาการ การเลือกตั้งโดยมีจุดโหวตคะแนนเสียงตามพื้นที่ต่างๆ โดยที่เราสามารถเข้าไปโหวตในพื้นที่ที่เราอาศัยอยู่ แต่ละจุดก็จะมีการนับคะแนนว่าผู้สมัครแต่ละคนได้รับคะแนนในพื้นที่นั้นเท่าไร (Mapper) แล้วก็จะถูกส่ง (shuffle) ไปยังพื้นที่กลางในการนับผลคะแนนรวม (Reducer) เพื่อนับว่าแต่ละผู้สมัครได้คะแนนจากทั่วประเทศเท่าไร