#22 MapReduce ที่มา การทำงาน และการเอาไปใช้

หลังจากที่เขียนเรื่องที่เกี่ยวกับ Data Structures & Algorithms ไปในบทความก่อนหน้าที่เขียนถึง Big-O Notation, Searching กับ Sorting Algorithms กับ Shortest Path อย่าง Dijkstra’s กับ Bellman-Ford’s Algorithm รวมถึง A* Search Algorithm

คราวนี้มาเข้าเรื่องที่เกี่ยวข้องกับ Data ที่เป็นพื้นฐานหนึ่งเลยคือ MapReduce

The English version is available here.

สาเหตุที่เขียนเรื่องนี้มาก็ไม่ใช่อะไร วันก่อนเราได้อ่านเปเปอร์หนึ่งที่มีชื่อว่า MapReduce: Simplified Data Processing on Large Clusters ที่เขียนโดยผู้พัฒนา Jeffrey Dean และ Sanjay Ghemawat ที่ทำงานอยู่ในบริษัท Google

เมื่ออ่านแล้ว เราก็สรุปรายละเอียดที่มา ขั้นตอนการประมวลผล และตัวอย่างในเปเปอร์นั้น ร่วมกับเสริมรายละเอียดอื่นในแง่การนำไปต่อยอด กับการนำไปใช้งานต่อ

ว่าแต่ก่อนอื่นเลย MapReduce มันคืออะไร?

สารบัญ

• MapReduce
• ขั้นตอนการทำงาน
• ตัวอย่าง
• การเอาไปใช้
• เพิ่มเติม
• สรุป
• ส่งท้าย
• แหล่งข้อมูลอ้างอิง

MapReduce

MapReduce [1] เป็นวิธีการเขียนโปรแกรมที่ใช้ในการประมวลผล และจัดการกับข้อมูลที่มีขนาดใหญ่ (หรือ Big Data) ที่มีปริมาณข้อมูลมหาศาล ซึ่งจำเป็นต้องใช้คลัสเตอร์ที่มีเซิร์ฟเวอร์จำนวนหลายร้อย หลายพันเครื่อง

ที่มาของการคิดค้น MapReduce ขึ้นมาก็มีที่มาจากทางบริษัท Google จำเป็นต้องประมวลผลข้อมูลดิบที่มีปริมาณข้อมูลมหาศาล ได้แก่ ข้อมูลเอกสารที่ผ่านการค้นหา กับข้อมูลการทำ Web Request เป็นต้น

โดยทั่วไป เราสามารถการประมวลผลข้อมูลเหล่านี้โดยการวนลูป หรือเขียนโปรแกรมทั่ว ๆ ไปได้เลย อย่างไรก็ดีข้อมูลที่เรามีอยู่ตอนนี้มันมีจำนวนมาก เราจำเป็นต้องใช้คอมพิวเตอร์ที่มีจำนวนมากเป็นหลักร้อย หรือหลักพันเครื่องเพื่อที่จะประมวลผลให้ได้ภายในระยะเวลาที่จำกัด

การประมวลผลแบบนี้ เราจำเป็นต้องพิจารณาตามด้านล่างนี้ ได้แก่

1. การประมวลผลแบบคู่ขนาน (Parallelize the computation)
2. การกระจายข้อมูล (Distribute the data)
3. การจัดการกับข้อผิดพลาดที่เกิดขึ้น (Handle failures)

จากข้อพิจารณาตามข้างบนเหล่านี้ ผู้พัฒนาได้ออกแบบเครื่องมือ MapReduce ที่ได้รับแรงบันดาลใจมาจากการทำ Map และ Reduce ที่ใช้ในการเขียนโปรแกรมภาษา Lisp และภาษาที่เป็น Functional Programming อื่น ๆ โดยแสดงตามภาพด้านล่างนี้ [2]

เมื่อได้รับแรงบันดาลใจจากที่มาการทำ Map และ Reduce ใน Lisp แล้ว ผู้วิจัยสังเกตว่าการประมวลผลข้อมูลส่วนใหญ่เราจะทำ

• Map operation ที่ประมวลผลในแต่ละข้อมูล (Record) เพื่อที่จะสร้างข้อมูลคู่อันดับ Key-Value ที่อยู่ระหว่างกลาง (หรือ Intermediate key/value pairs)
• Reduce operation ที่ประมวลผลข้อมูลระหว่างกลางทุกข้อมูลที่มี Key ที่เหมือนกันเพื่อที่จะรวมข้อมูลอย่างมีประสิทธิภาพ

