Алгоритм кэширования сохранения результата кэш памяти

Обновлено: 02.07.2024

Есть много способов сделать приложения быстрыми. Кэширование — это один из подходов, который при правильном использовании значительно ускоряет работу и снижает нагрузку на вычислительные ресурсы. Модуль Python functools поставляется с декоратором @lru_cache, который позволяет кэшировать результаты выполнения ваших функций, используя стратегию Least Recently Used (LRU). Это простой, но мощный метод, который вы можете использовать, чтобы использовать возможности кэширования в вашем коде.

В этом уроке вы узнаете:

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

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

Что такое кэширование и как его использовать

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

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

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

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

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

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

Вот пример того, как может выглядеть этот метод кеширования:

Сохраните этот код в файле caching.py, установите библиотеку запросов и запустите скрипт:

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

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

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

Новые записи, скорее всего, будут использованы повторно Более старые записи, скорее всего, будут использованы повторно Недавно использованные записи, скорее всего, будут использованы повторно Наиболее вероятно, что будут повторно использованы наименее используемые записи Записи с большим количеством совпадений с большей вероятностью будут использоваться повторно

В следующих разделах вы более подробно рассмотрите стратегию LRU и то, как ее реализовать с помощью декоратора @lru_cache из модуля functools.

Стратегия кэширования недавно использованного (LRU)

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

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

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

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

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

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

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

Эта стратегия очень быстрая. Доступ к наименее недавно использовавшемуся элементу и обновление кеша — это операции со временем выполнения O(1).

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

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

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

Игра с лестницей

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

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

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

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

Такой подход называется рекурсией. Если вы хотите узнать больше, ознакомьтесь с разделом «Рекурсивное мышление в Python».

Вот функция, реализующая эту рекурсию:

Сохраните этот код в файл с именем stairs.py и запустите его с помощью следующей команды:

Великолепно! Код работает для 4 ступенек, но если ступенек будет больше? Измените количество ступенек в строке 33 на 30 и перезапустите скрипт:

Ух ты, более 53 миллионов комбинаций! Можно с ума сойти!

Время исполнения кода

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

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

Вам также необходимо импортировать модуль timeit в начале кода:

Вот построчное объяснение этих дополнений:

Строка 1 импортирует имя steps_to() , чтобы timeit.repeat() знал, как его вызвать.
Строка 2 подготавливает вызов функции с номером лестницы, который вы хотите достичь, который в данном случае равен 30. Это оператор, который будет выполнен и рассчитан по времени.
Линия 3 звонит timeit.repeat() с кодом настройки и оператором. Это вызовет функцию 10 раз, возвращая количество секунд, которое заняло каждое выполнение.
Строка 4 определяет и печатает самое короткое возвращенное время.

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

Измерения времени зашумлены, потому что система одновременно выполняет другие процессы. Самое короткое время всегда наименее шумно, что делает его наилучшим представлением времени выполнения функции.

Теперь снова запустим скрипт:

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

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

Мемоизация для улучшения решения

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

Обратите внимание, что вам нужно вызывать steps_to() с одним и тем же аргументом несколько раз. Например, steps_to(5) вычисляется два раза, steps_to(4) вычисляется четыре раза, steps_to(3) семь раз и steps_to(2) шесть раз. Вызов одной и той же функции несколько раз добавляет циклы вычислений, в которых нет необходимости — результат всегда будет одним и тем же. Чтобы решить эту проблему, вы можете использовать метод, называемый мемоизацией. Такой подход гарантирует, что функция не запускается для одних и тех же входных данных более одного раза, сохраняя ее результат в памяти, а затем ссылаясь на него позже, когда это необходимо. Этот сценарий звучит как прекрасная возможность использовать декоратор Python @lru_cache !

Примечание. Дополнительная информация о мемоизации и использовании @lru_cache для ее реализации в «Мемоизация в Python».

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

Импортируйте декоратор @lru_cache из модуля functools .
Используйте @lru_cache для украшения steps_to() .

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

Запуск обновленного скрипта дает следующий результат:

В результате кеширование время выполнения функции с 40 секунд уменьшилось до 0,0008 миллисекунд! Это фантастическое улучшение!

