Design a caching library.

package com.androidinterview.cachinglib;

import java.time.Duration;

// One generic surface, so a network response cache, a computed value cache and
// a small object cache are the same library rather than three of them. A null
// ttl means the entry lives until it is evicted for size.
//
// Notice what is missing. There is no load or fetch method. This library
// stores, it never goes and gets anything, and keeping that line clean is what
// stops it from growing into a repository.
public interface Cache<K, V> {

    V get(K key);

    void put(K key, V value, Duration ttl);

    void remove(K key);

    void clear();
}

package com.androidinterview.cachinglib;

import java.time.Clock;
import java.time.Duration;
import java.time.Instant;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

// Memory in front of an optional disk tier, plus the one thing a plain key
// value store cannot do, dropping a whole group of entries at once.
public final class LayeredCache<K, V> implements Cache<K, V> {

    // The disk tier is a port, not a class. This library never picks a file
    // format, and an app on Android hands it a DiskLruCache. An in session
    // cache of computed values passes null and stays memory only.
    //
    // The expiry crosses the disk hop with the value, in both directions. A
    // tier that only stored the value would resurrect an expired entry on the
    // next read and promote it into memory with no expiry at all.
    public interface DiskTier<K, V> {
        record Stored<V>(V value, Instant expiresAt) {
        }

        Stored<V> read(K key);

        void write(K key, V value, Instant expiresAt);

        void delete(K key);

        void clear();
    }

    private final MemoryCache<K, V> memory;
    private final DiskTier<K, V> disk;
    private final Clock clock;
    // Tag to the keys filed under it, so a logout drops every entry belonging
    // to that user without the caller having tracked what it stored. Both the
    // map and each set are concurrent, because a logout calling clear runs
    // against a background put that is still filing keys under a tag.
    private final Map<String, Set<K>> tagged = new ConcurrentHashMap<>();

    public LayeredCache(MemoryCache<K, V> memory, DiskTier<K, V> disk) {
        this(memory, disk, Clock.systemUTC());
    }

    public LayeredCache(MemoryCache<K, V> memory, DiskTier<K, V> disk, Clock clock) {
        this.memory = memory;
        this.disk = disk;
        this.clock = clock;
    }

    @Override
    public V get(K key) {
        V hot = memory.get(key);
        if (hot != null || disk == null) {
            return hot;
        }
        DiskTier.Stored<V> cold = disk.read(key);
        if (cold == null) {
            return null;
        }
        Instant now = Instant.now(clock);
        if (cold.expiresAt() != null && now.isAfter(cold.expiresAt())) {
            // Expired while it sat on disk. Delete rather than promote, or the
            // entry would come back from the dead with every process start.
            disk.delete(key);
            return null;
        }
        // Promote, so a value read off disk once is never read off disk twice,
        // and promote with whatever life the entry has left.
        Duration remaining = cold.expiresAt() == null ? null : Duration.between(now, cold.expiresAt());
        memory.put(key, cold.value(), remaining);
        return cold.value();
    }

    @Override
    public void put(K key, V value, Duration ttl) {
        memory.put(key, value, ttl);
        if (disk != null) {
            disk.write(key, value, ttl == null ? null : Instant.now(clock).plus(ttl));
        }
    }

    public void put(K key, V value, Duration ttl, String tag) {
        put(key, value, ttl);
        tagged.computeIfAbsent(tag, unused -> ConcurrentHashMap.newKeySet()).add(key);
    }

    public void clearTag(String tag) {
        Set<K> keys = tagged.remove(tag);
        if (keys != null) {
            keys.forEach(this::remove);
        }
    }

    @Override
    public void remove(K key) {
        memory.remove(key);
        if (disk != null) {
            disk.delete(key);
        }
    }

    @Override
    public void clear() {
        memory.clear();
        if (disk != null) {
            disk.clear();
        }
        tagged.clear();
    }
}

package com.androidinterview.cachinglib;

import java.time.Clock;
import java.time.Duration;
import java.time.Instant;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.ToIntFunction;

// The memory tier, and two decisions live in it.
//
// The budget is bytes rather than entries, because only a caller supplied
// sizeOf knows what a value actually costs. Counting slots treats a ten byte
// string and a ten megabyte bitmap as equals.
//
// Expiry is lazy. An entry that timed out is dropped when something reads it,
// so the library never owns a background thread whose whole job is deleting
// entries nobody has asked for.
public final class MemoryCache<K, V> implements Cache<K, V> {

