Что такое lru cache

Декоратор @lru_cache() модуля functools в Python.

Кеширование результата выполнения функции.

Синтаксис:

Параметры:

Возвращаемое значение:

Описание:

Декоратор @lru_cache() модуля functools оборачивает функцию с переданными в нее аргументами и запоминает возвращаемый результат соответствующий этим аргументам. Такое поведение может сэкономить время и ресурсы, когда дорогая или связанная с вводом/выводом функция периодически вызывается с одинаковыми аргументами.

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

Различные аргументы можно рассматривать как отдельные вызовы с отдельными записями в кэше. Например f(a=1, b=2) и f(b=2, a=1) различаются по порядку ключевых аргументов и могут иметь две отдельные записи в кэше.

Обратите внимание: специфичность типа применяется только к непосредственным аргументам функции, а не к их содержимому. Скалярные аргументы Decimal(42) и Fraction(42) обрабатываются как отдельные вызовы с разными результатами. Напротив, аргументы кортежа (‘answer’, Decimal(42)) и (‘answer’, Fraction(42)) обрабатываются как эквивалентные.

Примеры использования:

Пример кэша LRU для статического веб-контента:

Пример эффективного вычисления чисел Фибоначчи с использованием кэша для реализации техники динамического программирования:

Источник

Эффективное кеширование. От теории к практике

Как правило, статьи о кешировании начинаются за здравие, а заканчиваются LRU кешем. Попробуем переломить эту тенденцию? Начнем с того, чем LRU плох, а закончим за здравие. Я надеюсь.

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

Спрашивая на собеседованиях какие алгоритмы кеширования вы знаете — как правило слышишь в ответ, ммм… LRU Cache… Зато если спросить про алгоритмы сортировки, вероятность услышать что-то помимо «Пузырек» — значительно выше. Человек готов потратить несколько дней на поиск оптимальной библиотеки ресайза изображений или веб фреймворка, не понимая, что реализовав эффективный кеш, он может взять в принципе любую библиотеку со схожими характеристиками, так как кеш — минимизирует обращения к ней, сгладив разницу в быстродействии.

Для Relap.io, как для хайлоад сервиса, кеширование особенно важно. Например, вчера мы показали рекомендации на различных сайтах 789301033 раз. Поэтому у нас густо обмазано кешем все: рекомендации, картинки, реклама и так далее.

Не все кеши одинаково полезны

Хороший пример LRU Cache.

На конкурсы алгоритмов его обычно не берут. Никто не хочет иметь ничего общего с неудачником. Сложно придумать более неэффективный алгоритм. Единственный алгоритм, у которого LRU Cache выигрывает по эффективности — это, наверно, просто очередь, например, FIFO. Тем не менее, LRU встроен везде и всюду как дефолтный и, к сожалению, часто единственный алгоритм, так как он прост в реализации.

Вам хотелось бы пользоваться сайтом, приложением или операционной системой, которая тормозит, неэффективна и жрет ресурсы как не в себя, но зато она написана на простом в реализации языке, например, условном бейсике? Если нет — добро пожаловать под кат.

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

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

Несколько лет назад мы писали приложение под андроид для Surfingbird. Мы перешли на RX Java. Асинхронизировали все что можно. Сгладили все переходы анимацией, тем не менее осталась одна нерешенная проблема, это постоянные перезагрузки картинок. И ваше приложение буквально кишит картинками, и они постоянно ротируются меняются и вам не хватает памяти для их размещения.

Признаюсь, я поначалу думал что все дело в имаджлоадере. Достаточно выбрать эффективный и вуаля. Я пересмотрел все. Пикассо, Фейсбуковский fresco, UIL не помню уже все названия. Но проблема оставалась. Картинки грузились где то чуть быстрее, где то чуть плавнее, но они грузились. Тогда я сел, и написал свой. Простой. Чистый. Легкий. И это не помогло. Глупые имаджлоадеры продолжали постоянно теребить картинки нервируя пользователя и никак не могли отделить зерна от плевел. Тогда я вспомнил о правиле Парето.

Если предположить, что 20% картинок — показываются 80% раз — все встает на свои места. Единственное что осталось понять — какие именно картинки надо хранить.

Как работает LRU cache?

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

Если внимательно посмотреть на скриншот, то можно увидеть, что сообщения пользователей сопровождаются аватарками, а в теле сообщений — встречаются картинки. Перед вами стоит задача — сделать максимально плавный интерфейс. Давайте еще раз взглянем на скриншот выше. Мы видим 2 повторяющиеся автарки в диалоге, и затем юзер 1 прислал большую картинку.

Пока все идет неплохо.

