Distributed Unique ID Generator (Snowflake) ডিজাইন

প্রতিটা বড় সিস্টেমে একটা মৌলিক দরকার—প্রতিটা row, message, order, বা event-এর জন্য একটা unique ID। single database-এ AUTO_INCREMENT দিয়েই কাজ চলে যায়। কিন্তু যখন তোমার ১০টা database shard আর ৫০টা সার্ভার, তখন? আজ আমরা Snowflake-স্টাইল distributed ID generator ডিজাইন করব।

১. সমস্যা বোঝা (Requirements)

Functional Requirements:

• প্রতিটা ID globally unique হতে হবে।
• ID হবে 64-bit (একটা BIGINT/long-এ ধরে যায়, index-friendly)।
• ID গুলো roughly time-sortable—অর্থাৎ পরে তৈরি ID আগের ID-র চেয়ে বড়।
• শুধু সংখ্যা (numeric), যাতে DB index ছোট ও দ্রুত হয়।

Non-functional Requirements:

• High throughput: সেকেন্ডে হাজার-হাজার ID, ideally কোনো network call ছাড়াই (local generation)।
• Low latency: ID তৈরি হবে মাইক্রোসেকেন্ডে।
• High availability: কোনো single point of failure থাকবে না।
• Scalable: নতুন সার্ভার/node যোগ করা সহজ হবে।

কেন auto-increment distributed-এ চলে না?

• Collision: প্রতিটা node নিজে increment করলে দুটো node একই ID দিতে পারে।
• Coordination bottleneck: এক central counter থেকে সবাই নিলে সেটাই bottleneck আর single point of failure।
• Sharding-এ অসম্ভব: ১০টা shard থাকলে কে কোন রেঞ্জ পাবে তা manage করা ভঙ্গুর।
• Security/business leak: ক্রমিক ID দেখে প্রতিযোগী আন্দাজ করতে পারে দিনে কত order হচ্ছে।

২. স্কেল আন্দাজ (Estimation)

ধরি peak load: 10,000 ID/সেকেন্ড per machine
machine সংখ্যা: 1024 (machine ID 10 bit = 2^10)

মোট ক্ষমতা: 1024 × প্রতি ms-এ sequence

Snowflake bit layout (64 bit):
  1 bit   → sign (সবসময় 0, positive)
  41 bit  → timestamp (millisecond, custom epoch থেকে)
  10 bit  → machine ID (2^10 = 1024 node)
  12 bit  → sequence (2^12 = 4096 ID প্রতি ms প্রতি machine)

প্রতি machine প্রতি ms: 4096 ID
প্রতি machine প্রতি সেকেন্ড: 4096 × 1000 = 4,096,000 ID
1024 machine মিলে: ~4.1 বিলিয়ন ID/সেকেন্ড  → প্রচুর headroom

41-bit timestamp আয়ু:
  2^41 ms ≈ 2.2 × 10^12 ms ≈ 69 বছর
  custom epoch ব্যবহার করলে (যেমন 2020 থেকে) → 2089 পর্যন্ত চলবে

৩. API ডিজাইন

# একটা নতুন unique ID জেনারেট করা (local, no network)
generateId() -> long

# ID থেকে অংশগুলো বের করা (debug/analytics-এর জন্য)
parseId(id: long) -> {
  timestamp: long,   # epoch থেকে millisecond
  machineId: int,
  sequence: int
}

লক্ষ্য করো—generateId() কোনো network বা DB call করে না, পুরোটা in-process হয়। এটাই Snowflake-এর সবচেয়ে বড় শক্তি।

৪. ডেটা মডেল

Snowflake-এর সৌন্দর্য হলো এর কোনো persistent table লাগে না—ID তৈরি হয় bit manipulation দিয়ে। তবে প্রতিটা node-এর in-memory state ও machine ID assignment থাকে।

Field	Bits	মান (range)	উদ্দেশ্য
sign	1	সবসময় 0	সংখ্যা positive রাখা
timestamp	41	0 – 2.2T ms	time ordering, ~69 বছর
machine ID	10	0 – 1023	কোন node বানিয়েছে
sequence	12	0 – 4095	একই ms-এ একাধিক ID আলাদা করা

Machine ID কোথা থেকে আসে? ZooKeeper/etcd থেকে startup-এ একটা unique machine ID lease নেওয়া হয় (যাতে দুই node একই machine ID না পায়)। বিকল্পে Kubernetes pod ordinal বা config থেকেও আসতে পারে। এই assignment-এর জন্য একটা ছোট coordination store যথেষ্ট—runtime-এ কোনো call লাগে না।

৫. হাই-লেভেল ডিজাইন

প্রতিটা application server-এর ভেতরেই একটা ID generator library থাকে। flow:

