MapReduce


MapReduce

MapReduce เป็น framework ในการเขียนโปรแกรมแบบหนึ่งที่ช่วยในงานประมวลผลที่มี data set จำนวนมาก หลักการทำงานจะเป็นการทำงานแบบ parallel ซึ่งจะอาศัยเครื่องคอมพิวเตอร์หลายๆเครื่องช่วยกันทำงาน โดยที่ผู้ใช้งานนั้นไม่ต้องสนใจเบื้องหลังการทำงานเช่น parallelization, data distribution, loads balancing และ fault tolerance ในการทำงานแล้วผู้ใช้งาน MapReduce จะสนใจแค่ส่วนของ Map และส่วนของ Reduce ซึ่ง Map จะทำการจับคู่ของ Key/Value ที่เราต้องการ  แล้วก็จะส่งไปให้ Reduce ทำการประมวลผลเพื่อให้ได้ผลลัพธ์ที่ต้องการ

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));

จากตัวอย่างโปรแกรมจะเป็นการนับจำนวนของตัวอักษร ‘W’ โดย Map จะจับคู่ Key/Value เป็น W/1 แล้วส่งไปยัง Reduce ทำการบวก value ของ W ตามที่ Map ส่งมา

หลักการทำงาน

หลักการทำงานของ MapReduce คือจะกระจายงานต่างๆไปให้ Map-Worker ที่อยุ่บนแต่ละเครื่องทำงาน ซึ่งผู้ที่ควบคุมการกระจายงานก็คือ Master โดยหลังจากที่ worker ทำงานเสร็จแล้วก้จะแจ้งให้ Master เพื่อที่ Master จะส่งต่อผลของการ Map ให้กับ Reduce-Worker เพื่อทำงานให้ได้ผลลัพธ์ต่อไป

ขั้นตอนโดยละเอียดจะอธิบายจากรูปด้านล่าง

 

จากรูปภาพ อธิบายหลักการทำงานได้ดังนี้

  1. เริ่มจากการ Map เมื่อมีการใช้งานตัว library จะแบ่งไฟล์ที่เป็นอินพุตเป็นส่วนย่อยๆประมาณ 16 MB ถึง 64 MB
  2.  Master จะดูว่ามี worker ตัวไหนว่างอยู่บ้างก็จะ assign task ให้ซึ่งก็จะมีทั้ง map และ reduce task
  3. สำหรับ worker ที่ถูก assign map task ก็จะอ่านข้อมูลจากอินพุตไฟล์ที่ถูกแบ่งแล้ว Map key/value ตามที่ผู้ใช้งานเขียนไว้
  4. ผลของการ Map จะถูกเก็บไว้ที่เครื่องที่ทำการ Map ซึ่งจะมีการแบ่งเป็นส่วนๆตาม key ที่กำหนด โดย Partitioning function ของ MapReduce library และจะมีการส่งข้อความไปยัง master เพื่อให้ master ส่งงานให้ reduce worker ต่อไป
  5. เมื่อ reduce worker ได้รับข้อความจาก master ก็จะทำอ่านไฟล์จากตำแหน่งที่ master ให้มาแล้วทำการจัดเรียงข้อมูลตาม key
  6. เมื่อเรียงข้อมูลตาม key เสร็จแล้วก็จะทำตาม reduce function ตามที่ผู้ใช้งานกำหนดไว้ โดย output ที่ออกมาจะขึ้นอยู่กับจำนวนของ reduce worker แล้วสุดท้ายก็จะมีการรวมไฟล์ output เป็นไฟล์เดียว
  7. เมื่อ MapReduce เสร็จแล้วก็จะแจ้งให้ master รู้ เพื่อแจ้งต่อไปยังโปรแกรมว่าทำ MapReduce เสร็จแล้ว

การจัดการด้าน Fault Tolerance

MapReduce จะมีการทำสำนำของข้อมูลไปยังเครื่องอื่นๆที่อยู่ใกล้เคียงในขั้นตอนการแบ่งไฟล์ ซึ่งทำให้เมื่อมี map worker บางตัวที่ไม่ทำงาน ตัวอื่นก็สามารถทำงานแทนได้ โดยการตรวจสอบว่า map worker ยังทำงานอยู่หรือไม่จะทำโดย master ที่ ping ไปให้ worker ตามช่วงเวลาที่กำหนด เพื่อ worker ไม่สนองภายในช่วงเวลาที่กำหนด master จะ assign task ที่เคยให้กับ worker ตัวที่ไม่ทำงานไปให้ตัวอื่นทำงานแทนไม่ว่า worker ตัวนั้นจะทำ Map เท่าไรก็ตาม เนื่องจากผลของการ Map นั้นเก็บอยู่ใน local disk ซึ่งทำให้ไม่สามารถเข้าถึงไฟล์ที่ Map เสร็จไม่ได้แล้วหาก worker ไม่ทำงาน ยกเว้นในกรณีของการเก็บไฟล์ที่ Map เสร็จไว้บนระบบเครือข่ายก็จะทำให้ไม่ต้อง assign task ที่ทำงานเสร็จแล้วให้กับ worker ตัวอื่น

เรียบเรียงจาก
Introduction to Parallel Programming and MapReduce
http://code.google.com/intl/th/edu/parallel/mapreduce-tutorial.html

A Very Brief Introduction to MapReduce
http://hci.stanford.edu/courses/cs448g/a2/files/map_reduce_tutorial.pdf

Simplified Data Processing on Large Clusters
http://research.google.com/archive/mapreduce.html

Map Reduce: A really simple introduction
http://ksat.me/map-reduce-a-really-simple-introduction-kloudo/

ติดป้ายกำกับ:

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s

%d bloggers like this: