Distributed data EP. 1: Replication

สวัสดีค่ะ บทความนี้เราจะเล่าเกี่ยวกับการทำ distributed data กัน

ก่อนอื่นทำไมเราถึงอยาก distributed data และเรื่องอะไรที่เราจำเป็นต้อง concern บ้าง ?

• Scalability — เพราะยิ่งข้อมูลมีเยอะมาก, ยิ่งมีการ read และ write มากกว่าที่ 1 เครื่องจะรันไหว เราจึงต้องกระจาย load ตรงนี้มาหลายๆ machine
• Fault tolerance/High Availability — แม้ว่ามีเครื่องที่ down ไป ก็ยังมีเครื่องอื่นๆที่ยังรองรับในกรณี failover
• Latency — ทำให้ user สามารถเข้าถึง datacenter ที่ใกล้ที่สุดเพื่อลดเวลารอมากที่สุด
• Disconnected mode — หาก application เรามียังคงทำงานได้อยู่แม้จะมีปัญหาเรื่อง network

แล้วเราทำ distributed data ได้ยังไงได้บ้าง?

วิธีที่จะทำให้ data ถูก distributed ข้าม multiple node ได้ มี 2 วิธี

1. Replication

การ copy data เดียวกันเก็บไว้ในหลายๆ node หลายๆ location ที่แตกต่างกัน และเมื่อเกิดเหตุการณ์มีบาง node ที่ตาย ก็จะยังมี data ที่ถูกเก็บใน node อื่นๆที่ยังอยู่

2. Partitioning หรือ Sharding

คือการแบ่งข้อมูลที่ใหญ่มากๆออกมาเป็น subset เล็กๆ ซึ่ง subset นี้เราจะเรียกว่า partitions และ partitions จะถูก assign ไปตาม node

ในบทความนี้เราจะเน้นเล่าเรื่อง Replication เป็นหลัก

Replication means keeping a copy of the same data on multiple machines

หลายเหตุผลที่เราต้องทำ replication คือ

• เพื่อให้ data กระจายอยู่ใกล้กับ geolocation ที่ user อยู่
• เพื่อให้ system ยังคงทำงานได้แม้จะมีบางส่วนที่ failed ไป
• เพื่อ scale out และทำให้ machine สามารถ serve read queries ได้ (increase read throughput)

ถ้าข้อมูลนั้นไม่มีการเปลี่ยนแปลงไปตามกาลเวลา มันคงเป็นเรื่องง่ายๆในการ copy ข้อมูล

แต่ชีวิตจริงไม่ได้เป็นแบบนั้นน่ะสิ

ข้อมูลเรามีการเปลี่ยนแปลงตลอด ดังนั้น เราจึงต้องมีวิธีรับมือได้หลายรูปแบบที่แตกต่างกันตามรูปแบบการ replicate ระหว่าง node

• Single-leader
• Multiple-leader
• Leaderless

เริ่มจากตัวแรก

1. Single Leader

Leader-based replication หรือ active/passive หรือ master-slave replication

1 ตัวจะเป็น leader (หรือ master หรือ primary) และตัวที่ store copy จะเป็น follower (replicas, slaves, secondaries, หรือ hot standbys)

เมื่อ client อยาก write ลง database เขาจะส่ง request นี้ไปหา leader โดยที่ leader จะเป็นคนทำการ write data นี้คนแรกใน local storage ของตัวเอง

ถัดไป leader ก็จะทำหน้าที่เป็นคนส่ง data change นี้ให้กับ followers ซึ่ง data change นี้เราเรียกว่า replication stream จากนั้น followers ก็จะ update ข้อมูลลง local storage ของตัวเองเช่นกัน จนสุดท้าย leader ก็จะส่งบอก client ว่า update เสร็จเรียบร้อยแล้วนะ

ในเรื่องของการ read, client จะสามารถ read จากใครก็ได้ ไม่ว่าจะเป็น leader หรือ follower

