问题描述

Hashing：将任意大小的数据映射到固定大小数据的过程；

Hash/Hash-Code：Hasing 操作后得到的固定大小的数据，通常是整数；

Hash-Function：用于将数据映射为 Hash 的函数；
两种 Hash-Function 用于不同目的：cryptographic；non-cryptographic；

Collision：碰撞，即两个不同的数据具有相同的 Hash-Code；
解决 Collision 的常用做法是：Chaining；Open Addressing；

Hash-Table/Hash-Map：是 CS 中常用的两种数据结构，其用于恒定时间查找；

Distributed Hashing：将多个 Hash 分布在多个不同的存储位置（比如服务器）；

Rehashing：如果存储位置的数量发生变化，则需要重新计算所有 Hash 的存储位置；

Rehashing Problem：Rehasing 带来的问题便是大量 Hash 的存储位置发生变化；

解决方案

Consistent Hashing：是种特殊类型的哈希，其所使用的哈希函数随着散列函数范围的变化而变化最小。

Consistent Hashing 提供分布式方案，使其不依赖于存储位置的数量，这通过抽象环（Hash-Ring）来解决，这使得存储位置数量的变化不会影响整个系统；

顺时针：bob@example.com, mark@example.com on S2； smith@example.com, adam@example.com on S3； alex@example.com, john@example.com on S1；

S1, S2, S3 是三个存储位置，当 S3 消失后，其上的数据将被 S1 承载；
为了减轻 S1 压力，提出 Virtual-Node 概念：将 S3 分为多个 Virtual-Node，当 S3 消失后，其 Virtual-Node 上的数据将 S1、S2 承载；
该过程中，S1 S2 原有的 Hash-Code 无需重新计算，所以减少对整个系统的影响；

将如有 N 个存储位置，K 个 Key：如果移除某个存储位置，则仅会影响 K/N 个 Hash-Code（因为每个存储位置存储 K/N 个 Key，当该位置消失，则影响 K/N 个 Key）

参考文献

Consistent Hashing. Consistent hashing idea was introduced… | by Vivek Kumar Singh