(3)一致性哈希vs哈希取模算法

大数字取模 分散不同桶，两个桶， 2、3、4、5 ，模 2 分桶：

扩容 新桶 ，模 3 来结果：

每次扩展 和 收缩 所有条目分布 重新计算 ，某些场景不可接受。文件 分布 在哪台 哈希算法 决定 ，这个系统想要 加 一台机器时就需要 停 下来等所有文件 重新分布一次 才能对外提供服务，一台机器掉线尽管 只掉一部分数据 ，所有数据访问路由 都会出问题 。 无法平滑的扩缩容 。

无状态化 ，用多个桶，  模 7个 ，开始只有两个 3 和 6。同样取模，分到不存在的桶，往下找第一个真实存桶。 2 和 3 分3 桶， 4 和 5分 6 桶。

添加新  编号4桶， 还是模 7 ：

3 号桶取模 小于等于 3 ，4 号桶只需从 6 号桶 拿走属于它数字就可， 只调整一个桶重新分布 。即使有 1 亿个桶，增加减少一个桶也只会影响一个桶的数据分布。

只需 和后面机器同步 数据 就可工作 ，同步到后一台机器再下线。 实现中 可以让每台机器 同步一份自己前面机器的数据 ，即使 掉线也不影响 这部分数据服务。

问题：编号  6 的机桶下线 了， 没有后一个桶了 ，哈希空间做成 环状 ， 数据给 3  ：

一致性哈希还能 实现部分 的分布式系统 无锁化 ， 算法的确定性 ，分到哪个桶也是确定的就 不存在争抢 ， 不需要分布式锁 了。

查找效率：普通的哈希 查询 一次 哈希计算就可以找到对应的桶了  O(1) ，一致性哈希需要将 排好序 的 桶组成 一个 链表 ，一路找下去k 个桶  O(k)

O(k) 对于哈希来说 不能忍 ，这个量级了用哈希没意义，在排好序桶里查询， 二分 把时间复杂度降到 O(logk) ，桶组合需不断增减，链表实现二分肯定不行，用 跳转表快速跳转 也能 实现 O(logk) 

跳转表中， 每个桶记录距离自己 1，2，4 距离的数字所存的桶，不管查询落在哪个节点上，对整个哈希环上任意的查询一次都 可以至少跳过一半的查询空间？ ，这样递归下去很快就可以定位到数据是存在哪个桶上。

上面只是 一种 ，很多一致性哈希 变体 。如选桶：上面顺着数字选 对面 出现 第一个桶 ，其实也可选距离 数字最近桶 ，这样跳转表规则也变。同样跳转表不同算法实现：  CAN，Chord，Tapestry，Pastry 这四种 DHT  

1、如果 6号 (里面有数据)桶突然 宕机 了，是不是里面的数据也丢失了？来不及将桶里的数据往前一个桶移？

答：实际情况会做冗余，画的是一个桶， 实际可能是三个

2、 「一致性」 是扩缩容前后数据在桶里的 分布是一致 的

3、 分布式 系统中怎么 实现服务间的事务 ，目前有哪些通用做法，比如dubbo

用zk或者etcd这种分布式 锁 服务，让接口是 幂等， 可以反复重试

4、增加此类 *** 作会 拖慢集群的性能 。如果某节点上一刻 宕机 ，往后新数据会进入 下一个节点 ，宕机节点 恢复 ，下一个节点还要同步原属宕机的数据，复杂度为O(nlogn)，会不会代价略高？开源的ketama没有同步数据这一做法，所以本质上只是近似一致性哈希，是不是一个trade-off的选择？

答：这个场景不适合使用一致性哈希吧。以 负载均衡 为例，理论上是认为后台服务器是 无状态 的吧。所以宕机重启 不应该有数据同步 的问题。

处理数据同步，raft强一致方案

