简单系统设计 —— 一致性哈希（七）
本系列，是自己学习Grokking the System Design过程中的笔记。
希望读者在看完全文后，也能留下你们的经验。我万分荣幸能收到你们的消息。
如果能从这里学到点东西，记得请我喝杯☕☕☕~
—— MinRam
一、前言 Overview
《Consistent Hashing and Random Trees: Distributed Caching Protocols for Releifying Hot Spots on the World Wide Web》一文中完整介绍了一致性哈希的思想，有兴趣可以深挖下。
一致性哈希 （Consistent Hash）, 是分布式系统中极为重要的一个组成。首先了解什么是哈希表，总的来说就是这样一个公式：
$$ Index = Hash_Function(Key) $$
包含：键，值和哈希关系(给定键能得到唯一的值或者存储值的地址)。能够在恒定时间内通过键，找到对应的值。
前面提到的，当我们存在容量为N的缓存机制时，或者总结点数为N的数据分片节点。最直接且常见的哈希方程就是 Key % N。但将面临两个问题：
- 不支持水平扩展 Not be horizontally scalable
当插入一个新的缓存节点时，整个哈希表中的映射关系将被破坏失效[ K mod N ≠ K mod (N+1)]。这将导致系统需要较长的停机时间，去更新所有的缓存映射。 - 分布不均匀 Not be load balance
实际场景中，数据并不是均匀的。有些数据更经常被访问（Hot data)，并且更容易被哈希到同一个节点；而相反的，有些数据几乎用不到；
而这些问题，能够被一致性哈希很好地改善。
二、一致哈希 Consistent Hash
对于分布式缓存系统或者类似的分布式哈希表（Distributed Hash Table), 一致哈希策略至关重要。
上节中，传统的哈希函数，将Key与当前节点数N关联。导致增删节点时候，需要重置所有的映射关系。而一致性哈希的目的，就是使增删节点时需要重置键值数量最小化。
在一致哈希中，整个哈希函数与节点数量N，并无直接关系：
- 当节点添加时，其他节点（部分节点）上承载的部分键值对，将被重新分配到该新增节点上；
- 当节点移除时，该节点上承载的部分键值对，将被其他节点分摊；
三、策略原理 How to work
一致性哈希函数，常把键映射成一个整数。例如将输入Key映射到[0,256]的输出范围内。从而整个输出范围，通过头尾相接，可以形成一个环。
主要举例说明：
给定一个缓存服务器列表 [A, B, C], 每个输入都会被映射到环上的某个值 [0, 256]。
- 将缓存服务器映射到环上的某个点
- 对于每个环上的值，按照顺时针🔃方向移动，碰到的第一个服务器就是对应缓存所在的服务器。
通过以下动画演示：
每个键Key, 通过哈希函数，映射到[0, 256]之间，再通过顺时针，找到自己的命中节点（缓存节点）；
当移除缓存节点时，比如节点A，所有在节点A上的键Key，都会重新映射到下一个顺时针节点上，而其他节点不会受到影响；
当添加一个缓存节点时，比如节点A，将从下一个顺时针节点中，移动部分键Key到新增节点上；
上面提到实际数据虽然是随机分布的，但并非均匀分布。这会导致最终映射到环上的值也不均匀。因而提出了数据副本的概念。对于一个键Key，数据会被存储在多个缓存节点中，存在多个副本。随着副本数量增加，最后在环上的分布将更加均匀。
