صرفه جویی در 100 ترابایت رم دیگر

Cloudflare در مقیاسی بسیار بزرگ عمل می کند که حتی پس از سال ها کار در اینجا، واقعی به نظر نمی رسد. ما هزاران سرور در سرتاسر جهان با پتابایت رم و میلیون ها هسته پردازنده داریم و همه آنها به حداکثر رسیده است. به همان اندازه که این منابع به نظر گسترده هستند، آنها هنوز محدود هستند، و زمانی که شما نیاز به اجرای هر سرویس در هر گره دارید، فضایی برای هدر رفتن فضای باقی نمی گذارد.

در این مقیاس، پیشرفت‌های کوچک بسیار بزرگ‌تر می‌شوند، بنابراین حتی پیشرفت‌های 1% در یک زمان ارزش جشن گرفتن دارند. و برخی از ترفندها به موارد بسیار بیشتری اضافه می شوند: در این پست، به این خواهیم پرداخت که چگونه تغییرات کوچک در یک الگوریتم واحد باعث کاهش قابل توجه حافظه یکی از سرویس های مبتنی بر Pingora ما شده است. این به ما امکان داد تا بیش از 100 ترابایت حافظه رم را در سطح جهانی بازیابی کنیم، علاوه بر 100 ترابایت حافظه ای که تیم DNS در ماه گذشته توانسته بود از بین ببرد.

حفظ اشتراک عادلانه منابع بین تیم ها به خصوص در سازمان های بزرگ آسان نیست. یکی از راه‌هایی که Cloudflare برای حفظ تعادل تضمین می‌کند، تلاش‌های خستگی‌ناپذیر تیم فوق‌العاده Performance است.

این داستان با بلیطی شروع می شود که توسط ایوان ثبت شده است که متوجه شد: استفاده بیش از حد از حافظه از pingora-ketama در روتر Pingora Backend. یافته‌ها این بود که سرویس تعادل بار داخلی ما، Pingora Backend Router (بله، PBR)، به طور قابل‌توجهی بیشتر از آنچه انتظار می‌رفت از حافظه استفاده می‌کرد - به‌ویژه در ساختارهای مرتبط با pingora-ketama، که کتابخانه منبع باز ما برای مدیریت هش کردن مداوم است.

برای اینکه بخواهیم در مورد اینکه چگونه به این استفاده بیش از حد از حافظه پرداختیم، باید در مورد اینکه هش ثابت چیست، چرا از آن در PBR استفاده می‌کنیم و چگونه اینقدر حافظه را تشنه می‌کند صحبت کنیم. در طول راه، مقداری Rust و حتی کمی ریاضی را یاد خواهیم گرفت.

هش پیوسته روشی است که به طور گسترده برای توزیع وظایف در چندین سرور استفاده می شود به گونه ای که در هنگام اضافه یا حذف سرورها نیازی به تغییرات بزرگ نباشد. در داخل از آن برای هدایت درخواست‌های قابل ذخیره‌سازی به سرورها توسط URL استفاده می‌کنیم. این به ما این امکان را می دهد که فقط یک کپی از یک فایل ذخیره شده در هر مرکز داده را نگه داریم و راهی پایدار برای یافتن مکان هر فایل می دهد. ما قبلا به این سیستم اشاره کرده‌ایم، اما بیایید وقت بگذاریم تا چگونگی و چرایی استفاده از این الگوریتم و نحوه عملکرد آن را بررسی کنیم.

مفهوم کلیدی هش کردن سازگار این است که در حالی که توابع هش می توانند هر نوع ورودی را بپذیرند، خروجی آنها به یک عدد صحیح بدون علامت محدود می شود (اعداد صحیح 32، 64 یا 128 بیتی بسته به اینکه کدام تابع هش کدام است). این به ما این امکان را می دهد که وظایف و سرورها را به روشی ثابت به یکدیگر مرتبط کنیم. بیشتر بحث‌های مربوط به هش کردن مداوم، فضای خروجی را به عنوان یک حلقه دایره‌ای پیوسته و پیوسته که از حداکثر مقدار خود به صفر می‌پیچد، در نظر می‌گیرید. این تصویر تجسم‌های خوبی را ایجاد می‌کند، اما همچنین می‌تواند مفهوم ساده محدوده‌های اعداد صحیح را پیچیده‌تر از آنچه لازم است به نظر برساند.