Пришла картинка 1024 на 768 пикселей, мы записали в кеш 1024*768*4 байт — и БАМ! Наши прекрасные аватарки выбило напрочь из кеша. Теперь там торжественно валяется картинка, которую нужно было показать один раз и не нужно было кешировать.

Как победить?

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

Простите, что я тут чуть чуть сжухлю, и опишу очень коротко прописные истины.

LRU — не использованный дольше всех вылетает из кеша.
MRU — последний использованный вылетает из кеша (специфичный кейс, бережем старье).
LFU — реже всего использованный вылетает из кеша.

Это база. Вас может испугать что затраты на вычисления растут с ростом сложности алгоритмов, но не критично. Попробуйте сравнить время лукапов по ключам в памяти со временем рендеринга картинки 1024 на 768. А именно это произойдет если алгоритм «промахнулся».

SNLRU (сегментированный LRU) — заводим несколько «коробочек» с LRU. Сперва кладем в первую коробочку, при повтороном запросе перекладываем во вторую из второй — в третью.

Это уже неплохой алгоритм, он используется в недрах freebsd, если не ошибаюсь. По крайней мере я сталкивался с ним в данном контексте.

Mid point LRU — сегментированный LRU в котором всего две коробочки.

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

ARC, GCLOCK — и прочие более сложные алгоритмы придется на время вынести за скобки. Не то чтобы они плохие или неинтересные, тот же ARC используется (точнее, наверное, использовался, судя по данной преисполненной боли статье: www.varlena.com/GeneralBits/96.php) в postgreSQL. Не удержусь от небольшой цитаты:

Database systems often use LRU algorithms but many are switching to other algorithms to better handle a variety of behaviors not handled well by LRU. For example, one one-time very large sequential scan might flood the cache with pages that are not expected to be used again any time soon. The cache then is not helpful until it is re-populated with more commonly used pages.

2Q — или две очереди, примечателен тем, что сохраняя простоту реализации, он прекрасно адаптируется. Кеш разделяется на три части, как в сегментированном LRU, но с более сложной стратегией:

Стратегия вытеснения из кеша:

Ссылка на каноническое описание.

Во первых — это красиво. Коробочку Main — делаем, например, 20% (помните о Парето?) именно тут скопятся наши аватарки. А вот Out — надо сделать побольше, процентов 60. Так как это «отстойник».

В чем прелесть In — новые элементы спокойно спускаются по FIFO трубе из In в Out, не подпрыгивая и никуда не перемещаясь по мере запросов. А вот если опять запросили (например пользователь подскролил вверх) и, картинка успела перейти из In в Out — вот она картинка победительница. Кеш на уровне архитектуры корректирует некие типичные корреляции, присутствующие в обычной жизни. И после внедрения исчезли постоянные перезагрузки в условиях ограниченного размера памяти. Парето сработал. Но мы еще не раз вернемся к Парето.

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

Обратите внимание на контейнеры:

Управление «кучками» реализовано на супербыстрых и экономичных по памяти LinkedHashSet, нам не важно значение, важно лишь в какой «кучке» какой ключ находится в данный момент. Это ключ к быстродействию.

Больше практики. Допустим мы хотим прикрутить его к имадж лоадеру — пул реквест к пикассо: github.com/square/picasso/pull/1134
Но вообще это не обязательно. Нормальные либы — позволяют подключить произвольный алгоритм кеширования — достаточно скопипастить класс и переопределить кеш (glide вроде умел, picasso, начиная с какой то версии)

Я уже не помню точных цифр по хитрейту в своем случае. Помню только что у LRU — хитрейт был более 70% но менее 80. У 2Q — чуть более 80%. Но чудо произошло. Потому что все, что нам надо — это закешировать 20% инфы, которая составит 80% трафика. Чудо еще кстати состояло в том, что по скорости 2Q был быстрее LRU.

У нас в Relap.io, несколько реализаций кешей, например моя — github.com/recoilme/2qcache (вообще я не перл программист, это моя первая и надеюсь единственная программа на этом языке, единственный ее плюс — она простая).

Поэтому рекомендую посмотреть на реализацию 2Q на перле от нашего ведущего разработчика:

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

🧩 Кэширование в Python: алгоритм LRU

Leo Matyushkin

Эта публикация – незначительно сокращенный перевод статьи Сантьяго Валдаррама Caching in Python Using the LRU Cache Strategy. Переведенный текст также доступен в виде блокнота Jupyter.

В этом руководстве мы рассмотрим:

Кэширование в Python: в чем польза

Кэширование – это метод оптимизации хранения данных, при котором операции с данными производятся эффективнее, чем в их источнике.

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

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

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

