在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括: 轮循算法(Round Robin)、哈希算法(HASH)、最少连接算法(Least Connection)、响应速度算法(Response Time)、加权法(Weighted )等。其中哈希算法是最为常用的算法. 典型的应用场景是
在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括: 轮循算法(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

译者 | 朱先忠审校 | 孙淑娟在我之前的博客中,我们已经了解了如何使用因果树来评估政策的异质处理效应。如果你还没有阅读过,我建议你在阅读本文前先读一遍,因为我们在本文中认为你已经了解了此文中的部分与本文相关的内容。为什么是异质处理效应(HTE:heterogenous treatment effects)呢?首先,对异质处理效应的估计允许我们根据它们的预期结果(疾病、公司收入、客户满意度等)选择提供处理(药物、广告、产品等)的用户(患者、用户、客户等)。换句话说,估计HTE有助于我

译者 | 朱先忠审校 | 孙淑娟引言模型超参数(或模型设置)的优化可能是训练机器学习算法中最重要的一步,因为它可以找到最小化模型损失函数的最佳参数。这一步对于构建不易过拟合的泛化模型也是必不可少的。优化模型超参数的最著名技术是穷举网格搜索和随机网格搜索。在第一种方法中,搜索空间被定义为跨越每个模型超参数的域的网格。通过在网格的每个点上训练模型来获得最优超参数。尽管网格搜索非常容易实现,但它在计算上变得昂贵,尤其是当要优化的变量数量很大时。另一方面,随机网格搜索是一种更快的优化方法,可以提供更好的

如何使用C++中的哈希搜索算法哈希(Hash)搜索算法是一种高效的查找和存储技术,它将关键字通过哈希函数转化为一个固定长度的索引,然后利用这个索引在数据结构中进行搜索。在C++中,我们可以通过使用标准库中的哈希容器和哈希函数来实现哈希搜索算法。本文将介绍如何使用C++中的哈希搜索算法,并提供具体的代码示例。引入头文件和命名空间首先,在使用C++中的哈希搜索算

SimCLR(Simple Framework for Contrastive Learning of Representations)是一种学习图像表示的自监督技术。 与传统的监督学习方法不同,SimCLR 不依赖标记数据来学习有用的表示。 它利用对比学习框架来学习一组有用的特征,这些特征可以从未标记的图像中捕获高级语义信息。SimCLR 已被证明在各种图像分类基准上优于最先进的无监督学习方法。 并且它学习到的表示可以很容易地转移到下游任务,例如对象检测、语义分割和小样本学习,只需在较小的标记

如何用Python编写哈希查找算法?哈希查找算法,又称为散列查找算法,是一种基于哈希表的数据查找方法。相比于线性查找和二分查找等传统查找算法,哈希查找算法具有更高的查找效率。在Python中,我们可以使用字典(dictionary)来实现哈希表,进而实现哈希查找。哈希查找算法的基本思想是将待查找的关键字通过哈希函数转换成一个索引值,然后根据索引值在哈希表中查

Python底层技术揭秘:如何实现哈希算法,需要具体代码示例摘要:哈希算法是计算机领域中常用的技术之一,用于快速确定数据的唯一标识。Python作为一门高级语言,提供了许多内建的哈希函数,如hash()函数以及各种散列算法的实现。本文将揭示哈希算法的原理和Python底层实现的细节,并提供具体的代码示例。哈希算法简介哈希算法,又称散列算法,是一种将任意长度的

译者 | 李睿 审校 | 孙淑娟随着机器学习成为人们每天都在使用的很多应用程序的一部分,人们越来越关注如何识别和解决机器学习模型的安全和隐私方面的威胁。 然而,不同机器学习范式面临的安全威胁各不相同,机器学习安全的某些领域仍未得到充分研究。尤其是强化学习算法的安全性近年来并未受到太多关注。 加拿大的麦吉尔大学、机器学习实验室(MILA)和滑铁卢大学的研究人员开展了一项新研究,主要侧重于深度强化学习算法的隐私威胁。研究人员提出了一个框架,用于测试强化学习模型对成员推理攻击的脆弱性。 研究

目前如谷歌新闻等很多应用都将聚类算法作为主要的实现手段,它们能利用大量的未标注数据构建强大的主题聚类。本文从最基础的 K 均值聚类到基于密度的强大方法介绍了 6 类主流方法,它们各有擅长领域与情景,且基本思想并不一定限于聚类方法。本文将从简单高效的 K 均值聚类开始,依次介绍均值漂移聚类、基于密度的聚类、利用高斯混合和最大期望方法聚类、层次聚类和适用于结构化数据的图团体检测。我们不仅会分析基本的实现概念,同时还会给出每种算法的优缺点以明确实际的应用场景。聚类是一种包括数据点分组的机器学习技术。给


热AI工具

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

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

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

安全考试浏览器
Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

ZendStudio 13.5.1 Mac
功能强大的PHP集成开发环境

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

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具