缓存算法–LRU

LRU

LRU是Least Recently Used 的缩写,翻译过来就是“最近最少使用”,也就是说,LRU缓存把最近最少使用的数据移除,让给最新读取的数据。而往往最常读取的,也是读取次数最多的,所以,利用LRU缓存,我们能够提高系统的performance.

LRU实现

LRU

1. 新数据插入到链表头部;
2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
3. 当链表满的时候,将链表尾部的数据丢弃。

LRU分析

【命中率】
当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。
【复杂度】
实现简单。
【代价】
命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部。

LRU-K

LRU-K中的K代表最近使用的次数,因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题,其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

实现

相比LRU,LRU-K需要多维护一个队列,用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候,才将数据放入缓存。当需要淘汰数据时,LRU-K会淘汰第K次访问时间距当前时间最大的数据。详细实现如下:

LRU-K

1. 数据第一次被访问,加入到访问历史列表;
2. 如果数据在访问历史列表里后没有达到K次访问,则按照一定规则(FIFO,LRU)淘汰;
3. 当访问历史队列中的数据访问次数达到K次后,将数据索引从历史队列删除,将数据移到缓存队列中,并缓存此数据,缓存队列重新按照时间排序;
4. 缓存数据队列中被再次访问后,重新排序;
5. 需要淘汰数据时,淘汰缓存队列中排在末尾的数据,即:淘汰“倒数第K次访问离现在最久”的数据。
LRU-K具有LRU的优点,同时能够避免LRU的缺点,实际应用中LRU-2是综合各种因素后最优的选择,LRU-3或者更大的K值命中率会高,但适应性差,需要大量的数据访问才能将历史访问记录清除掉。

分析

【命中率】
LRU-K降低了“缓存污染”带来的问题,命中率比LRU要高。
【复杂度】
LRU-K队列是一个优先级队列,算法复杂度和代价比较高。
【代价】
由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象,因此内存消耗会比LRU要多;当数据量很大的时候,内存消耗会比较可观。
LRU-K需要基于时间进行排序(可以需要淘汰时再排序,也可以即时排序),CPU消耗比LRU要高。

一致性哈希算法(consistent hashing)

在分布式系统中,如果某业务可以由多个相同的节点处理,很容易想到用HASH的方式将业务请求分散到这些节点处理,如果有N个节点,计算方法为:HASH(id)% N。

如果只是简单的计算,不涉及用户状态,这是一个简单有效的方案。如果节点的计算涉及用户状态,比如Memcache缓存服务等,好像也没什么问题,只要用同一个数据做id,上述HASH的结果也保持不变。但如果节点数量发生变化,比如由于业务量的增大而增加节点或由于机器宕机而减少节点,上述HASH的结果就不一样了。若增加2个节点,某id原处理节点为HASH(id)% N,新的处理节点就变成了HASH(id)% (N + 2),可能会将大量id的处理节点打乱重新分配,就会发现之前某节点保存的用户数据用不到了,而新的处理节点根本没有这些数据。在这段时间内,这些用户的状态受到破坏,如果是缓存服务,之前的缓存都消失了,起不到缓存的效果,可能需要从数据库更新缓存,压力瞬间冲向后端。

一致性哈希在一定程度上缓解了这个问题,步骤为:
1.将整个哈希值空间组织成一个虚拟圆环,假设某哈希函数H的值空间为0-(2^32-1),即32位无符号整数
2.将各节点用H函数哈希,可以将服务器的IP或主机名作为关键字哈希,这样每个节点就能确定其在哈希环上的位置
3.将id用H函数映射到哈希空间的一个值,沿该值向后,将遇到的第一个节点做为处理节点
下图中,若某id的HASH值落在node1和node2各自HASH值的中间位置,则此id对应的业务请求由node2处理。

hash1

当增加服务节点时,只会影响与之相邻的某一节点,其他节点不受影响。如果在node2和node4之间增加一个node5,则只有node4处理的部分id(HASH值落在node2之后、node5之前的那部分id)变为由node5来处理,其他节点处理的id不变。比开头所述的简单HASH方式有了很大的改善。

hash2

如果节点数不多,将这些节点映射到值空间之后,分布可能会很不均匀,必然会造成个别节点处理的id数量远大于其他节点,这就起不到负载均衡的效果。这可以通过引入虚拟节点的方式解决,即对每一个节点计算多个HASH值,尽量保证这些HASH值比较均匀的分布在值空间中。当根据id查找节点时,找到的是虚拟节点,然后再根据虚拟节点查找对应的真实节点。多了一次查找的过程。如下图:
hash3

 

一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义:
1、平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓存中去,这样可以使得所有的缓冲空间都得到利用。
2、单调性(Monotonicity):单调性是指如果已经有一些内容通过哈希分派到了相应的缓存中,又有新的缓存加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓存中去,而不会被映射到旧的缓存集合中的其他缓冲区。
3、分散性(Spread):在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。
4、负载(Load):负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同 的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

基于漏桶(Leaky bucket)与令牌桶(Token bucket)算法的流量控制

互联网服务赖以生存的根本是流量, 产品和运营会经常通过各种方式来为应用倒流,比如淘宝的双十一等,如何让系统在处理高并发的同时还是保证自身系统的稳定,通常在最短时间内提高并发的做法就是加机器,但是如果机器不够怎么办?那就需要做业务降级或系统限流,流量控制中用的比较多的两个算法就是漏桶和令牌桶.

漏桶算法(Leaky bucket)

