Twemproxy键分布逻辑及分片查询方法咨询

Great question! Let's break down how Twemproxy handles key sharding, plus share some code/libraries you can use to replicate its logic with ketama distribution and fnv1a_64 hashing.

Twemproxy uses a two-step process to map keys to backend shards:

Step 1: Hash the Key #

First, it applies a configured hash function (like your specified fnv1a_64) to the input key, generating a 64-bit integer hash. This hash serves as the unique identifier for the key in the sharding system.

Step 2: Map Hash to Shard via Ketama Distribution #

For ketama (consistent hashing) distribution—your chosen method—Twemproxy works like this:

• It creates multiple virtual nodes (default: 160 per server) for each backend server. Each virtual node gets a hash position on a circular "hash ring".
• The key's hash is placed on this ring. Twemproxy then finds the first virtual node whose hash is greater than or equal to the key's hash (traversing clockwise around the ring).
• The real backend server associated with that virtual node is the shard the key belongs to.

This approach minimizes key re-sharding when servers are added/removed, which is critical for avoiding mass cache invalidation.

If you need to independently calculate which shard a key belongs to (without relying on Twemproxy itself), here are practical options:

Python: Custom Implementation #

Since the logic is straightforward, you can build a lightweight version yourself that matches Twemproxy's behavior:

First, implement the fnv1a_64 hash function:

def fnv1a_64(key: str) -> int:
    FNV_OFFSET_BASIS = 14695981039346656037
    FNV_PRIME = 1099511628211
    hash_val = FNV_OFFSET_BASIS
    for byte in key.encode('utf-8'):
        hash_val ^= byte
        hash_val *= FNV_PRIME
        # Keep the value constrained to 64 bits
        hash_val &= 0xFFFFFFFFFFFFFFFF
    return hash_val

Then build the ketama sharder:

class KetamaSharder:
    def __init__(self, servers: list, virtual_nodes_per_server: int = 160):
        self.servers = servers
        self.virtual_node_map = {}
        self.sorted_virtual_hashes = []

        # Populate virtual nodes for each server
        for server in servers:
            for idx in range(virtual_nodes_per_server):
                virtual_key = f"{server}:{idx}"
                hash_val = fnv1a_64(virtual_key)
                self.virtual_node_map[hash_val] = server
                self.sorted_virtual_hashes.append(hash_val)
        
        # Sort hashes for efficient binary search
        self.sorted_virtual_hashes.sort()

    def get_shard(self, key: str) -> str:
        key_hash = fnv1a_64(key)
        # Find the first virtual node hash >= key hash
        left, right = 0, len(self.sorted_virtual_hashes)
        while left < right:
            mid = (left + right) // 2
            if self.sorted_virtual_hashes[mid] >= key_hash:
                right = mid
            else:
                left = mid + 1
        # Wrap around to the start if we reach the end of the ring
        if left == len(self.sorted_virtual_hashes):
            left = 0
        return self.virtual_node_map[self.sorted_virtual_hashes[left]]

Example Usage #

# Define your backend servers
servers = ["redis-server-01:6379", "redis-server-02:6379", "redis-server-03:6379"]

# Initialize the sharder
sharder = KetamaSharder(servers)

# Look up shard for a key
target_key = "user_profile:12345"
assigned_shard = sharder.get_shard(target_key)
print(f"Key '{target_key}' maps to shard: {assigned_shard}")

Go: Use a Mature Library #

For Go, the serialx/hashring library natively supports ketama distribution and fnv1a_64 hashing:

import "github.com/serialx/hashring"

func main() {
    // Initialize the ring with your servers and specify fnv1a_64
    ring := hashring.NewWithHashFunc(
        []string{"redis-server-01:6379", "redis-server-02:6379"},
        hashring.Fnv1a64,
    )

    // Get the shard for a key
    server, err := ring.GetNode("user_profile:12345")
    if err != nil {
        panic(err)
    }
    println("Assigned shard:", server)
}

Java: Combine Guava Hashing with Custom Ring #

In Java, use com.google.common.hash.Hashing for fnv1a_64, then implement your own ketama ring:

import com.google.common.hash.Hashing;
import java.nio.charset.StandardCharsets;
import java.util.SortedMap;
import java.util.TreeMap;

public class KetamaSharder {
    private final SortedMap<Long, String> virtualNodes = new TreeMap<>();
    private static final int VIRTUAL_NODES_PER_SERVER = 160;

    public KetamaSharder(String[] servers) {
        for (String server : servers) {
            for (int i = 0; i < VIRTUAL_NODES_PER_SERVER; i++) {
                String virtualKey = server + ":" + i;
                long hash = Hashing.fnv1a_64().hashString(virtualKey, StandardCharsets.UTF_8).asLong();
                virtualNodes.put(hash, server);
            }
        }
    }

    public String getShard(String key) {
        long keyHash = Hashing.fnv1a_64().hashString(key, StandardCharsets.UTF_8).asLong();
        SortedMap<Long, String> tailMap = virtualNodes.tailMap(keyHash);
        if (tailMap.isEmpty()) {
            return virtualNodes.get(virtualNodes.firstKey());
        }
        return tailMap.get(tailMap.firstKey());
    }

    public static void main(String[] args) {
        KetamaSharder sharder = new KetamaSharder(new String[]{"redis-01:6379", "redis-02:6379"});
        System.out.println("Assigned shard: " + sharder.getShard("user_profile:12345"));
    }
}

All these implementations align with Twemproxy's default behavior for ketama + fnv1a_64, so you'll get consistent shard assignments.

内容的提问来源于stack exchange，提问作者Archit Singla