কনসিস্টেন্ট হ্যাশিং ডিজাইন (Design Consistent Hashing)

হরাইজন্টাল স্কেলিং (horizontal scaling) অর্জনের জন্য, সার্ভারগুলোর মধ্যে রিকোয়েস্ট/ডেটা দক্ষতার সাথে এবং সমানভাবে বিতরণ করা অত্যন্ত গুরুত্বপূর্ণ। কনসিস্টেন্ট হ্যাশিং হলো এই লক্ষ্য অর্জনের জন্য একটি সাধারণত ব্যবহৃত কৌশল। কিন্তু প্রথমে, আসুন সমস্যাটির দিকে গভীরভাবে নজর দেই।

রিহ্যাশিং সমস্যা (The rehashing problem)

আপনার যদি n সংখ্যক ক্যাশ সার্ভার থাকে, তবে লোড ব্যালেন্স করার একটি সাধারণ উপায় হলো নিচের হ্যাশ পদ্ধতি ব্যবহার করা:

serverIndex = hash(key) % N, যেখানে N হলো সার্ভার পুলের সাইজ।

আসুন একটি উদাহরণের মাধ্যমে দেখি এটি কীভাবে কাজ করে। টেবিল ১-এ দেখানো হয়েছে, আমাদের ৪টি সার্ভার এবং ৮টি স্ট্রিং কী (string keys) আছে যাদের হ্যাশ ভ্যালু দেওয়া আছে।

টেবিল ১

একটি কী যে সার্ভারে সংরক্ষিত আছে তা খুঁজে পেতে, আমরা মডুলার অপারেশন f(key) % 4 সম্পাদন করি। উদাহরণস্বরূপ, hash(key0) % 4 = 1 এর অর্থ হলো ক্যাশ করা ডেটা আনতে একটি ক্লায়েন্টকে অবশ্যই সার্ভার ১-এর সাথে যোগাযোগ করতে হবে। চিত্র ১ টেবিল ১-এর ওপর ভিত্তি করে কীগুলোর বিন্যাস দেখায়।

[চিত্র ১-এর বর্ণনা: ছবিটি চারটি সার্ভার জুড়ে কী বিতরণ করার জন্য একটি সাধারণ কনসিস্টেন্ট হ্যাশিং স্কিম উপস্থাপন করে। উপরের লাইনটি serverIndex = hash % 4 সূত্রটি দেখায়, যা নির্দেশ করে যে একটি কীর হ্যাশ ভ্যালু (সম্ভবত কীটি থেকে তৈরি একটি সাংখ্যিক উপস্থাপনা) কোন সার্ভারে (0-3 ইনডেক্সযুক্ত) অ্যাসাইন করা হয়েছে তা নির্ধারণ করতে মডুলো-4 করা হয়েছে। নিচে, চারটি সার্ভার (server 0, server 1, server 2, server 3) রঙিন বাক্স হিসাবে দেখানো হয়েছে, প্রতিটি একটি সার্ভার ইনডেক্সের (যথাক্রমে 0, 1, 2, 3) সাথে যুক্ত। সার্ভারগুলোর নিচে, কীগুলোর একটি তালিকা (key1, key0, key2, key5, key6, key7) দেখানো হয়েছে, যেখানে কিছু কী (যেমন, key1, key0) তাদের বোঝানো হ্যাশ ভ্যালু এবং মডুলো অপারেশনের ওপর ভিত্তি করে নির্দিষ্ট সার্ভারগুলোর সাথে দৃশ্যত যুক্ত। ‘keover does not luppo full SVG ikey6’ টেক্সটটি key6-এর সাথে যুক্ত একটি ত্রুটিপূর্ণ বা অসম্পূর্ণ লেবেল বলে মনে হচ্ছে, যা ছবির OCR-এর একটি সম্ভাব্য সমস্যার ইঙ্গিত দেয়। সামগ্রিক ডায়াগ্রামটি একটি মৌলিক লোড ব্যালেন্সিং কৌশল চিত্রিত করে যেখানে কনসিস্টেন্ট হ্যাশিং অ্যালগরিদম ব্যবহার করে কীগুলো সার্ভার জুড়ে বিতরণ করা হয় যাতে সমান বিন্যাস নিশ্চিত হয় এবং রি-ব্যালেন্সিংয়ের সময় ডেটা মুভমেন্ট কমানো যায়।] চিত্র ১

