MapReduceเป็นแบบจำลองการเขียนโปรแกรมและการใช้งานที่เกี่ยวข้องสำหรับการประมวลผลและการสร้างชุดข้อมูลขนาดใหญ่ด้วย อัลกอริทึม แบบขนานและ แบบ กระจายบนคลัสเตอร์^{[ 1 ] [ 2 ] [ 3 ]}

โปรแกรม MapReduce ประกอบด้วยขั้นตอนการทำงานแบบ map ซึ่งทำหน้าที่กรองและจัดเรียงข้อมูล (เช่น การจัดเรียงนักเรียนตามชื่อจริงลงในคิว โดยแต่ละคิวแทนชื่อหนึ่งชื่อ) และ ขั้นตอนการทำงานแบบ reduceซึ่งทำหน้าที่สรุปผล (เช่น การนับจำนวนนักเรียนในแต่ละคิว ซึ่งจะได้ความถี่ของชื่อ) "ระบบ MapReduce" (หรือเรียกว่า "โครงสร้างพื้นฐาน" หรือ "เฟรมเวิร์ก") จะจัดการกระบวนการประมวลผลโดยการเชื่อมโยงเซิร์ฟเวอร์แบบกระจายเข้าด้วยกัน ดำเนินการต่างๆ แบบขนาน จัดการการสื่อสารและการถ่ายโอนข้อมูลระหว่างส่วนต่างๆ ของระบบ และจัดให้มีระบบสำรองและทน ต่อความผิดพลาด

โมเดลนี้เป็นความเชี่ยวชาญเฉพาะด้านของ กลยุทธ์ การแบ่ง-ประยุกต์-รวมสำหรับการวิเคราะห์ข้อมูล^{[ 4 ]} โดยได้รับแรงบันดาลใจจาก ฟังก์ชัน mapและreduceที่ใช้กันทั่วไปในการเขียนโปรแกรมเชิงฟังก์ชัน^{[ 5 ]}แม้ว่าวัตถุประสงค์ของฟังก์ชันเหล่านี้ในเฟรมเวิร์ก MapReduce จะไม่เหมือนกับรูปแบบดั้งเดิมก็ตาม^{[ 6 ]} ส่วนสำคัญของเฟรมเวิร์ กMapReduce ไม่ใช่ฟังก์ชัน map และ reduce จริงๆ (ซึ่งตัวอย่างเช่น คล้ายกับ การดำเนินการ reduce ^{[ 8 ]}และscatter ^{[ 9 ]}ของมาตรฐานMessage Passing Interface ปี 1995 ^{[ 7 ]} ) แต่เป็นความสามารถในการปรับขนาดและความทนทานต่อข้อผิดพลาดที่เกิดขึ้นกับแอปพลิเคชันต่างๆ เนื่องจากการทำงานแบบขนาน ดังนั้น การใช้งาน MapReduce แบบเธรดเดียวจึงมักจะไม่เร็วกว่าการใช้งานแบบดั้งเดิม (ที่ไม่ใช่ MapReduce) ข้อดีใดๆ มักจะเห็นได้เฉพาะกับ การใช้งาน แบบมัลติเธรดบนฮาร์ดแวร์มัลติโปรเซสเซอร์ เท่านั้น ^{[ 10 ]}การใช้โมเดลนี้จะมีประโยชน์ก็ต่อเมื่อการดำเนินการ shuffle แบบกระจายที่ได้รับการปรับให้เหมาะสม (ซึ่งช่วยลดต้นทุนการสื่อสารเครือข่าย) และคุณสมบัติความทนทานต่อข้อผิดพลาดของเฟรมเวิร์ก MapReduce เข้ามามีบทบาท การเพิ่มประสิทธิภาพต้นทุนการสื่อสารเป็นสิ่งสำคัญสำหรับอัลกอริทึม MapReduce ที่ดี^{[ 11 ]}

ไลบรารี MapReduce ถูกเขียนขึ้นในภาษาโปรแกรมหลายภาษา โดยมีระดับการเพิ่มประสิทธิภาพที่แตกต่างกัน การใช้งาน แบบโอเพนซอร์ส ที่เป็นที่นิยม ซึ่งรองรับการสับเปลี่ยนแบบกระจายเป็นส่วนหนึ่งของApache Hadoopชื่อ MapReduce เดิมทีหมายถึงเทคโนโลยีที่เป็นกรรมสิทธิ์ของ Googleแต่ต่อมาได้กลายเป็นเครื่องหมายการค้าทั่วไปในปี 2014 Google ไม่ได้ใช้ MapReduce เป็นโมเดลการประมวลผลข้อมูลขนาดใหญ่ หลักอีกต่อไป ^{[ 12 ]}และการพัฒนาApache Mahoutได้เปลี่ยนไปสู่กลไกที่มีประสิทธิภาพมากขึ้นและเน้นดิสก์น้อยลง ซึ่งรวมเอาความสามารถในการแมปและลดแบบเต็มรูปแบบไว้ด้วย^{[ 13 ]}

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

เฟรมเวิร์ก (หรือระบบ) MapReduce โดยทั่วไปประกอบด้วยการดำเนินการ (หรือขั้นตอน) สามขั้นตอน:

