您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

一致性哈希算法的介绍与实现

时间:2020-07-07 10:35:46  来源:  作者:

哈希函数,想必大家都不陌生。通过哈希函数我们可以将数据映射成一个数字(哈希值),然后可用于将数据打乱。例如,在HashMap中则是通过哈希函数使得每个桶中的数据尽量均匀。那一致性哈希又是什么?它是用于解决什么问题?本文将从普通的哈希函数说起,看看普通哈希函数存在的问题,然后再看一致性哈希是如何解决,一步步进行分析,并结合代码实现来讲解。

首先,设定这样一个场景,我们每天有1千万条业务数据,还有100个节点可用于存放数据。那我们希望能将数据尽量均匀地存放在这100个节点上,这时候哈希函数就能派上用场了,下面我们按一天的数据量来说明。

首先,准备下需要存放的数据,以及节点的地址。为了简单,这里的数据为随机整型数字,节点的地址为从“192.168.1.0”开始递增。

private static int dataNum = 10000000;
private static int nodeNum = 100;

private static List<Integer> datas = initData(dataNum);

private static List<String> nodes = initNode(nodeNum);

private static List<Integer> initData(int n) {
    List<Integer> datas = new ArrayList<>();
    Random random = new Random();
    for (int i = 0; i < n; i++) {
        datas.add(random.nextInt());
    }
    return datas;
}

private static List<String> initNode(int n) {
    List<String> nodes = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        nodes.add(String.format("192.168.1.%d", i));
    }
    return nodes;
}

接下来,我们看下通过“哈希+取模”得到数据相应的节点地址。这里的hash方法使用Guava提供的哈希方法来实现,后文也将继续使用该hash方法。

public static String normalHash(Integer data, List<String> nodes) {
    int hash = hash(data);
    int nodeIndex = hash % nodes.size();
    return nodes.get(nodeIndex);
}

private static int hash(Object object) {
    HashFunction hashFunction = Hashing.murmur3_32();
    if (object instanceof Integer) {
        return Math.abs(hashFunction.hashInt((Integer) object).asInt());
    } else if (object instanceof String) {
        return Math.abs(hashFunction.hashUnencodedChars((String) object).asInt());
    }
    return -1;
}

最后,我们对数据的分布情况进行统计,观察分布是否均匀,这里通过标准差来观察。

public static void normalHashMain() {
    Map<String, Integer> nodeCount = new HashMap<>();
    for (Integer data : datas) {
        String node = normalHash(data, nodes);

        if (nodeCount.containsKey(node)) {
            nodeCount.put(node, nodeCount.get(node) + 1);
        } else {
            nodeCount.put(node, 1);
        }
    }

    analyze(nodeCount, dataNum, nodeNum);
}

public static void analyze(Map<String, Integer> nodeCount, int dataNum, int nodeNum) {
    double average = (double) dataNum / nodeNum;

    IntSummaryStatistics s1
        = nodeCount.values().stream().mapToInt(Integer::intValue).summaryStatistics();
    int max = s1.getMax();
    int min = s1.getMin();
    int range = max - min;
    double standardDeviation
        = nodeCount.values().stream().mapToDouble(n -> Math.abs(n - average)).summaryStatistics().getAverage();

    System.out.println(String.format("平均值:%.2f", average));
    System.out.println(String.format("最大值:%d,(%.2f%%)", max, 100.0 * max / average));
    System.out.println(String.format("最小值:%d,(%.2f%%)", min, 100.0 * min / average));
    System.out.println(String.format("极差:%d,(%.2f%%)", range, 100.0 * range / average));
    System.out.println(String.format("标准差:%.2f,(%.2f%%)", standardDeviation, 100.0 * standardDeviation / average));
}

/**
平均值:100000.00
最大值:100818,(100.82%)
最小值:99252,(99.25%)
极差:1566,(1.57%)
标准差:240.08,(0.24%)
**/

其中标准差较小,说明分布较为均匀,那我们的需求达到了。