সার্ভার পুলের সাইজ নির্দিষ্ট থাকলে এবং ডেটা বিন্যাস সমান হলে এই পদ্ধতিটি ভালো কাজ করে। তবে, যখন নতুন সার্ভার যোগ করা হয় বা বিদ্যমান সার্ভার সরিয়ে ফেলা হয়, তখন সমস্যা দেখা দেয়। উদাহরণস্বরূপ, যদি সার্ভার ১ অফলাইন হয়ে যায়, তবে সার্ভার পুলের সাইজ হয়ে যায় ৩। একই হ্যাশ ফাংশন ব্যবহার করলে, একটি কীর জন্য আমরা একই হ্যাশ ভ্যালু পাই। কিন্তু মডুলার অপারেশন প্রয়োগ করলে আমরা ভিন্ন সার্ভার ইনডেক্স পাই কারণ সার্ভারের সংখ্যা ১ কমে গেছে। আমরা hash % 3 প্রয়োগ করে টেবিল ২-এর মতো ফলাফল পাই:

টেবিল ২

চিত্র ২ টেবিল ২-এর ওপর ভিত্তি করে কীগুলোর নতুন বিন্যাস দেখায়।

[চিত্র ২-এর বর্ণনা: ছবিটি তিনটি সার্ভার জুড়ে কী বিতরণ করার জন্য একটি সাধারণ কনসিস্টেন্ট হ্যাশিং স্কিম উপস্থাপন করে। উপরের লাইনটি serverIndex = hash % 3 সূত্রটি দেখায়, যা নির্দেশ করে যে এর হ্যাশ ভ্যালু (মডুলো ৩) এর অ্যাসাইনকৃত সার্ভার নির্ধারণ করে। নিচে, ‘Server Index’ লেবেলগুলো 0, 1, এবং 2 সার্ভার ইনডেক্স নির্দেশকারী কলামগুলোকে নির্দেশ করে। প্রতিটি ইনডেক্সের সাথে সামঞ্জস্যপূর্ণ একটি লেবেলযুক্ত সার্ভার বাক্স (‘server 0’, ‘server 1’, ‘server 2’, এবং ‘server 3’ যদিও হ্যাশিং স্কিমে কেবল তিনটি ব্যবহার করা হয়) রয়েছে। ‘Keys’ বিভাগটি উদাহরণ কীগুলো (‘key0’, ‘key1’, ‘key2’, ‘key3’, ‘key4’, ‘key5’, ‘key6’) তালিকাভুক্ত করে যা তাদের হ্যাশ ভ্যালুর ওপর ভিত্তি করে সার্ভারগুলোর মধ্যে বিতরণ করা হবে। উদাহরণস্বরূপ, hash('key0') % 3 সম্ভবত 0 ফলাফল দেবে, যা key0-কে server 0-এ অ্যাসাইন করবে এবং অন্যান্য কীর জন্যও একইভাবে কাজ করবে। দৃশ্যমান বিন্যাসটি মডুলো অপারেশন ব্যবহার করে সার্ভারগুলোর সাথে কীগুলোর একটি ধারণাগত ম্যাপিং দেখায়। ‘server 3’-এর উপস্থিতি বর্তমান তিন-সার্ভার সেটআপের বাইরে সম্ভাব্য ভবিষ্যৎ সম্প্রসারণের ইঙ্গিত দেয়।] চিত্র ২

চিত্র ২-এ দেখানো হয়েছে, বেশিরভাগ কী পুনরায় বিন্যস্ত (redistributed) করা হয়েছে, শুধু অফলাইন হওয়া সার্ভারে (সার্ভার ১) সংরক্ষিত কীগুলোই নয়। এর অর্থ হলো, যখন সার্ভার ১ অফলাইন হয়ে যায়, তখন বেশিরভাগ ক্যাশ ক্লায়েন্ট ডেটা আনতে ভুল সার্ভারের সাথে সংযোগ করবে। এটি ক্যাশ মিসের (cache misses) একটি ঝড় সৃষ্টি করে। কনসিস্টেন্ট হ্যাশিং হলো এই সমস্যা প্রশমিত করার একটি কার্যকর কৌশল।