ผู้วิจัยนำเทคนิคการประมวลผลนี้ไปใช้งาน ส่งผลให้ผู้พัฒนาสามารถเขียนโปรแกรมเพื่อประมวลผลข้อมูลแบบขนานได้ง่ายขึ้นมากกว่าเดิม และจัดการกับข้อผิดพลาดที่เกิดขึ้นได้อย่างมีประสิทธิภาพ

เลื่อนขึ้นไปข้างบนสุด ↑

---

ขั้นตอนการทำงาน

MapReduce นำชุดข้อมูลคู่อันดับ Key-Value มาประมวลผลเพื่อที่จะสร้างชุดข้อมูลผลลัพธ์ของคู่อันดับ Key-Value โดยผ่านการประมวลผลหลักทั้งหมด 2 ขั้นตอน ได้แก่ Map และ Reduce ที่เราแสดงตามภาพด้านล่างนี้

และเราสามารถสรุปขั้นตอนสำหรับการรันแบบคู่ขนานได้ตามด้านล่างนี้

Map

Map นำข้อมูลคู่อันดับ Key-Value ที่เป็น Input มาแบ่งข้อมูล (Partition) เพื่อให้ได้ข้อมูลที่มีขนาดเล็กลงประมาณ 16 ถึง 64 MB สำหรับการจะกระจายข้อมูลไปยังคอมพิวเตอร์ในแต่ละเครื่องในคลัสเตอร์

ข้อมูลที่ผ่านการแบ่งข้อมูลจะได้รับการประมวลผลในแต่ละข้อมูลด้วยฟังก์ชัน Map (M) ที่ผู้ใช้ได้เขียนขึ้น แล้วเราจะได้ผลลัพธ์ที่เป็นคู่อันดับ Key/Value ระหว่างกลาง (Intermediate key-value pairs)

เราสามารถสรุปขั้นตอน Map ได้ตามด้านล่างนี้

map (k1, v1) -> list(k2, v2)

โดย

• (k1, v1) คือคู่อันดับ Key-Value ที่เป็น Input
• (k2, v2) คือคู่อันดับ Key-Value ระหว่างกลาง (Intermediate key-value pairs)

ผลลัพธ์ที่ได้จะได้รับการบันทึกลงในไปดิสก์ (Local Disk)

Shuffle

Shuffle เป็นขั้นตอนที่อยู่ระหว่างขั้นตอน Map และ Reduce

ขั้นตอนนี้สำหรับการรันในคอมพิวเตอร์เครื่องเดียว เราจะนำผลลัพธ์ที่ได้ในขั้นตอนก่อนหน้าที่บันทึกไว้ใน Local Disk มาจัดกลุ่มโดยนำข้อมูลที่มี Key เดียวกันมาอยู่ด้วยกัน เพื่อที่จะที่จะรันอยู่ในฟังก์ชัน Reduce (R) เดียวกัน

ส่วนกรณีที่รันแบบคู่ขนาน (Parallel) เราจะแบ่งข้อมูลทั้งหมดเป็นส่วน ๆ (ทำ Partitioning) แล้วนำข้อมูลไปเรียงข้อมูล (Sort) และจัดกลุ่มข้อมูลให้ Key เดียวกันมาอยู่ด้วยกัน เพื่อที่จะรันอยู่ในฟังก์ชัน Reduce (R) เดียวกัน

ขั้นตอนนี้มีวัตถุประสงค์เพื่อที่จะลดปริมาณข้อมูลที่ส่งระหว่างคอมพิวเตอร์ผ่าน Network, Input/Output และ Bandwidth [3]

ขั้นตอนนี้สำหรับพาร์ท MapReduce ใน Hadoop เราจะเรียกว่า Shuffle and Sort phase

Reduce

Reduce เป็นขั้นตอนที่วนลูปเข้าไปในข้อมูลที่อยู่ระหว่างกลาง (Intermediate data) ที่ผ่านการทำ Shuffle เรียบร้อยแล้วมาประมวลผลโดยผ่านฟังก์ชัน Reduce (R) ที่ผู้ใช้ได้เขียนขึ้น เพื่อให้ได้ผลลัพธ์ออกมา

เราสามารถสรุปขั้นตอน Reduce ได้ตามด้านล่างนี้

reduce (k2, list(v2)) -> list(v2)

โดย

• (k2, list(v2)) คือคู่อันดับ Key-Value ระหว่างกลาง (Intermediate key-value pairs) ทีผ่านขั้นตอน Shuffle เรียบร้อยแล้ว
• list(v2) ผลลัพธ์ที่ได้

