关于redis:java-从零开始手写-redis11clock时钟淘汰算法详解及实现

前言

java 从零手写实现 redis（一）如何实现固定大小的缓存？

java 从零手写实现 redis（三）redis expire 过期原理

java 从零手写实现 redis（三）内存数据如何重启不失落？

java 从零手写实现 redis（四）增加监听器

java 从零手写实现 redis（五）过期策略的另一种实现思路

java 从零手写实现 redis（六）AOF 长久化原理详解及实现

java 从零开始手写 redis（七）LRU 缓存淘汰策略详解

后面咱们实现了 FIFO/LRU/LFU 等常见的淘汰策略，不过在操作系统中，实际上应用的是时钟页面置换算法。

LRU 的性能的确很好，不过比拟耗费内存，而且实现比拟麻烦。

时钟页面置换算法就是一种近似 LRU 的算法实现，能够看作是对 FIFO 算法的改良。

Clock 页面置换算法

为什么须要 clock 算法？

LRU 算法的性能靠近于 OPT, 然而实现起来比拟艰难，且开销大；FIFO 算法实现简略，但性能差。

所以操作系统的设计者尝试了很多算法，试图用比拟小的开销靠近 LRU 的性能，这类算法都是 CLOCK 算法的变体。

因为该算法循环地查看各页面的状况，故称为 CLOCK 算法，又称为最近未用 (Not Recently Used, NRU) 算法。

基本思路

须要用到页表项的拜访位（access bit），当一个页面被装入内存时，把该位初始化为 0，而后如果这个页被拜访（读 / 写）时，硬件把它置为 1.

把各个页面组织成环形链表（相似钟外表），把指针指向最老的页面（最先进来）；

当产生一个缺页中断，考查指针所指向的最老的页面，若它的拜访为为 0，则立刻淘汰。若拜访为 1，则把该地位为 0，而后指针往下挪动一格。如此上来，直到找到被淘汰的页面，而后把指针挪动到它的下一格。

集体纳闷

（1）如果找了一圈发现元素都是 1 怎么办？

是不是间接默认取第一个元素，这样认为就是回到了奢侈的 FIFO 机制。

（2）拜访的性能问题

这里的遍历能够认为是一个循环链表：

每一个节点内容：

K key;
boolean accessFlag;

奢侈的 FIFO 非常简单，间接往队列中扔元素就行，而后淘汰最老的一个元素。

这个如果真的应用链表作为数据结构，那么查找，更新工夫复杂度就是 O(N)，显然性能个别。

能想到的计划就是 HashMap 中存储 key+ 双向链表节点。

和性能改良版本的 LRU 比照，就是每次更新不做节点的移除调整，而只是更新对应的标记位。

简略的 CLOCK 算法

是通过给每一个拜访的页面关联一个附加位(reference bit)，有些中央也叫做应用位(use bit)。

他的次要思维是：当某一页装入主存时，将 use bit 初始化为 0；如果该页之后又被拜访到，应用位也还是标记成 1。

对于页面置换算法，候选的帧汇合能够看成是一个循环缓冲区，并且有一个指针和缓冲区相关联。遇到页面替换时，指针指向缓冲区的下一帧。

如果这页进入主存后发现没有空余的帧(frame)，即所有页面的应用位均为 1，那么这时候从指针开始循环一个缓冲区，将之前的应用位都清 0，并且留在最后的地位上，换出该桢对应的页。

ps: 这里发现没有空余的帧，会将所有应用位都清零。

例子

以上面这个页面置换过程为例，拜访的页面顺次是:1,2,3,4,1,2,5,1,2,3,4,5。

主存有 4 个闲暇的帧，每个页面对应的构造为(页面号，应用位)。

最开始页面号 1 进入主存，主存外面有闲暇的帧，将其应用位记成 1，因为主存中之前没有页面 1，所以会产生缺页中断。

同理随后的页面 2，3，4 进入主存，将其应用位记成 1，产生缺页中断。

当之后的页面 1，2 进入主存时，因为页面 1,2 曾经在主存中，不做解决。

