哈希算法
哈希算法:
将任意长度的二进制串,映射为固定长度的二进制值串,这个映射的规则就是哈希算法。
哈希算法作用:
1、唯一标识,哈希算法可以对大数据做信息摘要,通过一个较短的二进制编码来表示很大的数据
2、应用是用于校验数据的完整性和正确性
3、应用安全加密。
4、应用散列函数。
5、负载均衡
实现一个会话粘滞的负载均衡算法?
最直接的算法就是维护一张映射关系表,这张表的内容是客户端IP地址或者会话IS与
服务器编号的映射关系。客户端发出的每次请求,都要先在映射表中查找应该路由
到的服务器编号,然后再请求编号对应的服务器。这种方法简单,直观。但
如果客户端很多,映射表可能会很大,比较浪费内存空间。
客户端下线、上线,服务器扩容、缩荣都会导致映射表失效,这样维护映射表的成本就很大
我们可以通过哈希算法,对客户端的IP地址或者会话ID 计算哈希值,将取得的哈希值与服务器
列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号。
6、数据分片
假如我们有 1T 的日志文件,这里面记录了用户的搜索关键词,我们想要快速统计出每个关键词被搜索的次数,该怎么做呢?
我们可以先对数据进行分片,然后采用多台机器处理的方法,来提高处理速度。具体的思路是这样的:为了提高处理的速度,我们用 n 台机器并行处理。我们从搜索记录的日志文件中,依次读出每个搜索关键词,并且通过哈希函数计算哈希值,然后再跟 n 取模,最终得到的值,就是应该被分配到的机器编号。这样,哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说,同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数,最后合并起来就是最终的结果。
7、分布式存储
现在互联网面对的都是海量的数据、海量的用户。我们为了提高数据的读取、写入能力,一般都采用分布式的方式来存储数据,比如分布式缓存。我们有海量的数据需要缓存,所以一个缓存机器肯定是不够的。于是,我们就需要将数据分布在多台机器上。该如何决定将哪个数据放到哪个机器上呢?我们可以借用前面数据分片的思想,即通过哈希算法对数据取哈希值,然后对机器个数取模,这个最终值就是应该存储的缓存机器编号。
但是,如果数据增多,原来的 10 个机器已经无法承受了,我们就需要扩容了,比如扩到 11 个机器,这时候麻烦就来了。因为,这里并不是简单地加个机器就可以了。原来的数据是通过与 10 来取模的。比如 13 这个数据,存储在编号为 3 这台机器上。但是新加了一台机器中,我们对数据按照 11 取模,原来 13 这个数据就被分配到 2 号这台机器上了。
因此,所有的数据都要重新计算哈希值,然后重新搬移到正确的机器上。这样就相当于,缓存中的数据一下子就都失效了。所有的数据请求都会穿透缓存,直接去请求数据库。这样就可能发生雪崩效应,压垮数据库。所以,我们需要一种方法,使得在新加入一个机器后,并不需要做大量的数据搬移。这时候,一致性哈希算法就要登场了。
假设我们有 k 个机器,数据的哈希值的范围是 [0, MAX]。我们将整个范围划分成 m 个小区间(m 远大于 k),每个机器负责 m/k 个小区间。当有新机器加入的时候,我们就将某几个小区间的数据,从原来的机器中搬移到新的机器中。这样,既不用全部重新哈希、搬移数据,也保持了各个机器上数据数量的均衡。一致性哈希算法的基本思想就是这么简单。除此之外,它还会借助一个虚拟的环和虚拟结点,更加优美地实现出来。这里我就不展开讲了,如果感兴趣,你可以看下这个
对称加密算法(AES,DES)或者是非对称加密(RSA,ECC)