负载均衡器之集群缓存算法hash知识补充

一、负载均衡知识补充

常见的调度算法

  rr轮询:round-robin,默认调度算法,静态调度算法,按照客户端请求顺序逐一分配到不同的后端节点服务器,宕机的服务器会被自动从节点服务器池中剔除。
  wrr权重轮询:静态调度算法,在rr轮询算法的基础上加上权重,权重和用户访问成正比,权重值越大,被转发的请求也就越多
  ip_hash:静态调度算法,每个请求按客户端IP的Hash值分配,当新的请求到达时,先将其客户端IP通过哈希算法计算出一个值,在随后的客户端请求中,客户端IP的哈希值只要相同,就会被分配到同一台服务器,可以解决动态网页的session共享问题,但也会引起分配不均的弊端
  fair:动态调度算法,此算法会根据后端节点服务器的响应时间来分配请求,响应时间短的优先分配,可以依据页面大小和加载时间舱段智能地进行负载均衡,也就是根据后端服务器的响应时间来分配请求,响应时间短的优先分配。需要下载Nginx的相关模块upstream_fair
  least_conn:根据后端节点的连接数来决定分配情况,哪个机器连接数少就分发
  url_hash:根据访问URL的hash结果来分配请求的,让每个URL定向到同一个后端服务器,后端服务器为缓存服务器时效果显著,如果需要使用这种调度算法,必须安装Nginx的hash模块软件包
  一致性hash:一般用于代理后端业务为缓存服务(squid,memNoded)的场景,通过将用户请求的uri或者指定字符串进行计算,然后调度到后端的服务器上,此后任何用户查找同一个uri或者指定字符串都会被调度到这一台服务器上,因此后端的每个节点缓存的内容都是不同的,一致性hash算法可以解决后端某个或者几个节点宕机后,缓存的数据动荡最小。

负载均衡设备的URL哈希(HASH)功能主要应用在2种场合:
  url hash架构对url进行一次hash算法,然后通过hash结果找到对应的服务器。因为针对单一个url的hash结果是一样的,所以理论上这个url会被永久分配到固定的一台服务器上。

  1)大型网站。大型网站为了提高访问速率,将视频和图片等可缓存的内容缓存到CDN节点。每个CDN节点有很多台缓存服务器,前端配置负载均衡器进行流量分担。为了提高缓存服务器的存储效率和命中率,负载均衡器通常选择URL_HASH算法分配流量到缓存服务器。正常的情况下,不同缓存服务器所缓存内容是不同的,而相同URL的访问一定会到达同一台缓存服务器。
  2)互联网出口。可以是运营商城域网出口,也可以是大型企业的出口。为了提高访问速度,负载均衡设备与缓存配合将视频和图片等静态内容缓存到本地。与网站应用类似,URL HASH可以提高缓存效率和命中率。

负载均衡url hash 集中应用架构:

  1)基于dns的hash架构
  2)基于haproxy的自动hash架构
  3)基于nginx的手动hash架构

1.1 普通hash(url hash)应用于缓存集群的问题
案例:-问题描述:
  例如手机朋友网有n个服务器,为了方便用户的访问会在服务器上缓存数据,因此用户每次访问的时候最好能保持访问同一台服务器,已有的做法是根据server|Pindex[QQNUM%n] 得到的请求的服务器,这中方法很方便将用户分到同的服务器上,但是如果一台服务器挂掉了,那么n就变成n-1 那么 server|Pindex[QQNUM%n]与server|Pindex[QQNUM%(n-1)]基本都不一样了,所以太多的用户的请求都会转到其他服务器,这样会发生大量的访问错误。
问:如何改进或者换一种方法,使得:

  1)	一台服务器挂掉后,不会造成大面积的访问错误
  2)	原有的访问基本还是停留在同一台服务器上
  3)	尽量考虑负载均衡

分析:
  URL_hash命中率很高,同一个URL不会去找别的,万一有一个挂了,那么真个hash算法就会变了,跟后端数量有关系,当挂了一台机器,那么算法就变了,那么它可能去找其他机器,所有的web缓存都会失效,又会重新缓存重新排!导致后端存储NFS压力很大,因此有个设置为down的功能,会计数,只是导致宕掉的那台机器去找NFS,其他的不会变化!
  为了解决上述问题,又一个作为缓存的终极算法叫做一致性hash算法,这个是解决缓存问题最好算法 consistent hashing.
解决思路:采用一致性哈希方法可以解决此问题!
1.2 一致性hash介绍及解决缓存集群问题的原理简介
1.基本的场景
  比如有你N个Node服务器(后面简称Node)那么如何将一个对象object 映射到N个Node上面呢?你很可能 hash(object)%N一切都运行正常,再考虑如下的两种情况:

  1)一个Node 服务器m down掉了(实际应用中必须要考虑这种情况)这样所有映射到Node  m 的对象都会失效,怎么办,需要把Node m 从Node中移除,这个时候Node变成 N-1台,映射公式也变了hash(object)%(N-1);
  2)如果访问加重,需要添加Node,这个时候 Node是N+1台,映射公式就变成了 hash (object)%(N+1)