当之后的页面 5 进入主存时，主存内没有空余的帧，这时候随着指针循环挪动整个缓冲区，将之前页面的应用位全副清 0，即这时候页面 1,2,3,4 对应的应用位全副为 0，指针回到最后的地位，将页面 1 替换进来，页面 5 换入主存，同时应用位标记成 1。

以此类推，可知 CLOCK 共产生 10 次缺页中断。

Gclock(Generalized clock page replacement algorithm)

算法思维

该算法是 Clock 的变种。

绝对于 Clock 标记位采纳的是二进制 0 和 1 示意，Gclock 的标记位采纳的是一个整数，意味着实践上能够始终减少到无穷大。

工作原理

（1）当待缓存对象在缓存中时，把其标记位的值加 1。同时，指针指向该对象的下一个对象。

（2）若不在缓存中时，查看指针指向对象的标记位。如果是 0，则用待缓存对象替换该对象；否则，把标记位的值减 1，指针指向下一个对象。如此直到淘汰一个对象为止。因为标记位的值容许大于 1，所以指针可能循环多遍才淘汰一个对象。

ps: 这个有点相似于简化版本的 LFU，统计了对应的呈现次数。

WSclock(Working set clock page replacement algorithm)

算法思维

该算法同样是 clock 的变种，可能是理论使用最宽泛的算法。

它采纳 clock 的原理，是 ws 算法的增强版。

算法数据结构为循环链表，每个缓存对象保留了 ” 最近应用的工夫 ”rt 和 ” 是否援用 ” 的 R 标记位, 应用一个周期计时器 t。age 示意为以后工夫和 rt 的差值

工作原理

（1）当待缓存对象存在缓存中时，更新 rt 为以后工夫。同时，指针指向该对象的下一个对象。

（2）若不存在于缓存中时，如果缓存没满，则更新指针指向地位的 rt 为以后工夫,R 为 1。同时，指针指向下一个对象。如果满了，则须要淘汰一个对象。查看指针指向的对象，

• R 为 1，阐明对象在 working set 中，则重置 R 为 0，指针指向下一个对象。
• R 为 0。如果 age 大于 t，阐明对象不在 working set 中，则替换该对象，并置 R 为 1，rt 为以后工夫。如果 age 不大于 t，则持续寻找淘汰对象。如果回到指针开始的地位，还未寻找到淘汰对象，则淘汰遇到的第一个 R 为 0 的对象。

二次机会法（或者 enhanced clock）

改进型的 CLOCK 算法

思路：缩小批改页的缺页解决开销

批改 Clock 算法，使它容许脏页总是在一次时钟头扫描中保留下来，同时应用脏位（dity bit, 也叫写位）和应用位来领导置换

算法流程

在之前的 CLOCK 算法下面除了应用位(used bit)，还减少了一个批改位(modified bit)，有些中央也叫做 dirty bit。

当初每一页有两个状态，别离是(应用位，批改位)，可分为以下四种状况思考：

(0,0)：最近没有应用应用也没有批改，最佳状态！

(0,1)：批改过但最近没有应用，将会被写

(1,0)：应用过但没有被批改，下一轮将再次被用

(1,1)：应用过也批改过，下一轮页面置换最初的抉择

例子

以上面这个页面置换过程为例：

拜访的页面顺次是:0,1,3,6,2,4,5,2,5,0,3,1,2,5,4,1,0，其中红色数字示意将要批改的页面，即他们的 modified bit 将被设置成 1，在下图中这些页面用斜体示意，应用位和批改位如下图所示。上面的 ”Fault ?” 示意缺页时查找闲暇 frame 的次数。

替换程序

1. 从指针以后的地位开始寻找主存中满足 (应用位，批改位) 为(0,0)的页面；
2. 如果第 1 步没有找到满足条件的，接着寻找状态为 (0,1) 页面；
3. 如果仍然没有找到，指针回到最后的地位，将汇合中所有页面的应用位设置成 0。反复第 1 步，并且如果有必要，反复第 2 步，这样肯定能够找到将要替换的页面。

java 实现 clock 算法

阐明