接着,随着业务的发展,你发现100个节点不够用了,我们希望再增加10个节点,来提高系统性能。而我们还将继续采用之前的方法来分布数据。这时候就出现了一个新的问题,我们是通过“哈希+取模”来决定数据的相应节点,原来数据的哈希值是不会改变的,可是取模的时候节点的数量发生了变化,这将导致的结果就是原来的数据存在A节点,现在可能需要迁移到B节点,也就是数据迁移问题。下面我们来看下有多少数据将发生迁移。

private static int newNodeNum = 11;

private static List<String> newNodes = initNode(newNodeNum);

public static void normalHashMigrateMain() {
    int migrateCount = 0;
    for (Integer data : datas) {
        String node = normalHash(data, nodes);
        String newNode = normalHash(data, newNodes);
        if (!node.equals(newNode)) {
            migrateCount++;
        }
    }
    System.out.println(String.format("数据迁移量:%d(%.2f%%)", migrateCount, migrateCount * 100.0 / datas.size()));
}

/**
数据迁移量:9091127(90.91%)
**/

有90%多的数据都需要进行迁移,这是几乎全部的量了。普通哈希的问题暴露出来了,当将节点由100扩展为110时,会存在大量的迁移工作。在1997年MIT提出了一致性哈希算法,用于解决普通哈希的这一问题。

我们再分析下,假设hash值为10000,nodeNum为100,那按照index = hash % nodeNum得到的结果是0,而将100变为110时,取模的结果将改变为100。如果我们将取模的除数增大至大于hash值,那hash值取模的结果将仍是其本身。也就是说,只要除数保证大于hash值,那取模的结果将不会改变。这里的hash值是int,4个字节,那我们把除数固定为2^32-1,index = hash % (2^32-1)。取模的结果也将固定在0到2^32-1中,可将其构成一个环,如下所示。

一致性哈希算法的介绍与实现

 

取模的结果范围

现在的除数是2^32-1,hash值为10000,取模的结果为10000,而我们有100个节点,该映射到哪个节点上呢?我们可以先将节点通过哈希映射到环上。为了绘图方便,我们以3个节点为例,如下图所示:

一致性哈希算法的介绍与实现

 

一致性哈希环

10000落到环上后,如果没有对应的节点,则按顺时针方向找到下一个节点,便为hash值对应的节点。下面我们用JAVA的TreeMap来存节点的hash值,利用TreeMap的tailMap寻找节点。

我们使用和之前同样的方法,测试下当节点由100变为110时,数据需要迁移的情况,如下所示:

public static void consistHashMigrateMain() {
    int migrateCount = 0;
    SortedMap<Integer, String> circle = new TreeMap<>();
    for (String node : nodes) {
        circle.put(hash(node), node);
    }
    SortedMap<Integer, String> newCircle = new TreeMap<>();
    for (String node : newNodes) {
        newCircle.put(hash(node), node);
    }

    for (Integer data : datas) {
        String node = consistHash(data, circle);
        String newNode = consistHash(data, newCircle);
        if (!node.equals(newNode)) {
            migrateCount++;
        }
    }
    System.out.println(String.format("数据迁移量:%d(%.2f%%)", migrateCount, migrateCount * 100.0 / datas.size()));
}

public static String consistHash(Integer data, SortedMap<Integer, String> circle) {
    int hash = hash(data);
    // 从环中取大于等于hash值的部分
    SortedMap<Integer, String> subCircle = circle.tailMap(hash);
    int index;
    // 如果在大于等于hash值的部分没有节点,则取环开始的第一个节点
    if (subCircle.isEmpty()) {
        index = circle.firstKey();
    } else {
        index = subCircle.firstKey();
    }
    return circle.get(index);
}

/**
数据迁移量:817678(8.18%)
**/

可见需要迁移的数据由90%降到了8%,效果十分可观。那我们再看下数据的分布情况,是否仍然均匀:

