一致性哈希算法以及其PHP实现
在做服务器负载均衡时候可供选择的负载均衡的算法有很多，包括： 轮循算法（Round Robin）、哈希算法（HASH）、最少连接算法（Least Connection）、响应速度算法（Response Time）、加权法（Weighted ）等。其中哈希算法是最为常用的算法.
典型的应用场景是： 有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务。
常用的算法是对hash结果取余数 (hash() mod N)：对机器编号从0到N-1，按照自定义的hash()算法，对每个请求的hash()值按N取模，得到余数i，然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；如果新增一台机器，会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言，这通常是不可接受的颠簸（因为这意味着大量缓存的失效或者数据需要转移）。那么，如何设计一个负载均衡策略，使得受到影响的请求尽可能的少呢？
在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法，可以说Consistent Hashing 是分布式系统负载均衡的首选算法。
1、Consistent Hashing算法描述
下面以Memcached中的Consisten Hashing算法为例说明。
由于hash算法结果一般为unsigned int型，因此对于hash函数的结果应该均匀分布在[0,232-1]间，如果我们把一个圆环用232 个点来进行均匀切割，首先按照hash(key)函数算出服务器（节点）的哈希值， 并将其分布到0～232的圆上。
用同样的hash(key)函数求出需要存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器（节点）上。
Consistent Hashing原理示意图新增一个节点的时候，只有在圆环上新增节点逆时针方向的第一个节点的数据会受到影响。删除一个节点的时候，只有在圆环上原来删除节点顺时针方向的第一个节点的数据会受到影响，因此通过Consistent Hashing很好地解决了负载均衡中由于新增节点、删除节点引起的hash值颠簸问题。
Consistent Hashing添加服务器示意图虚拟节点（virtual nodes）：之所以要引进虚拟节点是因为在服务器（节点）数较少的情况下（例如只有3台服务器），通过hash(key)算出节点的哈希值在圆环上并不是均匀分布的（稀疏的），仍然会出现各节点负载不均衡的问题。虚拟节点可以认为是实际节点的复制品（replicas），本质上与实际节点实际上是一样的（key并不相同）。引入虚拟节点后，通过将每个实际的服务器（节点）数按照一定的比例(例如200倍)扩大后并计算其hash(key)值以均匀分布到圆环上。在进行负载均衡时候，落到虚拟节点的哈希值实际就落到了实际的节点上。由于所有的实际节点是按照相同的比例复制成虚拟节点的，因此解决了节点数较少的情况下哈希值在圆环上均匀分布的问题。
虚拟节点对Consistent Hashing结果的影响
从上图可以看出，在节点数为10个的情况下，每个实际节点的虚拟节点数为实际节点的100-200倍的时候，结果还是很均衡的。
第3段中有这些文字：“但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；”
为何是 (N-1)/N 呢？解释如下：
比如有 3 台机器，hash值 1-6 在这3台上的分布就是：
host 1: 1 4
host 2: 2 5
host 3: 3 6
如果挂掉一台，只剩两台，模数取 2 ，那么分布情况就变成：
host 1: 1 3 5
host 2: 2 4 6
可以看到，还在数据位置不变的只有2个： 1，2，位置发生改变的有4个，占共6个数据的比率是 4/6 = 2/3
这样的话，受影响的数据太多了，势必太多的数据需要重新从 DB 加载到 cache 中，严重影响性能
【consistent hashing 的办法】
上面提到的 hash 取模，模数取的比较小，一般是负载的数量，而 consistent hashing 的本质是将模数取的比较大，为 2的32次方减1，即一个最大的 32 位整数。然后，就可以从容的安排数据导向了，那个图还是挺直观的
以下部分为一致性哈希算法的一种PHP实现。
下载地址 ：http://zwzweb.googlecode.com/files/Consistent%20Hashing.php
相关文章：
Linux入门（四）
目录： 1234567891011121314一、根文件系统层级标准FHS二、bash的基础特性（一）1.命令历史 2.命令行补全 3.路径补全 4.命令行展开 5.命令执行的状态结果 6.引用 7.快捷键 三、目录管理相关命令mkdir、rmdir、tree四、引用命令的执行结果五、文…
OSI[七层]与TCP/IP[四层]模型简述简图
OSI参考模型（OSI/RM）的全称是开放系统互连参考模型（Open System Interconnection Reference Model，OSI/RM），它是由国际标准化组织（International Standard Organization，ISO…
中国国际消费电子博览会拥抱转型，全新面貌拭目以待！
2021年9月24—26日，第十九届中国国际消费电子博览会（简称电博会）将在青岛国际会展中心隆重举行，如今距离电博会开幕已不到3个月的时间，全国各地的参展企业跃跃欲试、积极筹备。 长久以来，电博会为全球消费…
Fragment提交transaction导致state loss异常
下面自从Honeycomb发布后，下面栈跟踪信息和异常信息已经困扰了StackOverFlow很久了。 java.lang.IllegalStateException: Can not perform this action after onSaveInstanceState at android.support.v4.app.FragmentManagerImpl.checkStateLoss(FragmentManager.j…
ASP网络编程从入门到精通 下载
《ASP网络编程从入门到精通》 清华大学出版社 特点： 面向ASP零基础读者，循序渐进 全面分析ASP技术细节 用代码描述个个知识点，操作性强 通过典型模块设计，体会ASP的奥妙 通过网上商城购物系统，增加项目开发经验 适合的…
项目Makefile文件模板
整理出来的一个Makefile模板,新增了一个内容,调用gcc生成依赖文件,这样如果某个c文件包含的头文件被更新了,该c文件以及依赖于该c文件的obj文件都会被重新编译.这个模板是按照我习惯的项目文件组织形式进行定义的,我的习惯是头文件放在include文件夹,代码放在src文件夹,目标文件…
小撒、金晨都想拥有！百度全球首款汽车机器人亮相，车内躺着看星星
整理 | 禾木木 出品 | AI科技大本营（ID:rgznai100） 金晨坐了都想带回家的车、无人车出行服务、撒贝宁与祝融号对话等等。 这届百度世界大会真的很惊艳。 8月18日，百度与央视新闻联合举办“AI这时代，星辰大海——百度世界大会2021…
解决oracle11g安装导致数据库无法自动搜集统计信息-转
近期发现个别11G数据库无法自动收集统计信息，部分视图查询结果如下： SQL> select client_name,status from dba_autotask_client where client_name auto optimizer stats collection;CLIENT_NAME STATUS -----------------------------------------…
服务器监控--cacti中英文版安装全解
近段时间一直在整服务器监控方面的东西,以下就是cacti中英文版安装的全过程,各安装包基本都是最新的,基于Centos 5.2平台下安装的!!#!/bin/bash# BY kerryhu# QQ:263205768# MAIL:king_819163.com# BLOG:[url]http://kerry.blog.51cto.com[/url]# Please manual operation yum …
lighttpd1.4.18代码分析
lighttpd1.4.18代码分析(八)--状态机(2)CON_STATE_READ状态posted 2008-09-24 10:50 那谁 阅读(2225) | 评论 (1) 编辑 lighttpd1.4.18代码分析(七)--状态机(1)CON_STATE_REQUEST_START状态posted 2008-09-22 15:10 那谁 阅读(2259) | 评论 (0) 编辑 lighttpd1.4.18代码分析…
惊艳亮相！马斯克发布自研超算 Dojo 芯片、特斯拉人形机器人
编译 | 禾木木 出品 | AI科技大本营（ID:rgznai100） 北京时间 8 月 20 日，特斯拉 AI 日终于开始了！在活动上不仅推出自研计算机系统Dojo 及 D1 芯片，同时还推出了特斯拉的下一个大型项目：人形机器人&#x…
git revert和git reset的区别
git revert 是撤销某次操作，此次操作之前的commit都会被保留git reset 是撤销某次提交，但是此次之后的修改都会被退回到暂存区具体一个例子，假设有三个commit， git st:commit3: add test3.ccommit2: add test2.ccommit1: add test…
python之深浅拷贝
对于 数字 和 字符串 而言，赋值、浅拷贝和深拷贝无意义，因为其永远指向同一个内存地址。 import copy # ######### 数字、字符串 #########n1 123 # n1 "age 10"print(id(n1)) # ## 赋值 ##n2 n1 print(id(n2)) # ## 浅拷贝 ##n2 copy.cop…
linux:关于Linux系统中 CPU Memory IO Network的性能监测
我们知道：系统优化是一项复杂、繁琐、长期的工作.通常监测的子系统有以下这些：CPUMemoryIONetwork下面是常用的监测工具Linux 系统包括很多子系统（包括刚刚介绍的CPU，Memory，IO，Network，等&…
火爆 GitHub！这个 AI 神器究竟有什么魅力？
图像分割（image segmentation）技术是计算机视觉领域的一个重要的研究方向，图像分割是计算机视觉中的一个关键过程。它包括将视觉输入分割成片段以简化图像分析。片段表示目标或目标的一部分，并由像素集或“超像素”组成。图像分割…
HTTP 状态代码
HTTP 状态代码 如果向您的服务器发出了某项请求要求显示您网站21kaiyun.com上的某个网页（例如，当用户通过浏览器访问您的网页时），那么，您的服务器会返回 HTTP 状态代码以响应该请求。 此状态代码提供了有关请求状态的信…
[Web 开发] 定制IE下载对话框的按钮（打开/保存）
下图常见的IE 下载对话框， 上面有3个主要按钮： Run （打开）， Save（保存）， Cancel （取消） 在某些情况下， 你不希望用户点击“Run” 按钮 或者 “Sav…
25 年汽车技术老兵亲述，自动驾驶新驶向
受访者 | 俞斌 记者 | 伍杏玲 出品 | AI科技大本营（ID:rgznai100） 在 IT 发展长河中，我们面对过不同的技术风口，历史终究大浪淘沙沉者为金。其中“自动驾驶”似乎是经久不衰的“风口”，成为人类的终极追求之一…
当你学了现在的忘了前面的
我怀疑我的智商应该不是很高，要不然我也不会学的如此狼狈。虽然我总是能很好的理解现在所学的知识点，但是我就是记不住，当下次再次需要上次的知识点来解决问题的时候，我总是忘的差不多了，要不就是没把握和对不对的问题…
HTTP referer
HTTP Referer是header的一部分，当浏览器向web服务器发送请求的时候，一般会带上Referer，告诉服务器我是从哪个页面链接过来的，服务器籍此可以获得一些信息用于处理。比如从我主页上链接到一个朋友那里，他的服务器就能够…
设置grep高亮显示匹配项
grep是个非常高频的命令，我们通过给它设置别名，来把匹配项区分出来，这样可以更直观。 设置前： 12[rootzabbix ~]# /sbin/ifconfig eth0 | grep inet addr inet addr:192.168.88.66 Bcast:192.168.88.255 Mask:255.255.255.0 设置…
PHP之源码目录结构
PHP之所以能在web开发语言中排名靠前，不仅仅是因为语法简单，上手容易。我个人认为更多是因为其语言本身的：模块的易扩展性，可维护性以及内存安全管理等特点。写过PHP的程序员不一定都知道：PHP是如何执行的？…
SSAS系列——【07】多维数据（查询Cube）
原文:SSAS系列——【07】多维数据（查询Cube）1、什么是MDX？ MDX叫做“多维表达式”，是一种查询语言，是一种和SQL类似的查询语言，它基于 XML for Analysis (XMLA) 规范，并带有特定于 SQL Server A…
什么是图数据库？图数据库实践与创新浅析
近日，中国工程院院士，清华大学计算机科学与技术系教授郑纬民先生，在人民日报发表文章《把握图数据库自主创新机遇》，建议国内科研学者和工程人员，要在图数据库的理论研究与工程研发上坚持自主创新道路，确保…
C# 对应 Oracle 存储过程 的 SYS_REFCURSOR 应该 传入什么类型的参数?
Oracle中scott用户下创建存储过程：(注：从9i开始有了sys_refcursor这种类型，在以前的Oracle版本中需要使用REF CURSOR,并且还需放在一个程序包中)create or replace procedure sp_getdept(result out sys_refcursor)asbeginopen result for se…
Fedora 15 安装与配置一览
Fedora 15 将于2011.5.24日发布，今日离正式版发布还有4天。笨兔兔这里提前给大家支招用好Fedora 15。下面是笨兔兔在安装、配置Fedora 15 过程中的小结，希望给大家配置自己的Fedora 15 带来方便。仅供参考，如有错误，敬请指出。 『…
Win7封装无损廋身清单
整理了一下，大致如下。清理不会伤及系统功能。娱乐性的东西建议删除，因为这些不是功能性的，包括示例视频、示例音乐和一些主题图片以及一些系统自带的游戏。另外一些属于安装过程中产生的，重装封装不需要这些文件，对比…
苹果新算法已混进 iOS 14.3！CSAM 检测技术再遭网友争议
整理 | 禾木木、郑丽媛 出品 | AI科技大本营（ID:rgznai100） 苹果宣布即将推出 CSAM 检测系统时，遭到了 4000 多个组织及个人的公开反对，他们质疑苹果会破坏用户隐私和端到端加密机制。一位 Reddit 用户发现 CSAM 算法竟已被悄悄地…
2.最详细的WSDD配置文件注释
https://blog.csdn.net/u011063151/article/details/52590282转载于:https://www.cnblogs.com/sharpest/p/7851185.html
CloudStack部署篇二 高级网络设置
CloudStack 4.2.1版本基础安装： http://51log.blog.51cto.com/6076767/1598046测试默认UI访问 http:ip1:8080/client/选择【我以前使用过cloudstack,跳过配置指南】；开始应用网络配置；一、 高级网络部署管理服务器 （mangermant m…