Lock-freie Datenstrukturen im Trading.

Locks sind in Low-Latency-Systemen das, was Stop-Schilder im Autobahnnetz wären: funktioniert irgendwie, aber zerstört den Durchsatz. Lock-freie Datenstrukturen erlauben mehreren Threads, parallel zu arbeiten, ohne sich gegenseitig zu blockieren — zu einem Preis, den man kennen sollte.

Was bedeutet „lock-frei" überhaupt?

Ein Algorithmus heißt lock-frei, wenn mindestens einer der konkurrierenden Threads garantiert in endlicher Zeit Fortschritt macht. Das schließt klassische Mutexe aus — dort kann jeder Thread blockiert sein, wenn der Eigentümer eingefroren ist. Strenger ist wait-free: jeder Thread macht in endlicher Zeit Fortschritt, unabhängig vom Verhalten der anderen. Wait-frei ist akademisch elegant, in der Praxis selten nötig und meist teurer als lock-frei.

Wichtig: „lock-frei" heißt nicht automatisch „schnell". Lock-freie Algorithmen können unter hoher Contention schlechter performen als ein simpler Spinlock. Der Vorteil zeigt sich primär in zwei Dimensionen: Latenz-Tail (keine unerwarteten Kontextwechsel) und Skalierung über viele Kerne hinweg.

Das Arbeitstier: SPSC-Ringbuffer.

Die am häufigsten gebrauchte lock-freie Struktur in Trading-Systemen ist der Single-Producer-Single-Consumer-Ringbuffer. Genau ein Thread schreibt, genau einer liest. Die Implementierung ist einfach, die Performance hervorragend — typisch 10–20 ns pro Operation auf modernen CPUs.

#include <atomic>
#include <array>
#include <optional>

template <typename T, std::size_t N>
class SpscRing {
    static_assert((N & (N - 1)) == 0, "N must be power of two");
public:
    bool push(const T& v) noexcept {
        auto head = head_.load(std::memory_order_relaxed);
        auto next = (head + 1) & (N - 1);
        if (next == tail_.load(std::memory_order_acquire))
            return false; // full
        buffer_[head] = v;
        head_.store(next, std::memory_order_release);
        return true;
    }

    std::optional<T> pop() noexcept {
        auto tail = tail_.load(std::memory_order_relaxed);
        if (tail == head_.load(std::memory_order_acquire))
            return std::nullopt; // empty
        T v = buffer_[tail];
        tail_.store((tail + 1) & (N - 1), std::memory_order_release);
        return v;
    }

private:
    alignas(64) std::atomic<std::size_t> head_{0};
    alignas(64) std::atomic<std::size_t> tail_{0};
    std::array<T, N> buffer_;
};

Die alignas(64)-Direktive ist nicht kosmetisch: ohne sie würden head_ und tail_ in dieselbe Cache-Line fallen und sich gegenseitig invalidieren — sogenanntes False Sharing. Mit korrektem Alignment liegt jede Variable in ihrer eigenen Line, und Producer und Consumer stören sich nicht.

Memory Ordering verstehen.

Die Wahl der Memory-Order-Argumente ist der heikelste Teil. Vereinfacht:

• relaxed: nur Atomarität, keine Garantien über Reihenfolge zu anderen Operationen. Ideal für Zähler.
• acquire/release: bildet eine Happens-Before-Beziehung. Was vor dem Release geschrieben wurde, ist nach dem matching Acquire sichtbar. Der praktische Standard für die meisten Producer-Consumer-Muster.
• seq_cst: globale totale Ordnung über alle seq_cst-Operationen. Teuer, fast nie wirklich nötig — aber sicher.

Faustregel: Beginnen Sie mit seq_cst, messen Sie, und reduzieren Sie nur auf acquire/release, wenn Sie wirklich verstehen, was Sie tun. Die Performance-Gewinne sind real, die Falltiefe bei Bugs aber auch.

MPSC und MPMC: Die nächste Stufe.

