Matchmaking queue

Deep dive

How it works

Parts:

• Ticket — members, rating, RD, RTT per region, enqueue time.
• Bucket index — per mode, ordered map keyed by (rating, id).
• Window function — w(t) for rating and RTT, widening with wait, capped.
• Matcher — each tick, oldest first, mutual-window candidates, smallest gap.
• Ready check — confirm, penalize no-shows, requeue with original time.

1. Ticket: {id, members, rating, rd, rtt_ms[region], enqueued_at, mode}. For Glicko-2 or TrueSkill, use μ for pairing and let σ/RD widen the window: a new player's true rating can be hundreds of points from μ.
2. Bucket by mode (and hard constraints such as platform or input device). Inside a bucket, index tickets by rating (ordered map keyed by (rating, id)).
3. Window: w(t) = min(base + k_rd·RD + rate·wait, max). Typical shape: start at 50-100 Elo, widen tens of points per second, cap at a few hundred. Optionally a hard ceiling after which the player is told the queue is empty instead of getting an absurd match.
4. Region: each client pings every region beacon at enqueue. A region is acceptable if RTT ≤ rtt_base + rtt_rate·wait (capped). The best region is always acceptable. Pick the shared region that minimizes the worse of the two RTTs.
5. Tick: process tickets oldest first; each scans its rating window, keeps candidates that accept it back and share a region, and takes the smallest rating gap (ties: the older partner). Remove both, emit a match.
6. Confirm: send a ready check (about 10-20 s). Anyone who declines or times out is penalized; everyone who accepted goes back into the queue with their original enqueue time.

max gap
   ^             ________________ cap
   |            /
   |          /   widen: base + RD term + rate * wait
   |        /
   | ______/  base
   +-------------------------------> wait time

Parties and teams. A party is one ticket with several members. Team rating = mean of members is easy to exploit (a high-rated player with low-rated friends gets easy opponents); weight it toward the strongest member (max, or a mean of the top members) or add a premade bonus. For NvN, build teams from tickets whose sizes sum to N (a small bin-packing problem per candidate set), then split them into two teams minimizing the difference of team ratings; prefer matching premade groups against premade groups. Large parties shrink the candidate set, so their windows widen faster.

Fairness vs wait. Suppose tickets arrive at λ per second and a fraction f(r) per rating point sits near rating r. A window ±w then catches new partners at about 2·w·λ·f(r) per second, and expected wait scales as 1/(w·λ·f). With normally distributed ratings, the top 0.1% sit where f is about 100× smaller than at the median, so the same rules give them 100× longer waits. Tune rate and cap per rating band, or batch them across regions. Track per band: median and p95 wait, mean rating gap, favourite's realized win rate.

Code

One mode, 1v1, in-memory. Ordered index for the rating band scan, mutual windows that widen with wait, region masks that relax with wait, oldest-first greedy pairing.

// 1v1 matchmaking queue for one mode: rating index, windows that widen with wait time,
// region filter that relaxes with wait time, oldest-first greedy pairing per tick.
use std::collections::{BTreeMap, HashMap};

pub const REGIONS: usize = 4;

#[derive(Clone, Debug)]
pub struct Ticket { pub id: u64, pub rating: i32, pub rd: i32, pub enqueued_ms: u64, pub rtt_ms: [u16; REGIONS] }

pub struct Params {
    pub base: i32, pub per_sec: i32, pub max_window: i32, // rating window = base + rd/2 + per_sec * wait, capped
    pub rtt_base: u16, pub rtt_per_sec: u16, pub rtt_max: u16,
}

#[derive(Debug, PartialEq)]
pub struct Match { pub a: u64, pub b: u64, pub region: usize }

pub struct Queue { p: Params, index: BTreeMap<(i32, u64), ()>, tickets: HashMap<u64, Ticket> }

