The problem
Store and serve key-value data across dozens of servers over UDP, and keep every key available and consistent while servers are suspended or rejoin.
Key decisions
- Consistent hashing
- Keys are placed on a hash ring, so when a server joins or leaves only the keys next to it move. Any server can accept a request and forward it to the right owner.
- Gossip membership
- Servers share membership information with random peers, so failures are detected without a central coordinator.
- Replication with repair
- Each key is copied to neighbouring servers on the ring. When a server fails or rejoins, the ring is compared with its previous state to work out which replicas to move, and the copies are sent in batches.
- At-most-once requests
- A request cache returns the stored reply for retried requests, so a lost UDP reply never applies a write twice.
Results
- No keys lost when servers failed mid-test
- About 47,000 requests per second across 40 nodes
Built with
Java, Protocol Buffers, UDP, JUnit, AWS EC2, Terraform