মৌলিক পদ্ধতির দুটি সমস্যা (Two issues in the basic approach)

কনসিস্টেন্ট হ্যাশিং অ্যালগরিদমটি MIT-এর Karger এবং তার সহকর্মীদের দ্বারা প্রবর্তন করা হয়েছিল [1]। মৌলিক ধাপগুলো হলো:

• একটি ইউনিফর্মলি ডিস্ট্রিবিউটেড (uniformly distributed) হ্যাশ ফাংশন ব্যবহার করে রিং-এ সার্ভার এবং কী ম্যাপ করা।
• একটি কী কোন সার্ভারে ম্যাপ করা হয়েছে তা খুঁজে পেতে, কীর অবস্থান থেকে ঘড়ির কাঁটার দিকে রিং-এ প্রথম সার্ভারটি না পাওয়া পর্যন্ত এগিয়ে যান।

এই পদ্ধতির সাথে দুটি সমস্যা চিহ্নিত করা হয়েছে। প্রথমত, একটি সার্ভার যোগ বা সরানো হতে পারে বিবেচনা করে রিং-এর সমস্ত সার্ভারের জন্য সমান সাইজের পার্টিশন রাখা অসম্ভব। একটি পার্টিশন হলো পাশাপাশি দুটি সার্ভারের মধ্যবর্তী হ্যাশ স্পেস। এটি সম্ভব যে রিং-এ প্রতিটি সার্ভারের জন্য বরাদ্দকৃত পার্টিশনের সাইজ খুব ছোট বা বেশ বড় হতে পারে। চিত্র ১০-এ, যদি s1 সরিয়ে ফেলা হয়, তবে s2-এর পার্টিশন (দ্বিমুখী তীর চিহ্ন দ্বারা হাইলাইট করা) s0 এবং s3-এর পার্টিশনের চেয়ে দ্বিগুণ বড়।

[চিত্র ১০-এর বর্ণনা: ছবিটি চারটি সার্ভারের (s0, s1, s2, s3) একটি বৃত্তাকার বিন্যাস উপস্থাপন করে যা রঙিন বৃত্ত হিসাবে চিত্রিত, যাদের ‘s’ এবং একটি সংখ্যা দিয়ে লেবেল করা হয়েছে। এই সার্ভারগুলো একটি ধূসর বৃত্তাকার পথে অবস্থান করে। বাম দিকে, ‘Servers’ লেবেলযুক্ত রঙিন আয়তক্ষেত্রাকার বাক্সগুলোর একটি উল্লম্ব স্ট্যাক ‘server 0,’ ‘server 1,’ ‘server 2,’ এবং ‘server 3’ তালিকাভুক্ত করে, যা স্পষ্টত রিং-এর রঙিন বৃত্তগুলোর সাথে সামঞ্জস্যপূর্ণ। একটি উজ্জ্বল গোলাপী বক্র তীর চিহ্ন ডেটা প্রবাহ নির্দেশ করে, যা সার্ভার s1 থেকে শুরু হয়ে সার্ভার s2-এ এবং তারপর সার্ভার s0-এ চলতে থাকে। টেক্সট ‘s0 = server 0s1…’ নির্দেশ করে যে সার্ভার s0-এর পরিচয়ে সার্ভার 0 এবং 1 থেকে তথ্য অন্তর্ভুক্ত। নিচে, একটি বার্তা ‘Viewer does not support full SVG 1.1’ ডায়াগ্রামের সম্পূর্ণ ভিজ্যুয়াল বিবরণ রেন্ডার করার একটি সীমাবদ্ধতা নির্দেশ করে।] চিত্র ১০

দ্বিতীয়ত, রিং-এ কীগুলোর একটি অসম বিন্যাস (non-uniform key distribution) হতে পারে। উদাহরণস্বরূপ, যদি সার্ভারগুলো চিত্র ১১-এ তালিকাভুক্ত অবস্থানে ম্যাপ করা হয়, তবে বেশিরভাগ কী সার্ভার 2-এ সংরক্ষিত হয়। তবে, সার্ভার 1 এবং সার্ভার 3-এ কোনো ডেটা নেই।