Multi-Producer-Single-Consumer (MPSC) braucht einen Atomic-Compare-and-Swap (CAS) auf dem Head-Pointer, weil sich Producer um Slots streiten. Implementierungen wie die von Dmitry Vyukov sind seit Jahren etabliert und kommen mit minimalem Overhead aus.

MPMC ist deutlich teurer. Hier hilft oft eine Partitionierung: statt einer großen MPMC-Queue mehrere SPSC- oder MPSC-Queues, deterministisch verteilt nach Symbol-Hash oder Order-ID. Das ist die Architektur, die unter anderem LMAX und CME intern fahren.

Hazard Pointers und das ABA-Problem.

Das berüchtigte ABA-Problem: Thread A liest Pointer X, wird unterbrochen. In der Zeit wird X freigegeben, neu allokiert und zufällig auf dieselbe Adresse zurückgesetzt. Wenn A weiterläuft und ein CAS auf X durchführt, sieht es denselben Wert wie zuvor — und akzeptiert die Operation, obwohl der Inhalt sich fundamental geändert hat.

Lösungen:

• Tagged Pointers: 16 Bit Versionszähler im Pointer. Funktioniert gut auf x86_64, aber nicht portabel.
• Hazard Pointers (Maged Michael): jeder Thread veröffentlicht die Pointer, die er gerade liest. Speicher wird erst freigegeben, wenn kein Hazard Pointer mehr auf ihn zeigt. Korrekt, aber implementierungstechnisch komplex.
• Epoch-basiertes Reclamation: Threads kündigen ihre Anwesenheit in „Epochen" an; Freigabe geschieht zwei Epochen später. Effizient, gut für Read-Heavy-Workloads.

Performance-Realismus.

In Benchmarks erreichen gute SPSC-Ringbuffer 100–200 Millionen Operationen pro Sekunde pro Core. MPSC-Queues liegen typischerweise bei 30–80 Millionen, MPMC bei 5–20 Millionen. Mit dem Wechsel von std::mutex auf einen Spinlock gewinnt man oft das 5- bis 10-fache; der Sprung auf eine echte lock-freie Variante bringt noch einmal das 2- bis 5-fache, abhängig von der Zahl der Kerne und der Contention.

Wichtig: Die Zahlen gelten in Mikrobenchmarks. In einem realen Trading-System dominieren oft andere Faktoren — Netzwerkstack, Kernel-Latenz, Cache-Effekte aus dem umgebenden Code. Lock-freier Code lohnt sich primär, wenn Sie diese Faktoren bereits adressiert haben.

Fallstricke aus der Praxis.

Was in produktivem Code schiefgeht:

• Falsch dimensionierte Ringbuffer — zu klein, und der Producer blockiert; zu groß, und die L1/L2-Caches werden vergiftet.
• Vergessenes Padding für False Sharing. Findet man oft erst, wenn man perf c2c ausführt und auf einmal viele HITM-Events sieht.
• Falsche Annahmen über das Memory-Modell, die auf x86 funktionieren, aber auf ARM (Apple Silicon, Graviton) krachen. Tests müssen mindestens auf einer schwach geordneten Architektur laufen.
• Lock-freie Strukturen, die intern dynamisch allokieren. Das negiert den ganzen Sinn — Allokation ist nicht lock-frei.

Wann es sich wirklich lohnt.

Lock-freier Code ist Investition in Komplexität. Er lohnt sich, wenn: (1) Ihre Strategie tatsächlich im Mikrosekunden-Regime spielt, (2) Sie genug Cores haben, dass Parallelismus relevant ist, und (3) Sie das Personal haben, das den Code korrekt schreibt und reviewt. Für drei der vier Strategien, die ich in den letzten zwei Jahren gebaut habe, war ein gut geschriebener Spinlock völlig ausreichend.

Sie sind unsicher, ob lock-freie Strukturen Ihren Stack wirklich schneller machen? Erstgespräch buchen — wir messen den Status quo und entscheiden datenbasiert.