Sequencer-based Architecture (CRDT-free)

[murphyjacob4]

Note: This proposal was discussed in the weekly tech sync. I have had an AI write this so that we can unblock discussion. Hopefully I will have some time to revisit and clean it up, but don't want to block discussion.

Summary

This issues proposes an active-active (multi-writer) replication architecture for Valkey powered by an elected Central Sequencer.

The core tenets of this design are:

1. Optimistic Local Execution: Replicas accept and execute writes locally for low client latency.
2. Reused Election Infrastructure: The primary node serves as the central sequencer (primary == sequencer), leveraging Valkey's existing election and failover mechanisms.
3. Total Ordering via Key Versioning: Replicas stream operations with key-level logical version numbers to the sequencer, which establishes a canonical global ordering.
4. Dual-Channel PSYNC Replication: Two symmetric, independent PSYNC streams (upstream and downstream) using standard replid and repl_offset prevent double-apply and enable seamless reconnects without per-command Op IDs.
5. Optimized Zero-Echo Replication: For conflict-free writes, the sequencer does not replicate command payloads back to the originating replica (only to other replicas), minimizing network overhead.
6. Conflict Reconciliation: When conflicts or divergence occur, the sequencer corrects the originating replica (initially via key snapshots, with targeted deltas as a future enhancement).

---

Architecture Overview

Diagram 1: Clean Write Path (No Conflict, Zero-Echo)

sequenceDiagram
    autonumber
    actor ClientA as Client A
    participant RepA as Replica A (Origin)
    participant Seq as Sequencer (Primary)
    participant RepB as Replica B
    actor ClientB as Client B

    Note over RepA,RepB: Key 'mylist' is at Version v1 = ["item0"]

    ClientA->>RepA: LPUSH mylist "itemA"
    RepA->>RepA: Apply locally: ["itemA", "item0"] & write repl_backlog
    RepA-->>ClientA: OK (low latency)
    RepA-)Seq: Upstream async replication (LPUSH mylist "itemA", base_version: v1)
    
    Seq->>Seq: Apply & commit to canonical state: ["itemA", "item0"] (v2)
    Note over Seq,RepA: Zero-echo back to Replica A
    Seq-)RepB: Downstream async replication (LPUSH mylist "itemA", v2)
    RepB->>RepB: Apply locally: ["itemA", "item0"]

Loading

Diagram 2: Conflict & Rebase Path (Concurrent Writes & Snapshot Correction)

sequenceDiagram
    autonumber
    actor ClientA as Client A
    participant RepA as Replica A
    participant Seq as Sequencer (Primary)
    participant RepB as Replica B
    actor ClientB as Client B

    Note over RepA,RepB: Key 'mylist' is at Version v1 = ["item0"]

    %% Concurrent Writes
    par Concurrent Optimistic Writes
        ClientA->>RepA: LPUSH mylist "itemA"
        RepA->>RepA: Apply locally: ["itemA", "item0"] & write repl_backlog
        RepA-->>ClientA: OK (low latency)
        RepA-)Seq: Upstream: LPUSH mylist "itemA" (base_version: v1)
    and
        ClientB->>RepB: LPUSH mylist "itemB"
        RepB->>RepB: Apply locally: ["itemB", "item0"] & write repl_backlog
        RepB-->>ClientB: OK (low latency)
        RepB-)Seq: Upstream: LPUSH mylist "itemB" (base_version: v1)
    end

    %% Sequencer receives RepA first (Clean)
    Seq->>Seq: Apply Op A (base: v1 == canonical: v1) -> ["itemA", "item0"] (v2)
    Seq-)RepB: Downstream: LPUSH mylist "itemA" (v2)
    Note over RepB: RepB detects conflict with pending local v2<br/>(Drops delta & awaits sequencer snapshot)

    %% Sequencer receives RepB second (Conflict / Rebase)
    Seq->>Seq: Op B has base: v1 != canonical: v2 (Rebase detected!)
    Seq->>Seq: Rebase Op B on top of v2 -> ["itemB", "itemA", "item0"] (v3)
    Seq-)RepA: Downstream: LPUSH mylist "itemB" (v3)
    Seq-)RepB: Correction: Snapshot 'mylist' = ["itemB", "itemA", "item0"] (v3)
    Note over RepB: RepB applies snapshot correction & advances to v3 (Converged)