برای بحث ما، خروجی 32 بیتی تابع هش خود را به عنوان یک خط عددی نشان خواهیم داد.

حال، فرض کنید مجموعه‌ای از سرورها، A، B، و C و مجموعه‌ای از وظایف t-z داریم. ما می‌توانیم هر کدام را بر اساس هش مقادیر نماینده آن‌ها روی خط اعداد نگاشت کنیم، بنابراین چیزی شبیه آدرس‌های IP برای سرورها و کلیدهای حافظه پنهان برای وظایف.

تخصیص وظایف به سرورها اکنون فقط به یافتن اولین سرور در سمت چپ هر وظیفه است. ما می‌توانیم این را به صورت بصری با رنگ‌آمیزی در ناحیه هش‌هایی که به هر سرور مرتبط می‌شود، نشان دهیم. توجه داشته باشید که محدوده پوشش داده شده توسط سرور C به ابتدا می رسد، از این رو این ایده وجود دارد که هش ها در یک حلقه وجود دارند.

و همین است. در سطح پایه، هش کردن مداوم به همین سادگی است – اما زمان زیادی طول نمی کشد تا متوجه شوید که فضایی برای بهبود وجود دارد. توجه داشته باشید که محدوده تحت پوشش سرور A در مثال ما به طور قابل توجهی بزرگتر از B یا C است. این یک مشکل است زیرا کسری از درخواست هایی که یک سرور رسیدگی می کند با اندازه محدوده آن در خط اعداد متناسب است. در حالت ایده‌آل، ما می‌خواهیم تضمین کنیم که هر سرور دارای اندازه یکسانی خواهد بود، اما از آنجا که هش‌ها اساسا اعداد تصادفی هستند، باید در مورد اندازه مناطق از نظر آماری صحبت کنیم. 😨

اول: نترسید. قول می دهم که قرار نیست به شما دروغ بگویم و با خیال راحت در محدوده یک روز درس احتمال می مانیم. وقتی در مورد توزیع های آماری صحبت می کنیم، دو عامل بزرگ وجود دارد که به ما کمک می کند تا عدم قطعیت را به روش های مفید کمی کنیم: مقدار مورد انتظار و انحراف استاندارد. به زبان ساده شده (بیش از حد)، مقدار مورد انتظار نقطه‌ای را به ما می‌دهد که اندازه‌گیری‌های مبتنی بر توزیع در مرکز قرار می‌گیرند، و انحراف معیار نشان می‌دهد که بیشتر اندازه‌گیری‌ها چقدر به آن نقطه مرکزی نزدیک هستند.

برای هش کردن مداوم، می‌توانیم این عوامل را برای اندازه کسری محدوده مرتبط با یکی از سرورهای N محاسبه کنیم. (جزئیات در مورد اینکه این فرمول از کجا آمده است).

از نظر اعداد مشخص، فرض کنید 100 سرور داریم. فرمول های بالا نشان می دهد:

این به ما می‌گوید که می‌توانیم انتظار داشته باشیم که محدوده‌ای که هر سرور مدیریت می‌کند در حدود 0.99٪ از کل متمرکز شود و بیشتر طول‌ها در 1٪ از آنچه انتظار می‌رود قرار گیرد. این خوب به نظر می رسد تا زمانی که متوجه شویم که 0.99٪ از کل طول است. ما باید انحراف استاندارد را با مقدار مورد انتظار مقیاس کنیم تا ببینیم خطا به عنوان کسری از اندازه هدف چقدر است. این مقدار ضریب تغییرات نامیده می شود.

سادگی هش کردن مداوم یک شمشیر دو لبه است. درک و پیاده‌سازی آن آسان است زیرا همه چیز در همان خط شماره به هش‌هایی تبدیل می‌شود که به راحتی قابل ربط هستند، اما هر گونه بهبودی در سیستم نیز باید با آن خط شماره مرتبط باشد. این بدان معناست که راه حل برای هر مشکل هش ثابت فقط می تواند هش های بیشتر باشد. این کمتر شبیه یک چکش طلایی است (ابزاری که با آن همه مشکلات شبیه میخ به نظر می رسد) و بیشتر شبیه یک میخ طلایی است زیرا همه ابزارها را به چکش تبدیل می کند.

