Building a Distributed Redis Cluster in Go Using Simple Consistent Hash

We introduce EasyRedis, a multi‑module Go project that implements a usable Redis service, and we focus on the distributed cluster component built with a consistent‑hash algorithm.

Consistent Hash Algorithm

When sharding data across nodes, the naive approach node = hashCode(key) % n changes the node assignment for most keys whenever the number of nodes n changes, causing costly data reshuffling. Consistent hashing maps both keys and server addresses into a 2^32‑size ring so that only keys near a changed node need to be remapped.

Nodes are placed on the ring by hashing their IP address; a key’s hash is then located by a clockwise search to the first node encountered. Virtual nodes are used to improve distribution without adding physical servers.

Code Implementation

The consistent‑hash code resides in tool/consistenthash/consistenthash.go:

type HashFunc func(data []byte) uint32

type Map struct {
    hashFunc  HashFunc       // hash function
    replicas  int            // number of virtual nodes per real node
    hashValue []int          // sorted hash values
    hashMap   map[int]string // hash value → real node address
}

func New(replicas int, fn HashFunc) *Map {
    m := &Map{replicas: replicas, hashFunc: fn, hashMap: make(map[int]string)}
    if m.hashFunc == nil {
        m.hashFunc = crc32.ChecksumIEEE
    }
    return m
}

Adding nodes generates replicas hash values per IP address and stores them in a sorted slice:

func (m *Map) Add(ipAddrs ...string) {
    for _, ipAddr := range ipAddrs {
        if ipAddr == "" { continue }
        for i := 0; i < m.replicas; i++ {
            hash := int(m.hashFunc([]byte(strconv.Itoa(i) + ipAddr)))
            m.hashValue = append(m.hashValue, hash)
            m.hashMap[hash] = ipAddr
        }
    }
    sort.Ints(m.hashValue)
}

Finding the node for a key searches the first hash value greater than or equal to the key’s hash, wrapping around to the first element if necessary:

func (m *Map) Get(key string) string {
    if m.IsEmpty() { return "" }
    partitionKey := getPartitionKey(key)
    hash := int(m.hashFunc([]byte(partitionKey)))
    idx := sort.Search(len(m.hashValue), func(i int) bool { return m.hashValue[i] >= hash })
    if idx == len(m.hashValue) { idx = 0 }
    return m.hashMap[m.hashValue[idx]]
}

func getPartitionKey(key string) string {
    beg := strings.Index(key, "{")
    if beg == -1 { return key }
    end := strings.Index(key, "}")
    if end == -1 || end == beg+1 { return key }
    return key[beg+1 : end]
}

Cluster Implementation

The cluster code lives in cluster/cluster.go. When the cluster starts, it reads the peers list from the configuration, creates a consistent‑hash map with 100 virtual nodes per real node, and adds all peer addresses plus its own address:

const replicas = 100

type Cluster struct {
    self        string
    clientFactory *RedisConnPool
    engine      *engine.Engine
    consistHash *consistenthash.Map
}

func NewCluster() *Cluster {
    cluster := Cluster{clientFactory: NewRedisConnPool(), engine: engine.NewEngine(), self: conf.GlobalConfig.Self}
    cluster.consistHash = consistenthash.New(replicas, nil)
    // deduplicate peers
    contains := make(map[string]struct{})
    peers := make([]string, 0, len(conf.GlobalConfig.Peers)+1)
    for _, peer := range conf.GlobalConfig.Peers {
        if _, ok := contains[peer]; ok { continue }
        peers = append(peers, peer)
    }
    peers = append(peers, cluster.self)
    cluster.consistHash.Add(peers...)
    return &cluster
}

When a client sends a Redis command, the cluster looks up the command handler in clusterRouter. Currently only set and get are registered and both delegate to defultFunc:

func (cluster *Cluster) Exec(c abstract.Connection, redisCommand [][]byte) (result protocol.Reply) {
    defer func() {
        if err := recover(); err != nil {
            logger.Warn(fmt.Sprintf("error occurs: %v
%s", err, string(debug.Stack())))
            result = protocol.NewUnknownErrReply()
        }
    }()
    name := strings.ToLower(string(redisCommand[0]))
    routerFunc, ok := clusterRouter[name]
    if !ok { return protocol.NewGenericErrReply("unknown command '"+name+"' or not support command in cluster mode") }
    return routerFunc(cluster, c, redisCommand)
}

var clusterRouter = make(map[string]clusterFunc)

func init() {
    clusterRouter["set"] = defultFunc
    clusterRouter["get"] = defultFunc
}

func defultFunc(cluster *Cluster, conn abstract.Connection, redisCommand [][]byte) protocol.Reply {
    key := string(redisCommand[1])
    peer := cluster.consistHash.Get(key)
    return cluster.Relay(peer, conn, redisCommand)
}

The Relay method decides whether the target peer is the local node; if so it executes the command locally via the engine, otherwise it obtains a connection from the pool and forwards the command to the remote node:

func (cluster *Cluster) Relay(peer string, conn abstract.Connection, redisCommand [][]byte) protocol.Reply {
    if cluster.self == peer {
        return cluster.engine.Exec(conn, redisCommand)
    }
    client, err := cluster.clientFactory.GetConn(peer)
    if err != nil { logger.Error(err); return protocol.NewGenericErrReply(err.Error()) }
    defer cluster.clientFactory.ReturnConn(peer, client)
    logger.Debugf("command:%q, forward to ip:%s", protocol.NewMultiBulkReply(redisCommand).ToBytes(), peer)
    reply, err := client.Send(redisCommand)
    if err != nil { logger.Error(err); return protocol.NewGenericErrReply(err.Error()) }
    return reply
}

Result

The cluster works for basic SET and GET operations, distributing keys according to the consistent‑hash ring. A screenshot of the running cluster is shown below:

Note that the current implementation stores cluster metadata in a static configuration file; production systems typically use gossip or Raft protocols for dynamic membership, which will be added in a future revision.