Why Skip Lists Are the Wrong Default for Matchmaking Queues: A Fenwick Tree Case Study

Published on HackerNoon. Read the full article.

Matchmaking systems keep asking the same three questions of their player pool: how many players sit within a rating range, what is a given player’s global rank, and how do we add and remove players fast enough to keep up with roughly 50,000 queries per second. Many teams reach for a skip list (Redis’s sorted set is the common example) without measuring the alternatives.

I benchmarked sorted arrays, skip lists, pure Fenwick trees, and a hybrid of a Fenwick tree with per-bucket player lists. At 100K players:

• Rank queries: about 17 ns for the Fenwick tree against 624 ns for the skip list, roughly 35x faster.
• Range counts: 31 ns against 1,190 ns, roughly 38x faster.
• Memory: 28 bytes per player against 97, about 3x less.
• Scaling to 1M players: skip list latency degraded 2.21x while the Fenwick tree stayed flat.

The article also covers median versus p99 latency, a trade-off table for choosing a structure, and when not to use this approach.