The Tale of Taming TigerBeetle's Tail Latency by Tobias Ziegler

Learn how we reduced TigerBeetle’s tail latency through algorithm engineering. ‘Algorithm engineering goes beyond studying theoretical complexity and considers how algorithms are executed efficiently on modern super-scalar CPUs. Specifically, we will look at Radix Sort and a k-way merge and explore how to implement them efficiently. We then demonstrate how we apply these algorithms incrementally to avoid latency spikes in practices.

1. A ScyllaDB Community
The Tale of Taming
TigerBeetle’s Tail
Tobias Ziegler
Software Engineer

2. Narrator: Tobias Ziegler (he/him)

■PhD in (Distributed) OLTP Databases
■I love performance engineering
■Sports fanatic & coffee enthusiast
Software Engineer at TigerBeetle

3. The Villain: TigerBeetle’s Tail

4. The Villain: TigerBeetle’s Tail

Throughput: 404k tx/s
Batch Latency:
■p50 = 13 ms
■p99 = 103 ms
■p100 = 104 ms

5. The Protagonist: TigerBeetle
High-Performance Financial Transactions Database (OLTP)
■Debit/Credit primitive instead of SQL (Oasis)
■Reliable, fast, highly available
■Replicated + persistent storage for fault tolerance

Are We I/O Bound?

6. I/O Is the Bottleneck of the Past
Network Bandwidth SSD Bandwidth

7. CPU Is the New Bottleneck
TODO: Nicer Figure

8. The Protagonist: TigerBeetle
Single-Core by Design
■Optimized for Updates & Writes
■Power-Law Workloads: Contention Cannot Be Parallelized
“Design is the beauty of turning
constraints into advantages”

9. So, let us change this!
What happens here?

10. (Simplified) Processing Model
TXN Batch
Processing
mutable table

11. Algorithm Selection & Design

12. K-Way Merge: Naive
Merge k sorted runs into one sorted sequence.

Naïve approach:

■Scan all k runs to find the minimum element.

■Repeat until all n elements are merged.

Time complexity: O(n · k)

R
u
n
R
u
n
R
u
n
R
u
n

13. Merge k sorted runs into one sorted sequence.

Tree-Based approaches:

■Select min-element in log(k).

■Repeat until all n elements are merged.

Time complexity: O(n · log(k))

K-Way Merge: Tree-Based
R
u
n
R
u
n
R
u
n
R
u
n

14. Tree of Losers


1
5
…
2
3
…
4
7
…
3
8
…
Initializing:

15. Tree of Losers

5
…

3
…
4
7
…
3
8
…
2 4
3
Previous
winner: 1
Only one path competes → 1 comparison per
level (vs. 2 in a min-heap). Asymptotically
optimal.

16. Did We Tame The Tail?
Not Really!
Throughput: 398k tx/s
Batch Latency:
■p50 = 13 ms
■p99 = 101 ms
■max = 102 ms

17. Algorithm Engineering
bridges theory and practice

18. Map our abstract algorithm onto actual hardware.

19. ■Modern CPUs are quite complex:
●Pipelined, Super Scalar, Out Of Order, Speculative Execution
Need simple mental model to map our Algorithm to CPU.
■Everyone has a mental model, but how accurate is it?
■To find this out we need two things
●Representative Benchmark (different Key and Value Sizes, …)
●Tooling (Perf, Polar Signals, VTune …)
Methodology & Tooling

20. CPU Counters
CPUs have lots of performance counters:
■Instructions: machine instructions executed (“retired”)
■Cache/ TLB hits/misses: for different caches
■Branch hits/misses: (in)correctly predicted branches
■…

21. CPU Counters with perf stat
> perf stat ./loser_tree

Ok, so what?

22. CPU Counters with PerfEvent
■Library that can measure some part of your code
■Normalizes the CPU counters
■This allows you to reason about the algorithm/data structure

> ./loser_tree

23. Let’s Talk Performance
This is the naive Tree of Losers that we implemented.
TODO perf counters

24. Optimizing for Cache Misses: Eytzinger Layout
Rule #1: Data must be ready for the CPU to enable instruction-level parallelism!


TODO perf counters

25. Optimizing for TLB Misses: Huge Pages
TLB Misses cost in the order of ~50+ CPU cycles
TODO perf counters

26. Avoid Branch Mispredictions: Go Branchless
Branch Mispredictions cost around 15-20 cycles.
TODO perf counters

27. Reduce Instructions: Unrolling and Co.
Make every instruction count!
TODO perf counters

28. Ablation Study and Final Result
TODO perf counters

29. Incremental
TODO perf counters

30. At Last We Tamed the Tail.

32. Thank you! Let’s connect.
Tobias Ziegler
[email protected]
@Tobias__Ziegler
github.com/toziegler