小结:
  说明如果突然之间几乎所有的Node都失效了,对于服务器而言,这就是一场灾难,洪水般的访问就会直接冲向后台服务器。
  我们再来考虑第三个问题,由于硬件能力越来越强,你可想让后面添加的节点多做点活,显然上面的hash算法也做不到。
  那么问题来了,有什么方法可以改变这个情况呢? 它来了===》consistent hashing
好了,上面例子铺垫完毕,下面我们一起来看下 一致性hash算法。
1.2.1 一致性hash性质
良好的分布式hash系统汇总的一致性hash算法应该满足以下几个方面
  1)平衡性(blance)
  平衡性是指哈希的结果能够尽可能分不到所有的缓冲区中,这样可以使用所有的缓冲区都能利用,很多哈希算法都能满足这一条件。
  2)单调性(monotonicity)
  单调性是指如果有一些内容通过hash分派到了相应的缓冲区中,又有新的缓冲加入到系统中。哈希的结果能保证原有分配的内容可以映射到新的缓冲区中去,而不会映射到旧的缓冲集合中的其他缓冲区中。
  这点上面的hash算法和hash (object)%N 难以满足单调性的要求。
  3)分散性(spread)
  在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中一部分,当终端希望通过hash过程将内容映射到缓存区上时,由于不同的终端所见的缓存范围又能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不容的缓冲区中,这种情况显然是应该避免的,因为把相同的内容存储到不同的缓存区中,降低了系统存储的效率。
  分散性的定义就是上述情况发生的严重程度,好的哈希算法应该能够尽量避免不一致的情况发生,也就是尽量降低分散性。
  4)负载(load)
  负载的问题实际上是从另外一个角度看待分散性问题,既然不容的终端可能把相同的内容映射到不容的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射到不同的内容。与分散性一样,这种情况也是应该避免的,因此好的哈希算法应该能够尽量降低缓冲区的负荷。
  5)平滑性(smoothness)
平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。
1.2.2 一致性hash原理
下面就用5个步骤简单讲解 consietent hashing 算法的基本原理
1)环形hash空间
  考虑通常的hash算法都是将value 映射到一个32位的key值,也就是(0~2的32次方-1)数值空间,我们可以将这个空间想象一个首(0) 一个尾(2的32次方-1)

2)把对象应映射到hash空间
  接来下考虑4个对象, object1~object4 ,通过hash函数计算出hash的key值,在环上分布。

Hash(object1)=key1;
Hash(object2)=key2;
Hash(object3)=key3;
Hash(object4)=key4;

3)把Node映射到hash空间
Consistent hashing的基本思想就是将对象和Node都映射到同一个hash数值空间中,并且使用相同的hash算法。
  假设当前 A,B和C,D 共4台ceche, 那么映射结果如下,他们在hash空间中,以对应的hash值排列。Node的hash计算,一般的方法可以使用Node机器的IP地址或者机器名作为hash输入

Hash (NodeA) =keyA;
Hash (NodeB) =keyB;
Hash (NodeC) =keyC;
Hash (NodeD) =keyD;


4)把对象映射到Node
  现在Node和对象都已经通过同一个hash算法映射数值到hash数值空间中了,接来下要考虑就是如何将对象映射到Node上面了、
在这个环形空间中,如果沿着顺时针从对象的key值出发,直到遇到第一个Node,那么就将值存储在这个Node上,以为对象和Node的hash值是固定的,,因此这个Node和object3对应的NodeC ,object4对应的NodeB;

5)考察ceche的变动
前面说过,通过hash然后求余的方法带来的最大问题就在于不能满足单调性,当Node变动时,Node会失效,进而对后台的服务器造成巨大的冲击,那么我们现在来分析分析 consistent hashing 算法。

a.移除Node
假如NodeB 挂掉了,根据上面降到的映射方法,这时受影响将仅是那些本来映射到NodeB上面那些对象。
因此这里仅需要变动对象object4 将其重新映射到Node上即可。

平衡性说明:
  平衡性是指哈希的结果能够尽可能分不到所有的缓冲区中,这样使得所有的服务器缓存空间都被利用。
  hash算法并不能保证绝对的平衡,如果Node少得话,对象并不能被均匀的映射到Node上。
为了解决这种情况。consistent hashing 引入了”虚拟节点”的概念。
“虚拟节点”:virtual node
  是实际节点在hash空间的复制品(relica),一个实际节点应若干个虚拟节点,这个对应数也称为”复制个数” ”虚拟节点”在hash空间以hash值排列。
查询对象所在的node对应关系:

总结:
  一致性hash的作用:可以确保宕机几点,新增服务器,或者整个缓存的动荡最小,还可以解决缓存不太平衡的问题,提高整体的命中率。

发表评论

发表评论

*

沙发空缺中,还不快抢~