تصميم matching engine بلغة Rust: price-time priority بلا وقفات GC

الـ matching engine في بورصة فورية مهمته ضيقة. يأخذ تدفقًا مرتبًا من الأوامر - أمر جديد، إلغاء، استبدال - ويطبّقها على order book وفق price-time priority، ثم يُصدر تدفقًا مرتبًا من الأحداث: صفقات، وتحديثات دفتر، ورفوض، وإقرارات.

وكل ما فيه من صعوبة يأتي من ثلاثة قيود مكدّسة فوق تلك المهمة: أن تكون النتيجة متطابقة في كل إعادة تشغيل للمدخل نفسه، وأن تحتفظ بقية الأمر المنفَّذ جزئيًا بمكانها في الطابور، وألا يتحرك ذيل الـ latency عند وصول اندفاع.

الـ order book فهرس مرتب لمستويات السعر فوق طوابير FIFO

الدفتر جانبان، كل منهما مجموعة مستويات مرتبة بالسعر. والمستوى ليس رقمًا - إنه طابور أوامر راكدة عند ذلك السعر، بترتيب الوصول. والمطابقة تلمس أفضل مستوى باستمرار والمستويات العميقة نادرًا، فتُختار البنية لنمط الوصول هذا لا للأناقة.

• الأسعار أعداد صحيحة بالـ ticks، لا أعداد عائمة أبدًا - فالـ tick هو وحدة الأداة، والمقارنة والحساب على الأعداد الصحيحة دقيقان تمامًا
• يحفظ كل جانب مستوياته بترتيب السعر، مع بلوغ أفضل سعر دون بحث - فقمة الدفتر تُقرأ عند كل أمر
• يحمل المستوى طابور FIFO من الأوامر الراكدة، مع الكمية الراكدة المجمّعة، فلا يلزم إعادة حساب المجموع بالمرور على الطابور
• تُحفظ الأوامر في slab مخصَّص مسبقًا ويُشار إليها بمقابض فهرسية، والطابور تطفلي: روابط التالي والسابق تسكن داخل سجل الأمر نفسه
• خريطة منفصلة من معرّف أمر العميل إلى مقبض الـ slab تجعل الإلغاء والاستبدال بحثًا مباشرًا، فلا يمسح الإلغاء الدفتر أبدًا
• الإزالة من الطابور بالمقبض لا بالبحث - فإلغاء أمر راكد عميق يكلّف مثل إلغاء عند قمة الدفتر

نتيجة الطوابير التطفلية والمقابض الفهرسية أن الأمر الراكد لا يتحرك في الذاكرة أبدًا ما دام حيًا. وموضعه في الطابور خاصية لروابطه، لا لمكان جلوسه، وهذا ما يجعل التنفيذات الجزئية رخيصة لاحقًا.

الـ price-time priority حلقة على المستويات، ثم على طابور

الأمر المهاجم الوارد يمشي على الجانب المقابل من أفضل سعر إلى الداخل. وعند كل مستوى يمشي على طابور FIFO من مقدمته. ويتوقف حين لا يعود سعر المستوى مقبولًا للأمر الوارد أو حين تبلغ الكمية الواردة صفرًا.

• خذ أفضل مستوى مقابل؛ وإن كان سعره لا يتقاطع مع سعر الـ limit الوارد، فتوقف
• خذ الأمر الأمامي في طابور ذلك المستوى - فهو الأقدم عند ذلك السعر، وأولوية الوقت تعني أنه يُنفَّذ أولًا
• الكمية المتداولة هي الأصغر بين الكميتين المتبقيتين؛ وسعر الصفقة هو سعر الأمر الراكد، لأن الأمر الراكد هو من وضع الشروط
• أنقص البقيتين، وأصدر حدث الصفقة، وأنقص مجموع المستوى
• إذا بلغت بقية الأمر الراكد صفرًا، افصله عن الطابور وأعد خانته في الـ slab؛ وإذا فرغ المستوى، احذف المستوى
• كرّر حتى تصير الكمية الواردة صفرًا أو لا يبقى مستوى مقبول

دلالات أنواع الأوامر قرارات تُتخذ عند حدود هذه الحلقة لا داخلها. فـ immediate-or-cancel يُسقط البقية بدل إراحتها. وfill-or-kill يجري تمريرة جافة أولًا ثم ينفذ كاملًا أو يرفض. وpost-only يرفض إن كان الأمر سيتقاطع عند الوصول. وإبقاء هذه خارج الحلقة يعني أن الحلقة تبقى المكان الوحيد الذي تتغير فيه حالة الدفتر.