1. แผนผัง:โหนดผู้ปฏิบัติงานแต่ละโหนดจะนำmapฟังก์ชันไปใช้กับข้อมูลในเครื่อง และเขียนผลลัพธ์ลงในที่จัดเก็บชั่วคราว โหนดหลักจะตรวจสอบให้แน่ใจว่ามีการประมวลผลข้อมูลอินพุตที่ซ้ำซ้อนเพียงชุดเดียวเท่านั้น
2. การสับเปลี่ยน:โหนดผู้ปฏิบัติงานจะกระจายข้อมูลใหม่โดยอิงจากคีย์เอาต์พุต (ที่สร้างโดยmapฟังก์ชัน) เพื่อให้ข้อมูลทั้งหมดที่อยู่ในคีย์เดียวกันอยู่บนโหนดผู้ปฏิบัติงานเดียวกัน
3. Reduce:ตอนนี้โหนดทำงานจะประมวลผลข้อมูลเอาต์พุตแต่ละกลุ่มตามคีย์แบบขนาน

MapReduce ช่วยให้สามารถประมวลผลแบบกระจายสำหรับขั้นตอนการแมปและการลดข้อมูลได้ การแมปสามารถทำได้แบบขนาน โดยมีเงื่อนไขว่าการดำเนินการแมปแต่ละครั้งต้องเป็นอิสระจากกัน ในทางปฏิบัติ สิ่งนี้มีข้อจำกัดโดยจำนวนแหล่งข้อมูลอิสระและ/หรือจำนวน CPU ที่อยู่ใกล้กับแต่ละแหล่งข้อมูล ในทำนองเดียวกัน ชุดของ 'ตัวลดข้อมูล' สามารถดำเนินการในขั้นตอนการลดข้อมูลได้ โดยมีเงื่อนไขว่าเอาต์พุตทั้งหมดของการดำเนินการแมปที่มีคีย์เดียวกันจะต้องถูกส่งไปยังตัวลดข้อมูลเดียวกันในเวลาเดียวกัน หรือฟังก์ชันการลดข้อมูลเป็นแบบเชื่อมโยงได้แม้ว่ากระบวนการนี้มักจะดูไม่มีประสิทธิภาพเมื่อเทียบกับอัลกอริทึมที่ทำงานแบบลำดับ (เนื่องจากต้องเรียกใช้กระบวนการลดข้อมูลหลายครั้ง) แต่ MapReduce สามารถนำไปใช้กับชุดข้อมูลขนาดใหญ่กว่าที่เซิร์ฟเวอร์ "ทั่วไป" เครื่องเดียวจะจัดการได้ – ฟาร์มเซิร์ฟเวอร์ขนาดใหญ่สามารถใช้ MapReduce เพื่อจัดเรียง ข้อมูล ขนาดเพตาไบต์ได้ในเวลาเพียงไม่กี่ชั่วโมง^{[ 14 ]}การทำงานแบบขนานยังเปิดโอกาสให้สามารถกู้คืนจากความล้มเหลวบางส่วนของเซิร์ฟเวอร์หรือที่เก็บข้อมูลระหว่างการดำเนินการได้ หากแมปเปอร์หรือรีดิวเซอร์ตัวใดตัวหนึ่งล้มเหลว งานสามารถกำหนดเวลาใหม่ได้ โดยสมมติว่าข้อมูลอินพุตยังคงใช้งานได้

อีกวิธีหนึ่งในการมอง MapReduce คือ มองว่าเป็นกระบวนการคำนวณแบบขนานและกระจาย 5 ขั้นตอน:

1. เตรียมข้อมูลป้อนเข้าสำหรับฟังก์ชัน Map() – ระบบ MapReduce จะกำหนดตัวประมวลผล Map กำหนดคีย์ข้อมูลป้อนเข้าK1ที่ตัวประมวลผลแต่ละตัวจะทำงานด้วย และส่งข้อมูลป้อนเข้าทั้งหมดที่เกี่ยวข้องกับคีย์นั้นให้กับตัวประมวลผลดังกล่าว
2. เรียกใช้โค้ด Map() ที่ผู้ใช้ป้อน –ฟังก์ชันMap() จะทำงานเพียงครั้งเดียวสำหรับแต่ละ คีย์ K1โดยสร้างเอาต์พุตที่จัดเรียงตามคีย์K2
3. "สับเปลี่ยน" ผลลัพธ์จาก Map ไปยังโปรเซสเซอร์ Reduce – ระบบ MapReduce จะกำหนดโปรเซสเซอร์ Reduce กำหนด คีย์ K2ที่แต่ละโปรเซสเซอร์ควรทำงานด้วย และส่งข้อมูลทั้งหมดที่สร้างจาก Map ซึ่งเกี่ยวข้องกับคีย์นั้นไปยังโปรเซสเซอร์ดังกล่าว
4. เรียกใช้โค้ด Reduce() ที่ผู้ใช้กำหนด –ฟังก์ชัน Reduce() จะถูกเรียกใช้เพียงครั้งเดียวสำหรับแต่ละ คีย์ K2ที่สร้างขึ้นโดยขั้นตอน Map
5. สร้างผลลัพธ์สุดท้าย – ระบบ MapReduce จะรวบรวมผลลัพธ์ทั้งหมดจาก Reduce และจัดเรียงตามK2เพื่อสร้างผลลัพธ์สุดท้าย

