প্ল্যানেটারি স্কেলের ক্লাউড প্ল্যাটফর্মে কোটি কোটি ডেটা কী (Key) কোন সার্ভারে সংরক্ষিত হবে তা কোনো একক কেন্দ্রীয় ডিরেক্টরি দিয়ে পরিচালনা করা অসম্ভব। কেন্দ্রীয় রাউটার ব্যর্থ হলে সমগ্র সিস্টেম ভেঙে পড়ে। অন্যদিকে প্রচলিত মডুলো হ্যাশিং ($mathcal{H}(k) pmod N$) পদ্ধতিতে ক্লাস্টারে একটি নতুন সার্ভার যুক্ত বা বিচ্ছিন্ন হলেই প্রায় সমস্ত ডেটার অবস্থান এলোমেলো হয়ে যায়। ১৯৯৭ সালে ডেভিড কার্গার এবং তাঁর সহকর্মীরা উদ্ভাবন করেন কনসিস্টেন্ট হ্যাশিং (Consistent Hashing)। এই যুগান্তকারী অ্যালগরিদম সার্ভার বৃদ্ধি বা হ্রাসের সময় ডেটা স্থানান্তরের পরিমাণকে মাত্র $O(K/N)$-এ সীমাবদ্ধ করে, যা অ্যামাজন ডায়নামো, অ্যাপাচি ক্যাসান্ড্রা, আকামাই CDN এবং বিটটরেন্টের মতো আধুনিক সিস্টেমের ভিত্তি স্থাপন করেছে।
১. প্রচলিত মডুলো হ্যাশিংয়ের ব্যর্থতা ও সার্কুলার রিং
সাধারণ সিস্টেমে ডেটার অবস্থান নির্ধারিত হয় এভাবে: $ ext{Node} = mathcal{H}(k) pmod N$। যখন নোড সংখ্যা $N$ পরিবর্তিত হয়ে $N+1$ বা $N-1$ হয়, তখন প্রায় সমস্ত ডেটা কী-এর মডুলো মান পরিবর্তিত হয়ে যায়। গাণিতিকভাবে প্রায় $1 – rac{1}{N}$ অংশ ডেটাকে ইন্টারনেটে এক সার্ভার থেকে অন্য সার্ভারে সরাতে হয়, যা ক্লাউড নেটওয়ার্কে ভয়াবহ ট্র্যাফিক জ্যাম সৃষ্টি করে।
কনসিস্টেন্ট হ্যাশিং রিং (Consistent Hash Ring)
কনসিস্টেন্ট হ্যাশিং সার্ভার এবং ডেটা কী—উভয়কেই একটি কাল্পনিক বৃত্তাকার হ্যাশ রিংয়ের (Hash Ring) পরিধিতে স্থাপন করে। যদি একটি ১২৮-বিট বা ১৬০-বিট হ্যাশ ফাংশন (যেমন SHA-1) ব্যবহার করা হয়, তবে রিংয়ের মান $0$ থেকে $2^b – 1$ পর্যন্ত বিস্তৃত থাকে:
- সার্ভার ম্যাপিং: প্রতিটি ফিজিক্যাল সার্ভারের আইপি অ্যাড্রেস হ্যাশ করে রিংয়ের একটি নির্দিষ্ট কোণে বসানো হয়: $h_n = mathcal{H}( ext{IP})$।
- কী ম্যাপিং: ডেটা কী-কে হ্যাশ করে রিংয়ের পরিধিতে নির্দিষ্ট বিন্দুতে বসানো হয়: $h_k = mathcal{H}(k)$।
- রাউটিং নিয়ম: একটি ডেটা কী ঘড়ির কাঁটার দিকে (Clockwise) এগিয়ে প্রথম যে সার্ভারকে পায়, সেই সার্ভারেই ডেটাটি সংরক্ষিত হয়।
যখন ক্লাস্টারে নতুন একটি সার্ভার যুক্ত হয়, তখন শুধুমাত্র তার নিকটবর্তী পূর্ববর্তী সার্ভারের কিছু ডেটা নতুন সার্ভারে স্থানান্তরিত হয়। বাকি সমস্ত সার্ভারের ডেটা সম্পূর্ণ অক্ষত থাকে। স্থানান্তরিত ডেটার পরিমাণ হয় অত্যন্ত কম:
$$mathbb{E}[ ext{Relocated Data}] = rac{K}{N+1}$$
২. হটস্পট সমস্যা ও ভার্চুয়াল নোড (Vnodes)
ফিজিক্যাল সার্ভারগুলোকে সরাসরি রিংয়ে বসালে হ্যাশ ফাংশনের অসম বণ্টনের কারণে কোনো কোনো সার্ভার রিংয়ের অনেক বড় অংশ দখল করে বসে, যার ফলে সেই সার্ভারে প্রচণ্ড চাপ (Hotspot) সৃষ্টি হয়।
এই সমস্যা দূর করতে ব্যবহৃত হয় ভার্চুয়াল নোড (Virtual Nodes বা Vnodes)। একটি ফিজিক্যাল সার্ভারকে রিংয়ে মাত্র একটি বিন্দুতে না রেখে শত শত কাল্পনিক টোকেনে ($V pprox 128 ext{ to }256$) ভাগ করে রিংয়ের বিভিন্ন স্থানে ছড়িয়ে দেওয়া হয়:
$$v_{i, j} = mathcal{H}( ext{NodeID}_i mathbin{Vert} j)$$
সেন্ট্রাল লিমিট থিওরেম অনুযায়ী, ভার্চুয়াল নোডের সংখ্যা বৃদ্ধির সাথে সাথে সার্ভারগুলোর মধ্যে কাজের বণ্টন প্রায় নিখুঁত সুষম রূপ ধারণ করে ($sigma propto 1/sqrt{V}$)। এছাড়াও কোনো ফিজিক্যাল সার্ভার ক্র্যাশ করলে তার লোড অন্য যেকোনো একটি সার্ভারের ওপর না পড়ে ক্লাস্টারের সমস্ত সার্ভারের মাঝে সমানভাবে বণ্টিত হয়।
৩. ক্যাডেমলিয়া DHT এবং XOR দূরত্ব মেট্রিক
সম্পূর্ণ বিকেন্দ্রীভূত পিয়ার-টু-পিয়ার নেটওয়ার্কে (যেমন Ethereum এবং BitTorrent) নোডগুলো কীভাবে একে অপরকে খুঁজে বের করে? এর উত্তর হলো ক্যাডেমলিয়া (Kademlia) DHT। ক্যাডেমলিয়া দুটি নোডের মধ্যবর্তী দূরত্ব নির্ণয়ে বিটওয়াইজ এক্সক্লুসিভ-অর (XOR) অপারেশন ব্যবহার করে:
$$d(x, y) = x oplus y$$
XOR মেট্রিকের প্রতিসমতা ($d(x,y) = d(y,x)$) এবং একমুখী অনন্যতার কারণে নোডগুলো তাদের রাউটিং টেবিলে ($k$-buckets) অত্যন্ত নির্ভরযোগ্যভাবে অন্যান্য নোডের তথ্য ক্যাশ করে রাখতে পারে এবং মাত্র $mathcal{O}(log N)$ নেটওয়ার্ক হপে যেকোনো ডেটা খুঁজে বের করতে সক্ষম হয়।