Реализация кэширования в Python посредством словаря

В Python можно реализовать кэширование, используя словарь. Вместо того, чтобы каждый раз обращаться к серверу, можно проверять, есть ли контент в кэше, и опрашивать сервер только если контента нет. В качестве ключа можно использовать URL статьи, а в качестве значения – ее содержимое:

Примечание. Для запуска этого примера у вас должна быть установлена библиотека requests :

Стратегии кэширования

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

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

Погружаемся в идею LRU-кэширования

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

На следующем рисунке показано представление кэша после того, как пользователь запросил статью из сети.

Процесс заполнения LRU-кэша, шаг 1

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

Процесс заполнения LRU-кэша, шаг 2

Вторая статья занимает последний слот, перемещая первую статью вниз по списку.

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

Заглядываем за кулисы кэша LRU

Один из способов реализовать кэш LRU в Python – использовать комбинацию двусвязного списка и хеш-таблицы. Головной элемент двусвязного списка указывает на последнюю запрошенную запись, а хвостовой – на наиболее давно использовавшуюся.

На рисунке ниже показана возможная структура реализации кэша LRU.

Схема реализации кэширования

Использование @lru_cache для реализации кэша LRU в Python

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

Наглядное представление алгоритма: перепрыгиваем ступеньки

Представим, что мы хотим определить число способов, которыми можем достичь определенной ступеньки на лестнице. Сколько есть способов, например, добраться до четвертой ступеньки, если мы можем переступить-перепрыгнуть 1, 2, 3 (но не более) ступеньки? На рисунке ниже представлены соответствующие комбинации.

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

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

Опишем программно рекурсивное решение в точности, как мы его сейчас видим:

Код работает для 4 ступенек. Давайте проверим, как он подсчитает число вариантов для лестницы из 30 ступенек.

Получилось свыше 53 млн. комбинаций. Однако когда мы искали решение для тридцатой ступеньки, сценарий мог длиться довольно долго.

Засекаем время выполнения программного кода

Измерим, как долго длится выполнение кода.

Для этого мы можем использовать модуль Python timeit или соответствующую команду в блокноте Jupyter.

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

Использование мемоизации для улучшения решения

Наша рекурсивная реализация решает проблему, разбивая ее на более мелкие шаги, которые дополняют друг друга. На следующем рисунке показано дерево для семи ступенек, в котором каждый узел представляет определенный вызов steps_to() :

Дерево вызовов функции step_to()

Можно заметить, что алгоритму приходится вызывать steps_to() с одним и тем же аргументом несколько раз. Например, steps_to(5) вычисляется два раза, steps_to(4) – четыре раза, steps_to(3) – семь раз и т. д. Вызов одной и той же функции несколько раз запускает вычисления, в которых нет необходимости – результат всегда один и тот же.

Импортируем декоратор из модуля functools и применим к основной функции.

От единиц секунд к десяткам наносекунд – потрясающее улучшение, обязанное тем, что за кулисами декоратор @lru_cache сохраняет результаты вызова steps_to() для каждого уникального входного значения.

Другие возможности @lru_cache

Применим @lru_cache с использованием атрибута maxsize и добавим вызов метода cache_info() :

Добавление срока действия кэша

Перейдем от учебного примера к более реалистичному. Представьте, что мы хотим отслеживать появление на ресурсе Real Python новых статей, содержащих в заголовке слово python – выводить название, скачивать статью и отображать ее объем (число символов).

Real Python предоставляет протокол Atom, так что мы можем использовать библиотеку feedparser для анализа канала и библиотеку requests для загрузки содержимого статьи, как мы это делали раньше.

Скрипт будет работать непрерывно, пока мы не остановим его, нажав [Ctrl + C] в окне терминала (или не прервем выполнение в Jupyter-блокноте).

Код загружает и анализирует xml-файл из RealPython. Далее цикл перебирает первые пять записей в списке. Если слово python является частью заголовка, код печатает заголовок и длину статьи. Затем код «засыпает» на 5 секунд, после чего вновь запускается мониторинг.

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

Критерии исключения записей из кэша

Декоратор @timed_lru_cache реализует функциональность для оперирования временем жизни записей в кэше (в секундах) и максимальным размером кэша.

Перед доступом к записи в кэше декоратор проверяет, не наступила ли дата истечения срока действия. Если это так, декоратор очищает кэш и повторно вычисляет время жизни и срок действия. Время жизни распространяется на кэш в целом, а не на отдельные статьи.

Кэширование статей с помощью нового декоратора

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

Заключение

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

В этом уроке мы кратко рассмотрели:

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

Источник