vlambda博客
学习文章列表

/**
 * LRU缓存算法实现
 */
public class LRUCache<k, v> {
    //容量
    private int capacity;
    //当前有多少节点的统计
    private int count;
    //缓存节点
    private Map<k, Node<k, v>> nodeMap;
    private Node<k, v> head;
    private Node<k, v> tail;
    public LRUCache(int capacity) {
        if (capacity < 1) {
            throw new IllegalArgumentException(String.valueOf(capacity));
        }
        this.capacity = capacity;
        this.nodeMap = new HashMap<>();
        //初始化头节点和尾节点，利用哨兵模式减少判断头结点和尾节点为空的代码
        Node headNode = new Node(null, null);
        Node tailNode = new Node(null, null);
        headNode.next = tailNode;
        tailNode.pre = headNode;
        this.head = headNode;
        this.tail = tailNode;
    }
    public void put(k key, v value) {
        Node<k, v> node = nodeMap.get(key);
        if (node == null) {
            if (count >= capacity) {
                //先移除一个节点
                removeNode();
            }
            node = new Node<>(key, value);
            //添加节点
            addNode(node);
        } else {
            //移动节点到头节点
            moveNodeToHead(node);
        }
    }
    public Node<k, v> get(k key) {
        Node<k, v> node = nodeMap.get(key);
        if (node != null) {
            moveNodeToHead(node);
        }
        return node;
    }
    private void removeNode() {
        Node node = tail.pre;
        //从链表里面移除
        removeFromList(node);
        nodeMap.remove(node.key);
        count--;
    }
    private void removeFromList(Node<k, v> node) {
        Node pre = node.pre;
        Node next = node.next;

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

        node.next = null;
        node.pre = null;
    }
    private void addNode(Node<k, v> node) {
        //添加节点到头部
        addToHead(node);
        nodeMap.put(node.key, node);
        count++;
    }
    private void addToHead(Node<k, v> node) {
        Node next = head.next;
        next.pre = node;
        node.next = next;
        node.pre = head;
        head.next = node;
    }
    public void moveNodeToHead(Node<k, v> node) {
        //从链表里面移除
        removeFromList(node);
        //添加节点到头部
        addToHead(node);
    }
    class Node<k, v> {
        k key;
        v value;
        Node pre;
        Node next;
        public Node(k key, v value) {
            this.key = key;
            this.value = value;
        }
    }
}

/**
 *Redis存储的value对象
 */
typedef struct redisObject {
    unsigned type:4; 
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /*在LRU算法中，24 bits的lru是用来记录LRU time的。
                                                    在LFU中也可以使用这个字段，不过是分成16 bits与8bits使用，
                                                    高16bits的用来记录最近一次计数器降低的，时间ldt( Last decr time)，单位是分钟，
                                                    低8bits记录计数器数值counter(LOG_C)。*/
    int refcount;
    void *ptr;
} robj;

lfu-log-factor  10 #可以调整计数器counter的增长速度，lfu-log-factor越大，counter增长的越慢。
lfu-decay-time  1   #是一个以分钟为单位的数值，可以调整counter的减少速度   

//LFU算法更新策略
void updateLFU(robj *val) {
    unsigned long counter = LFUDecrAndReturn(val); #调用减少次数的函数
    counter = LFULogIncr(counter); #调用增加次数的函数
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}
//减少次数函数
unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8; #获取最近一次的记录时间
    unsigned long counter = o->lru & 255; #获取最近一次记录的访问次数
    #根据配置的lfu_decay_time计算应该降低多少，其中LFUTimeElapsed用来计算当前时间与ldt的差值
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    #已过去n个lfu_decay_time，则将counter减少n，counter - num_periods。 
   if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    return counter;
}
/**
 *增加次数函数
 *counter并不是简单的访问一次就+1，而是采用了一个0-1之间的p因子控制增长。
 *counter最大值为255。取一个0-1之间的随机数r与p比较，当r<p时，才增加counter，这和 
 *比特币中控制产出的策略类似。p取决于当前counter值与lfu_log_factor因子，counter值 
 *与lfu_log_factor因子越大，p越小，r<p的概率也越小，counter增长的概率也就越小。
*/
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}
//增长情况如下,可见counter增长与访问次数呈现对数增长的趋势，随着访问次数越来越大，counter增长的越来越慢。
+--------+------------+------------+------------+------------+------------+
| factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   |
+--------+------------+------------+------------+------------+------------+
|      0      | 104            | 255             | 255             | 255        | 255              |
+--------+------------+------------+------------+------------+------------+
|      1      | 18              | 49               | 255             | 255        | 255               |
+--------+------------+------------+------------+------------+------------+
|     10     | 10              | 18               | 142             | 255        | 255              |
+--------+------------+------------+------------+------------+------------+
|    100    | 8                | 11               | 49               | 143        | 255              |
+--------+------------+------------+------------+------------+------------+