Loading

---

Key Design Principles

1. Sequencer Election, Role & Failover

• Election & Topology: The central sequencer is elected using Valkey's existing cluster / Sentinel election and failover protocols (primary == sequencer), reusing standard heartbeat monitoring and failover pathways without requiring an external consensus layer.
• Failover & Canonization: When the active sequencer fails, a new primary/sequencer is elected from among the surviving replicas.
• Opportunistic State Becomes Canonical: Upon promotion, the newly elected sequencer's local opportunistic state immediately becomes the cluster's canonical state. Any local writes that were in its backlog are canonized, and it assumes the authoritative version counters for all keys.
• Replica Reconciliation: Other replicas reconnect to the newly promoted sequencer (via PSYNC), stream any remaining unacknowledged backlog, and reconcile their local states against the new sequencer's canonical stream.

2. Optimistic Local Execution

• Clients issue write commands to their closest/local replica.
• The replica executes the mutation locally and immediately returns the result to the client.
• In parallel, the replica buffers and forwards the command to the sequencer along with the key's current local logical sequence/version number.

3. Key Versioning Metadata

• Each key maintains a single logical version / sequence number.
• When a replica forwards a mutation Op(K) to the sequencer, it attaches the base_version of K observed at the time of local execution.

4. Dual-Channel Bidirectional Replication & Double-Apply Prevention (Dual PSYNC)

Rather than introducing custom transaction IDs, operation UUIDs, or novel sync protocols, the architecture runs two symmetric, independent PSYNC replication channels between each replica and the sequencer, fully reusing Valkey's standard Replication IDs (replid) and monotonic byte offsets (repl_offset):

flowchart LR
    subgraph SequencerNode ["Elected Sequencer"]
        Seq["Sequencer Engine"]
    end

    subgraph ReplicaNodeA ["Replica A"]
        RepA["Replica A Engine"]
    end

    RepA -- "Upstream PSYNC (Replica A is Master)" --> Seq
    Seq -- "Downstream PSYNC (Sequencer is Master)" --> RepA

Loading

1. Upstream Channel (Replica -> Sequencer):

   • Role: The replica acts as the producer/master of its local optimistic write stream (replica_replid, replica_repl_offset), and the sequencer acts as the consumer.
   • Upstream Backlog: When a replica applies an optimistic write locally, it appends the command to its local repl_backlog and advances its replica_repl_offset.
   • Double-Apply Prevention via Upstream PSYNC: When reconnecting, the upstream link negotiates via PSYNC <replica_replid> <upstream_offset>. The sequencer confirms its last_processed_offset, and the replica resumes streaming strictly from last_processed_offset + 1. This guarantees strictly exactly-once processing upstream with zero duplicate execution.
   • Backlog Trimming: Periodic upstream REPLCONF ACK heartbeats allow the replica to safely trim its local backlog up to the sequencer's acknowledged offset.

2. Downstream Channel (Sequencer -> Replica):

   • Role: The sequencer acts as the authoritative master of the globally ordered stream (sequencer_replid, sequencer_repl_offset), and replicas act as followers.
   • Downstream PSYNC: Replicas consume canonical operations, rebased updates, and snapshot corrections. On reconnect, the downstream link negotiates via standard PSYNC <sequencer_replid> <downstream_offset>.

3. Failover & History Preservation:

   • Reuses Valkey's existing dual replication ID model (replid and replid2 with second_replid_offset) during sequencer failover, enabling seamless partial resynchronization across primary promotions.

5. Authoritative Sequencing & Downstream Replication