[চিত্র ১১-এর বর্ণনা: ছবিটি সার্ভারগুলোর একটি বৃত্তাকার বিন্যাস উপস্থাপন করে, যা একটি ধূসর রিং হিসাবে চিত্রিত যার মধ্যে রঙিন নোড পৃথক সার্ভার নির্দেশ করে। রিং-এর পরিধি বরাবর চারটি রঙিন নোড, s0, s1, s2, এবং s3 লেবেলযুক্ত, প্রতিটি একটি নির্দিষ্ট সার্ভার নির্দেশ করে। s0 হালকা বেগুনি, s1 হালকা নীল, s2 গোলাপী, এবং s3 হালকা কমলা। s0-এর পাশে একটি টেক্সট অ্যানোটেশন স্পষ্ট করে যে s0 server 0s1...-এর সাথে সামঞ্জস্যপূর্ণ, যা একটি নামকরণ প্রথা নির্দেশ করে। রিং-এর সাথে সাথে রঙিন নোডগুলোর মাঝখানে চারটি রঙহীন, সাদা বৃত্ত রয়েছে, যা সম্ভাব্য অতিরিক্ত সার্ভার অবস্থান বা সংযোগ পয়েন্ট নির্দেশ করে। বৃত্তাকার বিন্যাসের বাম দিকে, একটি উল্লম্ব তালিকা চারটি আয়তক্ষেত্রাকার বাক্স প্রদর্শন করে, যাদের প্রতিটি যথাক্রমে server 0, server 1, server 2, এবং server 3 লেবেলযুক্ত, যা রিং-এর নোডগুলোর কালার স্কিমের প্রতিফলন ঘটায় এবং তাদের শনাক্তকরণের জন্য একটি কী (key) প্রদান করে। ছবির নিচে একটি বার্তা রয়েছে যা নির্দেশ করে যে ভিউয়ার সম্পূর্ণ SVG 1.1 সমর্থন করে না। সামগ্রিক ডায়াগ্রামটি একটি রিং টপোলজি বা একটি ডিস্ট্রিবিউটেড সিস্টেম নির্দেশ করে যেখানে সার্ভারগুলো একটি বৃত্তাকার ফ্যাশনে আন্তঃসংযুক্ত।] চিত্র ১১

এই সমস্যাগুলো সমাধান করতে ভার্চুয়াল নোড (virtual nodes) বা রেপ্লিকা নামক একটি কৌশল ব্যবহার করা হয়।

ভার্চুয়াল নোড (Virtual nodes)

একটি ভার্চুয়াল নোড আসল নোডকে নির্দেশ করে, এবং প্রতিটি সার্ভার রিং-এ একাধিক ভার্চুয়াল নোড দ্বারা প্রতিনিধিত্ব করা হয়। চিত্র ১২-এ, সার্ভার 0 এবং সার্ভার 1 উভয়েরই 3টি করে ভার্চুয়াল নোড আছে। 3টি স্বেচ্ছাচারীভাবে বেছে নেওয়া হয়েছে; এবং বাস্তব-বিশ্বের সিস্টেমে, ভার্চুয়াল নোডের সংখ্যা অনেক বেশি থাকে। s0 ব্যবহার করার পরিবর্তে, আমাদের কাছে রিং-এ সার্ভার 0-কে প্রতিনিধিত্ব করতে s0_0, s0_1, এবং s0_2 আছে। একইভাবে, s1_0, s1_1, এবং s1_2 রিং-এ সার্ভার 1-কে প্রতিনিধিত্ব করে। ভার্চুয়াল নোডের সাথে, প্রতিটি সার্ভার একাধিক পার্টিশনের জন্য দায়ী থাকে। s0 লেবেলযুক্ত পার্টিশনগুলো (edges) সার্ভার 0 দ্বারা পরিচালিত হয়। অন্যদিকে, s1 লেবেলযুক্ত পার্টিশনগুলো সার্ভার 1 দ্বারা পরিচালিত হয়।

