一致性哈希最早是1997年在麻省理工大学提出的一种解决热点问题的算法。后来在分布式环境被广泛使用。
试想如果我们的服务产生大量数据,这些数据的存取如果只是单台服务器,那么肯定会出现一定的性能瓶颈,所以我们需要多台数据库来支撑业务。
而在分布式的环境中,数据的分布需要解决以下几个问题:
- 数据服务器发生故障的时候,整体不会受到影响
- 服务器扩容时,
- 数据分布不均匀
而一致性哈希很好地解决了这些问题,它的核心思想是设置一个2^32次方个空间的环形空间,然后分成几个区域,数据哈希值所在的指定区域就会决定数据的落地位置(也就是落到哪一台服务器上面)。
这里假设我们有三台服务器:
- Server A
- Server B
- Server C
将机器通过特定的Hash函数
算出对应的key值,然后将这些标记值散列在这个环形空间
上。
这个时候将一个数据(Data)对象使用同样的Hash函数
算出对应的key值,并将这些值也标记在环形空间
上。按顺时针方向去找最近的服务器对应key标记,这台服务器就是这个数据对象要落地的位置了。
比如这个数据最终会落到Server C
上面去,每次读取数据也通过同样的方式来寻找图片的位置。
在以上的例子中。假设出现三个数据:
- Data1
- Data2
- Data3
Data1
存在Server A
上,Data2
存在Server B
上,Data3
存在Server C
上。
而Server A
宕机了,那么这个时候可能无法查询到数据Data1
了。但是并不妨碍数据Data2
和Data3
的查询。
如果这个时候出现了Server D
,Data3
通过上面的方式,就会查询到Server D
上,而这台新的服务器上并没有数据。我们可以改进一下,如果当前的位置查不到数据,可以顺延去下一个节点(也就是Server C
)上查找数据。
光光以上这样还不够,如果每台服务器仅有一个节点,数据很容易堆积到一台服务器上。
这个时候可以通过添加虚拟节点来解决这个问题,我们将一台服务器做出多个映射值。这样可以在环形上,让服务器分布地更加均匀一些。
通过一致性哈希算法,数据很好地被存到的不同的机器上,分摊了单机服务器的压力。