Message sequence numbers

Deep dive

How it works

In: messages of one stream, each with (epoch, seq), and acks or NACKs from the receiver · Out: messages delivered once, in order, without gaps, or a resync request · State: sender (epoch, next) plus a retransmit buffer; receiver (epoch, next_expected) plus a bounded reorder buffer · Cost: O(1) per in-order message, O(log k) per out-of-order one, 4-8 bytes per message or batch

Sender keeps (epoch, next) and a retransmit buffer of unacked messages. Receiver keeps (epoch, next_expected) and a bounded reorder buffer.

1. Send: stamp (epoch, next++), keep a copy until acked. If the buffer is full, stop (backpressure).
2. Receive seq in the current epoch:
   • seq < next_expected or already buffered: duplicate, drop.
   • seq == next_expected: deliver, then drain consecutive buffered successors.
   • seq > next_expected: buffer it and NACK [next_expected, first buffered).
3. Ack: periodically send next_expected (cumulative). The sender frees everything below it.
4. Retransmit on NACK or ack timeout. If the requested range was already trimmed, the receiver needs a snapshot plus the sequence it reflects.
5. Epochs: a sender that restarts without its counter takes a higher epoch and restarts at 0. The receiver resets on a higher epoch and drops anything from a lower one.
6. Reconnect: the client sends (stream, epoch, next_expected); the server replays from its buffer or falls back to a snapshot.

sender:   0  1  2  3  4
wire:     0  .  2  3  2(dup)
receiver: deliver 0 | buffer 2 → NACK [1,2) | buffer 3 | dup | 1 arrives → deliver 1,2,3
ack:      next_expected = 4  → sender drops 0..3 from its buffer

Code

32-bit sequences on the wire, 64-bit inside: extend picks the 64-bit value closest to the expected one (the QUIC packet-number decoding trick), so internal comparisons never wrap.

use std::collections::{BTreeMap, VecDeque};

/// Expand a 32-bit wire sequence to the 64-bit value closest to `expected`.
pub fn extend(wire: u32, expected: u64) -> u64 {
    const WIN: u64 = 1 << 32;
    const HALF: u64 = 1 << 31;
    let cand = (expected & !(WIN - 1)) | wire as u64;
    if cand + HALF <= expected { cand + WIN }
    else if cand > expected + HALF && cand >= WIN { cand - WIN }
    else { cand }
}

pub struct Sender<T: Clone> { epoch: u32, next: u64, unacked: VecDeque<T>, cap: usize }

impl<T: Clone> Sender<T> {
    /// `epoch` must exceed every epoch this stream used before (persist it).
    pub fn new(epoch: u32, cap: usize) -> Self { Sender { epoch, next: 0, unacked: VecDeque::new(), cap } }
    /// Stamp and keep a copy until acked; Err = window full, apply backpressure.
    pub fn send(&mut self, msg: T) -> Result<(u32, u32, T), T> {
        if self.unacked.len() == self.cap { return Err(msg); }
        let seq = self.next;
        self.next += 1;
        self.unacked.push_back(msg.clone());
        Ok((self.epoch, seq as u32, msg))
    }
    fn base(&self) -> u64 { self.next - self.unacked.len() as u64 }
    /// Cumulative ack: receiver has everything < `upto`.
    pub fn ack(&mut self, upto: u64) {
        let n = upto.saturating_sub(self.base()).min(self.unacked.len() as u64);
        self.unacked.drain(..n as usize);
    }
    /// Resend [from, to). Buffer is contiguous, so lookup is index arithmetic.
    /// None = already trimmed: the receiver needs a snapshot instead.
    pub fn resend(&self, from: u64, to: u64) -> Option<Vec<(u32, u32, T)>> {
        if from < self.base() { return None; }
        let to = to.min(self.next);
        Some((from..to).map(|s| (self.epoch, s as u32, self.unacked[(s - self.base()) as usize].clone())).collect())
    }
}

#[derive(Debug, PartialEq)]
pub enum Recv<T> {
    Deliver(Vec<T>),            // in order, plus any buffered successors
    Duplicate,                  // already delivered or already buffered
    Stale,                      // older epoch: zombie sender
    Gap { from: u64, to: u64 }, // buffered; request [from, to)
    Resync { from: u64 },       // reorder buffer full: snapshot/replay from `from`
}

pub struct Receiver<T> { epoch: u32, next: u64, pending: BTreeMap<u64, T>, max_pending: usize }

impl<T> Receiver<T> {
    pub fn new(max_pending: usize) -> Self { Receiver { epoch: 0, next: 0, pending: BTreeMap::new(), max_pending } }
    pub fn next_expected(&self) -> u64 { self.next } // the cumulative ack and resume cursor
    pub fn on_message(&mut self, epoch: u32, wire: u32, msg: T) -> Recv<T> {
        if epoch < self.epoch { return Recv::Stale; }
        if epoch > self.epoch { self.epoch = epoch; self.next = 0; self.pending.clear(); }
        let seq = extend(wire, self.next);
        if seq < self.next || self.pending.contains_key(&seq) { return Recv::Duplicate; }
        if seq > self.next {
            if self.pending.len() >= self.max_pending { return Recv::Resync { from: self.next }; }
            self.pending.insert(seq, msg);
            let to = *self.pending.keys().next().unwrap(); // first message we do have
            return Recv::Gap { from: self.next, to };
        }
        let mut out = vec![msg];
        self.next += 1;
        while let Some(m) = self.pending.remove(&self.next) { out.push(m); self.next += 1; }
        Recv::Deliver(out)
    }
}