impl Queue {
    pub fn new(p: Params) -> Self { Queue { p, index: BTreeMap::new(), tickets: HashMap::new() } }
    pub fn push(&mut self, t: Ticket) { self.index.insert((t.rating, t.id), ()); self.tickets.insert(t.id, t); }
    pub fn cancel(&mut self, id: u64) -> Option<Ticket> {
        let t = self.tickets.remove(&id)?;
        self.index.remove(&(t.rating, id));
        Some(t)
    }
    fn wait_s(t: &Ticket, now: u64) -> i32 { (now.saturating_sub(t.enqueued_ms) / 1000) as i32 }
    fn window(&self, t: &Ticket, now: u64) -> i32 {
        (self.p.base + t.rd / 2 + self.p.per_sec * Self::wait_s(t, now)).min(self.p.max_window)
    }
    /// Regions this ticket accepts now: RTT under a limit that grows with wait; the best region always counts.
    fn regions(&self, t: &Ticket, now: u64) -> u32 {
        let lim = (self.p.rtt_base as i32 + self.p.rtt_per_sec as i32 * Self::wait_s(t, now)).min(self.p.rtt_max as i32);
        let best = (0..REGIONS).min_by_key(|&r| t.rtt_ms[r]).unwrap();
        (0..REGIONS).filter(|&r| r == best || t.rtt_ms[r] as i32 <= lim).fold(0, |m, r| m | 1 << r)
    }

    /// One matchmaking pass. Oldest ticket picks first: the longest waiters get the best partners.
    pub fn tick(&mut self, now: u64) -> Vec<Match> {
        let mut order: Vec<(u64, u64)> = self.tickets.values().map(|t| (t.enqueued_ms, t.id)).collect();
        order.sort_unstable();
        let mut out = Vec::new();
        for (_, id) in order {
            let Some(t) = self.tickets.get(&id) else { continue }; // already matched this tick
            let (w, regs) = (self.window(t, now), self.regions(t, now));
            let mut best: Option<(i32, u64, u64)> = None; // (rating gap, partner enqueue time, partner id)
            for (&(r, cid), _) in self.index.range((t.rating - w, 0)..=(t.rating + w, u64::MAX)) {
                if cid == id { continue; }
                let c = &self.tickets[&cid];
                let gap = (r - t.rating).abs();
                if gap > self.window(c, now) || regs & self.regions(c, now) == 0 { continue; } // must be mutual
                if best.map_or(true, |b| (gap, c.enqueued_ms) < (b.0, b.1)) { best = Some((gap, c.enqueued_ms, cid)); }
            }
            if let Some((_, _, cid)) = best {
                let (a, b) = (self.cancel(id).unwrap(), self.cancel(cid).unwrap());
                let shared = self.regions(&a, now) & self.regions(&b, now);
                let region = (0..REGIONS).filter(|r| shared & 1 << r != 0)
                    .min_by_key(|&r| a.rtt_ms[r].max(b.rtt_ms[r])).unwrap(); // minimize the worse RTT
                out.push(Match { a: a.id, b: b.id, region });
            }
        }
        out
    }
}

fn main() {
    let p = Params { base: 50, per_sec: 10, max_window: 400, rtt_base: 60, rtt_per_sec: 5, rtt_max: 150 };
    let mut q = Queue::new(p);
    let eu = [20, 90, 160, 250];
    let us = [95, 25, 80, 200];
    q.push(Ticket { id: 1, rating: 1500, rd: 50, enqueued_ms: 0, rtt_ms: eu });
    q.push(Ticket { id: 2, rating: 1700, rd: 50, enqueued_ms: 0, rtt_ms: eu });
    q.push(Ticket { id: 3, rating: 1540, rd: 50, enqueued_ms: 1000, rtt_ms: us });
    // t = 1 s: 1 and 3 are 40 apart but share no region yet (EU-only vs US-only); 1 and 2 are 200 apart.
    assert!(q.tick(1_000).is_empty());
    // t = 8 s: RTT limits near 100 ms let both accept regions 0 and 1; windows cover 40, not 200.
    assert_eq!(q.tick(8_000), vec![Match { a: 1, b: 3, region: 1 }]);
    // Player 2 waits alone; its window keeps growing until someone arrives.
    q.push(Ticket { id: 4, rating: 1950, rd: 50, enqueued_ms: 20_000, rtt_ms: eu });
    assert!(q.tick(20_000).is_empty()); // gap 250 > window of the new ticket (75)
    assert_eq!(q.tick(38_000).len(), 1); // new ticket's window reached 75 + 180 = 255
    println!("ok");
}

Complexity and constants