本文次要实现一个简略版本的 clock 算法，并对惯例的实现加上肯定的性能优化。（全网可能是独家的，或者说第一个这么实现的）

优化次要是基于性能的思考，相似于后面对于 LRU 的性能优化，将查问操作从 O(N) 优化到 O(1)。

实现思路

咱们定义一个合乎以后业务场景的循环链表（这个前期也能够独立进来，有工夫独自写一个数据结构我的项目，便于复用）

定义蕴含 accessFlag 的节点。

咱们应用双向链表，而不是单向链表，这样删除的性能是最好的。

应用 map 保留 key 的信息，防止循环整个链表判断 key 是否存在，用空间换取工夫。

好了，接下来就是高兴的编码阶段了。

代码实现

节点定义

/**
 * 循环链表节点
 * @author binbin.hou
 * @since 0.0.15
 * @param <K> key
 * @param <V> value
 */
public class CircleListNode<K,V> {

    /**
     * 键
     * @since 0.0.15
     */
    private K key;

    /**
     * 值
     * @since 0.0.15
     */
    private V value = null;

    /**
     * 是否被拜访过
     * @since 0.0.15
     */
    private boolean accessFlag = false;

    /**
     * 后一个节点
     * @since 0.0.15
     */
    private CircleListNode<K, V> pre;

    /**
     * 后一个节点
     * @since 0.0.15
     */
    private CircleListNode<K, V> next;

    //getter & setter
}

这里很简略的几个元素：key, value, accessFlag（是否拜访过的标识），而后就是 next, pre 用户实现双向链表。

双向链表实现

根本属性

为了和原来的 Lru 双向链表保持一致，咱们实现原来的额接口。

public class LruMapCircleList<K,V> implements ILruMap<K,V> {private static final Log log = LogFactory.getLog(LruMapCircleList.class);

    /**
     * 头结点
     * @since 0.0.15
     */
    private CircleListNode<K,V> head;

    /**
     * 映射 map
     * @since 0.0.15
     */
    private Map<K, CircleListNode<K,V>> indexMap;

    public LruMapCircleList() {
        // 双向循环链表
        this.head = new CircleListNode<>(null);
        this.head.next(this.head);
        this.head.pre(this.head);

        indexMap = new HashMap<>();}

}

初始化 Head 节点，indexMap 用户保留 key 和双向节点之间的关系。

删除元素

/**
 * 移除元素
 *
 * 1. 是否存在，不存在则疏忽
 * 2. 存在则移除，从链表 +map 中移除
 *
 * head==>1==>2==>head
 *
 * 删除 2 之后：* head==>1==>head
 * @param key 元素
 * @since 0.0.15
 */
@Override
public void removeKey(final K key) {CircleListNode<K,V> node = indexMap.get(key);
    if(ObjectUtil.isNull(node)) {log.warn("对应的删除信息不存在：{}", key);
        return;
    }
    CircleListNode<K,V> pre = node.pre();
    CircleListNode<K,V> next = node.next();
    //1-->(x2)-->3  间接移除 2
    pre.next(next);
    next.pre(pre);
    indexMap.remove(key);
    log.debug("Key: {} 从循环链表中移除", key);
}

节点的删除不难，间接从循环链表中移除节点即可，同时移除 indexMap 中的信息。

更新

此处对于 put/get 用的是同一个办法，实际上如果想实现加强版本的 clock 算法，二者还是辨别开比拟好，不过个人感觉原理差不多，此处就不再实现了，预计这就是淘汰算法的最初一个大节。

/**
 * 放入元素
 *
 * 相似于 FIFO，间接放在队列的最初
 * 
 * head==>1==>head
 * 退出元素：*
 * head==>1==>2==>head
 *
 *（1）如果元素不存在，则直接插入。* 默认 accessFlag = 0;
 *（2）如果曾经存在，则更新 accessFlag=1;
 *
 * @param key 元素
 * @since 0.0.15
 */