برای حل مشکل بارهای کاری نامتعادل، می‌توانیم به جای یک سرور، چندین هش اضافه کنیم. ما به طور لحظه ای به ریاضیات پشت این موضوع خواهیم رسید، اما باید حس شهودی داشته باشیم که در حالی که هر محدوده فردی دارای انحراف استاندارد بزرگی است، با اضافه کردن یک دسته به یکدیگر، اندازه کل آنها یکسان می شود. اگر مثال سه سرور خود را از نمودارهای بالا بگیریم و دو هش دیگر را به صورت تصادفی برای هر سرور اضافه کنیم، می بینیم که به یکنواخت شدن حجم کاری هر سرور کمک می کند.

این یک نمونه ساختگی است. ماهیت تصادفی سیستم به این معنی است که هیچ تضمینی وجود ندارد که با افزودن 2 هش اضافی به ازای هر سرور چقدر پیشرفت خواهید داشت، اما باید حس شهودی داشته باشد که ترکیب بیشتر این بخش‌های هش با هم توزیع یکنواخت‌تری ایجاد می‌کند. هر بخش در مجموع شانس متعادل کردن بخش دیگر را دارد. شاید یکی خیلی کوتاه باشد. شاید یکی خیلی طولانی باشد این اساسا همان چیزی است که قانون اعداد بزرگ به ما می گوید باید اتفاق بیفتد... مشکل واضح این است که فقط برای اعداد بزرگ کار می کند.

در NGINX، تعداد پایه هش ها در هر سرور به 160 کدگذاری می شود و Pingora از همان مقدار پیش فرض استفاده می کند. فعلا از ریاضیات صرف نظر می کنم، اما اگر به مثال 100 سرور خود برگردیم، اگر از 160 امتیاز در هر سرور به جای یک امتیاز استفاده کنیم، ضریب تغییرات (که می توانیم آن را مانند حاشیه خطا در نظر بگیریم) از حدود 99٪ به حدود 8٪ کاهش می یابد، بهبود قابل توجهی.

در بالا دیدیم که افزایش تعداد هش‌ها در هر سرور به میزان ثابت به ما امکان می‌دهد تا نحوه توزیع یکنواخت بارهای کاری در هر سرور را بهبود بخشیم، اما اگر نخواهیم کار را به طور مساوی توزیع کنیم، چه؟ در مورد Cloudflare، ما برخی از سرورها را داریم که فضای ذخیره سازی بیشتری نسبت به بقیه دارند، بنابراین بهتر است تعداد درخواست های اختصاص داده شده به یک سرور متناسب با فضای دیسک آن باشد. یکی از راه های انجام این کار با الگوریتم کتاما است.

نامگذاری کمی خنده دار است زیرا الگوریتم به نام کتابخانه ای است که برای اولین بار در آن پیاده سازی شده است و نام کتابخانه ... خوب می توانید آن را در گوگل جستجو کنید 😶‍🌫️.

برای ما، از آنجایی که می‌خواهیم حجم کار بر اساس فضای ذخیره‌سازی مقیاس شود، می‌توانیم از فضای دیسک به عنوان وزن استفاده کنیم، این دقیقا همان کاری است که تیم پینگورا سال‌ها انجام می‌دهد. در جاهای دیگر شرکت که بارهای کاری محاسباتی بیشتری دارند، وزن ها ممکن است بر اساس تعداد CPU یا GPU باشد.

آخرین مشکلی که باید به آن بپردازیم این است که تا کنون با این فرض کار می کنیم که هر سروری می تواند هر درخواستی را انجام دهد، اما در عمل اینطور نیست. مواردی مانند الزامات انطباق یا ویژگی‌های ذخیره‌سازی فعال به این معنی است که تنها زیر مجموعه‌ای از سرورها می‌توانند هر درخواست خاصی را انجام دهند. متأسفانه، برخلاف قبل، نمی‌توانیم این مشکل را با افزودن هش‌های بیشتر به همان حلقه حل کنیم. ما باید حلقه‌های کاملا جدیدی را اضافه کنیم، و نه تنها این - هر ترکیبی از ویژگی‌ها به طور بالقوه به حلقه خاص خود نیاز دارد!