• Enqueue and cancel: O(log n) in the ordered index plus O(1) hash map.
• Greedy tick: O(n log n) to order tickets by age plus the candidates scanned per window. In a dense bucket a ±200 window can hold thousands of tickets: cap the scan at the nearest K by rating (walk outward from the ticket's own rating) or split the bucket into rating shards.
• Optimal batch pairing (1v1): build a graph with edge cost = rating gap + latency penalty − wait bonus, solve minimum-cost perfect matching with Edmonds' blossom algorithm, O(n³). Practical up to a few thousand tickets per tick per bucket.
• Tick cadence: 1-5 s. Shorter ticks give faster first matches; longer ticks give the optimizer more tickets to choose from.

Efficiency

Cost: a greedy tick is O(n log n) plus candidates scanned. Blossom batch matching is O(n³): practical up to a few thousand tickets per tick per bucket.

Levers:

• Scan only the K nearest ratings, walking outward — avoids thousands of candidates — dense rating bands.
• Wider windows per rating band — the top 0.1% would wait about 100× longer with uniform rules — rating tails.

Naive → standard → state of the art:

• First-come pairing with a fixed window · fast, unfair at the tails
• Oldest-first greedy with mutual, widening windows · O(n log n + scan) per tick
• Batch minimum-cost matching with latency and wait terms · O(n³) per bucket

Implementation notes

• Rating windows in integer rating points, times in monotonic milliseconds from the matchmaker's clock, never client time.
• Region pings: measure on enqueue, refresh on long waits; reject obviously spoofed values (RTT below physical minimums) and cap what a client can claim.
• Shard by mode × region group, one single-threaded matchmaker per shard; a ticket lives in exactly one shard. Use a lease or leader election so two instances never match the same ticket.
• Keep ticket state in memory with a durable copy only for recovery; on a matchmaker restart, clients re-enqueue with their original enqueue time.
• Expire tickets whose client stopped heart-beating (e.g. 2-3 missed heartbeats): ghosts produce failed ready checks and punish real players.
• After a match is confirmed, hand off to server allocation (pick or spin up a game server in the chosen region) asynchronously; the matchmaker must not block on it.

Pitfalls

• One-sided windows: the long-waiting ticket accepts anyone, the new ticket gets a lopsided match it would never have accepted.
• Unbounded widening: a top player gets matched against a beginner after five minutes. Cap the gap and let the queue fail honestly.
• Re-queue after a failed ready check with a fresh timestamp: the innocent players lose their wait.
• Pairing only within the cheapest region: players near region borders wait forever while a neighbouring region has opponents.
• Dodging: players cancel when they see the opponent. Hide identities until the game starts or penalize repeated cancels.
• Smurfs and new accounts with default ratings: high RD should widen the window and let ratings converge fast, not place them at the median.
• Rating-based queues for tiny populations: the same few players meet repeatedly; add a recent-opponent penalty.

Variants and alternatives

In production

• Games: AWS GameLift FlexMatch, PlayFab Matchmaking, Nakama's matchmaker, Open Match (Google and Unity); Lichess pools pair waiting players in waves every few seconds using weighted maximum matching.
• Mobility: Lyft Line put each request into a matching pool for 1 minute before assigning a driver.
• Healthcare: pairwise kidney exchange matches incompatible patient-donor pairs with each other as a matching problem (Roth, Sönmez, Ünver 2005).

Implementations

Sources

• Arpad Elo, The Rating of Chessplayers, Past and Present, 1978.
• Mark Glickman, Example of the Glicko-2 system (technical note, glicko.net). pdf
• Herbrich, Minka, Graepel, TrueSkill: A Bayesian Skill Rating System, NIPS 2006. paper
• Jack Edmonds, Paths, Trees, and Flowers, Canadian Journal of Mathematics, 1965. paper
• Chen et al., EOMM: An Engagement Optimized Matchmaking Framework, WWW 2017.
• AWS, Amazon GameLift FlexMatch Developer Guide. docs
• Open Match documentation, open-match.dev. docs
• Roth, Sönmez, Ünver, Pairwise kidney exchange, Journal of Economic Theory, 2005. paper
• Lyft Engineering, Matchmaking in Lyft Line, Part 1. post