An awesome challenge by fly.io and Kyle Kingsbury.
Echo -- a simple echo, nothing fancy.
The solution generates unique int64 id based on timestamp, machine-id and an internal counter.
All broadcast solutions are a simplified version of gossip protocol, a good article from Martin Fowler.
Broadcast a,b,c -- everyone sends to everyone.
Broadcast d uses an optimized version, where only the first receiver propagates data to others.
Broadcast e uses a more optimized version: a receiver collects data, then the received data is transmitted to other nodes according to a scheduled interval.
The solution is based on CRDT logic.
Articles:
Solutions are based on single writer/multiple-readers approach:
- using linearizable-KV we can set up our leader (partition-leader), which serves all writes (readers redirect writes to the leader).
- reads are served by every node.
Articles:
- https://bravenewgeek.com/building-a-distributed-log-from-scratch-part-1-storage-mechanics/
- https://bravenewgeek.com/building-a-distributed-log-from-scratch-part-2-data-replication/
Txn b: based on snapshots and last-write-wins model. Also, it broadcasts all writes to other nodes.
Txn c: initially, I thought about something more sophisticated like proper MVCC, but then it turned out (and proved by @elh's solution) that snapshots (again) + broadcasting writes works.
Articles:
- https://jepsen.io/consistency
- https://vldb.org/pvldb/vol5/p298_per-akelarson_vldb2012.pdf
- https://ebrary.net/64772/computer_science/implementing_read_committed
The project tree
├── LICENSE
├── Makefile // build and run commands
├── README.md
├── build
├── cmd // <- the solutions are here
├── go.mod
├── go.sum
├── internal // set of common/reusable go-files
└── maelstrom // maelstrom is in the root, but under gitignoreI use Makefile for building and running solutions.
Note that custom names of bin-files are used.