LRUCache Implementation

http://www.thinkingyu.com/articles/LIRS/

众所周知，缓存块替换策略的高效性对于I/O系统的整体性能有着非常重要的影响。目前，LRU（Least Recently Used）算法以其简单有效的特点被广泛使用，但是在一些典型的负载情形下，即使显著增大了Cache的容量，LRU算法的命中率也不会显著提高。这些都反映出LRU算法在面对弱局部性负载时的捉襟见肘。 下面是一些用来证明LRU性能瓶颈的具有代表性的例子：

1. 缓存污染问题：大量促发地对冷块进行访问会对热块进行不明智的替换，这在序列扫描应用中非常普遍
2. 循环性质访问问题：假如需要对一个文件进行循环性质的访问，并且文件的大小略微大于Cache的大小，那么就会出现即将被访问的块被当做冷块替换出去，一个明智的替换策略应尽量保证Cache的失效率近似于缓存空间不足的比例。
3. 不关注访问的概率性特征：在多用户访问数据库场景中，每一条记录的访问都涉及B类树数据结构，也就是需要先访问索引再访问数据，假设我们需要访问20000条记录，索引信息被压缩在100个块中，而有10000个块来承载记录，我们用R(i)表示对记录的访问，用I(i)表示对索引的访问，按照数据库的访问方式应该是这样子的：I(1),R(1),I(2),R(2),I(3),R(3)…,可以发现索引块的访问概率为0.5%，而记录数据块的访问概率为0.005%。然而，LRU会在缓存空间保持相同数目的索引块和记录块，甚至记录块的数目要多于索引块。好的替换策略需要考虑访问概率的特征，让访问概率较高的块驻留在缓存的时间长一些。

LRU算法在这些情景下表现拙劣的根本原因在于它基于一个粗糙的假设：最长时间没被访问的块要经过相对来说最长的时间间隔才会被再次访问。这在一些局部性不是很高的应用场景下不适用，所以就到了我们LIRS算法一展身手的时候了。

LIRS使用IRR（Inter-Reference Recency）来表征每个缓存块的历史信息，单从名字不容易看出IRR的具体含义，参照原论文的定义是这样的： 一个缓存块的IRR是指在相继地访问这个块之间访问其它非重复缓存块的个数，听起来还是有点拗口，我们用图来说明，如图所示：

缓存块1的IRR就是3，因为在相继地访问1之间访问了2,3,4，尽管3被访问两次，但只算一次。特别的，我们把一个块从最近一次访问到当前时间之间访问其它块的非重复个数叫做这个块的recency。比如上图缓存块1的recency是2。

LIRS算法不同于LRU的地方就是在选择要被替换的块时不仅仅考虑recency，也考虑IRR，通过考量一个块的IRR我们就能对这个块的访问历史有更准确的把握。具有较小的IRR的块LIRS称之为LIR块，高IRR块称之为HIR块。所有缓存块被分成LIR和HIR两个集合，LIR块集合的大小需要控制小于Cache的大小以保证LIR块可以常驻Cache，访问LIR块永远不会失效，Cache的一小部分空间留给HIR块，缓存中HIR块会随时被淘汰即使它最近被访问过。HIR块分为两种形式：驻Cache的HIR块（resident-HIR）和非驻Cache的HIR块（nonresident-HIR）。LIRS算法的关键在于如何动态地维护LIR和HIR集合。当一个HIR块再次被访问，它会得到一个新的IRR，如果这个IRR小于LIR集合最大的recency，那么我们需要让此HIR块和具有最大recency的LIR块互换角色以保持LIR和HIR集合的大小恒定。

LIRS的工作流程与其实现需要的数据结构紧密相关，因此在这里先谈一下LIRS实现需要的数据结构。

####LIRS数据结构：

• LIRS栈：LIRS栈用来存储entries，每个entry都代表一个缓存块并且记录该缓存块的状态（LIR/HIR）和是否驻留在Cache中，LIRS使用这个栈来确定每个缓存块的recency和动态调整LIR和HIR集合。
• ListQ：为了替换时找寻resident-HIR块方便，把所有resident-HIR块链接到一起形成的链表。

