ต่อจากเปเปอร์ The Anatomy of a Large-Scale Hypertextual Web Search Engine เมื่อวานนี้ ยังอยู่ในช่วงไล่อ่านเปเปอร์ชิ้นสำคัญๆ ของกูเกิล ตั้งใจว่าจะอ่านให้ได้วันละสาม แต่เอาจริงขี้เกียจ เลยได้วันละอันเท่านั้น

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

ซอฟต์แวร์ที่โด่งดังตัวแรกคือ Google File System ซึ่งเก็บข้อมูลทุกอย่างเป็น 3 สำเนา แยกกันอยู่คนละเครื่อง ส่วน MapReduce นั้นอยู่ในเลเยอร์ที่สูงขึ้นมาอีกหน่อย นั่นคือเป็น ไลบรารีภาษา C++ ที่คอยกระจายงานให้กับโปรแกรมของกูเกิล

ี่ชื่อ MapReduce นั้นมาจาก 2 องค์ประกอบ คือ map กับ reduce (เค้าบอกว่าเอามาจาก Functional programming ผมก็เขียนไม่เป็นเสียด้วย) แต่สรุปง่ายๆ ว่างานประมวลผลข้อมูลเกือบทุกแบบ มันมีโครงสร้างหลักคล้ายๆ กันหมด คือสองส่วนนี้

คิดว่าอธิบาย map กับ reduce โดยใช้ตัวอย่างน่าจะเข้าใจง่ายที่สุด ตัวอย่างที่กูเกิลใช้คือ การนับคำในเอกสาร 1 ชิ้น สมมติว่าเอกสารเรามีคำทั้งหมดดังนี้

to be or not to be

รันฟังก์ชัน map จะได้ (to,1), (be, 1), (or, 1), (not, 1), (to, 1), (be, 1) จะเห็นว่าเป็นงานง่ายๆ โง่ๆ แต่ตอนรันจริง อินพุตมันจะเยอะมหาศาล

เอาผลลัพธ์ของ map มารัน reduce ต่อ ซึ่งในที่นี้ reduce ของเราคือ sum จะได้ (to,2), (be, 2), (or, 1), (not, 1)

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

แผนผังการทำงานของ MapReduce ดูตามภาพ น่าจะอธิบายได้ด้วยตัวมันเอง

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

• atomic commit กันข้อมูลหาย
• ตรวจสอบ failure เป็นระยะ
  • ถ้า worker ตาย -> รันใหม่
  • ถ้า master ตาย -> ทำ checkpoint เป็นระยะ แล้วรันต่อจาก checkpoint
• ดูแลเรื่อง load balancing เช่น ทำ pipelining
• ทำ locality สำหรับ map คือจะรันฟังก์ชัน map บนเครื่องที่มีข้อมูลอยู่แล้ว เพื่อจะได้ไม่ต้องเรียกข้อมูลข้าม network (ช้ากว่าดิสก์)
• ส่วน reduce นั้นปกติทำข้าม network แต่บางกรณีอาจทำแบบ local ได้ (เพื่อประสิทธิภาพที่ดีขึ้น) เค้าเรียก combiner
• แก้ปัญหา straggler (สมมติว่าแบ่งงาน 100 ชิ้น มันจะมีงานชิ้นที่ 98-99 ที่ไปซวยเจอเครื่องมีปัญหา ทำให้เวลารวมช้าขึ้นเยอะมาก) เค้าแก้ปัญหาโดยการรันงานที่ 98-99 สำรองไว้ แล้วใช้อันที่เสร็จก่อน

ตัวอย่างงานที่ใช้ MapReduce ช่วย คือ distributed grep และ distributed sort ส่วนงานจริงๆ ก็คือเอามา reindex ฐานข้อมูลเว็บเพจจริงของกูเกิล (>20TB) แทนโค้ดเดิมทีเคยใช้มานาน ช่วยให้ maintain code สะดวกขึ้น

MapReduce ถูกเขียนขึ้นในปี 2003 (เปเปอร์ออกปี 2004) และถือว่าเป็นการยกระดับสถาปัตยกรรมด้านการคำนวณของกูเกิลขึ้นอีกชั้น คือจากเดิมที่ต่างคนต่างทำมั่วๆ บนคลัสเตอร์ ข้อมูลซ้ำซ้อน ดูแลยากหาบั๊กยาก ก็จับมาใช้ MapReduce ให้หมดเพื่อความเป็นระเบียบ ถือว่าเป็นวิศวกรรมซอฟต์แวร์อีกแขนงหนึ่ง

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

ปัจจุบันมีคน implement เป็นโอเพนซอร์สแล้ว คือโครงการ Hadoop ซึ่งอยู่ภายใต้ Apache และ Lucene (และคนทำไปอยู่กับ Yahoo! แล้ว)

เปเปอร์นี้อ่านยากพอสมควร (แต่มัน) ต้องใช้ความรู้สมัยเรียนเยอะ ไม่ได้ใช้นานก็ต้องเสียเวลานึกเยอะหน่อย ความรู้ที่ต้องใช้ได้แก่

• Mathematics โดยเฉพาะเรื่อง function/correlation
• Data structure โดยเฉพาะ dictionary (key, value) และมี pointer มาแจมๆ เล็กน้อย
• Computer architecture เรื่อง pipelining เหมือนกับของ CPU
• Parallels computing เช่น atomic commit
• โค้ดตัวอย่างเป็น C++ แต่เขียนเป็น C สั้นๆ เข้าใจง่าย แต่ก็ต้องมีพื้น C มาบ้าง (มีเรียก substr หรือ StringToInt อะไรทำนองนี้)

(ผมอ่านเข้าใจประมาณ 80% เพราะเรื่อง functional ก็ไม่แม่นนัก)

เอกสารของ MapReduce มีสองไฟล์ คือสไลด์ กับเปเปอร์ (อธิบายเรื่องเดียวกัน) แนะนำให้อ่านสไลด์ก่อนหนึ่งรอบ บางรูปที่สไลด์ไม่มีคำอธิบาย มีในเปเปอร์

อ่านจบแล้วรู้สึกว่าต้องจำชื่อของ Jeffrey Dean กับ Sanjay Ghemawat ไว้เสียแล้ว เห็นทำของสำคัญกันหลายอย่างในกูเกิลเลยแฮะ