电子商务网站建设是学什么,wordpress支持视频播放,网页设计师的岗位职责,wordpress 文件结构一致性Hash算法关于一致性Hash算法#xff0c;在我之前的博文中已经有多次提到了#xff0c;MemCache超详细解读一文中”一致性Hash算法”部分#xff0c;对于为什么要使用一致性Hash算法、一致性Hash算法的算法原理做了详细的解读。算法的具体原理这里再次贴上#xff1a;…一致性Hash算法关于一致性Hash算法在我之前的博文中已经有多次提到了MemCache超详细解读一文中”一致性Hash算法”部分对于为什么要使用一致性Hash算法、一致性Hash算法的算法原理做了详细的解读。算法的具体原理这里再次贴上先构造一个长度为2^32的整数环(这个环被称为一致性Hash环)根据节点名称的Hash值(其分布为[0, 2^32-1])将服务器节点放置在这个Hash环上然后根据数据的Key值计算得到其Hash值(其分布也为[0, 2^32-1])接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点完成Key到服务器的映射查找。这种算法解决了普通余数Hash算法伸缩性差的问题可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。当然万事不可能十全十美一致性Hash算法比普通的余数Hash算法更具有伸缩性但是同时其算法实现也更为复杂本文就来研究一下如何利用Java代码实现一致性Hash算法。在开始之前先对一致性Hash算法中的几个核心问题进行一些探究。数据结构的选取一致性Hash算法最先要考虑的一个问题是构造出一个长度为2^32的整数环根据节点名称的Hash值将服务器节点放置在这个Hash环上。那么整数环应该使用何种数据结构才能使得运行时的时间复杂度最低首先说明一点关于时间复杂度常见的时间复杂度与时间效率的关系有如下的经验规则O(1) O(log2N) O(n) O(N * logN) O(N^2) O(N^3) 2^N 3^N N!一般来说前四个效率比较高中间两个差强人意后三个比较差(只要N比较大这个算法就动不了了)。OK继续前面的话题应该如何选取数据结构我认为有以下几种可行的解决方案。1、解决方案一排序List我想到的第一种思路是算出所有待加入数据结构的节点名称的Hash值放入一个数组中然后使用某种排序算法将其从小到大进行排序最后将排序后的数据放入List中采用List而不是数组是为了结点的扩展考虑。之后待路由的结点只需要在List中找到第一个Hash值比它大的服务器节点就可以了比如服务器节点的Hash值是[0,2,4,6,8,10]带路由的结点是7只需要找到第一个比7大的整数也就是8就是我们最终需要路由过去的服务器节点。如果暂时不考虑前面的排序那么这种解决方案的时间复杂度(1)最好的情况是第一次就找到时间复杂度为O(1)(2)最坏的情况是最后一次才找到时间复杂度为O(N)平均下来时间复杂度为O(0.5N0.5)忽略首项系数和常数时间复杂度为O(N)。但是如果考虑到之前的排序我在网上找了张图提供了各种排序算法的时间复杂度2、解决方案二遍历List既然排序操作比较耗性能那么能不能不排序可以的所以进一步的有了第二种解决方案。解决方案使用List不变不过可以采用遍历的方式(1)服务器节点不排序其Hash值全部直接放入一个List中(2)带路由的节点算出其Hash值由于指明了”顺时针”因此遍历List比待路由的节点Hash值大的算出差值并记录比待路由节点Hash值小的忽略(3)算出所有的差值之后最小的那个就是最终需要路由过去的节点在这个算法中看一下时间复杂度1、最好情况是只有一个服务器节点的Hash值大于带路由结点的Hash值其时间复杂度是O(N)O(1)O(N1)忽略常数项即O(N)2、最坏情况是所有服务器节点的Hash值都大于带路由结点的Hash值其时间复杂度是O(N)O(N)O(2N)忽略首项系数即O(N)所以总的时间复杂度就是O(N)。其实算法还能更改进一些给一个位置变量X如果新的差值比原差值小X替换为新的位置否则X不变。这样遍历就减少了一轮不过经过改进后的算法时间复杂度仍为O(N)。总而言之这个解决方案和解决方案一相比总体来看似乎更好了一些。3、解决方案三二叉查找树抛开List这种数据结构另一种数据结构则是使用二叉查找树。当然我们不能简单地使用二叉查找树因为可能出现不平衡的情况。平衡二叉查找树有AVL树、红黑树等这里使用红黑树选用红黑树的原因有两点1、红黑树主要的作用是用于存储有序的数据这其实和第一种解决方案的思路又不谋而合了但是它的效率非常高2、JDK里面提供了红黑树的代码实现TreeMap和TreeSet另外以TreeMap为例TreeMap本身提供了一个tailMap(K fromKey)方法支持从红黑树中查找比fromKey大的值的集合但并不需要遍历整个数据结构。使用红黑树可以使得查找的时间复杂度降低为O(logN)比上面两种解决方案效率大大提升。为了验证这个说法我做了一次测试从大量数据中查找第一个大于其中间值的那个数据比如10000数据就找第一个大于5000的数据(模拟平均的情况)。看一下O(N)时间复杂度和O(logN)时间复杂度运行效率的对比因为再大就内存溢出了所以只测试到4000000数据。可以看到数据查找的效率TreeMap是完胜的其实再增大数据测试也是一样的红黑树的数据结构决定了任何一个大于N的最小数据它都只需要几次至几十次查找就可以查到。当然明确一点有利必有弊根据我另外一次测试得到的结论是为了维护红黑树数据插入效率TreeMap在三种数据结构里面是最差的且插入要慢上5~10倍。Hash值重新计算服务器节点我们肯定用字符串来表示比如”192.168.1.1″、”192.168.1.2″根据字符串得到其Hash值那么另外一个重要的问题就是Hash值要重新计算这个问题是我在测试String的hashCode()方法的时候发现的不妨来看一下为什么要重新计算Hash值/*** String的hashCode()方法运算结果查看* author 哓哓**/public class StringHashCodeTest { public static void main(String[] args) { System.out.println(192.168.0.0:111的哈希值 192.168.0.0:1111.hashCode()); System.out.println(192.168.0.1:111的哈希值 192.168.0.1:1111.hashCode()); System.out.println(192.168.0.2:111的哈希值 192.168.0.2:1111.hashCode()); System.out.println(192.168.0.3:111的哈希值 192.168.0.3:1111.hashCode()); System.out.println(192.168.0.4:111的哈希值 192.168.0.4:1111.hashCode()); }}我们在做集群的时候集群点的IP以这种连续的形式存在是很正常的。看一下运行结果为192.168.0.0:111的哈希值1845870087192.168.0.1:111的哈希值1874499238192.168.0.2:111的哈希值1903128389192.168.0.3:111的哈希值1931757540192.168.0.4:111的哈希值1960386691这个就问题大了[0,2^32-1]的区间之中5个HashCode值却只分布在这么小小的一个区间什么概念[0,2^32-1]中有4294967296个数字而我们的区间只有122516605从概率学上讲这将导致97%待路由的服务器都被路由到”192.168.0.1″这个集群点上简直是糟糕透了另外还有一个不好的地方规定的区间是非负数String的hashCode()方法却会产生负数(不信用”192.168.1.0:1111″试试看就知道了)。不过这个问题好解决取绝对值就是一种解决的办法。综上String重写的hashCode()方法在一致性Hash算法中没有任何实用价值得找个算法重新计算HashCode。这种重新计算Hash值的算法有很多比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法用别的Hash算法也可以比如FNV1_32_HASH算法的计算效率就会高一些。一致性Hash算法实现版本1不带虚拟节点使用一致性Hash算法尽管增强了系统的伸缩性但是也有可能导致负载分布不均匀解决办法就是使用虚拟节点代替真实节点第一个代码版本先来个简单的不带虚拟节点。下面来看一下不带虚拟节点的一致性Hash算法的Java代码实现/** * 不带虚拟结点的一致性Hash算法 * author 哓哓 * */public class ConsistentHashWithoutVN { /** * 待加入Hash环的服务器列表 */ private static String[] servers { 192.168.0.0:111
