ব্যাকএন্ড ইঞ্জিনিয়ারিং: কনসিস্টেন্ট হ্যাশিং

কনসিস্টেন্ট হ্যাশিং সার্ভারে লোড ব্যালেন্স করার একটি অ্যালগরিদম। এটা ব্যবহার করে নিশ্চিত করা হয় ডিস্ট্রিবিউটেড সিস্টেমে নতুন সার্ভার যোগ করলে বা কোন সার্ভার ডাউন হয়ে গেলে অন্যান্য সার্ভারের উপর যতটা সম্ভব কম প্রভাব পরে।  এই লেখায় আমি বেসিক হ্যাশিং নিয়ে তেমন আলোচনা করবো না, আমি আলোচনা করবো কনসিস্টেন্ট হ্যাশিং কিভাবে কাজ করে এবং কি ধরণের সমস্যা সমাধান করতে এটা কাজে লাগে সেটা নিয়ে।

শুরুতেই অ্যালগরিদম বর্ণনা করা আগে আমি কিছু ব্যাকগ্রাউন্ড দিয়ে শুরু করবো যাতে তুমি বুঝতে পারো ঠিক কোন সমস্যা সমাধান করার জন্য এটা ব্যবহার করা হয়। কনসিস্টেন্ট হ্যাশিং এর একটা খুবই কমন ব্যবহার হলো ডিস্ট্রিবিউটেড ক্যাশ এ কোন ডেটা কোথায় রাখা হবে সেটা ঠিক করা। আমরা সেটা নিয়েই আলোচনা করতে করতে কনসিস্টেন্ট হ্যাশিং নিয়ে জানবো।

ধরা যাক তুমি ইউটিউবের মতো একটা অ্যাপের মেইনটেইনার। তোমার কাছে একটা ডেটাবেসে অনেক ভিডিওর মেটাডেটা আছে। অর্থাৎ ভিডিওটার টাইটেল, ক্যাটাগরি, আপলোডার এসব তথ্য রাখা আছে। এটা যেকোন ধরণের ডেটাবেস হতে পারে, সেটা আমাদের আলোচনার বিষয় না।

সমস্যা হলো তোমার সাইটে ইউজার প্রচুর, কয়েক মিলিয়ন ইউজার প্রতি সেকেন্ডে তোমার অ্যাপে ভিডিও দেখে। প্রতিবার তোমার মেটাডেটা নিয়ে আসতে হয় ডেটাবেজ থেকে।  একসময় দেখলে ডেটাবেজ এত লোড সামলাতে পারছে না, তুমি কখন করলে কি, একটা ক্যাশ সার্ভার বসিয়ে দিলে ডেটাবেজের সামনে।

ক্যাশ সার্ভারের মেমরিতে তুমি ভিডিওগুলোর মেটাডেটা ক্যাশ করে রাখলে, যখন কারো ডেটা প্রয়োজন তখন আগে দেখলে ক্যাশে আছে নাকি, থাকলে সাথে সাথে রিটার্ন করলে, না থাকলে ডেটাবেস থেকে ডেটা এনে রিটার্ন করলে এবং সেই সাথে ডেটা ক্যাশে রেখে দিলে। তুমি এক্ষেত্রে LRU cache ব্যবহার করতে পারো, অন্য একটি লেখায় সেটা নিয়ে আলোচনা করেছি, আপাতত সেটা নিয়ে চিন্তা করার দরকার নাই।

তো কিছুদিন তোমার জীবন ভালোই চললো, কিন্তু এরপর দেখলে যে একটা সার্ভারে জায়গা হচ্ছে না। হয়তো তোমার সার্ভারে ৫০গিগাবাইট মেমরি আছে কিন্তু মেটাডেটা ডেটাবেসে ১৫০ গিগাবাইট ডেটা আছে।

ক্যাশ মিস রেট অনেক বেড়ে যাওয়ায় তুমি চিন্তা করলে একাধিক সার্ভারে ডেটা ক্যাশ করে রাখবে। এবং এখন তোমার সিস্টেমে জটিলটা শুরু!