漏桶算法强制一个常量的输出速率而不管输入数据流的突发性,当输入空闲时,该算法不执行任何动作.就像用一个底部开了个洞的漏桶接水一样,水进入到漏桶里,桶里的水通过下面的孔以固定的速率流出,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率.如下图所示:

leaky bucket

令牌桶(Token bucket)

令牌桶算法的基本过程如下:

  1. 每秒会有 r 个令牌放入桶中,或者说,每过 1/r 秒桶中增加一个令牌
  2. 桶中最多存放 b 个令牌,如果桶满了,新放入的令牌会被丢弃
  3. 当一个 n 字节的数据包到达时,消耗 n 个令牌,然后发送该数据包
  4. 如果桶中可用令牌小于 n,则该数据包将被缓存或丢弃

token bucket

漏桶和令牌桶比较

“漏桶算法”能够强行限制数据的传输速率,而“令牌桶算法”在能够限制数据的平均传输数据外,还允许某种程度的突发传输。在“令牌桶算法”中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的上限,因此它适合于具有突发特性的流量。

 RateLimiter

我们可以使用 Guava 的 RateLimiter 来实现基于令牌桶的流量控制。RateLimiter 令牌桶算法的单桶实现,RateLimiter 对简单的令牌桶算法做了一些工程上的优化,具体的实现是 SmoothBursty。需要注意的是,RateLimiter 的另一个实现 SmoothWarmingUp,就不是令牌桶了,而是漏桶算法。

SmoothBursty 有一个可以放 N 个时间窗口产生的令牌的桶,系统空闲的时候令牌就一直攒着,最好情况下可以扛 N 倍于限流值的高峰而不影响后续请求,就像三峡大坝一样能扛千年一遇的洪水.

信用卡校验位算法THE LUHN MOD-10

1. 对卡号上的每位数字乘以权重。其规则是,如果卡号数字个数是偶数,则第一位乘以2,否则就乘以1,然后以后分别是,1,2,1,2,1,2;
2. 如果每位数字乘以权重后超过9 ,则需要减去 9;
3. 将所有的处理过的加权数字求和,用 数字 10 求模运算;
4. 余数应该是0,否则可能是输入错误。也可能是一个假号。

Bloom Filter概念和原理

Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。

 

1 Overview

Bloom filter最早由 Burton Howard Bloom提出,是一种用于判断成员是否存在于某个集合中的数据结构。 Bloom filter的判断基于概率论:

  • 如果某个成员存在于集合中,那么Bloom filter不会返回假(即不存在),也就是说false negative是不可能的。
  • 如果某个成员实际上不存在于集合中,Bloom filter可能返回真(即存在),这种情况被称为false positive。

Bloom filter通常被实现为一个包含 m 位的位数组(bit array),所有位的初始值都为0。 Bloom filter支持以下两种类型的操作:

  • add。将成员添加到Bloom filter中。以该成员为参数调用 k 个索引函数(index functions),得到 k 个位数组的索引值,取值范围是 [0, m), 然后将位数组的对应位设置为1。
  • query。判断某个成员是否已经添加到Bloom filter中。以该成员为参数调用 k 个索引函数,得到 k 个位数组的索引值,然后根据这些索引值检查位数组:当位数组中所有的对应位均为1时,那么认为该成员已经存在。

如果query的结果为真(即positive),那么实际上存在以下两种可能性:

  • 该成员已经被add到集合中,即该成员的确存在。
  • 该成员未被add到集合中,但是query过程中检查的所有位均被设置为1(由于添加的其它成员导致)。这种情况被称为false positive。

传统的Bloom filter 不支持从集合中删除成员。对于每个添加到Bloom filter中的成员,实际上将其位数组中的 k位设置为1。尽管将这些位重置为0可以保证从Bloom filter中删除该成员,但是这样做的副作用是可能会影响某些其它成员,因为其它成员也可能被映射到这些被重置为0的位中的一位或者多位, 从而最终导致false negatives。对于Bloom filter而言,false negatives是不被允许的。 Counting Bloom filter由于采用了计数,因此支持remove操作。

Bloom filter 使用的 k 个index functions,有时也被称为hash functions,它们通常被假定为彼此独立,返回值在可能的取值范围内均匀分布(这是以下一系列数学证明的基础)。

 

2 The Math

Bloom filter的基本概念并不复杂,接下来分析一下query操作对某个未被添加的成员返回positive(即false positive)的概率:

假设p是位数组中某一位为1的概率, 那么false positive的概率是 pk 。如果n是已经添加到Bloom filter中的成员个数,那么 p = 1 – (1 – 1/m)nk,经过一系列推导得到 p ≈ ( 1 – e-kn/m ) , 当 k = m / n * ln2 时(ln 即 loge),p为最小值。 例如当k = 8, m/n = 10时, false positive的理论值为0.00846。以下是段计算false positive的实例代码:

Java代码
  1. public static double calculateFalsePositiveProbability(int k, int m, int n) {
  2.     return Math.pow((1 - Math.exp(-k * (double) n  / (double) m)), k);
  3. }

 

对于某些应用而言,false positive的概率已经是一个足够好的判断Bloom filter准确性的指标,Peter C.Dillinger 和 Panagiotis Manolios 在其Bloom Filters in Probablistic Verfification的论文中指出,对于query过程中的不确定性, state omission 是一个更合适的指标。建议感兴趣的读者阅读该论文,顺便也可以复习一下相关的数学知识。