ขั้นตอนทั้งห้าเหล่านี้สามารถมองได้อย่างมีเหตุผลว่าดำเนินไปตามลำดับ – แต่ละขั้นตอนจะเริ่มต้นก็ต่อเมื่อขั้นตอนก่อนหน้าเสร็จสมบูรณ์แล้ว – แม้ว่าในทางปฏิบัติแล้ว ขั้นตอนต่างๆ สามารถสลับกันได้ตราบใดที่ผลลัพธ์สุดท้ายไม่ได้รับผลกระทบ

ในหลายสถานการณ์ ข้อมูลอินพุตอาจถูกกระจาย ( "แบ่งส่วน" ) ไปยังเซิร์ฟเวอร์ต่างๆ มากมายแล้ว ซึ่งในกรณีนี้ ขั้นตอนที่ 1 อาจง่ายขึ้นอย่างมากโดยการกำหนดเซิร์ฟเวอร์ Map ที่ประมวลผลข้อมูลอินพุตที่มีอยู่บนเครื่องนั้นๆ ในทำนองเดียวกัน ขั้นตอนที่ 3 อาจเร็วขึ้นได้โดยการกำหนดโปรเซสเซอร์ Reduce ที่อยู่ใกล้กับข้อมูลที่สร้างโดย Map มากที่สุดเท่าที่จะเป็นไปได้

ฟังก์ชัน Map และReduceของMapReduceต่างก็ถูกกำหนดขึ้นโดยอ้างอิงจากโครงสร้างข้อมูลในรูปแบบคู่ (คีย์, ค่า) ฟังก์ชันMapรับข้อมูลคู่หนึ่งที่มีประเภทอยู่ในโดเมนข้อมูล หนึ่ง และส่งคืนรายการคู่ข้อมูลในโดเมนที่แตกต่างกัน:

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

ฟังก์ชัน Mapจะถูกนำไปใช้แบบขนานกับทุกคู่ (ที่มีคีย์เป็นk1) ในชุดข้อมูลอินพุต ซึ่งจะสร้างรายการคู่ (ที่มีคีย์เป็นk2) สำหรับการเรียกใช้แต่ละครั้ง หลังจากนั้น เฟรมเวิร์ก MapReduce จะรวบรวมคู่ทั้งหมดที่มีคีย์เดียวกัน ( k2) จากทุกรายการและจัดกลุ่มเข้าด้วยกัน โดยสร้างกลุ่มหนึ่งกลุ่มสำหรับแต่ละคีย์

จากนั้นจึงนำ ฟังก์ชันReduceมาใช้แบบขนานกับแต่ละกลุ่ม ซึ่งจะทำให้ได้ชุดค่าต่างๆ ที่อยู่ในโดเมนเดียวกัน:

Reduce(k2, list (v2))→ list((k3, v3))^{[ 15 ]}

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

ดังนั้นเฟรมเวิร์ก MapReduce จึงแปลงรายการคู่ (คีย์, ค่า) เป็นรายการคู่ (คีย์, ค่า) อีกรายการหนึ่ง^{[ 16 ]}พฤติกรรมนี้แตกต่างจากการรวมกันของ map และ reduce ในการเขียนโปรแกรมเชิงฟังก์ชันทั่วไป ซึ่งรับรายการค่าแบบสุ่มและส่งคืนค่าเดียวที่รวมค่า ทั้งหมด ที่ส่งคืนโดย map

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

ตัวอย่าง MapReduce แบบดั้งเดิมจะนับจำนวนการปรากฏของแต่ละคำในชุดเอกสาร: ^{[ 17 ]}

ฟังก์ชันmap (String name, String document): // name: ชื่อเอกสาร// document: เนื้อหาของเอกสารสำหรับแต่ละคำ w ในเอกสาร: ปล่อย (w, 1) ฟังก์ชันreduce (String word, Iterator partialCounts): // word: คำ// partialCounts: รายการนับย่อยที่รวมกันแล้ว ผลรวม = 0 สำหรับแต่ละพีซีใน partialCounts: ผลรวม += พีซี ปล่อย (คำ, ผลรวม) 

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

ยกตัวอย่างอีกกรณีหนึ่ง สมมติว่าในฐานข้อมูลที่มีประชากร 1.1 พันล้านคน เราต้องการคำนวณจำนวนการติดต่อทางสังคมโดยเฉลี่ยของแต่ละบุคคลตามช่วงอายุ ในSQLสามารถแสดงคำสั่งค้นหาดังกล่าวได้ดังนี้:

เลือกอายุ, ค่าเฉลี่ย( ราย ชื่อติดต่อ) จากโซเชียลบุคคลจัดกลุ่มตามอายุเรียงลำดับตามอายุ

เมื่อใช้ MapReduce ค่าคีย์ K1อาจเป็นจำนวนเต็ม 1 ถึง 1100 ซึ่งแต่ละค่าแทนชุดข้อมูล 1 ล้านรายการ ค่าคีย์ K2อาจเป็นอายุของบุคคลในหน่วยปี และการคำนวณนี้สามารถทำได้โดยใช้ฟังก์ชันต่อไปนี้:

