前言

前几天跟朋友聊到了数据库的分表，提及了“一致性哈希算法”。虽然一直以来都知道这个东西，但是未曾深入的探究。因此，在了解到一些皮毛之后在此写下了自己的理解，如有写的不当，还望指正。同时，我也用Python写了一个简单的实现思路至于GitHub，有兴趣的朋友可以进行查阅。

比较

一般说来，当我们涉及到分布式存储时，常见的有两种算法，一种是较为简单的取模算法，另外一种就是此文所提及的“一致性哈希算法”。
取模算法的优势在于，对于数据的操作较为简单，在项目的前期不失为一个不错的选择。但是弊端也非常明显，一旦当我们数据增长到一定的规模，我们再在之前的架构上增加节点时，会导致大量的数据需要重新迁移。而在这篇文章里面也用数据指出了两种不同算法的差异性。

虽然一致性哈希算法并不能完全解决增加节点时数据迁移的问题，但是他已经在很大程度上减少了我们数据的迁移量。此外，当我们在移除一个节点时，我们甚至不会影响到其他的节点。

原理

在一致性哈希算法中，所有的数据呈环装分布（包括Node节点），而我们会以统一的哈希算法来根据我们要存储的节点名，或者key进行hash转换，一一映射到这个环中，如下图所示。

我想此图应该非常清晰的阐明了一致性哈希算法的运作原理，同时，也解释了为什么我在上文说:

当我们在移除一个节点时，我们甚至不会影响到其他的节点。

的原因。

当然，在此图中我添加了两个Rep的节点，这里的做法主要目的在于维护数据的平衡性，如果具体的hash算法写的不是特别合适，那么会导致数据呈现一边倒的趋势。因此，添加两个Replication可以帮助我们分散数据，这也符合一致性哈希算法的要求:

1、平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
2、单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
3、分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
4、负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
注：上述要求取自于每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)

来源:https://hellonine.top/index.php/archives/93/