Примечание. В Python 3.8 и более поздних версиях вы можете использовать декоратор @lru_cache без скобок, если вы не указываете никаких параметров. В предыдущих версиях вам может потребоваться включить круглые скобки: @lru_cache() .

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

Распаковка функциональности @lru_cache

С помощью декоратора @lru_cache вы сохраняете каждый вызов и ответ в памяти, чтобы получить к ним доступ позже, если потребуется снова. Но сколько вызовов вы можете сохранить, прежде чем иссякнет память?

Декоратор Python @lru_cache предлагает атрибут maxsize , который определяет максимальное количество записей до того, как кеш начнет удалять старые элементы. По умолчанию, maxsize установлен на 128. Если вы установите maxsize на None , то кеш будет расти бесконечно, и никакие записи не будут удалены. Это может стать проблемой, если вы храните в памяти большое количество различных вызовов.

Вот пример @lru_cache с использованием атрибута maxsize:

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

Чтобы увидеть, что происходит с этим новым дополнением к коду, вы можете использовать cache_info() , предоставляемый декоратором @lru_cache , для проверки количества попаданий и промахов и текущего размера кеша. Для наглядности удалите код, который определяет время выполнения функции. Вот как выглядит окончательный сценарий после всех изменений:

Если вы вызовете скрипт еще раз, то увидите следующий результат:

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

Вот разбивка свойств, предоставляемых cache_info() :

hits = 52 — это количество вызовов, которые @lru_cache вернул непосредственно из памяти, поскольку они существовали в кеше.
misses = 30 — это количество вызовов, которые не поступили из памяти и были рассчитаны. Поскольку вы пытаетесь найти количество шагов, чтобы достичь тридцатой ступени, имеет смысл, что каждый из этих вызовов пропускал кэш при первом выполнении.
maxsize = 16 — это размер кеша, который вы определили с помощью атрибута maxsize декоратора.
currsize = 16 — текущий размер кеша. В этом случае это показывает, что ваш кеш заполнен.

Если вам нужно удалить все записи из кеша, вы можете использовать cache_clear() , предоставленный @lru_cache .

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

Сохраните этот сценарий в файл с именем monitor.py, установите анализатор каналов и библиотеки запросов и запустите сценарий. Он будет работать непрерывно, пока вы не остановите его, нажав Ctrl + C в окне терминала:

Вот пошаговое объяснение кода:

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

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

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

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

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

Вот возможная реализация этого нового декоратора:

Вот разбивка этой реализации:

Строка 4 — Декоратор @timed_lru_cache будет поддерживать время жизни записей в кеше (в секундах) и максимальный размер кеша.
Строка 6: Код завершает декорированную функцию декоратором lru_cache . Это позволяет вам использовать функциональность кеширования, уже предоставленную lru_cache .
Строки 7 и 8 — Эти две строки инструментируют декорированную функцию с двумя атрибутами, представляющими время жизни кеша и фактическую дату истечения срока его действия.
Строки с 12 по 14 — Перед доступом к записи в кэше декоратор проверяет, не истекла ли текущая дата по истечении срока действия. Если это так,затем он очищает кеш и повторно вычисляет время жизни и дату истечения срока действия.

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

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

Теперь вы можете использовать свой новый декоратор @timed_lru_cache со сценарием монитора, чтобы предотвратить получение содержимого статьи при каждом доступе к ней.

Собрав для простоты код в один сценарий, вы получите следующее:

Обратите внимание, как строка 30 украшает get_article_from_server() с помощью @timed_lru_cache и указывает срок действия 10 секунд. Любая попытка получить доступ к той же статье с сервера в течение 10 секунд после ее загрузки вернет содержимое из кеша и никогда не попадет в сеть.

Запустите скрипт и посмотрите на результат:

Заключение

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

В этом уроке вы узнали:

Что такое разные стратегии кеширования и как они работают.
Как использовать декоратор @lru_cache в Python.
Как создать новый декоратор для расширения функциональности @lru_cache .
Как измерить время выполнения вашего кода с помощью модуля timeit .
Что такое рекурсия и как с ее помощью решить задачу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

