Fenwick Trees Make a Practical Case Against Skip Lists in Game Matchmaking Queues

Ivan Fekete’s HackerNoon case study, Why Skip Lists Are the Wrong Default for Matchmaking Queues, is not a funding announcement. No funding amount, investor list, or company round was disclosed. The traction signal is technical instead: a benchmark-backed argument that production matchmaking systems may be paying too much latency and memory cost by reaching first for skip lists, especially Redis-style sorted sets.

The problem sits underneath a familiar multiplayer game workflow. A matchmaker receives player tickets, separates them by hard constraints such as region and game mode, then tries to form groups among players with similar skill. That skill score is often treated as MMR, whether it comes from Elo, Glicko-2, TrueSkill, or a custom rating model.

The less discussed question is what happens after every queued player already has a score. The service still needs to answer operational queries constantly: how many players sit within an acceptable MMR range, what is a player’s global rank, and how quickly can the queue absorb adds and removes as players join, disconnect, retry, or cancel. Fekete models a mature shard as needing roughly 50,000 range-count queries per second and 5,000 global-rank queries per second, plus frequent updates.

The default answer in many systems is a sorted set backed by a skip list. Redis exposes this pattern through commands such as ZRANGEBYSCORE, and the approach is attractive because it is already available, ordered, and flexible. Open Match, Google’s open source matchmaking framework, has also helped normalize sorted-set thinking in this part of the stack. The appeal is clear: skip lists give logarithmic operations and avoid writing custom indexing code.

Fekete’s benchmark challenges that default. The alternative is a Fenwick tree, also called a binary indexed tree, a compact data structure designed for cumulative frequency tables. The core idea is simple: bucket MMR into integer slots, store counts per bucket, and answer range sums by combining partial prefix sums. If MMR runs from 0 to 5,000, then the tree size is tied to 5,001 buckets, not to the number of players. That distinction drives most of the performance result.

A pure Fenwick tree is not enough for a full matchmaker because it stores counts, not player IDs. It can tell the system that 64 players exist between 1,450 and 1,550 MMR, but not which players they are. The hybrid version solves that by pairing the Fenwick tree with per-bucket player lists and a player-to-position map. Adds append the player ID to the right bucket and update the tree. Removes use swap-and-pop inside the bucket and update the moved player’s position. Range counts and rank queries still touch only the compact tree.

That design changes the operating profile. A skip list follows pointers through heap-allocated nodes. Even when the algorithmic complexity looks good, each pointer chase can miss cache and add latency. A Fenwick tree works mostly over a small flat array. The benchmark’s most important lesson is not that Big O is wrong, but that Big O hides memory locality, allocator behavior, and tail latency.

At 100,000 players, the reported median isolated-operation numbers are stark. Fenwick rank queries came in around 17 ns, hybrid around 17 ns, sorted array around 181 ns, and skip list around 624 ns. Range-count queries showed a similar spread: Fenwick around 31 ns, hybrid around 32 ns, sorted array around 355 ns, and skip list around 1,190 ns. Updates were the sorted array’s failure point because inserts and deletes require shifting memory, while skip list updates were far slower than the Fenwick-family options.

The scaling result is the more commercially relevant part. When population rises from 100,000 to 1 million players, Fenwick and hybrid rank-query time stays essentially flat because the bucket count does not change. The skip list slows as the structure grows and its cache behavior worsens. For live games, that matters because matchmaking demand is bursty. A queue index that behaves predictably at larger shard sizes can reduce overprovisioning and leave more headroom for other work such as party logic, fraud checks, rating updates, and telemetry.

Memory tells the same story. Fekete reports roughly 28 bytes per player for Fenwick, 41 bytes for the hybrid structure, 44 bytes for a sorted array, and 97 bytes for a skip list at 100,000 players. Projected to 20 million players, that implies about 560 MB for Fenwick, 860 MB for hybrid, and 1.94 GB for skip list. Those are not abstract numbers for a game backend team. They affect host density, cache pressure, failover cost, and how many shards can fit into a given fleet shape.

The market positioning here is not a startup pitch, but it does map cleanly to an infrastructure opportunity. Matchmaking sits inside a broader market for real-time multiplayer backends, including managed game services, custom game server orchestration, and internal platform teams at studios. Companies in that market usually sell reliability, scale, and developer speed. This case study points to a narrower claim: there may be performance left on the table in the queue-index layer, especially for games that use bounded, quantized skill ratings.

The skeptical part matters. Fenwick trees are not a universal replacement for skip lists. If ratings are continuous and cannot be quantized without losing meaningful precision, a skip list, balanced tree, kd-tree, or multidimensional structure may be a better fit. If the queue is tiny, the speed difference may not justify extra implementation work. If the system needs exact global ranking across many hosts, federation becomes a separate hard problem. A per-shard Fenwick can answer local counts cheaply, but global rank requires aggregation logic and consistency decisions.

There is also product nuance. Many modern matchmakers do not rely on one scalar skill score. They may account for uncertainty, party size, latency, role preference, behavior score, input method, device class, or monetization-neutral cohorting rules. A one-dimensional Fenwick index is excellent when the main query is “how many candidates exist between these two MMR values?” It is less complete when the actual match function is multidimensional and policy-heavy. Fekete suggests deriving a conservative one-dimensional estimate, such as μ minus a multiple of σ for TrueSkill-style systems, but that trades expressiveness for speed.

For engineering teams, the practical takeaway is to benchmark the query shape, not just the data structure name. A sorted set is convenient and may be correct for early stages. Once the service has high query volume, bounded integer ratings, and frequent range expansion, a Fenwick-plus-buckets design becomes a serious candidate. It offers exact counts, fast rank queries, lower memory use, and tighter p99 behavior, while preserving player enumeration through bucket lists.

The study also fits a larger pattern in infrastructure software: specialized structures often beat general-purpose defaults once the workload becomes clear. Redis sorted sets remain valuable because they are easy to operate and broadly useful. But matchmaking is not a generic sorted-set problem when MMR is bounded, bucketable, and queried mostly through ranges. In that narrower domain, a compact cumulative-frequency structure can turn a common backend bottleneck into a predictable array operation.

For readers who want the underlying theory, Peter Fenwick’s original paper, “A New Data Structure for Cumulative Frequency Tables,” is the starting point, while William Pugh’s skip list paper explains the probabilistic structure behind the sorted-set alternative. For applied matchmaking context, Riot’s Matchmaking Explained posts and Microsoft’s TrueSkill 2 paper are useful companions.

No investors are backing this as a disclosed venture, and no funding amount is attached. The traction is the benchmark itself: a concrete, reproducible claim aimed at teams building high-throughput multiplayer systems. That makes the story less about startup capital and more about infrastructure judgment. The opportunity is not hype. It is a reminder that mature systems often get faster when engineers stop treating defaults as neutral.