LRU, метод вытеснения из кэша

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

    Мы будем под кэшированием понимать сохранение результатов вычислений в ответ на некоторые запросы. То есть, повторный результат запроса не всегда вычисляется заново, но иногда берется из таблицы, называемой кэшем. Сложно переоценить роль кеширования в современных системах. При этом часто возникает проблема, связанная с недостатком памяти. Действительно, что делать, если запросов много, а памяти хватает лишь для хранения ограниченного числа результатов? В этом случае, как правило, кеш стрится следующим образом. Фиксируется размер кэша, пусть будет N, и сохраняются результаты только для N самых «популярных» запросов.

    То есть сохраняются результаты вычислений, которые скорее всего запросят заново.
    Как определять эти «популярные» запросы? Наиболее известным способом является LRU, о котором я и расскажу в этой статье.

    LRU (least recently used) — это алгоритм, при котором вытесняются значения, которые дольше всего не запрашивались. Соответственно, необходимо хранить время последнего запроса к значению. И как только число закэшированных значений превосходит N необходимо вытеснить из кеша значение, которое дольше всего не запрашивалось.

    Для реализации этого метода нам понадобятся две структуры данных:
    1. Хеш-таблица hashTable, которая будет хранить непосредственно закэшированные значения.
    2. Очередь с приоритетами timeQueue. Структура, которая поддерживает следующие операции:
      • Добавить пару значение и приоритет timeQueue.Add(val, priority).
      • Извлечь (удалить и вернуть) значение с наименьшим приоритетом timeQueue.extractMinValue().
    Подробнее про очереди с приоритетами можно почитать здесь

    Предположим, что для исходных вычислений использовался метод calculate(x). Мы заменим метод calculate на новый calculateWithCache, который пополняет кеш, выталкивает устаревшие значения и запрашивает результат у calculate, если не найдет в кеше.

    Так будет выглядеть алгоритм работы calculateWithCache:

    calculateWithCache(key) {
        curTime = getCurrentTime();
        // Если значение уже было в кэше вернем его
        if (key in hashTable) {
            // Сначала обновим время последнего запроса к key
            timeQueue.set(key, curTime);
            return hashTable[key];
        }
        // Иначе вычислим результат
        result = calculate(key);
    
        // Если в кэше уже N элементов, то вытесним самый старый
        if (hashTable.length == N) {
            minKey = timeQueue.extractMinValue();
            hashTable.remove(minKey);
        }
    	
        // Добавим в таблицу, и в очередь
        hashTable.add(key, result);
        timeQueue.add(key, curTime);
    	
        return result;
    }
    


    Вот и все. Теперь вместо необходимости сбрасывать кэш пользователю необходимо задать размер кэша. При этом приветствуется задание разумного значения по-умолчанию.

    Если воспользоваться эффективной реализацией очереди с приоритетами, то оверхед, который требует LRUO(log N).

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

    Вопрос для тех, кто хочет чуть подумать. Как добиться константного оверхеда, считая, что сложность операции с хеш-таблицей — константа?
    Подсказка: нужно убрать очередь с приоритетами и использовать обычную очередь:)

    Можно найти более сложные эвристики, учитывающие время вычисления calculate для данного ключа key, или объем результата, или что-то еще.
    Но в большинстве задач LRU наиболее адекватно определяет самые «популярные» запросы.

    Примечание 1: Можно ограничить объем памяти на кэш, а не количество хранимых значений. Алгоритм практически не изменится, только вместо длины будет занимаемая память + память для хранения нового значения.
    Примечание 2: Специально избегал вопросов многопоточности, так как это не тема данной статьи.

    Update (Спасибо ToSHiC22 за комментарий) Для интересующихся ссылка на чуть более продвинутую реализацию 2Q
    Метки:
    • +24
    • 28,8k
    • 8
    Поделиться публикацией
    Комментарии 8
    • +6
      А чем двусвязный список + hash не угодил, зачем хранить время?
      • 0
        Ну да это и есть ответ на вопрос, просто исходный LRU описывается именно с временами. Да и мне кажется, что проще понять.
        • 0
          По-моему, стопка листов, в которую новый кладем сверху, а самый старый забираем снизу, понятнее.
          • +1
            Не только. Если лист в середине и спрашивается опять, то он должен быть поднят наверх.
            Для этого нужен именно двусвязанный список и еще хеш-таблица, для отслеживания какой лист на каком месте. Как правильно сказали в самом первом комментарии.
      • +3
        Варианты с одной очередью не очень хороши — однократно запрошенные элементы будут вытеснять чуть менее популярные элементы, которые запрашивали много раз. В интернетах встречаются статьи про кэши 2Q, где эта проблема частично решена: хэш-таблица для поиска элементов и 2 очереди. Сначала элемент попадает в нижнюю очередь, а если его запросили второй раз и он всё ещё в кэше — то тогда в верхнюю. Когда верняя очередь заканчиваются — элементы из неё вытесняются в нижнюю, из нижней же элементы вытесняются совсем и удаляются из кэша. Получается константное время поиска записи и её добавления

        Кстати, в бусте есть контейнер, который отлично подходят для подобных схем — intrusive list. Ну и ещё intrusive hashmap, чтобы уж совсем минимально с памятью работать.
        • +1
          Спасибо, читал в процессе написания статьи, и решил не грузить. Добавил ссылку для интересующихся.
        • 0
          О том какие готовые решения предоставляет Java можно почитать в статье Java LRU Cache
          • 0
            А как решаем проблему консистентности?

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.