Consistent hashing: server বাড়ালে সব নড়ে না কেন
সাধারণ hash-mod-N একটি server যোগ করলে প্রায় সব key নতুন জায়গায় পাঠায়। Consistent hashing অল্প অংশই নাড়ায়। Ring কীভাবে কাজ করে, দেখুন।
ধরুন cache key N টি server-এ ছড়াচ্ছেন server = hash(key) mod N দিয়ে। N না বদলানো পর্যন্ত ঠিক চলে। ৪টি থেকে ৫টি server করলে বেশিরভাগ key অন্য server-এ চলে যায়, cache খালি দেখায় আর database-এ চাপ পড়ে।
ধারণাটা
Consistent hashing server ও key দুটোকেই একটি বৃত্তে (hash ring) বসায়, যেমন ০ থেকে 2^32 পরিসর।
- প্রতিটি server-এর নাম hash করে ring-এর একটি বিন্দুতে বসান।
- প্রতিটি key hash করে ring-এ বসান।
- Key-টি তার বিন্দু থেকে ঘড়ির কাঁটার দিকে প্রথম পাওয়া server-এর।
কেন কাজে লাগে
- Server যোগ: শুধু নিজের ও বিপরীত দিকের প্রতিবেশীর মাঝের key নেয়। গড়ে মাত্র প্রায় 1/N key নড়ে।
- Server বাদ: শুধু তার key-গুলো ঘড়ির দিকের পরের server-এ যায়। বাকিরা অক্ষত।
Virtual node
অল্প বিন্দু থাকলে ring-এর ভাগ অসম হয়। সমাধান virtual node: প্রতিটি physical server ring-এ অনেক বিন্দুতে (যেমন ১০০ থেকে ২০০) থাকে। এতে load সমান হয়, আর শক্তিশালী server-কে বেশি virtual node দেওয়া যায়।
Ring-এ replication
কপি রাখতে প্রতিটি key ঘড়ির দিকে পরের কয়েকটি আলাদা server-এ রাখুন। Dynamo-ধাঁচের database এটি করে।
কোথায় ব্যবহার হয়
Distributed cache, sharded database, CDN, sticky routing লাগে এমন load balancer, এবং Cassandra ও DynamoDB-এর মতো সিস্টেম।
সীমাবদ্ধতা
গড়ে ভালো ভারসাম্য দেয়, কিন্তু খুব জনপ্রিয় একটি key তার server-কে তবুও ডুবাতে পারে। Hot key replicate বা ভাগ করলে সাহায্য হয়।
মূল কথা: server-এর সংখ্যা বদলায় আর সব data নতুন করে ঘাঁটা পোষায় না, এমন জায়গায় consistent hashing ব্যবহার করুন।
System Design সিরিজের 10 নম্বর পর্ব (মোট ১৫)। আগের পর্ব: Database replication: leader-follower, lag ও failover.
