前言

一致性 Hash 算法在很多领域都有应用，比如缓存领域的 MemCache 、 Redis 等，负载均衡的 Nginx ， RCP 领域的 Dubbo 。今天手撸一个简单的一致性Hash算法，相对于各大开源组件来说，这里主要为了说明算法实现。

友情提示：如果你还没听说过一致性 Hash 算法，建议你先自行搜索，了解算法原理和思路。

代码实现

计算 MD5

    private byte[] computeMd5(String key) {
        MessageDigest md5Digest;
        try {
            md5Digest = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("MD5 not supported", e);
        }
        md5Digest.update(key.getBytes());
        return md5Digest.digest();
    }

Ketama Hash 算法实现

    private int getHashCode(String origin) {
        byte[] bKey = computeMd5(origin);
        long rv = ((long) (bKey[3] & 0xFF)<< 24)
                | ((long) (bKey[2] & 0xFF)<< 16)
                | ((long) (bKey[1] & 0xFF)<< 8)
                | (bKey[0] & 0xFF);
        return (int) (rv & 0xffffffffL);
    }

一致性 Hash 接口定义

package org.xueliang.algorithm.loadbalance;

import java.util.List;

/**
 * @author xueliang
 * @since 2020-03-26 16:48
 */
public interface LoadBalance {

    ServerNode select(List<ServerNode> serverNodes, Invocation invocation);
}

服务器节点定义

package org.xueliang.algorithm.loadbalance;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;

/**
 * @author xueliang
 * @since 2020-03-26 16:50
 */
@Getter
@Setter
@NoArgsConstructor
@AllArgsConstructor
public class ServerNode {

    private String hostname;
}

一致性 Hash 接口定义

构建一致性 Hash 环

    private TreeMap<Long, ServerNode> buildVirtualServerNodes(List<ServerNode> serverNodes) {
        TreeMap<Long, ServerNode> virtualServerNodes = new TreeMap<>();
        serverNodes.forEach(serverNode -> {
            IntStream.range(0, VIRTUAL_NODE_SIZE).forEach(i -> {
                virtualServerNodes.put((long) getHashCode(serverNode.getHostname() + VIRTUAL_NODE_SUFFIX + i), serverNode);
            });
        });
        return virtualServerNodes;
    }

在 Hash 环上定位处理请求的服务器节点

    private ServerNode locate(TreeMap<Long, ServerNode> virtualServerNodes, Invocation invocation) {
        Long hash = (long) getHashCode(invocation.getHashKey());
        Map.Entry<Long, ServerNode> entry = virtualServerNodes.ceilingEntry(hash);
        if (entry == null) {
            entry = virtualServerNodes.firstEntry();
        }
        return entry.getValue();
    }

处理逻辑主流程

    @Override
    public ServerNode select(List<ServerNode> serverNodes, Invocation invocation) {
        TreeMap<Long, ServerNode> virtualServerNodes = buildVirtualServerNodes(serverNodes);
        return locate(virtualServerNodes, invocation);
    }

相关阅读

负载均衡算法之加权轮询算法实现