یک پیشرفت بزرگ از Zaidoon حاصل شد، که بینشی در مورد ساختار ما برای ذخیره هش در PBR داشت. این ساختار به شکل زیر است:

متأسفانه، Rust آن را به این راحتی نمی کند. تغییر اندازه ایندکس همانطور که در بالا انجام دادیم باعث کاهش ردپای حافظه نمی شود. این به این دلیل است که Rust دارای قوانین تراز است که به اندازه یک ساختار در حافظه نیاز دارد تا مضرب بزرگترین (یا "تراز شده ترین") میدان آن باشد. در این مورد، هش با چهار بایت بزرگترین است، بنابراین زمانی که در حافظه ذخیره می شود، یک Point باید دارای اندازه $mN \times 4m$ باشد، بنابراین حداقل اندازه هشت بایت است.

خوشبختانه راه های شناخته شده ای برای حل این موضوع وجود دارد. شما (منظور من است) ممکن است وسوسه شوید از #[repr(packed)] استفاده کنید، اما به دلایل خوبی بحث برانگیز است. راه حل ایمن تر اما کمتر قابل خواندن این است که هش و ایندکس را به عنوان آرایه بایت خام ذخیره کنید و با دریافت کننده به آنها دسترسی پیدا کنید. هر دو روش به یک چیز کامپایل می شوند.

این تغییر ساده (اگر کلامی) میزان حافظه مورد استفاده برای هش کردن مداوم را تا 25 درصد کاهش می دهد! برای انجام بهتر از آن، باید به ریاضیات برگردیم، بنابراین همه به چیزی ادامه می دهند. این کشش خانه است.

ممکن است متوجه شده باشید که ما فرمول انحراف استاندارد را برای مواردی که فقط یک هش در هر سرور وجود دارد ارائه کردیم. استخراج فرمول برای مواردی که $m k m$ هش در هر سرور وجود دارد، آسان نیست، و اکثر منابع فقط یک تقریب یا محدودیت مجانبی را به شما ارائه می دهند، اما ما نه. من ممکن است آمارگیر نباشم، اما با یک معلم حساب دیفرانسیل و انتگرال بزرگ شدم (سلام، مامان!)، و می خواستم ارزش واقعی آن را بدانم. اشتقاق کامل در یک پست تکمیلی است، اما نتیجه این است.

برای اینکه ببینیم چگونه افزایش تعداد هش دقت را بهبود می بخشد، باید دوباره به ضریب تغییرات نگاه کنیم.

پیش‌بینی‌های ریاضی زیبای من فقط زمانی کار می‌کند که به هش‌ها در یک حلقه پیوسته فکر کنیم، اما در عمل از اعداد 32 بیتی برای هش‌هایی استفاده می‌کنیم که پتانسیل برخورد دارند، و با افزایش تعداد هش‌ها، احتمال برخورد به طرز شگفت‌آوری به سرعت بالا می‌رود (به پارادوکس تولد مراجعه کنید). برخوردها اهمیت دارند زیرا در حالت ایده‌آل، هر هش به حجم و توزیع درخواست‌های انجام‌شده توسط سرور مرتبط کمک می‌کند، اما برخورد به این معنی است که برخی از مشارکت‌ها به‌طور تصادفی حذف می‌شوند و خطای غیرقابل پیش‌بینی ایجاد می‌کند.

اگر برخی از نتایج شبیه سازی شده با هش های 32 بیتی را با نرخ خطای پیش بینی شده مقایسه کنیم، می بینیم که برای مراکز داده با سرورهای 2048، نرخ خطا افزایش می یابد: بین 10000 تا 100000 هش در هر سرور.

در نهایت، حتی اگر این درک به نوعی بد به نظر می‌رسد، برای برنامه ما برای بازیابی مقداری RAM خبر خوبی است! اکنون که مقداری ریاضی برای پشتیبان گیری از آن داریم، به این نتیجه رسیدیم که می‌توانیم تعداد هش‌هایی را که برای هر سرور تولید می‌کنیم تا 90 درصد کاهش دهیم، بدون اینکه دچار خطای قابل‌توجهی شویم، بنابراین این همان کاری است که ما قصد انجام آن را داریم.

