Rust'ta Matching Engine Tasarımı: GC Duraklamaları Olmadan Price-Time Priority

Bir spot borsa matching engine'inin işi dardır. Sıralı bir komut akışını - yeni emir, iptal, değiştirme - alır, bunları price-time priority altında bir order book'a uygular ve sıralı bir olay akışı yayar: işlemler, defter güncellemeleri, retler, onaylar.

Zor olan her şey bu işin üstüne yığılmış üç kısıttan gelir: sonuç, aynı girdinin her replay'inde birebir aynı olmalı; kısmen gerçekleşen bir emrin kalanı kuyruktaki yerini korumalı; ve ani bir yük geldiğinde latency kuyruğu kıpırdamamalı.

Order book, FIFO kuyrukları üzerinde sıralı bir fiyat seviyesi indeksidir

Defter iki taraftır; her biri fiyata göre sıralanmış bir seviye koleksiyonudur. Bir seviye bir sayı değildir - o fiyattaki bekleyen emirlerin geliş sırasına göre dizilmiş bir kuyruğudur. Eşleştirme en iyi seviyeye sürekli, derin seviyelere ise nadiren dokunur; bu yüzden yapı zarafete göre değil, bu erişim örüntüsüne göre seçilir.

• Fiyatlar tick cinsinden tam sayıdır, asla kayan nokta değil - tick enstrümanın birimidir ve tam sayılarda karşılaştırma ve aritmetik kesindir
• Her taraf seviyelerini fiyat sırasında tutar ve en iyi fiyata arama yapmadan erişilir - defterin tepesi her komutta okunur
• Bir seviye, bekleyen emirlerden oluşan bir FIFO kuyruğunu ve toplam bekleyen miktarı tutar; böylece toplam, kuyruk baştan sona dolaşılarak yeniden hesaplanmak zorunda kalmaz
• Emirler önceden ayrılmış bir slab'de tutulur ve indeks handle'larıyla referanslanır; kuyruk ise intrusive'dir: sonraki ve önceki bağlantılar emir kaydının kendi içinde yaşar
• Client order id'den slab handle'a ayrı bir eşleme, iptal ve değiştirmeyi doğrudan bir aramaya dönüştürür; böylece bir iptal defteri asla taramaz
• Kuyruktan çıkarma arama ile değil handle ile yapılır - derinde bekleyen bir emrin iptali, defterin tepesindeki bir iptalle aynı maliyettedir

Intrusive kuyrukların ve indeks handle'larının sonucu şudur: bekleyen bir emir yaşadığı sürece bellekte hiç yer değiştirmez. Kuyruktaki konumu, nerede durduğunun değil bağlantılarının bir özelliğidir; ilerleyen aşamada kısmi gerçekleşmeleri ucuz kılan da budur.

Price-time priority, seviyeler üzerinde, ardından bir kuyruk üzerinde dönen bir döngüdür

Gelen agresif bir emir, karşı tarafı en iyi fiyattan içeriye doğru dolaşır. Her seviyede FIFO kuyruğunu baştan itibaren dolaşır. Seviye fiyatı gelen emir için artık kabul edilebilir olmadığında ya da gelen miktar sıfıra ulaştığında durur.

• En iyi karşı seviyeyi al; fiyatı gelen limit fiyatıyla kesişmiyorsa dur
• O seviye kuyruğunun en önündeki emri al - bu fiyattaki en eski emirdir ve zaman önceliği onun önce gerçekleşmesi demektir
• İşlem miktarı, iki kalan miktarın küçüğüdür; işlem fiyatı ise bekleyen emrin fiyatıdır, çünkü koşulları bekleyen emir belirlemiştir
• Her iki kalanı azalt, işlem olayını yay ve seviye toplamını azalt
• Bekleyen emrin kalanı sıfıra ulaşırsa onu kuyruktan çıkar ve slab slotunu geri ver; seviye boşalırsa seviyeyi kaldır
• Gelen miktar sıfır olana ya da kabul edilebilir seviye kalmayana kadar tekrarla

Emir tipi semantiği, bu döngünün içinde değil sınırında alınan kararlardır. Immediate-or-cancel kalanı deftere koymak yerine düşürür. Fill-or-kill önce kuru bir geçiş yapar ve ya bütünüyle icra eder ya da reddeder. Post-only, emir gelişinde kesişecekse reddeder. Bunları döngünün dışında tutmak, döngünün defter durumunun değiştiği tek yer olarak kalması demektir.