এবার তুমি ৩টা ক্যাশ সার্ভারে ১৫০ গিগাবাইট ডেটা ভাগাভাগি করে রাখলে।  কিন্তু তোমার মনে হয়তো প্রশ্ন এসেছে, কোন ভিডিওর ডেটা কোন সার্ভারে থাকবে?  আমরা একটা ভিডিওর ডেটা একটামাত্র ক্যাশ সার্ভারেই রাখতে চাই, ডেটা রেপ্লিকেশন আজকের আলোচনার বাইরে।

মনে করো তোমার ক্যাশ সার্ভারের সংখ্যা $N$ এবং প্রতিটা সার্ভারকে $0$ থেকে $N – 1$ এর মধ্যে একটি সংখ্যা দিয়ে চিহ্নিত করা হয়েছে। $key$ ডিস্ট্রিবিউট করার একটা উপায় হলো $key$ এর হ্যাশ ভ্যালু বের করে $N$ দিয়ে ভাগশেষ (Modulus) বের করা। আমাদের উদাহরণে এই $key$ হবে video_id। এ কাজের জন্য আমরা sha256 জাতীয় কোন অ্যালগোরিদম ব্যবহার করে হ্যাশভ্যালু বের করতে পারি।

এখন আমরা সহজেই বের করতে পারবো কোন ভিডিওর মেটাডেটা কোন ক্যাশ সার্ভারে আছে।  সমস্যা হবে যদি আমাদের নতুন একটা সার্ভার অ্যাড করতে হয়। তখন আমাদের map_server_id ফাংশনে hash(video_id) ঠিকঠাক থাকলেও $N$ এর মান পরিবর্তন হয়ে যাবে। এতে করে অনেক ভিডিও আইডি আগে যে সার্ভারে হিট করছিলো সেখানে না করে অন্য আরেকটা সার্ভারে করবে।

হয়তো $100120$ নম্বর ভিডিওটা আগে সার্ভার $1$ এ হিট করছিলো, এখন হয়তো $2$ এ করবে এবং সেই নতুন সার্ভারে ভিডিওটা ক্যাশ করা নেই। আবার সার্ভার $1$ এ ভিডিওটা ক্যাশ করা আছে কিন্তু সেখানে এখন আর কেও খুজছে না। অর্থাৎ key গুলো remapped হয়ে গিয়েছে অন্য সার্ভারে।

একসময় অবশ্য পুরানো সার্ভারের ক্যাশ ডেটা এক্সপায়ার হয়ে যাবে এবং নতুন সার্ভারে রিকুয়েস্ট আসলে সেখানে ডেটা ক্যাশ হয়ে যাবে, কিন্তু মাঝখান দিয়ে বেশ কিছু সময় ক্যাশ হিট রেট খুব খারাপ থাকবে এবং তোমার সার্ভিসের পারফরমেন্সে সেটা প্রভাব ফেলবে।

একই সমস্যা হবে যদি কোন সার্ভার ডাউন হয়ে যায়।  ১০০টার মধ্যে একটা মাত্র সার্ভার ডাউন হলেই সব $key$ এর ম্যাপিং এলোমেলো হয়ে গিয়ে বাকি ৯৯টা সার্ভারের পারফরমেন্স খারাপ করে দিবে।  এখানেই কনসিস্টেন্ট হ্যাশিং আমাদের সাহায্য করতে পারে।

কনসিস্টেন্ট হ্যাশিং

আমরা কল্পনা করতে পারি আমাদের সার্ভারগুলো একটা বৃত্তের উপর বসানো আছে। পুরো বৃত্তটাকে $2^{32} – 1$ (INT_MAX) অংশে ভাগ করা হয়েছে। ভাগ করার পর ৩টা অংশে আমাদের সার্ভার ৩টাকে বসিয়ে দিয়েছি। নিচের ছবি দেখো:

এটাকে বলা হয় কনসিস্টেন্ট হ্যাশিং  রিং। বৃত্তের উপরে সার্ভারের লোকেশন পেতে হলে আমাদেরকে সার্ভারের কোনো একটা আইডেন্টিফায়ারকে হ্যাশ করে 2^32 – 1 দিয়ে মড করতে হবে, তাহলে বের হয়ে যাবে বৃত্তের কোথায় সার্ভারটি বসবে। এই আইডেন্টিফায়ার হতে পারে সার্ভারের আইপি অ্যাড্রেস বা অন্য কোন ডিভাইস আইডি।

