Java:手写线程平安LRU缓存X探讨影响命中率的因素

admin • 2020年5月7日 21:08 • 时事新闻 • 阅读 57

最近遇到一个需求，需要频仍接见数据库，然则接见的内容只是 id + 名称 这样的简朴键值对。

频仍的接见数据库，网络上和内存上都会给数据库服务器带来不小肩负。

于是计划写一个简朴的LRU缓存来缓存这样的键值对。思量到tomcat的用户设施接见是多线程举行的。

以是还要保证cache是线程平安的。制止在用户操作的时刻修改了cache导致其他用户读到不合法的信息。

 构想

一, 数据结构选取

思绪:

1.最简朴的是用链表，最新接见的元素所在节点插入到头节点的后面，当要接纳的时刻就去释放链表尾部节点。

问题 ： 若是数据量伟大，那么这条链表就会十分长，即使是线性时间庞大度的查找，也会耗掉不少时间。

2.打散链表，接纳散列法，将节点散列到散列表中，这样，我们一长条的链表就会被打散成若干长度更小的链表。

Java:手写线程平安LRU缓存X探讨影响命中率的因素

如果我们的散列算法设计适合，让整个链表平均的洒在散列表上，那么所用时间最坏情形可以 酿成原本的 1/m ， m是散列表的巨细。

3.在2中，虽然我们使用了散列表来打散，然则若是散列算法欠妥，或者正好碰着最坏情形，照样有可能节点集中在一条链上。

Java:手写线程平安LRU缓存X探讨影响命中率的因素

 

 

 

以是我们可以把链表设计成树，这样我们就保证了最坏时的logN级的查找庞大度。

Java:手写线程平安LRU缓存X探讨影响命中率的因素

 

 

 

总体上方式3会比2高效，然则实现起来庞大得多，以是我们接纳方式2。

 

二, 接纳计谋

接纳的时刻需要思量到

1.怎么样让接纳的内容在最近尽可能不被接见到，这可能需要连系自己的程序营业来决议，一样平常的做法是接纳最近最少使用的内容，不可能准确展望某内容在不久

的未来不被接见。

2.接纳内容之后需要让整个存储结构尽可能平均，尽可能不泛起

 

 

 

 Java:手写线程平安LRU缓存X探讨影响命中率的因素

 

这种情形。

于是接纳计谋，接纳最长的谁人链表的末尾节点，这种做法不能说百分百可靠，

可能由于散列算法设计不合理，导致节点都群集在某个槽中，这样的话谁人槽的链表就会稀奇长。

这时这个链表上的节点总是要接见的，然则我们接纳的是最长的链表，那么我们总是在接纳最近要接见的内容

就很不合理，然则若是我们的散列算法适合，那么我们就能接纳的同时保持整个散列表结构逻辑上平均。

绝对平均也欠好，由于若是绝对平均，那么就没有一个较长的链表，可以缓存尽可能多，最近被频仍接见的内容。

以是，散列算法的设计十分主要。

三, 线程平安

线程平安，这里是简朴地接纳 ReentrantReadWriteLock，分为读写两把锁，在读取缓存但不写的时刻，占用读锁。

若是没掷中，需要向散列表中写新内容，或修改，则占用写锁。

注重点:

 　　并发编程使用 ReentrantReadWriteLock 无法做到锁升级，需要释放读锁之后再获取写锁。

在释放读锁到获取写锁之间，需要思量到所有其他线程获取写锁修改某些我们需要的量的情形。

好比我们对A接见用读写锁R

　　R.readLock().lock();

　　M = null;

//0

　　if(A != null){

　　　　M = A;

　　}

　　R.readLock().unlock();

//1

　　R.writeLock().lock();

//2

　　function(M);

　　A = new XX();

在1处，可能有其他线程先占有了写锁，而且执行完了2之后的代码，以是我们在0处的判断就失效了。

以是在2之后还需要判断

//2

　　if(A != null){

　　M = A;

　　}

也就是要思量释放读锁与获取写锁之间，其他线程可能获取写锁修改某些共享量。

在下面的代码注释中有详细说明

最先编写

首先，我们要实现我们选取的数据结构，这里选的是2中的数据结构。