    private record Entry<V>(V value, int bytes, Instant expiresAt) {
        boolean isExpired(Instant now) {
            return expiresAt != null && now.isAfter(expiresAt);
        }
    }

    private final long maxBytes;
    private final ToIntFunction<V> sizeOf;
    // The clock is injected so a test can expire an entry without sleeping.
    private final Clock clock;
    // The same access order LinkedHashMap as the LRU cache answer, with two
    // things added for this library. The entry records its byte size at
    // insert, so the counter cannot drift if sizeOf is not stable, and it
    // carries the expiry that get checks lazily.
    private final LinkedHashMap<K, Entry<V>> entries = new LinkedHashMap<>(16, 0.75f, true);
    private long bytes;

    public MemoryCache(long maxBytes, ToIntFunction<V> sizeOf) {
        this(maxBytes, sizeOf, Clock.systemUTC());
    }

    public MemoryCache(long maxBytes, ToIntFunction<V> sizeOf, Clock clock) {
        this.maxBytes = maxBytes;
        this.sizeOf = sizeOf;
        this.clock = clock;
    }

    @Override
    public synchronized V get(K key) {
        Entry<V> entry = entries.get(key);
        if (entry == null) {
            return null;
        }
        if (entry.isExpired(Instant.now(clock))) {
            remove(key);
            return null;
        }
        return entry.value();
    }

    // A value larger than the whole budget is inserted and evicted by the same
    // call, so put stores nothing and says nothing. Rejecting it up front is a
    // fair alternative. This version keeps put total.
    @Override
    public synchronized void put(K key, V value, Duration ttl) {
        int size = sizeOf.applyAsInt(value);
        Instant expiresAt = ttl == null ? null : Instant.now(clock).plus(ttl);
        Entry<V> previous = entries.put(key, new Entry<>(value, size, expiresAt));
        if (previous != null) {
            bytes -= previous.bytes();
        }
        bytes += size;
        trimTo(maxBytes);
    }

    @Override
    public synchronized void remove(K key) {
        Entry<V> removed = entries.remove(key);
        if (removed != null) {
            bytes -= removed.bytes();
        }
    }

    @Override
    public synchronized void clear() {
        entries.clear();
        bytes = 0;
    }

    // onTrimMemory hands this a smaller budget than the configured one, which
    // is the only reason the budget is a parameter and not the field.
    public synchronized void trimTo(long budget) {
        Iterator<Map.Entry<K, Entry<V>>> oldestFirst = entries.entrySet().iterator();
        while (bytes > budget && oldestFirst.hasNext()) {
            bytes -= oldestFirst.next().getValue().bytes();
            oldestFirst.remove();
        }
    }
}

package com.androidinterview.cachinglib

import kotlin.time.Duration

// One generic surface, so a network response cache, a computed value cache and
// a small object cache are the same library rather than three of them.
//
// Notice what is missing. There is no load or fetch method. This library
// stores, it never goes and gets anything, and keeping that line clean is what
// stops it from growing into a repository.
interface Cache<K : Any, V : Any> {

    operator fun get(key: K): V?

    fun put(key: K, value: V, ttl: Duration? = null)

    fun remove(key: K)

    fun clear()
}

package com.androidinterview.cachinglib

import java.util.concurrent.ConcurrentHashMap
import kotlin.time.Duration
import kotlin.time.Duration.Companion.milliseconds

// The disk tier is a port, not a class. This library never picks a file
// format, and an app on Android hands it a DiskLruCache. An in session cache
// of computed values passes nothing and stays memory only.
//
// The expiry crosses the disk hop with the value, in both directions. A tier
// that only stored the value would resurrect an expired entry on the next read
// and promote it into memory with no expiry at all.
interface DiskTier<K : Any, V : Any> {
    data class Stored<V>(val value: V, val expiresAtMillis: Long?)

    fun read(key: K): Stored<V>?
    fun write(key: K, value: V, expiresAtMillis: Long?)
    fun delete(key: K)
    fun clear()
}

