إدارة الذاكرة
السر وراء سرعة Bing: كيف تفوق mimalloc على مقايضة تخصيص الذاكرة بـ 12,000 سطر
يستخدم مُخَصِّص mimalloc من Microsoft Research آلاف القوائم الحرة لكل صفحة وتقنية ذكية لسرقة الصفحات لتحقيق التزامن العالي وانخفاض هدر الذاكرة، كما توضح مجموعة RiSE في مدونة تقنية جديدة.
غالبًا ما يمر تخصيص الذاكرة دون أن يلاحظه أحد في أداء الأنظمة. لكن بالنسبة لفريق Bing في Microsoft، فإن التحول إلى مُخَصِّص مخصص صممه قسم الأبحاث الخاص بالشركة ترجم مباشرة إلى أوقات استجابة أسرع. هذا المُخَصِّص، mimalloc، هو موضوع منشور مدونة جديد من مجموعة RiSE في Microsoft Research، يشرح قرارات التصميم التي تسمح له بالتوسع من بيئة تشغيل لغة برمجة أحادية الخيط إلى خدمة سحابية بحجم 500 جيجابايت.
باستخدام 12,000 سطر فقط من لغة C، تم تصميم mimalloc ليكون مضغوطًا عن قصد. يكمن ابتكاره الحقيقي في كيفية تجاوزه لمعضلة كلاسيكية في الأنظمة: الاختيار بين التوسع عبر العديد من الخيوط والحفاظ على استخدام الذاكرة قريبًا مما يحتاجه التطبيق بالفعل. تتعمق المدونة، المنشورة على موقع Microsoft Research، في البنية بعمق تقني غير معتاد، بما في ذلك مقتطفات من المسار السريع المسار ووصف لآلية "سرقة الصفحات" المطورة مع فريق Azure Cosmos DB.
المسار السريع: فروع قليلة، لا عمليات ذرية
تتمثل الفكرة الأساسية لـ mimalloc في أن معظم عمليات التخصيص صغيرة ومحلية للخيط. يحصل كل خيط على كومة محلية خاصة به، أو "theap"، والتي تمتلك مجموعة من "صفحات mimalloc" بحجم 64 كيلوبايت. تحتوي كل صفحة على كتل من فئة حجم واحدة. لتخصيص كتلة، يقوم الخيط ببساطة بنقلها من قائمة حرة، دون أقفال، دون عمليات ذرية. توفر المدونة مخرجات التجميع للمسار السريع على x64: سبعة تعليمات مع فرعين نادرين فقط (واحد للتخصيصات كبيرة الحجم، وآخر للصفحة الفارغة).
يأتي هذا التقليل من الفروع من استراتيجية تهيئة دقيقة: مؤشر theap المحلي للخيط ليس فارغًا أبدًا، وجميع الإدخالات في مصفوفة small_pages تشير إلى صفحات فارغة مهيأة مسبقًا (قائمتهم الحرة فارغة). كما يلاحظ المؤلفون، فإن هذا يلغي فحصين شرطيين تحتاجهما معظم المُخَصِّصات، مما يحول الحالة الشائعة إلى خط مستقيم من التعليمات.
ثلاث قوائم حرة لكل صفحة، الإلهام العشوائي
حيث يختلف mimalloc بشكل حاد عن أقرانه هو في تصميم القائمة الحرة. تحتفظ كل صفحة من صفحات mimalloc بثلاث قوائم حرة: القائمة الرئيسية free للتخصيصات، وقائمة local_free للكتل التي يحررها الخيط المالك، وقائمة thread_free، الذرية، للكتل التي تحررها خيوط أخرى. يمكن للبرنامج بسهولة أن يكون لديه آلاف القوائم الحرة قيد التشغيل.
تربط المدونة هذا التصميم صراحة بالخوارزميات العشوائية. تمامًا كما تستخدم شجرة treap الانقسامات العشوائية للحفاظ على توازن الشجرة دون دوران معقد، يعتمد mimalloc على قانون الأعداد الكبيرة: مع آلاف القوائم الذرية لكل صفحة، فإن احتمالية محاولة خيطين تحرير الذاكرة لنفس الصفحة في وقت واحد ضئيلة. معظم عمليات المقارنة والتبديل تكون غير متنازع عليها ورخيصة. يكتب المؤلفون: "بالمحض الصدفة، نحصل أيضًا على أشجار متوازنة بما يكفي"، ممددين التشبيه.
يحسن هذا الترتيب لكل صفحة أيضًا من توطين ذاكرة التخزين المؤقت. نظرًا لأن التخصيص يميل إلى البقاء داخل نفس الصفحة حتى تمتلئ، فمن المحتمل أن تكون الكتل المحررة حديثًا في نفس خطوط ذاكرة التخزين المؤقت التي يستخدمها الخيط بالفعل، وهذا تناقض حاد مع التصميمات التي تحتوي على قائمة حرة واحدة لكل فئة حجم، والتي يمكنها توزيع الكتل عبر الذاكرة.
معضلة المُخَصِّص الثلاثية: مقاييس تظهر التوتر
تتضمن المدونة معيارًا يوضح المقايضة. باستخدام مجموعة خيوط Windows مع حوالي 800 خيط نشط، يقوم الاختبار بتشغيل عبء عمل يتناوب بين التخصيص وإلغاء التخصيص وفترات الحظر القصيرة، وهي محاكاة للخدمات السحابية الحديثة. تتم مقارنة ثلاثة مُخَصِّصات:
- مُخَصِّص النظام القياسي: مشاركة ممتازة للذاكرة (1.1× فقط ملتزم على البيانات الحية)، لكنه تمكن من تخصيص 56 جيجابايت فقط خلال مدة الاختبار. لم يتوسع.
- مُخَصِّص متزامن منافس: خصص 262 جيجابايت، أي ما يقرب من 4 أضعاف، لكنه التزم بذاكرة أكبر 4 مرات من البيانات الحية. على نطاق واسع، تصبح هذه النسبة غير مقبولة.
- mimalloc: خصص نفس 262 جيجابايت مع الحفاظ على الذاكرة الملتزمة عند 1.3× فقط من البيانات الحية. يبقى الخط الأحمر (الملتزم) قريبًا من الخط الأزرق (الحي).
تنسج المدونة الفضل في هذا الاختراق إلى "سرقة الصفحات"، وهي آلية تم تطويرها مع فريق Azure Cosmos DB والتي تسمح للخيوط بالاستيلاء على الصفحات دون مزامنة باهظة الثمن عبر الخيوط. يعد المؤلفون بتقرير فني قادم مع وصف دقيق، لكن نتائج المعيار تشير بالفعل إلى أن mimalloc يحقق ما كان يعتبر مستحيلًا منذ فترة طويلة: توسيع نطاق الإنتاجية دون تفجير الذاكرة.
من Lean إلى Bing إلى CPython
تم تصميم mimalloc في الأصل عام 2020 لدعم لغتي البرمجة Lean و Koka، اللتين تعتمدان على العد المرجعي الموجه من المترجم، ومنذ ذلك الحين تم اعتماده على نطاق واسع خارج Microsoft Research. تستخدمه Bing في الإنتاج، مما يساهم مباشرة في أوقات استجابة أسرع. خارج الشركة، هو مُخَصِّص الذاكرة لإصدار NoGIL من CPython 3.13+، ومدمج في Unreal Engine، ويستخدم في ألعاب مثل Death Stranding. غلاف Rust الخاص به وحده يشهد أكثر من 100,000 تحميل يوميًا.
تم استضافة المشروع على GitHub وحصل على أكثر من 12,000 نجمة. توجد إصدارات لأنظمة Windows و macOS و Linux و FreeBSD و NetBSD و DragonFly BSD ووحدات تحكم ألعاب مختلفة. تؤكد المدونة أن هياكل البيانات الداخلية الواضحة، فلسفة "الجداول، وليست الرسوم البيانية الانسيابية" المقتبسة من Fred Brooks، جعلت من السهل على المساهمين الخارجيين نقل وتخصيص المُخَصِّص مقارنة بالعديد من مُخَصِّصات الصناعة.
ما يعنيه هذا لبناة الأنظمة
بالنسبة للفرق التي تبني خدمات عالية التزامن، خاصة تلك التي تستخدم نماذج لغوية كبيرة بأحجام ذاكرة تصل إلى مئات الجيجابايت، فإن أوقات التخصيص الأسوأية المحدودة لـ mimalloc والتجزئة الداخلية المنخفضة تقدم مسارًا ملموسًا لأداء أفضل دون إعادة كتابة كود التطبيق. إنه بديل جاهز لـ malloc و free.
الدرس الأعمق هو أن المُخَصِّص يتوسع ليس بسبب بنية بيانات ثورية ولكن بسبب رهان إحصائي متعمد: وزع تكلفة التنسيق عبر آلاف القوائم الصغيرة، وستنخفض احتمالية التعارض. في عصر يستمر فيه عدد الخيوط لكل خادم في النمو، وحيث يستهلك استدلال نماذج اللغات الكبيرة غالبًا مئات الجيجابايت، فإن هذا الرهان يؤتي ثماره في الإنتاج، على نطاق واسع، داخل Microsoft وخارجها.