This story was originally published on HackerNoon at: https://hackernoon.com/why-skip-lists-are-the-wrong-default-for-matchmaking-queues-a-fenwick-tree-case-study.
Why a Fenwick tree beats a skip-list sorted set for matchmaking queues: ~35x faster queries, 3x less memory, reproducible Go benchmarks, and the caveats.
Check more stories related to gaming at: https://hackernoon.com/c/gaming.
You can also check exclusive content about #game-development, #fenwick-tree, #skip-lists, #matchmacking-algorithm, #game-server-architecture, #online-game-matchmaking, #game-matchmaking-algorithm, #hackernoon-top-story, and more.
This story was written by: @ivan-fekete. Learn more about this writer by checking @ivan-fekete's about page,
and for more stories, please visit hackernoon.com.
Matchmaking queues need three things from their core data structure: range-count queries as the skill window widens, global rank lookups for leaderboards, and constant add/remove updates. The usual default is a skip-list-backed sorted set, the kind Redis ships and OpenMatch used, but benchmarked on the same host, it runs about 35x slower on rank queries and 38x slower on range counts than a Fenwick tree, and uses roughly 3x the memory. The cause is cache locality: a Fenwick tree is a single ~40 KB array that stays L2-resident, while a skip list chases pointers across scattered heap nodes. When MMR is bounded and quantizes naturally, a Fenwick tree with per-bucket player lists is the better default, and the article includes the Go code, reproducible numbers, and the cases where a skip list still wins.