منع التداول الذاتي والكميات الدنيا والتحقق من الـ tick واللوت تنتمي كذلك إلى ما قبل الحلقة. فالأمر الذي يبلغ المطابقة قد ثبتت سلامة بنيته، فلا تحمل الحلقة فروع أخطاء تبطّئها أو يُختلف حولها.

الحتمية هي ما يجعل الذيل قابلًا للتنبؤ، والتخصيص هو ما يكسره

نادرًا ما يكون متوسط الـ latency هو المشكلة. المشكلة أسوأ قياس أثناء الاندفاع، وهو الوقت الذي يهم فيه المحرك أكثر ما يهم والأرجح أن تقع فيه وقفة توقف العالم. وتحت بيئة تشغيل مُدارة فيها garbage collector، يجدول تلك الوقفة الجامعُ لا أنت، وتقع في منتصف الاندفاع الذي أنتج النفايات.

التخصيص اليدوي نسخة أصغر من المشكلة نفسها. فمخصِّص عام قد يمشي على قوائم حرة، أو يأخذ قفلًا، أو يطلب من النواة ذاكرة إضافية، والاستدعاء الذي يفعل ذلك هو الذي يظهر في الذيل. والعلاج واحد في الحالتين: لا تخصّص على المسار الساخن إطلاقًا.

• سجلات الأوامر وسجلات المستويات ومخازن الأحداث تأتي من ساحات محدَّدة الحجم عند الإقلاع - وعدد التخصيصات في الحالة المستقرة على مسار المطابقة صفر
• الخانات المحرَّرة تعود إلى قائمة حرة داخل الساحة، فتعيد الأداة النشطة استخدام الذاكرة نفسها طوال الجلسة
• البنى ثابتة الشكل وثابتة الحجم، وحدود السعة تُفرَض كرفض لا كحدث نمو
• تُكتب الأحداث الصادرة في ring buffer مخصَّص مسبقًا يفرغه خيط آخر - ولا يُحجب خيط المطابقة أبدًا على مستهلك
• خيط المطابقة كاتب واحد فوق الدفتر، فلا قفل على حالة الدفتر ولا غموض ترتيب يحتاج حسمًا
• تُرتَّب المدخلات تسلسليًا قبل بلوغها المحرك، ورقم التسلسل، لا وقت الوصول، هو ما يحدد الترتيب

يكون المحرك حتميًا حين ينتج تسلسل المدخلات نفسه تسلسل المخرجات نفسه، بايتًا ببايت، على جهاز آخر وبعد سنة. وأي شيء يقرأ ساعة الحائط أو جدولة الخيوط أو ترتيب تكرار الـ hash داخل مسار المطابقة يكسر هذه الخاصية.

لذلك فالطوابع الزمنية مدخل، لا شيء يقرأه المحرك بنفسه. فالمُسلسِل يختم الأمر حين يقبله، وحلقة المطابقة تعامل الختم كبيانات. والعشوائية، إن لزمت، تأتي من مولّد ببذرة تكون البذرة نفسها جزءًا من السجل.

السجل هو حالة المحرك، والدفتر ذاكرة مؤقتة له

الاسترداد ليس ميزة تُركَّب بعد أن تعمل المطابقة. يكتب المحرك سجلًا للإلحاق فقط بالأوامر المقبولة بترتيب التسلسل، والدفتر في الذاكرة ليس إلا نتيجة طيّ ذلك السجل. وإعادة البناء بعد عطل تعني إعادة تشغيله.

• يُسجَّل الأمر في السجل ويصبح دائمًا قبل مطابقته، فلا يمكن أن يضيع أمر مقبول بسبب عطل بين الإقرار والتنفيذ
• السجل هو تسلسل المدخلات لا المخرجات - فالمخرجات مشتقة، وإعادة اشتقاقها هي بالضبط ما تفعله إعادة التشغيل
• اللقطات الدورية للدفتر تحمل رقم التسلسل الذي أُخذت عنده، فيحمّل الاسترداد لقطة ويعيد تشغيل ذيل السجل فقط
• توافق اللقطة وإعادة التشغيل يُفحَص لا يُفترض: إعادة التشغيل من اللقطة السابقة يجب أن تعيد إنتاج اللقطة التالية
• تدفق الأحداث يحمل أرقام التسلسل نفسها، فيمكن استئناف المستهلكين في اتجاه المصب - المخاطر والتسوية وبيانات السوق - من نقطة معلومة بدل إعادة مزامنتهم يدويًا

المحرك يكتب السجل، لكن الديمومة خاصية لمسار التخزين ولعدد الأجهزة التي تملك السجل قبل خروج الإقرار. وذلك قرار نسخ متماثل وعتاد، وهو حيث يُربح زمن الاسترداد أو يُخسر فعليًا.