หลังจากการประมวลผลในขั้นตอน Map, Shuffle และ Reduce แล้ว เราจะได้ข้อมูลที่แบ่งเป็นส่วน ๆ ออกมา โดยไฟล์หนึ่งไฟล์ก็เป็นผลลัพธ์ตามฟังก์ชัน Reduce 1 ฟังก์ชัน

โดยทั่วไป ผู้พัฒนาไม่จำเป็นต้องรวมไฟล์ผลลัพธ์ให้เป็นไฟล์เดียว เราจะนำข้อมูลเหล่านั้นไปผ่านฟังก์ชัน MapReduce อีกฟังก์ชันหนึ่ง หรือนำไปใช้กับโปรแกรมประมวลผลแบบ Distributred Processing ที่รองรับการประมวลผลกับไฟล์ที่แบ่งเป็นส่วน ๆ

เลื่อนขึ้นไปข้างบนสุด ↑

---

ตัวอย่าง

เปเปอร์นี้ผู้วิจัยได้ยกตัวอย่างการใช้งานฟังก์ชัน MapReduce สำหรับการนำจำนวนคำที่ปรากฏในไฟล์เอกสาร โดยผู้วิจัยเขียน Pseudocode ได้ตามด้านล่างนี้

map(String key, String value):
    // key: document name
    // value: document contents for each word w in value:
    EmitIntermediate(w, "1");
    
reduce(String key, Iterator values):
    // key: a word
    // values: a list of counts
    int result = 0;
    for each v in values:
        result += ParseInt(v);
    Emit(AsString(result));

โดยฟังก์ชัน

• Map ให้ผลลัพธ์ Intermediate Data ที่เป็นคำแต่ละคำ กับจำนวนคำที่ปรากฏในเอกสาร (ตัวอย่างใน Psuedocode กำหนดให้เท่ากับ 1)
• Reduce รวมผลลัพธ์จำนวนคำที่นับได้ในแต่ละคำที่กระจายไปในแต่ละโหนด

การเขียนโค้ด เราสามารถเขียนโค้ดด้วยภาษาได้หลายภาษา ได้แก่ ภาษา Java, C++ และ Python

จากการใช้งานฟังก์ชันข้างบนนี้ เราสามารถเปรียบเทียบได้กับการทำสำมะโนครัวที่ทำในสมัยอาณาจักรโรมันที่ส่งคนไปแต่ละเมือง เพื่อที่จะนับจำนวนคนทุกคน แล้วจะส่งผลลัพธ์ที่ได้ไปยังเมืองหลวง

ผลลัพธ์ที่ได้จะเป็นจำนวนประชากรในอาณาจักรนั้น ๆ

การประมวลผลแบบคู่ขนานนี้ทำให้การนับจำนวนประชากรทำได้อย่างรวดเร็วขึ้นมากกว่าการใช้คนเดียวนับจำนวนประชากรไปทีละเมือง [4]

เลื่อนขึ้นไปข้างบนสุด ↑

---

การเอาไปใช้

MapReduce ได้รับนำไปใช้พัฒนาต่อยอดโดยผู้พัฒนาที่มีชื่อว่า Dug Cutting และ Mike Cafarella ที่ทำงานอยู่ในบริษัท Yahoo โดยได้เป็นเครื่องมือภายใต้โครงการของ Apache ที่มีชื่อว่า Apache Hadoop [5]

Apache Hadoop เป็นเครื่องมือสำหรับการจัดการ และประมวลผลกับข้อมูลที่มีขนาดใหญ่ด้วยการกระจายไปยังเครื่องคอมพิวเตอร์ส่วนบุคคลทั่วไปได้ที่เชื่อมต่อกันเป็นคลัสเตอร์

โดยเครื่องมือการประมวลผลแบบ Map และ Reduce อยู่ภายใต้เครื่องมือ Hadoop MapReduce อีกทีนึง

เครื่องมือนี้ตอนออกใหม่ ๆ ก็เป็นจุดเริ่มต้นของการประมวลผลข้อมูลที่มีขนาดใหญ่ที่ใช้งานในหลายบริษัท อย่างไรก็ดี เครื่องมือนี้มีข้อเสีย [6, 7] อยู่หลายจุด ได้แก่

