Как проверить вытеснение и ёмкость LRU-кеша iOS

После нескольких переходов между страницами списка только что просмотренные данные уже вытесняются из кеша, хотя его заданная ёмкость ещё не достигнута. Не спешите добавлять память. Чаще причина в том, что чтение не обновляет порядок обращений, а запись по существующему ключу оставляет дубликаты. На облачном Mac можно вынести логику кеша в отдельный пакет Swift и воспроизвести проблему несколькими детерминированными последовательностями операций — без интерфейса, сети и симулятора.

Сначала определите пять правил работы кеша

Здесь мы проверяем LRU-кеш с ограничением по числу записей: первым вытесняется элемент, к которому дольше всего не обращались. Срок действия записей и сохранение на диск не рассматриваются. Для начала зафиксируем пять правил:

• При успешном чтении ключ становится последним использованным.
• Чтение отсутствующего ключа не меняет существующий порядок.
• Запись по существующему ключу обновляет значение и делает ключ последним использованным, но не увеличивает число записей.
• Если запись нового ключа приводит к превышению ёмкости, вытесняется ключ, к которому дольше всего не обращались.
• При нулевой ёмкости данные не сохраняются; отрицательная ёмкость считается ошибкой вызова.

Эти правила должна согласовать команда, а не выводить их из деталей реализации. Например, если по требованиям приложения чтение не должно продлевать пребывание записи в кеше, это уже другая политика доступа. Использовать для неё те же ожидаемые результаты без изменений нельзя.

Доля попаданий — эксплуатационная метрика, а порядок вытеснения — функциональный контракт. Даже при нормальной доле попаданий в кеше могут оставаться дубликаты ключей и вытесняться не те записи.

Реализуйте наблюдаемую модель в отдельном каталоге

После установки полного набора инструментов на узле выполните следующие команды в отдельном рабочем каталоге. Права администратора и запуск графического интерфейса не нужны.

mkdir LRUContract
cd LRUContract
swift package init --type library

Замените содержимое Sources/LRUContract/LRUContract.swift следующей реализацией. Массив хранит ключи от давно не использовавшихся к недавно использованным, чтобы упростить проверки. Это не высокопроизводительная реализация для кешей большого объёма.

public final class LRU<Key: Hashable, Value> {
    private let capacity: Int
    private var values: [Key: Value] = [:]
    public private(set) var oldestFirst: [Key] = []

    public init(capacity: Int) {
        precondition(capacity >= 0)
        self.capacity = capacity
    }

    public var count: Int { values.count }

    public func get(_ key: Key) -> Value? {
        guard let value = values[key] else { return nil }
        touch(key)
        return value
    }

    public func put(_ key: Key, _ value: Value) {
        guard capacity > 0 else { return }
        values.updateValue(value, forKey: key)
        touch(key)
        if values.count > capacity {
            let victim = oldestFirst.removeFirst()
            values.removeValue(forKey: victim)
        }
    }

    private func touch(_ key: Key) {
        oldestFirst.removeAll { $0 == key }
        oldestFirst.append(key)
    }
}

Метод touch сначала удаляет ключ с прежней позиции, а затем добавляет его в конец. Поэтому один ключ не может занимать два места в порядке обращений. Для записи используется updateValue: это также позволяет не примешивать к логике обновления семантику удаления, свойственную присваиванию через сабскрипт словаря. Если в рабочей реализации перейти на словарь с двусвязным списком, тесты из этой статьи можно сохранить. Но утверждать, что показанный вариант с массивом имеет константную временную сложность, нельзя.

Разделите ошибки чтения и обновления короткими последовательностями

Удалите автоматически созданный пример теста из каталога тестов и сохраните следующий код в Tests/LRUContractTests/LRUContractTests.swift. Мы явно используем XCTest и не зависим от того, какой тестовый фреймворк выбрал шаблон при инициализации пакета.

import XCTest
@testable import LRUContract