الاختبار هو إعادة تشغيل حتمية مع ثوابت يجب أن تصمد دائمًا

الحتمية هي ما يجعل المحرك قابلًا للاختبار. فلأن المدخل نفسه يعطي المخرج نفسه، تصير الجلسة المسجّلة اختبار انحدار، ويمكن إعادة إنتاج أي عطل عُثر عليه مرة واحدة بدقة بدل مطاردته.

• منصة إعادة التشغيل: أطعمها تسلسل أوامر مسجّلًا، وقارن تدفق الأحداث الصادر بالمخزَّن، وأخفق عند أول اختلاف مع رقم التسلسل
• فحوص الثوابت بعد كل أمر في بنيات الاختبار - طوابير مرتبة بالوصول، ومجاميع المستويات مساوية لمجموع طوابيرها، ولا دفتر متقاطع، وكمية إجمالية محفوظة عبر كل صفقة
• اختبارات قائمة على الخصائص تولّد تسلسلات أوامر عشوائية لكن سليمة البنية وتتحقق من الثوابت بدل نتائج بعينها
• نموذج مرجعي تفاضلي: تنفيذ بطيء وصحيح بداهةً ببنى بيانات ساذجة، يُشغَّل على المدخل نفسه، وأي اختلاف يُعامَل كخلل في التنفيذ السريع
• اختبار fuzzing عند حدود فاكّ الترميز، حيث يصل المدخل المشوَّه من الخارج وحيث قد يُسقط أي panic خيط المطابقة
• قياس الـ latency تحت شكل الاندفاع الذي يقلقك، بتسجيل التوزيع لا المتوسط، لأن الذيل هو الرقم الذي يحسم التصميم

ما تمنحك إياه Rust هنا، وما لا تمنحه

تزيل Rust فئة من المشكلات أكثر مما تجعل الحلقة أسرع بذاتها. فلا يوجد garbage collector، فلا تُجدول وقفة من وراء ظهرك. والملكية تجعل انضباط الكاتب الواحد شيئًا يفرضه المترجم بدل شيء على مراجعة الكود أن تلحظه. ومقابض الـ slab والروابط التطفلية، وهي مظنة الخطأ في لغة بلا أعمار، قابلة للفحص هنا. وحالات panic عند تجاوز الأعداد الصحيحة في بنيات التصحيح تلتقط صنفًا من العلل يفسد الدفتر بصمت.

الحد الأمين هو أن معظم ما يحدد latency الذيل ليس اللغة:

• جدولة النواة، ومعالجة المقاطعات، وتثبيت المعالج، وإدارة الطاقة تحرّك الذيل أكثر مما يحركه كود المطابقة
• واجهة الشبكة، ووجود تجاوز النواة أو غيابه، والمسار الفيزيائي إلى المنصة تضع أرضية لا ينزل المحرك تحتها
• التسلسل وبروتوكول السلك عند الحدود هما غالبًا الكلفة الغالبة، لا المطابقة نفسها
• دلالات المطابقة وأنواع الأوامر وقواعد الرسوم والحسومات ومراحل السوق قرارات عمل - والقاعدة الخاطئة المنفذة بسرعة تبقى خاطئة
• فحوص المخاطر وحدود المراكز ومسار التسوية تسكن خارج المحرك ولها latency خاص بها وأنماط فشل خاصة بها
• التشغيل - النشر والمراقبة ودليل التصرف عند فشل إعادة التشغيل - هو ما يقرر هل تنجو الضمانات من الاحتكاك بحادث في الإنتاج

لـ Rust كلفة أيضًا. فالـ borrow checker يبطّئ الأسابيع الأولى لتصميم ما زال يتحرك، والمنظومة الخاصة ببروتوكولات البورصات أرقّ منها في لغات أقدم، وكتل unsafe حول البنى اللاقفلية تحتاج انضباط المراجعة نفسه المطلوب لأي كود مكافئ في أي مكان. واختيارها قرار بشأن ذيل الـ latency وسلامة الذاكرة في نواة ذات كاتب واحد، لا قرار بشأن راحة المطور.

تبني amBrain بنية تداول تحتية في يريفان، أرمينيا منذ 2019، بمسارات ساخنة بلغة Rust - بيانات سوق تصل في أقل من 5 ms، وفحوص مخاطر قبل التداول في أقل من 1 ms. إن كنت تصمم matching engine وتريد استعراض بنية الدفتر أو صيغة السجل أو منصة إعادة التشغيل، فهذا حديث يستحق أن يجري قبل كتابة أول سطر في المسار الساخن.