3中的数据结构读者可以自行实现，需要注重的是，树若是旋转，则需要把旋转后的根节点挂到散列表上

1.链表设计

我们知道，链表的脱链和挂入有时刻需要检查前驱后继节点是否非空。这使得我们的代码实现起来很庞大，而且维护的时刻阅读也不方便。

于是我们计划让一根链表生来就有头和尾节点，这两个节点存放的值是无用的，这两个节点是闲置的，这样我们删除链表中的某个节点时

就不用检查他的前驱后继是否非空，由于有一最先的两个头尾节点，前驱后继肯定非空。

我们接纳的时刻接纳的是尾节点的前一个节点。有一种特殊情形，若是头节点和尾节点之间没有其他节点呢？接纳的不就是头节点？

我们的接纳计谋是接纳长度最长的链表中的节点，而且当整个散列表的巨细到达了特定值才会接纳，以是一样平常不会接纳头节点。

虽然多了头和尾两个节点，然则相比于我们成千上万的数据，微不足道。

  private class Node{

        /**
         * 当前节点的id
         */
        long now;

        /**
         * id - 名称键值对中的名称
         */
        String name;

        /**
         * 前驱
         */
        Node pre;

        /**
         * 后继
         */
        Node next;
    }

2.每条链表的治理结构

为了治理每个链表，好比纪录链表的长度信息，保留链表的头尾指针（引用）。我们需要用一个数据结构治理链表

 private class HeadManager{

        /**
         * 链接前一个治理结构(链表长度小于即是当前链表)和后一个治理结构(链表长度大于即是当前链表)
         */
        HeadManager pre, next;

        /**
         * 当前链表的长度
         */
        int size = 0;
        
        /**
         * 链表中闲置的头节点
        * */
        Node head = new Node();

        /**
         * 链表中闲置的尾节点
         */
        Node tail = new Node();
        
        {
            /*
             * 一最先让首尾相连
             */
            head.next = tail;
            tail.pre = head;
        }
    }

这些治理结构是根据各自的链表长度巨细组织成一条链表的，我们暂且称之为治理链表。当我们要接纳节点的时刻，就去找治理链表末尾的治理结构，把他的倒数第二个节点释放（尾节点闲置）。同样我们也需要闲置的治理结构头节点和尾节点来简化我们的代码。

总体框架：

public class PlatformCache {

    /**
     * 当整个散列表中的值跨越这个巨细，就会最先接纳
     */
    private static final int MAX_SIZE = 1024;

    /**
     * 散列表所在数组的初始巨细
     */
    private static final int INIT_SIZE = 64;

    private static Double rate = 0.0;

    private static Double time = 0.0;

    /**
     * 读写锁
     */
    private ReentrantReadWriteLock reentrantReadWriteLock;

    /**
     * 整个散列表中的节点数
     */
    private int size;

    /**
     * 散列表
     */
    private HeadManager[] tables;

    /**
     * 治理结构链表中的闲置头
     */
    private HeadManager inOrderHead;

    /**
     * 治理结构链表中的闲置尾
     */
    private HeadManager inOrderTail;

    /**
     * 单例
     */
    private static PlatformCache instance;

}
 