แตกต่างกับ write ที่จะ write ผ่าน leader เท่านั้น

ใครใช้บ้าง ?

mode ของ replication นี้ถูกนำมาเป็น feature ใช้ในหลายที่ เช่น

• relational database (PostgreSQL, MySQL, SQL server’s AlwaysOn Availability group),
• nonrelational db (MongoDB, RethinkDB, Espresso)
• หรือที่ไม่ใช้ database เอง (Kafka, RabbitMQ)

Choosing new Leader/Failover

แล้วถ้า leader ตายขึ้นมาล่ะทำยังไง ?

คำตอบง่ายมาก ก็เอา follower ขึ้นมาเป็น leader ตัวใหม่แทนสิ !

แต่ด้วยการนี้ client จำเป็นที่จะต้อง reconfigure ไปยัง leader ตัวใหม่ และ follower ก็จะต้องไป consume ที่ leader ตัวใหม่ ซึ่ง process นี้ถูกเรียกว่า “Failover”

Steps ของ failover:

• บอกได้ว่า Leader failed จริงๆ: เช่น node นั้นไม่ respond มาช่วงเวลาหนึ่งแล้ว เช่น 30 sec
• เลือก leader ตัวใหม่: ขั้นตอนนี้จะเรียกว่า “Election” หรือการเลือกตั้ง โดย candidate จะเป็น node ที่มีข้อมูล up-to-date มากที่สุดเมื่อเทียบกับ leader ตัวเก่าเพื่อลดโอกาส data loss มากที่สุด (พูดง่ายๆ เหมือนเลือกผู้นำก็ต้องเลือกคนที่สานต่องานคนเก่าได้ smooth นั่นแหล่ะ)
• ระบบปรับมาใช้ leader ตัวใหม่: คราวนี้ client ก็จะส่ง request ไปยัง leader ตัวใหม่ได้

Synchronous vs Asynchronous Replication

อีกคอนเซปที่สำคัญคือรายละเอียดในการ replicate มีทั้ง synchronous และ asynchronous

สมมติว่าเรามี follower 2 ตัว 2 แบบ, ตัวแรกเป็นแบบ synchronous ตัวที่ 2 เป็น asynchronous

Synchronous (สีฟ้า):

เมื่อ client มีการ update ข้อมูล ก็จะไปบอก leader, จากนั้น leader ก็จะไปบอก follower 1 ว่ามีการ update dataนะ รอจนกว่าจะมั่นใจได้ว่า follower 1 update data ครบแล้ว จึงค่อยบอก client ว่าการ update ข้อมูลสำเร็จแล้ว

ข้อดีของ synchronous คือ เราสามารถมั่นใจได้ว่า ตัว follower มีข้อมูลที่ up-to-date ตามตัว leader แล้ว

แต่ ! ถ้า follower 1 เราเสียขึ้นมาล่ะ

follower เราอาจจะมีการ crash และไม่ respond ขึ้นมา ก็จะส่งผลให้ leader รอเก้อ ใน database จึงไม่ค่อยนิยมใช้ synchronous ล้วนๆเท่าไร จึงไปใช้แบบ asynchronous มากกว่า

Asynchronous (สีแดง):

เมื่อ client update ข้อมูล, Leader ส่งไปหา follower 2, คราวนี้ Leader ไม่รอ follower 2 แล้ว แต่จะไปบอก client เลยว่าเสร็จทุกอย่างแล้วน้า

ข้อดีของ asynchronous คือ ต่อให้มี follower ไหนตาย leader ก็จะยังทำงานให้การ write data ต่อไปได้อยู่อย่างไม่ติดขัด

Semi-synchronous:

การที่ระบบจะเป็น synchronous ล้วนๆนี่เป็นเรื่องที่ยากมาก ไม่งั้นหากมี follower ไหนตายทุกอย่างคง freeze ไปทั้งหมด ดังนั้นเขาจะผสมระหว่าง synchronous และ asynchronous เข้าด้วยกัน

