关于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 */@Overridepublic 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 */@Overridepublic 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 */@Overridepublic 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");// 拜访一次Acache.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

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

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