When the sequencer receives an upstream operation:

• It validates the operation's base_version against the key's current canonical version.
• If No Conflict Occurs (Clean Write):
  • Originating Replica: Does not receive the command payload back (zero-echo). The replica's local state is already up-to-date, and normal periodic replication offsets handle backlog trimming.
  • Other Replicas: The sequencer writes the operation to its downstream replication backlog and streams it to all other replicas via standard replication channels.
• If a Conflict / Divergence Occurs:
  • Conflict Handling on Replicas (Drop & Await): If a replica receives a downstream delta for a key on which it has an active, uncommitted local write with the same base version, it recognizes that its local write lost the sequencer race. It drops the incoming delta and awaits the sequencer's authoritative snapshot.
  • Originating Replica: The sequencer detects that the replica's optimistic state diverged from canonical order (e.g., another write was ordered first). The sequencer sends a correction payload (snapshot or reconciliation delta) back to the originating replica to reconcile local state.
  • Other Replicas: Receive the sequencer's canonical final state / resolved operation.

---

Unified Mutation Rebasing & Conflict Handling

The replication protocol treats all mutations under a single, unified Rebase & Correction model regardless of the specific command type (SET, LPUSH, HINCRBY, ZADD, etc.):

1. Clean Commit (base_version == canonical_version):

   • The operation was applied against the current canonical baseline.
   • Originating Replica: Zero payload echo. Upstream offset acknowledged for standard backlog trimming.
   • Other Replicas: Receive the command via the standard downstream replication stream.

2. Rebased Mutation (base_version != canonical_version):

   • The originating replica executed its mutation against a stale baseline (e.g. $v_0$, but sequencer is at $v_1$).
   • The sequencer rebases the mutation by applying it on top of its current canonical state (producing $v_2$).
   • Because the originating replica's local history diverged from canonical ordering, the sequencer issues a correction to the rebased replica.
   • Reconciliation Strategy:
     • Phase 1 (Baseline): Sequencer sends a key snapshot / authoritative replacement to the rebased replica.
     • Phase 2 (Optimization): Targeted delta corrections / operational transforms where advantageous.
   • Other Replicas: Receive the rebased mutation / canonical stream as normal.

---

Detailed Scenarios

Scenario 1: Clean Write (No Conflict, Zero-Echo)

1. Key counter is at v1 = 10.
2. Replica A receives INCR counter -> applies locally (11), responds to client, and forwards INCR counter (base: v1) to sequencer.
3. Sequencer receives the op; canonical version matches v1. Sequencer applies INCR -> counter = 11 (v2).
4. Downstream:
   • Replica A: No command payload replicated back. State is already 11.
   • Replica B: Receives INCR counter (v2) from sequencer and updates state to 11.

Scenario 2: Concurrent List Pushes (LPUSH)

1. Key queue has v1 = ["msg0"].
2. Client A on Replica A executes LPUSH queue msgA -> local state: ["msgA", "msg0"].
3. Client B on Replica B executes LPUSH queue msgB -> local state: ["msgB", "msg0"].
4. Sequencer receives Replica A's push first, then Replica B's push:
   • Sequencer applies msgA -> ["msgA", "msg0"] (v2).
   • Sequencer applies msgB -> ["msgB", "msgA", "msg0"] (v3).
5. Downstream:
   • Replica A: Receives LPUSH queue msgB (v3) from sequencer and updates state to ["msgB", "msgA", "msg0"].
   • Replica B: Receives LPUSH queue msgA (v2, base: v1) from sequencer $\rightarrow$ detects conflict with its local pending write $\rightarrow$ drops the delta and awaits snapshot. Sequencer then delivers snapshot ["msgB", "msgA", "msg0"] (v3) to Replica B.
   • Both replicas converge to ["msgB", "msgA", "msg0"].

Scenario 3: Conflicting Overwrites (SET)

