redis之数据过期清除策略、缓存淘汰策略详解

# maxmemory <bytes> //redis占用的最大内存

#maxmemory-policy noeviction

typedef struct redisobject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:lru_bits;
 /* 
\*lru time (relative to global lru_clock) or
\* lfu data (least significant 8 bits frequency
\* and most significant 16 bits access time). 
*/
int refcount;
void *ptr;
} robj;

long timemillis=system.currenttimemillis();
system.out.println(timemillis/1000); //获取当前秒
system.out.println(timemillis/1000 & ((1<<24)-1));//获取秒的后24位

11111111111111111000000000011111110 假如这个是我当前秒单位的时间，获取后8位 是 11111110
11111111111111111000000000011111111 获取后8位 是11111111
11111111111111111000000000100000000 获取后8位 是00000000

unsigned long long estimateobjectidletime(robj *o) {
	//获取秒单位时间的最后24位
	unsigned long long lruclock = lru_clock();
	//因为只有24位，所有最大的值为2的24次方-1
	//超过最大值从0开始，所以需要判断lruclock（当前系统时间）跟缓存对象的lru字段的大小
	if (lruclock >= o->lru) {
	//如果lruclock>=robj.lru，返回lruclock-o->lru，再转换单位
	return (lruclock - o->lru) * lru_clock_resolution;
	} else {
	//否则采用lruclock + (lru_clock_max - o->lru)，得到对象的值越小，返回的值越大，越大越容易被淘汰
	return (lruclock + (lru_clock_max - o->lru)) *
	lru_clock_resolution;
	}
}

typedef struct redisobject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:lru_bits;
 /* lru time (relative to global lru_clock) or
* lfu data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;

uint8_t lfulogincr(uint8_t counter) {
	//如果已经到最大值255，返回255 ，8位的最大值
	if (counter == 255) return 255;
	//得到随机数（0-1）
	double r = (double)rand()/rand_max;
	//lfu_init_val表示基数值（在server.h配置）
	double baseval = counter - lfu_init_val;
	//如果达不到基数值，表示快不行了，baseval =0
	if (baseval < 0) baseval = 0;
	//如果快不行了，肯定给他加counter
	//不然，按照几率是否加counter，同时跟baseval与lfu_log_factor相关
	//都是在分子，所以2个值越大，加counter几率越小
	double p = 1.0/(baseval*server.lfu_log_factor+1);
	if (r < p) counter++;
	return counter;
}

unsigned long lfudecrandreturn(robj *o) {
	//lru字段右移8位，得到前面16位的时间
	unsigned long ldt = o->lru >> 8;
	//lru字段与255进行&运算（255代表8位的最大值），
	//得到8位counter值
	unsigned long counter = o->lru & 255;
	//如果配置了lfu_decay_time，用lfutimeelapsed(ldt) 除以配置的值
	//lfutimeelapsed(ldt)源码见下
	//总的没访问的分钟时间/配置值，得到每分钟没访问衰减多少
	unsigned long num_periods = server.lfu_decay_time ?lfutimeelapsed(ldt) / server.lfu_decay_time : 0;
	if (num_periods)
	//不能减少为负数，非负数用couter值减去衰减值
	counter = (num_periods > counter) ? 0 : counter - num_periods;
	return counter;
}

//对象ldt时间的值越小，则说明时间过得越久
unsigned long lfutimeelapsed(unsigned long ldt) {
	//得到当前时间分钟数的后面16位
	unsigned long now = lfugettimeinminutes();
	//如果当前时间分钟数的后面16位大于缓存对象的16位
	//得到2个的差值
	if (now >= ldt) return now-ldt;
	//如果缓存对象的时间值大于当前时间后16位值，则用65535-ldt+now得到差值
	return 65535-ldt+now;
}

/**
 * @description :
 * @author : huangcong
 * @date : 2023/6/28 9:48
 **/
public class linkedhashmaplru<k, v> extends linkedhashmap<k, v> {

    private integer initialcapacity;

    public linkedhashmaplru(integer initialcapacity) {
        super(initialcapacity, 0.75f, boolean.false);
        this.initialcapacity = initialcapacity;
    }

    @override
    protected boolean removeeldestentry(map.entry<k, v> eldest) {
        return super.size() > initialcapacity;
    }

    public object getvalue(object key) {
        object v = super.get(key);
        if (objects.isnull(v)) {
            return -1;
        }
        return v;
    }