Kendi kendine işlem engelleme, asgari miktarlar ve tick ile lot doğrulaması da döngüden önceye aittir. Eşleştirmeye ulaşan bir emrin düzgün biçimlendirildiği zaten kanıtlanmıştır; böylece döngüde onu yavaşlatacak ya da üzerinde anlaşmazlığa düşülecek hata dalları bulunmaz.

Kuyruğu öngörülebilir kılan determinizm, onu bozan ise bellek ayırmadır

Ortalama latency nadiren sorundur. Sorun, ani yük anındaki en kötü ölçümdür - motorun en çok önem taşıdığı ve bir stop-the-world duraklamasının düşmesinin en muhtemel olduğu an. Garbage collector'lı yönetilen bir çalışma zamanında bu duraklamayı siz değil collector planlar ve tam da çöpü üreten yoğunluğun ortasına düşer.

Elle bellek ayırma, aynı sorunun daha küçük bir sürümüdür. Genel amaçlı bir ayırıcı free list'leri dolaşabilir, bir kilit alabilir ya da çekirdekten daha fazla bellek isteyebilir; bunu yapan çağrı da kuyrukta görünen çağrıdır. Çözüm her iki durumda da aynı: sıcak yolda hiç bellek ayırmayın.

• Emir kayıtları, seviye kayıtları ve olay tamponları başlangıçta boyutlandırılan arenalardan gelir - kararlı durumda eşleştirme yolundaki bellek ayırma sayısı sıfırdır
• Boşalan slotlar arena içindeki bir free list'e döner; böylece yoğun bir enstrüman tüm oturum boyunca aynı belleği yeniden kullanır
• Yapılar sabit biçimli ve sabit boyutludur; kapasite limitleri bir büyüme olayı olarak değil, bir ret olarak uygulanır
• Dışa giden olaylar, başka bir iş parçacığının boşalttığı önceden ayrılmış bir ring buffer'a yazılır - eşleştirme iş parçacığı asla bir tüketici yüzünden bloklanmaz
• Eşleştirme iş parçacığı defter üzerinde tek yazıcıdır; bu yüzden defter durumunda kilit ve çözülecek bir sıralama belirsizliği yoktur
• Girdiler motora ulaşmadan önce sıralanır ve sırayı geliş zamanı değil, sıra numarası belirler

Bir motor, aynı girdi dizisi farklı bir makinede ve bir yıl sonra bayt bayt aynı çıktı dizisini ürettiğinde deterministiktir. Eşleştirme yolu içinde duvar saatini, iş parçacığı zamanlamasını veya hash yineleme sırasını okuyan her şey bu özelliği bozar.

Bu yüzden zaman damgaları bir girdidir, motorun kendisi için okuduğu bir şey değil. Sequencer bir komutu kabul ederken damgalar ve eşleştirme döngüsü damgayı veri olarak ele alır. Rastgelelik gerekiyorsa, tohumu journal'ın parçası olan tohumlanmış bir üreteçten gelir.

Motorun durumu journal'dır, defter ise onun bir önbelleğidir

Kurtarma, eşleştirme çalıştıktan sonra üstüne eklenen bir özellik değildir. Motor, kabul edilen komutları sıra düzeninde yalnızca ekleme yapılan bir journal'a yazar ve bellekteki defter, o journal'ın katlanmasının sonucundan başka bir şey değildir. Bir çökmeden sonra yeniden kurmak, onu replay etmek demektir.

• Bir komut eşleştirilmeden önce journal'a yazılır ve kalıcı hale gelir; böylece kabul edilen bir emir, onay ile icra arasındaki bir çökmede kaybolamaz
• Journal çıktı değil, girdi dizisidir - çıktılar türetilir ve replay'in yaptığı tam olarak onları yeniden türetmektir
• Defterin periyodik anlık görüntüleri alındıkları sıra numarasını taşır; böylece kurtarma bir anlık görüntüyü yükler ve journal'ın yalnızca kuyruğunu replay eder
• Anlık görüntü ile replay'in uyumu varsayılmaz, denetlenir: önceki anlık görüntüden replay, bir sonrakini birebir üretmelidir
• Olay akışı aynı sıra numaralarını taşır; böylece aşağı akıştaki tüketiciler - risk, takas, piyasa verisi - elle yeniden senkronize edilmek yerine bilinen bir noktadan devam ettirilebilir

Journal'ı motor yazar, ama kalıcılık depolama yolunun ve onay çıkmadan önce kaydın kaç makinede bulunduğunun bir özelliğidir. Bu bir replikasyon ve donanım kararıdır; kurtarma süresi de asıl orada kazanılır ya da kaybedilir.

