哈希算法(2
Varsion

负载均衡

常见的负载均衡算法包括轮询、随机、加权轮询等

那么如何实现一个会话粘滞的负载均衡算法。也就是说,需要在同一个客户端,在一次会话中的所有请求路由都同步到同一个服务器上。

最直接的办法就是维护一张客户端IP地址胡总和会话ID与服务器编号的映射关系的映射关系表。客户端发出的每次请求,都要现在该表中查找应该路由到的服务器编号,然后再请求编号对应的服务器。这是个简单直观的方法,同时也存在几个弊端。

  • 如果客户端很多,映射表可能会很大,比较浪费内存空间
  • 客户端下线、上线,服务器扩容、缩容都会导致映射失效,这样维护映射表的成本就会很大

哈希算法可以完美的解决这些问题。

可以通过哈希算法,对客户端IP地址或者会话ID计算哈希值,将得到的哈希值与服务器列表的大小进行去模运算,最终得到的值就是应该被路由到的服务器编号。

数据分片

假如现在有1T的记录了用户数搜索关键词的日志文件,我们应该如何快速统计出每个关键词的搜索量。

存在有两个问题,一是搜索日志文件很大,没办法放到一台机器的内存中,二是如果只用一台机器去处理这个工作,时间会很长。

针对这两个难点,可以先对数据进行分片,然后采用多台机器处理的方法,来提高处理速度。

具体的思路是这样的:

为了提高处理的速度,我们用 n 台机器并行处理。我们从搜索记录的日志文件中,依次读出每个搜索关键词,并且通过哈希函数计算哈希值,然后再跟 n 取模,最终得到的值,就是应该被分配到的机器编号。

这样,哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说,同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数,最后合并起来就是最终的结果。

分布式存储

现在互联网面对的都是海量的数据、海量的用户。为了提高数据的读取能力和写入能力,一般都采用分布式的而方式来存储数据,比如分布式缓存。

同时一台缓存机器是肯定不够用的,需要将数据分布在多台机器上。

可以借用前面数据分片的思想,即通过哈希算法对数据取哈希值,然后对机器个数取模,来根据这个最终值决定存储该数据的缓存机器编号。

但是,数据增多时就需要再次增加机器,但是不单单应该是简单的增加一台机器。

假如原来有10台机器,要根据10来取模,原来的数据是通过与 10 来取模的。比如 13 这个数据,存储在编号为 3 这台机器上。但是新加了一台机器中,我们对数据按照 11 取模,原来 13 这个数据就被分配到 2 号这台机器上了。

因此,所有的数据都要重新计算哈希值,然后重新搬移到正确的机器上。这样就相当于,缓存中的数据一下子就都失效了。所有的数据请求都会穿透缓存,直接去请求数据库。这样就可能发生雪崩效应,压垮数据库。

所以,需要一种方法,使得在新加入一个机器后,并不需要做大量的数据搬移。这时候,一致性哈希算法就要登场了。

假设有 k 个机器,数据的哈希值的范围是[0, MAX]。将整个范围划分成 m 个小区间(m 远大于 k),每个机器负责 m/k 个小区间。

当有新机器加入的时候,就将某几个小区间的数据,从原来的机器中搬移到新的机器中。这样,既不用全部重新哈希、搬移数据,也保持了各个机器上数据数量的均衡。


  • Post title:哈希算法(2
  • Post author:Varsion
  • Create time:2020-09-01 10:10:31
  • Post link:https://blog.varsion.cn/post/a4437ba0.html
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Comments