หากจะกล่าวว่า Google คืออันดับหนึ่งด้าน distributed system ก็คงเป็นคำกล่าวที่ไม่ได้เกินจริง เพราะด้วยตัวธุรกิจของ Google ที่ต้อง scale ได้ตั้งแต่วันแรก ประกอบกับผลงานที่ผ่านมาของ Google ทั้งในแวดวง academia และ cloud

เช่น

วันนี้ผมจะขอพูดอีกหนึ่ง project ที่หลายๆคนอาจเริ่มได้ยินกันมาบ้าง นั้นคือ Google Spanner ที่ Google สุดแสนจะภูมิใจ ถึงขั้นนำมาให้บริการบน Google Cloud และยังเป็น database ที่ไม่มีใครเหมือนได้อีกแล้ว แม้แต่ open source ยังทำไม่ได้เหมือนเป๊ะแม้จะมี Spanner paper ให้อ่านก็ตาม

เอาล่ะ น่าสนใจกันละครับว่าทำไมมันถึงไม่มีใครเหมือนได้อีกแล้ว อยากรู้ลองอ่านกันต่อเลย

SQL & NoSQL databases

Consistency และ Scalability เป็นปัญหาโลกแตกใน relational database มาโดยตลอด เพราะเหมือนเราต้องเลือกสักอย่าง

และด้วย CAP Theorem ที่กำเนิดทฤษฎีที่ต้องเลือกระหว่าง CP หรือ AP ขึ้นมา ทำให้เกิดการเลือกฝ่ายเกิดขึ้น อย่าง Google นั้นมักเลือก database แบบ CP เช่น BigTable พูดอีกนัยหนึ่งคือ Google หมกมุ่นกับเรื่อง Consistency มากกว่า ในขณะที่ฝั่ง Amazon จะเลือก availiability และ eventual consistency เพื่อ low latency แทน

แต่เมื่อ Google เริ่มถือครองธุรกิจที่หลากหลาย และ applications หลายตัวก็มีความต้องการ database ที่ตอบโจทย์ทั้ง ACID, transactions, high availiability และต้อง scale ระดับโลกได้ด้วยในเวลาเดียวกัน ย้ำอีกครั้งนะครับ ระดับโลก ไม่ใช่แค่ในประเทศหรือทวีป ! ทำให้คราวนี้ Google ต้องการสร้าง database ที่เหนือกว่า BigTable ไปอีกขั้นครับ

ลองสรุปกันก่อนนะครับว่าเรามีอะไรบ้าง

Google มองว่าทางที่ Amazon เลือกอย่าง eventual consistency มันยังไม่ใช่คำตอบของพวกเขา เพราะ 1. eventual consistency คือเมื่อไหร่ล่ะ ? และ 2. last-write-wins timestamp เป็นการแก้แบบชุ่ยๆ เพราะมันไม่สามารถให้ consistency และ serializability ได้เลย

BigTable สามารถ scale write and read ได้ดีมากๆอยู่แล้วจากการทำ partition + Region server และ replication จาก GFS รวมไปถึงเรื่องการ auto sharding, auto-rebalancing และ automatic failure

เพราะงั้น Google จึงคิดว่า เราเอา BigTable ของเรามาปัดฝุ่นใหม่แล้วเสริมความสามารถให้ supports serializability, consistency และ ACID transaction ได้ก็น่าจะตอบโจทย์เรานะ

และนั้นคือจุดกำเนิดของ Spanner ครับ !

Spanner architecture

spanner-architecture
Spanner paper

มีความคล้ายกับ BigTable มาก เนื่องจากทีมงานของ Spanner หลายๆคนก็มาจาก BigTable นี้แหละ และการที่ BigTable เป็น CP ไม่เหมือนกับ Cassandra ที่เป็น AP ตาม CAP theorem จึงเป็นอะไรที่เหมาะเหม็งกับการเป็น base architecture ของ Spanner อย่างมาก

Tablets

Note: Tablets จริงๆแล้วมันก็คือ partitions ที่เก็บ data ของเรานี้แหละครับ ผมขออนุญาตใช้คำว่า partitions แทนเพื่อให้เข้าใจง่ายขึ้นมาอีกนิดนะครับ

โจทย์ที่ Google ต้องตีให้แตกคือ 1.ต้องเป็น strict consistency และ 2.replications เพื่อ high availability

การใช้ asynchronous replication นั้นอาจดีต่อ performance แต่ก็ก่อให้เกิด replication lag และ inconsistency ของ data ได้ ดังนั้น solution จึงเหลือเพียงแค่เลือกใช้ consensus algorithm เพื่อสร้าง unified group กัน

