文档章节

一致性哈希算法以及其PHP实现

刘纪君
 刘纪君
发布于 2014/11/18 09:50
字数 1404
阅读 21
收藏 1
点赞 0
评论 0
在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括:  轮循算法(Round Robin)、哈希算法(HASH)、最少连接算法(Least Connection)、响应速度算法(Response Time)、加权法(Weighted )等。其中哈希算法是最为常用的算法.

    典型的应用场景是: 有N台服务器提供缓存服务,需要对服务器进行负载均衡,将请求平均分发到每台服务器上,每台机器负责1/N的服务。

    常用的算法是对hash结果取余数 (hash() modN):对机器编号从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实现。

© 著作权归作者所有

共有 人打赏支持
刘纪君
粉丝 29
博文 78
码字总数 59637
作品 0
郑州
高级程序员
memcached精讲第二部

老男孩之memcached精讲第二部 1.1Memcache 服务器的安装。 Linux,FreeBSD,Solaris,windows。这里以Centos6.4为例进行说明。 软件地址:Memcached 下载地址: libevent 下载地址: 网友安装...

妙曼 ⋅ 2017/02/20 ⋅ 0

memcache视频教程分享下载

课程目录: 01-memcahced介绍及安装 02-add命令详细介绍 03-增删改查及统计命令 04-memcached内存分配机制 05-LRU删除机制 06-Linux下编译memcached 07-key value的长度限制 08-windows下安装...

查看地址 ⋅ 2014/11/19 ⋅ 1

Memcache缓存服务器(Nginx+php+Memcache+MySQL)

一、MemCache简介: MemCache是一个自由、源码开放、高性能、分布式的分布式内存对象缓存系统,用于动态Web应用以减轻数据库的负载。它通过在内存中缓存数据和对象来减少读取数据库的次数,从...

何小帅 ⋅ 2017/03/24 ⋅ 0

一致性哈希算法及其在分布式系统中的应用

摘要 本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题场景,借此介绍一致性哈希算法以及...

abing_hu ⋅ 2013/09/01 ⋅ 0

一致性哈希算法以及其PHP实现

在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括: 轮循算法(Round Robin)、哈希算法(HASH)、最少连接算法(Least Connection)、响应速度算法(Response Time)、加权法(...

晨曦之光 ⋅ 2012/03/09 ⋅ 0

PHP: 深入了解一致性哈希

随着memcache、redis以及其它一些内存K/V数据库的流行,一致性哈希也越来越被开发者所了解。因为这些内存K/V数据库大多不提供分布式支持(本文以redis为例),所以如果要提供多台redis server来...

陈亦 ⋅ 2014/02/27 ⋅ 15

[算法] 从 Memcached 分布式应用看一致性哈希散列函数的选择

一致性哈希算法来源于 P2P 网络的路由算法,目前主流的 P2P 软件就是利用我们所熟知的 DHT (Distributed Hash Table,分布式哈希表) 来定位整个分布式网络的信息,另外此算法在目前火热的云计...

长平狐 ⋅ 2012/11/19 ⋅ 0

一致性哈希及其 Python 实现

声明:本文仅限于简书发布,其他第三方网站均为盗版,原文地址: 一致性哈希及其 Python 实现 记得之前看一些集群数据库或者和集群相关的文章和书籍的时候,总是会有人提到一致性哈希这个东西...

yetship ⋅ 2017/09/27 ⋅ 0

哈希分布与一致性哈希算法简介

前言 在我们的日常web应用开发当中memcached可以算作是当今的标准开发配置了。相信memcache的基本原理大家也都了解过了,memcache虽然是分布式的应用服务,但分布的原则是由client端的api来决...

晨曦之光 ⋅ 2012/03/09 ⋅ 0

聊聊jump consistent hash

序 本文主要简介一下jump Consistent hash。 jump consistent hash jump consistent hash是一致性哈希的一种实现,论文见A Fast, Minimal Memory, Consistent Hash Algorithm 经典的一致性哈...

xixicat ⋅ 2017/11/11 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

懒惰根本就不存在

简评:芝加哥大学心理学教授,懒惰根本就不存在。(本文表面讲行为心理学实则讲教育) 金句:以好奇而不是判断来回应一个人的无效行为,是非常有帮助的。 本文「我」代表原作者 E Price。 自...

极光推送 ⋅ 23分钟前 ⋅ 0

Excel提取单元格中最后一个“.”后面的数据

java.lang.String ----- String =TRIM((MID(SUBSTITUTE(B2,".",REPT(" ",99)),(LEN(B2)-LEN(SUBSTITUTE(B2,".","")))*99,99)))...

klog ⋅ 25分钟前 ⋅ 0

mac远程桌面

下载安装remote-desktop-mac Mac beta 客户端 mac通过远程桌面访问windows服务器。

亚林瓜子 ⋅ 30分钟前 ⋅ 0

firrtl

动手---sbt(2)之后,再回头看 chisel第一个实验,根据 https://github.com/freechipsproject/firrtl 发现firrtl没有执行sbt assembly命令,重新执行这个命令,结果成功。如下图: joe@joe-As...

whoisliang ⋅ 34分钟前 ⋅ 0

NIO

一、通道(Channel):用于源节点与目标节点的连接。在 Java NIO 中负责缓冲区中数据的传输。Channel 本身不存储数据,因此需要配合缓冲区进行传输。 二、通道的主要实现类 java.nio.channel...

stars永恒 ⋅ 34分钟前 ⋅ 0

Android悬浮窗的实现

0. 前言   现在很多应用都使用到悬浮窗,例如微信在视频的时候,点击Home键,视频小窗口仍然会在屏幕上显示。这个功能在很多情况下都非常有用。那么今天我们就来实现一下Android悬浮窗,以...

猴亮屏 ⋅ 34分钟前 ⋅ 0

日志采集中的关键技术分析

概述 日志从最初面向人类演变到现在的面向机器发生了巨大的变化。最初的日志主要的消费者是软件工程师,他们通过读取日志来排查问题,如今,大量机器日夜处理日志数据以生成可读性的报告以此...

tqyin ⋅ 36分钟前 ⋅ 0

使用Navicat将数据导出为text文本 然后再导入

将数据导出为text文本效率很高 1. 准备工作 1.1 准备表结构 1.2 目标库 执行生成表结构sql 2.将表数据导出为text文本 生成的text文本 3. 目标库 导入text 4.效果...

Lucky_Me ⋅ 41分钟前 ⋅ 0

IntelliJ IDEA 乱码解决方案 (项目代码、控制台等)

文章介绍了idea下,项目乱码、控制台乱码及运行tomcat控制台乱码的解决方案,文章链接:https://www.cnblogs.com/vhua/p/idea_1.html

Funcy1122 ⋅ 44分钟前 ⋅ 0

IDEA使用sonarLint

一、IDEA如何安装SonarLint插件 1.打开 Idea 2.点击【File】 3.点击【Settings】 4.点击【Plugins】 5.在搜索栏中输入“sonarlint”关键字 6.点击【Install】进行安装 7.重启Idea 二、IDEA如...

开源中国成都区源花 ⋅ 49分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部