1. Startup-এ machine ID নাও — ZooKeeper/etcd থেকে unique 10-bit ID lease।
2. generateId() কল হলে:
   • বর্তমান সময় নাও (currentMillis)।
   • যদি এই ms-এ আগে ID দেওয়া হয়ে থাকে → sequence ১ বাড়াও।
   • যদি sequence 4095 ছাড়িয়ে যায় (এই ms-এ আর জায়গা নেই) → পরের ms পর্যন্ত busy-wait করো।
   • নতুন ms হলে sequence 0 থেকে শুরু।
3. Bit shift দিয়ে জোড়া লাগাও:

id = ((currentMillis - epoch) << 22)
   | (machineId << 12)
   | sequence

timestamp সবচেয়ে উপরে থাকায় বড় ID = নতুন ID, তাই sort করলেই time order।

৬. গভীরে (Deep Dive)

৬.১ Sequence ও একই ms-এ একাধিক ID

একই millisecond-এ একই machine অনেক ID চাইতে পারে। তাই 12-bit sequence counter—এক ms-এ 4096টা পর্যন্ত আলাদা ID। logic:

• নতুন request-এর currentMillis == lastMillis হলে: sequence = (sequence + 1) & 0xFFF (12-bit mask)।
• mask করার পর 0 হয়ে গেলে মানে overflow—তখন পরের millisecond না আসা পর্যন্ত while (now <= lastMillis) now = currentMillis() দিয়ে wait।
• নতুন ms এলে sequence reset হয়ে 0।

এই পুরো block thread-safe হতে হবে (synchronized/atomic), কারণ একই machine-এ multiple thread একসাথে ID চাইতে পারে।

৬.২ Clock Skew ও Clock Going Backwards

এটাই Snowflake-এর সবচেয়ে নাজুক জায়গা। timestamp source হলো system clock, আর NTP sync বা VM migration-এ ঘড়ি হঠাৎ পিছিয়ে যেতে পারে।

• যদি currentMillis < lastMillis (ঘড়ি পিছিয়েছে), পুরোনো timestamp দিয়ে ID দিলে আগের কোনো ID-র সাথে collision হতে পারে।
• নিরাপদ আচরণ: ছোট পিছিয়ে গেলে (যেমন কয়েক ms) ঘড়ি catch up না করা পর্যন্ত wait করো। বড় পিছিয়ে গেলে error throw করে ওই node-কে ID দেওয়া থেকে বিরত রাখো।

৬.৩ Snowflake vs UUID

বৈশিষ্ট্য	UUID (v4)	Snowflake
সাইজ	128-bit	64-bit
Sortable?	না (random)	হ্যাঁ (time-ordered)
Coordination	লাগে না	machine ID assignment লাগে
DB index	বড়, random write → fragmentation	ছোট, sequential → দ্রুত
তথ্য বহন	না	timestamp + machine বের করা যায়

UUIDv4 পুরো random—কোনো coordination লাগে না, কিন্তু 128-bit বড় এবং random হওয়ায় B-tree index-এ insert হলে page fragmentation ও খারাপ performance দেয়। Snowflake 64-bit, sequential, তাই index-friendly—তবে machine ID assign করার একটা ছোট দাম দিতে হয়। (নোট: UUIDv7 সম্প্রতি time-ordered হওয়ায় Snowflake-এর কাছাকাছি সুবিধা দেয়।)

৭. বটলনেক ও স্কেলিং

• Machine ID সীমা (1024): 10 bit-এ মাত্র 1024 node। আরও লাগলে bit reallocate করা যায় (যেমন machine 12-bit, sequence 10-bit)—trade-off বুঝে।
• Clock dependency: পুরো সিস্টেম system clock-এর উপর নির্ভর; NTP ঠিকমতো configure করা জরুরি (slew mode, step নয়)।
• Sequence overflow: এক ms-এ 4096-র বেশি ID দরকার হলে busy-wait latency বাড়ায়—তখন একাধিক node-এ load ছড়াও।
• Centralized বিকল্প: খুব high availability চাইলে এক central generator bottleneck হয়; তাই Snowflake-এর decentralized মডেলই scale-এ জেতে।
• Ticket server বিকল্প: Flickr-এর মতো একটা/দুটো MySQL ticket server (replace into) দিয়েও ID দেওয়া যায়, কিন্তু সেটা network round-trip যোগ করে—Snowflake local হওয়ায় এগিয়ে।

৮. সারসংক্ষেপ

Snowflake একটা সরল কিন্তু শক্তিশালী আইডিয়া: ৬৪ bit-কে timestamp + machine ID + sequence-এ ভাগ করো, সবচেয়ে উপরে timestamp রাখো যাতে ID sortable হয়, আর machine ID-র জন্য একবারই coordination করো—runtime-এ কখনো নয়। ফলে কোনো network call ছাড়াই unique, sortable, 64-bit ID—প্রায় unlimited throughput-এ।