بناء محرّك مطابقة أوامر بزمن أقل من ميكروثانية باستخدام C++20
كيف يحقق تصميم هياكل بيانات من ثلاث طبقات إلغاءً بتعقيد O(1) وزمن استجابة أقل من ميكروثانية.
النظام الذي تقوم عليه كل بورصة
يوجد محرّك مطابقة أوامر في قلب كل بورصة إلكترونية مثل NYSE وNASDAQ وCME. يطابق أوامر الشراء بأوامر البيع عند أفضل سعر متاح. يتطلب بناؤه على مستوى الأنظمة فهم أولوية السعر والزمن وتخصيص الذاكرة في المسار المتكرر وهندسة زمن الاستجابة دون الميكروثانية.
NanoMatch هو تنفيذي من الصفر باستخدام C++20، ويعالج 1M+ أمر في الثانية في اختبار اصطناعي أحادي الخيط، بزمن استجابة أقل من ميكروثانية.
هيكل البيانات ذو الطبقات الثلاث
قد يستخدم تنفيذ بسيط طابور أولوية واحدًا. يجد هذا الهيكل أفضل سعر بتعقيد O(1)، لكن إلغاء الأمر يستغرق O(n). في هذا التنفيذ، تجعل فهرسة مباشرة وطابور أوامر لكل مستوى سعري الإلغاء بتعقيد O(1).
يستخدم NanoMatch ثلاثة هياكل تتعاون معًا:
| الطبقة | الهيكل | الغرض |
|---|---|---|
| مستويات السعر | std::map<Price, PriceLevel> | ترتيب حسب السعر؛ std::greater للشراء (الأعلى أولًا)، وstd::less للبيع (الأدنى أولًا). إدراج O(log M)، وأفضل سعر عبر begin() بتعقيد O(1). |
| طابور الأوامر | std::list<Order> لكل مستوى | طابور FIFO عند كل سعر؛ إضافة O(1) وحذف بالمكرّر O(1). |
| البحث | std::unordered_map<OrderID, Iterator> | إلغاء O(1)؛ يعطي البحث بالتجزئة مكرّرًا في القائمة ويكون الحذف ثابت الزمن. |
أسعار صحيحة لتجنب أخطاء الفاصلة العائمة
تُخزّن الأسعار بالسنت كقيم int32_t ($101.50 = 10150). مقارنة الفاصلة العائمة (==) غير موثوقة بسبب خطأ التمثيل. قد تبقي في محرّك المطابقة مستويات ينبغي دمجها منفصلة، أو تطابق الأوامر بسعر خاطئ. تجعل العمليات الصحيحة المقارنة دقيقة وحتمية.
مخصّص الذاكرة المجمع
تعرّض كل عملية malloc / free في المسار المتكرر النظام لاستدعاءات النواة وتنافس أقفال المخصّص وتلوث الذاكرة المخبئية. يستخدم NanoMatch مخصّصًا مجمعًا مخصصًا بقائمة كتل حرة:
- يخصص مسبقًا
std::vector<T>متجاورًا بسعة ثابتة allocate()= أخذ رأس القائمة الحرة = O(1)، دون استدعاءات نظامdeallocate()= الإضافة إلى رأس القائمة = O(1)، دون استدعاءات نظام- توجد الذاكرة كلها في كتلة متجاورة واحدة ملائمة للذاكرة المخبئية
يبيّن الاختبار أن هذا المخصّص يزيل تذبذب التخصيص الذي يسبب ارتفاعات زمن الاستجابة الطرفي.
دلالات صحيحة لأنواع الأوامر
أربعة أنواع أوامر بدلالات مناسبة للأنظمة التشغيلية:
- Limit: تنفيذ الجزء القابل للمطابقة وإبقاء الباقي في دفتر الأوامر
- Market: ضبط السعر على
MAX/MINلضمان المطابقة، دون إبقاء الأمر في الدفتر - IOC (تنفيذ فوري أو إلغاء): مثل الأمر المحدد، لكن يُلغى الجزء غير المنفّذ
- FOK (تنفيذ كامل أو إلغاء): فحص مسبق ذري باستخدام
can_fill_completely()يمسح جميع المستويات القابلة للمطابقة قبل التنفيذ. عند نقص السيولة، لا يُنفّذ أي جزء
يُنفّذ التعديل بإلغاء الأمر ثم إضافته من جديد. ويفقد الأمر المعدّل أولوية الزمن كما يحدث في NYSE أو NASDAQ.
توزيع زمن الاستجابة
| المئين | زمن الاستجابة |
|---|---|
| p50 | 84 ns |
| p99 | 625 ns |
| p99.9 | 1,250 ns |
تبلغ نتيجة p99.9 نحو 15 ضعفًا لنتيجة p50. في هذا الاختبار، نشأت الارتفاعات من إعادة توازن الشجرة الحمراء السوداء عند إضافة مستوى سعري، ومن أوامر تعبر مستويات متعددة، ومن فقدان الذاكرة المخبئية في المستويات غير المستخدمة مؤخرًا.