背景

最近学习nginx源码,了解到lru算法,lru算法一般应用在缓存的数据淘汰。还没有来得及详细了解lru算法在nginx中的应用,初步了解了一下lru算法,总结一下,等过段时间再来补充。

场景

我们现在的程序需要从某个地方获取数据,比如说硬盘或者远程服务器,这个获取的过程比较耗时,而且往往会重复获取相同的数据。

我们需要在本地建一个缓存池,如果获取相同的数据的话,那我们就直接从缓存池中拿就好了,这样会大大节省时间。但是,缓存池是存储在内存里面的,内存大小有限,所以我们需要给缓存池限制一个大小,这就导致了我们的缓存池容量达到顶峰的时候,再加入新的缓存需要删除一些现有的缓存。

根据lru算法,我们删除的缓存就是时间最长没有使用过的那些。也就是近期最少使用的。

其实这个算法很好实现,我们用一个最后一次使用的时间戳去对每一个缓存标志一下,然后缓存满了之后,当我们再加入新缓存的时候,我们把所有的缓存遍历一下,删除最少使用的k个缓存即可。但是这样实现的话,时间复杂度是O(n),当缓存量很大的时候,导致时间复杂度很高,缓存反而浪费了大量时间。

如果我们的缓存池缓存量不够大的话,那么缓存的命中率就会很低,也起不到很好的性能优化效果。

所以,我们需要设计一个时间复杂的足够小的算法来解决这个问题。

实现

我们使用一个DataPool来模拟硬盘或者远程服务器的数据,我们要获取的数据是Student学生信息,我们本地用一个CachePool来模拟缓冲池。

我们先来看一下Student、DataPool、CachePool的定义

class Student {
    public Student(String name, int age, int classId){
        this.name = name;
        this.age = age;
        this.classId = classId;
    }
    public String name;
    public int age;
    public int classId;
}

class DataPool {
    private Map<String, Student> pool;

    public DataPool(){
        pool = new HashMap<>();
    }
    public Student getData(String key){
        return pool.get(key);
    }
    public void setData(String key, Student student){
        pool.put(key, student);
    }
}

class Cache {
    private Map<String, Student> pool = new HashMap<>();
    private Map<String, DLinked> flag = new HashMap<>();
    private int size;
    private DLinked head, tail;

    public Cache(int size){
        this.size = size;
    }

    public Student getData(DataPool dataPool, String key){
        Student result = pool.get(key);
        if (result != null) {
            DLinked node = flag.get(key);
            node.pre.next = node.next;
            node.next.pre = node.pre;
            tail.next = node;
            tail = node;
            return result;
        }

        result = dataPool.getData(key);
        DLinked node = new DLinked(key);
        if (head == null) head = tail = node;
        else {
            tail.next = node;
            node.pre = tail;
            tail = node;
        }

        flag.put(key, node);
        setData(key, result);
        return result;
    }

    public void setData(String key, Student val){
        if (pool.size() == size) lru();
        pool.put(key, val);
    }

    public class DLinked{
        public DLinked(String cur){
            this.cur = cur;
            this.next = this.pre = null;
        }
        public String cur;
        public DLinked pre;
        public DLinked next;
    }

    public void lru(){
        DLinked tmp = head;
        head = head.next;
        pool.remove(tmp.cur);
        flag.remove(tmp.cur);
    }

    public void show(){
        System.out.println("=================================");
        Iterator<Map.Entry<String, Student>> it = pool.entrySet().iterator();
        while(it.hasNext()){
            Student s = it.next().getValue();
            System.out.println(s.name);
        }
        System.out.println("=================================");
    }
}

我们设置缓存的目的就是为了快速定位我们需要的数据,所以,我们需要用Map容器去存我们的数据。

我们为了定位近期最少使用的数据的话,可以使用双向链表来实现,链表的尾部是最近使用的数据,首部是最近最少使用的数据。

当我们获取缓存的时候,如果这个数据已经在缓存中,我们就把这个数据放到队尾,我们通过Map结构来映射链表指向的缓存数据,如果这个数据没有在缓存中,我们就从DataPool中获取,然后放入缓存,放入链表的尾部。

我们使用下面的代码测试一下。

public class Main {
    static void initDataPool(DataPool dataPool){
        dataPool.setData("linukey", new Student("linukey", 22, 1));
        dataPool.setData("binghe", new Student("binghe", 23, 2));
        dataPool.setData("lisi", new Student("lisi", 24, 3));
        dataPool.setData("wangwu", new Student("wangwu", 25, 4));
        dataPool.setData("zhouliu", new Student("zhouliu", 26, 5));
    }
    public static void main(String[] args) {
        DataPool dataPool = new DataPool();
        Cache cache = new Cache(2);

        initDataPool(dataPool);

        cache.getData(dataPool, "linukey");
        cache.show();
        cache.getData(dataPool, "binghe");
        cache.show();
        cache.getData(dataPool, "lisi");
        cache.show();
        cache.getData(dataPool, "wangwu");
        cache.show();
        cache.getData(dataPool, "zhouliu");
        cache.show();
    }
}

总结

以上是对lru算法的一个初步学习,后面详细了解lru算法在nginx中的应用后,会再更新。


原创文章,转载请注明地址: 文章地址