BigTable and Chubby Lock Service

มาว่ากันต่อถึงงานวิจัยอีก 2 ชิ้นสำคัญของกูเกิล

BigTable

BigTable เป็นฐานข้อมูลแบบตารางเดียวขนาดยักษ์ (เกินคำว่าใหญ่ไปแล้ว) ถึงแม้มันจะขาดฟีเจอร์หลายอย่างของฐานข้อมูลแบบ relational แต่ว่าจุดสำคัญอยู่ที่การจัดการข้อมูลขนาดใหญ่มากๆ (ใหญ่ที่สุดที่กูเกิลอ้างในเปเปอร์คือ ~800TB ซึ่งมาจาก crawler)

ลูกค้าของ BigTable มีอยู่ประมาณ 60 รายได้แก่ Google Analytics, Google Earth, Orkut เป็นต้น

ตอนนี้โครงสร้างพื้นฐานในการเก็บข้อมูลของกูเกิลจึงมี 2 ระบบ คือ Google File System (สำหรับข้อมูลที่เป็น unstructured เช่น ไฟล์เป็นก้อนๆ) และ BigTable (สำหรับข้อมูลแบบ structure เหมือนที่เก็บลงฐานข้อมูลทั่วๆ ไป) โดย BigTable นั้นขี่อยู่บน GFS อีกชั้นนึง (ให้ GFS ช่วยจัดการเรื่อง redundancy ให้) ตารางใน BigTable จะมีตารางเดียวแต่ขนาดใหญ่มาก โครงสร้างของตารางจะพิสดารกว่าตารางในฐานข้อมูลทั่วๆ ไปอยู่พอสมควร ดูภาพประกอบ

• BigTable เป็นฐานข้อมูล 3 มิติ คือนอกจาก row กับ column แล้ว จะยังมีมิติของเวลา (หรือ revision) มาด้วย โดยสามารถเลือกให้เฉพาะบาง column มีมิติของเวลาได้ (t ในภาพ)
• row key จะเก็บเป็น string ความยาวได้สูงสุดถึง 64KB (โดยปกติจะยาว 10-100 Byte) ตามตัวอย่างจะเห็นว่าปกติแล้วจะเป็น URL นั่นเอง
• ตารางของ BigTable นั้นใหญ่มากๆ เวลาเก็บลง file system จริงจะตัดแบ่งตารางเป็นส่วนๆ แยกกันเก็บในคลัสเตอร์ ดังนั้น locality (อยู่บนเครื่องเดียวกัน) จึงสำคัญเพราะว่าจะได้ลดเวลาในการส่งข้อมูลข้ามเครื่อง BigTable จึงต้องมีวิธีเก็บข้อมูลที่ช่วยเพิ่ม locality ดังนี้
  • row - จากภาพจะเห็นว่า URL ถูกเรียงย้อนกลับเป็น com.cnn.com พอเก็บแบบนี้แล้ว เวลา sort จะทำให้ URL ของโดเมนเดียวกันอยู่ติดกัน จึงเพิ่มโอกาสที่เวลาเก็บจริงบน file system จะอยู่บนเครื่องเดียวกัน
  • column - จากภาพจะเห็นว่าชื่อคอลัมน์มีสองส่วน (anchor:cnnsi.com) ส่วนหน้าจะเรียกว่า family ส่วนหลังเรียก qualifier
    • BigTable จะแยกตารางย่อย (เรียก tablet) ของคอลัมน์ที่มี family เดียวกัน และเก็บไว้ในไฟล์เดียวกัน
    • ตามปกติ 1 family จะใช้กับบริการของกูเกิล 1 อย่าง เช่น Analytics กับ Search จะมี column family คนละอันกัน แต่แชร์ URL (ซึ่งอยู่ใน row) เดียวกัน
  • timestamp เก็บเป็น 64-bit integer (ละเอียดระดับ microsecond)
• ข้อมูลในตารางสามารถตั้งให้ compress ได้ (เพราะเก็บเว็บเพจลงไปทั้งหน้า ดูในคอลัมน์ contents) โดยใช้อัลกอริทึมเฉพาะที่ optimize แล้วจะบีบได้อัตราส่วนสูงสุด 10:1 (เพราะว่า locality เนื่องจากเพจที่มาจากโดเมนเดียวกัน ข้อมูลคล้ายๆ กันจะถูกเก็บลงในไฟล์เดียวกัน)

วิธีเก็บและเชื่อมต่อตาราง จะคล้ายๆ linked list ดูได้ตามภาพ คงไม่ลงรายละเอียด (เพราะไม่ได้อ่านส่วนนี้ :P)

เรื่องของประสิทธิภาพและ scalability นั้นสูงมาก ยิ่งหั่นตารางใหญ่เป็น tablet ย่อยๆ มากเท่าไร ประสิทธิภาพยิ่งสูง (ไม่เพิ่มเป็น linear แต่ตัวเลขที่เปเปอร์ยกมาคือ เพิ่มจำนวน tablet 500 เท่าจะได้ประสิทธิภาพ 300 เท่า)