เช่น 1 ตัวเป็น synchronous, อีก 1 ตัวเป็น asynchronous หากตัวที่ synchronous ตายขึ้นมาวันหนึ่ง ตัวที่เป็น async ก็จะกลายร่างมาเป็น synchronous ให้

ข้อดีคือ จะเป็นการการันตีได้ว่ายังมี node ที่ up-to-date copy จาก leader: กลายมาเป็น 2 nodes ที่ data เท่ากัน

ข้อเสียของ Asynchronous

ในช่วงที่ follower ยังมี data ไม่เท่ากับ leader ขึ้นมา เนื่องจากยัง sync ไม่ทัน เราเรียกว่าช่วงเวลานี้ว่า replication lag

ปัญหาอะไรบ้างที่สามารถเกิดในช่วงเวลานี้

• ตอนเราเพิ่ง update data ไป, เราดันไป read จาก follower replica พอดี ทำให้ได้ outdated data มา

วิธีนี้แก้ด้วยการ read-after-write consistency คือ บังคับให้คนที่เพิ่ง update data เห็นสิ่งที่ตัวเองเพิ่ง write ไป เพื่อมั่นใจได้ว่า data นั้นได้ถูก saved และ node อื่นๆค่อยถูก update ต่อไป

• ตอนเราเพิ่ง update data ไป, คนอื่นดันไป read จาก follower พอดี ได้ updated data แต่ดันไป refresh อีกรอบ เลยได้ outdated data (จาก follower ที่ update ไม่ทัน)

วิธีนี้แก้ด้วย Monotonic read ซึ่งเป็นการการันตีว่า ถ้าได้ updated แล้ว จะไม่มีการย้อนไป older data

• เราเพิ่ง update data ไปและ client อีกคนเพิ่ง update data ไป, observer อีกคนดันเห็น sequence ผิด (ดันไปเห็นของ client ก่อนของเรา) เคสนี้เกิดในเคสที่เป็น partition ร่วมด้วย

วิธีนี้แก้ด้วยการการันตีเรื่อง consistent prefix read การันตีว่าต้อง order ของการ write เรียงถูกต้อง ผู้ที่อ่านก็จะอ่านได้ถูกต้อง

2. Multi-leader Replication

ข้อเสียของ Single leader คือ หาก Leader ตาย เราก็ไม่สามารถ write ข้อมูลลง database ได้ จึงเกิด Multi-leader ขึ้น เพื่อเพิ่มให้เราสามารถ write ข้อมูลได้มากกว่า 1 node

Multi-leader มีอีกชื่อหนึ่งว่า master-master, active/active replication

Usecase อะไรบ้างที่เหมาะกับ Multi-leader

Multi-datacenter

• ลองจินตนาการง่ายๆก็ได้หากเรายังคงใช้ Single leader อยู่ ซึ่ง Leader นั้นตั้งอยู่แค่ 1 datacenterทำให้การ write ผูกติดเฉพาะแค่ 1 datacenter เท่านั้น
• เคส multi-leader จะเหมาะกับเคสที่เรามีหลาย datacenter ทำให้เรามี leader กระจายไปตาม datacenter ที่เรามีอยู่

Client on offline mode

• นั่นคือ application เราสามารถไม่เชื่อมต่อ internet แล้วเรายังสามารถแก้ไขกับ application ได้อยู่ (เช่น แอพปฏิทิน) มันจะมี change ที่เกิดขึ้นเก็บใน local device พอระบบเรากลับมาออนไลน์ปุ๊บ database ของเราก็จะอัพเดทไป server หรือ device เครื่องอื่นๆ
• มองจากตรงนี้ local device เราก็ทำหน้าที่เหมือนเป็น leader นั่นเอง

Realtime Collaborative editing

• ยกตัวอย่างเช่น Google Docs ที่ทำให้คนสามารถเข้ามาแก้ไขเอกสารในเวลาเดียวกันได้
• เมื่อมี user ที่ edit เอกสาร, change ที่เกิดขึ้นก็จะเก็บไว้ที่ local replica แล้ว change นั้นก็จะถูก update ไปยัง server และคนอื่นๆที่ยัง edit เอกสารเดียวกัน

