شرکت کلودفلر (Cloudflare) در مقیاسی فعالیت میکند که حتی پس از سالها کار کردن در آن، واقعی به نظر نمیرسد. ما هزاران سرور در سراسر جهان با پتابایتها حافظه رم و میلیونها هسته پردازنده داریم و همه آنها تا حد نهایی تحت فشار هستند. هرچقدر هم که این منابع وسیع به نظر برسند، باز هم محدود هستند و وقتی نیاز دارید که هر سرویس روی هر گودی اجرا شود، جایی برای فضای هدررفته باقی نمیماند.
در این مقیاس، بهبودهای کوچک به شدت بزرگ میشوند، بنابراین حتی بهبودهای 1%-at-a-time ارزش جشن گرفتن دارند. و برخی تغییرات جمعاً دستاوردهای خیلی بیشتری به همراه دارند: در این مقاله، بررسی خواهیم کرد که چگونه تغییرات کوچک در یک الگوریتم واحد، ردپای حافظه یکی از سرویسهای مبتنی بر پینگورا (Pingora) ما را به طور قابل توجهی کاهش داد. این کار به ما اجازه داد تا بیش از ۱۰۰ ترابایت حافظه رم را در سطح جهانی بازپس بگیریم، علاوه بر آن ۱۰۰ ترابایت حافظهای که تیم دیاناس (DNS) ماه گذشته موفق به حذف آن شده بود.
چیزی را هدر ندهید
حفظ اشتراکگذاری عادلانه منابع بین تیمها کار آسانی نیست، بهویژه در سازمانهای بزرگ. یکی از راههایی که کلودفلر تضمین میکند این تعادل حفظ شود، تلاشهای خستگیناپذیر تیم فوقالعادهی عملکرد (Performance team) است.
این داستان با یک تیکت ثبتشده توسط ایوان (Ivan) شروع شد که متوجه شده بود: استفاده بیش از حد حافظه از pingora-ketama در روتر بکاند پینگورا (Pingora Backend Router). این یافته نشان داد که سرویس بارگذاری داخلی ما، یعنی روتر بکاند پینگورا (بله، PBR)، بهطور قابلتوجهی بیشتر از حد انتظار حافظه مصرف میکند — بهویژه در ساختارهای مرتبط با pingora-ketama که کتابخانه متنباز ما برای مدیریت هشینگ سازگار است.
برای صحبت در مورد اینکه چگونه این استفاده ظاهراً بیش از حد از حافظه را برطرف کردیم، باید در مورد اینکه هشینگ سازگار چیست، چرا از آن در PBR استفاده میکنیم و چگونه اینقدر حریص به حافظه شده است، صحبت کنیم. در طول مسیر، مقداری زبان Rust و حتی کمی ریاضی یاد خواهیم گرفت.
هشینگ سازگار
هشینگ سازگار یک روش به طور گسترده استفاده شده برای توزیع وظایف در میان سرورهای متعدد به گونهای است که هنگام اضافه یا حذف شدن سرورها، نیازی به تغییرات بزرگ نباشد. ما به صورت داخلی از آن برای مسیریابی درخواستهای قابل کش شدن به سرورها بر اساس URL استفاده میکنیم. این کار به ما اجازه میدهد تنها یک کپی از فایل را در هر مرکز داده ذخیره کنیم و یک راه پایدار برای یافتن مکان هر فایل ارائه میدهد. ما قبلاً به این سیستم اشاره کردهایم، اما بیایید وقت بگذاریم و بررسی کنیم که چگونه و چرا از این الگوریتم استفاده میشود و چگونه کار میکند.
مفهوم کلیدی هشینگ سازگار این است که در حالی که توابع هش میتوانند هر نوع ورودی را بپذیرند، خروجی آنها به یک عدد صحیح بدون علامت واحد (اعداد ۳۲، ۶۴ یا ۱۲۸ بیتی بسته به تابع هش) محدود میشود. این به ما اجازه میدهد وظایف و سرورها را به روشی سازگار با یکدیگر مرتبط کنیم. بیشتر بحثها درباره هشینگ سازگار باعث میشوند فکر کنید که فضای خروجی یک حلقه پیوسته و دایرهای است که از حداکثر مقدار خود به صفر میرسد. این تصویرسازی برای برخی تجسمهای زیبا خوب است، اما همچنین میتواند مفهوم ساده بازههای عددی را پیچیدهتر از آنچه نیاز است نشان دهد. برای بحث ما، خروجی ۳۲ بیتی تابع هش خود را به صورت یک خط عدد نشان خواهیم داد.
اکنون، فرض کنید مجموعهای از سرورها (A، B و C) و مجموعهای از وظایف (t-z) داریم. ما میتوانیم هر کدام را بر اساس هش مقادیر نماینده آنها روی خط اعداد نگاشت کنیم، بنابراین چیزی مانند آدرسهای IP برای سرورها و کلیدهای کش برای وظایف.
اختصاص دادن وظایف به سرورها اکنون صرفاً یافتن اولین سرور در سمت چپ هر وظیفه است. ما میتوانیم این را به صورت بصری با رنگ کردن ناحیه هشهایی که با هر سرور مرتبط خواهند بود، نشان دهیم. توجه داشته باشید که محدوده پوشش داده شده توسط سرور C به ابتدا برمیگردد، از این رو این ایده که هشها در یک حلقه وجود دارند.
و همین است. در سطح پایه، هشینگ سازگار به همین سادگی است — اما طولی نمیکشد که میبینید فضایی برای بهبود وجود دارد. توجه داشته باشید که محدوده پوشش داده شده توسط سرور A در مثال ما به طور قابل توجهی بزرگتر از B یا C است. این یک مشکل است زیرا کسری از درخواستهایی که یک سرور مدیریت میکند متناسب با اندازه محدوده آن روی خط اعداد خواهد بود. در حالت ایدهآل، ما دوست داریم تضمین کنیم که هر سرور اندازه مساوی خواهد داشت، اما از آنجایی که هشها اساساً اعداد تصادفی هستند، باید در مورد اندازه مناطق از نظر آمار صحبت کنیم. 😨
ریاضی و عواقب آن
اول: نترسید. من قول میدهم که قصد فریب شما را ندارم و به طور ایمن در حدود یک درس احتمالات روز اول خواهیم ماند. وقتی در مورد توزیعهای آماری صحبت میکنیم، دو عامل بزرگ وجود دارد که به ما کمک میکند عدم قطعیت را به روشهای مفید کمّی کنیم: مقدار مورد انتظار (expected value) و انحراف معیار (standard deviation). به زبان (بیش از حد) ساده، مقدار مورد انتظار نقطهای را به ما میدهد که اندازهگیریها بر اساس آن متمرکز خواهند بود و انحراف معیار میگوید که بیشتر اندازهگیریها چقدر به آن نقطه مرکزی نزدیک هستند.
برای هشینگ سازگار، ما میتوانیم این عوامل را برای اندازه کسری محدوده مرتبط با یکی از N سرور محاسبه کنیم.
از نظر اعداد مشخص، بیایید فرض کنیم ۱۰۰ سرور داریم. فرمولهای بالا نتیجه میدهند:
این به ما میگوید که میتوانیم انتظار داشته باشیم محدودهای که هر سرور مدیریت میکند حول 0.99٪ از کل متمرکز شود و بیشتر طولها در حدود 1٪ از آنچه انتظار میرود قرار گیرند. این خوب به نظر میرسد تا زمانی که متوجه شویم این 0.99٪ از کل طول است. ما باید انحراف معیار را با مقدار مورد انتظار مقیاسبندی کنیم تا ببینیم خطا به عنوان کسری از اندازه هدف چقدر بزرگ است. این مقدار ضریب تغییرات (coefficient of variation) نامیده میشود.
چه میشود اگر هشها را اضافه کنیم؟
سادگی هشینگ سازگار یک شمشیر دوبر لبه است. درک و پیادهسازی آن آسان است زیرا همه چیز به هشهای به راحتی قابل ارتباط روی همان خط اعداد تبدیل میشود، اما هرگونه بهبودی در سیستم نیز باید با آن خط اعداد قابل ارتباط باشد. این بدان معناست که راهحل هر مشکل هشینگ سازگار فقط میتواند هشهای بیشتر باشد.
برای حل مشکل بارهای کاری نامتوازن، میتوانیم به جای فقط یک هش، چندین هش برای نمایندگی هر سرور اضافه کنیم. ما به زودی به ریاضیات پشت این موضوع خواهیم رسید، اما باید این حس شهودی را ایجاد کند که در حالی که هر محدوده فردی دارای انحراف معیار بزرگی است، اضافه کردن یک دسته به یکدیگر باید اندازه کل آنها را متعادل کند. اگر مثال سه سروره خود را از نمودارهای بالا بگیریم و دو هش دیگر به صورت تصادفی برای هر سرور اضافه کنیم، میبینیم که به هموار کردن بار کاری هر سرور کمک میکند.
این یک مثال مسصنوعی است. ماهیت تصادفی سیستم به این معنی است که هیچ تضمینی وجود ندارد که چقدر بهبود از اضافه کردن 2 هش اضافی به ازای هر سرور دریافت خواهید کرد، اما باید این حس شهودی را ایجاد کند که ترکیب بیشتر این بخشهای هش با هم، توزیع یکنواختتری ایجاد میکند. این اساساً همان چیزی است که قانون اعداد بزرگ (law of large numbers) به ما میگوید باید اتفاق بیفتد… مشکل واضح این است که فقط برای اعداد بزرگ کار میکند. در NGINX، تعداد مبنای هشها به ازای هر سرور روی 160 سختکد شده است، و پینگورا از همان مقدار به عنوان پیشفرض استفاده میکند. اگر به مثال ۱۰۰ سرور خود برگردیم، اگر به جای فقط یک نقطه، از ۱۶۰ نقطه به ازای هر سرور استفاده کنیم، ضریب تغییرات از حدود ۹۹٪ به حدود ۸٪ کاهش مییابد که یک بهبود قابل توجه است.
چه میشود اگر هشهای بیشتری اضافه کنیم؟
ما در بالا دیدیم که افزایش تعداد هشها به ازای هر سرور به مقدار ثابت به ما اجازه میدهد تا نحوه توزیع یکنواخت بارهای کاری را بهبود ببخشیم، اما چه میشود اگر نخواهیم کار را به طور مساوی توزیع کنیم؟ در مورد کلودفلر، ما برخی سرورها را داریم که فضای ذخیرهسازی بیشتری نسبت به بقیه دارند، بنابراین بهتر است تعداد درخواستهای اختصاص داده شده به یک سرور متناسب با فضای دیسک آن باشد. یک راه برای انجام این کار استفاده از الگوریتم کهتاما است.
برای ما، از آنجایی که میخواهیم بار کاری بر اساس ذخیرهسازی مقیاسبندی شود، میتوانیم از فضای دیسک به عنوان وزن استفاده کنیم، که دقیقاً همان کاری است که تیم پینگورا سالهاست انجام میدهد. در جاهای دیگر شرکت که بارهای کاری فشردهتر پردازشی هستند، وزنها ممکن است بر اساس تعداد پردازنده مرکزی یا گرافیکی باشند.
چه میشود اگر هشهای حتی بیشتری اضافه کنیم؟؟
آخرین مشکلی که باید به آن بپردازیم این است که تاکنون تحت این فرض کار میکنیم که هر سرور میتواند هر درخواستی را مدیریت کند، اما در عمل اینطور نیست. مواردی مانند الزامات انطباق یا ویژگیهای فعال کش به این معنی است که تنها زیرمجموعهای از سرورها میتوانند هر درخواست خاص را مدیریت کنند. متأسفانه، بر خلاف قبل، ما نمیتوانیم این مشکل را با اضافه کردن هشهای بیشتر به همان حلقه حل کنیم. ما باید حلقههای کاملاً جدید اضافه کنیم و نه تنها این — هر ترکیبی از ویژگیها به طور بالقوه به حلقه خاص خود نیاز دارد!
بهبودهای ذخیرهسازی
یک بهبود بزرگ از سوی زیدون (Zaidoon) آمد، کسی که بینشی درباره ساختار ما برای ذخیرهسازی هشها در PBR داشت. آن ساختار به این شکل است:
متأسفانه، زبان Rust این کار را خیلی آسان نمیکند. تغییر اندازه ایندکس همانطور که در بالا انجام دادیم هیچ کاری برای کاهش ردپای حافظه انجام نمیدهد. این به این دلیل است که Rust قوانین همترازی دارد که ایجاب میکند اندازه یک ساختار در حافظه چندی از بزرگترین (یا «بیشترین همترازی») فیلد آن باشد. در این مورد، هش بزرگترین با چهار bytes است، بنابراین هنگام ذخیرهسازی در حافظه، یک نقطه ملزم است اندازه $mN \times 4m$ داشته باشد، بنابراین حداقل اندازه هشت bytes است.
خوشبختانه راههای شناختهشدهای برای دور زدن این وجود وسوسهانگیز است که از #[repr(packed)] استفاده کنید، اما این به دلایل خوب بحثبرانگیز است. یک راهحل امنتر اما کمتر خوانا این است که هش و ایندکس را به عنوان آرایه بایت خام ذخیره کرده و با دریافتکنندهها به آنها دسترسی داشته باشید. هر دو روش به یک چیز کاملاً مشابه کامپایل میشوند.
این تغییر ساده میزان حافظه استفاده شده برای هشینگ سازگار را تا رقم خیرهکننده ۲۵٪ کاهش میدهد! برای انجام بهتر از این، باید به ریاضیات برگردیم.
چه میشود اگر هشهای کمتری امتحان کنیم؟
برای دیدن اینکه چگونه افزایش تعداد هش دقت را بهبود میبخشد، باید دوباره به ضریب تغییرات نگاه کنیم.
پیشبینیهای ریاضیات من فقط در صورتی کار میکنند که به هشها در یک حلقه پیوسته فکر کنیم، اما در عمل ما از اعداد ۳۲ بیتی برای هشها استفاده میکنیم که پتانسیل تصادم دارند، و احتمال تصادمات به طرز شگفتآوری به سرعت با افزایش تعداد هشها افزایش مییابد. تصادمات مهم هستند زیرا در حالت ایدهآل، هر هش در حجم و توزیع درخواستهای مدیریت شده توسط سرور مرتبط مشارکت میکند، اما یک تصادم به این معنی است که برخی مشارکتها به طور تصادفی حذف میشوند و خطای غیرقابل پیشبینی را معرفی میکنند.
در نهایت، اگرچه این درک کمی بد به نظر میرسد، اما خبر عالی برای برنامه ما برای بازپسگیری مقداری رم است! اکنون که مقادیری ریاضی برای پشتیبانی از آن داریم، مشخص کردیم که میتوانیم تعداد هشهایی را که برای هر سرور تولید میکردیم تا ۹۰٪ بدون متحمل شدن هیچ خطای قابل توجهی کاهش دهیم، بنابراین این کاری است که قصد انجام آن را داشتیم.
مایگریشن بدون ذوب کردن مبدأها
یک مشکل دیگر وجود داشت: تغییر حلقه هش تغییر میدهد که برخی درخواستهای قابل کش کجا میروند. حتی اگر حلقه جدید بهتر باشد، تغییر دادن کل شبکه به یکباره عملاً تقریباً تمام محتوای کش شده را نامعتبر میکند. این امر یک بهینهسازی حافظه را به یک افزایش آخرالزمانی در ترافیک مبدأ تبدیل میکند.
بنابراین ما این را به یک سوئیچ جهانی تبدیل نکردیم. برای مدتی، PBR هر دو نسخه از بارگذار تعادل قابل کش را در حافظه حمل کرد: حلقه کهتامای قدیمی و حلقه کوچکتر جدید. هر درخواست از چارچوب مهاجرت عادی ما استفاده کرد تا تصمیم بگیرد کدام حلقه باید بکاند را انتخاب کند.
سپس ما مهاجرت را در لایهها انجام دادیم. ما با مکانهای اعتبارسنجی کوچک شروع کردیم، از گروههای به تدریج بزرگتر از مراکز داده عبور کردیم و تنها پس از آن به سمت بقیه جهان ادامه دادیم.
بخش مهم این بود که ما دو بعد را به طور مستقل کنترل کردیم: چقدر ترافیک از حلقه جدید استفاده کرد و آن ترافیک اجازه داشت کجا برود. در طول مهاجرت، ما ردیابیهای انتخاب بکاند، شمارندههای نسخه حلقه، خطاهای اتصال PBR، حافظه فرآیند، زمان راهاندازی، رفتار کش و ترافیک مبدأ را زیر نظر داشتیم. هنگامی که مهاجرت به ۱۰۰٪ رسید، مسیر قدیمی موقت حلقه را حذف کردیم، و تمام!
نمودار بالا مقایسه حافظه استفاده شده توسط PBR را در هفته تغییر در مقایسه با دادههای چند هفته قبل و همچنین نتیجه تفریق یکی از دیگری نشان میدهد. افت شدید روزی است که نسخه PBR با حلقههای هش بزرگ (که اکنون استفاده نمیشوند) برای همیشه از رده خارج شد.
خودتان امتحان کنید
تمام تغییراتی که در این پست در مورد آنها صحبت کردیم اکنون در pingora-ketama crate در قالب یک ویژگی کارگو در دسترس هستند. حلقه v2 دارای فرمت ذخیرهسازی فشرده، روش مرتبسازی سریعتر و قابلیت مقیاسبندی تعداد پایه هشها به ازای هر گد است. تمرکز ما در ایجاد این تغییرات روی پایداری و کنترل بود، بنابراین حلقه v1 دقیقاً مشابه چیزی است که پینگورا کهتاما همیشه استفاده کرده است.
فراتر از امتحان کردن تغییرات واقعی هشینگ سازگار ما، من میخواهم الهامبخش شما باشم تا در سیستمهای خودتان کاوش کنید تا ببینید چه تصمیمات «ساده» یا «واضحی» بردهای بالقوه را پنهان کردهاند، اگر مایل هستید وارد اعداد شوید. ممکن است نتوانید تمام مشکلات خود را با Rust حل کنید، اما ریاضیات جهانی است.
منبع: blog.cloudflare.com