一旦访问不命中需要对Cache中的缓存块进行替换时，选择ListQ的头部的块进行替换，然而这个被替换的HIR块的entry如果在LIRS栈中已存在则仍需要保存它的entry，只不过状态从resident-HIR变为nonresident-HIR。LIRS还有一个特殊的“栈剪枝”操作以确保LIRS栈底的块entry永远处于LIR状态，操作的过程就是从栈底开始将HIR块entry依次删除直到栈底的entry是LIR状态。“栈剪枝”的作用是保持栈底entry状态为LIR，这样如果访问命中一个resident-HIR，那我们就知道这个resident-HIR的新IRR一定小于栈底LIR块的recency，故可以互换它们的角色，并把栈底的resident-HIR块的entry移动到ListQ的链表尾部。

####LIRS算法关键流程：

• 访问LIR块：由于LIR块常驻Cache，所以访问肯定命中，只需要把此LIR块entry从当前位置移到LIRS栈顶即可，当然如果LIR块entry原来是在栈底，就需要进行一次栈剪枝。
• 访问resident-HIR块：此时命中，这里分两种情况：（1）如果这个块entry在之前就在LIRS栈里，那么它转化为LIR状态，移到栈顶，并从ListQ中删除它，栈底的LIR块entry转化为HIR状态，移到ListQ队列末尾，开始栈剪枝。（2）由于之前的栈剪枝导致此resident-HIR块的entry不在LIRS栈里，仅在ListQ里，此时把它移到队列末尾，并把一个此entry副本置于LIRS栈栈顶。
• 访问nonresident-HIR块：此时命中失败，决定换出ListQ队头的HIR块，在ListQ里删除它，如果在LIRS栈有它的entry，把它转化为non-resident状态，把待换入的访问块的entry置于LIRS栈顶，这里分两种情况：（1）如果在LIRS栈里有一个待换入块的non-resident状态entry，此时删掉这个entry，把栈顶的entry转化为LIR状态，栈底的LIR entry转化为HIR，移动到ListQ队列尾，进行栈剪枝。（2）如果待换入块没有entry在LIRS栈里，不需要修改它的状态，直接推送一个此块的entry副本到ListQ尾部。

LIRS的算法流程还是比较麻烦的，接下来通过几个实例进一步说明

####几个例子：

程序如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <string>

#include <boost/shared_ptr.hpp>

#include <muduo/base/Logging.h>

#define NODEBUG

#define LRUStackSLocation int
#define LRUStackLocation  int
#define LRUListQLocation  int
#define InvalidLocation -1
#define BottomLocation 0

class Entry;
typedef boost::shared_ptr<Entry> EntryPtr;

class Entry
{

public:

    enum EntryState
    {
        kLIR = 0,
        kresidentHIR,
        knonResidentHIR,
        kInvalid
    };

    explicit Entry(int value , EntryState state = kInvalid):
                   value_(value) , rValue_(value_) , state_(state)
    {

    }

    void setState(EntryState state)
    {
        state_ = state;
    }

    EntryState getState()
    {
        return state_;
    }

    std::string returnStateStr(EntryState state)
    {
        switch(state)
        {
        case kLIR:
            return "LIR";
        case kresidentHIR:
            return "resident HIR";
        case knonResidentHIR:
            return "no resident HIR";
        default:
            return "Invalid";
        }
    }

public:

    int const& rValue_;

private:

    EntryState state_;
    int value_;
};

class LRUStack
{
public:

    void movToTop(LRUStackLocation location)
    {
        if(location == container_.size() - 1)
            return;
        auto it = container_.begin() + location;
        EntryPtr tmp = container_[location];
        container_.erase(it);
        container_.push_back(tmp);
#ifndef NODEBUG
        debugToString("test");
#endif
    }

    void debugToString(std::string const& name)
    {
        std::cout << "#############" << name << "#############\n";

        std::for_each( container_.begin(), container_.end(), [](EntryPtr& item)
            { std::cout << "<" << item->rValue_ << " , " <<
              item->returnStateStr( item->getState() ) << ">\n";} );

        std::cout << "#############" << name << "#############\n";
    }

    LRUStackLocation find(int value)
    {
        LRUStackLocation location = InvalidLocation;
        int step = 0;
        for(auto it : container_)
        {
            if( it->rValue_ == value )
            {
                location = step;
                break;
            }
            else
                ++step;
        }

        return location;
    }

