GoD-DB (Go DynamoDB-like System)

A Go-based implementation of a DynamoDB-like distributed key-value store, featuring consistent hashing, virtual nodes, N-way replication, gossip-based membership, vector clocks, and quorum-based reads and writes. It follows the design of the Amazon Dynamo paper.

Features

• Consistent Hashing: Keys are distributed across nodes using consistent hashing for scalability and fault tolerance.
• Virtual Nodes: Each physical node is represented by multiple virtual nodes on the hash ring for better distribution.
• Dynamic Membership: Nodes can join and leave the cluster dynamically via gossip protocol.
• Tunable Consistency: Configurable read quorum (R) and write quorum (W) for different consistency levels.
• Data Replication: Keys are replicated across N nodes for fault tolerance.
• Read Repair: Inconsistent replicas are repaired during read operations.

Architecture

A client sends a put/get over gRPC to any worker, which becomes the coordinator for that request. The coordinator uses consistent hashing (with virtual nodes) to locate the N replicas responsible for the key, forwards the operation to them, and waits for W write or R read acknowledgements to satisfy the configured quorum. Each worker persists its data in a local Redis instance, discovers its peers through a shared discovery Redis, and keeps membership up to date with a gossip protocol. Stale replicas are fixed by read repair.

flowchart TB
    Client(["Client CLI"])

    subgraph Cluster["GoD-DB cluster — gossip membership"]
        direction LR
        W1["Worker :8080<br/>coordinator"]
        W2["Worker :8081"]
        W3["Worker :8082"]
        W1 -.->|gossip| W2
        W2 -.->|gossip| W3
        W3 -.->|gossip| W1
    end

    R1[("Redis :63079")]
    R2[("Redis :63080")]
    R3[("Redis :63081")]
    Disc[("Discovery Redis :63179")]

    Client -->|"gRPC put/get"| W1
    W1 ==>|"replicate to N (quorum W/R)"| W2
    W1 ==> W3
    W1 --- R1
    W2 --- R2
    W3 --- R3
    W1 -.->|register| Disc
    W2 -.->|register| Disc
    W3 -.->|register| Disc

Loading

• Write path: client → coordinator → hash ring selects N replicas → replicate → acknowledge once W replicas confirm.
• Read path: client → coordinator → read from replicas → return once R agree → read-repair any stale copies.

Virtual Nodes in GoD-DB

Virtual nodes (or "vnodes") are a technique used in GoD-DB's consistent hashing implementation to improve key distribution and balance load across physical nodes, following the approach used in Amazon's DynamoDB.

How Virtual Nodes Work

Rather than representing each physical node as a single point on the hash ring, virtual nodes allow each physical node to be represented by multiple points on the ring. This provides several benefits:

1. Better Distribution: Virtual nodes result in more uniform distribution of keys across physical nodes.
2. Smoother Rebalancing: When nodes join or leave, virtual nodes ensure that only a small fraction of keys need to be redistributed, spread across multiple physical nodes.
3. Heterogeneous Nodes: By assigning more virtual nodes to more powerful hardware, the system can account for heterogeneous node capabilities.

Configuration

The number of virtual nodes can be configured per node:

# Start a worker with 100 virtual nodes per physical node
go run cmd/worker/main.go -virtualnodes=100

The default is 10 virtual nodes per physical node.

Implementation Details

In the implementation:

• Each physical node is mapped to multiple positions on the hash ring by creating multiple hash values
• For node identification, virtual node IDs are created by appending a suffix to the physical node ID
• The mapping from virtual nodes to physical nodes is maintained internally by the consistent hashing algorithm
• Key lookups are performed using the standard consistent hashing algorithm, treating virtual nodes as regular nodes

Usage

Starting a Worker Node

go run cmd/worker/main.go -port=50051 -redisport=63079 -virtualnodes=50

Starting a Client

go run cmd/client/main.go -server=localhost:50051

Configuration Options

Worker nodes accept the following configuration options:

• -port: Port to listen on for RPC requests
• -redisport: Port for the Redis storage backend
• -virtualnodes: Number of virtual nodes per physical node (default: 10)
• -replication: Replication factor (N)
• -writequorum: Write quorum (W)
• -readquorum: Read quorum (R)
• -gossip: Gossip interval (e.g., "10s")
• -peers: Number of peers to gossip with in each round
• -enablegossip: Enable/disable gossip protocol
• -discovery: Redis address for service discovery

Running Tests

The unit tests (consistent-hash ring and vector clocks) need no external services:

go test ./...

Running a Local Cluster

Each node uses Redis as its storage backend, so install Redis first:

sudo apt-get install redis-server   # Debian/Ubuntu

Then bring up a full cluster — three Redis instances, a discovery Redis, and three workers (ports 8080–8082) — with the helper script:

./run_cluster.sh

Per-process logs are written to logs/, and Ctrl+C tears the whole cluster down. In another terminal, connect a client to any worker:

go run cmd/client/main.go -server=localhost:8080

To build a fresh cluster and run an automated end-to-end PUT/GET check:

./test-goddb.sh

License

Released under the MIT License.