一致性哈希 _生活百科

文章插图
一致性哈希【一致性哈希】一致性哈希算法在1997年由麻省理工学院提出(参见扩展阅读[1]) ，设计目标是为了解决网际网路中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到套用。
基本介绍中文名：一致性哈希
时间：1997年
地区：麻省理工学院
(参见：扩展阅读
哈希算法一致性哈希提出了在动态变化的Cache环境中，哈希算法应该满足的4个适应条件：均衡性(Balance)平衡性是指哈希的结果能够儘可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。单调性(Monotonicity)单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那幺哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。（这段翻译信息有负面价值的，当缓冲区大小变化时一致性哈希(Consistent hashing)儘量保护已分配的内容不会被重新映射到新缓冲区。）简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x → ax + b mod (P)在上式中， P表示全部缓冲的大小。不难看出，当缓冲大小发生变化时(从P1到P2) ，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。

文章插图
哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关係需要在系统内全部更新。而在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。分散性(Spread)在分散式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲範围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够儘量避免不一致的情况发生，也就是儘量降低分散性。负载(Load)负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那幺对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够儘量降低缓冲的负荷。从表面上看，一致性哈希针对的是分散式缓冲的问题，但是如果将缓冲看作P2P系统中的Peer ，将映射的内容看作各种共享的资源(数据，档案，媒体流等) ，就会发现两者实际上是在描述同一问题。路由算法在一致性哈希算法中，每个节点(对应P2P系统中的Peer)都有随机分配的ID 。在将内容映射到节点时，使用内容的关键字和节点的ID进行一致性哈希运算并获得键值。一致性哈希要求键值和节点ID处于同一值域。最简单的键值和ID可以是一维的，比如从0000到9999的整数集合。根据键值存储内容时，内容将被存储到具有与其键值最接近的ID的节点上。例如键值为1001的内容，系统中有ID为1000 ， 1010 ， 1100的节点，该内容将被映射到1000节点。为了构建查询所需的路由，一致性哈希要求每个节点存储其上行节点(ID值大于自身的节点中最小的)和下行节点(ID值小于自身的节点中最大的)的位置信息(IP位址) 。当节点需要查找内容时，就可以根据内容的键值决定向上行或下行节点发起查询请求。收到查询请求的节点如果发现自己拥有被请求的目标，可以直接向发起查询请求的节点返回确认；如果发现不属于自身的範围，可以转发请求到自己的上行/下行节点。为了维护上述路由信息，在节点加入/退出系统时，相邻的节点必须及时更新路由信息。这就要求节点不仅存储直接相连的下行节点位置信息，还要知道一定深度(n跳)的间接下行节点信息，并且动态地维护节点列表。当节点退出系统时，它的上行节点将尝试直接连线到最近的下行节点，连线成功后，从新的下行节点获得下行节点列表并更新自身的节点列表。同样的，当新的节点加入到系统中时，首先根据自身的ID找到下行节点并获得下行节点列表，然后要求上行节点修改其下行节点列表，这样就恢复了路由关係。结论一致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的网路拓扑中分布存储和路由。每个节点仅需维护少量相邻节点的信息，并且在节点加入/退出系统时，仅有相关的少量节点参与到拓扑的维护中。所有这一切使得一致性哈希成为第一个实用的DHT算法。但是一致性哈希的路由算法尚有不足之处。在查询过程中，查询讯息要经过O(N)步(O(N)表示与N成正比关係， N代表系统内的节点总数)才能到达被查询的节点。不难想像，当系统规模非常大时，节点数量可能超过百万，这样的查询效率显然难以满足使用的需要。换个角度来看，即使用户能够忍受漫长的时延，查询过程中产生的大量讯息也会给网路带来不必要的负荷。使用二分查找算法可以将时间複杂度降低为O(log2n)英文解释Consistent hashing is a scheme that provides hash table functionality in a way that the addition or removal of one slot does not significantly change the mapping of keys to slots.