Complexity and constants

• In-order message: one compare, one increment; no allocation if the delivery Vec is reused.
• Out-of-order: O(log k) BTreeMap insert, each node a likely cache miss. For dense windows a ring of slots indexed by seq % window plus a bitmap is O(1) and cache-friendly.
• Wire cost: 4 bytes of sequence (8 if you never want to think about wrap). Put the epoch in the handshake, not every message. Batch headers carry base_seq + count (Kafka record batches, MoldUDP64), so the cost is per batch.
• Ack traffic: cumulative acks every N messages or T ms, e.g. one ack per 64 messages or 10 ms, whichever comes first. Acks are idempotent, so losing one costs nothing.
• Sender memory: window × average message size; it bounds how far a slow receiver can fall behind before it needs a snapshot.

Efficiency

• Cost: the in-order path is one compare and one increment, no allocation when the delivery Vec is reused. Out-of-order arrival is an O(log k) BTreeMap insert, likely a cache miss per node. Wire cost is 4 bytes per message, or one base_seq + count header per batch; the epoch goes in the handshake. Sender memory is window × average message size. Bound: network (acks, retransmits) and, on the receiver, cache misses.
• Levers:
  • batch headers (base_seq + count) — header cost per batch, not per message (Kafka record batches, MoldUDP64) — high message rates
  • cumulative acks, one per 64 messages or 10 ms (order of) — fewer packets, and a lost ack costs nothing — all links
  • ring of slots indexed by seq % window plus a bitmap — O(1) and cache-friendly instead of BTreeMap pointer chasing — dense reorder windows
  • sender copies kept as serialized bytes — a resend is one writev of a contiguous slice — retransmit-heavy links
  • NACK after a short reorder delay — avoids spurious retransmits (TCP waits for 3 duplicate ACKs) — reordering networks
• Naive → standard → state of the art:
  • per-message ack and per-message retransmit timer · one ack packet per message
  • cumulative acks, NACK on gap, BTreeMap reorder buffer · O(1) in order, O(log k) out of order
  • batch sequence headers, slot-ring reorder buffer, selective ack ranges · O(1) per message, header cost per batch

Implementation notes

• One writer per stream assigns sequences right before the bytes hit the socket or the log. An AtomicU64::fetch_add shared by several threads gives numbers whose order differs from send order.
• Keep sequences per stream (per connection, per partition, per game). A global counter becomes a contention point, and it makes every receiver see gaps that belong to other streams.
• Persist only the epoch (one fsync per restart), not the counter. Alternatively use a fencing token or lease epoch as the epoch.
• NACK after a short reorder delay (a few ms or a few later messages). An immediate NACK on every reorder causes spurious retransmits; TCP waits for 3 duplicate ACKs before fast retransmit.
• Ring-buffer the sender copies of serialized bytes, not objects: a resend becomes one writev of a contiguous slice.
• Make the resume cursor the same number as the ack, so reconnect and steady-state share one code path.

Pitfalls

• Comparing wrapped 32-bit sequences with <: wrong after 2^32 messages. Use serial arithmetic ((a.wrapping_sub(b) as i32) > 0) or extend to 64 bits.
• Restarting the counter at 0 after a crash without bumping the epoch: the receiver silently drops everything as duplicates.
• Assigning a sequence, then failing to send or persist that message: a permanent gap. Assign after the point of no return, or send an explicit gap-fill (FIX SequenceReset with GapFillFlag=Y).
• Unbounded reorder buffer: a hostile or broken sender sends seq = next + 10^9 and the receiver buffers forever. Cap it and fall back to resync.
• Acking a message that was buffered but not yet delivered: the sender frees it, and a crash loses it. Ack the contiguous delivered prefix only.
• Trimming the sender buffer on time instead of on acks: a slow client asks for a range that is gone. Detect it (None above) and send a snapshot.

Variants and alternatives

In production

TCP (32-bit byte sequences, PAWS timestamps against wrap), QUIC (62-bit packet numbers truncated to 1-4 bytes on the wire), FIX (MsgSeqNum tag 34, ResendRequest, SequenceReset/gap fill), Nasdaq MoldUDP64 market data (64-bit sequence plus a re-request server), Kafka idempotent producer (producer id, epoch, per-partition sequence), Server-Sent Events (Last-Event-ID on reconnect), NATS JetStream stream sequences, Aeron (NAK-driven loss recovery over UDP).

Implementations

Sources

• R. Elz, R. Bush, Serial Number Arithmetic, RFC 1982, 1996. rfc
• D. Borman, B. Braden, V. Jacobson, R. Scheffenegger, TCP Extensions for High Performance (PAWS), RFC 7323, 2014. rfc
• J. Iyengar, M. Thomson (eds.), QUIC: A UDP-Based Multiplexed and Secure Transport, RFC 9000, 2021 (Appendix A.3: packet number decoding). rfc
• W. Eddy (ed.), Transmission Control Protocol (TCP), RFC 9293, 2022. rfc
• Apache Kafka, KIP-98: Exactly Once Delivery and Transactional Messaging. wiki
• WHATWG, HTML Standard: Server-sent events (Last-Event-ID). spec