ออกแบบ Unique ID Generator

บทนี้กล่าวถึงความท้าทายในการออกแบบ Unique ID Generator สำหรับ Distributed Systems โดยเน้นการสร้าง IDs ที่ไม่ซ้ำกันและเรียงลำดับตามวันที่ได้

บทนำ

การออกแบบ Unique ID Generator สำหรับ Distributed Systems เป็นความท้าทายที่สำคัญ Auto-increment Keys แบบดั้งเดิมไม่เหมาะสมในสภาพแวดล้อมแบบ Distributed เนื่องจากปัญหาการ Synchronize ความสนใจอยู่ที่การสร้าง IDs ที่ไม่ซ้ำกันและเรียงลำดับตามวันที่ขนาด 64-bit

ข้อกำหนด

• IDs ต้องไม่ซ้ำกันและเป็นตัวเลข
• IDs ต้องเรียงลำดับตามวันที่ (แต่ไม่จำเป็นต้องเพิ่มทีละ +1)
• IDs ต้องใส่ใน 64 bits
• ระบบต้องสร้าง มากกว่า 10,000 IDs ต่อวินาที

ตัวเลือก High-Level Design

แนวทาง Twitter Snowflake

ส่วนประกอบ

• Sign Bit (1 bit): คือ 0 เสมอ
• Timestamp (41 bits): Milliseconds since Custom Epoch (Twitter ใช้ 1288834974657)
• Datacenter ID (5 bits): ระบุได้ถึง 2^5 = 32 Datacenters
• Machine ID (5 bits): ระบุได้ถึง 2^5 = 32 Machines ภายในแต่ละ Datacenter
• Sequence Number (12 bits): ติดตาม IDs ที่สร้างบน Machine ใน Millisecond เดียวกัน รองรับถึง 2^12 = 4096 IDs ต่อ Millisecond

ข้อดี

ข้อพิจารณาเพิ่มเติม

1. Clock Synchronization

ความท้าทาย: ID Generation ตั้งสมมติฐานว่า Clocks ถูก Synchronize ข้าม Servers

วิธีแก้ไข: ใช้ Network Time Protocol (NTP) เพื่อลด Drift

2. Section Length Tuning

ปรับขนาด Sections (เช่น Bits Sequence น้อยลง, Bits Timestamp มากขึ้น) ตาม Use Case

3. High Availability

ID Generators เป็น Mission-critical และต้อง Fault-tolerant

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