Реализация класса с истекающими ключами

40. Реализовать хранилище с истекающими ключами

Условие задачи:
Необходимо реализовать класс, который хранит пары ключ → значение с ограниченным временем жизни (TTL).

Методы:

set(String key, String value, int duration) — сохраняет значение на duration миллисекунд;
если на момент вызова set() такой же неистёкший ключ уже существует, вернуть true, иначе false;
повторный set() должен заменить значение и заново запустить TTL;
get(String key) — вернуть значение, если ключ ещё действует, иначе "-1";
count() — вернуть количество неистёкших ключей.

Истёкшие записи могут удаляться лениво — при обращении к хранилищу.

Спойлеры к решению

Подсказки

💡 Вместе со значением храни момент его истечения.
💡 Для измерения временного интервала лучше использовать System.nanoTime(), а не системные часы.
💡 Если класс используется конкурентно, операция проверки существующего ключа и его замены должна быть атомарной.
💡 Для этого удобно использовать ConcurrentHashMap.compute().
💡 При удалении просроченной записи важно не удалить новое значение, которое другой поток уже успел записать по тому же ключу.

Решение

public class ExpiringMap {

    private static class Entry {
        private final String value;
        private final long expiresAt;

        private Entry(String value, long expiresAt) {
            this.value = value;
            this.expiresAt = expiresAt;
        }

        private boolean isExpired(long now) {
            return now - expiresAt >= 0;
        }
    }

    private final ConcurrentHashMap<String, Entry> storage =
            new ConcurrentHashMap<>();

    public boolean set(String key, String value, int duration) {
        Objects.requireNonNull(key, "key");
        Objects.requireNonNull(value, "value");

        if (duration < 0) {
            throw new IllegalArgumentException(
                    "duration не может быть отрицательным"
            );
        }

        AtomicBoolean existed = new AtomicBoolean(false);

        storage.compute(key, (k, oldEntry) -> {
            long now = System.nanoTime();

            existed.set(
                    oldEntry != null
                            && !oldEntry.isExpired(now)
            );

            long expiresAt =
                    now + TimeUnit.MILLISECONDS.toNanos(duration);

            return new Entry(value, expiresAt);
        });

        return existed.get();
    }

    public String get(String key) {
        Objects.requireNonNull(key, "key");

        Entry entry = storage.get(key);

        if (entry == null) {
            return "-1";
        }

        if (entry.isExpired(System.nanoTime())) {
            storage.remove(key, entry);
            return "-1";
        }

        return entry.value;
    }

    public int count() {
        long now = System.nanoTime();
        int count = 0;

        for (Map.Entry<String, Entry> mapEntry
                : storage.entrySet()) {

            Entry entry = mapEntry.getValue();

            if (entry.isExpired(now)) {
                storage.remove(mapEntry.getKey(), entry);
            } else {
                count++;
            }
        }

        return count;
    }
}

Каждая запись хранит не только значение, но и момент окончания её действия:

private final String value;
private final long expiresAt;

Для TTL используется:

System.nanoTime()

Он подходит для измерения интервалов времени и не зависит от перевода системных часов вперёд или назад.

В set() используется:

storage.compute(key, ...)

Операция выполняется атомарно для конкретного ключа. Поэтому два потока не смогут одновременно проверить старое значение и независимо перезаписать его, получив некорректный результат true/false.

Например:

map.set("name", "Ivan", 1000); // false
map.set("name", "Petr", 1000); // true

Второй вызов возвращает true, поскольку на момент обновления ключ ещё существует, но его значение и TTL всё равно заменяются.

При истечении срока в get() используется:

storage.remove(key, entry);

а не просто:

storage.remove(key);

Это важно при конкурентном доступе. Если другой поток уже заменил просроченную запись новой, условное удаление не затронет новое значение.

Пример:

ExpiringMap map = new ExpiringMap();

System.out.println(
        map.set("a", "hello", 1000)
); // false

System.out.println(
        map.get("a")
); // hello

System.out.println(
        map.count()
); // 1

После окончания TTL:

get("a") → "-1"
count()  → 0

set() и get() в среднем работают за O(1).

count() требует просмотра хранилища, поэтому работает за O(n), где n — количество записей.

При конкурентных изменениях ConcurrentHashMap даёт слабосогласованный обход, поэтому count() не является атомарным снимком всей карты. Если требуется строго точное значение относительно одновременно выполняющихся set() и get(), операции придётся дополнительно координировать общей блокировкой.

Также контракт с "-1" неоднозначен, если "-1" является допустимым значением. В реальном API для отсутствующего ключа удобнее возвращать Optional<String>.