对hash结果取余数 (hash() mod N)：机器编号从 0到N-1 ，hash()值 按N取模 ， 余数i，分发到编号i机器 。致命问题，宕机，落在该机器请求无法处理，有 (N-1)/N 服务器的缓存数据重新计算；为何是 (N-1)/N 呢：3 台机器，hash值 1-6 分布：

host 1: 1 4

host 2: 2 5

host 3: 3 6

挂掉一台，只剩两台， 模数取 2：

host 1: 1 3 5

host 2: 2 4 6

位置不变2个： 1，2，位置改变4个，占共6个数据的比率是 4/6 = 2/3。

N个真实 节点,每个映射成 M个虚拟节 点, MN个虚拟节点散列在圆环上 真虚相互交错分布，真down后,平均分到所有节点

访问方法：

写入缓存请求，Key值为K，计算器hash值Hash(K)， Hash(K) 对应于环中的某一个点，没有映射到机器节点，顺时针查找，直到找到有映射机器的节点，确定目标节点，超过2^32找不到，命中第一个。

缺陷：server数量很少时，环中分布不均匀，导致cache到server不均匀

例：用电话号码group by，如移动用户多，就会倾斜，reverse或加随机数解决

hash取模对模数有要求，用奇数不用偶数，数据量大的时模数不好选，用上面办法。

>      当页面被恶意木马攻击更改后,监控状态脚本并不能检测出异常,但是Web的页面已经存在相当大的安全隐患所以能不能寻找到一种方法判断自己所负责的Web服务器页面内容是否遭到恶意木马的攻击和修改显得十分重要通过Hash值的方法可以非常高效的检测到WEB服务器页面的数据内容是否完整,如果页面内容被恶意木马更改,新页面的Hash值是不同于原始的Hash值的,我们就可以以此作为判断的依据!

获取Hash值的方法:

md5sum /var/> 如 >

使用。

设定一个圆环上 0-2^3̂2-1 的点，每个点对应一个缓存区，每个键值对存储的位置也经哈希计算后对应到环上节点。但现实中不可能有如此多的节点，所以倘若键值对经哈希计算后对应的位置没有节点，那么顺时针找一个节点存储它。

1、考虑增加服务器节点的情况，该节点顺时针方向的数据仍然被存储到顺时针方向的节点上，但它逆时针方向的数据被存储到它自己。这时候只有部分数据会失效，被映射到新的缓存区。

2、考虑节点减少的情况。该缺失节点顺时针方向上的数据仍然被存储到其顺时针方向上的节点，设为 beta，其逆时针方向上的数据会被存储到 beta 上。同样，只有有部分数据失效，被重新映射到新的服务器节点。

扩展资料：

一致性哈希算法

这种方法可以应对节点失效的情况，当某个分布式集群节点宕机，服务请求可以通过hash算法重新分配到其他可用的服务器上。避免了无法处理请求的状况出现  。

但这种方法的缺陷也很明显，如果服务器中保存有服务请求对应的数据，那么如果重新计算请求的hash值，会造成大量的请求被重定位到不同的服务器而造成请求所要使用的数据失效，这种情况在分布式系统中是非常糟糕的。