1. Key config is at v1 = "alpha".
2. Replica A sets config = "beta" (base: v1).
3. Replica B sets config = "gamma" (base: v1).
4. Sequencer receives Replica A first -> sets config = "beta" (v2).
5. Sequencer receives Replica B with stale base: v1 -> sequencer rebases B on top of v2 -> sets config = "gamma" (v3).
6. Downstream:
   • Replica A: Receives SET config = "gamma" (v3) from sequencer and updates to "gamma".
   • Replica B (Rebased Origin): Receives key snapshot correction from sequencer (config = "gamma" at v3) to reconcile its local state.

---

Replication & Network Efficiency Summary

Scenario	Originating Replica (Writer)	All Other Replicas
No Conflict (Clean write)	Zero payload echo (periodic offset ACK trims local backlog)	Full command replicated downstream
Conflict Detected (Divergence / stale base)	Correction / Key Snapshot sent to reconcile state	Canonical command / state replicated downstream

---

Full Sync & Divergence Recovery

When network partitions or prolonged disconnections cause the command stream to diverge beyond the capacity of the replication backlog, nodes fall back to a full synchronization (FULLRESYNC) while preserving un-sequenced local mutations:

1. Upstream Backlog Drain Prior to Snapshot (Flush-Before-Snapshot)

Flushing the replica's un-sequenced backlog before generating the RDB snapshot ensures optimal network efficiency and avoids transmitting modified keys twice:

• Trigger: A replica reconnects with a downstream replication offset that has rolled out of the sequencer's repl_backlog.
• Step 1: Flush Upstream Backlog: Before the snapshot is captured, the replica streams its entire un-sequenced local repl_backlog upstream to the sequencer.
• Step 2: Sequencer Rebasing: The sequencer processes and authoritatively rebases the replica's pending mutations directly on top of its canonical in-memory state.
• Step 3: RDB Snapshot Generation (FULLRESYNC): Once the upstream backlog is fully drained and ingested, the sequencer generates and transmits the RDB snapshot (with per-key logical versions).
• Step 4: Single-Pass Convergence (Zero Duplicate Key Transfers): The replica flushes its local data and loads the sequencer's RDB snapshot. Because the snapshot already incorporates all of the replica's rebased writes in their final canonical state, no keys are transferred twice, no secondary post-RDB catch-up phase is required, and the replica is immediately converged and ready for client traffic upon loading the snapshot.

2. Upstream Backlog Protection & Backpressure

• Reuses existing Valkey backlog configuration (repl-backlog-size, repl-backlog-ttl).
• If a replica loses its upstream connection to the sequencer while continuing to accept local writes, its local repl_backlog will accumulate un-sequenced mutations.
• When the local backlog reaches capacity, the replica applies backpressure (e.g. rejecting new writes with -ERR replication backlog full or degrading to read-only mode) to prevent silently overwriting un-replicated local writes before they can be flushed to the sequencer.

3. Reconnection & Resync Flow

[Replica Reconnects]
        │
        ├──► [Offset within Sequencer Backlog] ──► Sequencer issues +CONTINUE (Partial Sync)
        │
        └──► [Offset outside Sequencer Backlog] ─► 1. Flush Upstream Backlog to Sequencer
                                                         │
                                                         ▼
                                                   2. Sequencer Rebases Backlog into State
                                                         │
                                                         ▼
                                                   3. Sequencer Generates RDB Snapshot
                                                      (Includes Rebased Writes)
                                                         │
                                                         ▼
                                                   4. Replica Loads RDB Snapshot
                                                      (Immediately Converged & Ready)

Design Comparison: Sequencer vs. CRDTs vs. Pure LWW