final class LRUContractTests: XCTestCase {
    func testReadPromotesAndMissDoesNot() {
        let cache = LRU<String, Int>(capacity: 2)
        cache.put("a", 1)
        cache.put("b", 2)
        XCTAssertNil(cache.get("missing"))
        XCTAssertEqual(cache.oldestFirst, ["a", "b"])
        XCTAssertEqual(cache.get("a"), 1)
        XCTAssertEqual(cache.oldestFirst, ["b", "a"])
        cache.put("c", 3)
        XCTAssertNil(cache.get("b"))
        XCTAssertEqual(cache.oldestFirst, ["a", "c"])
        XCTAssertEqual(cache.count, 2)
    }

    func testUpdateDoesNotConsumeAnotherSlot() {
        let cache = LRU<String, Int>(capacity: 2)
        cache.put("a", 1)
        cache.put("b", 2)
        cache.put("a", 9)
        XCTAssertEqual(cache.count, 2)
        XCTAssertEqual(cache.oldestFirst, ["b", "a"])
        cache.put("c", 3)
        XCTAssertNil(cache.get("b"))
        XCTAssertEqual(cache.get("a"), 9)
    }

    func testZeroCapacityStoresNothing() {
        let cache = LRU<String, Int>(capacity: 0)
        cache.put("a", 1)
        XCTAssertEqual(cache.count, 0)
        XCTAssertTrue(cache.oldestFirst.isEmpty)
        XCTAssertNil(cache.get("a"))
    }
}

Запустите swift test. Сбой первого теста обычно указывает на неправильное обновление порядка при чтении или побочные эффекты при промахе. Если не проходит второй тест, сначала проверьте обновление существующего ключа. Третий не даёт незаметно сохранять одну запись при нулевой ёмкости. Не ограничивайтесь проверкой итогового количества: оно может быть верным, даже если в кеше остались совсем не те ключи.

Сама проверка тоже может изменить порядок

get — не интерфейс наблюдения без изменения состояния. Если вызвать его ради проверки значения, изменится выбор следующей записи для вытеснения. Поэтому в примере сначала проверяется порядок, а затем читается значение. Не перебирайте в тесте все ключи с вызовом get просто для проверки: так тест сам изменит проверяемое состояние.

Перейдите от трёх тестов к проверке последовательностей

При подключении реального кеша добавьте четыре вида последовательностей: ёмкость один, многократная перезапись одного ключа, несколько промахов подряд и повторная вставка после вытеснения. После каждого шага проверяйте, что число записей не превышает ёмкость, в порядке обращений нет повторяющихся ключей, а его длина совпадает с фактическим числом записей.

Для дальнейших проверок можно использовать псевдослучайные операции с фиксированным начальным значением генератора. Но помимо него нужно сохранять и полный список операций. Запись о сбое должна содержать как минимум номер операции, ключ, записываемое значение и порядок до и после выполнения. Тогда последовательность удастся воспроизвести и после обновления реализации.

Если рабочая версия использует связный список, возьмите простую модель на массиве за эталон. Выполняйте одну и ту же последовательность в обеих реализациях и сравнивайте результаты. Не копируйте рабочую реализацию в качестве «правильного ответа»: иначе один и тот же дефект легко останется незамеченным с обеих сторон.

Соблюдайте границы при интеграции в iOS-проект

В примере нет синхронизации. Даже две асинхронные задачи загрузки не могут напрямую совместно использовать этот экземпляр. После перехода на actor или единую последовательную точку доступа обновление порядка при чтении, запись и вытеснение должны быть защищены вместе. Блокировка только записи всё равно приведёт к нарушению порядка.

Ограничение по числу записей также не означает ограничение по объёму в байтах. Десять миниатюр и десять исходных изображений требуют разного количества памяти. Если перейти к ограничению по стоимости хранения, придётся отдельно определить правила для суммарной стоимости, замены стоимости при обновлении того же ключа и отказа в сохранении слишком большой отдельной записи. Существующие тесты количества не доказывают соблюдение бюджета памяти.

Наконец, адаптируйте реальный кеш приложения к тому же контракту, а не оставляйте тесты только для учебной модели. После успешного прохождения чисто алгоритмических тестов добавьте несколько интеграционных проверок: убедитесь, что запись после завершения загрузки и чтение из интерфейса действительно обращаются к одному экземпляру. Сохранённые последовательности, вызывающие сбой, помогут решить проблему лучше, чем слепое увеличение ёмкости кеша.

Часто задаваемые вопросы