ใครใช้บ้าง ?

หลาย database ที่ supportเรื่อง multi-leader (ที่ implement ร่วมกับ external tools) ก็มี

Tungsten Replicator for MySQL, BDR for PostgreSQL

ฟังดู multi-leader มีข้อดีมากมาย แต่ถ้าหาก Leader ถูก write ข้อมูลเดียวกันและเกิด conflict ข้าม datacenter ขึ้นมาล่ะ นั่นก็เป็นข้อเสียของ multi-leader ที่น่าปวดหัว ซึ่งเราจะยังไม่เล่าวิธี handle conflict ในนี้ไม่งั้นจะยาวเกินไป 555

3. Leaderless Replication

ในขณะที่ Single leader กับ Multi-Leader เน้นการใช้ Leader เป็นคนกำหนดการ write แต่ตัว Leaderless จะแตกต่างออกไป

วิธีการของ Leaderless นั้น client จะเป็นคนส่งการ write data ไป replica โดยไม่ได้กำหนดว่าใครเป็น leader

ในตัวอย่าง client ส่งไป 3 replicas พร้อมๆกัน สมมติว่า replica ตัวที่ 3 เกิด offline ขึ้นมาจึงไม่ได้ถูก write กลายเป็นว่าข้อมูลจึงไม่เท่ากับตัว replica อื่นๆ

อ้าว เกิดถ้ามีคนเข้ามา read ตัว replica ที่ 3 (หลังมัน online แล้ว) ขึ้นมาทำไงล่ะ?

ก็จะได้ข้อมูลไม่เท่ากันงั้นเหรอ?

วิธีแก้ของ leaderless คือ ทุกครั้งที่ client request ขอดูข้อมูล จะเป็น request ที่ส่งไปหา node 2–3 ตัวแบบ parallel กัน เปรียบเทียบ และจะดึงข้อมูลที่ update ที่สุด เช็คได้จากเลข version นั่นเอง

แล้ว replica ตัวที่ 3 จะ catch up data ได้ยังไง? มี 2 วิธี

• จากการ read: เมื่อ client read จะพบว่า replica 3 มีข้อมูลที่ล้าหลังไปแล้ว, ก็จะเกิดการ write value กลับไปให้ replicaตัวที่ 3 มีข้อมูลที่ update ตาม
• จาก Anti-entropy process: เป็น background process ที่จะคอยเช็คว่ามี replica ไหนมีข้อมูลไม่เท่ากับชาวบ้านไหม ก็จะคอย update ให้

ใครใช้บ้าง ?

Riak, Cassandra, Voldermort

และ in-house database ของ Amazon ชื่อ Dynamo-style (facts: ไม่ใช่ DynamoDB นะ ตัวนั้นเป็น Single-Leader)

สรุป

เราได้รู้ว่า Replication นั้นคือการ copy data ที่เหมือนกันกระจายไปหลายๆ machine เพื่อทำให้เกิด High Availablility, Latency ที่เร็วขึ้น, scalability ที่ดีขึ้น

โดยวิธี replication แบ่งออกเป็น 3 แบบคือ Single-leader, Multi-leader, และ Leaderless

โดยหากเป็นแบบ leader-based ตัว leader จะเป็นตัวกำหนดการ write ของ data และหากเป็น leaderless ก็จะสามารถทำทั้ง read และ write ได้ใน node หลายๆตัว โดยทั้ง 3 ตัวต่างมีข้อดีข้อเสียที่แตกต่างกันออกไป

รวมถึงเรายังได้รู้ว่า replication มีวิธีการ copy แบบ synchronous และ asynchronous และเข้าใจปัญหาต่างๆที่สามารถเกิดได้จาก asynchronous ด้วย

ref.

Designing Data-Intensive Applications Chapter 5