Question

一致性hash算法，采用哪种算法实现比较好，比如MD5，CRC32，或者其它

Answer 1

环割法（一致性 hash）环割法的原理如下：

1. 初始化的时候生成分片数量 X × 环割数量 N 的固定方式编号的字符串，例如 SHARD-1-NODE-1，并计算所有 X×N 个字符串的所有 hash 值。

2. 将所有计算出来的 hash 值放到一个排序的 Map 中，并将其中的所有元素进行排序。

3. 输入字符串的时候计算输入字符串的 hash 值，查看 hash 值介于哪两个元素之间，取小于 hash 值的那个元素对应的分片为数据的分片。

跳跃法（jumpstringhash）跳跃法的原理如下：1. 根据公式：

将数据落在每一个节点的概率进行平均分配。

2. 对于输入的字符串进行计算 hash 值，通过判断每次产生的伪随机值是否小于当前判定的节点 1/x，最终取捕获节点编号最大的作为数据的落点。3. 在实际使用中使用倒数的方法从最大节点值进行反向判断，一旦当产生的伪随机值大于 x 则判定此节点 x 作为数据的落点。

数据比较

下面将通过测试对环割法和跳跃法的性能及均衡性进行对比，说明 DBLE 为何使用跳跃法代替了环割法。

• 数据源：现场数据 350595 条

• 测试经过：

  1. 通过各自的测试方法执行对于测试数据的分片任务。

  2. 测试方法：记录分片结果的方差；记录从开始分片至分片结束的时间；记录分片结果与平均数的最大差值。

  3. 由于在求模法 PartitionByString 的方法中要求分片的数量是 1024 的因数，所以测试过程只能使用 2 的指数形式进行测试，并在 PartitionByString 方法进行测试的时候不对于 MAC 地址进行截断，取全量长度进行测试。

Answer 2

CRC全称为Cyclic Redundancy Check，又叫循环冗余校验。CRC是目前使用中最老的一种校验算法，CRC是种根据网络数据封包或电脑档案等数据产生简短固定位数校验码的一种散列函数（HASH，把任意长度的输入通过散列算法，最终变换成固定长度的摘要输出，其结果就是散列值，按照HASH算法，HASH具有单向性，不可逆性），主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者储存之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。一般来说，循环冗余校验的值都是32位的整数。由于本函数易于用二进制的电脑硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误，因此获得广泛应用。
正因为CRC具有以上特点，对于网络上传输的文件类很少只使用CRC作为校验依据，文件传输相比通信底层传输风险更大，很容易受到人为干预影响。

MD5全称为Message-Digest Algorithm 5，又叫摘要算法和哈希算法。
MD5由MD4、MD3、MD2改进而来，MD5散列长度通常是128位，是目前被大量广泛使用的散列算法之一，主要用于密码加密和文件校验等，虽然MD5比CRC的安全可靠性要高的多，但目前已经找到可行的破解方法。现在网上虽然出现有些破解网站和软件，不过可以肯定实际作用范围相当有限，比如，即使黑客拿到了PASSWORD MD5值，除了暴力破解，即使找到碰撞结果也未必能够影响用户安全问题，因为对于密码还要限定位数、类型等，但是如果是面向数字签名等应用，可能就会被破解掉。

SHA全称为Secure Hash Algorithm，又叫安全散列算法。SHA家族算法有SHA-1、SHA-224、SHA-256、SHA-384和SHA-512（后四者通常并称SHA2），原理和MD4、MD5相似。SHA可将一个最大2^64位（2305843009213693952字节）信息，转换成一串160位（20字节）的散列值（摘要信息），是目前应用最广的HASH算法。同MD5一样，从理论角度，SHA1也不是绝对可靠，目前也已经找到SHA1的碰撞条件，但“实用”的碰撞算法软件还没出现。于是美国NIST又开始使用SHA2，研究更新的加密算法。

补充：虽然目前这几种校验算法都找到了破解条件，但像目前主流使用的MD5、SHA1还是值得信赖的，因为MD5和SHA1都具有高度的离散性，哪怕是只修改一个字节值都会导致MD5或SHA1值“巨大”变化，从实践角度，不同信息具有相同MD5或SHA1码的可能性非常低，通常认为是不可能的，对于普通的下载文件或操作系统，想通过简单的修改某个字节或某些字节，又要保证文件名、大小和安装可靠性的前提下，想达到MD5、SHA1碰撞效果也几乎是不可能的。