一个设计良好的分布式系统应该具有良好的单调性，即服务器的添加与移除不会造成大量的哈希重定位，而一致性哈希恰好可以解决这个问题。

   由于Redis Cluster（集群）采用哈希分区规则，所以先介绍下常见的哈希分区规则。常见的哈希规则： 节点取余分区规则、一致性哈希分区（Consistent hashing）、虚拟槽（Virtual slot）分区。

   使用特定的数据，如Redis的键或用户ID，再根据节点（运行在集群模式下的Redis服务器）的数量N使用公式：hash(key) % N计算出hash值，用来决定数据存储在哪个节点上。例如，将20个数据存储在4个节点上：

  一致性哈希分区实现思路是为系统中的每个节点分配一个token，范围是0~2 32 -1，这些token构成一个哈希环。数据读写执行节点查找 *** 作时，先根据key计算出哈希值，然后顺时针找到第一个遇到的token节点。

  一致性哈希分区的缺点：

   Redis Cluster采用的就是虚拟槽分区。 虚拟槽分区巧妙的使用了哈希空间，使用分散度良好的哈希函数将所有的数据映射到一个固定范围的整数集合中，整数定义为槽（slot）。这个范围一般远远大于节点数，这是为了消除哈希的倾斜性，便于数据拆分和扩展。例如Redis Cluster槽的范围是0~16383。槽是集群内数据管理和迁移的基本单位，每个节点都会负责一定数量的槽。
  如在Redis中，假设有5个节点，每个节点平均负责3276个槽。

  (1) 常见的哈希分区规则有：节点取余分区、一致性哈希分区和虚拟槽分区。
  (2) Redis Cluster数据分区规则采用虚拟槽方式，所有的键映射到16384个槽中，每个节点负责一部分槽和相关数据，实现数据和请求的负载均衡。
   本文完

  注：本文参考《Redis开发与运维》，如发现错误，请指正！

1、微软已经变更Win10系统的激活规则，重装后激活可以不使用密钥。相比之前的Win7/Win81等 *** 作系统，新规则让重装激活变得更加简单。
之所以重装不需要密钥就能够激活，是因为微软已将激活信息存储在云端，当你重装系统后，联网情况下会自动在云端进行验证。
并且重装Windows10时，安装程序虽然也会要求输入密钥，但你可以选择跳过。重装完成以后，Win10系统会自动激活，因为在云端验证时会自动判断这台电脑是否已经安装并激活过Win10。
2、长期以来，微软的产品激活都依赖于电脑硬件哈希，硬件哈希具有唯一性，且算法不可逆，也不绑定到微软的任何服务中，它只与电脑硬件本身相关。Win10安装程序会检查系统激活状态，并将其报告给激活服务器。Windows激活服务器会根据硬件哈希以及所激活的Win10版本（家庭版、专业版或其他版本）产生许可证书从而激活系统。重装激活时也只需要验证硬件哈希以及系统版本，不需要用户输入激活密钥。

哈希(Hash)算法,即散列函数。它是一种单向密码体制,即它是一个从明文到密文的不可逆的映射,只有加密过程,没有解密过程。同时,哈希函数可以将任意长度的输入经过变化以后得到固定长度的输出。哈希函数的这种单向特征和输出数据长度固定的特征使得它可以生成消息或者数据。
计算方法：
用来产生一些数据片段（例如消息或会话项）的哈希值的算法。使用好的哈希算法，在输入数据中所做的更改就可以更改结果哈希值中的所有位；因此，哈希对于检测数据对象（例如消息）中的修改很有用。此外，好的哈希算法使得构造两个相互独立且具有相同哈希的输入不能通过计算方法实现。典型的哈希算法包括 MD2、MD4、MD5 和 SHA-1。哈希算法也称为“哈希函数”。
另请参阅： 基于哈希的消息验证模式 (HMAC), MD2, MD4, MD5,消息摘要, 安全哈希算法 (SHA-1)
MD5一种符合工业标准的单向 128 位哈希方案，由 RSA Data Security, Inc 开发。 各种“点对点协议(PPP)”供应商都将它用于加密的身份验证。哈希方案是一种以结果唯一并且不能返回到其原始格式的方式来转换数据（如密码）的方法。质询握手身份验证协议(CHAP) 使用质询响应并在响应时使用单向 MD5哈希法。按照此方式，您无须通过网络发送密码就可以向服务器证明您知道密码。
质询握手身份验证协议(CHAP)“点对点协议(PPP)”连接的一种质询响应验证协议，在 RFC 1994 中有所描述。 该协议使用业界标准 MD5哈希算法来哈希质询串（由身份验证服务器所发布）和响应中的用户密码的组合。
点对点协议
用点对点链接来传送多协议数据报的行业标准协议套件。RFC 1661 中有关于 PPP 的文档。
另请参阅： 压缩控制协议 (CCP)，远程访问，征求意见文档 (RFC)，传输控制协议/Internet 协议 (TCP/IP)，自主隧道。