[চিত্র ১২-এর বর্ণনা: ছবিটি একটি রিং টপোলজি ব্যবহার করে দুটি সার্ভারের (যাদের ‘server 0’ এবং ‘server 1’ লেবেলযুক্ত) মধ্যে ডেটা প্রবাহ চিত্রিত করে এমন একটি সিস্টেম আর্কিটেকচার ডায়াগ্রাম উপস্থাপন করে। ডায়াগ্রামটি নোডগুলোর একটি বৃত্তাকার বিন্যাস দেখায়, যেখানে চারটি নোড বেগুনি রঙের (s0_0, s0_1, s0_2 লেবেলযুক্ত, সার্ভার 0-এর ডেটা নির্দেশ করে) এবং চারটি নোড হালকা নীল রঙের (s1_0, s1_1, s1_2 লেবেলযুক্ত, সার্ভার 1-এর ডেটা নির্দেশ করে)। একটি পুরু গাঢ় ধূসর রেখা এই নোডগুলোকে বৃত্তাকারভাবে সংযুক্ত করে, যা মূল ডেটা পাথওয়ে নির্দেশ করে। পাতলা রেখা, হালকা বেগুনি এবং হালকা নীল রঙের, নির্দিষ্ট নোডগুলোর মধ্যে ডেটা স্থানান্তর চিত্রিত করে। হালকা বেগুনি রেখা (s0 লেবেলযুক্ত) সার্ভার 0 থেকে উৎপন্ন ডেটা প্রবাহ নির্দেশ করে, যখন হালকা নীল রেখা (s1 লেবেলযুক্ত) সার্ভার 1 থেকে ডেটা প্রবাহ নির্দেশ করে। উদাহরণস্বরূপ, একটি হালকা বেগুনি রেখা s0_2 থেকে s1_2-এ সংযুক্ত, যা সার্ভার 0-এর দ্বিতীয় ডেটা পয়েন্ট থেকে সার্ভার 1-এর দ্বিতীয় ডেটা পয়েন্টে ডেটা স্থানান্তর নির্দেশ করে। একইভাবে, একটি হালকা নীল রেখা s1_0 থেকে s0_0-এ সংযুক্ত, যা বিপরীত দিকে ডেটা স্থানান্তর দেখায়। টেক্সট ‘s0 = server 0s1…’ নির্দেশ করে যে s0 লেবেলগুলো উভয় সার্ভার থেকে ডেটা সমন্বিত একটি সমন্বিত ডেটা শনাক্তকারী নির্দেশ করে। নিচে একটি নোট নির্দেশ করে যে ভিউয়ার ডায়াগ্রামে ব্যবহৃত SVG ফরম্যাটকে সম্পূর্ণরূপে সমর্থন করে না।] চিত্র ১২

একটি কী কোন সার্ভারে সংরক্ষিত আছে তা খুঁজে পেতে, আমরা কীর অবস্থান থেকে ঘড়ির কাঁটার দিকে যাই এবং রিং-এ প্রথম যে ভার্চুয়াল নোডটির সাথে দেখা হয় তা খুঁজে বের করি। চিত্র ১৩-এ, k0 কোন সার্ভারে সংরক্ষিত আছে তা খুঁজে পেতে, আমরা k0-এর অবস্থান থেকে ঘড়ির কাঁটার দিকে যাই এবং ভার্চুয়াল নোড s1_1 খুঁজে পাই, যা সার্ভার 1-কে নির্দেশ করে।

[চিত্র ১৩-এর বর্ণনা: ছবিটি দুটি সার্ভার, ‘server 0’ (বেগুনি) এবং ‘server 1’ (সায়ান) এবং একটি রিং-আকৃতির নেটওয়ার্কের সাথে তাদের মিথস্ক্রিয়া দেখায় এমন একটি সিস্টেম আর্কিটেকচার ডায়াগ্রাম উপস্থাপন করে। রিংটি ছয়টি নোড নিয়ে গঠিত: তিনটি s0_0, s0_1, s0_2 লেবেলযুক্ত (বেগুনি) সার্ভার 0-এর ইনস্ট্যান্স নির্দেশ করে, এবং তিনটি s1_0, s1_1, s1_2 লেবেলযুক্ত (সায়ান) সার্ভার 1-এর ইনস্ট্যান্স নির্দেশ করে। এই নোডগুলো একটি ধূসর বৃত্তাকার রেখার চারপাশে সাজানো, যা একটি রিং টপোলজি নির্দেশ করে। একটি পৃথক কালো নোড, k0 লেবেলযুক্ত, রিং-এর সাথে সংযুক্ত এবং এটির দিকে ফিরে যাওয়া একটি সেলফ-লুপিং তীর চিহ্ন রয়েছে, যা একটি কন্ট্রোল বা কোঅর্ডিনেশন ফাংশন নির্দেশ করে। উপরের ডানদিকে একটি টেক্সট অ্যানোটেশন স্পষ্ট করে যে s0 সার্ভার 0 ইনস্ট্যান্সগুলো নির্দেশ করে (0s1...), যা একটি নামকরণ প্রথা নির্দেশ করে। ডায়াগ্রামের নিচে একটি বার্তা প্রদর্শিত হয় যা নির্দেশ করে যে ভিউয়ার ইমেজ তৈরি করতে ব্যবহৃত SVG ফরম্যাটকে সম্পূর্ণরূপে সমর্থন করে না।] চিত্র ১৩