@Override
public void updateKey(final K key) {CircleListNode<K,V> node = indexMap.get(key);
    // 存在
    if(ObjectUtil.isNotNull(node)) {node.accessFlag(true);
        log.debug("节点已存在，设置节点拜访标识为 true, key: {}", key);
    } else {
        // 不存在，则插入到最初
        node = new CircleListNode<>(key);
        CircleListNode<K,V> tail = head.pre();
        tail.next(node);
        node.pre(tail);
        node.next(head);
        head.pre(node);
        // 放入 indexMap 中，便于疾速定位
        indexMap.put(key, node);
        log.debug("节点不存在，新增节点到链表中：{}", key);
    }
}

这里次要就是辨别下节点是否曾经存在。

（1）已存在，间接获取节点，更新 accessFlag=true;

（2）不存在：插入新的节点，accessFlag = false

淘汰数据

/**
 * 删除最老的元素
 *
 *（1）从 head.next 开始遍历，如果元素 accessFlag = 0，则间接移除
 *（2）如果 accessFlag=1，则设置其值为 0，循环下一个节点。*
 * @return 后果
 * @since 0.0.15
 */
@Override
public ICacheEntry<K, V> removeEldest() {
    //fast-fail
    if(isEmpty()) {log.error("以后列表为空，无奈进行删除");
        throw new CacheRuntimeException("不可删除头结点!");
    }
    // 从最老的元素开始，此处间接从 head.next 开始，后续能够思考优化记录这个 key
    CircleListNode<K,V> node = this.head;
    while (node.next() != this.head) {
        // 下一个元素
        node = node.next();
        if(!node.accessFlag()) {
            // 未拜访，间接淘汰
            K key = node.key();
            this.removeKey(key);
            return CacheEntry.of(key, node.value());
        } else {
            // 设置以后 accessFlag = 0, 持续下一个
            node.accessFlag(false);
        }
    }
    // 如果循环一遍都没找到，间接取第一个元素即可。CircleListNode<K,V> firstNode = this.head.next();
    return CacheEntry.of(firstNode.key(), firstNode.value());
}

间接遍历节点，遇到 accessFlag=0 的间接淘汰即可。

如果 accessFlag=1，则设置其值为 0，而后持续下一个。（这里有点免死金牌只能用一次的感觉）

循环一遍都没有找到，实际上间接取 head.next 即可，降级为 FIFO。当然因为咱们曾经更新 accessFlag=0 了，实际上持续循环也能够。

• 实现的不足之处

这里有一个待改良点：咱们不见得每次都从开始循环。这样实际上毛病比拟显著，导致越先入队的元素第二次肯定被淘汰，其余未被拜访的元素可能会始终存在，能够用一个元素记住这个地位。（上一次被淘汰的节点的 next 节点），感觉这样才更加合乎 clock 算法的思维。

还有一种办法就是不把拜访过的 accessFlag 置为 0，循环一圈都找不到元素间接降级为 FIFO，不过这个在大部分元素被拜访之后，性能会变差。所以还是倡议标记一下上次循环的地位。

调用

咱们在 cache 满的时候，调用下以后循环链表即可：

import com.github.houbb.cache.api.ICache;
import com.github.houbb.cache.api.ICacheEntry;
import com.github.houbb.cache.api.ICacheEvictContext;
import com.github.houbb.cache.core.model.CacheEntry;
import com.github.houbb.cache.core.support.struct.lru.ILruMap;
import com.github.houbb.cache.core.support.struct.lru.impl.LruMapCircleList;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;

/**
 * 淘汰策略 -clock 算法
 *
 * @author binbin.hou
 * @since 0.0.15
 */
public class CacheEvictClock<K,V> extends AbstractCacheEvict<K,V> {private static final Log log = LogFactory.getLog(CacheEvictClock.class);

    /**
     * 循环链表
     * @since 0.0.15
     */
    private final ILruMap<K,V> circleList;

    public CacheEvictClock() {this.circleList = new LruMapCircleList<>();
    }

