搜索
首页后端开发php教程一致性哈希算法以及其PHP实现详细解析_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实现。点击下载

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
PHP和Python:解释了不同的范例PHP和Python:解释了不同的范例Apr 18, 2025 am 12:26 AM

PHP主要是过程式编程,但也支持面向对象编程(OOP);Python支持多种范式,包括OOP、函数式和过程式编程。PHP适合web开发,Python适用于多种应用,如数据分析和机器学习。

PHP和Python:深入了解他们的历史PHP和Python:深入了解他们的历史Apr 18, 2025 am 12:25 AM

PHP起源于1994年,由RasmusLerdorf开发,最初用于跟踪网站访问者,逐渐演变为服务器端脚本语言,广泛应用于网页开发。Python由GuidovanRossum于1980年代末开发,1991年首次发布,强调代码可读性和简洁性,适用于科学计算、数据分析等领域。

在PHP和Python之间进行选择:指南在PHP和Python之间进行选择:指南Apr 18, 2025 am 12:24 AM

PHP适合网页开发和快速原型开发,Python适用于数据科学和机器学习。1.PHP用于动态网页开发,语法简单,适合快速开发。2.Python语法简洁,适用于多领域,库生态系统强大。

PHP和框架:现代化语言PHP和框架:现代化语言Apr 18, 2025 am 12:14 AM

PHP在现代化进程中仍然重要,因为它支持大量网站和应用,并通过框架适应开发需求。1.PHP7提升了性能并引入了新功能。2.现代框架如Laravel、Symfony和CodeIgniter简化开发,提高代码质量。3.性能优化和最佳实践进一步提升应用效率。

PHP的影响:网络开发及以后PHP的影响:网络开发及以后Apr 18, 2025 am 12:10 AM

PHPhassignificantlyimpactedwebdevelopmentandextendsbeyondit.1)ItpowersmajorplatformslikeWordPressandexcelsindatabaseinteractions.2)PHP'sadaptabilityallowsittoscaleforlargeapplicationsusingframeworkslikeLaravel.3)Beyondweb,PHPisusedincommand-linescrip

PHP类型提示如何起作用,包括标量类型,返回类型,联合类型和无效类型?PHP类型提示如何起作用,包括标量类型,返回类型,联合类型和无效类型?Apr 17, 2025 am 12:25 AM

PHP类型提示提升代码质量和可读性。1)标量类型提示:自PHP7.0起,允许在函数参数中指定基本数据类型,如int、float等。2)返回类型提示:确保函数返回值类型的一致性。3)联合类型提示:自PHP8.0起,允许在函数参数或返回值中指定多个类型。4)可空类型提示:允许包含null值,处理可能返回空值的函数。

PHP如何处理对象克隆(克隆关键字)和__clone魔法方法?PHP如何处理对象克隆(克隆关键字)和__clone魔法方法?Apr 17, 2025 am 12:24 AM

PHP中使用clone关键字创建对象副本,并通过\_\_clone魔法方法定制克隆行为。1.使用clone关键字进行浅拷贝,克隆对象的属性但不克隆对象属性内的对象。2.通过\_\_clone方法可以深拷贝嵌套对象,避免浅拷贝问题。3.注意避免克隆中的循环引用和性能问题,优化克隆操作以提高效率。

PHP与Python:用例和应用程序PHP与Python:用例和应用程序Apr 17, 2025 am 12:23 AM

PHP适用于Web开发和内容管理系统,Python适合数据科学、机器学习和自动化脚本。1.PHP在构建快速、可扩展的网站和应用程序方面表现出色,常用于WordPress等CMS。2.Python在数据科学和机器学习领域表现卓越,拥有丰富的库如NumPy和TensorFlow。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
1 个月前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
1 个月前By尊渡假赌尊渡假赌尊渡假赌
威尔R.E.P.O.有交叉游戏吗?
1 个月前By尊渡假赌尊渡假赌尊渡假赌

热工具

WebStorm Mac版

WebStorm Mac版

好用的JavaScript开发工具

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)