এখন একই ভাবে কোন ভিডিও আইডি আসলে সেটাকেও আমরা বৃত্তের কোন অংশে ম্যাপিং করতে পারে একই হ্যাশ ফাংশন এবং মড ভ্যালু ব্যবহার করে।

আইডিয়াটা হলো key বা এক্ষেত্রে ভিডিও আইডিকে বৃত্তের উপরে ম্যাপিং করার পর আমরা বৃত্ত ক্লক-ওয়াইজ ঘুরতে থাকবে এবং কাছাকাছি যে সার্ভার পাবো সেই সার্ভার ওই key এর দায়িত্ব নিবে।

 

উপরের উদাহরণে $100120$ কে ম্যাপিং করে $0$ এবং $2$ নম্বর সার্ভারের মধ্যে একটা লোকেশন পেয়েছি, তাই $100120$ হিট করছে সার্ভার $2$ এ।  ক্লক-ওয়াইজের জায়গায় তুমি কাউন্টার ক্লক-ওয়াইজও ইমপ্লিমেন্ট করতে পারো, এটা তোমার ইচ্ছা।

এখন নতুন সার্ভার অ্যাড করলে কি ঘটবে? ধরা যাক আমি সার্ভার $3$ যোগ করছি, সেটা $0$ এবং $2$ এর মাঝে কোথাও বসেছে।

সার্ভার $3$ বসানোর পর $0$ এবং $2$ এর মাঝে ম্যাপিং হতো এমন কিছু key এখন $0$ এবং $3$ এর মাঝে ম্যাপিং হবে।  তারমানে আগে ক্যাশ সার্ভার $2$ এ হিট করতো এমন কিছু key এখন সার্ভার $3$ এ হিট করবে।  অন্য কোন সার্ভারের উপর এই নতুন সার্ভার যোগ করার কোন প্রভাব পরবে না।

কোনো সার্ভার করে ডাউন হয়ে গেলেও ঠিক একই ঘটনা, যদি সার্ভার $1$ ডাউন হয় তাহলে সেই সার্ভারের ট্রাফিক সার্ভার $0$ তে চলে যাবে, বাকি সার্ভারের উপর কোনো প্রভাব পড়বে না।

এটাই হলো কনসিস্টেন্ট হ্যাশিং এর বেসিক কনসেপ্ট। সাধারণ হ্যাশিং এর থেকে এর সুবিধা হলো সার্ভারের সংখ্যা বাড়া বা কমার ইমপেক্ট অনেকটা কমে যায়।

এই অ্যাপ্রোচে দুটি বড় সমস্যা আছে। সেটা নিয়ে এখন আলোচনা করবো।

সার্ভার লোকেশন ডিস্ট্রিবিউশন

একটা সমস্যা হলো সার্ভারের লোকেশন ডিস্ট্রিবিউশন। বৃত্তের উপর সার্ভারকে হ্যাশ করে ম্যাপিং করলে এক সার্ভার থেকে অন্য সার্ভারের মাঝে যে দূরত্ব সেটা সমান নাও হতে পারে। আমাদের উদাহরনে $0$ এবং $3$  এর মাঝখানে বেশ বড় একটা গ্যাপ কিন্তু $3$ এবং $2$ এর গ্যাপ বেশ ছোট। তারমানে অনেক বেশি key সার্ভার $3$ এ হিট করবে, সার্ভার $2$ তেমন ট্রাফিক পাবে না। তারমানে আমাদের একটা উপায় বের করতে হবে সব সার্ভারে প্রায় কাছাকাছি লোড রাখার।

ডোমিনো ইফেক্ট

এটা বেশ মজার একটা সমস্যা। ডোমিনো কি না জানলে নিচের ছবি দেখো:

কনসিস্টেন্ট হ্যাশিং এ একটা সার্ভার ডাউন হলে সেই সার্ভারের সমস্ত লোড পরের সার্ভারের উপর গিয়ে পরে। ধরা যাক সার্ভার 3 কোন কারণে ডাউন হয়ে গেল, এখন সব দায়িত্ব গিয়ে পড়লো সার্ভার $2$ এর উপরে। সার্ভার $2$ এই বাড়তি ট্রাফিক সামলাতে না পেরে নিজেই ডাউন হয়ে গেল! এখন সার্ভার 3 আর 2 এর দায়িত্ত গিয়ে পড়লো $1$ এর উপরে, $1$ এর উপরে লোড পড়বে আরো বেশি! এভাবে করে ১টা সার্ভার ডাউন হলে সেটা ট্রাফিক সামলাতে গিয়ে একের পর এক সার্ভার ডোমিনোর মত ভেঙে পড়তে পারে।

