Кэширование: сверху вниз

Пост Кэширование: сверху вниз появился первым на Coderscat Анкет

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

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

В информатике есть только две тяжелые вещи:

Кэш недействительный и называть вещи.

– Фил Карлтон

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

Рисунок 1: Кэширование: сверху снизу

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

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

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

Кэширование используется в сценариях, таких как:

Читать операции по численности операции записи.
Операции идут с Принцип местности Анкет

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

Вот некоторые ключевые аспекты, связанные с кэшированием:

Коэффициент попадания

𝑁 (ℎ𝑖𝑡)/(𝑁 (ℎ𝑖𝑡)+𝑁 (𝑚𝑖𝑠ℎ𝑖𝑡))

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

Стратегия доступа к данным кэша и обновления

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

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

Наименьшее недавно (LRU)
Наименее часто используется (LFU)
Совсем недавно использовался (MRU)
Сначала, сначала (FIFO)

Между тем, кэширование может представлять некоторые другие вопросы, такие как несоответствие данных.

Однократное или распределенное кэширование

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

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

CDN

CDN (Сеть доставки контента) — это важная интернет -инфраструктура, внедряя концепцию кэширования.

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

Рисунок 2: Источник: Вики

Типичный рабочий процесс CDN:

Когда клиент запрашивает данные из узла CDN, узел CDN проверяет, не установлены ли кэшированные данные.

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

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

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

Последующий вопрос: как сервер CDN проверяет, имеет ли клиент последний кэшированный контент?

Ответ относится к методологии кэширования HTTP.

Http caching

В контексте Интернета пользователи читают чаще, чем писать.

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

В контексте HTTP используется множество схем кеша. Самым важным заголовком кэша является контроль от кеша.

Рисунок 3: Заголовки HTTP, связанные с кэшированием

Контроль кэша: без магазина

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

Контроль кэша: без кеша

Кэш отправит запрос на исходный сервер для проверки перед выпуском кэшированной копии.

Контроль кэша: частное

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

Контроль кэша: публичная

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

*Но как мы решаем устаревшую проблему данных?*

Ответ etags/last-модифицирован, сервер проверит эти заголовки, чтобы определить, подтверждается ли локальный кэш клиента.

Рисунок 4: HTTP Caching: Client and Server Flow

Ответ HTTP с 304 будет отправлен, если он будет подтвержден, в противном случае ответ 200 с новым контентом.

Другое решение для истекших данных — генерировать новый уникальный URL -адрес ресурсов, в обычных случаях файлы файлов StyleShip, изображения на HTML -страницах, файлы JavaScript будут внедрять отпечаток пальца в имя файла. Так что клиенты будут получать из нового URL -адреса, если сервер обновлен контент.

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

Nginx кэширование

Рисунок 5: Изображение Кредит: Конфиденциальность Канада ( https://privacycanada.net )

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

Рисунок 6: Конфигурация кэша NGINX: https://serversforhackers.com/c/nginx-caching

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

Здесь необходимо заметить еще один момент, что мы устанавливаем размер пространства памяти (для ключей кеша) на 10 м, кэшированное значение хранится на диске с Path/TMP/Nginx.

Вариант * неактивно = 60 м* Используется для указания того, как долго элемент может оставаться в кэше, не будучи доступ.

За исключением лучшей производительности, Nginx Cache также может улучшить доступность сайтов, мы могли бы использовать * proxy_cache_use_stale* Параметры для доставки кэшированного контента, когда происхождение упало.

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

Кэширование системы Linux

Имейте в виду, System-Call стоит дорого, а операция данных на диске (чтение/запись) намного медленнее, чем работа по памяти. Linux будет максимизировать использование памяти компьютеров для лучшей производительности.

Давайте проверим команду «бесплатно»:

Рисунок 7: Linux бесплатная команда

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

Не волнуйтесь, Linux не Ешьте вашу память Анкет Система просто заимствует * неиспользованная память* для кэширования диска. Это выглядит так, будто у вас мало памяти.

Когда данные записываются, Linux сначала записывает его в кэш страниц (в памяти) и отмечает страницу на грязное, содержание этих грязных страниц периодически передается (а также с синхронизацией системы или FSYNC) на базовое устройство хранения Анкет

Давайте запустим некоторые команды, чтобы проверить это:

Рисунок 8: Команда Linux Sync

Из вывода мы могли бы узнать после написания данных 200 МБ, грязные страницы в системе растет.

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

Файл -блоки записываются в кэш страницы не только во время написания, но и при чтении файлов.

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

ЦП кэширование

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

Рисунок 9: Изображение Credit Extrectech.com

Кэши ЦП — это небольшие пулы памяти, которые хранят информацию. ЦП, скорее всего, понадобится дальше. Все современные процессоры имеют несколько уровней CPU Caches. Время доступа сильно варьируется между каждым уровнем кэша, более высокая стоимость на байт более высоких уровней выше, чем более медленные, а также с меньшей мощностью. Кэш L1 быстрее, чем кэш L2, а кэш L2 более быстрее, чем ОЗУ.

Рисунок 10: Изображение кредит https://hazelcast.com/glossary/memory-caching/

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

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

Давайте проведем проверку с этими двумя функциями C, каковы различия между ними?

Почему первая функция почти в 2 раза быстрее, чем последняя?

int array_sum_row(int a[M][N]) {
  int i,j,sum=0;
  for(i = 0; i

Потому что макет ряда в памяти используется компиляторами C/C ++.

Когда доступ к данным в [i] [0], ближайшие данные A [i] [1] ~ a [i] [k] будут загружены в кэш. Согласно Ордену Итерации, поскольку элементы поблизости были кэшированы, мы получим высокий уровень попадания в кеш.

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

Кэширование в алгоритмах

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

function fib(n) {
 if (n < 2) {
   return n
 }
 return fib(n - 1) + fib(n - 2)
}

JavaScript

Если мы проанализируем вычислительный процесс в визуализации, мы обнаружим, что во время вычислений есть некоторые дублированные части. Его сложность в Big O обозначениях — 𝑂 (2𝑛) O (2n).

Рисунок 11: Изображение Кредит: https://medium.com/@porzingod

Мемонизация (наполнение кеша сверху вниз) может использоваться для оптимизации производительности, мы используем массив для хранения вычисленного результата:

memFib(n) {
   if (mem[n] is undefined)
       if (n < 2) result = n
       else result = memFib(n-2) + memFib(n-1)
       mem[n] = result
   return mem[n]
}

JavaScript

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

tabFib(n) {
   mem[0] = 0
   mem[1] = 1
   for i = 2...n
       mem[i] = mem[i-2] + mem[i-1]
   return mem[n]
}

JavaScript

Идея уменьшения дублированных вычислений также применяется в * Динамическое программирование (DP) * , ключевым наблюдением за задачей DP является поиск перекрывающихся подзадач и использование кэша для хранения перекрывающихся результатов.

Резюме вверх

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

Основным принципом является: используйте кэш, чтобы уменьшить дубликат в вычислениях (Fibonacci), а иногда и храните дубликаты данных на более быстром компоненте, если это необходимо (случай в CDN, кэш памяти).

Рисунок 12: Классическая цитата CS

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

Как начинающий программист , мы должны овладеть этим!

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

CDN

Http caching

Nginx кэширование

Кэширование системы Linux

ЦП кэширование

Кэширование в алгоритмах

Резюме вверх

Рекомендации

Читайте ещё по теме: