散列函数
散列函数即Hashed function也可以称为哈希函数，它可以把一段数据输入进去经过运算得到一串固定长度的散列值，散列函数把数据压缩成一段特殊位长的数据串，将数据的格式固定下来得到散列值，有点像现实生活中的DNA一样。如果大家下载过软件留意过一般一些软件都会提供一些校验码，这些校验码就是防止软件被篡改，只要修改了一点点那么的结果就是不一样的，但是不同的输入可能会散列成相同的输出，这得看使用的具体算法了，所以不可能从散列值逆向出来输入的原值，简单理解就是一把一堆数据压缩成一段固定长度的数据段的函数。

散列函数的关键在于它的散列算法，现在有很多种类似于散列函数的算法例如：MD5、SHA-256等等，在密码学中有广泛的应用，本篇文章主要讲解的是散列函数在分布式架构场景中的应用Conistency Hashed。

Consistent Hashing
传统哈希数据负载方案 Load Balancing Algorithms就是使用哈希函数对服务器总数取余，然后余数就是对应的服务器编号，然后把数据文件存储到相应的服务器上，优点就是能做到数据分摊，但是缺点也很明显计算服务器编号的哈希公式hash(x)%n里面的n为集群服务器总数，是固定死的，这样的话如果在运行中的时候添加节点和删除节点就很麻烦需要修改公式里面的n，这样之前存储的数据文件再通过原来的公式去计算那么就得到不同的结果，直接失效了，为了解决这样的问题有学者就提出了一致性哈希方案。

一致性哈希算法在1997年由麻省理工学院提出，是一种特殊的哈希算法，目的是解决分布式缓存的问题。在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系，也就是在动态扩容的时候添加服务器或者缩容的时候减少服务器不会影响到整体的服务质量。

在分布式存储系统里面最重要就是数据怎么在这些集群里面分布存储，怎么把数据分布到集群中不同节点上，并且还能保证集群节点之间的负载均衡。目前场景就数据分布方式有很多种，最常见有：哈希分布，顺序分布，这两种经典的实现应用有Amazon Dynamo和Google BigTable这两个分布式存储系统。

Google BigTable采用就是将数据规划成一个大表然后根据主键顺序拆解成不同的小表范围进行存储，而Amazon Dynamo采用的方式就是本文我要讲的一致性哈希的方式把数据分片存储在集群中不同节点里面。

一致性哈希算法最大好处就是能动态添加节点或者删除节点，并且还能动态调整节点数据负载的范围，下图就是笔者画的一致性哈希原理图，如下：

一致性哈希原理就是分配2^n-1次方个token节点，然后把这些节点围成一个环，而这个环上的每一个点都可以当成服务器所在的位置也可以是数据文件所在的位置，然后顺时针查找，找到最近那个节点服务器，即可把数据文件存储到这台服务器上如上图所示。

添加服务器： 例如下图中在集群中添加一个节点为D服务器，只需要在添加的时候计算出来D在环上的位置token值，然后将其添加到集群里面，此时集群里面的服务器信息也需要更新，方便其他服务器知道D的存在。另外就是添加的服务器只会影响到之前位置上的数据文件，如下图在C到A之间添加D，当D成功被添加到集群里面了，只会影响到C到D这一段的token位置上的数据文件，当然这个可以根据具体实现来规划，如图下有一个文件本来存储在A服务器上的，当D被添加到集群里面，可以选择把这个数据文件从A上迁移到D上进行存储，通过这个可以看出来如果发生节点服务器添加只会影响到集群中部分数据，而不会影响到整个集群。

删除服务器： 如下图要把刚刚添加的D节点删除，那么就需要把D节点上存储的数据，迁移到它的下一个节点上，目前D下一个节点正是A节点，所有把数据迁移到A上进行存储，如果D节点上存储的数据比较多的话也可以通过分摊法把数据分摊迁移到集群其他的节点上即可保存。

数据倾斜问题： 如果集群中的节点过少并且数据节点没有经过好的计算得出token的位置的话，可能每个节点之间的数据存储会发生数据倾斜，如下图A节点存储的数据比较多，这时可以引入一个虚拟节点来保存数据。虚拟节点作用就是把一些节点分配不平均的情况下，使得数据平均分摊到整个集群其他节点上，图下把B2设置为虚拟节点，而这个节点只是一个虚拟的，它有一个上级节点也就是真正存储数据的节点是B，当数据文件要存储的时候通过计算得到的token位置是属于B2那么这个数据真正存储的地方也是B节点，从而达到数据平摊效果。

小 结
这些典型的应用有Amazon Dynamo数据库，也有Facebook Cassandra数据库，另外一个就是经常使用的缓存中间件了Redis，当然Redis这个相当于一个简化版本的。