一致性哈希算法与实现

关注
发布于: 2020 年 07 月 08 日
背景随着业务系统越来越大，我们需要更高并发、更高存储的缓存，比如如Redis，但是：
单台Redis性能、容量不足以满足需求时，怎么使用Redis集群来进行分布式缓存?
写入数据时，如何决定将内容缓存在集群中的哪一台Redis服务器上，并且查询时能找到这台机器?
随机分配不合理，想要查询的时候我们自己也不知道在哪，只能通过轮询来获取数据。
hash取模假如我有3个缓存节点A\B\C，根据对象的 hashCode(object) % 3  缓存到对应的节点。当有一天扩容1台机器后，我们的缓存集群变为了4个，数据变为了根据 hashCode(object) % 4 放入对应节点。这样会出现，绝大部分的缓存都会无法命中。
一致性hash 而consistent hashing就是来把这种「绝大部分」无法命中 变为 「绝大部分」都能命中。
简单的说，在移除 / 添加一个 cache 时，它能够尽可能小的改变已存在 key 映射关系，尽可能的满足单调性的要求。
下面，本文剩下部分重点来讲讲这个一致性哈希算法。
最小数据失效Hash 算法的一个衡量指标是单调性（ Monotonicity ），定义如下：
﻿
单调性是指如果已经有一些内容通过哈希分派到了相应的缓存节点中，又有新的缓存节点加入到系统中，哈希的结果应能够保证原有已分配的内容可以被映射到新的节点，而不会被映射到旧的缓冲集合中的其他缓冲区。
﻿
容易看到，上面的简单 hash 算法 hashCode(object) % N 难以满足单调性要求。
﻿
上面这话有点绕口，我写个简单demo说明：
原有节点A、B、C：
A - 1, 3, 9
B - 5, 6, 8
C - 2, 4, 7
新增D:
A - 3, 9
B - 5, 8
C - 2, 4
D - 1, 6, 7 
这里不会出现A里面的1、2、9会因为新增节点导致路由到B、C上，B、C也是类似，这样保证最小路由变化度。
﻿
每个程序员，尤其是JAVA程序员，应该都知道Object基类的hashCode函数，hashCode会返回一个  0~2^32-1次方 之间的数字。
想象一下，将此范围映射到一个圆中，其中包含许多对象（1、2、3、4）和缓存节点（A，B，C），这些对象标记在它们哈希到的点上。
﻿
为了找到对象进入哪个缓存节点，我们绕圆顺时针移动直到找到缓存节点。因此，在上图中，我们看到对象1和4属于缓存A，对象2属于缓存B，对象3属于缓存C。请考虑一下如果删除缓存C会发生什么:对象3会归属到缓存A，其他对象映射不变。如果然后在标记的位置添加另一个缓存D，它将获取对象3和4，仅保留属于A的对象1。
﻿
数据分布均衡考量 Hash 算法的另一个指标是平衡性 (Balance)，定义如下：
﻿
平衡性是指哈希的结果能够尽可能平均分布到所有的缓冲节点中，这样可以使得所有的缓冲空间都得到利用。
﻿
而Hash的本质上是随机的，因此缓存之间的对象分布可能不均匀。解决此问题的方法是引入“虚拟节点的概念”。他们是真实缓存节点的副本，因此，无论何时添加缓存，我们都会在圆中为其创建多个“虚拟节点”。
﻿
可以在下图看到效果，该图模拟将10000个对象存储在10个缓存中而产生的。
X轴标识缓存节点的副本数。当它很小时，我们会看到对象在整个缓存中的分布是不平衡的，因为标准差很高。而随着副本数量的增加，对象的分布变得更加平衡（标准差大约为平均值的5%-10%是一个比较好的性能与平衡性的点）。
例子hash环的实现
import static cn.hutool.core.map.MapUtil.isEmpty;
import cn.hutool.core.util.HashUtil;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.stream.IntStream;
import lombok.Data;
import lombok.extern.slf4j.Slf4j;
import org.apache.commons.math3.stat.descriptive.moment.StandardDeviation;
/**
 * 一致性hash环
 */