    void pushEntry(EntryPtr item)
    {
        container_.push_back(item);
    }

    void eraseBottomEntry()
    {
        container_.erase(container_.begin());
    }

    void eraseEntryByLocation(LRUStackLocation location)
    {
        container_.erase(container_.begin() + location);
    }

    void setTopState(Entry::EntryState state)
    {
        setStateByLocation(getContainerSize() - 1 , state);
    }

    void setBottomState(Entry::EntryState state)
    {
        setStateByLocation(BottomLocation , state);
    }

    void setStateByLocation(LRUStackLocation location , Entry::EntryState state)
    {
        (container_[location])->setState(state);
    }

    Entry::EntryState getBottomState()
    {
        return (container_[BottomLocation])->getState();
    }

    Entry::EntryState getStateByLocation(LRUStackLocation location)
    {
        return (container_[location])->getState();
    }


    EntryPtr getBottomEntry()
    {
        return container_[BottomLocation];
    }

    EntryPtr getTopEntry()
    {
        return container_[getContainerSize() - 1];
    }

    EntryPtr getEntryByLocation(LRUStackLocation location)
    {
        return container_[location];
    }

    int getSize()
    {
        return container_.size();
    }

private:

    typedef std::vector<EntryPtr> EntryVec;
    EntryVec container_;

    int getContainerSize()
    {
        return container_.size();
    }
};

class LRUStackS:public LRUStack
{
public:

    void stackPruning()
    {
        while (true)
        {
            Entry::EntryState state = getBottomState();
            assert(state != Entry::kInvalid);
            if(state == Entry::kresidentHIR || state == Entry::knonResidentHIR)
                eraseBottomEntry();
            else
                break;
        }
    }

    void findAndSetState(int value , Entry::EntryState state)
    {
        LRUStackSLocation location = find(value);
        if(location != InvalidLocation)
            setStateByLocation(location , state);
    }
};

class LRUListQ:public LRUStack
{
public:

    void pushToEnd(EntryPtr item)
    {
        pushEntry(item);
    }

    void popFront()
    {
        eraseBottomEntry();
    }

    void movToEnd(LRUListQLocation location)
    {
        movToTop(location);
    }

    void findAndRemove(int value)
    {
        LRUListQLocation location = find(value);
        if(location != InvalidLocation)
            eraseEntryByLocation(location);
    }

    EntryPtr getAndRemoveFrontEntry()
    {
        EntryPtr tmp = getBottomEntry();
        eraseBottomEntry();
        return tmp;
    }
};

class LIRSExecutor
{
public:

    LIRSExecutor(int lirSize , int hirSize):lirSize_(lirSize),
                                            hirSize_(hirSize),
                                            hitTimes_(0)
    {
        cache_.reserve(lirSize_ + hirSize_);
    }

    void access(int value)
    {
        auto ptr = std::find(cache_.begin() , cache_.end()
            , value);
        if( ptr != cache_.end() )
        {
            LRUStackSLocation location = stackS_.find(value);
            if(location >= 0)
            {
                Entry::EntryState state = stackS_.getStateByLocation(location);
                if(state == Entry::kLIR)
                {
                    stackS_.movToTop(location);
                    stackS_.stackPruning();
                }
                else
                {
                    hitHIRInStackS(location);
                    listQ_.findAndRemove(value);
                }
            }
            else
            {
                location = listQ_.find(value);
                if(location >= 0)
                {
                    stackS_.pushEntry(listQ_.getEntryByLocation(location));
                    listQ_.movToEnd(location);
                }
                else
                    LOG_FATAL << "hit but there is not such a man in LRU S stack\n";
            }
            hitTimes_++;
        }
        else
        {
            if( (lirSize_--) > 0)
            {
                cache_.push_back(value);
                EntryPtr tmp(new Entry(value , Entry::kLIR));
                stackS_.pushEntry(tmp);
            }
            else if( (hirSize_--) > 0)
            {
                cache_.push_back(value);
                addAResidentHIREntry(value);
            }
            else
            {
                EntryPtr tmp = listQ_.getAndRemoveFrontEntry();
                stackS_.findAndSetState(tmp->rValue_ , Entry::knonResidentHIR);//if find will set
                std::vector<int>::iterator ptr = std::find(cache_.begin() ,
                    cache_.end() , tmp->rValue_);
                if( ptr != cache_.end() )
                {
                    *ptr = value;
                }
                else
                    LOG_FATAL << "miss error\n";

                LRUStackSLocation location = stackS_.find(value);
                if(location >= 0)
                {
                    hitHIRInStackS(location);
                }
                else
                {
                    addAResidentHIREntry(value);
                }

            }
        }
        stackS_.debugToString("LRU stack S");
        std::cout << "\n";
        listQ_.debugToString("LRU list Q");
        std::cout << "\n";
    }