Dimension	Sequencer-Based (This Proposal)	CRDT-Based (e.g. PN-Counters, OR-Sets, RGA)	Pure Last-Write-Wins (LWW / Timestamps)
Data Structure Semantics	Native Valkey Semantics: Full support for Lists (LPUSH, LREM, LTRIM), Hashes, Sets, Sorted Sets, and Counters via mutation rebasing.	Constrained / Specialized: Many standard Valkey operations (e.g., list indexing, LSET, LTRIM, BRPOP) cannot be modeled cleanly as CRDTs without semantic compromises.	Lossy for Collections: Treats whole keys/fields as scalar values; cannot merge concurrent collection mutations without data loss.
Memory & Metadata Overhead	Minimal: 1 logical version integer per key (no tombstones or vector clocks).	High: Requires vector clocks, per-element timestamps, causal dot-contexts, and tombstones for deleted elements.	Low: 1 physical/hybrid timestamp per key or field.
Data Loss on Concurrent Writes	Zero loss on collection & commutative writes: Concurrent LPUSH, SADD, INCR are rebased and merged into canonical state.	Zero loss: Merged via commutative/associative join semilattice functions.	High: Concurrent updates silently overwrite each other based on timestamp (lost increments, lost list items).
Clock Synchronization Dependency	None: Relies strictly on logical version numbers and sequencer arrival order. Immune to NTP drift / leap seconds.	None to Low: Relies on logical/vector clocks (though LWW-CRDT variants use timestamps).	Critical: Highly vulnerable to clock skew, NTP desynchronization, and future-dated write domination.
Tombstone Garbage Collection	Not Required: Standard Valkey DEL / UNLINK lifecycle applies directly.	Complex: Requires distributed GC protocols to purge tombstones without risking element resurrection.	Not Required: Standard deletion applies.
Topology & Consensus	Primary/Replica Topology: Leverages existing Valkey cluster / Sentinel election (primary == sequencer).	Decentralized / Mesh: Replicas can replicate peer-to-peer without an elected leader.	Decentralized / Mesh: Peer-to-peer replication with timestamp arbitration.
Implementation Complexity	Low to Moderate: 100% reuse of existing Valkey replication engine (repl_backlog, replid, repl_offset, PSYNC, RDB).	Extremely High: Requires reimplementing core data structures, serialization formats, and merge functions across all commands.	Low: Timestamp checks on write/replication.

---

Detailed Architectural Trade-offs

1. Sequencer-Based Design (This Proposal)

• Pros:
  • Preserves Native Semantics: Complex collection commands (LPUSH, RPUSH, LTRIM, HINCRBY, ZADD) work identically to single-node Valkey because the sequencer applies and rebases them in deterministic sequence.
  • Zero Extra Memory Bloat: Avoids storing tombstones or vector clocks; only a single logical version number is tracked per key.
  • Leverages Existing Valkey Stack: Reuses cluster election, replication backlogs, replid/offset tracking, and PSYNC without requiring external dependencies or new distributed engines.
  • Zero Lost Updates: Commutative and collection mutations from partitioned replicas are preserved and rebased upon reconnection rather than overwritten.
• Cons / Trade-offs:
  • Sequencer Dependency for Total Order: Canonical ordering requires an active sequencer. If the sequencer fails, standard failover must elect a new primary to resume canonical sequencing (though replicas can continue accepting optimistic local writes).
  • Snapshot Reconciliation on Rebase: In the initial baseline implementation, conflicting non-commutative mutations on the same key trigger a full key snapshot to the rebased replica.

2. Conflict-free Replicated Data Types (CRDTs)

• Pros:
  • True Peer-to-Peer Multi-Master: Replicas can exchange updates directly in any mesh topology without a central sequencer or primary election.
  • Partition Progress: Replicas can continue writing indefinitely during arbitrary network splits without coordinating with a leader.
• Cons:
  • Substantial Memory Overhead: CRDTs require storing metadata (timestamps, node IDs, vector clocks) for every element, plus maintaining tombstones for deleted elements to prevent resurrection.
  • Semantic Mismatch with Valkey: Standard Valkey data structures are not CRDTs. Replicating list index mutations (LSET, LINSERT), list trimming (LTRIM), or blocking operations (BLPOP) with CRDTs either requires completely redesigning data structures (e.g. RGA, Logoot) or accepting degraded semantic compatibility.
  • High Maintenance Burden: Adding or modifying Valkey commands requires authoring and proving custom conflict-resolution functions.

