‏کلادفلر با کمی ریاضی ۱۰۰ ترابایت رم آزاد کرد

تیم کلادفلر تو این مقاله تعریف می‌کنه که چطور مصرف حافظه‌ی Pingora Backend Router یا همون PBR رو پایین آورده. PBR سرویس داخلی پخش بار کلادفلره و بخش زیادی از رمش صرف کتابخونه‌ی متن‌باز pingora-ketama می‌شد. تو بعضی سرورها این مصرف به ۶ گیگابایت هم می‌رسید. نتیجه‌ی نهایی این شد که بیشتر از ۱۰۰ ترابایت رم تو کل شبکه آزاد شد.

ماجرا به consistent hashing برمی‌گرده (یعنی سرورها و درخواست‌ها رو با هش روی یه محور عددی می‌ذاری و هر درخواست به نزدیک‌ترین سرور می‌رسه). اگه هر سرور فقط یه هش داشته باشه، بار خیلی نامتعادل پخش می‌شه. نویسنده حساب کرده که با ۱۰۰ سرور، ضریب تغییرات (یعنی اندازه‌ی خطا نسبت به سهم عادی هر سرور) حدود ۹۹ درصده، یعنی بعضی سرورها دو برابر بقیه کار می‌کنن. راه‌حل معمول اینه که برای هر سرور چند تا هش بسازی. NGINX و Pingora پیش‌فرض ۱۶۰ هش برای هر سرور دارن که این خطا رو به حدود ۸ درصد می‌رسونه.

کلادفلر این عدد رو با الگوریتم ketama بر اساس فضای دیسک هر سرور هم ضرب می‌کنه. از طرف دیگه، چون همه‌ی سرورها نمی‌تونن هر درخواستی رو جواب بدن (مثلاً به خاطر قوانین compliance یا فیچرهای کش)، برای هر ترکیب فیچر یه ring جدا لازمه. همین باعث شد ده‌ها ring با تعداد خیلی زیادی هش تو حافظه بمونه.

اولین بهبود از خود struct اومد. هر هش با یه index چهار بایتی ذخیره می‌شد، در حالی که PBR هیچ‌وقت بیشتر از حدود ۶۵ هزار سرور رو مدیریت نمی‌کنه و ۱۶ بیت کافیه. ولی قوانین alignment در Rust (یعنی اندازه‌ی struct باید مضربی از بزرگ‌ترین فیلدش باشه) نمی‌ذاشت با عوض کردن نوع فیلد، حافظه کم بشه. برای همین داده‌ها رو تو یه آرایه‌ی ۶ بایتی ریختن و با getter خوندن:

struct Point([u8; 6]);

impl Point {
   fn hash(&self) -> u32 {
	u32::from_ne_bytes(self.0[0..4].try_into().unwrap())
   }
}

همین تغییر ساده ۲۵ درصد از حافظه‌ی consistent hashing رو کم کرد. قدم بعدی ریاضی بود. نویسنده فرمول دقیق خطا رو برای k هش در هر سرور درآورده و نشون داده هر بار که خطا یه پله کم می‌شه، تعداد هش‌ها باید تقریباً ده برابر بشه. با حدود ۱۰۰ هزار هش برای هر سرور، ۹۰ هزار تای آخر فقط ۰.۷ درصد خطا رو کم می‌کرد. تازه چون هش‌ها ۳۲ بیتی‌ان، تصادم هش‌ها (همون birthday paradox) خطا رو بیشتر هم می‌کرد. پس تعداد هش‌ها رو ۹۰ درصد کم کردن.

برای اینکه کش کل شبکه یهو خالی نشه و بار روی سرورهای اصلی سایت‌ها نره، مدتی هر دو ring قدیمی و جدید تو حافظه موندن. مهاجرت هم دیتاسنتر به دیتاسنتر جلو رفت و همیشه امکان برگشت بود. این تغییرات الان تو crate pingora-ketama به‌صورت یه cargo feature در دسترسه. ring نسخه‌ی v2 فرمت فشرده، مرتب‌سازی سریع‌تر و امکان تنظیم تعداد پایه‌ی هش‌ها رو داره.

نکات کلیدی:

• بیشتر از ۱۰۰ ترابایت رم تو کل شبکه‌ی کلادفلر آزاد شد.
• فشرده کردن struct از ۸ به ۶ بایت، ۲۵ درصد حافظه‌ی consistent hashing رو کم کرد.
• تعداد هش‌های هر سرور ۹۰ درصد کم شد، بدون خطای قابل توجه.
• NGINX و Pingora به‌طور پیش‌فرض ۱۶۰ هش برای هر سرور می‌سازن.
• مهاجرت با نگه داشتن هم‌زمان ring قدیمی و جدید و به‌صورت دیتاسنتر به دیتاسنتر انجام شد.
• ring نسخه‌ی v2 به‌صورت یه cargo feature تو crate pingora-ketama منتشر شده.