Client-Side Sharding Implementation

The Jedis client library, which served as the default Redis driver for Spring Boot prior to version 2.x, offers built-in support for sharded connections. The ShardedJedisPool class enables distribution of keys across multiple Redis instances.

public class RedisShardingDemo {
    public static void main(String[] args) {
        JedisPoolConfig config = new JedisPoolConfig();
        
        JedisShardInfo primaryNode = new JedisShardInfo("localhost", 6379);
        JedisShardInfo secondaryNode = new JedisShardInfo("192.168.1.100", 6379);
        
        List<JedisShardInfo> clusterNodes = Arrays.asList(primaryNode, secondaryNode);
        ShardedJedisPool connectionPool = new ShardedJedisPool(config, clusterNodes);
        
        try (ShardedJedis client = connectionPool.getResource()) {
            for (int idx = 0; idx < 100; idx++) {
                client.set("key_" + idx, String.valueOf(idx));
            }
            for (int idx = 0; idx < 100; idx++) {
                System.out.println(client.get("key_" + idx));
            }
        }
    }
}

After executing the above test, checking DBSIZE on each instance reveals an uneven distribution, such as 44 keys on one server and 56 on another. The distribution is determined by the underlying hashing algorithm.

Hash-Based Distribution

A straightforward approach uses hash-modulo: hash(key) % N, where N represents the number of nodes. While simple, this static sharding rule requires massive data redistribution whenever nodes are added or removed. To address this limitation, consistent hashing was introduced.

Consistent Hashing Algorithm

Consistent hashing organizes the entire hash space into a virtual ring. The hash space ranges from 0 to 2^32-1, forming a circle where these values overlap. When distributing nodes, each server's IP or name is hashed and placed on this ring. For data storage or retrieval, the key is hashed, and the system locates the first node encountered when moving clockwise from that hash position.

This design minimizes disruption during node changes. Adding a new node only affects data that would map to that node's position on the ring, and removing a node only impacts the segment between it and its predecessor. However, with few nodes, data distribution can become uneven. Virtual nodes solve this by mapping multiple logical nodes to each physical server, creating a more balanced distribution.

Implementation in Jedis

Jedis implements consistent hashing using a TreeMap (Red-Black tree) to store node references. The initialization process creates 160 virtual nodes per physical node:

private void initialize(List<S> shardConfigs) {
    nodeRing = new TreeMap<>();
    
    for (int nodeIdx = 0; nodeIdx < shardConfigs.size(); nodeIdx++) {
        S config = shardConfigs.get(nodeIdx);
        int weight = config.getWeight();
        
        for (int vnodeIdx = 0; vnodeIdx < 160 * weight; vnodeIdx++) {
            String nodeKey = config.getName() != null 
                ? config.getName() + "*" + weight + vnodeIdx
                : "SHARD-" + nodeIdx + "-NODE-" + vnodeIdx;
            nodeRing.put(hashAlgorithm.hash(nodeKey), config);
        }
        connectionMap.put(config, config.createResource());
    }
}

When accessing data, the client computes the key's hash and locates the appropriate node:

public S locateNode(byte[] key) {
    SortedMap<Long, S> tailMap = nodeRing.tailMap(hashAlgorithm.hash(key));
    if (tailMap.isEmpty()) {
        return nodeRing.get(nodeRing.firstKey());
    }
    return tailMap.get(tailMap.firstKey());
}

Client-side sharding offers simplicity and flexibility without external dependencies, but it cannot dynamically adjust to topology changes, and each client must maintain identical routing logic.

Proxy-Based Architectures

Proxy solutions extract sharding logic into an intermediary layer. Notable implementations include Twemproxy (developed by Twitter) and Codis (created by豌豆荚).

Twemproxy

Twemproxy provides stability and high availability but has limitations: it requires external components (LVS/HAProxy + Keepalived) for automatic failover and needs configuration changes for scaling operations.

Codis

Codis, written in Go, operates similarly to database middleware like MyCat. It partitions keys into 1024 slots (by default), with each slot mapped to a Redis server group. Codis uses CRC32 hashing followed by modulo to determine slot assignment. Slot mappings are synchronized across Codis proxies via ZooKeeper or etcd.

Redis Cluster Architecture

Introduced in Redis 3.0, Redis Cluster provides native distributed capabilities with high availability. Unlike Codis, it operates without a central coordinator—clients can connect to any node in the cluster.

Data Distribution Model

Redis Cluster employs a virtual slot mechanism with 16,384 slots distributed across master nodes. Each key is assigned a slot via CRC16(key) % 16384. Each master maintains a bitmap indicating which slots it owns.

To ensure related keys reside on the same node, hash tags can be used. Only the portion within curly braces is considered for slot calculation:

127.0.0.1:7293> SET user{2673}:profile "data"
OK
127.0.0.1:7293> SET user{2673}:finance "info"
OK

Client Redirection

When a client accesses the wrong node, the server responds with a MOVED error specifying the correct host and port:

127.0.0.1:7291> GET mykey
(error) MOVED 13724 127.0.0.1:7293

Smart clients like Jedis cache slot-to-node mappings locally to minimize redirection overhead.

Cluster Management Commands

Data Migration

When adding nodes, slots must be reassigned and data migrated. The resharding command facilitates this:

redis-cli --cluster add-node 127.0.0.1:7291 127.0.0.1:7297
redis-cli --cluster reshard 127.0.0.1:7291

Automatic Failover

When a master fails, its slaves initiate an election:

1. Slave detects master's FAIL state
2. Slave increments currentEpoch and broadcasts FAILOVER_AUTH_REQUEST
3. Masters respond with FAILOVER_AUTH_ACK if the request is valid
4. Slave collecting majority of ACKs becomes new master
5. New master broadcasts PONG to notify cluster

Redis Cluster integrates replication and monitoring capabilities similar to Redis Sentinel, providing both data distribution and high availability in a decentralized architecture that can scale to approximately 1,000 nodes.