# 朴素哈希：hash(key) % N
def get_node(key, num_nodes):
    return hash(key) % num_nodes

# 3 个节点时:
# key1 → hash(key1) % 3 = 1 → Node 2
# key2 → hash(key2) % 3 = 0 → Node 1
# key3 → hash(key3) % 3 = 2 → Node 3

# 问题：增加 1 个节点（3 → 4）后:
# key1 → hash(key1) % 4 = 3 → Node 4  ← 命中节点改变！
# key2 → hash(key2) % 4 = 0 → Node 1
# key3 → hash(key3) % 4 = 2 → Node 3

import hashlib
import bisect

class ConsistentHash:
    """一致性哈希实现（带虚拟节点）"""

    def __init__(self, nodes=None, vnodes=150):
        self.vnodes = vnodes
        self.ring = []        # 排序的哈希值列表
        self.ring_map = {}    # 哈希值 → 节点
        self.nodes = set()

        if nodes:
            for node in nodes:
                self.add_node(node)

    def _hash(self, key):
        """计算哈希值"""
        h = hashlib.md5(key.encode('utf-8')).hexdigest()
        return int(h, 16)

    def add_node(self, node):
        """添加节点"""
        self.nodes.add(node)
        for i in range(self.vnodes):
            vnode_key = f"{node}:vnode{i}"
            h = self._hash(vnode_key)
            bisect.insort(self.ring, h)
            self.ring_map[h] = node

    def remove_node(self, node):
        """移除节点"""
        self.nodes.discard(node)
        for i in range(self.vnodes):
            vnode_key = f"{node}:vnode{i}"
            h = self._hash(vnode_key)
            self.ring.remove(h)
            del self.ring_map[h]

    def get_node(self, key):
        """获取 Key 对应的节点"""
        if not self.ring:
            return None
        h = self._hash(key)
        idx = bisect.bisect_right(self.ring, h)
        if idx == len(self.ring):
            idx = 0
        return self.ring_map[self.ring[idx]]


# 使用示例
ch = ConsistentHash(
    nodes=["mc1:11211", "mc2:11211", "mc3:11211"],
    vnodes=150
)

# 路由 Key
print(ch.get_node("user:1001"))    # mc2:11211
print(ch.get_node("user:1002"))    # mc1:11211
print(ch.get_node("session:abc"))  # mc3:11211

# 添加新节点
ch.add_node("mc4:11211")
print(ch.get_node("user:1001"))    # 大概率不变

# 验证分布均匀性
from collections import Counter
dist = Counter(ch.get_node(f"key:{i}") for i in range(10000))
for node, count in sorted(dist.items()):
    print(f"{node}: {count} ({count/100:.1f}%)")

package consistent

import (
    "hash/crc32"
    "sort"
    "strconv"
    "sync"
)

type ConsistentHash struct {
    mu       sync.RWMutex
    ring     []uint32
    ringMap  map[uint32]string
    nodes    map[string]bool
    vnodes   int
}

func New(vnodes int) *ConsistentHash {
    return &ConsistentHash{
        ring:    make([]uint32, 0),
        ringMap: make(map[uint32]string),
        nodes:   make(map[string]bool),
        vnodes:  vnodes,
    }
}

func (ch *ConsistentHash) hash(key string) uint32 {
    return crc32.ChecksumIEEE([]byte(key))
}

func (ch *ConsistentHash) AddNode(node string) {
    ch.mu.Lock()
    defer ch.mu.Unlock()

    ch.nodes[node] = true
    for i := 0; i < ch.vnodes; i++ {
        h := ch.hash(node + ":vnode" + strconv.Itoa(i))
        ch.ring = append(ch.ring, h)
        ch.ringMap[h] = node
    }
    sort.Slice(ch.ring, func(i, j int) bool {
        return ch.ring[i] < ch.ring[j]
    })
}

func (ch *ConsistentHash) RemoveNode(node string) {
    ch.mu.Lock()
    defer ch.mu.Unlock()

    delete(ch.nodes, node)
    newRing := make([]uint32, 0)
    for _, h := range ch.ring {
        if ch.ringMap[h] != node {
            newRing = append(newRing, h)
        } else {
            delete(ch.ringMap, h)
        }
    }
    ch.ring = newRing
}

func (ch *ConsistentHash) GetNode(key string) string {
    ch.mu.RLock()
    defer ch.mu.RUnlock()

    if len(ch.ring) == 0 {
        return ""
    }
    h := ch.hash(key)
    idx := sort.Search(len(ch.ring), func(i int) bool {
        return ch.ring[i] >= h
    })
    if idx >= len(ch.ring) {
        idx = 0
    }
    return ch.ringMap[ch.ring[idx]]
}

# libmemcached 使用 Ketama 一致性哈希算法
# 配置字符串中指定:
# --SERVER=mc1:11211 --SERVER=mc2:11211 --SERVER=mc3:11211 --HASH=WHEEL

<?php
$mc = new Memcached();

// 设置一致性哈希算法
$mc->setOption(Memcached::OPT_LIBKETAMA_COMPATIBLE, true);

// 添加服务器
$mc->addServers([
    ['mc1', 11211, 100],  // [host, port, weight]
    ['mc2', 11211, 100],
    ['mc3', 11211, 100],
]);

// 自动使用一致性哈希路由
$mc->set('user:1001', $userData, 3600);
$mc->get('user:1001');  // 自动路由到正确的节点

import net.spy.memcached.MemcachedClient;
import net.spy.memcached.ConnectionFactoryBuilder;

// 使用 Ketama 一致性哈希
ConnectionFactoryBuilder builder = new ConnectionFactoryBuilder();
builder.setHashAlg(DefaultHashAlgorithm.KETAMA_HASH);
builder.setLocatorType(ConnectionFactoryBuilder.LocatorType.CONSISTENT);

MemcachedClient mc = new MemcachedClient(
    builder.build(),
    AddrUtil.getAddresses("mc1:11211 mc2:11211 mc3:11211")
);

import "github.com/bradfitz/gomemcache/memcache"

// gomemcache 默认使用一致性哈希
mc := memcache.New("mc1:11211", "mc2:11211", "mc3:11211")
// 自动使用 fnv32a 一致性哈希路由

# 好的做法：Key 有明确前缀
"user:1001"      # 可控的哈希分布
"session:abc123" # 不同前缀分散到不同节点

# 不好的做法：Key 有相同前缀
"cache_1", "cache_2", "cache_3"  # 可能集中在同一节点

class ResilientMemcached:
    def __init__(self, servers):
        self.healthy = set(servers)
        self.all_servers = servers
        self.mc = memcache.Client(servers)
        self.fail_counts = {}

    def get(self, key):
        try:
            value = self.mc.get(key)
            self.fail_counts[key] = 0
            return value
        except Exception as e:
            self.fail_counts[key] = self.fail_counts.get(key, 0) + 1
            if self.fail_counts[key] >= 3:
                # 标记节点不健康，移除
                self._mark_unhealthy(key)
            return None

    def _mark_unhealthy(self, key):
        # 更新一致性哈希环，临时移除故障节点
        pass