แอพพลิเคชันจริงที่ยกตัวอย่างมาคือ Google Analytics ซึ่งเก็บข้อมูลทั้งหมดลง 2 ตารางเท่านั้น!!! ตารางแรกคือ raw click ขนาด ~200TB และจะมีโปรแกรมมารันข้อมูลในตารางนี้เป็นระยะ (ผ่าน MapReduce) และเก็บข้อมูลลงตาราง summary ขนาด ~20TB

ปัจจุบันโครงการ Hadoop เองกำลังทำโครงการย่อยเลียนแบบ BigTable ในชื่อ HBase และยังมีโครงการคล้ายๆ กันอีกมาก (แต่ไม่เหมือนซะทีเดียว) เช่น พวก RDBMS cluster edition ทั้งหลาย ไม่ว่าจะเป็น MySQL, DB2, Oracle

Chubby Lock Service

ในการประมวลผลแบบขนานนั้น ประเด็นสำคัญที่ต้องใส่ใจคือการ sync กันระหว่างข้อมูลแต่ละสำเนา ให้ข้อมูลเหมือนกันและไม่มีปัญหาแย่งชิง resource กันเอง โปรแกรมที่มาจัดการเรื่องนี้คือ lock manager

Lock manager โดยมากจะทำงานที่ระดับ file system ในท้องตลาดมีหลายตัว เช่น Oracle Cluster File System ที่มีความสามารถนี้ในตัว ของกูเกิลนั้นชื่อ Chubby

Chubby เป็นรากฐานสำคัญที่ถูกเรียกใช้โดย GFS และ BigTable (ในแง่ของ implementation) สำหรับสองโปรแกรมนี้จะใช้ Chubby ในการเลือก master ที่ใช้สั่งงาน ส่วนโปรแกรมอื่นๆ อาจเรียกใช้ Chubby ในการทำ partition ข้อมูล

เครื่องทั้งหมดที่ใช้ Chubby ร่วมกันจะเรียก Chubby cell (หรือ Chubby instance) ซึ่ง 1 cell โดยปกติจะมีประมาณ 1 หมื่นเครื่อง (เครื่องละ 4 CPU) ส่วนมากจะอยู่ใน data center เดียวกัน อย่างไรก็ตามกูเกิลจะมี replica อย่างน้อยอีก 1 ชุด อยู่ใน data center ที่ห่างกันอย่างต่ำเป็นหลักพันกิโล (สงสัยกลัวโดนนิวเคลียร์ลง)

Chubby ส่งข้อมูลด้วยโปรโตคอล Paxos ซึ่งเป็นแบบ asynchronous

ที่เหลือไม่ค่อยเกี่ยวข้องแล้วเลยไม่ได้อ่านต่อ

สรุป

โครงสร้างพื้นฐานด้านเซิร์ฟเวอร์ของกูเกิลนั้น เริ่มจากความคิดของ Page และ Brin สมัยอยู่ Standford (ตามเปเปอร์ The Anatomy of a Large-Scale Hypertextual Web Search Engine ที่เขียนถึงไปแล้ว) ซึ่งสถาปัตยกรรมแบบนี้ทำให้กูเกิลทำงานได้รวดเร็ว มีประสิทธิภาพ จนดังขึ้นมาในช่วงแรก

อย่างไรก็ตาม เมื่อกูเกิลขยายขนาดขึ้น สถาปัตยกรรมต้นตำรับเริ่มไม่เพียงพอ วิศวกรในกูเกิลจึงต้องพัฒนาโครงสร้างพื้นฐานที่เป็นเรื่องเป็นราวกว่าเดิมมารองรับ ซึ่งชิ้นสำคัญได้แก่

• Google File System
• MapReduce
• BigTable
• Chubby Lock Service

ทั้ง 4 ตัวนี้เป็น "major force multipliers" (ที่มา) ที่ช่วยเพิ่มศักยภาพในการแข่งขันของกูเกิล และสร้างความได้เปรียบเหนือคู่แข่งอย่าง Yahoo! ได้ตลอดมา ทั้ง 4 ตัวนี้เริ่มโผล่ขึ้นมาช่วงปี 2002-2005 ซึ่งเป็นช่วงที่กูเกิลขยายตัวอย่างมีนัยยะสำคัญ หลังจาก 4 ตัวนี้พร้อมแล้ว การพัฒนาบริการใหม่ๆ ของกูเกิลจึงทำได้เร็วและง่ายขึ้น เพราะไม่ต้องเสียเวลามาสนใจเรื่องรายละเอียดของการทำงานบนคลัสเตอร์นั่นเอง

ผมคงไม่เขียนถึง GFS แล้วเนื่องจากว่าเคยอ่านไปเมื่อนานแล้ว และไม่มีเวลาอ่านซ้ำ

สำหรับผู้สนใจเรื่องพวกๆ นี้ เว็บบล็อกที่น่าสนใจคือ High Scalability