Building a Fast Lock-free Queue for Trading Systems by Sarthak Sehgal

When every microsecond counts, inter-thread communication must be lean and predictable. This talk dives into the design of a high-performance SPSC bounded queue for ultra-low latency trading systems. We’ll cover eliminating locks with atomics, reducing sync costs with memory ordering, and avoiding traps like false sharing, all backed by real-world measurements and cache analysis. Attendees will gain practical strategies for writing lock-free data structures that deliver under pressure.

1. A ScyllaDB Community
Building a Fast Lock-free
Queue for Trading Systems
Sarthak Sehgal
Tech Lead

2. Sarthak Sehgal he/him

Tech Lead at Maven Securities
■Working at a high frequency options market making firm
■Interested in finance, low level programming, and C++
under the hood
■Sometimes, I write about C++ at sartech.substack.com

3. Overview
■Motivation & Problem Setup
■Building an SPSC queue using std::atomic
■Optimizations
●Memory Ordering
●Cache alignment
●Variable caching

4. Motivation

5. Motivation
■On Nasdaq:
●1 million msgs/s
●Peaks at 3-4 million msgs/s at open/close
Exchange

6. Source: Stefan Schlamp LinkedIn

7. Problem Setup

8. Problem Setup
■One producer and one consumer
■Both threads are pinned on separate physical cores
■Fixed size buffer (bounded queue)

9. Queue using std::atomic

10. Producer

14. Consumer

15. Instruction Execution Order in CPU

16. Out-of-order execution

17. Out-of-order execution

18. Out-of-order execution
Out of order atomic update and memory access leads to incorrect behavior

19. Aspects of std::atomic
1.Atomicity - operations on the atomic object are indivisible

20. Aspects of std::atomic
1.Atomicity - operations on the atomic object are indivisible
2.Memory Ordering - determines how memory access (atomic and non-atomic)
surrounding an atomic operation are sequenced. This is used for memory
access synchronization across threads.

21. Aspects of std::atomic
1.Atomicity - operations on the atomic object are indivisible
2.Memory Ordering - determines how memory access (atomic and non-atomic)
surrounding an atomic operation are sequenced. This is used for memory
access synchronization across threads.
Fortunately, the default load and store operations ensure that reordering does not occur. This behavior is
governed by memory ordering. As we will uncover, memory ordering has a significant impact on the
performance.

22. Memory ordering in atomic

23. std::memory_order_relaxed
■No ordering constraints for reads or writes around the atomic variable
■Only ensures atomicity

24. Optimization: Using relaxed ordering

25. std::memory_order_acquire / release

26. std::memory_order_acquire / release

27. std::memory_order_acquire / release

28. Optimization: Using memory ordering

29. False Sharing

30. False Sharing
■False sharing occurs when two or more threads access different variables
that are located on the same cache line

31. Results

32. Checkout my slides and blog for the complete code

33. Resources
■Fedor Pikus’ introductory talk on std::atomic and memory ordering
■Source code of boost spsc lockfree queue
■Herb Sutter’s atomic weapons talk

34. Thank you! Let’s connect.
Sarthak Sehgal
[email protected]
linkedin/sarthaksehgal99
sartech.substack.com