Cache Algorithm

什么是缓存：
存储使用频繁数据的临时地方。

缓存命中：
如果不是预存的话第一次要miss掉。
1、如果有足够的缓存空间，未命中的对象后面会被存储到缓存中。
2、如果缓存满了，就有根据对应的缓存策略，替换数据。即替换策略


缓存算法可以分为：
  1. 基于时间的策略

  2. 基于访问频率的策略

  3. 基于二者坚固的策略

  4. 时间距离分布策略

  5. 数据访问模式

  6. 基于VoD系统架构的策略等



缓存策略：

  1. 缓存什么内容

  2. 何时进行缓存（预取策略，提前将部分磁盘数据放入缓存，可以减少磁盘io，加大cache命中率。）

  3. 当缓存空间已满时如何进行替换，即缓存替换算法

分类：

基于时间访问：按各缓存项的被访问时间来组织缓存队列，决定替换对象。如：LRU

基于访问频率：用缓存项的被访问频率来组织缓存。如LFU,LRU-2,2Q,LIRS

二者兼顾：如FBR,LRFU,ALRFU

基于访问模式：某些应用有比较明确的数据访问特点，进而产生与其相适应的缓存策略

贝莱蒂算法（Belady‘s Algorithm）
最有效率的缓存算法会丢掉未来最长时间内不使用的数据，这种理想情况被称作为最优算法或者千里眼算法。由于要预计数据多久后才被使用基本上是不可能的，所以这种算法没有实际的可操作性，它的作用在于为不同的缓存算法订立一个优劣标准。

OPT（clairvoyant replacement algorithm）
当一个页面需要被cache而导致已保存的内容需要替换出去时，OPT算法会将cache中某个将来最长时间内都不会被访问的页面替换出去。很明显，该算法只是理论上的一种理想化算法，实际应用中设计的算法都是该算法的近似算法。

Adaptive Replacement Cache（ARC）
介于 LRU 和 LFU 之间，是由2个 LRU 组成，第一个，也就是 L1，包含的条目是最近只被使用过一次的，而第二个 LRU，也就是 L2，包含的是最近被使用过两次的条目。因此， L1 放的是新的对象，而 L2 放的是常用的对象。被认为是性能最好的缓存算法之一，能够自调，并且是低负载的。也保存着历史对象，这样，就可以记住那些被移除的对象，同时，也可以看到被移除的对象是否可以留下，取而代之的是踢走别的对象。

LFU(LeastFrequentlyUsed)
按照每个缓存块的被访问频率将缓存中的各块排序，当缓存空间已满时候，替换掉缓存队列中访问频率最低的一项，与LRU的缺点类似，LFU仅维护各项的被访问频率信息，对于某项缓存，如果该项的过去有着极高的访问频率，而最近访问频率较低，当缓存空间已满时该项很难被从缓存中替换出来，进来导致命中率下降。

LRU（LeastRecentlyUsed）
最近最早使用的缓存对象会被踢走，该算法维护一个缓存项队列，队列中的缓存项按照每项的最后被访问时间排序。当缓存空间已满时，将处理队尾即删除最后一次被访问时间距离现在最久的项。将新的区段放入队列首部。例如对于VoD系统,在没有VCR操作的情况下,数据被由前至后顺序访问,已访问过的数据不会被再次访问。所以LRU算法将最新被访问的数据最后被替换不适用于VoD系统。LRU算法的缺点是它没有考虑文件访问的一些规律，有时候会表现出很低的性能，尤其是在数据库系统中，通常数据都有访问模式可循，这时候使用LRU算法不能够充分利用这些规律，在有些情况下可能会出现LRU将一个用户访问次数多的文件从lru list中替换出来，而插入一个用户访问次数低的文件，引起cache pollution问题。
为了完善LRU出现了 LRU2和2Q

LRU-2
算法记录下每个缓存页面最后两次被访问的时间，替换页面时替换倒数第二次访问时间距现在最久的一项。在IRM（IndependentReferenceModel）访问模式下，LRU-2有着很好的预期命中率，由于LRU-2算法要维护一个优先级队列，所以该算法复杂度为logN
（N为缓存队列中缓存项的数量）这个算法的主要思想是说不能仅仅依靠一次访问就决定一个文件应该cache。LRU/2算法在实现时使用的数据结构是优先级队列，时间复杂度为O(nlogn)。为了能够解决cache pollution的问题，LRU/2有两个参数是需要调参的：(1)correlated reference period，在一个correlated reference period时间段内，多次文件访问只算作一次，这样可以避免cache pollution的问题，当某个文件在一个period时间内多次访问后，经历一段时间才再次进行访问，这时候这个保存在cache中的文件会在一个period时间段过后更新为一个低的优先级。(2)retained information period。这个时间段是当一个文件从cache中删除后它的访问历史记录会在一个period时间段内保存。

