数据结构与算法之美 | 学习笔记18 —— 哈希算法在分布式中的应用
上节的数据结构与算法之美 | 学习笔记17 —— 哈希算法（散列函数）应用中，介绍了安全加密、数据校验、唯一标识和散列函数四个应用，这节的三个应用都与分布式系统有关。
一、应用五：负载均衡
我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上，也就是实现一个会话粘滞（session sticky）的负载均衡算法。
最直接的方法是针对客户端IP或会话ID与服务器编号形成映射，每次客户端的请求都对应查找服务器编号。但是：
- 对于客户端数量大的情况，映射表会过大，浪费内存空间；
- 客户端下线、上线、服务器扩容、缩容都会导致映射失效，维护成本大；
利用哈希算法，对客户端IP地址或会话ID计算哈希值，将哈希值与服务器列表大小取模运算，最终得到的就是服务器编号。
二、应用六：数据分片
1. 统计搜索关键词出现的次数
在1T的日志文件中，统计用户搜索每个关键词的次数，对于如此大的文件，我们可以用数据分片，多台机器处理的方法。假设用n台机器并行处理，我们从日志文件中依次读出每个关键词，计算出哈希值后与n取模，最终得到被分配到的机器编号。这样，相同哈希值的关键词会被分配到同一机器，也就是相同的关键词会被分配到同一个机器，最后合并起来就是最终结果。
这个处理过程也是MapReduce的基本设计思想。
2. 快速判断图片是否在图库中
上一节用了唯一标识法，但对于图片量很大的情况，在单台机器上构建散列表会超出内存上限。这时可以用数据分片思想来做多机处理。
每次从图库中取一个图片，计算哈希值后与机器个数n取模，得到对应分配的机器编号。最后每个机器再单独对分配的图片构建散列表。
对图片进行判断是否在图库中时，先计算哈希值，与n取模，得到的数字就是对应机器编号，再去对应机器的散列表中进行查找。
这种海量数据处理问题，都可以采用多机分布式处理方法，借助这种数据分片思路，突破单机内存、CPU资源等限制。
三、应用七：分布式存储
对于海量数据，我们一般采用分布式存储。利用上面数据分片的思想，当机器数量增加或减少时，对应所有图片的机器分配也会相应发生变化。
因此，所有数据都要重新计算、分配。此时所有数据请求都会穿透缓存，直接去请求数据库，这可能会引发雪崩效应。
这时我们可以采用一致性哈希算法，假设有n台机器，我们将整个范围划分成m个区间，每个机器负责m/n个区间。自己维护一套在n个机器上的m个区间的映射，当新机器加入时，更改部分机器对应区间的映射关系。通过这样的方式，既不用重新计算哈希值、搬移数据，也保持了各个机器上数据数量的均衡。