скриншот_из_телеграмм.jpg

Пришла аватарка 1 — 100 на 100 пикселей, мы записали в кеш 100*100*4 байт.
Пришла аватарка 2 — 100 на 100 пикселей, мы записали в кеш 100*100*4 байт.
Пришла аватарка 1 — мы подняли ее в очереди наверх.

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

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

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

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

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

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

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

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

Cold — первая коробочка,
Warm — вторая,
Hot — третья.

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

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

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

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, но с более сложной стратегией:

Первая часть In — FIFO входящий кеш в который помещаются новые элементы.
Вторая часть Out — FIFO исходящий кеш, в который перемещаются элементы, вытесненные из коробочки In.
Третья часть Hot LRU кеш для элементов, запрошенных из Out.

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

элементы запрошенные из In никуда не двигаются. Вытесненные из In элементы — перемещаются в Out.
элементы запрошенные из Out — попадают в рай, в коробочку Main. Вытесненные же из Out (не использованные) — попадают сразу в ад (null).

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

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

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

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

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

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

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

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

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

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

Кэширование – один из подходов, который при правильном использовании значительно ускоряет работу и снижает нагрузку на вычислительные ресурсы. В модуле стандартной библиотеки Python functools реализован декоратор @lru_cache , дающий возможность кэшировать вывод функций, используя стратегию Least Recently Used (LRU, «вытеснение давно неиспользуемых»). Это простой, но мощный метод, который позволяет использовать в коде возможности кэширования.

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

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

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

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

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

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

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

Хотя вызов get_article() выполняется дважды, статья с сервера загружается лишь один раз. После первого доступа к статье мы помещаем ее URL и содержимое в словарь cache . Во второй раз код не требует повторного получения элемента с сервера.

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

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

Стратегия	Какую запись удаляем	Эти записи чаще других используются повторно
First-In/First-Out (FIFO)	Самая старая	Новые
Last-In/First-Out (LIFO)	Самая недавняя	Старые
Least Recently Used (LRU)	Использовалась наиболее давно	Недавно прочитанные
Most Recently Used (MRU)	Использовалась последней	Прочитанные первыми
Least Frequently Used (LFU)	Использовалась наиболее редко	Использовались часто

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

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

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

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

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

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

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

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

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

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

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

Примеры временной сложности различных функций Python рассматривались на proglib в статье «Сложность алгоритмов и операций на примере Python».

Начиная с версии 3.2, для реализации стратегии LRU Python включает декоратор @lru_cache .

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

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

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

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

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

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

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

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

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

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

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

Один из примеров мемоизации рассматривался в статье«Python и динамическое программирование на примере задачи о рюкзаке».

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

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

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

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

Если вы незнакомы с концепцией декораторов, но хотите глубже разобраться в вопросе, просто прочитайте материал«Всё, что нужно знать о декораторах Python» (она также адаптирована в форматеJupyterи Colab). Для наших задач достаточно знать, что это функции-обертки, которые позволяют модифицировать поведение функций и классов. Чтобы применить декоратор, достаточно объявить его перед определением функции.

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

В Python 3.8 и выше, если вы не указываете никаких параметров, можно использовать декоратор @lru_cache без скобок. В более ранних версиях необходимо добавить круглые скобки: @lru_cache() .

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

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

У декоратора @lru_cache есть атрибут maxsize , определяющий максимальное количество записей до того, как кэш начнет удалять старые элементы. По умолчанию maxsize равен 128. Если мы присвоим maxsize значение None , то кэш будет расти без всякого удаления записей. Это может стать проблемой, если мы храним в памяти слишком много различных вызовов.

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

Мы можем использовать информацию, возвращаемую cache_info() , чтобы понять, как работает кэш, и настроить его, чтобы найти подходящий баланс между скоростью работы и объемом памяти:

hits=52 – количество вызовов, которые @lru_cache вернул непосредственно из памяти, поскольку они присутствовали в кэше;
misses=30 – количество вызовов, которые взяты не из памяти, а были вычислены (в случае нашей задачи это каждая новая ступень);
maxsize=16 – это размер кэша, который мы определили, передав его декоратору;
currsize=16 – текущий размер кэша, в этом случае кэш заполнен.

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

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

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

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

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

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