Two Queues（2 Queues）
把被访问的数据放到LRU的缓存中，如果这个对象再一次被访问，我就把他转移到第二个、更大的LRU缓存。

MRU(Most Recently Used)
最近最频繁使用算法和最近最少使用算法相反，它会首先丢弃最近最常使用的数据，有观点认为“当文件在顺序访问时，MRU算法是最佳选择”，抱有这样观点的人也认为在反复进行大量数据的随即存储时，MRU因为倾向于保留旧的数据，所以比LRU算法有着更高的命中率，MRU算法经常用于旧的数据更常被用到的情况下。

FIFO（First in First out）：
  先进先出，低负载算法。常用的缓存对象放在后面，更早的放在前面。容量满的时候踢走前面的。很快，但不适用。

Second Chance：
比FIFO多了一个标志，无标志的话就踢出，否则清楚标志位然后重新加入缓存队列。

Clock：
我持有一个装有缓存对象的环形列表，头指针指向列表中最老的缓存对象。当缓存 miss 发生并且没有新的缓存空间时，我会问问指针指向的缓存对象的标志位去决定我应该怎么做。如果标志是0，我会直接用新的缓存对象替代这个缓存对象；如果标志位是1，我会把头指针递增，然后重复这个过程，知道新的缓存对象能够被放入。我比 second chance 更快。

Simple time-based：
通过绝对的时间周期去失效那些缓存对象。对于新增的对象，会保存特定的时间。很快，但是并不适用。

Extended time-based expiration：
通过相对时间去失效缓存对象的；对于新增的缓存对象会保存特定的时间，比如是每5分钟，每天的12点。

Sliding time-based expiration：
与前面不同的是，被管理的缓存对象的生命起点是在这个缓存的最后被访问时间算起的。很快，但是也不太适用。

LIRS(Low Inter-ReferenceRecenty Set)
维护一个变长的LRU队列，该队列的LRU端为最近至少被访问过2次的第Llirs项
(Llirs为算法参数)。LIRS算法在IRM访问模式下可以获得很高的命中率,但对于SDD访问模式效率明显下降。对于VoD系统,基于访问频率的策略可以捕捉到热点影片片段,使得对热点片段的大量请求免于进行缓慢的磁盘I/O。但影片热点会随时间不断变化,且此类策略无法利用VoD的顺序访问模式,所以纯粹以访问频率为度量来进行替换操作不适合VoD系统。

FBR[6](Frequency Based Replacement)
维护一个LRU队列,并将该队列分为New、Middle、Old三段。对队列中的每一缓存项均维护一个计数值。当缓存中的一项被命中时,被命中的缓存项被移至New段的MRU端,如果该项原本位于Old或Middle段,则其计数值加1,原位于New段则计数值不变。当进行替换操作时,删除Old段计数值最小的一项(LRU端)。

LRFU[7](LeastRecently FrequentlyUsed)
为每一个缓存项维护一个权值C(x),其初始值为0, C(x)按以下公式变化。在t时刻, C(x) =1+2-λC(x): x被访问到2-λC(x)　: x未被访问进行替换操作时,C(x)值最小的一项被删除。当时, LRFU算法行为类似于LFU;而当时,该算法行为逼近LRU算法。该算法通过选用合适的λ值来获得时间与频率因素的平衡。LRFU虽然通过一个值来兼顾访问时间与频率因素,但由于值固定,当访问模式变化时,该算法无法做出相应的调整而造成性能下降。ALRFU[8](Adaptive LRFU)在此方面对LRFU进行了改进。通过对数据访问模式的历史进行监控,ALRFU动态调整值来适应数据访问模式的改变,表现出比LRFU更好的适应性。
基于访问模式的缓存策略：

python demo:
LRU&LFU

import collections
import functools
from itertools import ifilterfalse
from heapq import nsmallest
from operator import itemgetter

class Counter(dict):
    'Mapping where default values are zero'
    def __missing__(self, key):
        return 0