এই দুইটা সমস্যারই একটা চমৎকার সমাধান  আছে, সেটা হলো সার্ভারকে বৃত্তের উপর একাধিক জায়গায় ম্যাপিং করা। নিচের ছবিতে আমরা প্রতিটা সার্ভারকে ২টি করে লোকেশনে ম্যাপিং করেছি:

আগে কোনো সার্ভার বেশি ট্রাফিক, কোন সার্ভার কম ট্রাফিক পাচ্ছিলো। এখন সেই সমস্যা অনেকটাই কমে এসেছে। ২ এর জায়গায় ৩টা লোকেশনে ম্যাপিং করলে গ্যাপ আরো কমে আসবে তবে কোন key এর জন্য সার্ভারের লোকেশন বের করতেও আরো সময় বেশি লাগবে। ডেভেলপার হিসাবে তোমাকে ঠিক করতে হবে তোমার কাছে কোনটা গুরুত্বপূর্ণ।

ডোমিনো ইফেক্টও এখন আর সমস্যা না। এখন যদি সার্ভার $3$ ডাউন হয় তাহলে সব দায়িত্ব কারো একার ঘাড়ে চাপবে না, বরং সার্ভার $1$ এবং $0$ সেই দায়িত্ব ভাগাভাগি করে নিবে।

সার্ভিস ডিসকভারি

আমাদের আর্কিটেকচারটা এখন দেখতে অনেকটা এরকম:

কোনো ক্যাশ সার্ভার ডাউন হয়ে গেলে বা নতুন সার্ভার যোগ হলে ভিডিও সার্ভারকে সেটা জানতে হবে, নাহলে কিভাবে বুঝবে কোন ক্যাশ সার্ভার থেকে ডেটা আনতে হবে? এটার জন্য আমরা একটা কো-অর্ডিনেটর সার্ভিস ব্যবহার করবো। কো-অর্ডিনেটরের কাজ হলো কিছু সময় পরপর পিং করে দেখা কোন কোন সার্ভার জীবিত আছে। কো-অর্ডিনেটর সেই তথ্য নিজের কাছে জমা রাখবে এবং জানিয়ে দিবে ভিডিও সার্ভিস কে। ভিডিও সার্ভিস সার্ভারের লিস্ট পেলে সে হ্যাশ করে করে বের করতে পারবে কোন সার্ভার বৃত্তের কোথায় ম্যাপিং হয়েছে।

 

কো-অর্ডিনেটর সার্ভিস ডিস্ট্রিবিউটেড সিস্টেমে খুবই কমন একটা জিনিস, এটা ইমপ্লিমেন্ট করার জন্য ডেডিকেটেড অনেক টুলস আছে, যেমন zookeeper এবং etcd। প্রশ্ন আসতে পারে কো-অর্ডিনেটর সার্ভিস ক্র্যাশ করলে কি হবে? কো-অর্ডিনেটর নিজেও একটা ডিস্ট্রিবিউটেড সিস্টেম, একাধিক নোডে এটা ডিপ্লয় করা হয়, তাই পুরোটা ক্র্যাশ করার সম্ভাবনা খুবই কম। তাও যদি ক্র্যাশ করে, ভিডিও সার্ভার ক্যাশ সার্ভারের একটা লিস্ট নিজেও মেইনটেইন করতে পারে, কো-অর্ডিনেটর ক্র্যাশ করলে সেই লিস্ট থেকে রিকুয়েস্ট পাঠাবে, তবে সেই সময়টায় নতুন সার্ভার বা ডাউন হওয়া সার্ভারের খোজ সে পাবে না।

আজ এই পর্যন্তই, হ্যাপি কোডিং!

রেফারেন্স:

ডিস্ট্রিবিউটেট ক্যাশ সিস্টেম ডিজাইন

Print Friendly, PDF & Email

ফেসবুকে মন্তব্য

comments

Powered by Facebook Comments

7,093 times read (exlcuding bots)

Leave a Reply

Your email address will not be published. Required fields are marked *