Key-value store with TTL
A mini Redis in forty minutes.

KeyValueStore<K,V>
  put(K, V)
  put(K, V, Duration)
  get(K): Optional<V>
  delete(K)
  close()

Entry<V>
  V value
  long expiresAt
  isExpired(now): bool

EvictionPolicy<K> (interface)
  onAccess(K)
  onPut(K)
  onRemove(K)
  victim(): K

LruEvictionPolicy<K>

ExpirySweeper
  DelayQueue<ExpiryTask> queue
  schedule(K, long expiresAt)
  run()

How they connect:
  KeyValueStore uses Entry
  KeyValueStore uses EvictionPolicy
  KeyValueStore uses ExpirySweeper
  LruEvictionPolicy implements EvictionPolicy

final class Entry<V> {
    final V value; final long expiresAt;
    Entry(V value, long expiresAt) { this.value = value; this.expiresAt = expiresAt; }
    boolean isExpired(long now) { return now >= expiresAt; }
}

class KeyValueStore<K, V> implements AutoCloseable {
    private final ConcurrentHashMap<K, Entry<V>> map = new ConcurrentHashMap<>();
    private final Clock clock;
    private final int maxSize;
    private final LinkedHashMap<K, Boolean> lru = new LinkedHashMap<>(16, 0.75f, true); // access order, guarded by `this`
    private final DelayQueue<ExpiryTask<K>> expiryQueue = new DelayQueue<>();
    private final Thread sweeper;

    KeyValueStore(int maxSize, Clock clock) {
        this.maxSize = maxSize; this.clock = clock;
        this.sweeper = Thread.ofVirtual().start(this::sweepLoop);
    }

    public void put(K key, V value) { put(key, value, null); }

    public void put(K key, V value, Duration ttl) {
        long expiresAt = ttl == null ? Long.MAX_VALUE : clock.millis() + ttl.toMillis();
        map.put(key, new Entry<>(value, expiresAt));
        if (ttl != null) expiryQueue.offer(new ExpiryTask<>(key, expiresAt, clock));
        synchronized (this) {
            lru.put(key, Boolean.TRUE);
            while (lru.size() > maxSize) {                       // evict the least recently used
                K victim = lru.keySet().iterator().next();
                lru.remove(victim);
                map.remove(victim);
            }
        }
    }

    public Optional<V> get(K key) {
        Entry<V> e = map.get(key);
        if (e == null) return Optional.empty();
        if (e.isExpired(clock.millis())) {                       // lazy expiry
            map.remove(key, e);                                  // remove only if it's still this exact entry
            synchronized (this) { lru.remove(key); }
            return Optional.empty();
        }
        synchronized (this) { lru.get(key); }                    // touch for LRU
        return Optional.of(e.value);
    }

    public boolean delete(K key) {
        synchronized (this) { lru.remove(key); }
        return map.remove(key) != null;
    }

    private void sweepLoop() {                                   // active expiry
        try {
            while (!Thread.currentThread().isInterrupted()) {
                ExpiryTask<K> t = expiryQueue.take();            // blocks until the earliest expiry is due
                Entry<V> e = map.get(t.key);
                if (e != null && e.expiresAt == t.expiresAt) {   // ignore if the key was overwritten with a new TTL
                    map.remove(t.key, e);
                    synchronized (this) { lru.remove(t.key); }
                }
            }
        } catch (InterruptedException ignored) { Thread.currentThread().interrupt(); }
    }

    @Override public void close() { sweeper.interrupt(); }

    static final class ExpiryTask<K> implements Delayed {
        final K key; final long expiresAt; private final Clock clock;
        ExpiryTask(K key, long expiresAt, Clock clock) { this.key = key; this.expiresAt = expiresAt; this.clock = clock; }
        public long getDelay(TimeUnit unit) { return unit.convert(expiresAt - clock.millis(), TimeUnit.MILLISECONDS); }
        public int compareTo(Delayed o) { return Long.compare(expiresAt, ((ExpiryTask<?>) o).expiresAt); }
    }
}