Код оборачивает функцию декоратором @lru_cache . Это позволяет нам использовать уже знакомую функциональность кэширования.

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

Теперь мы можем использовать новый декоратор @timed_lru_cache с функцией monitor() , чтобы предотвратить скачивание с сервера содержимого статьи при каждом новом запросе. Собрав код в одном месте, получим следующий результат:

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

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

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

какие бывают стратегии кэширования;
как работает LRU-кэширование в Python;
как использовать декоратор @lru_cache ;
как рекурсивный подход в сочетании с кэшированием помогает достаточно быстро решить задачу.

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

Общий процесс интернет-приложений (веб-сайт / приложение) можно резюмировать, как показано на рисунке:

Пользователь запрашивает из интерфейса (браузер / приложение) пересылку по сети, службы приложений в хранилище (базу данных или файловую систему), а затем возвращается к интерфейсу для представления контента.

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

1. Характеристики кеша

Кэш является объектом модели данных и имеет некоторые из его характеристик.

1.1 Скорость попадания

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

1.2 Самый большой элемент (или самое большое пространство)

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

1.3 Клиринговая стратегия

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

FIFO(first in first out)
Первые данные, которые попадают в кэш, будут очищены первыми, если места в кэше недостаточно (превышает максимальный предел элемента), чтобы освободить место для новых данных.
Алгоритм стратегии в основном сравнивает время создания элементов кеша. в Требования к эффективности данных Вы можете выбрать этот тип стратегии, чтобы отдать приоритет доступности последних данных.

LFU(less frequently used)
Независимо от того, истек срок его действия или нет, он оценивается по количеству использований элемента, а менее используемые элементы очищаются, чтобы освободить место.
Алгоритм стратегии в основном сравнивает hitCount (количество совпадений) элементов. Гарантия Сценарии высокочастотной достоверности данных , Можете выбрать такую стратегию.

LRU(least recently used)
Независимо от того, истекает ли срок его действия, в соответствии с меткой времени, когда элемент использовался в последний раз, очистите элемент с самой дальней используемой меткой времени, чтобы освободить место.
Алгоритм стратегии в основном сравнивает время, когда элемент последний раз использовался функцией get. в Сценарий горячих данных Более применимо, приоритет отдается обеспечению достоверности данных о точках доступа.

Кроме того, есть несколько простых стратегий, таких как:

По сроку годности убирать элементы с наибольшим сроком годности
В соответствии со сроком действия очистите элементы, срок действия которых истекает недавно.
Случайная уборка
Очистите в соответствии с длиной ключевых слов (или содержанием элемента) и т. Д.

2. Кэшировать медиа

От Аппаратная среда С точки зрения памяти и жесткого диска;
из технологии Можно разделить на память, файл жесткого диска, базу данных

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

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

База данных: как упоминалось ранее, одна из целей увеличения стратегии кэширования - уменьшить нагрузку на ввод-вывод базы данных. Возвращается ли использование баз данных в качестве носителя кэш-памяти к старой проблеме? На самом деле существует множество типов баз данных, например, те специальные базы данных, которые не поддерживают SQL, но имеют простые структуры хранения значений ключа (например, BerkeleyDB и Redis). скорость ответа с участием Пропускная способность Они намного выше, чем наши обычно используемые реляционные базы данных.

3. Классификация кеша и сценарии приложений.

По степени связи между кешем и приложением он делится на локальный кеш с участием удаленный кеш (распределенный кеш) 。

Локальный кеш: Относится Кеширование компонентов в приложении , Его самым большим преимуществом является то, что приложение и кеш находятся в одном процессе, кэш запросов работает очень быстро и нет чрезмерных сетевых накладных расходов. Более целесообразно использовать локальный кеш в сценариях, когда отдельное приложение не требует поддержки кластера или когда узлам не нужно уведомлять друг друга. ; В то же время его недостатки Поскольку кеш связан с приложением, несколько приложений не могут напрямую совместно использовать кеш. Каждое приложение или узел кластера должны поддерживать свой собственный отдельный кеш, что является пустой тратой памяти. 。