/**
* 获取单例
*/
public static PlatformCache getInstance(){
        if(instance == null){
            synchronized (PlatformCache.class){
                if(instance == null){
                    instance = new PlatformCache();
                }
            }
        }
        return instance;
}
public String getName(long id){
        try {//锁读锁 防止读入时修改
            reentrantReadWriteLock.readLock().lock();

            //简朴散列
            int index = hash(id);
            HeadManager manager = tables[index];

            //若是治理结构不在散列表中 就让fresh = true
            boolean fresh = false;

            if(manager != null){
                Node head = manager.head.next;
                while(head != null && head != manager.tail){

                    //掷中
                    if(id == head.now){
                        reentrantReadWriteLock.readLock().unlock();
                        reentrantReadWriteLock.writeLock().lock();
                        //到这里的时刻，可能有其他线程操作过我们掷中了的节点
                        //以是需要看一下我们的节点有没有被删除（前驱后继为空）
                        if(head.pre == null || head.next == null){
                            //若是删除了，就跳出循环，和没掷中合并成同一种情形
                            reentrantReadWriteLock.readLock().lock();
                            reentrantReadWriteLock.writeLock().unlock();
                            break;
                        }
                        //移到前面 示意最近接见过
                        moveForward(manager, head);return head.name;
                    }
                    head = head.next;
                }
            }else{
                fresh = true;
            }

            //接见数据库
            Platform platform = mapper.selectByPrimaryKey(id);
            if(platform != null){
                    reentrantReadWriteLock.readLock().unlock();
                    //1
                    reentrantReadWriteLock.writeLock().lock();
                    //这里的检查很主要 由于在1处可能其余线程获得了锁
                    //修改了我们要接见的index下标处的内容
                    if(tables[index] == null){
                        //建立新的 治理结构 并挂到散列表上
                        manager = new HeadManager();
                        tables[index] = manager;
                    }else{
                        //若是其他线程建立了治理结构
                        //那么他们可能把我们想要的节点放到链表中了
                        //以是再次遍历节点，看看能否找到
                        manager = tables[index];
                        fresh = false;
                        Node head = manager.head.next;
                        while(head != null && head != manager.tail){
                            //掷中
                            if(id == head.now){
                                //下面不用加写锁由于当前已经获得写锁
                                //移到前面 示意最近接见过
                                moveForward(manager, head);
                                return head.name;
                            }
                            head = head.next;
                        }
                    }

                //新建一个Node
                Node more = new Node();
                more.name = platform.getPlatformName();
                more.now = platform.getPlatformId();

                //插入到链表中闲置头节点的下一位
                Node now = manager.head.next;
                manager.head.next = more;
                more.next = now;
                now.pre = more;
                more.pre = manager.head;

                //更改治理结构治理的链表巨细和总巨细
                manager.size ++;
                size ++;

                if(fresh){
                    //若是新建了治理结构 就把治理结构挂入到巨细行列
                    insertBeforeHead(manager);
                }

                //治理结构的链表巨细增添时排序治理结构行列
                whenInc(manager);

                //超出了我们的预算，则举行接纳
                if(size > MAX_SIZE){

                    if(inOrderTail.pre == inOrderHead){
                        logger.error("缓存中头和尾之间没有缓存节点!");
                        throw new ServiceException("缓存错误已经纪录日志");
                    }

                    //删除链表长度最大的治理结构的链表尾节点的前一个节点
                    //inOrderTail是闲置的治理结构尾节点
                    //inOrderTail.pre是链表长度最大的治理结构
                    //inOrderTail.pre.tail是链表闲置的尾节点
                    //inOrderTail.pre.tail.pre真正需要接纳的节点
                    deleteNode(inOrderTail.pre.tail.pre);

                    //治理结构的链表长度和散列表总巨细均-1
                    inOrderTail.pre.size --;
                    size --;
                    whenDec(inOrderTail.pre);
                }

                return platform.getPlatformName();
            }
            return null;
        }finally {
            //释放所有锁
            try {
                //保险起见 牢固释放读写锁
                try {
                    if(reentrantReadWriteLock.writeLock().isHeldByCurrentThread()){
                        reentrantReadWriteLock.writeLock().unlock();
                    }
                }catch (Exception e){
                }
                try {
                    reentrantReadWriteLock.readLock().unlock();
                }catch (Exception e){
                }
            }catch (Exception e){
                //可以写入日志
            }
        }

    }

辅助性方式外提:

