หลังจากที่เขียนเรื่องที่เกี่ยวกับ 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 [1] เป็นวิธีการเขียนโปรแกรมที่ใช้ในการประมวลผล และจัดการกับข้อมูลที่มีขนาดใหญ่ (หรือ Big Data) ที่มีปริมาณข้อมูลมหาศาล ซึ่งจำเป็นต้องใช้คลัสเตอร์ที่มีเซิร์ฟเวอร์จำนวนหลายร้อย หลายพันเครื่อง
ที่มาของการคิดค้น MapReduce ขึ้นมาก็มีที่มาจากทางบริษัท Google จำเป็นต้องประมวลผลข้อมูลดิบที่มีปริมาณข้อมูลมหาศาล ได้แก่ ข้อมูลเอกสารที่ผ่านการค้นหา กับข้อมูลการทำ Web Request เป็นต้น
โดยทั่วไป เราสามารถการประมวลผลข้อมูลเหล่านี้โดยการวนลูป หรือเขียนโปรแกรมทั่ว ๆ ไปได้เลย อย่างไรก็ดีข้อมูลที่เรามีอยู่ตอนนี้มันมีจำนวนมาก เราจำเป็นต้องใช้คอมพิวเตอร์ที่มีจำนวนมากเป็นหลักร้อย หรือหลักพันเครื่องเพื่อที่จะประมวลผลให้ได้ภายในระยะเวลาที่จำกัด
การประมวลผลแบบนี้ เราจำเป็นต้องพิจารณาตามด้านล่างนี้ ได้แก่
- การประมวลผลแบบคู่ขนาน (Parallelize the computation)
- การกระจายข้อมูล (Distribute the data)
- การจัดการกับข้อผิดพลาดที่เกิดขึ้น (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 อันนี้เราได้เขียนบทความอธิบายไว้ในบทความก่อนหน้าที่ทำโปรเจคสำหรับการดึงข้อมูลต้นทุนการผลิตนักศึกษาต่อปีครับ
ผู้อ่านสามารถคลิกได้ที่ด้านล่างนี้
สรุป
MapReduce เป็นวิธีการเขียนโปรแกรมที่ใช้ในการประมวลผล และจัดการกับ Big Data ที่จำเป็นต้องใช้คลัสเตอร์ที่มีเซิร์ฟเวอร์จำนวนหลายร้อย หลายพันเครื่อง โดยเครื่องมือนี้ทำให้ผู้พัฒนาสามารถเขียนโปรแกรมเพื่อประมวลผลข้อมูลแบบขนานได้ง่ายขึ้นมากกว่าเดิม และจัดการกับข้อผิดพลาดที่เกิดขึ้นได้อย่างมีประสิทธิภาพ
เครื่องมือนี้ได้รับการพัฒนาต่อยอดไปใช้งานใน Apache Hadoop ที่เป็นจุดเริ่มต้นของการประมวลผล Big Data อย่างไรก็ดี เครื่องมือนี้มีข้อเสียด้านการประมวลผลที่ช้า กับไม่รองรับการรันข้อมูลแบบ Stream Data Processing และใช้งานยาก ส่งผลให้เกิดการพัฒนาเครื่องมือ Apache Spark และ Apache Flink ที่ได้รับความนิยมมากกว่า
ส่งท้าย
สำหรับผู้อ่านที่เห็นว่าบทความนี้ดี มีประโยชน์ ให้กดไลค์ หรือกดแชร์ไปยังแพลตฟอร์มโซเชียลต่าง ๆ นอกจากนี้ ผู้อ่านยังติดตามได้่ใน Linkedin หรือ X (หรือ Twitter) ได้ครับ
ข้อมูลอ้างอิง
- MapReduce: Simplified Data Processing on Large Clusters
- MapReduce: The programming model and practice – Google Research
- MAPREDUCE คืออะไร เข้าใจที่มา HADOOP และในด้าน DISTRIBUTED COMPUTING – Burasakorn Sabyeying (Mils)
- What is Apache MapReduce? – IBM
- Hadoop MapReduce deep diving and tuning – Today Software Magazine
- The Good and the Bad of Hadoop Big Data Framework
- Road to Data Engineer 2.0 – DataTH School