Redis 的键为什么消失：过期、淘汰与 TTL

import java.util.*;
public class Main {
    record Value(String text,Long deadline,long generation) {}
    record Event(String key,long deadline,long generation) {}
    static class Store {
        final Map<String,Value> values=new HashMap<>();
        final PriorityQueue<Event> events=new PriorityQueue<>(Comparator.comparingLong(Event::deadline));
        long generation,last=-1;
        void advance(long now) {
            if (now<0||now<last) throw new IllegalArgumentException("clock");
            last=now;
            while (!events.isEmpty()&&events.peek().deadline()<=now) {
                Event event=events.remove();
                Value current=values.get(event.key());
                // 旧定时事件不能影响覆盖后产生的新代际。
                if (current!=null&&current.generation()==event.generation())
                    values.remove(event.key());
            }
        }
        void set(String key,String text,Long ttl,boolean keep,long now) {
            if (ttl!=null&&(ttl<=0||keep)) throw new IllegalArgumentException("options");
            advance(now);
            Value old=values.get(key);
            Long deadline;
            if (keep) deadline=old==null?null:old.deadline();
            else deadline=ttl==null?null:Math.addExact(now,ttl);
            generation=Math.addExact(generation,1);
            // 普通覆盖没有TTL时，新代际明确不关联期限。
            Value value=new Value(text,deadline,generation);
            values.put(key,value);
            if (deadline!=null) events.add(new Event(key,deadline,generation));
        }
        long ttl(String key,long now) {
            advance(now);
            Value value=values.get(key);
            // 缺失与持久键使用不同特殊值。
            return value==null?-2:value.deadline()==null?-1:value.deadline()-now;
        }
    }
    static void eq(long expected,long actual) {
        if (expected!=actual) throw new AssertionError(actual);
    }
    public static void main(String[] args) {
        Store s=new Store();
        s.set("k","a",5L,false,0); eq(5,s.ttl("k",0));
        s.set("k","b",null,false,2); eq(-1,s.ttl("k",6));
        s.set("j","a",5L,false,6);
        s.set("j","b",null,true,8); eq(3,s.ttl("j",8)); eq(-2,s.ttl("j",11));
        s.set("r","a",10L,false,11);
        s.set("r","b",5L,false,12); eq(-2,s.ttl("r",17));
        s.set("x","a",1L,false,17);
        s.set("x","b",null,true,20); eq(-1,s.ttl("x",20));
        try { s.set("bad","a",0L,false,20); throw new AssertionError("ttl"); }
        catch (IllegalArgumentException expected) {}
        eq(-2,s.ttl("bad",20));
        System.out.println("PASS 8 expiration generation tests");
    }
}