　　private void deleteNode(Node node){
        Node next = node.next;
        node.pre.next = next;
        next.pre = node.pre;
        node.pre = node.next = null;
    }

    /**
     * 往后找，找到链表长度比自己小的治理结构，而且插到他后面
     */
    private void whenInc(HeadManager manager){
        HeadManager back = manager.next;

        while(back.size < manager.size && back != inOrderTail){

            back = back.next;
        }

        manager.pre.next = manager.next;
        manager.next.pre = manager.pre;

        HeadManager pre = back.pre;
        pre.next = manager;
        manager.pre = pre;

        back.pre = manager;
        manager.next = back;

    }

    private void insertBeforeHead(HeadManager manager) {
        HeadManager now = inOrderHead.next;

        inOrderHead.next = manager;
        manager.next = now;

        now.pre = manager;
        manager.pre = inOrderHead;
    }

    private int hash(Long id){
        Long tmp = id;
        id ^= tmp >>> 32;
        id ^= tmp >>> 16;
        id ^= tmp >>> 8;
        id ^= tmp >>> 4;
        return Math.toIntExact(id & (tables.length - 1));
    }

    /**
     * 往前找，找到链表长度比自己大的治理结构，而且插到他前面
     */
    private void whenDec(HeadManager manager){
        HeadManager front = manager.pre;

        while(front.size > manager.size && front != inOrderHead){
            front = front.pre;
        }
        manager.pre.next = manager.next;
        manager.next.pre = manager.pre;

        HeadManager next = front.next;
        front.next = manager;
        next.pre = manager;

        manager.pre = front;
        manager.next = next;
    }

　　 //被接见的节点放在链表头部 private void moveForward(HeadManager manager, Node head){
        Node now = manager.head;

        Node next = head.next;
        head.pre.next = next;
        next.pre = head.pre;

        head.pre = now;
        head.next = now.next;
        now.next.pre = head;
        now.next = head;
    }

 

Spring中资源的加载原来是这么一回事啊！

测试

测试了一下，不是很OK。

测试环境:

硬件: i5 4核CPU 内存8G

软件: Jmeter 300线程,每次请求使用limit 随机数,50 请求50条数据，数据库表中总共有3300条数据

　　  tomcat7.0

　　  JDK8.0

散列表的巨细是64

最大容纳Node个数是1024

系统跑到稳固的时刻，掷中率平均也许只有40%

其中稳固后的一组:

掷中率: 0.3817002017558209
各个链表长度：
0 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 0

Manager总数: 64
Node总数: 1024.0
方差: 8.0
散列表巨细:64

可以看出我们每个治理结构的链表长度都相等，整个散列表平均，然则掷中率着实太低。

我们改变一些量来实验提高掷中率。

实验1.改变散列算法

原本的散列法:

散列算法1：

int index = Math.toIntExact((id & (tables.length - 1)));

直接用以散列表长度-1 做为掩码取后几位做为下标。

 

我们接纳新的散列算法:

将id每一位的特征都用上。

散列算法2：

private int hash(Long id){
        id |= id >> 8;
        id |= id >> 8;
        id |= id >> 8;
        id |= id >> 8;
        return Math.toIntExact(id & (tables.length - 1));
 }

看看掷中率会不会提高。

运行稳固后，掷中率上升到50%左右。

运行稳固后的一组数据：

掷中率: 0.5101351858242434
各个链表长度：
0 1 2 3 6 7 7 7 8 8 9 9 9 9 9 10 10 11 11 12 14 16 16 16 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 21 21 21 21 21 21 21 21 21 21 21 21 21 21 0

Manager总数: 63
Node总数: 1024.0
方差: 43.465388506960714
散列表巨细 : 64

我们发现，虽然平均水平下降，然则掷中率有所上升，由于充分利用了元素标识id的特征。元素散列到散列表中的位置更有独特性。

固然，由于我们用的是按位或，以是元素会往数组下标大的偏向群集。

以是进一步改善我们的hash算法

散列算法3：

  private int hash(Long id){
        Long tmp = id;
        id ^= tmp >>> 32;
        id ^= tmp >>> 16;
        id ^= tmp >>> 8;
        id ^= tmp >>> 4;
        return Math.toIntExact(id & (tables.length - 1));
    }

我们让每一位都介入到特征值的天生中，然则削减了往下标大的地方群集的趋势

稳固后效果:

掷中率: 0.561265216523648
各个链表长度：
0 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 0

Manager总数: 64
Node总数: 1024.0
方差: 8.0
散列表巨细 : 64

我们发现散列表变得平均，掷中率响应也上升了不少。

与散列算法1比起来，散列表都是平均的，为什么掷中率高了靠近20%呢？

缘故原由可能是由于：算法1的散列表平均是接纳算法造成的，算法1散列的效果仍然很不平均，导致散列出的下标集中在某些地方。

