ออกแบบ Key-Value Store

Key-Value Store เป็นประเภทของ Non-relational Database ที่ข้อมูลถูกจัดเก็บเป็น Key-Value Pairs แต่ละ Key ไม่ซ้ำกัน และ Values ถูกเข้าถึงโดยใช้ Keys เหล่านี้

บทนำ

Key-Value Store เป็นประเภทของ Non-relational Database ที่ข้อมูลถูกจัดเก็บเป็น Key-Value Pairs แต่ละ Key ไม่ซ้ำกัน และ Values ถูกเข้าถึงโดยใช้ Keys เหล่านี้ บทนี้อธิบายวิธีออกแบบ Distributed Key-Value Store ที่รองรับ High Availability และ Scalability

Operations หลัก

• put(key, value) สำหรับแทรกข้อมูล
• get(key) สำหรับดึงข้อมูล

CAP Theorem

ภาพที่ 1: CAP Theorem Triangle

Distributed Key-Value Store ต้องรับมือกับ Trade-offs ที่ระบุโดย CAP Theorem

ประเภทระบบ

• CP Systems: Consistency และ Partition Tolerance (เช่น Banking Systems)
• AP Systems: Availability และ Partition Tolerance (เช่น Eventual Consistency)
• CA Systems: Consistency และ Availability ไม่สามารถมีอยู่ได้ในโลกจริงเพราะ Network Failure ไม่สามารถหลีกเลี่ยงได้

ส่วนประกอบของระบบ

1. Data Partitioning

ใช้ Consistent Hashing กระจายข้อมูลข้าม Servers อย่างเท่าเทียม

• การขยายอัตโนมัติเมื่อ Server ถูกเพิ่ม/ลบ
• Heterogeneity ผ่าน Virtual Nodes

2. Data Replication

จำลองข้อมูลข้าม N Servers เพื่อ High Availability

• เลือก N Servers โดยเดินทวนเข็มนาฬิกาจาก Server Position
• วาง Replicas ใน Data Centers ที่แตกต่างกัน

3. Consistency

Quorum Consensus:

• N: จำนวน Replicas ทั้งหมด
• W: Write Quorum Size (ต้องได้รับ Acknowledgment จาก W Replicas)
• R: Read Quorum Size (ต้องรอ Response จาก R Replicas)
• กฎ: W + R > N รับประกัน Strong Consistency

4. Inconsistency Resolution

ใช้ Vector Clocks ติดตาม Data Versions และแก้ไข Conflicts

• Vector Clock คือ [server, version] pair ที่เชื่อมโยงกับ Data Item
• ใช้ตรวจสอบว่า Version หนึ่งนำหน้า ตามหลัง หรือขัดแย้งกับ Version อื่น

5. การจัดการ Failures

a. Failure Detection

Gossip Protocol:

• แต่ละ Node รักษา Member IDs และ Heartbeat Counters
• แต่ละ Node เพิ่ม Heartbeat Counter เป็นระยะ
• หาก Heartbeat ไม่เพิ่มขึ้นเกินช่วงที่กำหนด Member ถือว่า Offline

b. Temporary Failures

Sloppy Quorum: ใช้ Healthy Nodes รักษา Operations ชั่วคราว

Hinted Handoff: Offline Servers ตาม kịp กับการเปลี่ยนแปลงเมื่อฟื้นตัว

c. Permanent Failures

ใช้ Merkle Trees สำหรับ Synchronization ที่มีประสิทธิภาพระหว่าง Replicas

Write และ Read Paths

Write Path

1. Persist Write ใน Commit Log
2. Save ข้อมูลใน Memory Cache
3. Flush ข้อมูลไปยัง SSTable เมื่อ Cache เต็ม

Read Path

1. ตรวจสอบ Memory Cache สำหรับข้อมูล
2. หากไม่มี ใช้ Bloom Filter เพื่อหาตำแหน่งข้อมูลใน SSTables
3. ดึงและส่งคืนข้อมูล

เนื้อหานี้อ้างอิงจาก ByteByteGo - System Design Interview - An Insider's Guide