ভার্চুয়াল নোডের সংখ্যা বৃদ্ধির সাথে সাথে, কীগুলোর বিন্যাস আরও ভারসাম্যপূর্ণ হয়ে ওঠে। এর কারণ হলো আরও বেশি ভার্চুয়াল নোডের সাথে স্ট্যান্ডার্ড ডেভিয়েশন (standard deviation) ছোট হয়ে যায়, যা ভারসাম্যপূর্ণ ডেটা বিন্যাসের দিকে নিয়ে যায়। স্ট্যান্ডার্ড ডেভিয়েশন পরিমাপ করে ডেটা কতটা ছড়িয়ে আছে। অনলাইন গবেষণার [2] দ্বারা পরিচালিত একটি পরীক্ষার ফলাফল দেখায় যে, একশ বা দুইশ ভার্চুয়াল নোডের সাথে, স্ট্যান্ডার্ড ডেভিয়েশন গড়ের 5% (200 ভার্চুয়াল নোড) এবং 10% (100 ভার্চুয়াল নোড) এর মধ্যে থাকে। যখন আমরা ভার্চুয়াল নোডের সংখ্যা বৃদ্ধি করি তখন স্ট্যান্ডার্ড ডেভিয়েশন আরও ছোট হবে। তবে, ভার্চুয়াল নোড সম্পর্কিত ডেটা সংরক্ষণ করতে আরও বেশি জায়গার প্রয়োজন হয়। এটি একটি ট্রেড-অফ (tradeoff), এবং আমরা আমাদের সিস্টেমের প্রয়োজনীয়তা অনুযায়ী ভার্চুয়াল নোডের সংখ্যা টিউন করতে পারি।

প্রভাবিত কী খুঁজে বের করা (Find affected keys)

যখন একটি সার্ভার যোগ বা সরানো হয়, তখন ডেটার একটি অংশ পুনরায় বিন্যস্ত করতে হয়। কীগুলো পুনরায় বিন্যস্ত করার জন্য প্রভাবিত রেঞ্জ (affected range) কীভাবে খুঁজে বের করব?

চিত্র ১৪-এ, সার্ভার 4 রিং-এ যোগ করা হয়েছে। প্রভাবিত রেঞ্জটি s4 (নতুন যোগ করা নোড) থেকে শুরু হয় এবং রিং-এ ঘড়ির কাঁটার বিপরীত দিকে (anticlockwise) এগিয়ে যায় যতক্ষণ না একটি সার্ভার পাওয়া যায় (s3)। সুতরাং, s3 এবং s4-এর মধ্যে অবস্থিত কীগুলো s4-এ পুনরায় বিন্যস্ত করতে হবে।