    @Override
    protected ICacheEntry<K, V> doEvict(ICacheEvictContext<K, V> context) {
        ICacheEntry<K, V> result = null;
        final ICache<K,V> cache = context.cache();
        // 超过限度，移除队尾的元素
        if(cache.size() >= context.size()) {ICacheEntry<K,V>  evictEntry = circleList.removeEldest();;
            // 执行缓存移除操作
            final K evictKey = evictEntry.key();
            V evictValue = cache.remove(evictKey);

            log.debug("基于 clock 算法淘汰 key：{}, value: {}", evictKey, evictValue);
            result = new CacheEntry<>(evictKey, evictValue);
        }

        return result;
    }


    /**
     * 更新信息
     * @param key 元素
     * @since 0.0.15
     */
    @Override
    public void updateKey(final K key) {this.circleList.updateKey(key);
    }

    /**
     * 移除元素
     *
     * @param key 元素
     * @since 0.0.15
     */
    @Override
    public void removeKey(final K key) {this.circleList.removeKey(key);
    }

}

其实调用的中央没什么难度，就是间接调用下办法即可。

测试

好的，代码写完咱们来简略的验证一下。

测试代码

ICache<String, String> cache = CacheBs.<String,String>newInstance()
        .size(3)
        .evict(CacheEvicts.<String, String>clock())
        .build();
cache.put("A", "hello");
cache.put("B", "world");
cache.put("C", "FIFO");
// 拜访一次 A
cache.get("A");
cache.put("D", "LRU");
Assert.assertEquals(3, cache.size());
System.out.println(cache.keySet());

日志

[DEBUG] [2020-10-07 11:32:55.396] [main] [c.g.h.c.c.s.s.l.i.LruMapCircleList.updateKey] - 节点不存在，新增节点到链表中：A
[DEBUG] [2020-10-07 11:32:55.398] [main] [c.g.h.c.c.s.s.l.i.LruMapCircleList.updateKey] - 节点不存在，新增节点到链表中：B
[DEBUG] [2020-10-07 11:32:55.401] [main] [c.g.h.c.c.s.s.l.i.LruMapCircleList.updateKey] - 节点不存在，新增节点到链表中：C
[DEBUG] [2020-10-07 11:32:55.403] [main] [c.g.h.c.c.s.s.l.i.LruMapCircleList.updateKey] - 节点已存在，设置节点拜访标识为 true, key: A
[DEBUG] [2020-10-07 11:32:55.404] [main] [c.g.h.c.c.s.s.l.i.LruMapCircleList.removeKey] - Key: B 从循环链表中移除
[DEBUG] [2020-10-07 11:32:55.406] [main] [c.g.h.c.c.s.e.CacheEvictClock.doEvict] - 基于 clock 算法淘汰 key：B, value: world
[DEBUG] [2020-10-07 11:32:55.410] [main] [c.g.h.c.c.s.l.r.CacheRemoveListener.listen] - Remove key: B, value: world, type: evict
[DEBUG] [2020-10-07 11:32:55.411] [main] [c.g.h.c.c.s.s.l.i.LruMapCircleList.updateKey] - 节点不存在，新增节点到链表中：D
[D, A, C]

合乎咱们的预期。

LRU、FIFO 与 Clock 的比拟

LRU 和 FIFO 实质都是先进先出的思路，但 LRU 是针对页面的最近拜访工夫来进行排序，所以须要在每一次页面拜访的时候动静的调整各个页面之间的先后顺序（每一个页面的最近拜访工夫变了）；而 FIFO 针对页面进入内存的工夫来进行排序，这个工夫是固定不变的，所以页面之间的先后顺序是固定不变的。

如果程序局部性，则 LRU 会很好。如果内存中所有页面都没有被拜访过会进化为 FIFO（如页面进入内存后没有被拜访，最近拜访工夫与进入内存的工夫雷同）。

LRU 算法性能较好，但零碎开销较大；FIFO 算法的零碎的开销较小，但可能产生 Belady 景象。

因而，择衷的方法就是 Clock 算法，在每一次页面拜访时，它不用去动静调整页面在链表中的程序，而仅仅是做一个标记，期待产生缺页中断的时候，再把它挪动到链表的开端。

对于内存当中未被拜访的页面，Clock 算法的体现与 LRU 一样好，而对于那些已经拜访过的页面，它不能像 LRU 那样记住它们的精确拜访程序。