/**
平均值:100000.00
最大值:589675,(589.68%)
最小值:227,(0.23%)
极差:589448,(589.45%)
标准差:77421.44,(77.42%)
**/

77%的标准差,一个字,崩!这是为啥?我们原本设想的是节点映射到环上时,能将环均匀划分,所以当数据映射到环上时,也将被均匀分布到节点上。而实际情况,由于节点地址相似,映射到环上的位置也将相近,所以造成分布的不均匀,如下图所示:

一致性哈希算法的介绍与实现

 

分布不均

由于A、B、C的地址相似,例如:

A: 192.168.1.0
B: 192.168.1.1
C: 192.168.1.2

所以映射的位置相近,那我们可以复制几份A、B、C,并且通过改变key,让节点能更均匀的划分环。比如我们在地址后面追加 “-index” 的序号,例如:

A0: 192.168.1.0-0
B0: 192.168.1.1-0
C0: 192.168.1.2-0

A1: 192.168.1.0-1
B1: 192.168.1.1-1
C1: 192.168.1.2-1

虽然A0、B0、C0会相距较近,但是和A1、B1、C1的key具有差别,将能够成功分开,这也正是虚拟节点的作用。达到的效果如下:

一致性哈希算法的介绍与实现

 

虚拟节点

下面我们通过代码验证下实际效果:

private static int vNodeNum = 100;

public static void consistHashVirtualNodeMain() {
    Map<String, Integer> nodeCount = new HashMap<>();
    SortedMap<Integer, String> circle = new TreeMap<>();
    for (String node : nodes) {
        for (int i = 0; i < vNodeNum; i++) {
            circle.put(hash(node + "-" + i), node);
        }
    }

    for (Integer data : datas) {
        String node = consistHashVirtualNode(data, circle);
        if (nodeCount.containsKey(node)) {
            nodeCount.put(node, nodeCount.get(node) + 1);
        } else {
            nodeCount.put(node, 1);
        }
    }

    analyze(nodeCount, dataNum, nodeNum);
}

/**
平均值:100000.00
最大值:122931,(122.93%)
最小值:74434,(74.43%)
极差:48497,(48.50%)
标准差:7475.08,(7.48%)
**/

可看到标准差已经由77%降到7%,效果显著。再多做几组实验,标准差随着虚拟节点数的变化如下:

一致性哈希算法的介绍与实现

 

结果中,随着虚拟节点数的增加,标准差逐步下降。可见虚拟节点能达到均匀分布数据的效果。

一句话总结下:

一致性哈希可用于解决哈希函数在扩容时的数据迁移的问题,而一致性哈希的实现中需要借助虚拟节点来均匀分布数据。



Tags:一致性哈希算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
哈希 Hash 算法介绍哈希算法也叫散列算法, 不过英文单词都是 Hash, 简单一句话概括, 就是可以把任意长度的输入信息通过算法变换成固定长度的输出信息, 输出信息也就是哈希...【详细内容】
2021-08-17  Tags: 一致性哈希算法  点击:(72)  评论:(0)  加入收藏
哈希函数,想必大家都不陌生。通过哈希函数我们可以将数据映射成一个数字(哈希值),然后可用于将数据打乱。例如,在HashMap中则是通过哈希函数使得每个桶中的数据尽量均匀。那一致...【详细内容】
2020-07-07  Tags: 一致性哈希算法  点击:(71)  评论:(0)  加入收藏
一致性哈希算法普通的哈希算法使用取余操作:hash(o) mod n,其中 n 代表机器的数量。如果在集群中新增加一个节点时,计算公式会变为:hash(o) mod (n+1);在集群中删除一个机器时,计...【详细内容】
2019-10-22  Tags: 一致性哈希算法  点击:(102)  评论:(0)  加入收藏
话说前几天有一次,某大厂的二面。然后呢,烟哥那天刚好有事,所以去不了。于是就约了一场视频面试了!...【详细内容】
2019-09-03  Tags: 一致性哈希算法  点击:(186)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条