3. Pure Last-Write-Wins (LWW) / Timestamp-Based

• Pros:
  • Simple to Implement: Minimal code changes; incoming updates overwrite local state if their timestamp is newer.
  • Low Metadata: Only requires storing a physical timestamp or Hybrid Logical Clock (HLC) per key/field.
• Cons:
  • Silent Data Loss: LWW is inherently lossy for non-commutative operations. Two concurrent INCR commands will result in one increment being silently lost. Concurrent LPUSH commands will result in one list push overwriting the other.
  • Clock Drift Sensitivity: Even minor clock skew between servers can cause writes from one node to permanently mask writes from other nodes.

Inherent Active-Active Trade-offs (Applicable to All Multi-Master Designs)

Like all asynchronous multi-master systems (including CRDTs and LWW), certain trade-offs are mathematically unavoidable without synchronous coordination:

1. Conditional Mutations (NX, XX, CAS): Optimistic conditional writes may succeed locally on a replica but fail when rebased against the sequencer's canonical state. (CRDTs avoid this only by disallowing conditional commands entirely).
2. Provisional Read Consistency: Reads on non-sequencer nodes are optimistic and subject to reconciliation if concurrent conflicting writes occur in other regions.

---

Open Questions & Future Enhancements

1. Rebase via Delta:

• For large composite structures (e.g., Hashes with thousands of fields), snapshot is very inefficient when there is only a small subset of elements out of sync. How can we support element-level deltas, and under what conditions should snapshotting fall back to these element-level deltas?

3. Transient Dirty Reads:
   • Since local reads on replicas are optimistic, is eventual consistency sufficient for all commands, or should an optional WAIT_SEQUENCED flag be provided for read-after-write strictness? How about Lua and MULTI/EXEC? Should we defer Lua transactions to the sequencer?

[murphyjacob4]

Some thoughts after posting:

• Special command rewrites: Need to audit how all commands would be replicated, but top of mind we would need to change at least:
  • LPOP key / RPOP key $\rightarrow$ LREM key 1 <exact_popped_value>: Prevents an LPOP from popping a newly prepended item that arrived at the sequencer concurrently. The item popped by the client remains the one removed. There are limitations (e.g. duplicate elements) which we could work around by giving list elements unique IDs, though that may be overkill for a first pass.
  • Floating-point counters (INCRBYFLOAT, HINCRBYFLOAT): Need to be streamed as relative accumulators (INCRBYFLOAT key +val), which rebase commutatively. Today we replicate these as absolute results (SET). Minor floating-point precision differences across architectures in multi-master mode should be acceptable.
• Eviction / Expiration: One major advantage of using a central sequencer is that we can centralize eviction (maxmemory) and TTL expiration, identical to primary/replica behavior today.
• Backlog and Offsets: If the sequencer is sending different replication streams to different nodes (e.g. not echoing back to the originator, sending snapshots on rebase), then a lot of today's shared offset machinery will break. The sequencer would likely need to track a per-replica offset and backlog (similar to how pre-unified replication backlogs worked). Alternatively, we could keep an identical replication stream and drop the "zero-echo" architecture by attaching an "originator ID" to each sequenced command so the originator simply skips executing commands it sent. However, "rebasing" still creates asymmetry (e.g. sending snapshots only to the diverged node), which would otherwise have to travel over a separate connection and introduce cross-stream race conditions.
• Networking / CPU Cost on the Sequencer: One disadvantage compared to decentralized/mesh architectures is that the sequencer bears most of the replication cost. For every write in the cluster, the sequencer pays either $N$ or $N-1$ downstream writes to replicas. At high replica counts, the sequencer will become the network/CPU bottleneck. In a true mesh-style active-active setup, each node pays $N-1$ writes for local writes and 0 for remote writes, more evenly distributing the load across all nodes.