置换算法补充

常见的置换算法，咱们根本曾经讲述了一遍了。

不过算法的变种，不同场景的算法也比拟多，这里补充没有详解的算法，此处就不做对应的实现了。

目标为了欠缺整个淘汰算法的认知体系。

最佳置换算法(OPT)

最佳 (Optimal, OPT) 置换算法所抉择的被淘汰页面将是当前永不应用的，或者是在最长工夫内不再被拜访的页面, 这样能够保障取得最低的缺页率。

但因为人们目前无奈预知过程在内存下的若千页面中哪个是将来最长工夫内不再被拜访的，因此该算法无奈实现。

最佳置换算法能够用来评估其余算法。假设零碎为某过程调配了三个物理块，并思考有以下页面号援用串：

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

过程运行时，先将 7, 0, 1 三个页面顺次装入内存。

过程要拜访页面 2 时，产生缺页中断，依据最佳置换算法，抉择第 18 次访问才需调入的页面 7 予以淘汰。

而后，拜访页面 0 时，因为已在内存中所以不用产生缺页中断。拜访页面 3 时又会依据最佳置换算法将页面 1 淘汰……依此类推，如图 3 -26 所示。

从图中能够看出釆用最佳置换算法时的状况。

能够看到，产生缺页中断的次数为 9，页面置换的次数为 6。

当然这个是实践算法，理论是无奈实现的，因为咱们无奈预知前面的数据会被如何应用。

页面缓冲算法(PBA：Page Buffering Algorithm)

尽管 LRU 和 Clock 置换算法都比 FIFO 算法好，但它们都须要肯定的硬件反对，并需付出较多的开销，而且，置换一个已批改的页比置换未修改页的开销要大。

而页面缓冲算法 (PBA) 则既可改善分页零碎的性能，又可采纳一种较简略的置换策略。

VAX/VMS 操作系统便是应用页面缓冲算法。它采纳了前述的可变调配和部分置换形式，置换算法采纳的是 FIFO。

该算法规定将一个被淘汰的页放入两个链表中的一个，即如果页面未被批改，就将它间接放入闲暇链表中；否则，便放入已批改页面的链表中。须留神的是，这时页面在内存中并不做物理上的挪动，而只是将页表中的表项移到上述两个链表之一中。

闲暇页面链表，实际上是一个闲暇物理块链表，其中的每个物理块都是闲暇的，因而，可在其中装入程序或数据。当须要读入一个页面时，便可利用闲暇物理块链表中的第一个物理块来装入该页。当有一个未被批改的页要换出时，实际上并不将它换出内存，而是把该未被批改的页所在的物理块挂在自在页链表的开端。

相似地，在置换一个已批改的页面时，也将其所在的物理块挂在批改页面链表的开端。利用这种形式可使已被批改的页面和未被批改的页面都依然保留在内存中。当该过程当前再次拜访这些页面时，只需破费较小的开销，使这些页面又返回到该过程的驻留集中。当被批改的页面数目达到肯定值时，例如 64 个页面，再将它们一起写回到磁盘上，从而显著地缩小了磁盘 I / O 的操作次数。

一个较简略的页面缓冲算法已在 MACH 操作系统中实现了，只是它没有辨别已批改页面和未修改页面。

置换算法比照

小结

clock 算法算是一种衡量，在理论的实际利用中，操作系统抉择的就是这种算法。

集体了解 clock 的益处就是 不必频繁地每次拜访都去更新元素的地位，只须要淘汰的时候进行一次更新即可，咱们在 LRU 中尽管应用双向链表优化，工夫复杂度为 O(1)，然而还是比拟节约的。

缓存的淘汰算法到这里根本是告一段落了，感激你的反对，愿你有所播种。

开源地址：https://github.com/houbb/cache

感觉本文对你有帮忙的话，欢送点赞评论珍藏关注一波。你的激励，是我最大的能源~

不晓得你有哪些播种呢？或者有其余更多的想法，欢送留言区和我一起探讨，期待与你的思考相遇。