// Memory in front of an optional disk tier, plus the one thing a plain key
// value store cannot do, dropping a whole group of entries at once. The tag
// index is a second map from a tag to the keys filed under it, so a logout
// clears every entry belonging to that user without the caller having tracked
// what it stored. Both the map and each set are concurrent, because a logout
// calling clear runs against a background put still filing keys under a tag.
class LayeredCache<K : Any, V : Any>(
    private val memory: MemoryCache<K, V>,
    private val disk: DiskTier<K, V>? = null,
    private val now: () -> Long = System::currentTimeMillis,
) : Cache<K, V> {

    private val tagged = ConcurrentHashMap<String, MutableSet<K>>()

    override fun get(key: K): V? {
        memory[key]?.let { return it }
        val cold = disk?.read(key) ?: return null
        val expiresAt = cold.expiresAtMillis
        if (expiresAt != null && now() > expiresAt) {
            // Expired while it sat on disk. Delete rather than promote, or the
            // entry would come back from the dead with every process start.
            disk.delete(key)
            return null
        }
        // Promote, so a value read off disk once is never read off disk twice,
        // and promote with whatever life the entry has left.
        memory.put(key, cold.value, expiresAt?.let { (it - now()).milliseconds })
        return cold.value
    }

    override fun put(key: K, value: V, ttl: Duration?) {
        memory.put(key, value, ttl)
        disk?.write(key, value, ttl?.let { now() + it.inWholeMilliseconds })
    }

    fun put(key: K, value: V, ttl: Duration?, tag: String) {
        put(key, value, ttl)
        tagged.getOrPut(tag) { ConcurrentHashMap.newKeySet() } += key
    }

    fun clearTag(tag: String) {
        tagged.remove(tag)?.forEach(::remove)
    }

    override fun remove(key: K) {
        memory.remove(key)
        disk?.delete(key)
    }

    override fun clear() {
        memory.clear()
        disk?.clear()
        tagged.clear()
    }
}

package com.androidinterview.cachinglib

import kotlin.time.Duration

// The memory tier, and two decisions live in it.
//
// The budget is bytes rather than entries, because only a caller supplied
// sizeOf knows what a value costs. Counting slots treats a ten byte string and
// a ten megabyte bitmap as equals.
//
// Expiry is lazy. An entry that timed out is dropped when something reads it,
// so the library never owns a thread whose whole job is deleting entries
// nobody has asked for. The clock is injected so a test can expire an entry
// without sleeping.
class MemoryCache<K : Any, V : Any>(
    private val maxBytes: Long,
    private val now: () -> Long = System::currentTimeMillis,
    private val sizeOf: (V) -> Int,
) : Cache<K, V> {

    private class Entry<V>(val value: V, val bytes: Int, val expiresAt: Long?)

    // The same access order LinkedHashMap as the LRU cache answer, with two
    // things added for this library. The entry records its byte size at
    // insert, so the counter cannot drift if sizeOf is not stable, and it
    // carries the expiry that get checks lazily.
    private val entries = LinkedHashMap<K, Entry<V>>(16, 0.75f, true)
    private var bytes = 0L

    @Synchronized
    override fun get(key: K): V? {
        val entry = entries[key] ?: return null
        val expiresAt = entry.expiresAt
        if (expiresAt != null && now() > expiresAt) {
            remove(key)
            return null
        }
        return entry.value
    }

    // A value larger than the whole budget is inserted and evicted by the same
    // call, so put stores nothing and says nothing. Rejecting it up front is a
    // fair alternative. This version keeps put total.
    @Synchronized
    override fun put(key: K, value: V, ttl: Duration?) {
        val size = sizeOf(value)
        val expiresAt = ttl?.let { now() + it.inWholeMilliseconds }
        entries.put(key, Entry(value, size, expiresAt))?.let { bytes -= it.bytes }
        bytes += size
        trimTo(maxBytes)
    }

    @Synchronized
    override fun remove(key: K) {
        entries.remove(key)?.let { bytes -= it.bytes }
    }

    @Synchronized
    override fun clear() {
        entries.clear()
        bytes = 0
    }

    // onTrimMemory hands this a smaller budget than the configured one, which
    // is the only reason the budget is a parameter and not the field.
    @Synchronized
    fun trimTo(budget: Long) {
        val oldestFirst = entries.entries.iterator()
        while (bytes > budget && oldestFirst.hasNext()) {
            bytes -= oldestFirst.next().value.bytes
            oldestFirst.remove()
        }
    }
}