Mysql分片：一致性哈希算法

一、一致性哈希的核心原理

哈希取模最大的痛点是：当分片数量（例如数据库节点数）发生变化时，几乎所有数据的哈希结果都会改变，导致大规模的数据迁移。一致性哈希就是为了解决这个“伸缩性差”的问题而诞生的。

核心思想：数据和节点共舞的“虚拟圆环”

一致性哈希不再简单粗暴地用数据哈希值对节点数量取模。它的核心在于引入了一个 “哈希环”（Hash Ring 或 Hash Circle）的概念。你可以把这个哈希环想象成一个巨大的虚拟圆盘，它的周长覆盖了所有可能的哈希值范围（比如从0到 $^{2^{32}}$ -1，或者 $^{2^{64}}$ −1，取决于哈希算法的输出范围）。

在这个哈希环上，有两类重要的参与者：

存储节点（服务器/数据库）：
- 我们不再直接用服务器数量做模数。而是将每一个真实的存储节点（比如你的 db_0、db_1、db_2 这些数据库服务器），通过一个哈希函数计算出一个哈希值。
- 这些哈希值就相当于服务器在圆环上的“座标点”。每个节点都会根据自己的哈希值，被放置到哈希环上的一个特定位置。
数据记录：
- 同样地，每一条待存储的数据记录（比如一个用户的信息、一个订单的详情），我们会选择它的某个字段作为分片键（比如 user_id 或 order_id）。
- 然后，我们用同样的哈希函数计算这个分片键的哈希值，把数据也映射到哈希环上的一个位置。这个哈希值就像是数据的“身份证号码”，它也对应着圆环上的一个“座标点”。

哈希环示意图：

智能罗盘：数据如何找到它的“归宿”？

当一条数据（或一个查询请求）要寻找它的存储位置时，一致性哈希的“智能罗盘”就会启动：

数据路由法则：从数据在哈希环上的存储数据位置开始，沿着圆环顺时针方向查找，遇到的第一个存储节点，就是这条数据存储的节点位置！

比如，在该哈希环上：

data1 存储在 nodeA：
- data1 位于 0 和 nodeA 之间。从 data1 顺时针查找，遇到的第一个存储节点是 nodeA。
data2 存储在 nodeB：
- data2 位于 nodeA 和 nodeB 之间。从 data2 顺时针查找，遇到的第一个存储节点是 nodeB。
data3 存储在 nodeC：
- data3 位于 nodeB 和 nodeC 之间。从 data3 顺时针查找，遇到的第一个存储节点是 nodeC。
data4 存储在 nodeA：
- data4 位于 nodeC 和 0 之间（或者说 nodeC 到 2^32-1 之间，因为环是闭合的）。从 data4 顺时针查找，遇到的第一个存储节点是 nodeA。

二、一致性哈希执行案例

我们来设计一个简单且易于理解的一致性哈希执行案例。我们将聚焦在一个非常常见的场景：一个简单的分布式缓存系统。

场景设定：

假设你正在开发一个热门的社交应用，其中有很多用户头像图片需要缓存。为了提高访问速度和系统承载能力，你决定使用多个缓存服务器来存储这些图片。当用户请求某个头像时，你需要知道这张图片存在哪个缓存服务器上。

缓存内容：用户头像图片。
唯一标识：user_id (用户ID)，我们将用它作为分片键。
缓存服务器：初始有 3 台服务器，命名为 CacheA, CacheB, CacheC。

我们将使用一致性哈希来决定每张图片存储在哪台缓存服务器上。

步骤一：服务器“入座”哈希环

在系统启动时，我们的缓存服务器需要先在哈希环上找到自己的“座位”。

我们会用哈希函数计算每台服务器名称的哈希值：
- Hash("CacheA") rightarrow 假设得到 100
- Hash("CacheB") rightarrow 假设得到 1500
- Hash("CacheC") rightarrow 假设得到 3000

我们在这假设该哈希函数计算的哈希值在0-3599之间

（注：为了简化，实际哈希值范围很大，这里用小数字示意相对位置）

我们将这些哈希值标注在哈希环上：

步骤二：用户头像图片“找主人”

现在，当用户请求或上传一张头像（user_id）时，系统需要知道它应该存在哪台缓存服务器上。

我们以两个用户为例：

用户ID: 1001 的头像
- 我们用同样的哈希函数计算 user_id = 1001 的哈希值：
  Hash("1001") rightarrow 假设得到 500
- 将 500 标注在哈希环上。
- 查找规则：从 500 这个点开始，沿着哈希环顺时针方向查找，遇到的第一个缓存服务器是谁，它就归谁管。
- 根据图示，从 500 顺时针，第一个遇到的服务器是 CacheB (1500)。
- 结论：用户1001的头像 存储到 CacheB。
用户ID: 2002 的头像
- Hash("2002") rightarrow 假设得到 3200
- 将 3200 标注在哈希环上（这里同上，我就不在画了）。
- 查找规则：从 3200 顺时针查找，由于环是闭合的，它会绕过 3599 重新从 0 开始，遇到的第一个服务器是 CacheA (100)。
- 结论：用户2002的头像 存储到 CacheA。

步骤三：服务器扩容，一致性哈希显神通

假设现在，你的社交应用用户量暴增，CacheA, CacheB, CacheC 三台服务器已经不够用了！你需要新增一台缓存服务器：CacheD。

哈希取模的痛点：如果是传统哈希取模 (Hash(user_id) % N)，N从3变成4，那几乎所有用户头像的位置都会重新计算，你需要把大量头像数据从旧服务器搬到新位置，系统可能要停机维护，非常麻烦！
一致性哈希的优势：
1. CacheD “入座”哈希环：
  - 我们计算 Hash("CacheD") rightarrow 假设得到 2000。
  - 将 CacheD (2000) 放置在哈希环上。它会落在 CacheB (1500) 和 CacheC (3000) 之间。
2. 数据迁移分析：
  - 观察哈希环，CacheD 的加入，只会影响到它逆时针方向的那个服务器（CacheB）所负责的部分数据。
  - 原来从 CacheB (1500) 顺时针到 CacheC (3000) 的这部分区间，现在被 CacheD (2000) 分割了。
  - 只有那些哈希值在 1500 到 2000 之间的用户头像，需要从 CacheB 迁移到 CacheD。
  - 而 CacheA 负责的头像数据、以及 CacheB 负责的哈希值小于 1500 的头像数据，位置完全不变！

这一特性是衡量分布式系统可伸缩性的关键优势。相比于传统哈希取模在节点变化时需要进行全局数据重分布，一致性哈希实现了渐进式、低影响的扩容/缩容操作，极大地降低了系统维护成本和业务中断风险。

三、总结：

一致性哈希算法通过将数据键与存储节点共同映射至一个环形哈希空间，并基于“顺时针最近匹配”原则进行数据路由，从而巧妙地解决了分布式系统在扩容或缩容场景下，传统哈希取模算法导致的大规模数据迁移问题。这一机制显著提升了系统的弹性伸缩能力和可用性。在构建高性能、高可扩展性的分布式缓存或分布式存储系统时，一致性哈希提供了一种高效且稳定的数据分布与管理策略。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.tpcf.cn/pingmian/88320.html

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！