频仍地对这些地方举行接见，可能频仍的在这些地方插入节点，以是这些活跃区域，也是长度增进最快的区域，而接纳的时刻又

总是接纳这些活跃区域，导致我们不久之前刚刚建立的节点总是被接纳，导致掷中率下降。

　　　　　　　   算法2虽然也是保持散列表平均，然则对散列表的接见由于散列算法散列得适合，以是涣散得对照开，以是是

“在平均情形下，增添一个，接纳一个，而且大大削减了接纳的是最近接见过的节点的概率”

实验2.改变散列表的巨细，但不改变最大Node数目

最大节点数照样1024，而散列表的槽数增添成128。

运行稳固后，掷中率没有显著的上升。

缘故原由可能是由于就算增添了槽数，但总的节点数稳定，该接纳照样接纳，导致掷中率没有显著上升。

然则链表的平均长度减小，在链表中遍历查询元素的时间削减。

使用散列算法2.

掷中率: 0.5074192929043583
各个链表长度：
0 1 1 1 1 1 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 7 7 8 8 8 8 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 0

Manager总数: 125
Node总数: 1024.0
方差: 9.836877824000004

 

使用散列算法3.

掷中率: 0.5587484035759898
各个链表长度：
0 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 0

Manager总数: 128
Node总数: 1024.0
方差: 1.0

实验3.散列表巨细稳定，增添节点个数

这个方式也许率是会增添掷中率的，由于削减了接纳次数，而且节点数靠近我们纪录总数的时刻，掷中率甚至可能靠近100%。

最大节点数增添成是2048，散列表的槽数为128。

运行稳固后: 掷中率靠近100%

使用散列算法2.

掷中率: 0.9811895632415405
各个链表长度：
0 1 1 1 1 1 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 7 8 8 8 8 8 9 9 9 10 10 10 11 11 11 11 11 11 11 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 14 14 14 15 15 15 15 15 16 16 16 17 18 18 18 18 18 20 20 20 20 20 21 21 22 22 23 25 34 35 37 37 37 37 38 38 39 40 40 40 41 41 42 45 46 49 49 49 49 50 50 50 0

Manager总数: 125
Node总数: 2048.0
方差: 198.067511296

实验4.改变接纳计谋

简朴的接纳接纳当前位置的末尾节点。

好比我们在0号位置插入一个新增的Node，导致整个散列表节点数跨越了最大值，那么就直接接纳0号位置的末尾节点（不是真正的末尾节点，真正的末尾节点被闲置）

使用散列算法2

掷中率: 0.5508982035928144
0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 9 9 10 10 10 10 10 10 11 11 11 11 12 12 12 13 13 14 15 16 16 17 18 19 20 20 20 20 21 21 22 23 23 24 25 28 29 29 31 34 0
Manager总数: 125
Node总数: 1024.0
方差: 57.676877824
散列表巨细 : 128

 

使用散列算法3

掷中率: 0.561866802451144
0 1 4 4 4 4 4 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 12 12 12 12 13 14 0
Manager总数: 128
Node总数: 1024.0
方差: 5.578125
散列表巨细 : 128

掷中率并没有多大的转变，然则散列表平均水平下降。

 

扩容与重散列:

明天考试，以后再更

 

最终接纳了：

1.散列算法3，保证散列的平均性

2.接纳最长链表

3.最大节点数 : 接纳总数据量的45%。好比总共有1000条数据，则最多有450个节点。选取的理由是掷中率可以到达80%，知足我的营业需求

Java:手写线程平安LRU缓存X探讨影响命中率的因素

 

 1500 / 3300 约即是 45%

 

固然，这是我的鸡肋营业，若是真的要用到海量数据的营业中去，则仅供参考。

有不妥之处，多谢指出。

原创文章，作者：admin，如若转载，请注明出处：https://www.2lxm.com/archives/8101.html

赞 (0)
admin admin
0 0
美国流感病人中有若干是新冠患者
« 上一篇 2020年5月7日 20:40
二分搜索树看这篇就足够了
下一篇 » 2020年5月7日 21:08

相关推荐