ziplist 编码的哈希对象使用压缩列表作为底层实现， 每当有新的键值对要加入到哈希对象时， 程序会先将保存了键的压缩列表节点推入到压缩列表表尾， 然后再将保存了值的压缩列表节点推入到压缩列表表尾， 因此：

保存了同一键值对的两个节点总是紧挨在一起， 保存键的节点在前， 保存值的节点在后；
先添加到哈希对象中的键值对会被放在压缩列表的表头方向， 而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。
举个例子， 如果我们执行以下 HSET 命令， 那么服务器将创建一个列表对象作为 profile 键的值：

另一方面， hashtable 编码的哈希对象使用字典作为底层实现， 哈希对象中的每个键值对都使用一个字典键值对来保存：

Redis 的字典使用哈希表作为底层实现， 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。

Redis 字典所使用的哈希表由 dicth/dictht 结构定义：

table 属性是一个数组， 数组中的每个元素都是一个指向 dicth/dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。

size 属性记录了哈希表的大小， 也即是 table 数组的大小， 而 used 属性则记录了哈希表目前已有节点（键值对）的数量。

sizemask 属性的值总是等于 size - 1 ， 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。

图 4-1 展示了一个大小为 4 的空哈希表 （没有包含任何键值对）。

哈希表节点使用 dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对：

key 属性保存着键值对中的键， 而 v 属性则保存着键值对中的值， 其中键值对的值可以是一个指针， 或者是一个 uint64_t 整数， 又或者是一个 int64_t 整数。

next 属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一次， 以此来解决键冲突（collision）的问题。

举个例子， 图 4-2 就展示了如何通过 next 指针， 将两个索引值相同的键 k1 和 k0 连接在一起。

Redis 中的字典由 dicth/dict 结构表示：

type 属性和 privdata 属性是针对不同类型的键值对， 为创建多态字典而设置的：

ht 属性是一个包含两个项的数组， 数组中的每个项都是一个 dictht 哈希表， 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

除了 ht[1] 之外， 另一个和 rehash 有关的属性就是 rehashidx ： 它记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1 。

图 4-3 展示了一个普通状态下（没有进行 rehash）的字典：

在Redis中，由于它对实时性要求更高，因此使用了渐进式rehash

当有新键值对添加到Redis字典时，有可能会触发rehash。Redis中处理哈希碰撞的方法与Java一样，都是采用链表法，整个哈希表的性能则依赖于它的大小size和它已经保存节点数量used的比率。
比率在1:1时，哈希表的性能最好，如果节点数量比哈希表大小大很多的话，则整个哈希表就退化成多个链表，其性能优势全无。

上图的哈希表，平均每次失败查找需要访问5个节点。为了保持高效性能，在不修改键值对情况下，

需要进行rehash，目标是将ratio比率维持在1:1左右。

Ratio ＝ Used / Size

rehash触发条件：

rehash执行过程：

Redis哈希为了避免整个rehash过程中服务被阻塞，采用了渐进式的rehash，即rehash程序激活后，并不是

马上执行直到完成，而是分多次，渐进式（incremental）的完成。同时，为了保证并发安全，在执行rehash

中间执行添加时，新的节点会直接添加到ht[1]而不是ht[0], 这样保证了数据的完整性与安全性。

另一方面，哈希的Rehash在还提供了创新的（相对于Java HashMap）收缩（shrink）字典，当可用节点远远

大于已用节点的时候，rehash会自动进行收缩，具体过程与上面类似以保证比率始终高效使用。

当哈希对象可以同时满足以下两个条件时， 哈希对象使用 ziplist 编码：

---