一致性哈希算法
大约 2 分钟
1. 哈希算法
哈希算法用来将一系列的值映射到一个区间内，在负载均衡、HashMap、数据库分库分表等场景经常使用。
然而该算法的应用在数据库等系统扩容时，具有严重缺陷：如果节点的数量发生了变化，而节点持久化了响应的数据，则必须对进行数据迁移。如果数据量较大则会带来极高的迁移成本。
使用一致性哈希算法则可以有效的解决上述问题。
2. 一致性哈希算法
2.1 介绍
一致性哈希算法和哈希算法的不同是：一致性哈希算法对2^32取模，而非节点的个数。取模的结果即为哈希环。这样节点就是环上的一个点，而数据映射的结果只需要按照顺时针的顺序找到第一个节点进行映射即可。
2.2 数据迁移
此时，如果需要数据迁移的话，例如A、B、C节点后续又增加了D节点，则只需要迁移A-D之间的数据到D即可。
2.3 数据分布
然而，一致性哈希算法不能保证数据的均匀分布，可能会有大量的请求集中在一个节点上，即超过50%的C-A之间的请求将落在A上。
为此，可以增加大量的虚拟节点个数，并将虚拟节点映射到实体节点上来解决这个问题（如Nginx的一致性哈希算法，每个真实节点背后包含了160个真实节点）。
这样以来，不但哈希节点变得均匀了，如果需要新增或移除节点，其增删的部分也会动态的被其他实际节点来分担。