您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

一致性哈希算法 Java 手寫實現：從基本環到虛擬節點完整代碼詳解

編輯：Java 綜合教學

一致性哈希算法 Java 手寫實現：從基本環到虛擬節點完整代碼詳解

一致性哈希解決分布式緩存（Memcached、Redis Cluster）節點增減時的數據遷移問題。本文提供兩版實現：無虛擬節點版與虛擬節點版，核心數據結構採用 List 模擬（生產環境用紅黑樹/TreeMap）。

應用場景

Memcached 客戶端分片路由
Jedis/Redisson 分片機制
分布式負載均衡、分庫分表路由

版本一：基本一致性哈希環（無虛擬節點）

核心類設計

// 真實節點
public class ServerNode {
    private String serverName; // "ip:port"
    private long serverHash;
    // getter/setter + hashCode/equals 僅比較 serverName 便於刪除
}

// 比較器：按哈希值升序
public class ServerComparator implements Comparator {
    public int compare(ServerNode n1, ServerNode n2) {
        return Long.compare(n1.getServerHash(), n2.getServerHash());
    }
}

// 一致性哈希主類
public class ConsistentHash {
    private List servers = new ArrayList<>();
    private CRC32 crc32 = new CRC32(); // 亦可用 MD5

    public long hash(String str) {
        crc32.reset();
        crc32.update(str.getBytes());
        return crc32.getValue();
    }

    public void addServer(String serverName) {
        ServerNode node = new ServerNode();
        node.setServerName(serverName);
        node.setServerHash(hash(serverName));
        servers.add(node);
        Collections.sort(servers, new ServerComparator());
    }

    public void deleteServer(String serverName) {
        ServerNode node = new ServerNode();
        node.setServerName(serverName);
        servers.remove(node); // 依賴 equals
    }

    public ServerNode getServer(String cacheKey) {
        long keyHash = hash(cacheKey);
        for (ServerNode node : servers) {
            if (keyHash <= node.getServerHash()) return node;
        }
        return servers.get(0); // 環首節點
    }
}

版本二：引入虛擬節點（解決數據傾斜）

為什麼需要虛擬節點？

物理節點少時，哈希環分佈不均 → 負載傾斜
節點下線，壓力全轉移給下一節點 → 雪崩風險
新增節點僅分擔下一節點壓力 → 擴容效果有限

將每個物理節點映射為 virtualCount（建議 100-200）個虛擬節點，名稱格式 ip:port-index。

虛擬節點實現

public class VirtualServerNode {
    private String serverName; // 物理節點名
    private long virtualServerHash;
    // getter/setter
}

public class ConsistentHashWithVirtualNode {
    private List virtualServers = new ArrayList<>();
    private static final int VIRTUAL_COUNT = 8; // 生產建議 150
    private CRC32 crc32 = new CRC32();

    public long hash(String str) { /* 同前 */ }

    public void addServer(String serverName) {
        for (int i = 0; i < VIRTUAL_COUNT; i++) {
            VirtualServerNode node = new VirtualServerNode();
            node.setServerName(serverName);
            node.setVirtualServerHash(hash(serverName + "-" + i));
            virtualServers.add(node);
        }
        Collections.sort(virtualServers, new VirtualServerComparator());
    }

    public void deleteServer(String serverName) {
        // 必須用索引遍歷刪除，避免 ConcurrentModificationException
        for (int i = 0; i < virtualServers.size(); i++) {
            if (virtualServers.get(i).getServerName().equals(serverName)) {
                virtualServers.remove(i--);
            }
        }
    }

    public VirtualServerNode getServer(String cacheKey) { /* 同基本版 */ }
}

測試驗證

public static void main(String[] args) {
    ConsistentHashWithVirtualNode ch = new ConsistentHashWithVirtualNode();
    ch.addServer("127.0.0.1:11211");
    ch.addServer("127.0.0.1:11212");
    ch.addServer("127.0.0.2:11211");
    ch.addServer("127.0.0.2:11212");

    System.out.println("hello -> " + ch.getServer("hello").getServerName());
    System.out.println("name  -> " + ch.getServer("name").getServerName());

    ch.deleteServer("127.0.0.1:11212");
    System.out.println("刪除節點後 hello -> " + ch.getServer("hello").getServerName());
}