哈希算法下——哈希算法在分布式系统中有哪些应用？
1. 应用五：负载均衡
负载均衡算法有很多，比如论询、随机、加权轮询等。那如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？也就是说，我们需要在同一个客户端上，把在一次会话中的所有请求都路由到同一个服务器上。
最直接的方法就是，维护一张映射关系表，这张表的内容是客户端 IP 地址或者会话 ID 与服务器编号的映射关系。客户端每次发出请求时，就从映射表中查找到对应的服务器编号，然后再请求该编号的服务器。这种方法简单直观，但也有几个弊端：
- 客户端很多的话映射表就会很大，比较浪费内存；
- 客户端上线下线，服务器扩容缩容都会导致映射失效，维护成本高。
如果借助哈希算法，我们可以对客户端 IP 地址或者会话 ID 计算哈希值，将得到的哈希值与服务器列表的大小进行取模运算，得到的值就是应该被路由到的服务器。这样，我们就把同一个 IP 过来的所有请求，都路由到同一个后端服务器上。
2. 应用六：数据分片
2.1. 如何统计 “搜索关键词” 出现的次数？
如果我们要处理 1T 的日志文件，来统计用户的搜索关键词特性。显然，一台机器不仅内存不够，而且处理速度也会很慢。因此，我们可以先对数据进行分片，然后采用多台数据处理的方法，来提高处理速度。
我们对读出的每个搜索关键词用哈希函数来计算哈希值，然后再和机器总数 N 取模，最终得到的值，就是该关键词应该被分配到的机器编号。这样，同一个关键词就会被分配到同一个机器上，每个机器会分别统计关键词出现的次数，最后再把结果合并起来。
2.2. 如何快速判断图片是否在图库中？
在 哈希算法上 中，我们介绍了如何应用哈希算法构建散列表来判断图片是否在图库中。但如果图片数量非常多的话，我们就无法在一台机器上建立散列表。
这时候，我们就可以仿照上面的思路，将数据进行分片，然后采用多机处理。我们对图库中的每张图片计算唯一标识，再和机器总数 N 取模，得到的值就是应该被分配到的机器编号，然后我们把唯一标识和图片路径发往对应的机器构建散列表。
当我们要判断一张图片是否在图库中的时候，我们通过同样的哈希算法，计算这个图片的唯一标识，再和机器总数 N 取模，然后就到对应的机器中去查找。
3. 应用七：分布式存储
现在互联网面对的都是海量的数据、海量的用户，为了提高对数据的读取、写入能力，一般都采用分布式的方式来存储数据，比如分布式缓存，我们需要将数据分布在多台机器上。
该如何决定某个数据该放到哪台机器上呢？我们可以借用前面数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，然后作为该数据应该存储的缓存机器编号。
但是，如果数据增多，原来的 10 个机器已经无法承受了，我们就需要进行扩容，比如扩充到 11 台机器。这时候，麻烦就来了，原来的数据是通过 10 来取模的，现在需要按照 11 来取模，同样的数据就会被分配到不同的机器上去了。
因此，所有的数据都需要重新计算哈希值，然后搬移到正确的机器上。这样就相当于缓存中的数据一下子就都失效了。所有的数据都会穿透缓存，直接去请求数据库。这样就可能发生雪崩效应，压跨数据库。因此，我们需要一种方法，使得在新加入一个机器后，并不需要做大量的数据搬移。
一致性哈希算法。假设我们有 K 个机器，数据的哈希值的范围为 [0, MAX]。我们将整个范围划分为 m 个小区间（m 远大于 K），每个机器负责 m/K 个小区间。当有新机器加入的时候，我们就将某几个小区间的数据搬移到新机器上去。这样，既不用全部重新计算哈希值，搬移数据，也保持了各个机器上数据数量的均衡。
获取更多精彩，请关注「seniusen」! 