یک مشکل دیگر وجود داشت: تغییر حلقه هش در جایی که برخی از درخواست‌های ذخیره‌سازی ذخیره می‌شوند، تغییر می‌کند. حتی اگر حلقه جدید بهتر باشد، تغییر یکباره کل شبکه تقریبا تمام محتوای کش شده را باطل می کند. بهینه سازی حافظه را به افزایش آخرالزمانی در ترافیک مبدا تبدیل می کند.

بنابراین ما این یک تلنگر جهانی را انجام ندادیم. برای مدتی، PBR هر دو نسخه از متعادل کننده بار قابل ذخیره را در حافظه داشت: حلقه قدیمی کتاما و نسخه کوچکتر جدید. هر درخواست از چارچوب مهاجرت عادی ما استفاده می‌کرد تا تصمیم بگیرد کدام حلقه باید باطن را انتخاب کند. این بدان معناست که تصمیم عرضه به ازای هر هش درخواست پایدار بود، و همچنین یک مسیر بازگشت تمیز به ما داد. اگر مشکلی به نظر می‌رسید، می‌توانیم درخواست‌های جدید را از طریق حلقه قدیمی بدون استفاده مجدد از PBR ارسال کنیم.

سپس مهاجرت را به صورت لایه‌ای رول کردیم. ما با مکان‌های اعتبارسنجی کوچک شروع کردیم، از طریق گروه‌های به تدریج بزرگ‌تر از مراکز داده حرکت کردیم و تنها پس از آن به سمت بقیه جهان ادامه دادیم.

بخش مهم این بود که ما دو بعد را به طور مستقل کنترل می‌کردیم: اینکه چه میزان ترافیک از رینگ جدید استفاده می‌کند، و اینکه این ترافیک در کجا مجاز است حرکت کند. انتشار درصد جهانی ساده می‌تواند به یکباره ریزش حافظه پنهان را در همه جا پخش کند. انتشار با دامنه مرکز داده، شعاع انفجار را کوچک نگه داشت و تشخیص اینکه آیا یک تغییر واقعا ایمن است یا خیر، بسیار آسان تر شد.

در طول انتقال، ردیابی‌های انتخاب باطن، شمارنده‌های نسخه حلقه، خطاهای اتصال PBR، حافظه پردازش، زمان راه‌اندازی، رفتار حافظه پنهان و ترافیک مبدا را مشاهده کردیم. هنگامی که مهاجرت به 100٪ رسید، ما مسیر موقت حلقه قدیمی را حذف کردیم، و voila!

نمودار بالا مقایسه حافظه استفاده شده توسط PBR در هفته تغییر را در مقایسه با داده های چند هفته قبل و همچنین نتیجه کم کردن یکی از دیگری را نشان می دهد. افت شدید روزی است که نسخه PBR با حلقه های هش بزرگ (اکنون استفاده نشده) برای همیشه از کار افتاده است. با نگاهی به تفاوت، نتیجه رضایت‌بخشی به دست می‌آید که تغییرات ما باعث کاهش 100 ترابایتی حافظه استفاده شده شده است!

تمام تغییراتی که در این پست درباره آنها صحبت کردیم اکنون در جعبه pingora-ketama به شکل یک ویژگی محموله تبلیغاتی (در حال حاضر) موجود است. حلقه v2 دارای فرمت ذخیره سازی فشرده، روش مرتب سازی سریعتر و توانایی مقیاس بندی تعداد پایه هش در هر گره است. تمرکز ما در ایجاد این تغییرات باید بر روی ثبات و کنترل باشد، بنابراین حلقه v1 مشابه چیزی است که pingora ketama همیشه از آن استفاده می‌کرده است، و کتابخانه این امکان را به شما می‌دهد که هر دو را به طور همزمان اجرا کنید و براساس درخواست به درخواست تصمیم بگیرید که از کدام و چه زمانی استفاده شود.

اگر مایلید وارد اعداد و ارقام شوید، فراتر از تلاش برای تغییرات هش مداوم ما، می‌خواهم از این الهام بگیرید تا در سیستم‌های خود کاوش کنید تا ببینید چه تصمیم‌های «ساده» یا «بدیهی» برنده‌های بالقوه را پنهان می‌کنند. ممکن است نتوانید همه مسائل خود را با Rust حل کنید، اما ریاضیات جهانی است.