    inline int getHitTimes()
    {
        return hitTimes_;
    }

private:

    typedef std::vector<int> intVec;
    intVec cache_;
    int hitTimes_;
    int lirSize_;
    int hirSize_;

    LRUStackS stackS_;
    LRUListQ  listQ_;

    void addAResidentHIREntry(int value)
    {
        EntryPtr tmp(new Entry(value , Entry::kresidentHIR));
        stackS_.pushEntry(tmp);
        listQ_.pushToEnd(tmp);
    }

    void hitHIRInStackS(LRUStackSLocation location)
    {
        stackS_.movToTop(location);
        stackS_.setTopState(Entry::kLIR);
        stackS_.setBottomState(Entry::kresidentHIR);
        listQ_.pushToEnd( stackS_.getBottomEntry() );
        stackS_.stackPruning();
    }
};

int main(void)
{
    LIRSExecutor executor(3 , 2);
    int a[] = {1 , 2 , 3 , 4 , 5  , 1 , 2 , 3 , 4};
    for(int i = 0 ; i != 1 ; ++i)
    {
        for(int j = 0 ; j != sizeof(a)/sizeof(int) ; ++j)
        {
            executor.access(a[j]);
        }
    }
    std::cout << executor.getHitTimes() << "\n";
    return 0;
}

http://calvin1978.blogcn.com/articles/lru.html
Redis、Memcached、Guava、Ehcache中的算法

1. LRU

简单粗暴的Redis

今天看Redis3.0的发行通告里说，LRU算法大幅提升了，就翻开源码来八卦一下，结果哭笑不得，这旧版的"近似LRU"算法，实在太简单，太偷懒，太Redis了。

在Github的Redis项目里搜索lru，找到代码在redis.c的freeMemoryIfNeeded()函数里。

先看2.6版的代码： 竟然就是随机找三条记录出来，比较哪条空闲时间最长就删哪条，然后再随机三条出来，一直删到内存足够放下新记录为止.......可怜我看配置文档后的想象，一直以为它会帮我在整个Redis里找空闲时间最长的，哪想到我有一百万条记录的时候，它随便找三条就开始删了。

好，收拾心情再看3.0版的改进：现在每次随机五条记录出来，插入到一个长度为十六的按空闲时间排序的队列里，然后把排头的那条删掉，然后再找五条出来，继续尝试插入队列.........嗯，好了一点点吧，起码每次随机多了两条，起码不只在一次随机的五条里面找最久那条，会连同之前的一起做比较......

中规中矩的Memcached

相比之下，Memcached实现的是再标准不过的LRU算法，专门使用了一个教科书式的双向链表来存储slab内的LRU关系，代码在item.c里，详见memcached源码分析-----LRU队列与item结构体，元素插入时把自己放到列头，删除时把自己的前后两个元素对接起来，更新时先做删除再做插入。

分配内存超限时，很自然就会从LRU的队尾开始清理。

同样中规中矩的Guava Cache

Guava Cache同样做了一个双向的Queue，见LocalCache中的AccessQueue类，也会在超限时从Queue的队尾清理，见evictEntries()函数。

和Redis旧版一样的Ehcache/Hazelcast

看文档，居然和Redis2.6一样，直接随机8条记录，找出最旧那条，刷到磁盘里，再看代码，Eviction类和 OnHeapStore的evict()函数。

再看Hazelcast，几乎一样，随机取25条。 这种算法，切换到LFU也非常简单。

小结

