ساخت موتور تطبیق سفارش با تأخیر کمتر از یک میکروثانیه در 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 است. در این بنچمارک، جهش‌ها از متعادل‌سازی درخت قرمزـسیاه هنگام افزودن سطح قیمت، عبور سفارش‌ها از چند سطح و خطای حافظهٔ نهان در سطوح سرد ناشی شدند.