ฟังก์ชัน Map รับอินพุตเป็นจำนวนเต็ม K1 ระหว่าง 1 ถึง 1100 ซึ่งแทนชุดข้อมูล social.person จำนวน 1 ล้านรายการ สำหรับแต่ละข้อมูล social.person ในชุดข้อมูล K1 ให้ Y เป็นอายุของบุคคลนั้น และNเป็นจำนวนผู้ติดต่อที่บุคคลนั้นมี สร้างเอาต์พุตเป็นระเบียน (Y, (N, 1)) ทำ ซ้ำจนครบฟังก์ชันฟังก์ชัน Reduce รับอินพุต:อายุ (เป็นปี) Y สำหรับแต่ละระเบียนอินพุต (Y, (N, C)) ให้ทำซ้ำ สะสมผลรวมของ N*C ใน Sสะสม ผลรวมของ C ใหม่ลง ใน C ทำซ้ำให้ A เป็น S/C ใหม่สร้างเอาต์พุตหนึ่งรายการ บันทึก (Y,(A,C ใหม่ )) จบฟังก์ชัน

โปรดทราบว่าในฟังก์ชันReduce นั้น Cคือจำนวนคนทั้งหมดที่มีผู้ติดต่อ N ราย ดังนั้นใน ฟังก์ชัน Mapจึงเป็นเรื่องปกติที่จะเขียนC=1เนื่องจากคู่ผลลัพธ์แต่ละคู่หมายถึงผู้ติดต่อของบุคคลเพียงคนเดียว

ระบบ MapReduce จะเรียงลำดับตัวประมวลผล Map จำนวน 1100 ตัว และป้อนข้อมูล 1 ล้านรายการให้กับแต่ละตัว ขั้นตอน Map จะสร้าง ข้อมูล (Y,(N,1)) จำนวน 1.1 พันล้าน รายการ โดย ค่า Yจะอยู่ระหว่าง 8 ถึง 103 จากนั้นระบบ MapReduce จะเรียงลำดับตัวประมวลผล Reduce จำนวน 96 ตัว โดยทำการสลับคู่คีย์/ค่า เนื่องจากเราต้องการค่าเฉลี่ยตามอายุ และป้อนข้อมูลหลายล้านรายการให้กับแต่ละตัว ขั้นตอน Reduce จะสร้างชุดข้อมูลเอาต์พุต(Y,A) ที่ลดลงเหลือเพียง 96 รายการ ซึ่งจะถูกจัดเก็บไว้ในไฟล์ผลลัพธ์สุดท้าย โดยเรียงลำดับตามค่า Y

ข้อมูลจำนวนในบันทึกมีความสำคัญหากมีการลดการประมวลผลมากกว่าหนึ่งครั้ง หากเราไม่เพิ่มจำนวนบันทึก ค่าเฉลี่ยที่คำนวณได้ก็จะผิดพลาด ตัวอย่างเช่น:

-- ผลลัพธ์แผนที่ #1: อายุ, จำนวนผู้ติดต่อ 10, 9 10, 9 10, 9 

-- ผลลัพธ์แผนที่ #2: อายุ, จำนวนผู้ติดต่อ 10, 9 10, 9 

-- ผลลัพธ์แผนที่ #3: อายุ, จำนวนผู้ติดต่อ 10, 10 

ถ้าเราลดจำนวนไฟล์#1และ#2ลง เราจะได้ไฟล์ใหม่ที่มีจำนวนผู้ติดต่อเฉลี่ย 9 รายต่อเด็กอายุ 10 ปี ((9+9+9+9+9)/5):

-- ลดขั้นตอนที่ 1: อายุ ค่าเฉลี่ยของจำนวนการติดต่อ 10, 9 

ถ้าเราลดจำนวนลงด้วยไฟล์#3เราจะสูญเสียจำนวนบันทึกที่เราเคยเห็นไปแล้ว ดังนั้นเราจะได้ค่าเฉลี่ย 9.5 รายชื่อติดต่อสำหรับบุคคลอายุ 10 ปี ((9+10)/2) ซึ่งผิด คำตอบที่ถูกต้องคือ 9.1 66 = 55 / 6 = (9×3+9×2+10×1)/(3+2+1)

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

• เครื่องอ่านข้อมูลเข้า
• ฟังก์ชันแผนที่​
• ฟังก์ชันพาร์ติชัน
• ฟังก์ชันเปรียบเทียบ​
• ฟังก์ชันลด​
• ตัวเขียนเอาต์พุต

ตัวอ่านข้อมูลเข้าจะแบ่งข้อมูลเข้าเป็นส่วนย่อยที่มีขนาดเหมาะสม (ในทางปฏิบัติ โดยทั่วไปคือ 64 MB ถึง 128 MB) และเฟรมเวิร์กจะกำหนดส่วนย่อยหนึ่งส่วนให้กับฟังก์ชันMap แต่ละฟังก์ชัน ตัวอ่านข้อมูลเข้าจะอ่านข้อมูลจากแหล่งจัดเก็บข้อมูลถาวร (โดยทั่วไปคือระบบไฟล์แบบกระจาย ) และสร้างคู่คีย์/ค่า

ตัวอย่างที่พบได้ทั่วไปคือการอ่านไดเร็กทอรีที่เต็มไปด้วยไฟล์ข้อความและส่งคืนแต่ละบรรทัดเป็นระเบียน