@Slf4j
@Data
public class ConsistentHash {
    // 虚拟节点
    private SortedMap<Integer, Node> virNodeCircle;
    // 真实节点
    private List<Node> realNodes;
    // 虚拟节点数量
    private int virNodeNum;
    ConsistentHash(List<Node> realNodes, int virNodeNum) {
        this.realNodes = realNodes;
        this.virNodeNum = virNodeNum;
        virNodeCircle = new TreeMap<>();
        realNodes.forEach(node -> addVirNode(node, virNodeNum));
    }
    private static Integer getHash(String str) {
        return HashUtil.fnvHash(str);
    }
    private void addVirNode(Node realNode, int num) {
        IntStream.range(0, num).forEach(
          n -> virNodeCircle.put(getHash(realNode.genKey(n)), realNode)
        );
    }
    Node getRealNodes(String key) {
        SortedMap<Integer, Node> tail = virNodeCircle.tailMap(getHash(key));
        return isEmpty(tail) ? virNodeCircle.get(virNodeCircle.firstKey()) : tail.get(tail.firstKey());
    }
    double standardDeviation() {
        double[] counts = new double[realNodes.size()];
        for (int i = 0; i < realNodes.size(); i++) {
            counts[i] = realNodes.get(i).getDataMap().size();
        }
        StandardDeviation standardDeviation = new StandardDeviation();
        return standardDeviation.evaluate(counts);
    }
}
节点对象
import static cn.hutool.core.map.MapUtil.newHashMap;
import java.util.Map;
import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.extern.slf4j.Slf4j;
@Slf4j
@Data
@Builder
@AllArgsConstructor
@NoArgsConstructor
public class Node {
    private String name;
    private String ip;
    private Map<String, String> dataMap = newHashMap();
    public void putData(String k, String v) {
        if (dataMap == null) {
            dataMap = newHashMap();
        }
        dataMap.put(k, v);
    }
    public String genKey(int virNodeNum) {
        return String.format("%s-%s-%s", this.ip, this.name, virNodeNum);
    }
}
测试代码
import static cn.hutool.core.collection.CollUtil.newHashMap;
import cn.hutool.core.util.RandomUtil;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import lombok.extern.slf4j.Slf4j;
@Slf4j
public class TestClient {
    public static void main(String[] args) {
        IntStream.range(1, 500).filter(i -> i % 20 == 1).boxed().forEach(vn -> buildConsistentHash(10, vn));
    }
    private static void buildConsistentHash(Integer relNodeNum, Integer virNodeNum) {
        final List<Node> readNodes = IntStream.range(0, relNodeNum).boxed()
            .map(i -> Node.builder().name("node" + i).ip("127.0.0." + i).build())
            .collect(Collectors.toList());
        ConsistentHash consistent = new ConsistentHash(readNodes, virNodeNum);
        buildData().forEach((k, v) -> consistent.getRealNodes(k).putData(k, v));
        readNodes.forEach(node -> log.debug("Node:[{}]的数据量为:[{}]", node.getIp(), node.getDataMap().size()));
        log.info("真实节点数:{}, 虚拟节点数:{}, 标准差为:{}",
            consistent.getRealNodes().size(), consistent.getVirNodeNum(), String.format("%.2d", consistent.standardDeviation()));
    }
    private static Map<String, String> buildData() {
        Map<String, String> kvMap = newHashMap();
        for (int i = 0; i < 1000000; i++) {
            kvMap.put(RandomUtil.randomString(3) + i, RandomUtil.randomString(2) + i);
        }
        return kvMap;
    }
}
返回结果
22:01:19.311 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:1, 标准差为:119759.92494987628
22:01:21.593 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:21, 标准差为:24546.188271637344
22:01:25.769 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:41, 标准差为:15725.772830328915
22:01:28.710 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:61, 标准差为:12504.043417142224
22:01:32.325 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:81, 标准差为:10402.254969209534
22:01:38.106 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:101, 标准差为:6649.675113199976
22:01:45.641 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:121, 标准差为:6062.941511987212
22:01:52.819 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:141, 标准差为:6365.190596779749
22:02:04.502 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:161, 标准差为:8059.04356056667
22:02:12.424 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:181, 标准差为:8122.947795528966
22:02:22.636 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:201, 标准差为:8824.542997295162
22:02:37.376 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:221, 标准差为:6410.592380323886
22:02:52.661 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:241, 标准差为:5624.744043559276
22:03:04.003 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:261, 标准差为:4537.978673863998
22:03:18.396 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:281, 标准差为:6434.237812066183
22:03:35.104 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:301, 标准差为:6341.479042340552
22:03:51.777 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:321, 标准差为:5627.906498473083
22:04:07.650 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:341, 标准差为:5843.552458336738
22:04:33.726 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:361, 标准差为:5847.998100014891
22:04:55.400 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:381, 标准差为:6026.846807779707
22:05:17.742 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:401, 标准差为:4410.508839376951
22:05:37.382 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:421, 标准差为:3011.6705589349503
22:05:59.384 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:441, 标准差为:3811.844085653732
22:06:35.480 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:461, 标准差为:3790.606459833747
22:07:01.975 [main] INFO com.gametask.api.hash.ConsistentHashMain - 真实节点数:10, 虚拟节点数:481, 标准差为:4561.7056264320945
﻿
总结虽然一致性hash能很好的解决一部分问题，但是也有不好的地方，就是数据迁移问题。因为所有数据都分散到各个机器上，没有很好的聚合，所以对于数据迁移是有一定困难。
﻿
还有就是使用什么样的hash算法：
第一代：SHA-1（1993），MD5（1992），CRC（1975），Lookup3（2006）
第二代：MurmurHash（2008）
第三代：CityHash， SpookyHash（2011）
在一致性hash方面，推荐：MurmurHash、FNV、Ketama，具体可以百度、Google查找下资料。
其他场景需要具体问题具体分析选择，毕竟我们一致性hash不仅仅使用在缓存，还有一些场景需要从安全性、性能、实现复杂度等来权衡。
﻿
软件设计没有银弹，每一种算法只是解决一种相对应的问题。不要手里拿着锤子，就看什么都是钉子，还是要具体问题具体分析。
发布于: 2020 年 07 月 08 日阅读数: 67
原文链接:【http://xie.infoq.cn/article/3f62a120d1d654e0c08a93a03】。文章转载请联系作者。
俊俊哥

关注
架构是平衡的艺术 2013.06.01 加入
还未添加个人简介
发布
暂无评论
创作场景

一致性哈希算法与实现

背景

随机分配

hash取模

一致性hash

最小数据失效

数据分布均衡

例子

总结

俊俊哥

评论