[চিত্র ১৪-এর বর্ণনা: ছবিটি সার্ভার এবং কী নির্দেশকারী নোডগুলোর একটি বৃত্তাকার বিন্যাস উপস্থাপন করে। s0, s1, s2, s3, এবং s4 লেবেলযুক্ত পাঁচটি রঙিন নোড যথাক্রমে সার্ভার 0 থেকে 4 নির্দেশ করে, যাদের সংশ্লিষ্ট রঙ বাম দিকে আয়তক্ষেত্রাকার সার্ভার বাক্সগুলোর কিংবদন্তির সাথে মিলে যায়। k0, k1, k2, k3, এবং অন্তত k4 (যদিও স্পষ্টভাবে লেবেলযুক্ত নয়) লেবেলযুক্ত পাঁচটি কালো নোড কী নির্দেশ করে। একটি পুরু ধূসর চাপ সার্ভার নোডগুলোকে বৃত্তাকারভাবে সংযুক্ত করে। সলিড তীর চিহ্ন k0 থেকে s4-এর দিকে একটি নির্দেশিত সংযোগ নির্দেশ করে যার লেবেল ‘keyo’ এবং একটি ড্যাশ করা তীর চিহ্ন k0 থেকে s0-এ একটি সংযোগ দেখায়। আরেকটি ড্যাশ করা তীর চিহ্ন s4 থেকে s0-এর দিকে একটি সংযোগ দেখায়। টেক্সট ‘s0 = server 0s1…’ নির্দেশ করে যে s0 একটি সমন্বিত বা একত্রিত সার্ভার নির্দেশ করে। কীগুলো ধূসর চাপের দিকে সার্ভারগুলোর মাঝখানে অবস্থান করে। সামগ্রিক কাঠামোটি একটি রিং টপোলজি নির্দেশ করে যেখানে কীগুলো সম্ভবত সার্ভারগুলোর মধ্যে রাউটিং বা অ্যাক্সেস পয়েন্ট হিসাবে কাজ করে।] চিত্র ১৪

যখন একটি সার্ভার (s1) চিত্র ১৫-এ দেখানো হিসাবে সরিয়ে ফেলা হয়, তখন প্রভাবিত রেঞ্জটি s1 (সরানো নোড) থেকে শুরু হয় এবং রিং-এ ঘড়ির কাঁটার বিপরীত দিকে এগিয়ে যায় যতক্ষণ না একটি সার্ভার পাওয়া যায় (s0)। সুতরাং, s0 এবং s1-এর মধ্যে অবস্থিত কীগুলো s2-এ পুনরায় বিন্যস্ত করতে হবে।

[চিত্র ১৫-এর বর্ণনা: ছবিটি একটি ধূসর চাপ দ্বারা সংযুক্ত নোডগুলোর একটি বৃত্তাকার বিন্যাস উপস্থাপন করে, যা একটি রিং টপোলজি নির্দেশ করে। s0, s1, s2, এবং s3 লেবেলযুক্ত চারটি রঙিন নোড বাইরের চাপের দিকে অবস্থান করে, যা সার্ভার নির্দেশ করে। s0 হালকা বেগুনি, s1 হালকা নীল, s2 গোলাপী, এবং s3 হালকা কমলা। এই সার্ভার নোডগুলো আরও একটি টেক্সট অ্যানোটেশন দ্বারা চিহ্নিত করা হয়েছে যাতে বলা হয়েছে s0 = server 0s1..., যা একটি নামকরণ প্রথা নির্দেশ করে। চারটি কালো-ভরা নোড k0, k1, k2, এবং k3 ধূসর চাপ এবং কাল্পনিক ব্যাসার্ধের ছেদবিন্দুতে স্থাপন করা হয়েছে যা রঙিন সার্ভার নোডগুলোকে কেন্দ্রে সংযুক্ত করে। এই k নোডগুলো সম্ভবত সিস্টেমের মধ্যে কী উপাদান বা পয়েন্ট নির্দেশ করে। k2 থেকে s2-এর দিকে একটি পুরু কালো বক্র তীর চিহ্ন একটি একমুখী প্রবাহ বা নির্ভরতা নির্দেশ করে। বাম দিকে, ‘Servers’ লেবেলযুক্ত একটি আয়তক্ষেত্রাকার বাক্স রিং-এর s নোডগুলোর রঙের প্রতিফলন ঘটায় সার্ভার 0, 1, 2, এবং 3 নির্দেশকারী চারটি রঙিন আয়তক্ষেত্র তালিকাভুক্ত করে। ছবির নিচে একটি বার্তা রয়েছে যা নির্দেশ করে যে ভিউয়ার ডায়াগ্রাম তৈরি করতে ব্যবহৃত SVG ফরম্যাটকে সম্পূর্ণরূপে সমর্থন করে না।] চিত্র ১৫