Building a Grow-Only Counter on a Sequentially Consistent KV Store
5 days ago
- #consistency-models
- #distributed-systems
- #crdt
- The post discusses building a Grow-Only Counter (G-Counter) on Maelstrom's sequentially consistent key-value store (SeqKV), addressing Challenge #4 in Fly.io's distributed systems series.
- Initial naive solutions using a single key or per-node keys with read-modify-write or CompareAndSwap (CAS) operations are non-deterministic due to concurrent updates and stale reads allowed under sequential consistency, where anomalies like stale reads after a cooldown period can occur.
- A CRDT-like approach is explored, where each node updates its own counter key, reducing write conflicts by summing all node counters for reads, but this still faces non-determinism due to SeqKV's consistency model and implementation quirks.
- The post explains sequential consistency as a model where operations have a total order consistent with each client's program order but may not match real-time order, allowing anomalies like stale reads, which differs from linearizability that enforces real-time order.
- A hacky solution involves writing a unique value to force SeqKV clients to the latest state before reads, leveraging SeqKV's internal behavior, while non-hacky alternatives include implementing a true CRDT with gossip or switching to a linearizable store like LinKV for deterministic results.