В компьютерной сфере,缓存играет важную роль в процессе программирования. Стратегия кэширования ресурсов браузера является ключевым фактором, влияющим на производительность веб-сайтов.Buffer PoolЭто значительно повышает эффективность запросов к базе данных; как широко используемая база данных кэширования, Redis предоставляет богатые структуры данных и стратегии кэширования для удовлетворения потребностей разработчиков. Кэш повсеместно используется в современных компьютерных системах и представляет собой очень глубокую и обширную тему.Цель этой статьи состоит в том, чтобы извлечь сущность проектирования системного кэша из многих существующих системных проектов, в основном по трем аспектам:
многоуровневый кэш
Политика удаления кеша
кеш-сейф
Обсуждая эти темы, автор объединит множество практических примеров, которые будут включать низкоуровневый контент, такой как исходный код PHP, исходный код Redis, стратегия кэширования браузера, дизайн хранилища данных mysql, алгоритм удаления кэша и т. д. Если вы Для более старших инженеров-разработчиков, которые хорошо разбираются в этом содержании, эта статья будет очень кстати. Чтобы позаботиться о новичках, автор также максимально ясно опишет сложные и важные моменты знаний.Длина этой статьи немного велика, поэтому читатели должны быть готовы!
1. Многоуровневый кеш
1.1 Иерархия памяти
Компьютеры используют разные технологии хранения для доступа к данным, и время доступа сильно различается. Более быстрые технологии стоят больше за байт, чем более медленные технологии, и имеют меньшую емкость. Разрыв в скорости между процессором и основной памятью (памятью) увеличивается. Основываясь на этой характеристике, все современные компьютерные системы используют金字塔式的存储器层次结构. Как показано ниже:
Двигаясь сверху вниз, устройства хранения данных становятся медленнее, дешевле и крупнее. Верхний уровень (L0) — это небольшое количество быстрых регистров ЦП, к которым ЦП может получить доступ за один такт.(Один тактовый цикл обычно меньше 1 нс); за ними следует одна или несколько кэш-памятей SRAM малого и среднего размера, доступ к которым можно получить за несколько тактов ЦП; за которыми следует большая основная память на основе DRAM, к которой можно получить доступ за десятки-сотни тактов ЦП; за ними следуют медленные, но большие локальные диски (обычно SSD) и, наконец, некоторые системы даже включают дополнительный уровень сетевой файловой системы (NFS), такой как служба CFS, предоставляемая Tencent Cloud.Распределенный обмен данными может быть достигнут путем подключения к нескольким серверам.
Далее мы будем использовать конкретные данные для количественной оценки и сравнения скорости ЦП, диска и сети с точки зрения ЦП, чтобы иметь более интуитивное представление о различиях в скорости различных компонентов компьютера.
тип
кешировать содержимое
расположение кеша
Сколько времени требуется для чтения данных
Сравните продолжительность базовой единицы
регистры процессора
4 байта и 8 байт
Встроенные регистры ЦП
0.38ns
1s
Кэш L1
64-байтовый блок
Встроенная кэш-память L1
0.5ns
1.3s
Кэш L2
64-байтовый блок
Встроенная кэш-память L2
7ns
18.2s
Кэш L3
64-байтовый блок
Кэш L3 на чипе
35ns
91s
ОЗУ
страницы 4 КБ
основная память
100ns
4 минуты
твердотельный накопитель SSD
сектор диска
дисковый контроллер
150us
4,5 дня
Сетевой диск (локальное монтирование NFS)
часть файла
Локальный диск
1.5ms
полтора месяца
Узкое место между процессором и памятью называетсяУзкое место фон Неймана, между ними разница в скорости как минимум в несколько сотен раз, которую можно представить как небо и землю, сутки на небе и год на земле. Обычные данные чтения диска еще медленнее, время адресации составляет 10 мс, по сравнению с базовым временем работы процессора 10 месяцев, вы можете иметь ребенка один раз! такУстройства ввода-вывода являются узким местом в компьютерных системах. Учитывая это, запросы API в нашей сети составляют более 100 миллисекунд на каждом шагу, а базовая единица по сравнению с процессором составляет более десяти лет!
Я полагаю, что благодаря приведенному выше описанию у читателя сложится глубокое впечатление о скорости обработки данных между компьютерными компонентами.
1.2 Принцип локальности
Хорошо написанная компьютерная программа обычно имеет хорошую локальность. То есть они, как правило, ссылаются на элементы данных, которые находятся рядом с другими элементами данных, на которые недавно ссылались, или на сам элемент данных, на который недавно ссылались. Эта тенденция называется局部性原理(principle of locality), является устойчивой концепцией, которая сильно влияет на дизайн и производительность как аппаратных, так и программных систем.
Локальность обычно принимает две разные формы:时间局部性(temporal locality)и空间局部性(spatial locality).
Временная локализация: место в памяти, на которое ссылаются один раз, вероятно, будет упоминаться много раз в недалеком будущем.
Пространственная локализация: если на ячейку памяти ссылаются один раз, программа, скорее всего, обратится к соседней ячейке памяти в недалеком будущем.
В конструкции механизма базы данных Mysql Innodb учитывается принцип локальности.
Механизм Innodb организует данные в виде страниц. Размер страницы по умолчанию составляет 16 КБ. Страница, на которой хранятся записи пользовательских данных, называется «страницей данных». Для ускорения поиска данных InnoDB использует структуру дерева B+ для хранить данные. Нижний лист Узел хранит «страницу данных», а соответствующая «страница каталога» извлекается из верхнего уровня «страницы данных». Окончательная базовая структура показана на следующем рисунке:
Записи на странице данных хранятся непрерывно.Когда необходимо получить доступ к данным определенной страницы, все данные полной страницы будут загружены в память, то естьДаже если нам нужно получить доступ только к одной записи страницы, нам нужно сначала загрузить данные всей страницы в память.. Это использует «пространственную локальность» принципа локальности. Как только вся страница загружена в память, возможен доступ для чтения и записи,После завершения доступа на чтение и запись пространство памяти, соответствующее странице, не освобождается в спешке, а кэшируется в пуле буферов., чтобы при повторном запросе на доступ к странице в будущем можно было сэкономить накладные расходы дискового ввода-вывода, что использует преимущество «локальности времени» в принципе локальности.
Принцип локальности — очень важный теоретический краеугольный камень в проектировании системного кэша, который будет несколько раз упоминаться ниже.
1.3 Кэш процессора
В этом разделе поговорим оCpu 高速缓存, Кэш процессора является ключевым фактором, влияющим на производительность программы.
1.3.1 Что такое кэш процессора?
Автор прямо цитирует описание Cpu cache в Википедии:
В компьютерной системе кэш ЦП (англ. CPU Cache, именуемый в этой статье кэшем) — это компонент, используемый для сокращения среднего времени, необходимого процессору для доступа к памяти. Это второй нисходящий уровень в пирамиде памяти, уступающий только регистрам ЦП. Его емкость намного меньше памяти, но скорость может быть близка к частоте процессора.
Когда процессор выдает запрос на доступ к памяти, он сначала проверяет, есть ли данные запроса в кэше. Если он есть (попадание), то данные возвращаются напрямую, без обращения к памяти, если нет (сбой), то соответствующие данные в памяти должны быть сначала загружены в кэш, а затем возвращены в процессор.
Причина, по которой кеш эффективен, заключается главным образом в том, что доступ к памяти во время работы программы характеризуется локальностью. Эта локальность включает в себя как пространственную локальность (Spatial Locality), так и временную локальность (Temporal Locality). Используя преимущество этой локализации, кеши могут достигать чрезвычайно высоких показателей попадания.
С точки зрения процессора кэш является прозрачным компонентом. Поэтому программисты обычно не могут напрямую вмешиваться в работу кэша. Однако можно реализовать определенные оптимизации программного кода на основе характеристик кеша, чтобы лучше использовать кеш.
1.3.2 Зачем мне нужен кэш процессора?
Выше мы упомянули узкое место фон Неймана. С совершенствованием технологий частота ЦП в последние десятилетия постоянно увеличивалась, и из-за ограничений производственного процесса и стоимости в настоящее время нет качественного прорыва в скорости доступа к компьютерной памяти. Таким образом, разрыв между скоростью обработки ЦП и скоростью доступа к памяти становится все больше и больше, в этом случае традиционный способ прямого подключения ЦП к памяти, очевидно, приведет к большому количеству простаивающих вычислительных ресурсов из-за к ожиданию доступа к памяти, снижая общую пропускную способность ЦП. В то же время из-за точечной концентрации доступа к данным в памяти очень рентабельно использовать относительно быстрый и дорогостоящий (относительно памяти) носитель в качестве слоя кэша между ЦП и памятью.
1.3.3 Архитектура кэш-памяти ЦП
Ранние компьютерные системы имели только три уровня иерархии памяти: регистры ЦП, основную память DRAM и дисковое хранилище. Из-за растущего разрыва между ЦП и основной памятью системные разработчики были вынуждены вставить небольшую кэш-память SRAM между регистровым файлом ЦП и основной памятью, называемуюL1高速缓存(一级缓存),Как показано ниже. Скорость доступа к кэшу L1 почти такая же, как и к регистру.
Поскольку разрыв в производительности между процессором и основной памятью продолжал расти, разработчики системы вставили больший кэш между кешем L1 и основной памятью, называемыйL2高速缓存, к нему можно получить доступ примерно за 10 тактов. Современные операционные системы также включают кэш большего размера, который называетсяL3高速缓存, в иерархии памяти он расположен между кэшем L2 и основной памятью и может быть доступен примерно за 50 циклов. Следующая диаграмма представляет собой простую архитектуру кэша:
Данные считываются и сохраняются через кеш, а ядро ЦП и кеш имеют специальный быстрый канал, основная память и кеш подключены к системной шине (BUS), которая также используется для связи других компонентов.
1.3.4 Дизайн массива PHP7
Что касается применения кеша ЦП, то конструкция массива PHP7 — очень классический случай. Массивы являются наиболее часто используемым типом данных в PHP, и повышение производительности массивов улучшит общую производительность программы. Давайте изучим PHP, сравнив структуру массивов PHP7 и PHP5.
Какие соображения были учтены разработчиками для повышения производительности массивов PHP?
Давайте сначала суммируем характеристики массивов PHP:
Массив в php представляет собой словарь dict, в котором хранятся пары ключ-значение, значение можно быстро найти через ключ, где ключ может быть целым числом или строкой (хэш-массив и упакованный массив).
Массивы упорядочены: порядок вставки, порядок обхода.
Массивы в PHP реализованы с помощью hashTable.Давайте сначала разберемся, что такое hashTable.
HashTable — это структура данных, которая с помощью определенной хеш-функции сопоставляет конкретный ключ с конкретным значением, поддерживает однозначное соответствие между ключами и значениями и может быстро найти значение по ключу (o(1)) Схематическая диаграмма общей HashTable выглядит следующим образом:
Чтобы реализовать порядок вставки и порядок обхода массива, PHP5 использует hashTable + двойной связанный список для реализации массива.На следующем рисунке показаны ключи как: «a», «b», «c», «d», и значение "1", "2", "3", "4" Эффект после вставки в массив:
На приведенном выше рисунке сегменты, в которых расположены b, c и d, хранятся и распределяются по одному и тому же слоту.Чтобы решить конфликт хэшей, несколько сегментов в слоте связаны через двусвязный список, который называетсялокальный двусвязный список; Для достижения порядка слоты также связаны через двусвязный список, называемыйГлобальный двусвязный список.
Разобравшись с принципом реализации массива php5, мы обнаружили два ключевых момента, влияющих на производительность:
Частые выделения памяти! Каждый раз, когда вы добавляете элемент в массив, вам нужно выделить память размером с ведро, а затем поддерживать несколько указателей. Хотя PHP основан на управлении пулом памяти (предварительно применяя большие блоки памяти для выделения по требованию), нельзя игнорировать потерю производительности, вызванную выделением памяти.
Частота попаданий в кэш процессора низкая! Поскольку корзины связаны указателями связанных списков, корзины выделяются случайным образом, а память в основном прерывистая, что уменьшает кеш процессора и не может повысить производительность обхода массива.
В ответ на два вышеупомянутых момента php7 изменил дизайн hashTable. Поскольку это словарь, hashTable по-прежнему используется, но реализация массива php7 удаляет слот,Распределение сегментов использует непрерывную память; Сегменты больше не поддерживаются с помощью реальных указателей, сегменты поддерживают только индекс в массиве, а сегменты связаны с сегментами через адреса памяти, как показано на следующем рисунке:
Как разрешить конфликты хэшей в массивах в PHP7?
PHP7 преобразовал zval, в zval есть объединение u2, которое занимает 4 байта и хранит некоторую вспомогательную информацию. Значения в массиве PHP7 также являются указателями zval один за другим.Когда возникает конфликт хэшей, следующий указатель, хранящийся в части u2 zval, сохраняет индекс, указывающий на следующий массив ведра.Через такой логически связанный список, конфликт хэша искусно разрешен. Что касается дизайна zval в PHP7, рекомендуется прочитать статью Brother Bird:Глубокое понимание zval ядра PHP7
можно увидеть,Наиболее важным изменением в улучшении производительности hashTable в php7 является то, что выделение сегментов использует непрерывную память.. Это не только экономит частые накладные расходы на выделение памяти при вставке элементов массива; для обхода массива требуется доступ только к одной корзине к одной корзине, частота попаданий в кэш ЦП очень высока, что значительно повышает производительность массива; это соответствует принципу местность .
Приведите пример применения многоуровневого кеширования: влияние браузеров на нашу жизнь очевидно, современные браузеры отличаются от прошлых, быстрая загрузка информации, плавное взаимодействие с пользователем, все благодаря сетевым технологиям. фактор, который является стратегией кэширования браузера. В этом разделе мы кратко представим механизм многоуровневого кэширования браузера.
Для запроса данных его можно разделить на три этапа: инициирование сетевого запроса, внутренняя обработка и ответ браузера. Кэширование браузера может помочь нам оптимизировать производительность на первом и третьем шагах. Например, если кеш используется напрямую без инициирования запроса или если запрос инициирован, но данные, хранящиеся в бэкэнде, согласуются с внешним интерфейсом, нет необходимости отправлять данные обратно, что уменьшает данные ответа.
Браузеры имеют четыре уровня кэша, каждый из которых имеет приоритет.
Service Worker
Memory Cache
Disk Cache
Push Cache
При поиске кеша по очереди и попадания нет, будет запрошена сеть.
1.4.1 Service Worker
Service Worker — это независимый поток, работающий за браузером, и обычно его можно использовать для реализации функций кэширования. При использовании Service Worker транспортным протоколом должен быть HTTPS. Поскольку в Service Worker задействован перехват запросов, для обеспечения безопасности необходимо использовать протокол HTTPS.Кэш Service Worker отличается от других встроенных механизмов кеширования в браузерах, он позволяет нам свободно контролировать, какие файлы кешируются, как сопоставлять кеш, как читать кеш, и кеш является постоянным..
Service Worker реализует функцию кэширования в три шага: сначала вам нужно зарегистрировать Service Worker, а затем вы можете кэшировать необходимые файлы после прослушивания события установки, а затем при следующем доступе пользователя вы можете запросить, существует ли кеш путем перехвата запроса. , если кеш есть, то можно напрямую прочитать файл кеша, иначе он будет запрашивать данные.
Когда сервис-воркер не попадает в кеш, нам нужно вызвать функцию выборки, чтобы получить данные. То есть, если мы не попадем в кеш в сервис-воркере, данные будут искаться в соответствии с приоритетом поиска в кеше. Но получаем ли мы данные из Memory Cache или из сетевого запроса, браузер покажет, что мы получили их от Service Worker.
1.4.2 Memory Cache
Кэш памяти — это кеш в памяти, который в основном содержит ресурсы, захваченные на текущей странице, такие как стили, скрипты, изображения и т. д., которые были загружены на страницу. Чтение данных в памяти определенно быстрее, чем с диска.Хотя кеш памяти эффективен при чтении, сохраняемость кеша очень короткая и будет освобождаться по мере освобождения процесса. Как только мы закрываем вкладку, кэш в памяти освобождается.
Когда мы посещаем страницу и снова обновляем страницу, мы можем обнаружить, что много данных поступает из кеша памяти.
Важным ресурсом кеша в кеше памяти является ресурс, загружаемый с помощью инструкций, связанных с предварительным загрузчиком (например, ). Как мы все знаем, соответствующие инструкции прелоадера уже являются одним из распространенных средств оптимизации страницы, он может разобрать файл js/css и запросить следующий ресурс из сети.
Следует отметить, что кэшу памяти все равно, какое значение HTTP-заголовка кэша Cache-Control возвращаемого ресурса при кэшировании ресурсов, при этом сопоставление ресурсов происходит не только для сопоставления URL, но и для Content-Type, CORS. Проверьте другие функции.
Почему не все данные браузера хранятся в памяти??
Даже если я не отвечу на этот вопрос, читатели должны понимать, что объем памяти в компьютере должен быть намного меньше емкости жесткого диска, а операционной системе необходимо тщательно рассчитывать использование памяти, поэтому памяти должно быть не так уж много. могут быть использованы нами. Google Chrome известен своей выдающейся производительностью, но он также занимает много памяти.
1.4.3 Disk Cache
Кэш диска - это кеш, хранящийся на жестком диске. Скорость чтения ниже, но все может храниться на диске. По сравнению с кешем памяти он лучше по емкости и своевременности хранения.
Среди всех кешей браузера охват Disk Cache в основном самый большой. Он будет судить, какие ресурсы необходимо кэшировать в соответствии с полями в HTTP Herder, какие ресурсы можно использовать напрямую без запроса, а какие ресурсы просрочены и требуют повторного запроса. И даже в случае кросс-сайта, как только ресурс с тем же адресом будет закэширован жёстким диском, он больше не будет запрашивать данные. Большая часть кеша поступает из Disk Cache.
Какие файлы браузер закидывает в память? которые закидываются на жесткий диск?
На этот счет в Интернете есть разные мнения, но некоторые мнения более достоверны: для больших файлов велика вероятность того, что они не будут храниться в памяти, а при высоком текущем использовании системной памяти файлы будут предпочтительно хранить на жестком диске.
1.4.4 Push Cache
Push Cache (push cache) — это контент в HTTP/2, он будет использоваться, когда ни один из трех вышеуказанных кешей не сработает. Он существует только в сеансе (Session) и освобождается после завершения сеанса, а время кэширования также очень короткое, всего около 5 минут в браузере Chrome, и он строго не реализует инструкции кэширования в заголовке HTTP.
В Push Cache в Китае очень мало информации, в том числе и потому, что HTTP/2 недостаточно популярен в Китае. Рекомендуется прочитать Джейка Арчибальда.HTTP/2 push is tougher than I thoughtЭта статья, несколько выводов в статье:
Все ресурсы могут быть загружены и кэшированы, но поддержка браузеров Edge и Safari относительно плохая.
Ресурсы без кеша и без хранилища могут быть отправлены
Как только соединение закрыто, Push Cache освобождается
Несколько страниц могут использовать одно и то же соединение HTTP/2, что означает, что они могут использовать один и тот же Push-кэш. В основном это зависит от реализации браузера.По соображениям производительности некоторые браузеры используют одно и то же HTTP-соединение для одного и того же доменного имени, но с разными вкладками.
Кэш в Push Cache можно использовать только один раз
Браузеры могут отказаться принимать push-уведомления ресурсов, которые уже существуют.
Вы можете передавать ресурсы в другие домены
Если ни один из четырех вышеперечисленных кэшей не попал, то можно делать только запросы на получение ресурсов.
Здесь представлен механизм многоуровневого кеша браузера Как видите, идея реализации механизма многоуровневого кеша браузера соответствует знанию многоуровневого кеша компьютерной системы, о котором мы упоминали ранее. , а также удовлетворяет местным требованиям половой принцип. Кэширование браузера содержит больше информации, которая заслуживает нашего углубленного изучения.Заинтересованные читатели могут изучить эту статью:Глубокое понимание механизма кэширования браузера
2. Стратегия ликвидации кеша
Согласно модели иерархии памяти пирамиды мы знаем:Чем выше скорость доступа процессора, тем меньше емкость хранилища.. В бизнес-сценариях наиболее часто используемыми компонентами хранилища являются память и диск. Мы часто кэшируем часто используемые данные в памяти, чтобы ускорить чтение данных. Дизайн Redis как базы данных кэша памяти также основан на этом соображении. Однако память сервера ограничена, и невозможно постоянно хранить данные в памяти, не уничтожая их. Кроме того, чрезмерное использование памяти также повлияет на другие задачи сервера, поэтому нам нужно использовать алгоритм устранения, чтобы максимизировать значение кэшированных данных в памяти.
В этом разделе будут представлены три наиболее часто используемых алгоритма устранения кеша в бизнесе:
Наименее недавно использованные (LRU) удаляют страницы, которые не использовались в течение длительного времени, используя время в качестве эталона.
Наименее часто используемые (LFU) исключают страницы с наименьшим количеством посещений за определенный период, используя количество посещений в качестве эталона.
Алгоритм «первым пришел — первым вышел» (FIFO).
Автор объединит конкретный механизм реализации устранения кеша в Redis и Mysql, чтобы помочь читателям узнать, как разработчики Mysql и Redis объединили свои соответствующие бизнес-сценарии для улучшения существующих алгоритмов кеша для удовлетворения потребностей бизнеса.
2.1 Наименее недавно использовавшиеся (LRU)
LRU — аббревиатура наименее недавно использованных, Этот алгоритм считает недавно использованные данные популярными данными и будет использоваться снова в следующий раз с высокой вероятностью. А данные, которые редко использовались в последнее время, с большой вероятностью не будут использованы в следующий раз. Эта идея очень подходит для бизнес-сценариев и может решить многие проблемы в реальной разработке, поэтому мы часто используем для кэширования идею LRU, которую обычно называют механизмом LRU-кэширования.
2.1.1 Реализация алгоритма удаления кэша LRU
В этом разделе автор берет в качестве примера проблему алгоритма на leetcode и использует код (язык Go) для реализации алгоритма LRU, чтобы помочь читателям глубже понять идею алгоритма LRU.
Разработайте и внедрите механизм кэширования LRU (наименее недавно использовавшийся) с использованием имеющихся у вас структур данных. Он должен поддерживать следующие операции: получить данные, получить и записать данные, положить.
Получить данные get(key) — Получить значение ключа (всегда положительное число), если ключ (ключ) существует в кеше, иначе вернуть -1.
Записать данные put(ключ, значение) - если ключ уже существует, изменить его значение данных; если ключ не существует, вставить набор "ключ/значение данных". Когда емкость кэша достигает верхнего предела, он должен удалить самые старые неиспользуемые значения данных перед записью новых данных, чтобы освободить место для новых значений данных.
Мы используем hashmap + двусвязный список для реализации. Операции размещения и получения могут выполняться за время O(1), а также поддерживать удаление первого добавленного узла за O(1).
Одним из преимуществ использования двусвязного списка является то, что для удаления узла не требуется никакой дополнительной информации, а узлы могут быть вставлены и удалены из головы или хвоста за постоянное время.
Одно предостережение заключается в том, что в реализации двусвязного списка псевдо-голова и псевдо-хвост используются для обозначения границ, так что нет необходимости проверять нулевые узлы при обновлении.
код показывает, как показано ниже:
type LinkNode struct {
key, val int
pre, next *LinkNode
}
type LRUCache struct {
m map[int]*LinkNode
cap int
head, tail *LinkNode
}
func Constructor(capacity int) LRUCache {
head := &LinkNode{0, 0, nil, nil}
tail := &LinkNode{0, 0, nil, nil}
head.next = tail
tail.pre = head
return LRUCache{make(map[int]*LinkNode), capacity, head, tail}
}
Это инициализирует базовую структуру данных, что-то вроде этого:
Затем мы добавляем некоторые необходимые методы работы для узла Node для выполнения следующих операций Get и Put:
Теперь начинаем доделывать Put. При реализации Put необходимо учитывать два случая.
Если элемент существует, это фактически эквивалентно выполнению операции Get, и он также перемещается на передний план (но следует отметить, что существует дополнительный шаг для обновления значения).
Если элемент не существует, мы вставляем его в начало элемента и помещаем значение элемента в карту. Если в это время элементы в кэше заполнены, необходимо удалить последний элемент.
После обработки прикрепите полный код функции Put.
func (this *LRUCache) Put(key int, value int) {
tail := this.tail
cache := this.m
if v, exist := cache[key]; exist {
v.val = value
this.MoveToHead(v)
} else {
v := &LinkNode{key, value, nil, nil}
if len(cache) == this.cap {
delete(cache, tail.pre.key)
this.RemoveNode(tail.pre)
}
this.AddNode(v)
cache[key] = v
}
}
На данный момент мы завершили алгоритм LRU с приложенным полным кодом:
type LinkNode struct {
key, val int
pre, next *LinkNode
}
type LRUCache struct {
m map[int]*LinkNode
cap int
head, tail *LinkNode
}
func Constructor(capacity int) LRUCache {
head := &LinkNode{0, 0, nil, nil}
tail := &LinkNode{0, 0, nil, nil}
head.next = tail
tail.pre = head
return LRUCache{make(map[int]*LinkNode), capacity, head, tail}
}
func (this *LRUCache) Get(key int) int {
cache := this.m
if v, exist := cache[key]; exist {
this.MoveToHead(v)
return v.val
} else {
return -1
}
}
func (this *LRUCache) RemoveNode(node *LinkNode) {
node.pre.next = node.next
node.next.pre = node.pre
}
func (this *LRUCache) AddNode(node *LinkNode) {
head := this.head
node.next = head.next
head.next.pre = node
node.pre = head
head.next = node
}
func (this *LRUCache) MoveToHead(node *LinkNode) {
this.RemoveNode(node)
this.AddNode(node)
}
func (this *LRUCache) Put(key int, value int) {
tail := this.tail
cache := this.m
if v, exist := cache[key]; exist {
v.val = value
this.MoveToHead(v)
} else {
v := &LinkNode{key, value, nil, nil}
if len(cache) == this.cap {
delete(cache, tail.pre.key)
this.RemoveNode(tail.pre)
}
this.AddNode(v)
cache[key] = v
}
}
2.1.2 Алгоритм LRU пула буферов Mysql
В бизнес-сценарии, использующем Mysql, возникнет проблема, если описанный выше алгоритм LRU будет использоваться для устранения стратегии. Например, выполните следующую инструкцию запроса:
select * from table_a;
Если в table_a много данных и они не будут использоваться после чтения, заголовок LRU будет занят большим объемом данных в table_a, что приведет к вытеснению горячих данных из кеша и вызовет много дискового ИО. такПул буферов Mysql использует вариант алгоритма наименее использовавшегося (LRU), который управляет пулом буферов как списком..
Буферный пул Mysql
Пул буферов — это область основного буфера, используемая для кэширования индексов, данных строк, адаптивных хэш-индексов, буферов вставки, блокировок и других внутренних структур данных. Размер буферного пула может быть изменен в соответствии с нашими реальными потребностями, поэтому каков подходящий размер буферного пула?Он представлен на официальном сайте MySQL.На выделенном сервере (то есть на сервере размещается только один экземпляр MySQL). ), 80% физической памяти отдается буферному пулу. Буферный пул позволяет считывать часто используемые данные прямо из памяти для обработки, что значительно ускорит работу. Для повышения эффективности операций массового чтения буферный пул разделен на страницы, которые могут содержать несколько строк. Для повышения эффективности управления кешем Buffer Pool реализован в виде связанного списка страниц, соответствующих страницам.
Структура буферного пула базы данных Mysql:
Когда требуется место для кэширования новых страниц в пуле буферов, освобождается последняя использованная страница, а новая страница добавляется в середину списка. Эта стратегия вставки средней точки делит список на два подсписка:
Заголовок представляет собой подсписок новых страниц, которые были недавно посещены.
Хвост — это подсписок старых страниц, которые посещались реже.
Алгоритм сохранит большое количество страниц в новом подсписке (то есть в начале структурного графа), которые используются запросом. Менее используемые страницы в старом подсписке являются кандидатами на освобождение.
Важно понимать следующие ключевые моменты:
3/8 буферного пула отведено под старый подсписок (то есть 3/8 используется для хранения старых страниц, остальное используется для хранения горячих данных, а та часть, которая хранит горячие данные, относительно велика. Конечно, это значение можно настроить самостоятельно, через innodb_old_blocks_pct, значение по умолчанию 37, что составляет 3/8*100, верхний предел 100, и его можно регулировать от 5 до 95. Можно сделать меньше, но после настройки , постарайтесь сделать так, чтобы данные в пределах этого соотношения, то есть данные в старом подсписке, были только на чтение.Однажды, если вы не понимаете саму нагрузку бизнес-данными, рекомендуется не модифицировать ее.)
Середина списка — это граница, где хвост нового подсписка встречается с головой старого подсписка.
Когда InnoDB считывает страницу в пул буферов, она сначала вставляет ее в среднюю точку (заголовок старого подсписка). Страница читается, потому что она требуется для указанной пользователем операции (например, SQL-запроса) или как часть операции упреждающего чтения, автоматически выполняемой InnoDB.
Посетите страницы в старом подсписке, чтобы сделать его «моложе», переместите его в начало пула буферов (в начало нового подсписка). Если страница читается по мере необходимости (SQL), она немедленно обращается к старому списку и перемещает страницу в начало нового списка. При предварительной выборке страницы, которую нужно прочитать, первого обращения к старому списку не происходит.
По мере работы базы данных страницы буферного пула, к которым нет доступа, перемещаются в конец списка. Страницы в старом и новом подсписках устаревают по мере изменения других страниц. Страницы в старом подсписке также устаревают с средней точкой вставки страницы. В конце концов, неиспользуемые страницы достигают хвоста старого подсписка и освобождаются. По умолчанию страницы, прочитанные запросом, будут немедленно перемещены в новый список, существующий в пуле буферов в течение более длительных периодов времени.
Благодаря усовершенствованию алгоритма LRU механизм InnoDB решает проблему, заключающуюся в том, что при большом объеме данных запроса горячие данные удаляются из кэша, что приводит к большому объему операций ввода-вывода на диске..
2.1.3 Примерная реализация LRU в Redis
Поскольку реальный LRU требует слишком много памяти (когда объем данных относительно велик), а Redis известен своей высокой производительностью, настоящий LRU должен вносить соответствующие корректировки каждый раз при доступе к данным, что неизбежно влияет на производительность Redis; это неприемлемо для разработчиков Redis, поэтому Redis использует метод случайной выборки для достижения приблизительного эффекта LRU.
В Redis есть параметр maxmemory-samples, для чего он используется?
1 # LRU and minimal TTL algorithms are not precise algorithms but approximated
2 # algorithms (in order to save memory), so you can tune it for speed or
3 # accuracy. For default Redis will check five keys and pick the one that was
4 # used less recently, you can change the sample size using the following
5 # configuration directive.
6 #
7 # The default of 5 produces good enough results. 10 Approximates very closely
8 # true LRU but costs a bit more CPU. 3 is very fast but not very accurate.
9 #
10 maxmemory-samples 5
Как мы сказали выше, приблизительный LRU использует случайную выборку для достижения приблизительного эффекта LRU. Этот параметр на самом деле является способом, предоставленным автором, который позволяет нам вручную вмешиваться в размер выборки.Чем больше параметр, тем ближе он к эффекту реального LRU, что, конечно, означает большее потребление памяти. (Начальное значение 5 является оптимальным для автора по умолчанию)
Верхний левый рисунок показывает идеальный алгоритм LRU, и ни новые добавленные ключи, ни недавно использованные ключи не должны быть вытеснены. Видно, что в Redis2.8, когда каждый раз случайным образом выбираются 5 ключей, вновь добавленный ключ и ключ, к которому недавно обращались, имеют определенную вероятность быть вытесненными; Redis3.0 имеет лучший эффект после добавления пула (рисунок в правом нижнем углу). Когда Redis 3.0 увеличивает пул и увеличивает количество ключей выборки до 10, это в основном эквивалентно идеальному LRU (хотя все еще есть небольшой разрыв).
Реализация кода LRU в Redis также относительно проста. Redis поддерживает 24-битные часы, которые можно просто понимать как отметку времени текущей системы, и эти часы обновляются через регулярные промежутки времени. Каждый ключевой объект также поддерживает 24-битные часы.При добавлении нового ключевого объекта системные часы будут назначены этим внутренним часам объекта. Например, если я хочу выполнить LRU сейчас, то я сначала получаю текущие глобальные часы, а затем нахожу тот, у которого самое большое расстояние между внутренними часами и глобальными часами (наибольшая разница) и устраняю его. тут что глобальные часы имеют только 24 бита, а вторая единица может храниться 194 дня, поэтому может случиться так что часы ключа больше чем глобальные часы.Если это произойдет то прибавьте двойку вместо вычитая их, чтобы найти самый длинный ключ.
в заключении:LRU в Redis — это не то же самое, что обычная реализация LRU.Обычный LRU будет точно отсеивать элементы в начале очереди, но Redis LRU не поддерживает очередь, а только случайным образом выбирает N(N) из всех ключей в соответствии с настроенной стратегией. Можно настроить), или выберите N ключей из всех ключей с установленным сроком действия, а затем выберите самый длинный неиспользуемый ключ из этих N ключей, чтобы исключить.
2.2 Least Frequently Used(LFU)
Алгоритм LFU (наименее часто используемый) исключает данные на основе их исторической частоты доступа. Его основная идея заключается в том, что «если к данным обращались много раз в прошлом, к ним будут обращаться чаще в будущем». Каждый блок данных LFU имеет счетчик ссылок, все блоки данных сортируются по счетчику ссылок, а блоки данных с одинаковым счетчиком ссылок сортируются по времени. LFU необходимо записывать записи доступа ко всем данным, а потребление памяти высокое, ее нужно сортировать на основе счетчика ссылок, а потребление производительности высокое. С точки зрения сложности реализации алгоритма LFU намного больше, чем LRU.
2.2.1 Реализация алгоритма удаления кэша LFU
В этом разделе автор берет в качестве примера проблему алгоритма на leetcode и использует код для реализации алгоритма LFU, чтобы помочь читателям глубже понять идею алгоритма LFU.
Разработайте и внедрите структуры данных для алгоритма кэширования наименее часто используемых (LFU). Он должен поддерживать следующие операции: получить и положить.
get(key) — если ключ существует в кеше, получить значение ключа (всегда положительное число), в противном случае вернуть -1.
put(key, value) — если ключ уже существует, измените его значение; если ключ не существует, вставьте пару ключ-значение. Когда кеш достигает своей емкости, наименее часто используемые элементы должны быть признаны недействительными, прежде чем будут вставлены новые. В этой задаче, когда есть ничья (т. е. два или более ключа имеют одинаковую частоту использования), следует удалить самый старый неиспользуемый ключ.
«Использование элемента» — это сумма количества вызовов функций get и put для элемента с момента его вставки. Количество использований будет установлено на 0 после удаления соответствующего предмета.
Пример:
В предыдущем разделе мы говорили об алгоритме LRU.Реализация LRU представляет собой хеш-таблицу плюс двусвязный список, что относительно просто. LFU намного сложнее: для достижения результата требуются две хеш-таблицы плюс N списков с двойной связью.
Давайте сначала посмотрим, что хранится в двух хеш-таблицах LFU.
Первая хеш-таблица — это хэш-таблица «ключ-значение» (далее — хэш-таблица kv).
Ключ здесь — клавиша ввода, ничего особенного. Ключ — это значение, его значение — не простое значение, а объект-узел.
Объект узла Node содержит ключ, значение и частоту, и этот узел появится в значении второй хеш-таблицы.
Насчет того, почему ключ повторно включается в Ноду, потому что в некоторых случаях мы получаем Ноду не через хэш-таблицу kv, а получаем Ноду другими методами, и тогда нам нужно использовать ключ в Ноде для перехода к хеш-таблице kv для выполнения некоторых операций, поэтому Node содержит некоторую избыточную информацию.
Вторая хеш-таблица, частотная хэш-таблица, намного сложнее.
Ключом в этой хеш-таблице является частота, то есть частота обращения к элементу (однократное обращение, двукратное обращение и т. д.), а его значением является двусвязный список
Объект Node, о котором я только что упоминал, появляется снова, Здесь Node на самом деле является узлом в двусвязном списке.
На первом рисунке мы представили, что Node содержит избыточный ключ.На самом деле, он также содержит избыточное значение частоты, потому что в некоторых случаях нам нужно передать значение частоты в узле в хэш-таблицу частот для поиска, поэтому также требуется избыточное значение частоты.
Давайте объединим две хеш-таблицы, чтобы увидеть полную структуру:
В хеш-таблице k-v ключ1 указывает на узел, а частота этого узла равна 1, который расположен в двусвязном списке ниже ключа=1 в хеш-таблице частот (на первом узле).
В соответствии с приведенным выше описанием мы можем определить основной код операции со структурой данных и двусвязным списком, который мы хотим использовать (используя язык Go):
Давайте взглянем на конкретную реализацию алгоритма LFU.Операция получения относительно проста.Давайте сначала поговорим об операции получения.
Конкретная логика операции get примерно следующая:
Возвращает -1, если ключ не существует
Если ключ существует, возвращается соответствующее значение, и в то же время:
Увеличить частоту обращения к элементу на +1
Удалить элемент из связанного списка частоты доступа i и поместить его в связанный список частоты i+1
Если связанный список частоты i пуст, удалите этот связанный список из хэш-таблицы частот.
Первый очень простой и, разумеется, давайте посмотрим на процесс выполнения второго пункта:
Если предположить, что частота обращения к элементу равна 3, и теперь к нему снова обращаются, то этот элемент нужно переместить в связанный список частоты 4. Если после удаления этого элемента связанный список частоты 3 станет пустым (остаются только головной узел и хвостовой узел), необходимо удалить связанный список и удалить соответствующую частоту (то есть удалить ключ=3), давайте посмотрим Процесс реализации:
Кодовая реализация метода Get в LFU:
func (this *LFUCache) Get(key int) int {
if node, ok := this.cache[key]; ok {
this.IncrFreq(node)
return node.val
}
return -1
}
func(this *LFUCache) IncrFreq(node *Node) {
_freq := node.freq
this.freq[_freq].RemoveNode(node)
if this.minFreq == _freq && this.freq[_freq].IsEmpty() {
this.minFreq++
delete(this.freq, _freq)
}
node.freq++
if this.freq[node.freq] == nil {
this.freq[node.freq] = createDL()
}
this.freq[node.freq].AddFirst(node)
}
Операция put намного сложнее, примерно включая следующие ситуации
Если ключ уже существует, измените соответствующее значение и увеличьте частоту доступа на 1.
Удалить элемент из связанного списка частоты доступа i и поместить его в связанный список частоты i+1
Если связанный список частоты i пуст, удалите этот связанный список из хэш-таблицы частот.
если ключ не существует
Если кэш превышает максимальную емкость, сначала удаляется элемент с наименьшей частотой обращения, а затем вставляется новый элемент.
Частота обращения новых элементов равна 1. Если соответствующий связанный список отсутствует в хеш-таблице частот, его необходимо создать
Если кэш не превышает максимальной емкости, вставьте новый элемент
Частота обращения новых элементов равна 1. Если в частотной хеш-таблице нет соответствующего связанного списка, его необходимо создать
Нам также необходимо поддерживать переменную minFreq в реализации кода для записи наименее часто встречающегося элемента в кэше LFU.Когда кеш заполнен, мы можем быстро найти наименее часто встречающийся связанный список для достижения временной сложности O(1).Удалить один элемент .
Конкретный метод:
При обновлении/поиске частота элемента равна +1, и если minFreq отсутствует в хеш-таблице частот, значит, в хеш-таблице частот нет элементов, то minFreq должен быть +1, иначе minFreq остается без изменений.
При вставке это просто, потому что частота новых элементов равна 1, поэтому просто измените minFreq на 1.
Давайте сосредоточимся на том, что происходит, когда кеш превышает максимальную емкость:
Реализация кода метода Put в LFU:
func (this *LFUCache) Put(key int, value int) {
if this.ncap == 0 {
return
}
//节点存在
if node, ok := this.cache[key]; ok {
node.val = value
this.IncrFreq(node)
} else {
if this.size >= this.ncap {
node := this.freq[this.minFreq].RemoveLast()
delete(this.cache, node.key)
this.size--
}
x := &Node{key: key, val: value, freq: 1}
this.cache[key] = x
if this.freq[1] == nil {
this.freq[1] = createDL()
}
this.freq[1].AddFirst(x)
this.minFreq = 1
this.size++
}
}
Я полагаю, что благодаря анализу и реализации базового алгоритма LFU читатели поняли идею и сложность алгоритма LFU. Многие алгоритмы сами по себе сложны не только для интеграции различных структур данных, но и для анализа и постоянного улучшения в соответствии со сценариями применения. Но алгоритмы действительно решают многие практические проблемы.Мы уже знаем о важности кэширования, но в дополнение к полному использованию различных компонентов компьютерной памяти для хорошей стратегии кэширования также важен хороший дизайн алгоритма. Итак, давайте рассмотрим реализацию алгоритма LFU в этом разделе в целом:
В целом, эффективность LFU выше, чем у LRU, и это позволяет избежать проблемы снижения частоты попаданий в кэш, вызванной периодическими или спорадическими операциями., в следующих случаях:
Данные D будут ошибочно приняты за данные, которые, скорее всего, будут доступны в будущем.
Автор Redis хотел улучшить алгоритм LRU, но обнаружил, что алгоритм LRU Redis зависит от числа случайных выборок maxmemory_samples, когда maxmemory_samples равно 10, это очень близко к идеальной производительности алгоритма LRU. , дальше самого алгоритма LRU идти сложно.
Таким образом, возвращаясь к исходной идее, первоначальное намерение алгоритма исключения состоит в том, чтобы сохранить те данные, к которым, скорее всего, будет осуществлен повторный доступ в будущем, в то время как алгоритм LRU только предсказывает, что данные, к которым недавно осуществлялся доступ, с наибольшей вероятностью будут доступны. в будущем. Мы можем изменить свое мышление и использовать алгоритм LFU (Least Frequently Used), то есть наиболее часто используемые данные с наибольшей вероятностью будут доступны в будущем. В приведенном выше случае приоритет резервирования может быть определен в соответствии с ситуацией частого доступа: B>A>C=D.
В алгоритме LFU для каждого ключа может поддерживаться счетчик. При каждом доступе к ключу счетчик увеличивается. Чем больше счетчик, тем чаще к нему можно обращаться.
Есть две проблемы с приведенным выше простым алгоритмом:
В алгоритме LRU можно вести двусвязный список, и тогда посещенный узел можно просто переместить в начало связанного списка, но в LFU это неосуществимо: узлы должны быть отсортированы строго по счетчику. сложность может достигать O(N).
Простое увеличение счетчика не идеально. Шаблон доступа часто меняется. Ключи, к которым часто обращаются в течение определенного периода времени, могут редко использоваться через определенный период времени. Только увеличение счетчика не отражает эту тенденцию.
Первую проблему легко решить: на опыте реализации LRU можно научиться поддерживать пул ключей, подлежащих устранению. Решение второй проблемы состоит в том, чтобы записывать время последнего доступа к ключу, а затем постепенно уменьшать значение счетчика.
Ранее мы говорили о структуре объекта Redis:
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;
В алгоритме LRU для записи времени LRU используется 24-битное поле lru.Это поле также может использоваться в LFU, но для использования оно разделено на 16 бит и 8 бит:
16 bits 8 bits
+----------------+--------+
+ Last decr time | LOG_C |
+----------------+--------+
Старшие 16 бит используются для записи времени ldt последнего уменьшения счетчика в минутах, а младшие 8 бит записывают значение счетчика.
После Redis 4.0 в стратегию исключения maxmemory_policy были добавлены два режима LFU:
volatile-lfu: алгоритм устранения LFU используется для ключей со сроком действия
allkeys-lfu: использовать алгоритм исключения LFU для всех ключей
Также есть 2 конфигурации для настройки алгоритма LFU:
lfu-log-factor 10
lfu-decay-time 1
lfu-log-factor может регулировать скорость роста счетчика.Чем больше lfu-log-factor, тем медленнее растет счетчик.
lfu-decay-time — это значение в минутах, которое регулирует скорость уменьшения счетчика.
реализация исходного кода
В lookupKey:
robj *lookupKey(redisDb *db, robj *key, int flags) {
dictEntry *de = dictFind(db->dict,key->ptr);
if (de) {
robj *val = dictGetVal(de);
/* Update the access time for the ageing algorithm.
* Don't do it if we have a saving child, as this will trigger
* a copy on write madness. */
if (server.rdb_child_pid == -1 &&
server.aof_child_pid == -1 &&
!(flags & LOOKUP_NOTOUCH))
{
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
updateLFU(val);
} else {
val->lru = LRU_CLOCK();
}
}
return val;
} else {
return NULL;
}
}
Когда стратегия LFU принята, updateLFU обновляет lru:
/* Update LFU when an object is accessed.
* Firstly, decrement the counter if the decrement time is reached.
* Then logarithmically increment the counter, and update the access time. */
void updateLFU(robj *val) {
unsigned long counter = LFUDecrAndReturn(val);
counter = LFULogIncr(counter);
val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}
нижний LFUDecrAndReturn
Во-первых, LFUDecrAndReturn уменьшает счетчик:
/* If the object decrement time is reached decrement the LFU counter but
* do not update LFU fields of the object, we update the access time
* and counter in an explicit way when the object is really accessed.
* And we will times halve the counter according to the times of
* elapsed time than server.lfu_decay_time.
* Return the object frequency counter.
*
* This function is used in order to scan the dataset for the best object
* to fit: as we check for the candidate, we incrementally decrement the
* counter of the scanned objects if needed. */
unsigned long LFUDecrAndReturn(robj *o) {
unsigned long ldt = o->lru >> 8;
unsigned long counter = o->lru & 255;
unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
if (num_periods)
counter = (num_periods > counter) ? 0 : counter - num_periods;
return counter;
}
Функция сначала получает самое последнее время уменьшения ldt старших 16 бит и счетчик счетчика младших 8 бит, а затем вычисляет, насколько оно должно уменьшиться в соответствии с настроенным lfu_decay_time.
LFUTimeElapsed используется для вычисления разницы между текущим временем и ldt:
/* Return the current time in minutes, just taking the least significant
* 16 bits. The returned time is suitable to be stored as LDT (last decrement
* time) for the LFU implementation. */
unsigned long LFUGetTimeInMinutes(void) {
return (server.unixtime/60) & 65535;
}
/* Given an object last access time, compute the minimum number of minutes
* that elapsed since the last access. Handle overflow (ldt greater than
* the current 16 bits minutes time) considering the time as wrapping
* exactly once. */
unsigned long LFUTimeElapsed(unsigned long ldt) {
unsigned long now = LFUGetTimeInMinutes();
if (now >= ldt) return now-ldt;
return 65535-ldt+now;
}
В частности, после преобразования текущего времени в минуты возьмите младшие 16 бит, а затем вычислите разницу now-ldt от ldt. Когда ldt > now, по умолчанию используется один цикл (16 бит, максимум 65535), а значение равно 65535-ldt+now.
Затем разделите разницу на настроенное время lfu_decay_time, LFUTimeElapsed(ldt) / server.lfu_decay_time, после того, как пройдет n lfu_decay_times, уменьшите counter на n, counter - num_periods.
Рост LFULogIncr
Функция роста LFULogIncr выглядит следующим образом:
/* Logarithmically increment a counter. The greater is the current counter value
* the less likely is that it gets really implemented. Saturate it at 255. */
uint8_t LFULogIncr(uint8_t counter) {
if (counter == 255) return 255;
double r = (double)rand()/RAND_MAX;
double baseval = counter - LFU_INIT_VAL;
if (baseval < 0) baseval = 0;
double p = 1.0/(baseval*server.lfu_log_factor+1);
if (r < p) counter++;
return counter;
}
Счетчик не просто +1 за одно посещение, но использует p-фактор от 0 до 1 для контроля роста. Максимальное значение счетчика 255. Возьмите случайное число r от 0 до 1 и сравните его с p. Когда r
Видно, что рост счетчика и количества посещений имеет логарифмическую тенденцию роста, по мере увеличения количества посещений рост счетчика становится все медленнее и медленнее.
Ключевая стратегия первокурсника
Другая проблема заключается в том, что при создании нового объекта, если счетчик объекта равен 0, он будет легко устранен.Также необходимо установить начальный счетчик для нового ключа, createObject:
robj *createObject(int type, void *ptr) {
robj *o = zmalloc(sizeof(*o));
o->type = type;
o->encoding = OBJ_ENCODING_RAW;
o->ptr = ptr;
o->refcount = 1;
/* Set the LRU to the current lruclock (minutes resolution), or
* alternatively the LFU counter. */
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
} else {
o->lru = LRU_CLOCK();
}
return o;
}
счетчик будет инициализирован в LFU_INIT_VAL, по умолчанию 5.
в заключении:Стратегия удаления LFU-кэша Redis повторно использует 24-битный lru в объекте Redis, но для использования он делится на 16-битный и 8-битный.Старшие 16 бит используются для записи времени ldt последнего сокращения счетчика в минутах, а записываются младшие 8 бит Значение счетчика counter. Счетчик объекта Redis не растет линейно, а предоставляет элемент конфигурации lfu-log-factor для управления скоростью роста технологии. Чтобы решить проблему «загрязнения кеша», когда исторические данные влияют на будущие данные, количество объектов Redis будет корректироваться с течением времени в соответствии с элементом конфигурации lfu_decay_time. Redis устанавливает начальный счетчик для каждого вновь добавленного ключа, чтобы предотвратить легкое удаление вновь добавленного ключа..
2.3 Алгоритм «первым пришел — первым вышел» (FIFO)
FIFO (первым пришел, первым вышел), первым пришел, первым ушел. При разработке FIFO Cache основной принцип заключается в следующем: если данные попадают в кэш первыми, они должны быть удалены первыми. Метод реализации очень прост, если можно использовать структуру данных очереди.
Поскольку частота попаданий в кэш относительно невелика, стратегия кэширования FIFO обычно не используется в проектах. Теория объективного идеализма: существование оправдано Ниже автор описывает применение очереди FIFO в процессе репликации Redis master-slave.
В структуре Redis master-slave главный узел должен синхронизировать данные с подчиненными узлами.От начала соединения master-slave до синхронизации данных он делится на три этапа:
На первом этапе сначала устанавливается соединение, а затем на втором этапе мастер-узел отправляет rdb-файл на подчиненный узел для синхронизации всего объема данных, в основном мы видим, что происходит на ведущем узле на третьем Этап заключается в многократной синхронизации инкрементных данных с подчиненным узлом.
Когда подчиненный узел и главный узел устанавливают соединение, сервер главного узла будет поддерживать复制积压缓冲区Для временного хранения команд инкрементной синхронизации; когда ведомый узел запрашивает данные синхронизации у ведущего узла, главный узел синхронизирует добавочные данные с ведомым узлом в соответствии со смещением данных синхронизации ведомого узла и повторяет процесс.
Буфер невыполненной репликации представляет собой циклическую очередь FIFO, используемую для хранения команд, выполняемых сервером.Каждый раз при распространении команды главный узел записывает распространенную команду и сохраняет ее здесь.
Буфер невыполненных копий состоит из двух частей: смещения и значения байта. Значение байта — это хранилище байтов инструкции Redis (инструкции Redis хранятся в формате сериализованного текстового протокола Redis), а смещение смещения — это смещение текущего значения байта в циклической очереди.
Главный узел поддерживает смещение каждого подчиненного узла, так что каждый раз, когда данные синхронизируются, главный узел знает, какую часть данных синхронизировать с подчиненным узлом. Благодаря такому буферу невыполненной репликации архитектура Redis master-slave реализует добавочную синхронизацию данных.Читатели, которые хотят узнать больше о деталях синхронизации master-slave, могут обратиться к другому моему блогу:Высокая доступность Redis — репликация master-slave
2.4 Сравнение стратегий устранения кеша FIFO, LRU и LFU
В этом разделе много места посвящено стратегии устранения кеша. Давайте сравним три стратегии кеша по четырем аспектам: частота попаданий в кеш, сложность реализации, стоимость хранения и дефекты:
Политика удаления кеша
частота попаданий в кэш
сложность реализации
стоимость хранения
дефект
FIFO
Низкий
очень простой
очень низко
Быстро, но мало практической ценности
LRU
высокий
относительно простой
высокий
Случайные и периодические пакетные операции приведут к резкому падению частоты попаданий LRU и серьезному загрязнению кэша.
LFU
очень высоко
относительно сложный
Очень высокий и требует много места для хранения
L имеет «загрязнение кеша», когда исторические данные влияют на будущие данные.
Проекты кеша Redis и Mysql учли идею стратегии устранения кеша, упомянутую в этом разделе, и были улучшены и реализованы в сочетании с их собственными бизнес-сценариями. Не существует идеальной стратегии устранения кеша. Целью этого раздела является выбор подходящего алгоритма устранения кеша в соответствии с конкретным бизнесом и необходимостью улучшить частоту попаданий в кеш.
3. Безопасность кэша
Безопасность кэша является очень актуальной темой.Большинство архитекторов на предприятиях будут учитывать вопросы, связанные с «безопасностью кэша», при проектировании систем кэширования, особенно когда служба достигает определенного уровня, «безопасность кэша» является проблемой, которую необходимо учитывать. Кроме того, в процессе собеседования вопросы, связанные с «безопасностью кеша», также являются горячими темами, потому что слишком важно разбираться в этих вопросах.Что может быть причиной каждого вопроса? Какие есть эффективные решения? Как избежать этих проблем? Это все, что должен знать квалифицированный программист.
В этом разделе, в сочетании с использованием промежуточного программного обеспечения кэша Redis, мы поговорим о наиболее распространенных проблемах в «безопасности кэша». И ввести соответствующие решения и методы предотвращения.
3.1 Прогрев кэша
Как говорится, все начинается с трудностей, и эта проблема также существует для систем, использующих промежуточное ПО кэша Redis.Когда системный параллелизм высок и принята архитектура master-slave, запустить службу очень сложно.! Причина в том, что когда система только запускается, в кеше нет данных, поэтому для запуска службы требуется большой доступ к базе данных, и в одно мгновение генерируется большой объем кэшированных данных. и слейв увеличивается, и частота синхронизации данных увеличивается.Вылетает вскоре после запуска.
Решение тоже очень простое,Нам лучше сначала подсчитать данные точки доступа с высокой частотой доступа, классифицировать данные в соответствии со статистическими результатами и позволить службе кэширования Redis преимущественно загружать данные точки доступа с высокой частотой доступа.. Конечно, этот процесс лучше всего выполнять как «предварительную загрузку». Данные хотспота загружаются до запуска сервиса. Когда ручную схему выполнения сложно реализовать, это можно сделать с помощью скрипта или CDN.
Подводя итог, прогрев кэша заключается в прямой загрузке соответствующих данных кэша в систему кэширования заранее, до запуска системы. Чтобы избежать проблемы с запросом сначала к базе данных, а затем кэшированием данных, когда пользователь запрашивает, позвольте пользователю напрямую запрашивать предварительно нагретые кэшированные данные.
3.2 Лавина кэша
Лавина кеша — часто встречающаяся проблема в службах кеша. Ниже приведен общий процесс аварийного лавинного кеша:
Пока система работает без сбоев, количество подключений к базе данных резко возрастает.
Сервер приложений не может вовремя обработать запрос, и клиент начинает отображать большое количество страниц с ошибками 408 и 500.
Клиент неоднократно обновляет страницу, чтобы попытаться получить данные, что приводит к скачку доступа к базе данных на стороне сервера и сбоям базы данных.
После сбоя базы данных сервер приложений также дает сбой
Попытка перезапустить сервер недействительна.В это время происходит сбой сервера redis, начинает появляться лавина, и кластер redis начинает падать.
Перезапуск базы данных недопустим, так как трафик слишком высок, база данных падает при запуске
Изучив причину вышеуказанной проблемы лавинного кэша, мы придем к следующему выводу:
Основная причина «лавины кеша»: за короткий промежуток времени срок действия большого количества ключей в кеше истек..
Мы можем использовать этот вывод, чтобы объяснить, как происходит описанное выше явление. После одновременного истечения срока действия большого количества ключей в кеше кеш Redis не может попасть в кеш, и запрос достигнет базы данных; если количество параллелизма велико, база данных не может вовремя его обработать, запрос Redis будет будет отставать, и постепенно будет происходить явление тайм-аута; всплеск Redis потерпел крах, и бессмысленно перезапускать сервер в это время, потому что ключевая проблема системы заключается в том, что в кеше нет доступных данных, Redis ресурсы сервера заняты, сервер тоже падает, кластер рушится, а сервер приложений тоже будет следить за крахами клиента по мере увеличения запросов. После возникновения такой ситуации нам бессмысленно перезапускать сервер, редис и базу данных! Ниже приведена простая схема лавины кеша:
Если возникла проблема "лавины кеша", как ее решить? Вот несколько эффективных решений:
Статическая обработка страницы, после использования статической страницы данные клиента не нужно получать из кеша, что может снизить нагрузку на кеш.Недостатком является то, что данные не обновляются вовремя.
Создайте многоуровневый кеш. Создание многоуровневого кеша может обеспечить большую защиту данных для каждого уровня кеша. Например, между базами данных redis и mysql добавляется слой кеша ehcache. При большом количестве ключей в кеше истекает, кеш ehcache может заменить кеш.База данных mysql временно блокирует трафик. Создание многоуровневого кеша увеличивает сложность системы.
Оптимизировать mysql. Например, добавление буферного пула в mysql, чтобы, когда большой объем трафика достигает mysql, пропускная способность mysql могла поддерживать параллелизм, чтобы он не рухнул сразу, а также мог предотвратить возникновение лавин.
Отслеживайте показатели производительности Redis. По анализу мы знаем, что «лавина» сопровождается резким увеличением загрузки ЦП, а также будет увеличиваться среднее время ответа на клиентские запросы, Мониторинг этих показателей производительности может помочь нам обнаружить проблемы раньше.
Ограничение, понижение. Это рассматривается с точки зрения клиента, жертвуя частью клиентского опыта и ограничивая некоторые клиентские запросы, можно эффективно снизить нагрузку на сервер приложений. После того, как система работает бесперебойно, она будет постепенно возобновляться.
Теперь, когда мы знаем, что «лавина кеша» вызвана централизованным истечением срока действия большого количества горячих клавиш за короткий промежуток времени, необходимо изучить некоторые методы предотвращения «лавины кеша».Самый эффективный метод — разбить срок действия кеша в соответствии с бизнес-данными., время истечения данных использует метод фиксированного времени + случайная временная метка, чтобы уменьшить количество ключей с истекшим сроком действия в наборе, и даже для супергорячих данных можно использовать постоянные ключи. Помните стратегию устранения кеша, о которой мы упоминали во второй части?Переключение стратегии устранения LRU на LFU также может эффективно предотвратить «лавину кеша».. Если вы считаете, что проблема по-прежнему непроста для решения, также можно использовать ручное обслуживание.Вы можете регулярно вести статистику по данным доступа, а также можно продлевать время истечения срока аренды данных точки доступа.
Подводя итог: кеш-лавина заключается в том, что объем данных с истекшим сроком действия становится слишком большим в одно мгновение, что оказывает давление на сервер базы данных. Если можно эффективно избежать концентрации времени истечения срока действия, можно эффективно предотвратить возникновение лавинных проблем.При использовании вместе с другими стратегиями, а также при мониторинге текущих данных сервера и своевременной корректировке в принципе можно предотвратить возникновение лавин. «кеш лавина».
3.3 Разбивка кеша
Поняв, что такое лавина кеша, мы могли бы подумать над следующим вопросом: причина лавины кеша в том, что срок действия большого количества горячих клавиш централизованно истекает, не вызовет ли это также и эту проблему, если истечет срок действия супергорячей клавиши?
Ответ - да! Давайте представим такой сценарий, компьютер Mac стоит 99 юаней за событие double 11 seckill.В начале события seckill возникли миллионы запросов в секунду, и кешированные данные истекли.Такое большое количество посещений достигло базы данных, и база данных должна быть недоступна! Это «разбивка кеша», о которой мы поговорим в этом разделе.
Сравнивая «лавину кеша», мы обнаружим, что «пробой кеша» и «лавина кеша» во многих явлениях схожи, и большинство решений «лавины кеша», о которых мы упоминали в предыдущем разделе, здесь.В отличие от «лавины кеша», после «сбоя кеша» память и ЦП Redis не будут работать ненормально, и это не приведет к сбою сервера приложений, что означает, что «сбой кеша» произойдет с меньшей вероятностью. не так серьезны, как "кэш-лавина". А вот в сценарии "seckill" такая проблема есть.
Давайте сначала поговорим о том, как решить и предотвратить проблему «поломки кеша». Вообще говоря, проблему "поломки кеша" можно предвидеть до того, как она возникнет. Например, до и после активности "Seckill" обязательно будет большое количество клиентских запросов. Тогда когда истечет срок действия ключа горячего кеша в системе , загрузите его вручную.На редис конечно можно зайти. Либо во время мероприятия мы можем использовать постоянный ключ и настроить стратегию ликвидации кэша LFU, что также может решить эту проблему. Конечно, есть и другие решения, например, автор ранее проанализировал, как 12306 может выдерживать высокий одновременный трафик, среди них используется метод многоуровневого кэширования локального кэша и кэша Redis, который также эффективен для решения проблемы разбивки кэша. ., до тех пор, пока локальный кеш и кеш в redis не истечет одновременно, большой объем трафика не будет прижиматься к базе данных.
Подытожим: истечение срока действия кеша — это момент, когда срок действия одного высокотемпературного данных истекает, а объем доступа к данным велик, после того, как redis пропущен, трафик достигает базы данных. Стратегия реагирования состоит в том, чтобы сосредоточиться на предотвращении, и ее можно вовремя скорректировать с помощью мониторинга.Основная причина заключается в том, чтобы учитывать эту проблему при проектировании системы кэширования.
3.4 Проникновение в кэш
В этом разделе давайте обсудим "проникновение в кеш". Прежде всего, "проникновение в кеш" и "проникновение в кеш" разные.Хакеры часто используют «проникновение в кэш», чтобы вывести из строя наши серверы..
Давайте посмотрим, что за явление происходит «проникновение в кэш»:Когда система работает плавно, с всплеском трафика, частота попаданий кэша Redis начинает падать, и в памяти нет аномалий, но ЦП начинает всплескивать, и доступ к базе данных также начинает всплескиваться, пока не произойдет сбой базы данных. ..
Существенной причиной для отслеживания проблемы оказалось то, что ключ, к которому обращался клиент, не существует в кеше Redis, а в базе нет связанных данных.В принципе, это все такой ключ, похоже, что кто-то сделал это специально. В этом случае разработчики должны быть бдительны, очень велика вероятность, что происходит хакерская атака!
После обнаружения проблемы, как мы можем решить ее? Первое, о чем думает большинство людей, это то, что, поскольку хакер знает, что в нашем кеше нет ключа, значит, ключ кэшируется в Redis, а значение равно NULL. Если вы так думаете, то это означает лишь то, что вы слишком молоды.Во-первых, хакеры не настолько глупы, чтобы использовать один и тот же ключ для атаки, а потом в памяти redis кэшируется большое количество недействительных ключей, и redis теряет смысл кэширования. Конечно, если вы обнаружите, что все эти запросы поступают с одного и того же IP-адреса или клиента, вы можете временно создать черный список, чтобы не допустить атакующего трафика, но хакеры обычно используют DDos (распределенную атаку типа «отказ в обслуживании»), которая часто неэффективна. .
Столкнувшись с такой дилеммой, наиболее распространенным решением в отрасли является использование «фильтра Блума». Несмотря на то, что существует определенная вероятность неправильной оценки, при разумных настройках параметров проблема может быть эффективно решена.
Что такое фильтр Блума?
Фильтр Блума можно понимать как неверную структуру набора, и когда вы используете его метод contains для определения существования объекта, он может ошибаться. Тем не менее, фильтр Блума не отличается особой точностью, и при разумных настройках параметров его точность может быть гарантирована.Когда фильтр Блума говорит, что значение существует, значение может не существовать, но пока он говорит, что значение не существует, значение определенно не существует.
Как работает фильтр Блума
Каждый фильтр Блума соответствует структуре данных Redis, которая представляет собой большой битовый массив и несколько различных несмещенных хэш-функций (хэш-значение элементов может быть вычислено более равномерно, так что функция отображается по хэшу в битовый массив в битовом массиве). массив). расположение случайное). Если показано, f, g, h являются такими хеш-функциями.
При добавлении ключа в фильтр Блума для хеширования ключа используется несколько хеш-функций. Сначала вычисляется целочисленное значение индекса, а затем выполняется операция по модулю над длиной битового массива для получения позиции. Каждая хеш-функция вычислит другое значение position, а затем установит эти позиции в битовом массиве в 1.
При запросе фильтра Блума, существует ли ключ, как и при добавлении, он также будет вычислять несколько позиций, полученных ключом через хеш, чтобы увидеть, все ли эти позиции в массиве равны 1, если одна позиция равна 0, тогда это значение не существует в фильтре Блума.
Помимо схемы фильтра Блума, автор считает, что необходимо также шифровать ключи в бизнесе, потому что пока ключи в бизнесе обычные, хакеры вообще этого не знают, мы можем по мнению ключ, трафик атаки хакера блокируется перед сервером кеша Redis. Кроме того, мониторинг кешированных данных должен быть выполнен хорошо.Если можно вовремя определить частоту попаданий в кеш, можно будет принять более ранние меры.
Подводя итог: "проникновение в кэш" означает, что клиент получает доступ к данным, которых нет в кэше и базе данных. Большое количество таких обращений приведет к разрушению базы данных. Когда эксплуатационный и обслуживающий персонал отслеживает эту ситуацию, они должны дать своевременное оповещение. Информация эффективно обрабатывается в соответствии с мерами, упомянутыми выше.
3.5 Мониторинг показателей эффективности
В предыдущих разделах, когда мы обсуждали различные опасности, скрытые в кеше, мы неоднократно подчеркивали важность мониторинга. Здесь я беру отдельный раздел, чтобы обобщить, какие показатели производительности мы должны отслеживать и какие команды могут помочь нам проанализировать проблемы в обычных бизнес-сценариях системы кэширования, Эти меры и навыки очень полезны для обеспечения безопасности нашей системы.
Для мониторинга показателей эффективности автор здесь перечисляет пять категорий, которые представлены в виде таблиц.
Показатели производительности: производительность
Name
Description
latency
Время, необходимое Redis для ответа на запрос
instantaneous_ops_per_sec
Среднее общее количество запросов, обрабатываемых в секунду
hit rate(calculated)
Коэффициент попаданий в кэш (расчетный)
Индикатор памяти: Память
Name
Description
use_memory
используемая память
mem_fragmentation_ratio
скорость фрагментации памяти
evicted_keys
Количество ключей, удаленных из-за максимального ограничения памяти
blocked_clients
Клиенты заблокированы из-за BLPOP, BRPOP или BLPUSH, BRPUSH
Индикатор основной деятельности: Основная деятельность
Name
Description
connected_clients
Количество клиентских подключений
connected_slaves
Количество рабов
master_last_io_seconds_ago
Количество секунд с момента последнего взаимодействия ведущий-ведомый
key_space
Общее количество ключевых значений в базе данных
Метрики постоянства: постоянство
Name
Description
rdb_last_save_time
Отметка времени последнего постоянного сохранения в базе данных
rdb_change_since_last_save
Количество изменений в базе данных с момента последней персистентности
Индикатор ошибки: Ошибка
Name
Description
rejected_connections
Количество соединений, отклоненных из-за достижения максимального количества клиентов
keyspace_misses
Сколько раз не удалось найти значение ключа (нет совпадений)
master_link_down_since_seconds
Продолжительность отключения ведущий-ведомый (в секундах)
Выше перечислены наиболее важные индикаторы в сервисе.Существуют некоторые инструменты с открытым исходным кодом для мониторинга этих индикаторов Redis, такие как:Cloud Insight Redis,Prometheus,Redis-stat,Redis-faina. Однако эти инструменты часто неэффективны в нашем более индивидуальном бизнесе, и компании часто разрабатывают свои собственные службы мониторинга для собственного бизнеса.
Redis предоставляет некоторые команды, которые также могут помочь нам в устранении неполадок. Например, showlog, monitor; кроме того, Redis также предоставляет тестовые команды, с помощью которых мы можем получить такие показатели производительности, как пропускная способность Redis и частота попаданий в кэш.
4. Постскриптум
Эта статья разбиралась с перерывами в течение полумесяца, и автор только извлек изложенное выше содержание со ссылкой на большое количество материалов. Многие части статьи действительно недостаточно углублены, а также есть некоторые пустые теории.Кроме того, собственный опыт работы автора не очень богат.По поводу mysql,redis и php многие базовые знания не изучены на месте .Статья заведомо неуместная и неправильная.Надеюсь читатели внесут исправления в поле сообщения после того как узнают.
Оглядываясь назад на эту статью, автор немного смущается говорить здесь о «кэше», но это все моя тяжелая работа, и это рассматривается как моя учебная заметка.
Дизайн системы и применение, связанное с «кэшем», это не просто то, что я упомянул, например: выбор и сжатие структур данных кеша, синхронизация данных между многоуровневыми кешами и т. д., это не упоминается, если в будущем Если У меня есть возможность, надеюсь усвоить эти знания вглубь и сделать некоторые дополнения к статье.