def lru_cache(maxsize=100):
    '''Least-recently-used cache decorator.

    Arguments to the cached function must be hashable.
    Cache performance statistics stored in f.hits and f.misses.
    Clear the cache with f.clear().
    http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used

    '''
    maxqueue = maxsize * 10
    def decorating_function(user_function,
            len=len, iter=iter, tuple=tuple, sorted=sorted, KeyError=KeyError):
        cache = {}                  # mapping of args to results
        queue = collections.deque() # order that keys have been used
        refcount = Counter()        # times each key is in the queue
        sentinel = object()         # marker for looping around the queue
        kwd_mark = object()         # separate positional and keyword args

        # lookup optimizations (ugly but fast)
        queue_append, queue_popleft = queue.append, queue.popleft
        queue_appendleft, queue_pop = queue.appendleft, queue.pop

        @functools.wraps(user_function)
        def wrapper(*args, **kwds):
            # cache key records both positional and keyword args
            key = args
            if kwds:
                key += (kwd_mark,) + tuple(sorted(kwds.items()))

            # record recent use of this key
            queue_append(key)
            refcount[key] += 1

            # get cache entry or compute if not found
            try:
                result = cache[key]
                wrapper.hits += 1
            except KeyError:
                result = user_function(*args, **kwds)
                cache[key] = result
                wrapper.misses += 1

                # purge least recently used cache entry
                if len(cache) > maxsize:
                    key = queue_popleft()
                    refcount[key] -= 1
                    while refcount[key]:
                        key = queue_popleft()
                        refcount[key] -= 1
                    del cache[key], refcount[key]

            # periodically compact the queue by eliminating duplicate keys
            # while preserving order of most recent access
            if len(queue) > maxqueue:
                refcount.clear()
                queue_appendleft(sentinel)
                for key in ifilterfalse(refcount.__contains__,
                                        iter(queue_pop, sentinel)):
                    queue_appendleft(key)
                    refcount[key] = 1


            return result

        def clear():
            cache.clear()
            queue.clear()
            refcount.clear()
            wrapper.hits = wrapper.misses = 0

        wrapper.hits = wrapper.misses = 0
        wrapper.clear = clear
        return wrapper
    return decorating_function


def lfu_cache(maxsize=100):
    '''Least-frequenty-used cache decorator.

    Arguments to the cached function must be hashable.
    Cache performance statistics stored in f.hits and f.misses.
    Clear the cache with f.clear().
    http://en.wikipedia.org/wiki/Least_Frequently_Used

    '''
    def decorating_function(user_function):
        cache = {}                      # mapping of args to results
        use_count = Counter()           # times each key has been accessed
        kwd_mark = object()             # separate positional and keyword args

        @functools.wraps(user_function)
        def wrapper(*args, **kwds):
            key = args
            if kwds:
                key += (kwd_mark,) + tuple(sorted(kwds.items()))
            use_count[key] += 1

            # get cache entry or compute if not found
            try:
                result = cache[key]
                wrapper.hits += 1
            except KeyError:
                result = user_function(*args, **kwds)
                cache[key] = result
                wrapper.misses += 1

                # purge least frequently used cache entry
                if len(cache) > maxsize:
                    for key, _ in nsmallest(maxsize // 10,
                                            use_count.iteritems(),
                                            key=itemgetter(1)):
                        del cache[key], use_count[key]

            return result

        def clear():
            cache.clear()
            use_count.clear()
            wrapper.hits = wrapper.misses = 0

        wrapper.hits = wrapper.misses = 0
        wrapper.clear = clear
        return wrapper
    return decorating_function


if __name__ == '__main__':

    @lru_cache(maxsize=20)
    def f(x, y):
        return 3*x+y

    domain = range(5)
    from random import choice
    for i in range(1000):
        r = f(choice(domain), choice(domain))

    print(f.hits, f.misses)

    @lfu_cache(maxsize=20)
    def f(x, y):
        return 3*x+y

    domain = range(5)
    from random import choice
    for i in range(1000):
        r = f(choice(domain), choice(domain))

    print(f.hits, f.misses)

本文整理于互联网上相关文章，下方有参考相关文章的链接。

参考资料：

http://blog.csdn.net/zhghost/article/details/5344962
http://blog.chinaunix.net/uid-23242010-id-147401.html
http://www.w3ccollege.org/index/caching-algorithm.html
http://www.leexiang.com/cache-algorithm原文打不开下面的是备用的
http://www.chinaz.com/web/2012/1204/284568.shtml
http://en.wikipedia.org/wiki/Cache_algorithms
LRU
http://blog.csdn.net/Ackarlix/article/details/1759793

DEMO
http://code.activestate.com/recipes/498245-lru-and-lfu-cache-decorators/