• ประมวลผลได้จำกัด โดยตัวโหนดสำหรับการประมวลผล MapReduce ทำงานได้เพียง 1 Input ต่อครั้ง ในกรณีที่มีข้อมูลขนาดใหญ่ การประมวลผลทำได้ช้ามากจนงานไม่เสร็จ
• ประมวลผลได้ช้า โดย MapReduce ไม่รองรับการ Cache ข้อมูล เครื่องมือนี้จำเป็นต้องใช้ Harddisk ที่เป็น HDFS (Hadoop Distributed File System) ในการอ่าน และเขียนข้อมูลทุกขั้นตอน ส่งผลให้ทำงานได้ช้ากว่าเครื่องมือประมวลผลข้อมูลที่มีขนาดใหญ่อื่น ๆ โดยช้ากว่า Apache Spark เมื่อประมวลผลแบบ Batch เหมือนกัน เนื่องมาจาก Apache Spark ที่รองรับการทำ Cache และประมวลผลในหน่วยความจำ
• ไม่รองรับการประมวลผลแบบ Real-time Data Processing
• ใช้งานยาก และเขียนโปรแกรมได้ยาก โดยทั่วไป เราจะใช้ SQL สำหรับการวิเคราะห์ข้อมูล แต่ตัว Hadoop มันไม่รองรับ ผู้พัฒนาจำเป็นต้องเขียนด้วย Java เท่านั้น

จากข้อเสียข้างบนเหล่านี้ส่งผลให้เกิดการพัฒนาเครื่องมืออย่าง Apache Spark กับ Apache Flink ที่รองรับการประมวลผลข้อมูลแบบ Steam และ Batch อย่างรวดเร็วเนื่องมาจากการประมวลผลในหน่วยความจำ ส่งผลให้หลายบริษัทเปลี่ยนเครื่องมือมาใช้ Apache Spark และ Apache Flink แทน

อย่างไรก็ดี เครื่องมือเหล่านี้ก็ยังใช้งานที่เก็บข้อมูลแบบ HDFS ที่อยู่เบื้องหลังอยู่ดี

เลื่อนขึ้นไปข้างบนสุด ↑

เพิ่มเติม

สำหรับ Apache Spark อันนี้เราได้เขียนบทความอธิบายไว้ในบทความก่อนหน้าที่ทำโปรเจคสำหรับการดึงข้อมูลต้นทุนการผลิตนักศึกษาต่อปีครับ

ผู้อ่านสามารถคลิกได้ที่ด้านล่างนี้

#13 ทำ Data Pipeline ดึง Data ต้นทุนนศ.ต่อปี

See more

---

สรุป

MapReduce เป็นวิธีการเขียนโปรแกรมที่ใช้ในการประมวลผล และจัดการกับ Big Data ที่จำเป็นต้องใช้คลัสเตอร์ที่มีเซิร์ฟเวอร์จำนวนหลายร้อย หลายพันเครื่อง โดยเครื่องมือนี้ทำให้ผู้พัฒนาสามารถเขียนโปรแกรมเพื่อประมวลผลข้อมูลแบบขนานได้ง่ายขึ้นมากกว่าเดิม และจัดการกับข้อผิดพลาดที่เกิดขึ้นได้อย่างมีประสิทธิภาพ

เครื่องมือนี้ได้รับการพัฒนาต่อยอดไปใช้งานใน Apache Hadoop ที่เป็นจุดเริ่มต้นของการประมวลผล Big Data อย่างไรก็ดี เครื่องมือนี้มีข้อเสียด้านการประมวลผลที่ช้า กับไม่รองรับการรันข้อมูลแบบ Stream Data Processing และใช้งานยาก ส่งผลให้เกิดการพัฒนาเครื่องมือ Apache Spark และ Apache Flink ที่ได้รับความนิยมมากกว่า

เลื่อนขึ้นไปข้างบนสุด ↑

---

ส่งท้าย

สำหรับผู้อ่านที่เห็นว่าบทความนี้ดี มีประโยชน์ ให้กดไลค์ หรือกดแชร์ไปยังแพลตฟอร์มโซเชียลต่าง ๆ นอกจากนี้ ผู้อ่านยังติดตามได้่ใน Linkedin หรือ X (หรือ Twitter) ได้ครับ

---

ข้อมูลอ้างอิง

1. MapReduce: Simplified Data Processing on Large Clusters
2. MapReduce: The programming model and practice – Google Research
3. MAPREDUCE คืออะไร เข้าใจที่มา HADOOP และในด้าน DISTRIBUTED COMPUTING – Burasakorn Sabyeying (Mils)
4. What is Apache MapReduce? – IBM
5. Hadoop MapReduce deep diving and tuning – Today Software Magazine
6. The Good and the Bad of Hadoop Big Data Framework
7. Road to Data Engineer 2.0 – DataTH School

เลื่อนขึ้นไปข้างบนสุด ↑