不过后来再想想，也许Redis本来就不是主打做Cache的，这种内存爆了需要通过LRU删掉一些元素不是它的主要功能，默认设置都是noeviction——内存不够直接报错的，所以就懒得建个双向链表，而且每次访问时都要更新它了，看Google Group里长长的讨论，新版算法也是社区智慧的结晶。何况，Ehcache和Hazelcast也是和它的旧版一样的算法，Redis的新版还比这两者强了。

后来，根据@刘少壮同学的提示，JBoss的InfiniSpan里还实现了比LRU更高级的LIRS算法，可以避免一些冷数据因为某个原因被大量访问后，把热数据挤占掉。

2. 过期键删除

如果能为每一个设置了过期的元素启动一个Timer，一到时间就触发把它删掉，那无疑是能最快删除过期键最省空间的，在Java里用一条DeplayQueue存着，开条线程不断的读取就能做到。但因为该线程消耗CPU较多，在内存不紧张时有点浪费，似乎大家都不用这个方法。

所以有了惰性检查，就是每次元素被访问时，才去检查它是否已经超时了，这个各家都一样。但如果那个元素后来都没再被访问呢，会永远占着位子吗？所以各家都再提供了一个定期主动删除的方式。

Redis

代码在redis.c的activeExpireCycle()里，看过文档的人都知道，它会在主线程里，每100毫秒执行一次，每次随机抽20条Key检查，如果有1/4的键过期了，证明此时过期的键可能比较多，就不等100毫秒，立刻开始下一轮的检查。不过为免把CPU时间都占了，又限定每轮的总执行时间不超过1毫秒。

Memcached

Memcached里有个文不对题的LRU爬虫线程，利用了之前那条LRU的队列，可以设置多久跑一次(默认也是100毫秒)，沿着列尾一直检查过去，每次检查LRU队列中的N条数据。虽然每条Key设置的过期时间可能不一样，但怎么说命中率也比Redis的随机选择N条数据好一点，但它没有Redis那种过期的多了立马展开下一轮检查的功能，所以每秒最多只能检查10N条数据，需要自己自己权衡N的设置。

Guava Cache

在Guava Cache里，同一个Cache里所有元素的过期时间是一样的，所以它比Memached更方便，顺着之前那条LRU的Queue检查超时，不限定个数，直到不超时为止。而且它这个检查的调用时机并不是100毫秒什么的，而是每次各种写入数据时的preWriteCleanup()方法中都会调用。

吐槽一句，Guava的Localcache类里面已经4872行了，一点都不轻量了。

Ehcache

Ehcache更乱，首先它的内存存储中只有惰性检查，没有主动检查过期的，只会在内存超限时不断用近似LRU算法(见上)把内存中的元素刷到磁盘中，在文件存储中才有超时检查的线程，FAQ里专门解释了原因。

然后磁盘存储那有一条8小时左右跑一次的线程，每次遍历所有元素.....见DiskStorageFactory里的DiskExpiryTask。 一圈看下来，Ehcache的实现最弱。

Algo Ramblings: LRUCache in java
The simplest way to create a cache using LinkedHashMap is to extend it. The constructor takes as an argument the maximum number of entries we want a Cache object to hold. The superclass constructor has three arguments: the initial capacity of the map, the load factor, and a boolean argument that tells theLinkedHashMap constructor to keep entries in access order instead of the default insertion order.


Android LruCache
https://github.com/android/platform_frameworks_base/blob/master/tools/layoutlib/bridge/src/android/util/LruCache.java
https://segmentfault.com/a/1190000004993260

public final V put(K key, V value) {
    if (key == null || value == null) {
        throw new NullPointerException("key == null || value == null");
    }

    V previous;
    synchronized (this) {
        putCount++;
        size += safeSizeOf(key, value);
        previous = map.put(key, value);
        if (previous != null) {
            size -= safeSizeOf(key, previous);
        }
    }

    if (previous != null) {
        entryRemoved(false, key, previous, value);
    }

    trimToSize(maxSize);
    return previous;
}

protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}

如果 key 或者 value 为空会抛出异常，否则在同步块中进行添加操作。首先是 putCount 加一，然后调用 safeSizeOf 方法增加size，接着把数据放到 map 中，如果这个 key 已经存放了数据，那么应该减去这条数据的大小，因为它已经被覆盖调了。同步块结束后，如果确实覆盖了数据，会调用 entryRemoved，这个方法默认是空，什么也没做，我们自己创建 LruCache 时可以选择重写。最后还需要调用 trimToSize，这个方法用来防止数据超出 maxSize。