ฟังก์ชัน Map รับคู่คีย์/ค่าหลายคู่ ประมวลผลแต่ละคู่ และสร้างคู่คีย์/ค่าเอาต์พุตตั้งแต่ศูนย์คู่ขึ้นไป ประเภทของข้อมูลอินพุตและเอาต์พุตของ Map อาจแตกต่างกันได้ (และมักจะแตกต่างกัน )

หากแอปพลิเคชันทำการนับคำ ฟังก์ชัน map จะแยกบรรทัดออกเป็นคำๆ และส่งออกคู่คีย์/ค่าสำหรับแต่ละคำ โดยแต่ละคู่ผลลัพธ์จะมีคำเป็นคีย์และจำนวนครั้งที่คำนั้นปรากฏในบรรทัดเป็นค่า

ผลลัพธ์ แต่ละรายการ จากฟังก์ชัน Map จะถูกจัดสรรให้กับ ตัวลด (reducer)เฉพาะตัวหนึ่ง โดย ฟังก์ชันpartitionของแอปพลิเคชัน เพื่อ วัตถุประสงค์ ใน การแบ่งส่วนข้อมูล (sharding ) ฟังก์ชัน partitionจะได้รับคีย์และจำนวนตัวลด และส่งคืนดัชนีของตัวลด ที่ต้องการ

โดยทั่วไปแล้ว ค่าเริ่มต้นคือการแฮชคีย์และใช้ค่าแฮชหารด้วยจำนวนตัวลด (reducer ) สิ่งสำคัญคือต้องเลือกฟังก์ชันการแบ่งพาร์ติชันที่ให้การกระจายข้อมูลต่อชาร์ดอย่างสม่ำเสมอโดยประมาณเพื่อ วัตถุประสงค์ใน การปรับสมดุลภาระงานมิฉะนั้น การทำงานของ MapReduce อาจหยุดชะงักเนื่องจากต้องรอตัวลดที่ทำงานช้า (เช่น ตัวลดที่ได้รับส่วนแบ่งข้อมูลที่ไม่สม่ำเสมอมากกว่า)

ระหว่างขั้นตอน map และ reduce ข้อมูลจะถูกสับเปลี่ยน (เรียงลำดับแบบขนาน / แลกเปลี่ยนระหว่างโหนด) เพื่อย้ายข้อมูลจากโหนด map ที่สร้างข้อมูลนั้นไปยัง shard ที่จะทำการลดขนาดข้อมูล การสับเปลี่ยนอาจใช้เวลานานกว่าเวลาในการคำนวณ ขึ้นอยู่กับแบนด์วิดท์ของเครือข่าย ความเร็วของ CPU ปริมาณข้อมูลที่สร้างขึ้น และเวลาที่ใช้ในการคำนวณ map และ reduce

ข้อมูลนำเข้าสำหรับแต่ละขั้นตอน Reduceจะถูกดึงมาจากเครื่องที่ทำการMap และจัดเรียงโดยใช้ ฟังก์ชัน เปรียบเทียบของแอปพลิเคชัน

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

ในตัวอย่างการนับคำ ฟังก์ชัน Reduceจะรับค่าอินพุต นำมาบวกกัน และสร้างเอาต์พุตเดียวซึ่งประกอบด้วยคำและผลรวมสุดท้าย

ตัวเขียนผลลัพธ์ (Output Writer)จะเขียนผลลัพธ์ของการดำเนินการลด (Reduce ) ลงในหน่วยเก็บข้อมูลถาวร

คุณสมบัติของโมโนอิดเป็นพื้นฐานในการรับรองความถูกต้องของการดำเนินการ MapReduce ^{[ 18 ] [ 19 ]}

ในแพ็คเกจ Algebird ^{[ 20 ]}การใช้งาน Map/Reduce ในภาษา Scala จำเป็นต้องใช้ประเภทคลาส monoid อย่างชัดเจน^{[ 21 ]}

การทำงานของ MapReduce เกี่ยวข้องกับข้อมูลสองประเภท: ประเภทAคือข้อมูลขาเข้าที่ถูกแปลง (mapping) และประเภทBคือข้อมูลขาออกที่ถูกลดทอน (reduced)

การดำเนิน การ Mapจะรับค่าแต่ละค่าของประเภทAและสร้างค่าb:B สำหรับแต่ละ a:Aการ ดำเนินการ Reduceต้องการการดำเนินการไบนารีที่กำหนดไว้บนค่าของประเภทBซึ่งประกอบด้วยการรวมb:B ที่มีอยู่ทั้งหมด เข้าเป็นค่าเดียว

จากมุมมองของข้อกำหนดพื้นฐาน การดำเนินการ MapReduce ใดๆ ก็ตามจะต้องมีความสามารถในการจัดกลุ่มข้อมูลที่กำลังลดขนาดใหม่ได้ตามอำเภอใจ ข้อกำหนดดังกล่าวประกอบด้วยคุณสมบัติสองประการของการดำเนินการ:

• คุณสมบัติการสลับที่: ( x • y ) • z = x • ( y • z )
• การมีอยู่ขององค์ประกอบที่เป็นกลางeซึ่งทำให้e • x = x • e = xสำหรับทุกx: B

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

คุณสมบัติทั้งสองนี้เทียบเท่ากับการมีโมโน อิด ( B , •, e ) บนค่าประเภทBที่มีการดำเนินการ • และมีองค์ประกอบที่เป็นกลางe

