Skip to content

mchernyakov/gossip-glomers

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

27 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Gossip Glomers

An awesome challenge by fly.io and Kyle Kingsbury.

Solutions

Challenge 1: Echo

Echo -- a simple echo, nothing fancy.

Challenge 2: Unique Id Generation

The solution generates unique int64 id based on timestamp, machine-id and an internal counter.

Challenge 3: Broadcast

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.

Challenge 4: Grow-Only Counter

The solution is based on CRDT logic.

Articles:

Challenge 5: Kafka-Style Log

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:

Challenge 6: Totally-Available Transactions

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 work.

Articles:

Project structure

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 gitignore

I use Makefile for building and running solutions.

Note that custom names of bin-files are used.