และสิ่งหนึ่งที่ Spanner ทำให้ผมต้องทึ่งคือการ implement Paxos consensus algorithm ใน partition level ครับ เพราะ Paxos เป็นอะไรที่มี cost สูงมากเมื่อเทียบกับ Raft แต่ก็นะ นี้คือ Google ที่มี private fibre network ของตัวเอง + data center ทั่วโลก

spanner-paxos
Spanner paper

เมื่อ Google แปะ Paxos ลงไปใน partitions สิ่งที่เกิดขึ้นคือ:

  1. High availability จาก election leader
  2. Paxos write ไม่จำเป็นต้องมาครบทุกคน แต่ใช้การทำ majority vote แทน
  3. มั่นใจได้ว่า partitions ของเรามี consistency
spanner-overview
https://www.slideshare.net/BenjaminBengfort/an-overview-of-spanner-googles-globally-distributed-database

อย่างไรก็ตามแต่ Spanner จำเป็นต้องใช้ pessimistic locking row ในขณะ write (two-phase-locking) กับ lead replicas เพื่อป้องกัน race conditions จาก transaction อื่นๆ เช่นหาก transaction ของเรา update record จากหลายๆ partitions พร้อมกัน อาจก่อให้เกิดปัญหา conflict และฝ่าฝืน strict serializability แบบ SQL ที่เราต้องการได้

นอกจากต้อง lock row แล้ว บางกรณีที่ transaction มี operation กับหลายๆ partitions Spanner จำเป็นต้องใช้ two-phase-commit กับ partitions เหล่านั้นเพื่อการันตีว่าทุกๆ commit ของเราถูก distribute ไปยัง partitions เหล่านั้นจริงๆ

Time

เวลาเป็นเรื่องที่น่ารำคาญมากกับ distributed system คือ netowrk มันเชื่อไม่ได้ และ hardware แต่ละ node ดันมีเวลาที่คลาดเคลื่อนจากกันอีก

ที่น่าเศร้ากว่านั้นและเป็นปัญหาใหญ่คือ หากเราต้องการ linearlizability เราจำเป็นต้องปรับจูนให้เวลาของทุกๆ node และทุกๆ zone ในโลกตรงกันให้ได้ เพื่อให้ transactions สามารถถูกจัดเรียงลงบนเส้น timeline เพียงเส้นเดียว

Linearizability (external consistency) คือปัญหาหลักของ distributed database เลย คือทำไงให้ query แล้วได้ข้อมูลเหมือนกัน พูดง่ายๆคือหลอก users ว่าเรามี single copy นะ

และพระเอกของงานคือ true time API ที่ Google คิดค้นขึ้นมาเองกับมือ โดยใช้ atomic clock และ GPS ติดตั้งในทุก datacenters ของ Google เพื่อใช้แทน NTP protocol ที่มีความคลาดเคลื่อนถึง 250 milliseconds ตรงกันข้าม true time API ของ Google ที่มี skew ที่ต่ำเพียงแค่ 7 milliseconds หรือพูดภาษาชาวบ้านคือมีความคลาดเคลื่อน + 7 miliseconds เท่านั้น

หลักการทำงานของ true time API คือจะ report เวลาแบบ confident interval เช่น A = [ A earliest , A latest ] และ B = [ B earliest , B latest ] ซึ่งเวลาที่ได้มาจะไม่มีทางทับซ้อนกัน หรือพูดอีกนัยหนึ่งคือ A earliest < A latest < B earliest < B latest ซึ่งตัว Spanner เองจะรอให้พ้น maximum time skew ก่อนจะ commit เสมอ เพื่อการันตีว่า timestamp ของแต่ละ transaction จะไม่ overlap กันโดยเด็ดขาด

CockroachDB - Spanner open source version ไม่สามารถการันตี linearlizability แบบที่ Spanner ทำได้เนื่องจากไม่มี hardware แบบที่ Google มี จึงการันตีได้เพียง serializability ของแต่ละ transaction เท่านั้น - source

และเมื่อ timestamp ของทุกๆ transaction ในทุกๆ zone เชื่อถือได้แล้ว ทีนี้ตัวระบบก็สามารถการันตี linearlizability ได้ละครับ

ผลพลอยได้อีกอย่างคือ read transaction แบบ snapshot isolation (read without locking) ซึ่งช่วยเพิ่ม performance โดยรวมของ database

Conclusion



 

Reference