Design a Synchronously Replicated Hash Map

Scenario

You are tasked with designing an in-memory, distributed key-value store (hash map) deployed across two servers: an Active (Primary) node and a Passive (Standby) node.

The system must enforce synchronous replication: every write operation processed by the active node must be successfully acknowledged by the passive replica before returning success to the client. If replication to the passive node fails or times out, the write operation must fail, leaving both nodes in a consistent, non-divergent state.

Requirements

Functional Requirements

• Client APIs: Support standard hash map operations:
  • put(key, value): Inserts or updates the value for a given key.
  • get(key): Retrieves the current value associated with the key.
  • delete(key): Removes the key from the map.
• Routing: All writes (put, delete) must route through the Active node. Reads (get) can be served by either node, but must reflect the latest committed state.
• Synchronous Consistency: If the passive node fails to persist or acknowledge a write, the active node must roll back its local change and return an error to the client.

Non-Functional Requirements

• Strong Consistency: Linearizable read/write semantics; no dirty reads or partial writes.
• Low Latency: Primary operations execute against in-memory hash tables, targeting sub-millisecond local latency and minimal network overhead.
• High Availability & Fault Recovery: Clear protocol for failover when the primary fails and a recovery mechanism for bringing the passive node back into sync after downtime.

Scale & Constraints

• Dataset size: Up to 100 GB in memory (~100 million keys).
• Workload: 20,000 writes/sec and 100,000 reads/sec.
• Single dedicated network link between nodes with typical round-trip time under 1 ms.

What Your Design Should Cover

1. Replication Protocol: Detail the step-by-step handshake for write operations (e.g., two-phase commit vs. replicated commit log vs. dual-write with undo logs). Explain how rollback is executed on failure.
2. Concurrency Control: How the in-memory map on each node handles concurrent reads and writes without blocking unrelated keys.
3. Node Failure & Failover: The mechanism for detecting node failures, handling split-brain scenarios, and orchestrating failover when the primary goes down.
4. Replica Catch-up: How a restarted passive node reconciles missing updates to rejoin the replication stream.