22、哈希算法（下）

思考：哈希算法在分布式系统中有哪些应用？

主要内容

继续哈希算法的应用场景

负载均衡

如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？
会话粘滞：同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。

简单粗暴的话，可以维护一个客户端 id 与 服务器编号的映射表，但维护需要成本并且还有考虑客户端上、下线的变动。

所以可以采用哈希算法，不需要去维护表，直接用哈希算法去计算，先求客户端 id 的哈希值，然后与服务器列表的大小取模运算，得到服务器编号。

数据分片

举案例说明：

如何统计“搜索关键词”出现的次数？

假如有 1T 的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？

这个问题有两个难点，第一个是搜索日志很大，没办法放到一台机器的内存中。第二个难点是，如果只用一台机器来处理这么巨大的数据，处理时间会很长。

处理方向：先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。

详细思路：用 n 台机器并行处理提高处理速度。从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。这样，哈希值相同的搜索关键词就被分配到了同一个机器上。
也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。

如何快速判断图片是否在图库中？

基于散列表：key 为图片信息的哈希值，vaule 为图片路径
然后对图片数据分片，准备 n 个机器。对每一个图片求哈希，再与 n 求余取模得到机器编号，然后将图片给该机器构建散列表。

判断时，同样获得图片哈希值，找到机器编号，然后再其中的散列表中查找。

给这 1 亿张图片构建散列表大约需要多少台机器？

MD 5 求哈希值，长度为 128 比特，即 16 字节
图片路径最长为 256 字节，假设平均为 128 字节
用链表解决散列冲突，则散列表每个数据为 16(哈希) + 128(图片路径) + 8(指针) = 152 字节

假设一台机器内存为 2GB，装载因子为 0.75，则可分配的空间为 2GB*0.75=1.5GB
那可以存 1.5GB / 1 52字节 约等于 1000W 张图片
那 1 亿张图片需要 10 台左右的机器

分布式存储

针对缓存机器，也可以通过先求数据的哈希值，然后求余取模获取缓存机器编号，最后存入数据。
当为了使用机器的增加，就要求**哈希算法保持一致性(一致性哈希算法)**。
白话解析：一致性哈希算法 consistent hashing

解答思考 && 内容总结

在负载均衡应用中，利用哈希算法替代映射表，可以实现一个会话粘滞的负载均衡策略。
在数据分片应用中，通过哈希算法对处理的海量数据进行分片，多机分布式处理，可以突破单机资源的限制。
在分布式存储应用中，利用一致性哈希算法，可以解决缓存等分布式系统的扩容、缩容导致数据大量搬移的难题。

新的思考

哈希算法还有很多其他的应用，比如网络协议中的 CRC 校验、Git commit id 等等。除了这些，你还能想到其他用到哈希算法的地方吗？