Message Deduplication and Ordering

Networks Are Liars

You send a message. The server processes it. The acknowledgment gets lost. Your client doesn't know the server received it, so it retries. Now the server has processed the same message twice.

Or: you send messages A, B, C in order. They take different network paths. The server receives A, C, B. Or A, A, C (B got lost and A was retried).

These aren't edge cases. These are normal conditions in distributed systems. TCP handles ordering within a single connection, but the moment you have reconnections, multiple connections, or a load balancer routing requests to different servers, all ordering bets are off.

Idempotency: The Foundation of Deduplication

An operation is idempotent if performing it multiple times produces the same result as performing it once. "Set balance to $100" is idempotent. "Add $100 to balance" is not.

For non-idempotent operations, you need idempotency keys — unique identifiers that let the server recognize and discard duplicates.

function generateIdempotencyKey(): string {
  return `${Date.now()}-${crypto.randomUUID()}`;
}

class IdempotentSender {
  private pendingKeys = new Map<string, { message: string; timestamp: number }>();

  send(ws: WebSocket, type: string, payload: unknown): string {
    const key = generateIdempotencyKey();
    const message = JSON.stringify({ key, type, payload });

    this.pendingKeys.set(key, { message, timestamp: Date.now() });
    ws.send(message);

    return key;
  }

  acknowledge(key: string): void {
    this.pendingKeys.delete(key);
  }

  retryPending(ws: WebSocket): void {
    for (const [key, { message }] of this.pendingKeys) {
      ws.send(message);
    }
  }
}

On the server side, you need a deduplication layer:

class DeduplicationLayer {
  private seen = new Map<string, { result: unknown; expiresAt: number }>();
  private cleanupInterval: ReturnType<typeof setInterval>;

  constructor(private ttlMs = 300_000) {
    this.cleanupInterval = setInterval(() => this.cleanup(), 60_000);
  }

  async process<T>(
    key: string,
    handler: () => Promise<T>
  ): Promise<{ result: T; duplicate: boolean }> {
    const existing = this.seen.get(key);
    if (existing) {
      return { result: existing.result as T, duplicate: true };
    }

    const result = await handler();
    this.seen.set(key, { result, expiresAt: Date.now() + this.ttlMs });
    return { result, duplicate: false };
  }

  private cleanup(): void {
    const now = Date.now();
    for (const [key, entry] of this.seen) {
      if (entry.expiresAt <= now) {
        this.seen.delete(key);
      }
    }
  }
}

Sequence Numbers: Ordering Within a Stream

When you need messages processed in order, assign monotonically increasing sequence numbers:

class SequencedStream {
  private nextSeq = 0;
  private buffer = new Map<number, unknown>();
  private expectedSeq = 0;

  send(ws: WebSocket, payload: unknown): void {
    const seq = this.nextSeq++;
    ws.send(JSON.stringify({ seq, payload }));
  }

  receive(
    seq: number,
    payload: unknown,
    onOrdered: (payload: unknown) => void
  ): void {
    if (seq < this.expectedSeq) {
      return; // duplicate, already processed
    }

    this.buffer.set(seq, payload);

    while (this.buffer.has(this.expectedSeq)) {
      onOrdered(this.buffer.get(this.expectedSeq));
      this.buffer.delete(this.expectedSeq);
      this.expectedSeq++;
    }
  }
}

This gives you total ordering within a single stream. Messages are buffered until all predecessors arrive, then delivered in sequence. Simple and effective for a single client-server connection.

But it breaks the moment you have multiple senders. Client A sends message 5, Client B sends message 5 — whose "5" comes first? Sequence numbers are local; they don't capture causality across multiple participants.

Lamport Timestamps: Causal Ordering Across Nodes

Leslie Lamport's 1978 paper gave us a beautifully simple idea: a logical clock that captures the "happened before" relationship.

Each node maintains a counter. The rules:

1. Before sending a message, increment your counter.
2. When receiving a message, set your counter to max(your counter, received counter) + 1.
3. If event A's timestamp is less than event B's, A might have happened before B.

class LamportClock {
  private time = 0;

  tick(): number {
    return ++this.time;
  }

  send(): number {
    return this.tick();
  }

  receive(remoteTime: number): number {
    this.time = Math.max(this.time, remoteTime) + 1;
    return this.time;
  }

  now(): number {
    return this.time;
  }
}

Vector Clocks: True Causality Detection

A vector clock is a Lamport clock per node. Each node maintains a vector of counters — one for every node in the system. This lets you distinguish between "A happened before B" and "A and B are concurrent."

class VectorClock {
  private clock: Map<string, number>;

  constructor(private nodeId: string, nodeIds: string[]) {
    this.clock = new Map(nodeIds.map((id) => [id, 0]));
  }

  tick(): Map<string, number> {
    this.clock.set(this.nodeId, (this.clock.get(this.nodeId) ?? 0) + 1);
    return new Map(this.clock);
  }

  send(): Map<string, number> {
    return this.tick();
  }

  receive(remote: Map<string, number>): Map<string, number> {
    for (const [nodeId, time] of remote) {
      this.clock.set(
        nodeId,
        Math.max(this.clock.get(nodeId) ?? 0, time)
      );
    }
    this.clock.set(this.nodeId, (this.clock.get(this.nodeId) ?? 0) + 1);
    return new Map(this.clock);
  }

  static compare(
    a: Map<string, number>,
    b: Map<string, number>
  ): 'before' | 'after' | 'concurrent' {
    let aBeforeB = false;
    let bBeforeA = false;

    const allKeys = new Set([...a.keys(), ...b.keys()]);
    for (const key of allKeys) {
      const aVal = a.get(key) ?? 0;
      const bVal = b.get(key) ?? 0;
      if (aVal < bVal) aBeforeB = true;
      if (aVal > bVal) bBeforeA = true;
    }

    if (aBeforeB && !bBeforeA) return 'before';
    if (bBeforeA && !aBeforeB) return 'after';
    return 'concurrent';
  }
}

Comparing two vector clocks:

• A "happened before" B if every entry in A is less than or equal to the corresponding entry in B, and at least one is strictly less.
• A and B are "concurrent" if neither dominates the other (A has some entries greater than B, and B has some entries greater than A).

Causal Ordering vs Total Ordering

These are fundamentally different guarantees:

For most real-time frontend applications, causal ordering is sufficient. You don't need all clients to see messages in the exact same order — you just need that if message B is a reply to message A, every client sees A before B.

Total ordering requires a consensus protocol (Raft, Paxos, or a centralized sequencer), which adds latency and complexity. It's necessary for financial transactions or any scenario where "who went first" has legal or monetary consequences.

The "Exactly Once" Myth

Here's the uncomfortable truth that every distributed systems textbook will tell you: exactly-once delivery is impossible in a system with unreliable networks.

You can have:

• At-most-once: Fire and forget. If the ACK is lost, don't retry. Message might be lost.
• At-least-once: Retry until acknowledged. Message might be delivered multiple times.
• Effectively-once: At-least-once delivery + idempotent processing. The message arrives at least once, but duplicate processing is detected and suppressed.

"Exactly once" is marketing language. What systems actually implement is "effectively once" — the combination of reliable delivery (retries) and idempotent processing (deduplication).