Lru cache что это

Алгоритмы кэширования

Кэш — это временное хранилище для данных, которые с наибольшей вероятностью могут быть повторно запрошены. Загрузка данных из кэша осуществляется быстрее, чем из хранилища с исходными данными, но и его объём существенно ограничен.

Алгоритмы кэширования

Алгоритмы кэширования — это подробный список инструкций, который указывает, какие элементы следует отбрасывать в кэш. Их еще называют алгоритмами вытеснения или политиками вытеснения.

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

Least recently used — LRU (Вытеснение давно неиспользуемых)

LRU — это алгоритм, при котором вытесняются элементы, которые дольше всего не запрашивались. Соответственно, необходимо хранить время последнего запроса к элементу. И как только кэш становится заполненным, необходимо вытеснить из него элемент, который дольше всего не запрашивался.

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

LRU на самом деле является семейством алгоритмов кэширования, в которое входит 2Q, а также LRU/K.

Для реализации понадобятся две структуры данных:

• Хеш-таблица, которая будет хранить закэшированные значения.
• Очередь, которая будет хранить приоритеты элементов и выполнять следующие операции:
  • Добавить пару значение и приоритет.
  • Извлечь (удалить и вернуть) значение с наименьшим приоритетом.
  • Проверяем, есть ли значение в кэше:
    • Если значение уже есть, то обновляем время последнего к нему запроса и возвращаем значение.
    • Если значения нет в кэше — вычисляем его.
    • Если кэш заполнен, то вытесняем самый старый элемент.

    Достоинства:

    • константное время выполнения и использование памяти.

    Недостатки:

    • алгоритм не учитывает ситуации, когда к определенным элементам обращаются часто, но с периодом, превышающим размер кэша (т.е. элемент успевает покинуть кэш).

    Псевдо-LRU — PLRU

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

    Most Recently Used — MRU (Наиболее недавно использовавшийся)

    MRU — алгоритм, который удаляет самые последние использованные элементы в первую очередь. Он наиболее полезен в случаях, когда чем старше элемент, тем больше обращений к нему происходит.

    Least-Frequently Used — LFU (Наименее часто используемый)

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

    В LFU каждому элементу присваивается counter — счётчик. При повторном обращении к элементу его счётчик увеличивается на единицу. Таким образом, когда кэш заполняется, необходимо найти элемент с наименьшим счётчиком и заменить его новым элементом. Если же все элементы в кэше имеют одинаковый счётчик, то в этом случае вытеснение осуществляется по методу FIFO: первым вошёл — первым вышел.

    Недостатки:

    • много обращений к элементу за короткое время накручивает счётчик и в результате элемент зависает в кэше.
    • алгоритм не учитывает “возраст” элементов.

    Multi queue — MQ (Алгоритм многопоточного кэширования)

    MQ — алгоритм, использующий несколько LRU очередей — Q0, Q1, …, Qn, между которыми элементы ранжируются/перемещаются в зависимости от частоты обращения к ним.

    В дополнение к очередям используется буфер “истории” — Q_out, где хранятся все идентификаторы элементов со счётчиками (частота обращения к элементу). При заполнении Q_out удаляется самый старый элемент.

    Элементы остаются в LRU очередях в течение заданного времени жизни, которое динамически определяется специальным алгоритмом.

    Если к очереди не ссылались в течение её времени жизни, то её приоритет понижается с Qi до Qi-1 или удаляется из кэша, если приоритет равен 0 — Q0.

    Каждая очередь также имеет максимальное количество обращений к её элементам. Поэтому если к элементу в очереди Qi обращаются более 2i раз, то этот элемент перемещается в очередь Qi+1.

    При заполнении кэша, будет вытеснен элемент из очереди Q0, который дольше всех не использовался.

    Картинка для наглядности:

    

    Другие алгоритмы

    Алгоритмов кэширования достаточно много, поэтому на данный момент не все здесь рассмотрены. С полным списком можно ознакомиться здесь.

    Со временем буду дополнять.

    Полезные ссылки

    Алгоритмы кэширования — статья на wiki.
    LRU (Least Recently Used) — подробная статья о LRU с примерами реализации на C, C++, Java.
    LRU, метод вытеснения из кэша — статья о том, как быстро реализовать алгоритм LRU.
    Least Frequently Used (LFU) Cache Implementation — статья о LFU с примером на C++.
    LFU cache in O(1) in Java — пример реализации LFU на Java.
    Алгоритмы кэширования — что-то вроде презентации некоторых алгоритмов кэширования в формате PDF.

    Lru cache что это

    LRU, или LRU cache (Least Recently Used) — алгоритм для хранения ограниченного объема данных: из хранилища вытесняется информация, которая не использовалась дольше всего. Его применяют при организации кэша.

    

    Освойте профессию
    «Fullstack-разработчик на Python»

    Кэш — это, например, данные приложений, которые те «держат под рукой», чтобы не загружать каждый раз при открытии. В таких хранилищах обычно находится информация, которую часто используют. Алгоритм LRU оставляет в кэше данные, которые использовались недавно, а те, к которым обращались давно, вытесняет.

    LRU — не единственный алгоритм для организации кэша. Есть похожая модель FIFO (First-In/First-Out). Она удаляет самые старые элементы. В отличие от нее, LRU смотрит не на время добавления, а на то, когда информацию использовали в последний раз.

    Кто и когда пользуется LRU

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

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

    Профессия / 12 месяцев
    Fullstack-разработчик на Python

    Создавайте веб-проекты самостоятельно

    

    Как работает алгоритм

    Реализовать алгоритм можно на любом языке программирования: C и C++, Java, Python и других. В популярных языках для LRU и других востребованных алгоритмов есть свои библиотеки и функции.

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

    

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

    Размер кэша фиксирован одним из двух способов: или в нем может храниться определенное количество элементов, или ограничен объем памяти.

    

    Станьте Fullstack-разработчик на Python и найдите стабильную работу
    на удаленке

    Преимущества и недостатки

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

    Как реализовать алгоритм

    Обычно реализация включает две структуры: хеш-таблицу с данными и список, где хранятся временные метки. Каждому элементу в таблице соответствует метка в списке — она определяет приоритет. Когда программа обращается к кэшу, чтобы добавить туда данные, алгоритм сверяется со списком приоритетов. А если к данным, которые есть в кэше, нужно обратиться, алгоритм не просто сверяется, а перезаписывает временную метку.

    Fullstack-разработчик на Python

    Fullstack-разработчики могут в одиночку сделать IT-проект от архитектуры до интерфейса. Их навыки востребованы у работодателей, особенно в стартапах. Научитесь программировать на Python и JavaScript и создавайте сервисы с нуля.

    Что такое кэширование?

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

    Системы кэширования хранятся на оборудовании с более быстрым доступом, таким как оперативная память (RAM). Оперативная память обеспечивает более быструю работу ввода-вывода и уменьшает задержку. Кэширование задействовано на всех уровнях технологий, например в операционных системах, CDN, DNS, во многих приложениях, таких как поиск, а также используется для повышения производительности медиаконтента в играх.

    При реализации уровня кэша важно понимать, какое значение имеет достоверность кэшированных данных. Успешное кэширование приводит к повышению частоты обращений, а значит, данные присутствуют при запросе к ним. Промах кэша возникает, когда информации в кэше не оказалось. Для управления истечением срока действия данных могут применяться такие элементы управления, как TTL (Time to live).

    Требования к функциональности

    • Нужно сохранить огромное количество данных — около терабайта.
    • Кэш должен выдерживать от 50 до 1 млн запросов в секунду.
    • Ожидаемая задержка — около 1 мс.
    • LRU (Least Recently Used) — алгоритм, при котором вытесняются значения, которые дольше всего не запрашивались.
    • 100% доступность.
    • Масштабируемость.

    Шаблоны доступа к кэшу

    • Кэш сквозной записи. Всякий раз, когда приходит какой-либо запрос на “запись”, он будет поступать в БД через кэш. Запись считается успешной только в том случае, если данные успешно записаны и в кэш, и в БД.
    • Кэш прямой записи. Запрос на запись идет напрямую в БД, минуя кэш, и подтверждение отправляется обратно. Данные не уходят в кэш, а записываются туда только при первом промахе кэша.
    • Кэш обратной записи. Обновленная запись отправляется в кэш, данные сохраняются в кэше, и подтверждение отправляется немедленно. Затем другой сервис передает данные в БД.

    Структура данных для реализации кэша называется “хеш-таблицей”. Все, что нам нужно, — это функция хеширования, ключ и значение.

    Работа с хеш-таблицей

    Как показано изображении, у нас есть три набора данных: “яблоко”, “мальчик” и “кот”, которые необходимо сохранить в хеш-таблице. Эти значения задаются в качестве входных параметров для функции хеширования ( hashCode() ), откуда мы получаем хешированные значения, в данном случае 53, 78 и 76. Затем эти значения делятся на количество ячеек в корзине, т.е. в данном случае на 10, и сохраняются в ячейке, номер которой совпадает со значением остатка: 53 в ячейке №3, 78 в ячейке №8 и так далее.

    Допустим, у нас есть еще одни данные “гусеница”, хешированное значение которых равно 66, и они должны сохраниться в ячейке № 6, как и “кот”. Когда два разных ключа выдают одно и то же значение ячейки, происходит коллизия. По очевидной причине нельзя сохранить оба значения в одном и том же месте.

    Существует несколько стратегий разрешения коллизий, такие как метод раздельных цепочек, открытая адресация, хеширование Робин Гуда. Простая стратегия — вместо сохранения в ячейке конкретного значения создавать связанный список, где и будут храниться пары ключ-значение. Это называется раздельными цепочками с использованием связанного списка.

    Чтобы получить значение, дайте ключ хеш-функции, например “яблоко”, получите хешированное значение, рассчитанное по количеству ячеек, и посмотрите на конкретное положение.

    Кэширование в распределенной системе

    Как показано на рисунке, все значения оранжевого цвета хранятся в узле 1, а синего — в узле 2. Если по какой-либо причине узел 2 выйдет из строя, эти два положения, т. е. ячейки под номерами 9 и 10, станут недоступны. Хеш-таблица в таком случае остается прежней, но размер корзины теперь равен 8. Теперь для того же примера “яблоко” нужно брать остаток от деления на 8 — 53/8. Вместо 3 получаем 5. В данном случае эта ячейка пуста.

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

    Работа с согласованным хеш-кольцом

    В обычном сценарии нам известна доступная область памяти, поскольку мы последовательно именуем ключи в хеш-таблице с помощью чисел, например от 1 до 10. Нюанс в том, что здесь ключи назначаются совершенно случайным образом.

    Для значения “яблоко” мы передаем его в функцию хеширования и получаем результат: 2394. Берем этот хеш-номер и сразу находим местоположение — набор ключей, который больше 2394, в данном случае это 3030. Мы сохраняем значение здесь.

    Допустим, есть еще один ключ “шарик” со значением 2567 — он также будет храниться в том же месте цепочки. Если мы получили хешированное значение 11000, то, поскольку доступного значения в ячейках нет, мы возвращаемся к началу и сохраняем в 1000. Это что-то вроде закольцовки. Вот как работает согласованное хеш-кольцо.

    Политика вытеснения кэша

    Как вытеснять кэш и когда нужно это делать?

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

    Одна из распространенных стратегий вытеснения — Least Recently Used или LRU. Она предполагает удаление записи, к которой за последнее время обращались реже всего.

    Необходимо каким-то образом выяснить, к какой ячейке происходило меньше всего обращений, и сохранить новую запись именно там. Как реализовать LRU?

    Пример кода LRU:

    Внутренние части кэша

    Мы разобрались с хеш-таблицами, оперативной памятью и LRU. Теперь нам нужен сервис, который обслуживает запросы на получение/размещение/удаление (get/put /delete). Несмотря на высокую скорость работу, оперативная память все равно блокирует вызовы. Поэтому нужен эффективный способ удовлетворения этих запросов.

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

    Как показано на рисунке выше, у нас есть очередь событий. Туда попадает любой запрос “get/put”. Также есть цикл событий, который выполняется бесконечно и представляет собой однопоточную операцию. Помимо этого, доступен пул потоков, который выполняет только операции ввода-вывода в оперативную память.

    Каждый раз, когда мы получаем запрос “get/put”, он помещается в очередь событий. Цикл событий продолжает считывать очередь событий и передает запрос, который свободно располагается в ней. Как только происходит передача в пул потоков, он выполняет обратный вызов и снова считывает очередь событий.

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

    Отказоустойчивость

    Как сделать систему кэширования отказоустойчивой? Мы знаем, что хеш-таблица и данные хранятся в оперативной памяти. А что, если произойдет потеря питания и все данные будут сброшены? Это означает, что система кэширования нестабильна, и это нужно исправить.

    1. Снимок с регулярным интервалом. Синхронный сервис “S” работает в фоновом режиме. Он берет замороженную копию хеш-таблицы и помещает ее в файл дампа, который сохраняется на жестком диске.

    2. Восстановление журнала. Сервис, отвечающий за чтение и запись в хеш-таблице, будет непрерывно восстанавливать файлы в журнале. Все операции в журнале выполняют асинхронный вызов, который продолжает обновлять его. Эти запросы можно поместить в промежуточную очередь, чтобы не влиять на возможность чтения/записи. Каждая операция регистрируется, и если оборудование выйдет из строя и снова включится, мы сможем восстановить хеш-таблицу через операции в файле журнала.

    Доступность

    Как сделать систему доступной на 100%?

    В кластере есть два узла, node1 и node2, и у обоих есть свой собственный кэш. Допустим, мы используем согласованное хеширование: узел 1 содержит ключи и значения, а узел 2 обрабатывает их. Что произойдет, если узел 1 выйдет из строя?

    Все запросы, поступающие на узел 1, будут приводить к промаху кэша. Они будут попадать в БД, увеличивая нагрузку по чтению/записи. Чтобы избежать этого, можно сделать реплику узла 1, например RF = 2. Поэтому, какие бы данные ни были у узла 1, такие же будут на узле 1’.

    Преимущество. Нагрузка снижается, потому что запросы, поступающие на узел 1, также будут отправляться на узел 1’ и обрабатываться им. Таким образом, запросы на чтение распределяются и обеспечивают высокую производительность с меньшей задержкой.

    Недостаток. Продолжительная синхронизация этих двух узлов может привести к непоследовательности.

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

    • Балансировка нагрузки и последовательное хеширование
    • Основные принципы кэширования веб-приложений
    • Лучший способ эффективно управлять неструктурированными данными

    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; > 

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

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

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

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

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

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

    Update (Спасибо ToSHiC22 за комментарий) Для интересующихся ссылка на чуть более продвинутую реализацию 2Q

    Похожие публикации:

    1. Как оформить портфолио анализа данных
    2. Как разрабатывать
    3. Как сохранить работоспособность
    4. Что такое презентер android