Распределенный кеш: Относится к и Отдельный компонент или служба кэширования приложения , Его самым большим преимуществом является то, что это независимое приложение, Изолированные от локальных приложений, несколько приложений могут напрямую совместно использовать кеш 。

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

3.1 Локальный кеш

3.1.1 Программирование напрямую реализует кеш

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

Реализация переменной-члена или локальной переменной

Реализация статической переменной
Наиболее часто используемый синглтон реализует статическое кэширование ресурсов:

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

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

Компонент базовой конфигурации Meituan MtConfig использует аналогичный принцип, используя кэширование статических переменных в сочетании с унифицированным управлением ZooKeeper для автоматического динамического обновления кеша.

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

3.1.2 Ehcache

Ehcache - самая популярная среда кэширования с открытым исходным кодом на чистом Java. Она имеет простую конфигурацию, понятную структуру и мощные функции. Это очень легкая реализация кеширования. Наш обычно используемый Hibernate объединяет связанные функции кэширования.

Основное определение Ehcache в основном включает:

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

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

element: Составная единица единичных данных кэша.

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

Основные особенности：

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

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

Поддержка различных стратегий кеширования, гибкость

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

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

Поддерживает несколько экземпляров диспетчера кеша и несколько областей кеша одного экземпляра

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

Для получения дополнительных инструкций по Ehcache перейдите по ссылке.

3.1.3 Guava Cache

Guava Cache - это инструмент кэширования в Guava, библиотеке набора инструментов повторного использования Java с открытым исходным кодом от Google. Реализованные функции кеширования:

Автоматически загружать входной узел в структуру кеша

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

У него есть механизм истечения срока для вычисления узла входа на основе последнего доступа или записи.

Кэшированный ключ инкапсулирован в справке WeakReference

Кэшированное значение инкапсулируется в ссылки WeakReference или SoftReference.

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

Архитектурный дизайн Guava Cache вдохновлен ConcurrentHashMap.
Как мы упоминали ранее, в простых сценариях вы можете закодировать небольшой объем данных с помощью хэш-карты для кеширования небольшого объема данных, но если результат может измениться со временем или в пространстве данных, вы хотите сохранить управляемо, необходимо реализовать эту структуру данных самостоятельно.

Guava Cache наследует идею ConcurrentHashMap и использует детализированные блокировки в нескольких сегментах для обеспечения безопасности потоков при поддержке сценариев с высоким уровнем параллелизма.
Кэш аналогичен Map, который представляет собой набор пар "ключ-значение". Разница в том, что он также должен обрабатывать логику алгоритма, такую как выселение, истечение срока действия и динамическая загрузка, а также требует некоторой дополнительная информация для выполнения этих операций. В связи с этим, согласно объектно-ориентированному мышлению, необходимо связывать методы и инкапсуляцию данных.

На рисунке 5 показана модель данных кеш-памяти. Можно увидеть, что интерфейс ReferenceEntry используется для инкапсуляции Пара "ключ-значение" , И используйте ValueReference для инкапсуляции Ценность 。

ReferenceEntryЭто абстракция узла пары ключ-значение, который содержит абстрактный класс Key и Value ValueReference.
Кэш состоит из нескольких сегментов, каждый из которых содержит массив ReferenceEntry, а каждый элемент массива ReferenceEntry представляет собой цепочку ReferenceEntry. ReferenceEntry содержит поля key, hash, valueReference и next. В дополнение к цепочке, сформированной в элементах массива ReferenceEntry, в сегменте все ReferenceEntry также образуют цепочку доступа (accessQueue) и цепочку записи (writeQueue)
ReferenceEntry может быть ключом сильного ссылочного типа или ключом типа WeakReference. Чтобы уменьшить использование памяти, вы также можете определить, нужна ли вам цепочка записи, а цепочка доступа определяет конкретную ссылку, которая будет созданы: StrongEntry, StrongWriteEntry, StrongAccessEntry, StrongWriteAccessEntry и т. д.
Для некоторых других инструкций по Guava Cache, пожалуйста, перейдите по ссылке

Читайте также: