پست قبلی رو ادامه ندادم دیگه، دیره یه مقدار :دی
این پست رو برای این می نویسم که جایی ثبت بشه تا بعد ها بتونم بهش رجوع کنم. ایرادی چیزی بود فیدبک بدید که باهم اصلاحش کنیم.
داشتم در مورد شبکه های distributed p2p مطالعه می کردم. به مبحث DHT رسیدم. DHT مخفف Distributed Hash Table. فرض کنید یه شبکه درست کردید که ۱۰۰۰ تا کلاینت بهش وصل شدن از سراسر دنیا. اینا برای پیدا کردن همدیگه به یه routing table یا یه hash table نیاز دارن که ازش بتونن بپرسن فلانی مثلا آی پیش چیه. این کار خیلی هم راحت نیست. برای اینکه سرور مرکزی وجود نداره که ازش درخواست کنید و اونم جواب بده. پس کلاینت (از این به بعد نود) نود ها باید از هم دیگه بپرسن. این هم امکان نداره که هر نود جداگانه اطلاعات تمام نود های دیگه رو داشته باشه، اینجوری باشه این سیستم scalable نخواهد بود. پس یه نود برای پیدا کردن آی پی نود دیگه از کدوم نود باید بپرسه؟ (بحث اینکه چطور بدون وجود سرور مرکزی، نود ها به شبکه جوین می شن مبحث bootstrapping هست که فعلا واردش نمیشیم)
شبکه های p2p که از سرور مرکزی استفاده میشه مثل Napster و ... مد نظرمون نیست اینجا.
البته توی bitcoin و بعضی از تکنولوژی هایی که با blockchain پیاده سازی شدن یه سری نود ها میتونن full node باشن که تمام اطلاعات رو بتونن دانلود کنن و لوکال داشته باشن ولی برای همه نود ها صدق نمی کنه.
خوب حالا که سرور مرکزی وجود نداره چیزی به اسم DHT هست. که به صورت تیکه به تیکه پخش میشه توی شبکه. با یه ضریب اطمینانی، هر تیکه از این hash table توسط چندین نود مختلف نگه داری میشه. فعلا از DHT بگذریم چون به بحث اصلی نمی رسیم. فقط بگم که یکی از راه های درست کردن این hash table استفاده از الگوریتم consistent hashing هست. الگوریتم Consistent Hashing برای اینه که هم هش هایی بسازیم که random هستن و هم این random بودنه باعث نشه که با هر اضافه شدن و حذف شدن یه نود hash table غیر قابل اعتماد بشه.
از جایی که HAProxy به عنوان load balancer داره ازش استفاده می کنه میتونه مثال خوبی باشه، برای اینکه دقیقا از همین الگوریتم استفاده میکنه تا درخواست هایی که از سمت درخواست کننده میاد رو به طور متعادل بین سرور هایی که وجود دارن پخش کنه. مثال:
فرض کنید ۲ تا سرور به عنوان load balancer دارید و HAProxy روشون نصب کردید. ۳ تا سرور هم دارید که پشت HA گذاشتیدشون. حالا توی هر HA باید سرور ها رو به عنوان نود به HA بدید.
در ساده ترین حالت ممکن بالانس کردن به صورت random هست که میتونه request شماره ۱ (req1) رو در یک زمان به نود ۱ بفرسته، دفعه بعد به نود ۲ بفرسته و ... . یه کم پیشرفته ترش کنیم میتونیم یه جدولی داشته باشیم که بگه req1 رو فقط به نود ۱ بفرست. (نود ۱ رندوم انتخاب شده. مسئله ی دیگه که پیش میاد اینه که ۲ تا سرور HA ما باید بدونن که اون یکی، req1 رو به چه نودی داده.) اما مشکل اصلی اینه که وقتی یکی از نود ها حذف بشن یا یه نود جدید اضافه بشه، دوباره برای تمام req ها باید سرور های رندوم جدید انتخاب بشه که ممکنه با دفعه قبلشون فرق داشته باشه. (اگه این اتفاق نیفته بالانس از بین میره) اما راهکار بعد استفاده از همین الگوریتمی هست که توضیح دادم که از اینجا به اختصار بهش میگیم CH.
حالا HA ها با همین الگوریتم CH و Hash Function به ازای هر نود یه hash تولید میکنن.
HAProxy 1:
node1 => hash(node1) => aaa node2 => hash(node2) => ccc node3 => hash(node3) => yyy
HAProxy 2:
node1 => hash(node1) => aaa node2 => hash(node2) => ccc node3 => hash(node3) => yyy
البته hash table به صورت key, value هست که هر هش به آی پی یا اسم نود اشاره میکنه.
خوب مشخصه که hash function به ازای یه ورودی مشخص همیشه یه خروجی ثابت بر میگردونه واسه همینه که توی هر دو سرور hash node1 شده aaa. این لیست از نود ها و هش هاشون روی حافظه هر دو HA به صورت مستقل به صورت Sort شده ذخیره میشن. مرحله بعد از همین hash function استفاده می شه تا req ورودی شماره ۱ رو تبدیل به یه هش ثابت کنه.
req1 => hash(req1) => bbb
مقدار هش برای هر دو HA یکسان خواهد بود. ولی این هش ها هیچ جا ذخیره نمی شن. فقط ازش استفاده میشه برای پیدا کردن نزدیک ترین سرور بعد از این هش. که بایه لوپ روی نودها و باینری سرچ با log n میشه نود مربوطه رو پیدا کرد.
node1 => hash(node1) => aaa --- bbb node2 => hash(node2) => ccc node3 => hash(node3) => yyy
که اینجا بعد از هش bbb اولین هشی که ازش بزرگتر هست رو پیدا میکنه که میشه ccc یعنی نود ۲. هیچ فرقی هم نمی کنه کدوم HA این req رو میگیره. هر دوشون به نتیجه نود ۲ میرسن. اگر هش req کمتر از aaa باشه همیشه نود ۱ پاسخگو هست. اگر هم بزرگتر از yyy باشه دوباره برمی گردیم از اول لیست شروع می کنیم که میشه همون نود ۱. برای همین هست که CH رو به صورت یه حلقه ای از هش ها نشون می دن. مثل این:
یه مشکل دیگه هست. به فرض اگر hash function ای که داریم از 000 شروع بشه و yyy تموم بشه. req های بعدی که میان هش های جدید رندوم ثابت میگیرن. و قطعا بین ۳ تا نودی که داریم بالانس درستی برقرار نمیشه. چون نود ۱ هش هایی رو که از 000 تا aaa رو باید هندل کنه. نود ۲ از aab تا ccc که تعدادشون قطعا کمتر از نود ۱ هست. نود ۳ هم از ccd تا fff رو هندل میکنه که باز نسبت به نود ۲ بیشتر هست. برای حل این مشکل هم تنها کافیه نود ها رو به صورت رندوم تکرار کنیم توی hash table.
node1 => hash(node1 - 1) => aaa node1 => hash(node1 - 2) => xxx node1 => hash(node1 - 3) => 555 node2 => hash(node2 - 1) => ccc node2 => hash(node2 - 2) => 111 node2 => hash(node2 - 3) => 999 node3 => hash(node3 - 1) => yyy node3 => hash(node3 - 2) => 222 node3 => hash(node3 - 3) => 444
خوب حالا یه مقدار بالانس تر شدن. برای همین توی تصویری که دایره شکل هست نود ها ۸ بار تکرار شدن تا کمک کنه به بالانس کردن قضیه.
توی این سیستم خیلی راحت یک نود میتونه حذف و اضافه بشه بدون اینکه کل سیستم رو تحت تاثیر قرار بده. مثلا اگر یه نود جدید ۴ اضافه کنیم و هشی که تولید میشه zzz باشه، تنها req هایی که هش اشون از yyy تا zzz باشه باید به نود ۴ برن. باقی مثل قبل می مونن.
باز هم یه مشکل دیگه هست. فرض کنید req1 یه درخواست سنگین باشه و req 2 یه درخواست خیلی سبک. اون وقت نود ی که قراره req 1 رو هندل کنه همیشه ریسورس بیشتری از نود های دیگه استفاده میکنه. این مشکل رو CH with bounded loads حل می کنه.
نسخه بهبود یافته این الگوریتم هم هست با عنوان Consistent Hashing With Bounded Loads توسط وهاب میررکنی، مرتضی زادی مقدم و میکل تراپ معرفی شد که بعدها HAProxy این بخش رو وارد سورس کد خودش کرد. (اینجا ببینید) این الگوریتم بهبود یافته با اضافه کردن میانگین لود و با یه فرمول ریاضی ساده، جلوی آور لود بعضی از نود ها رو در الگوریتم قبلی اصلاح کرد که باز این حالت با یک عددی مثل balance factor از ۱ تا ۲ قابل تنظیمه. اگه فرصت بشه در مورد این هم یه مطلب جدا می نویسم.
در نهایت خواستم این الگوریتم رو با golang پیاده کنم دیدم قبلا چند نفری اینکارو کردن و حتی یه نسخه اش توی golang/groupcache بود. اما چیزی که وجود نداشت این بود که اگر سرور ها یا نود ها از نظر منابع یکسان نباشن چطور باید هندل کرد که سعی کردم با درست کردن این mbrostami/consistenthash مشکل رو حل کنم.
موفق باشید