Test etmek, deterministik replay artı her zaman geçerli kalması gereken değişmezler demektir

Motoru test edilebilir kılan şey determinizmdir. Aynı girdi aynı çıktıyı verdiği için kaydedilmiş bir oturum bir regresyon testidir ve bir kez bulunan bir hata, peşinden koşulmak yerine birebir yeniden üretilebilir.

• Replay düzeneği: kaydedilmiş bir komut dizisini besle, yayılan olay akışını saklananla karşılaştır ve ilk ayrışmada sıra numarasıyla birlikte hata ver
• Test derlemelerinde her komuttan sonra değişmez kontrolleri - kuyruklar geliş sırasına göre sıralı, seviye toplamları kuyruklarının toplamına eşit, kesişen defter yok, toplam miktar her işlemde korunuyor
• Rastgele ama düzgün biçimlendirilmiş komut dizileri üreten ve belirli sonuçlar yerine değişmezleri doğrulayan property based testler
• Diferansiyel bir referans modeli: naif veri yapılarıyla yazılmış, yavaş ama bariz biçimde doğru bir uygulama aynı girdiyle çalıştırılır ve her uyuşmazlık hızlı olandaki bir hata sayılır
• Bozuk girdinin dışarıdan geldiği ve bir panic'in eşleştirme iş parçacığını düşüreceği decoder sınırında fuzzing
• Sizi endişelendiren yük profili altında latency ölçümü; ortalama yerine dağılımı kaydederek, çünkü tasarımı belirleyen sayı kuyruktur

Rust burada size ne verir, ne vermez

Rust, döngüyü kendi başına hızlandırmaktan çok bir sorun sınıfını ortadan kaldırır. Garbage collector yoktur, dolayısıyla arkanızdan planlanan bir duraklama da yoktur. Ownership sayesinde tek yazıcı disiplini, bir kod incelemesinin fark etmesi gereken bir şey olmaktan çıkıp derleyicinin dayattığı bir şeye dönüşür. Lifetime'ı olmayan bir dilde hataya açık olan slab handle'ları ve intrusive bağlantılar burada denetlenebilir. Debug derlemelerinde tam sayı taşmasında oluşan panic'ler, bir defteri sessizce bozan bir hata sınıfını yakalar.

Dürüst sınır şu: kuyruk latency'sini belirleyen şeylerin çoğu dil değildir:

• Çekirdek zamanlaması, kesme işleme, CPU pinning ve güç yönetimi kuyruğu eşleştirme kodundan daha çok oynatır
• Ağ arayüzü, kernel bypass'ın varlığı ya da yokluğu ve borsaya giden fiziksel yol, motorun altına inemeyeceği bir taban belirler
• Sınırdaki serileştirme ve wire protokolü çoğu zaman baskın maliyettir, eşleştirmenin kendisi değil
• Eşleştirme semantiği, emir tipleri, ücret ve iade kuralları ile piyasa seansları iş kararlarıdır - hızlıca uygulanan yanlış bir kural yine de yanlıştır
• Risk kontrolleri, pozisyon limitleri ve takas yolu motorun dışında yaşar; kendi latency'leri ve kendi hata modları vardır
• Operasyon - dağıtım, izleme, başarısız bir replay için runbook - garantilerin bir prodüksiyon olayıyla temasa dayanıp dayanmadığını belirler

Rust'ın da bir bedeli var. Borrow checker, hâlâ oturmamış bir tasarımın ilk haftalarını yavaşlatır; borsaya özgü protokoller için ekosistem eski dillerdekinden daha incedir ve lock-free yapıların etrafındaki unsafe bloklar, başka her yerdeki eşdeğer kod kadar inceleme disiplini ister. Onu seçmek, geliştirici konforuyla ilgili değil, latency kuyruğu ve tek yazıcılı bir çekirdekte bellek güvenliğiyle ilgili bir karardır.

amBrain 2019'dan beri Erivan, Ermenistan'da trading altyapısı kuruyor; sıcak yollar Rust ile yazılıyor - piyasa verisi 5 ms altında, işlem öncesi risk kontrolleri 1 ms altında. Bir matching engine tasarlıyorsanız ve defter yapısını, journal formatını ya da replay düzeneğini birlikte gözden geçirmek istiyorsanız, bu konuşmayı sıcak yolun ilk satırı yazılmadan önce yapmaya değer.