Contents
TABLE OF CONTENTS
← All posts

Building a Distributed Hash Table in Go

·12 min read
GoDistributed Systems

The Chord protocol is one of the canonical distributed hash table designs — elegant in its simplicity, with a clean ring topology and logarithmic routing. But reading the paper and implementing it in Go are two very different experiences. This post covers the gap between theory and practice, and the design decisions that emerged along the way.

The ring abstraction

Chord organizes nodes in a circular identifier space of size 2^m. Each node and key gets an m-bit identifier via a consistent hash function. A key k is assigned to the first node whose identifier is equal to or follows k in the identifier space — the successor of k. This gives you a clean invariant: at any point, each node is responsible for the keys between its predecessor and itself.

In Go, representing the ring starts with a sorted data structure. The naive approach is a sorted slice with binary search, but insertions and deletions are O(n). For a prototype that works fine. A production implementation would use a balanced tree or a skip list.

Created snippet.go
+14
+// Finger table entry points to successor at distance 2^i
+type FingerEntry struct {
+ Start uint64
+ Node *Node
+}
+
+type Node struct {
+ ID uint64
+ Address string
+ Finger []FingerEntry
+ Successor *Node
+ Predecessor *Node
+ Data map[string]string
+}

Finger tables and logarithmic routing

The finger table is what gives Chord its O(log N) lookup performance. Each node maintains a table of size m where the i-th entry points to the successor of (n + 2^i). To find a key, you forward the query to the finger entry that most immediately precedes the target — each hop at least halves the remaining distance.

Implementing this correctly requires careful handling of wraparound modulo 2^m. Go's uint64 arithmetic with overflow handled explicitly works well here. The more subtle challenge is maintaining finger tables under churn — nodes joining and leaving.

Created snippet.go
+15
+func (n *Node) ClosestPrecedingNode(id uint64) *Node {
+ for i := len(n.Finger) - 1; i >= 0; i-- {
+ if between(n.ID, id, n.Finger[i].Node.ID) {
+ return n.Finger[i].Node
+ }
+ }
+ return n
+}
+
+func between(a, x, b uint64) bool {
+ if a < b {
+ return a < x && x < b
+ }
+ return a < x || x < b
+}

Stabilization and eventual consistency

Chord does not maintain correctness of successor pointers on every join or leave — that would be too expensive. Instead, each node runs a periodic stabilization protocol: it asks its successor for its predecessor, and if that node should be the new successor, it updates its pointer. Successor lists (keeping the k nearest successors) provide fault tolerance.

In Go, this maps naturally to goroutines. Each node runs a stabilize loop with a configurable interval, communicating over gRPC. The key insight is that while individual pointers may be temporarily wrong, the system converges to correctness — as long as the stabilization interval is shorter than the mean time between failures.

What I'd do differently

The biggest lesson was that distributed systems testing is at least as hard as the implementation itself. Network partitions, slow nodes, and concurrent joins need systematic simulation. Jepsen-style testing with a deterministic scheduler would have caught several subtle bugs before they appeared in production-like environments.

The full implementation is on GitHub — it's about 2,000 lines of Go with a CLI for running local clusters. If you're learning distributed systems, building a DHT end-to-end is one of the most rewarding projects you can take on.

← Back to all posts