    public static void main(string[] args) {
        linkedhashmaplru<object, object> hashmaplru = new linkedhashmaplru<>(3);
        hashmaplru.put(1, "a");
        hashmaplru.put(2, "b");
        hashmaplru.put(3, "c");
        system.out.println(hashmaplru.entryset());

        // key存在变更其数据
        hashmaplru.put(3, "l");
        system.out.println(hashmaplru.entryset());

        // 当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值
        hashmaplru.put(4, "d");
        system.out.println(hashmaplru.entryset());

        hashmaplru.put(5, "f");
        system.out.println(hashmaplru.entryset());

        // 获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1
        object value =hashmaplru.getvalue(1);
        system.out.println(value);
    }
}

/**
 * @description : 构造一个node节点，承载数据
 * @author : hc
 * @date : 2023/6/28 12:14
 **/
public class node<k, v> {

    k key;

    v value;

    node<k, v> pre;

    node<k, v> next;

    public node() {
    }

    public node(k key, v value) {
        this.key = key;
        this.value = value;
        this.pre = this.next = null;
    }

    public void setkey(k key) {
        this.key = key;
    }

    public void setvalue(v value) {
        this.value = value;
    }
}

/**
 * @description :双向链表
 * @author : hc
 * @date : 2023/6/28 12:23
 **/
public class lrucache <k,v>{

    node<k,v> head;
    node<k,v> tail;

    public lrucache() {
        head = new node<>();
        tail = new node<>();
        head.next = tail;
        tail.pre = head;
    }

    // 头插法，靠近头部的是最新的数据
    public void add(node<k,v> node){
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
    }

    public void delete(node<k,v> node){
        node.next.pre =node.pre;
        node.pre.next = node.next;
        node.next = null;
        node.pre = null;
    }

    public node getnode(){
        return tail.pre;
    }

    // 打印链表
    public string getcache(){
        stringbuffer stringbuffer = new stringbuffer();
        node<k, v> node = head.next;
        while (node != tail){
            stringbuffer.append(node.key+"="+node.value + "\r\n");
            node = node.next;
        }
        return stringbuffer.tostring();
    }
}

/**
 * @description :
 * hash表：通过hash函数计算出hash值，然后（hash值 % 数组大小）得到对应数组中的位置
 * @author : hc
 * @date : 2023/6/28 16:23
 **/
public class lru {

    private integer cachesize; // 规定容器大小
    private map<integer,node<integer,integer>> map; // hash表，方便查找
    private lrucache<integer,integer> doublelinkedmap;// 双向链表，方便插入以及删除

    public lru(integer cachesize) {
    this.cachesize = cachesize;
    map = new hashmap<>();
    doublelinkedmap = new lrucache<>();
    }

    public int get(integer key){
        if (!map.containskey(key)){
            return -1;
        }
        node<integer, integer> node = map.get(key);
        doublelinkedmap.delete(node);
        doublelinkedmap.add(node);
        return node.value;
    }

    public integer put(integer key,integer value){
        // 如果哈希表中有，替换节点的value值
        if (map.containskey(key)){
            node<integer, integer> node = map.get(key);
            node.setvalue(value);
            doublelinkedmap.delete(node);
            doublelinkedmap.add(node);
            return key;
        }
        node<integer, integer> node = new node<>(key, value);
        // 如果hash没有，且容器中数据已经达到了规定大小，删除最后一个数据，在头部添加一个最新数据
        if (map.size() >= cachesize){
            node lastnode = doublelinkedmap.getnode();
            doublelinkedmap.delete(lastnode);
            doublelinkedmap.add(node);
            map.remove(key);
            map.put(key,node);
            return key;
        }
        // 如果hash没有，且容器中数据未达到了规定大小，直接在头部添加一个最新数据
        doublelinkedmap.add(node);
        map.put(key,node);
        return key;
    }

    // 删除节点
    public integer delete(integer key){
        if (!map.containskey(key)){
            return -1;
        }
        node<integer, integer> node = map.get(key);
        doublelinkedmap.delete(node);
        map.remove(key);
        return key;
    }

    public static void main(string[] args) {
        lru lru = new lru(3);
        lru.put(1,1);
        lru.put(2,2);
        lru.put(3,3);
        system.out.println(lru.doublelinkedmap.getcache());

        lru.put(2,4);
        system.out.println(lru.doublelinkedmap.getcache());

        lru.put(4,4);
        system.out.println(lru.doublelinkedmap.getcache());

        int i = lru.get(3);
        system.out.println(i);
        system.out.println(lru.doublelinkedmap.getcache());
    }
}