ไม่มีข้อกำหนดใดๆ เกี่ยวกับค่าของชนิดA ; สามารถใช้ฟังก์ชันใดๆ ก็ได้A → B สำหรับการดำเนินการ Mapซึ่งหมายความว่าเรามีcatamorphism A* → ( B , •, e ) โดยที่A*หมายถึงKleene star หรือ ที่ รู้จักกันในชื่อชนิดของลิสต์เหนือA

การ ดำเนินการ Shuffleนั้นไม่เกี่ยวข้องกับแก่นแท้ของ MapReduce โดยตรง แต่จำเป็นสำหรับการกระจายการคำนวณไปยังระบบคลาวด์

จากที่กล่าวมาข้างต้น สรุปได้ว่า การดำเนินการ Reduce แบบไบนารีทุกรูปแบบไม่ได้ ผลใน MapReduce เสมอไป ตัวอย่างที่ขัดแย้งมีดังนี้:

• การสร้างต้นไม้จากต้นไม้ย่อย: การดำเนินการนี้ไม่เป็นไปตามกฎการสลับที่ และผลลัพธ์จะขึ้นอยู่กับการจัดกลุ่ม
• การคำนวณค่าเฉลี่ยโดยตรง: ค่าเฉลี่ยไม่มีคุณสมบัติการสลับที่ (และไม่มีองค์ประกอบที่เป็นกลาง) ในการคำนวณค่าเฉลี่ย จำเป็นต้องคำนวณโมเมนต์

โปรแกรม MapReduce ไม่รับประกันว่าจะเร็วเสมอไป ประโยชน์หลักของโมเดลการเขียนโปรแกรมนี้คือการใช้ประโยชน์จากการดำเนินการสับเปลี่ยนที่ได้รับการปรับให้เหมาะสมของแพลตฟอร์ม และต้องเขียนเฉพาะ ส่วน MapและReduceของโปรแกรมเท่านั้น ในทางปฏิบัติ ผู้เขียนโปรแกรม MapReduce ต้องคำนึงถึงขั้นตอนการสับเปลี่ยน โดยเฉพาะอย่างยิ่งฟังก์ชันพาร์ติชันและปริมาณข้อมูลที่เขียนโดย ฟังก์ชัน Mapซึ่งอาจส่งผลกระทบอย่างมากต่อประสิทธิภาพและความสามารถในการขยายขนาด โมดูลเพิ่มเติม เช่น ฟังก์ชัน Combinerสามารถช่วยลดปริมาณข้อมูลที่เขียนลงดิสก์และส่งผ่านเครือข่ายได้ แอปพลิเคชัน MapReduce สามารถเพิ่มความเร็วได้ในระดับต่ำกว่าเชิงเส้นภายใต้สถานการณ์เฉพาะ^{[ 22 ]}

เมื่อออกแบบอัลกอริทึม MapReduce ผู้เขียนจำเป็นต้องเลือกจุดสมดุลที่ดี^{[ 11 ]}ระหว่างต้นทุนการคำนวณและต้นทุนการสื่อสาร ต้นทุนการสื่อสารมักจะมากกว่าต้นทุนการคำนวณ^{[ 11 ] [ 22 ]}และการใช้งาน MapReduce จำนวนมากได้รับการออกแบบมาเพื่อเขียนการสื่อสารทั้งหมดลงในที่เก็บข้อมูลแบบกระจายเพื่อการกู้คืนจากความล้มเหลว

ในการปรับแต่งประสิทธิภาพของ MapReduce ความซับซ้อนของการแมป การสับเปลี่ยน การเรียงลำดับ (การจัดกลุ่มตามคีย์) และการลดขนาดจะต้องนำมาพิจารณาด้วย ปริมาณข้อมูลที่ผลิตโดยตัวแมปเป็นพารามิเตอร์สำคัญที่เปลี่ยนต้นทุนการคำนวณส่วนใหญ่ระหว่างการแมปและการลดขนาด การลดขนาดรวมถึงการเรียงลำดับ (การจัดกลุ่มคีย์) ซึ่งมีความซับซ้อนแบบไม่เชิงเส้น ดังนั้น ขนาดพาร์ติชันที่เล็กจะช่วยลดเวลาในการเรียงลำดับ แต่ก็มีข้อแลกเปลี่ยนเนื่องจากการมีตัวลดขนาดจำนวนมากอาจไม่เหมาะสม อิทธิพลของขนาดหน่วยการแบ่งนั้นมีน้อยมาก (เว้นแต่จะเลือกไม่ดีเป็นพิเศษ เช่น <1MB) โดยเฉลี่ยแล้ว ผลประโยชน์จากการที่ตัวแมปบางตัวอ่านโหลดจากดิสก์ภายในเครื่องนั้นมีน้อย^{[ 23 ]}

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

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

การดำเนินการลดขนาด (Reduce) ทำงานในลักษณะเดียวกัน เนื่องจากคุณสมบัติที่ด้อยกว่าในด้านการดำเนินการแบบขนาน โหนดหลักจึงพยายามกำหนดตารางการดำเนินการลดขนาดให้อยู่ในโหนดเดียวกัน หรือในแร็คเดียวกันกับโหนดที่เก็บข้อมูลที่กำลังดำเนินการอยู่ คุณสมบัตินี้เป็นที่ต้องการเนื่องจากช่วยประหยัดแบนด์วิดท์ในเครือข่ายหลักของศูนย์ข้อมูล

