Consistent Hashing เป็นเทคนิคที่จำเป็นสำหรับการบรรลุ Horizontal Scaling โดยการกระจาย Requests และ Data ข้าม Servers อย่างมีประสิทธิภาพ ลดการกระจายข้อมูลใหม่เมื่อ Servers ถูกเพิ่มหรือลบ และรับประกันการกระจายข้อมูลที่สม่ำเสมอเพื่อลดปัญหาเช่น Server Hotspots
บทนำ
ภาพที่ 1: Hash Ring - Consistent Hashing
บทนี้สำรวจ Consistent Hashing ซึ่งเป็นเทคนิคที่จำเป็นสำหรับการบรรลุ Horizontal Scaling โดยการกระจาย Requests และ Data ข้าม Servers อย่างมีประสิทธิภาพ มันลดการกระจายข้อมูลเมื่อ Servers ถูกเพิ่มหรือลบ และรับประกันการกระจายข้อมูลที่สม่ำเสมอเพื่อลดปัญหาเช่น Server Hotspots
ปัญหา Rehashing
คำอธิบาย
ในวิธี Hashing แบบดั้งเดิม เช่น serverIndex = hash(key) % N การกระจายข้อมูลจะเป็นปัญหาเมื่อจำนวน Servers เปลี่ยน:
- การลบ Server ทำให้ Keys ส่วนใหญ่ถูกกำหนดใหม่ นำไปสู่ Cache Misses
- การเพิ่ม Server ส่งผลให้ Keys ถูกกระจายใหม่โดยไม่จำเป็น
ปัญหาหลัก
การกระจาย Keys ส่วนใหญ่เมื่อจำนวน Server เปลี่ยนทำให้เกิดความไม่มีประสิทธิภาพและ Overload
Consistent Hashing คืออะไร
นิยาม
Consistent Hashing รับประกันว่าเฉพาะส่วนน้อยของ Keys จะถูก Remap เมื่อ Servers ถูกเพิ่มหรือลบ สิ่งนี้ลดการหยุดชะงักและเพิ่มความสามารถในการขยาย
แนวคิดหลัก
1. Hash Space และ Ring
ภาพที่ 2: Hash Ring Structure
Hash Space สร้างเป็น Ring ต่อเนื่อง โดยมีค่า Hash กระจายจาก 0 ถึง 2^160-1 (เช่น ใช้ Hash Function เช่น SHA-1)
เมื่อเชื่อมทั้งสองปลายเข้าด้วยกัน เราได้ Ring
2. Server Lookup
Server ของ Key ถูกกำหนดโดยการเดินทวนเข็มนาฬิกาบน Ring จนกว่าจะพบ Server
3. การเพิ่มและลบ Servers
- การเพิ่ม Server: Server ใหม่กระจายเฉพาะ Keys ใกล้เคียงเท่านั้น มีเพียงส่วนน้อยของ Keys ถูกกระจายไปยัง Server ใหม่
- การลบ Server: Server ที่ถูกลบส่งผลกระทบเฉพาะ Keys ในช่วงของมัน Keys จาก Server ที่ถูกลบจะถูกกำหนดใหม่ไปยัง Server ถัดไปทวนเข็มนาฬิกา
ความท้าทายและวิธีแก้ไข
สองปัญหาในวิธีพื้นฐาน
- ขนาด Partitions ไม่เท่ากัน: Servers อาจมี Data Partitions ที่ไม่เท่ากัน
- การกระจาย Keys ไม่สม่ำเสมอ: บาง Servers อาจได้รับ Keys มากกว่า Others อย่างมีนัยสำคัญ
วิธีแก้ไข: Virtual Nodes
ภาพที่ 3: Virtual Nodes ช่วยกระจายโหลดอย่างสม่ำเสมอ
Virtual Nodes (หรือ VNodes) ช่วยแก้ปัญหาเหล่านี้:
- แต่ละ Server ถูกแทนด้วย Virtual Nodes หลายตัวบน Ring
- Virtual Nodes ปรับปรุงการกระจาย Keys และสมดุล Load
- เมื่อจำนวน Virtual Nodes เพิ่มขึ้น การกระจายของ Keys จะสม่ำเสมอมากขึ้น
Affected Keys
เมื่อ Servers ถูกเพิ่มหรือลบ:
- Server ที่เพิ่ม: Keys ที่ได้รับผลกระทบคือ Keys ระหว่าง Server ใหม่และ Predecessor ของมัน
- Server ที่ลบ: Keys ที่ได้รับผลกระทบคือ Keys ระหว่าง Server ที่ลบและ Predecessor ของมัน
ข้อดีของ Consistent Hashing
การใช้งานในโลกจริง
- Amazon Dynamo DB
- Apache Cassandra
- Discord
- Akamai CDN
- Google Maglev Load Balancer
เนื้อหานี้อ้างอิงจาก ByteByteGo - System Design Interview - An Insider's Guide