海量数据分流处理-------一致性哈希算法

大学时期做移动开发(ios),毕业后开始做大数据开发，到现在也为止也做过不少工程项目，掌握了不少我只认为是工具的东西，比如Hadoop中的HDFS、Mapreduce、Yarn、HBase、Hive、Sqoop、Flume、Mahout、Pig、Zookeeper等和Spark中的Spark SQL、Spark Streaming、MLlib等，越来越意识到算法在工程中的重要性，有了扎实的的算法基础，新的技术，新的工具能够很快的学会并且掌握，也是通往高级工程师的必经之路。今天来说一说海量数据分流处理中的一种方法：一致性哈希算法。

海量数据分流处理(负载均衡)的几种方法

一、传统Hash方法

实际应用：流量分发

1.png

这个算法的问题在于容错性和扩展性不好。所谓容错性是指当系统中某一个或几个服务器变得不可用时，整个系统是否可以正确高效运行；而扩展性是指当加入新的服务器后，整个系统是否可以正确高效运行。

现假设有一台服务器宕机了，那么为了填补空缺，要将宕机的服务器从编号列表中移除，后面的服务器按顺序前移一位并将其编号值减一，此时每个key就要按h = Hash(key) % (N-1)重新计算；同样，如果新增了一台服务器，虽然原有服务器编号不用改变，但是要按h = Hash(key) % (N+1)重新计算哈希值。因此系统中一旦有服务器变更，大量的key会被重定位到不同的服务器从而造成大量的缓存不命中。而这种情况在分布式系统中是非常糟糕的。

二、一致性Hash算法

假设某哈希函数H的值空间为0 - (2^32)-1（即哈希值是一个32位无符号整形），将各个服务器进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中三台服务器使用ip地址哈希后在环空间的位置如下：

Snip20170814_48.png

将数据块A、B、C、D的key使用相同的函数H计算出哈希值h，根据h确定此数据在环上的位置

Snip20170814_49.png
从各数据块的位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。
Snip20170814_50.png

可扩展性分析：增加一个server4，D重新指向server4

Snip20170814_51.png

容错性分析：server1挂掉，A重新指向server2

Snip20170814_52.png

综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性

思考：

一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题，此时应该怎么办？有时间我们讨论虚拟节点。