การใช้งานจริงนั้นไม่จำเป็นต้องมีความน่าเชื่อถือสูง เสมอไป ตัวอย่างเช่น ในHadoop เวอร์ชันเก่า NameNode เป็นจุดล้มเหลวเพียงจุดเดียวสำหรับระบบไฟล์แบบกระจาย ในขณะที่ Hadoop เวอร์ชันใหม่กว่ามีความพร้อมใช้งานสูงด้วยระบบ Failover แบบ Active/Passive สำหรับ "NameNode"

MapReduce มีประโยชน์ในการใช้งานที่หลากหลาย รวมถึงการค้นหาตามรูปแบบแบบกระจาย การเรียงลำดับแบบกระจาย การกลับกราฟลิงก์เว็บ การแยกค่าเอกพจน์^{[ 24 ] สถิติบันทึกการเข้าถึงเว็บ การสร้างดัชนีแบบกลับด้าน การจัดกลุ่มเอกสาร การเรียนรู้ของเครื่อง [ 25 ] และ}การแปลด้วยเครื่องเชิงสถิติยิ่ง^{ไปกว่า}นั้นโมเดล MapReduce ยังได้รับการปรับให้เข้ากับสภาพแวดล้อมการคำนวณหลายอย่าง เช่น ระบบมัลติคอร์และหลายคอร์^{[ 26 ] [ 27 ] [ 28 ]}กริดเดสก์ท็อป^{[ 29 ]} มัลติคลัสเตอร์^{[ 30 ]}สภาพแวดล้อมการคำนวณแบบอาสาสมัคร^{[ 31 ]}สภาพแวดล้อมคลาวด์แบบไดนามิก^{[ 32 ]}สภาพแวดล้อมมือถือ^{[ 33 ]}และสภาพแวดล้อมการคำนวณประสิทธิภาพสูง^{[ 34 ]}

ที่ Google นั้น MapReduce ถูกนำมาใช้เพื่อสร้างดัชนีของ Google สำหรับWorld Wide Web ขึ้นมาใหม่ทั้งหมด โดยแทนที่ โปรแกรม เฉพาะกิจ แบบเก่า ที่ใช้ในการอัปเดตดัชนีและดำเนินการวิเคราะห์ต่างๆ^{[ 35 ]}การพัฒนาที่ Google ได้ก้าวไปสู่เทคโนโลยีต่างๆ เช่น Percolator, FlumeJava ^{[ 36 ]}และMillWheelซึ่งนำเสนอการทำงานและการอัปเดตแบบสตรีมมิ่งแทนการประมวลผลแบบแบตช์ เพื่อให้สามารถผสานรวมผลการค้นหาแบบ "สด" ได้โดยไม่ต้องสร้างดัชนีใหม่ทั้งหมด^{[ 37 ]}

โดยปกติแล้ว ข้อมูลนำเข้าและข้อมูลส่งออกที่เสถียรของ MapReduce จะถูกจัดเก็บไว้ในระบบไฟล์แบบกระจาย ส่วนข้อมูลชั่วคราวจะถูกจัดเก็บไว้ในดิสก์ภายในเครื่อง และถูกดึงมาจากระยะไกลโดยตัวลดทอน (reducer)

David DeWittและMichael Stonebrakerนักวิทยาศาสตร์คอมพิวเตอร์ผู้เชี่ยวชาญด้านฐานข้อมูลแบบขนานและสถาปัตยกรรมแบบไม่มีการแบ่งปัน ได้วิพากษ์วิจารณ์ขอบเขตของปัญหาที่ MapReduce สามารถนำไปใช้ได้^{[ 38 ]}พวกเขาเรียกอินเทอร์เฟซของมันว่าระดับต่ำเกินไป และตั้งคำถามว่ามันแสดงถึงการเปลี่ยนแปลงกระบวนทัศน์อย่างที่ผู้สนับสนุนอ้างจริงหรือไม่^{[ 39 ]}พวกเขาตั้งคำถามต่อข้ออ้างเรื่องความแปลกใหม่ของผู้สนับสนุน MapReduce โดยยกตัวอย่างTeradataเป็นตัวอย่างของเทคโนโลยีที่มีอยู่ก่อนหน้ามานานกว่าสองทศวรรษ พวกเขายังเปรียบเทียบโปรแกรมเมอร์ MapReduce กับ โปรแกรมเมอร์ CODASYLโดยสังเกตว่าทั้งสอง "เขียนด้วยภาษาระดับต่ำและทำการจัดการเรคอร์ดระดับต่ำ" ^{[ 39 ]}การใช้ไฟล์อินพุตของ MapReduce และการขาด การสนับสนุน สคีมาทำให้ไม่สามารถปรับปรุงประสิทธิภาพที่เกิดจากคุณสมบัติระบบฐานข้อมูลทั่วไป เช่นB-treeและการแบ่งพาร์ติชันแบบแฮชได้แม้ว่าโครงการต่างๆ เช่นPig (หรือ PigLatin) , Sawzall , Apache Hive [ ^{40 ] HBase} [ ^{41 ] และ} Bigtable [ ^{41 ] [ 42 ] จะ}แก้ไขปัญหาเหล่านี้บางส่วนแล้วก็ตาม

