今天学习哈希算法（下）。本篇文章的主要内容是哈希算法如何解决分布式问题。
应用
负载均衡
负载均衡算法有很多，比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？也就是说，需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。
最直接的方法就是，维护一张映射关系表，这张表的内容是客户端IP地址或者会话ID与服务器编号的映射关系。客户端发出的每次请求，都要在映射表中查找应该路由到的服务器编号，然后再请求编号对应的服务器。这种方法简单直观，但也有几个弊端：
- 如果客户端很多，映射表可能会很大，比较浪费内存空间；
- 客户端下线、上线，服务器扩容、缩容都会导致映射失效，这样维护映射表的成本就会很大。
如果借住哈希算法，这些问题都可以非常完美地解决。可以通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。
数据分片
如何统计“搜索关键词”出现的次数
假如有1T的日志文件，这里面记录了用户的搜索关键词，想要快速统计出每个关键词被搜索的次数，该怎么做？
这个问题有两个难点，第一个是搜索日志很大，没办法放到一台机器的内存中。第二个难点是，如果只用一台机器来处理这么巨大的数据，处理时间会很长。
可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。具体思路：为了提高处理的速度，用n台机器并行处理。从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟n取模，最终得到的值，就是应该被分配到的机器编号。
这样，哈希值相同的搜索关键词就被分配到了同一台机器上。同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。
这个处理过程也是MapReduce的基本设计思想。
如何快速判断图片是否在图库中
假设图库有1亿张图片，如何快速判断图片是否在图库中？
同样可以对数据进行分片，然后采用多机处理。每次从图库中读取一个图片，计算唯一标识，然后与机器个数n求余取模，得到的值就是对应要分配的机器编号，然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。当要判断一个图片是否在图库中的时候， 通过同样的哈希算法，计算这个图片的唯一标识，然后与机器个数n求余取模。假设得到的值是k，那就去编号k的机器构建的散列表中查找。
实际上，针对海量数据的处理问题，都可以采用多机分布式处理。借住这种分片的思路，可以突破单机内存、CPU资源的限制。
分布式存储
为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据，比如分布式缓存。如果有海量的数据需要缓存，需要将数据分布在多台机器上。可以借用数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。但是，如果数据增多，原来的机器个数n已经无法承受了，就需要扩容。这时麻烦就来了，并不是简单地加个机器就可以了。因为机器个数的增加，按照之前的计算方法，会导致数据分到与之前不同的机器上。
因此，需要重新计算哈希值，然后重新搬移到正确的机器上。这样就相当于，缓存中的数据一下子就都失效了。所有的数据请求都会穿透缓存，直接去请求数据库。这样就可能发生雪崩效应，压垮数据库。
所以，就需要一种方法，使得在新加入一个机器后，并不需要做大量的数据搬移。这时候，一致性哈希算法就要登场了。假设有k个机器，数据的哈希值的范围是[0, MAX]。将整个范围划分成m个小区间（m远大于k），每个机器负责m/k个小区间。当有新机器加入的时候，就将某几个小区间的数据（每个机器负责m/(k+1)个小区间），从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。
关于一致性哈希算法，有篇文章写的很好：白话解析：一致性哈希算法 consistent hashing，通俗易懂。
解答开篇 & 内容小结
主要是三种哈希算法在分布式系统中的应用，分别是：负载均衡、数据分片、分布式存储。
在负载均衡应用中，利用哈希算法替代映射表，可以实现一个会话粘滞的负载均衡策略。在数据分片应用中，通过哈希算法对处理的海量数据进行分片，多机分布式处理，可以突破单机资源的限制。在分布式存储应用中，利用一致性哈希算法，可以解决缓存等分布式系统的扩容、缩容导致数据大量搬移的难题。
