Leaderless Key-Value Store

This repo contains an example leaderless key-value store based on:

• Rendezvous Hashing and MurmurHash to efficiently shard keys
• Quorum Consistency to tradeoff good consistency vs tolerating node failures
• Quorum Clocks to logically order the data

Nodes are homogenous. Every node acts as both storage and coordinator. This means that any node can accept external queries.

APIs are implemented with gRPC and Protobuf. Nodes store their data using BadgerDB.

Status

A 5-node cluster can accept 1krps of 10KB writes with minimal errors. This is with 2 EPYC CPU cores per node. Performance appeared to be CPU-bound so higher performance should be easily obtainable.

This is not intended as a production commercial project. It is merely for learning. There are numerous FIXME comments throughout the codebase. Many suggest performance improvements but others deal with rare errorcases.

This does not implement data re-replication. Nodes that have been offline and missed some writes do not get that missing data synced to them. Similarly new nodes do not get existing data. This could be added using a Dynamo-style Anti-Entropy process.

Notes

Regenerate protobuf Go code:

protoc -I=. --go_out=. --go-grpc_out=. api/api.proto

Start a 3-node local test server:

go run ./cmd/main/main.go ./examples/3-local-nodes/node-1.yml ./examples/3-local-nodes/cluster.yml
go run ./cmd/main/main.go ./examples/3-local-nodes/node-2.yml ./examples/3-local-nodes/cluster.yml
go run ./cmd/main/main.go ./examples/3-local-nodes/node-3.yml ./examples/3-local-nodes/cluster.yml

Interact manually with the Cluster API:

grpcurl -plaintext -d '{"key": "b"}' -proto api/api.proto localhost:8001 api.Cluster/Get
grpcurl -plaintext -d '{"entry": {"key": "b", "value": "b-value"}}' -proto api/api.proto localhost:8001 api.Cluster/Set

Interact manually with the Node API:

grpcurl -plaintext -d '{}' -proto api/api.proto localhost:8001 api.Node/Info
grpcurl -plaintext -d '{}' -proto api/api.proto localhost:8001 api.Node/Health
grpcurl -plaintext -d '{"key": "a"}' -proto api/api.proto localhost:8001 api.Node/Get
grpcurl -plaintext -d '{"entry": {"key": "a", "value": "a-value"}}' -proto api/api.proto localhost:8001 api.Node/Set

Load test with ghz:

ghz --rps=250 --duration 15s --skipFirst 1000 --insecure --connections 5 --proto ./api/api.proto --call api.Cluster/Set -d '{"entry": {"key": "{{.UUID}}", "value": "{{randomString 1024}}"}}' --lb-strategy=round_robin dns:///rz.46b.it:80