Greg Jorgensen เขียนบทความปฏิเสธมุมมองเหล่านี้^{[ 43 ]} Jorgensen ยืนยันว่าการวิเคราะห์ทั้งหมดของ DeWitt และ Stonebraker นั้นไม่มีมูลความจริง เนื่องจาก MapReduce ไม่ได้ถูกออกแบบหรือตั้งใจให้ใช้เป็นฐานข้อมูล

ต่อมา DeWitt และ Stonebraker ได้เผยแพร่การศึกษาเปรียบเทียบประสิทธิภาพโดยละเอียดในปี 2009 โดยเปรียบเทียบประสิทธิภาพของ MapReduce ของ Hadoopและ วิธีการ RDBMSในปัญหาเฉพาะหลายประการ^{[ 44 ]}พวกเขาสรุปว่าฐานข้อมูลเชิงสัมพันธ์มีข้อดีที่แท้จริงสำหรับการใช้งานข้อมูลหลายประเภท โดยเฉพาะอย่างยิ่งในการประมวลผลที่ซับซ้อนหรือในกรณีที่ข้อมูลถูกนำไปใช้ทั่วทั้งองค์กร แต่ MapReduce อาจใช้งานง่ายกว่าสำหรับผู้ใช้ในการนำไปใช้สำหรับงานประมวลผลแบบง่ายหรือแบบครั้งเดียว

รูปแบบการเขียนโปรแกรม MapReduce ได้รับการอธิบายไว้ในวิทยานิพนธ์ของDanny Hillis ในปี 1985 ^{[ 45 ]}ซึ่งมีจุดประสงค์เพื่อใช้บนConnection Machineโดยเรียกว่า "xapping/reduction" ^{[ 46 ]}และอาศัยฮาร์ดแวร์พิเศษของเครื่องนั้นเพื่อเร่งความเร็วทั้ง map และ reduce ภาษาถิ่นที่ใช้สำหรับ Connection Machine ในท้ายที่สุดคือ StarLisp ในปี 1986 ^{ซึ่งมี parallel และ [} 47 ] *mapซึ่งreduce!!ใน^{ทางกลับ}กันก็อิงตามCommon Lisp ในปี 1984 ซึ่งมี non-parallel และbuilt-in ^{[ 48 ]}แนวทางแบบต้นไม้ ที่ สถาปัตยกรรม hypercubeของ Connection Machine ใช้ในการดำเนินการในเวลา^{[ 49 ]}นั้นมีประสิทธิภาพเหมือนกับแนวทางที่อ้างถึงในเอกสารของ Google ว่าเป็นงานก่อนหน้า^{[ 3 ] : 11}mapreducereduce${\displaystyle O(\log n)}$

ในปี 2010 Google ได้รับสิทธิบัตรที่เรียกว่า MapReduce สิทธิบัตรนี้ยื่นจดในปี 2004 และอาจครอบคลุมการใช้งาน MapReduce โดยซอฟต์แวร์โอเพนซอร์ส เช่นHadoop , CouchDBและอื่นๆ ในArs Technicaบรรณาธิการยอมรับบทบาทของ Google ในการทำให้แนวคิด MapReduce เป็นที่นิยม แต่ตั้งคำถามว่าสิทธิบัตรนี้ถูกต้องหรือเป็นสิ่งใหม่หรือไม่^{[ 50 ] [ 51 ]}ในปี 2013 ในฐานะส่วนหนึ่งของ "คำมั่นสัญญา Open Patent Non-Assertion (OPN)" Google ให้คำมั่นว่าจะใช้สิทธิบัตรนี้เพื่อการป้องกันเท่านั้น^{[ 52 ] [ 53 ]}คาดว่าสิทธิบัตรจะหมดอายุในวันที่ 23 ธันวาคม 2026 ^{[ 54 ]}

งาน MapReduce ต้องเขียนเป็นโปรแกรมการไหลของข้อมูลแบบไม่มีวงจร กล่าวคือ ตัวแมปเปอร์แบบไร้สถานะตามด้วยตัวรีดิวเซอร์แบบไร้สถานะ ซึ่งดำเนินการโดยตัวกำหนดตารางเวลางานแบบแบตช์ รูปแบบนี้ทำให้การสอบถามชุดข้อมูลซ้ำๆ เป็นเรื่องยากและสร้างข้อจำกัดที่รู้สึกได้ในสาขาต่างๆ เช่นการประมวลผลกราฟ^{[ 55 ]} ซึ่งอัลกอริทึมแบบวนซ้ำที่กลับไปใช้ ชุดข้อมูลเดียวหลายครั้งเป็นเรื่องปกติ เช่นเดียวกับในกรณีที่มี ข้อมูลบน ดิสก์ ที่ มีความหน่วงสูงแม้แต่ในสาขาการเรียนรู้ของเครื่องที่ต้องผ่านข้อมูลหลายรอบถึงแม้ว่าอัลกอริทึมจะสามารถทนต่อการเข้าถึงข้อมูลแบบอนุกรมในแต่ละรอบได้ก็ตาม^{[ 56 ]}

• รูปแบบเบิร์ด-เมียร์เทนส์
• สัญญาขนาน

• Apache CouchDB
• Apache Hadoop
• อินฟินิสปาน
• ริแอค