上面在计算 size 大小时调用了 safeSizeOf 方法，看名字就觉得不一般，继续看它的代码：

private int safeSizeOf(K key, V value) {
    int result = sizeOf(key, value);
    if (result < 0) {
        throw new IllegalStateException("Negative size: " + key + "=" + value);
    }
    return result;
}
protected int sizeOf(K key, V value) {
    return 1;
}

这个方法又调用了 sizeOf 返回数据的大小，如果小于 0 抛出异常，否则就返回。sizeOf 这个方法是我们熟悉的，一般使用LruCache 都会重写这个方法返回每条数据的实际大小。为什么要重写呢？ 因为这个方法默认的实现是返回 1。这样的话，size 相当于记录的是缓存数据的条数，而这可能并不是我们想要的。

public void trimToSize(int maxSize) {
    while (true) {
        K key;
        V value;
        synchronized (this) {
            if (size < 0 || (map.isEmpty() && size != 0)) {
                throw new IllegalStateException(getClass().getName() + ".sizeOf() is reporting inconsistent results!");
            }

            if (size <= maxSize) {
                break;
            }

            Map.Entry<K, V> toEvict = map.eldest();
            if (toEvict == null) {
                break;
            }

            key = toEvict.getKey();
            value = toEvict.getValue();
            map.remove(key);
            size -= safeSizeOf(key, value);
            evictionCount++;
        }

        entryRemoved(true, key, value, null);
    }
}

内部是一个无限循环，删除 map 里面最久未使用的，然后更新 size，如果 size 小于 maxSize 就跳出循环。

public final V get(K key) {
    if (key == null) {
        throw new NullPointerException("key == null");
    }

    V mapValue;
    synchronized (this) {
        mapValue = map.get(key);
        if (mapValue != null) {
            hitCount++;
            return mapValue;
        }
        missCount++;
    }

    //找不到就创建一个value
    V createdValue = create(key);
    if (createdValue == null) {
        return null;
    }

    synchronized (this) {
        createCount++;
        mapValue = map.put(key, createdValue);

        if (mapValue != null) {
            // There was a conflict so undo that last put
            map.put(key, mapValue);
        } else {
            size += safeSizeOf(key, createdValue);
        }
    }

    if (mapValue != null) {
        entryRemoved(false, key, createdValue, mapValue);
        return mapValue;
    } else {
        trimToSize(maxSize);
        return createdValue;
    }
}

protected V create(K key) {
    return null;
}

key 依然不能为空，然后就是从 map 中取数据，递增hitCount，最后直接返回数据。这是成功找到缓存的情况，如果找不到还会执行下面的代码。下面的逻辑是调用 create 创建 value。create需要我们自己重写，默认返回 null，所以默认情况下找不到缓存就返回 null。 如果重写了 create 那么接着会把新建的数据加入 map，并且增加 size，执行 trimToSize 等操作。

https://madcoda.com/2012/10/using-lrucache-to-cache-bitmaps-and-limit-memory-usage/

Limiting the LruCache size by their count may not seemed useful when you are caching Bitmaps because they varies in size. If you set the cache size to 20, you could easily get OutOfMemoryError if the bitmaps are 2MBs each! What worse is that the LruCache now maintains a hard reference to the Bitmaps so they cannot be GC! We definitely need to limit the memory usage of the cache. Good news is that the LruCache class has a sizeof() method which you can override. Redefine the “size” to measure num of bytes and you’re done.

public class BitmapCache extends LruCache<String, Bitmap> {

public bitmapCache(int maxSizeBytes) {

super(maxSizeBytes);

}

@Override

protected int sizeOf(Long key, Bitmap value) {

return value.getByteCount();

}

}

https://techienotes.info/2015/08/28/caching-bitmaps-in-android-using-lrucache/
http://givemepass-blog.logdown.com/posts/300649-how-to-use-the-lrucache

Read full article from Algo Ramblings: LRUCache in java
http://www.thinkingyu.com/articles/LIRS/