В вычислительной технике кэш ( / k æ ʃ / KASH)[1]— это аппаратный или программный компонент, который хранит данные, чтобы будущие запросы на эти данные могли обслуживаться быстрее; данные, хранящиеся в кэше, могут быть результатом более раннего вычисления или копией данных, хранящихся в другом месте.Попадание в кэшпроисходит, когда запрошенные данные могут быть найдены в кэше, в то время какпромах кэшапроисходит, когда они не могут быть найдены. Попадания в кэш обслуживаются путем чтения данных из кэша, что быстрее, чем повторное вычисление результата или чтение из более медленного хранилища данных; таким образом, чем больше запросов может быть обработано из кэша, тем быстрее работает система.[2]
Чтобы быть экономически эффективными, кэши должны быть относительно небольшими. Тем не менее, кэши эффективны во многих областях вычислений, поскольку типичные компьютерные приложения получают доступ к данным с высокой степенью локальности ссылок . Такие шаблоны доступа демонстрируют временную локальность, когда запрашиваются данные, которые были недавно запрошены, и пространственную локальность, когда запрашиваются данные, которые хранятся рядом с данными, которые уже были запрошены.
В конструкции памяти существует неотъемлемый компромисс между емкостью и скоростью, поскольку большая емкость подразумевает больший размер и, следовательно, большие физические расстояния для прохождения сигналов, вызывая задержки распространения . Существует также компромисс между высокопроизводительными технологиями, такими как SRAM , и более дешевыми, легко производимыми в массовом порядке товарами, такими как DRAM , флэш-память или жесткие диски .
Буферизация , обеспечиваемая кэшем, обеспечивает либо задержку , либо пропускную способность ( полосу пропускания ).
Больший ресурс вызывает значительную задержку доступа — например, современному процессору с частотой 4 ГГц могут потребоваться сотни тактовых циклов, чтобы достичь DRAM. Это смягчается путем чтения больших фрагментов в кэш, в надежде, что последующие чтения будут из соседних мест и могут быть прочитаны из кэша. Прогнозирование или явная предварительная выборка могут использоваться для того, чтобы угадать, откуда будут поступать будущие чтения, и делать запросы заранее; если все сделано оптимально, задержка полностью обходится.
Использование кэша также позволяет повысить пропускную способность базового ресурса, собирая несколько мелкозернистых передач в более крупные и эффективные запросы. В случае схем DRAM дополнительная пропускная способность может быть получена за счет использования более широкой шины данных.
Аппаратное обеспечение реализует кэш как блок памяти для временного хранения данных, которые, вероятно, будут использоваться снова. Центральные процессоры (ЦП), твердотельные накопители (SSD) и жесткие диски (HDD) часто включают в себя аппаратный кэш, в то время как веб-браузеры и веб-серверы обычно полагаются на программное кэширование.
Кэш состоит из пула записей. Каждая запись имеет ассоциированные данные , которые являются копией тех же данных в некотором резервном хранилище . Каждая запись также имеет тег , который указывает идентификатор данных в резервном хранилище, копией которых является запись.
Когда клиенту кэша (процессору, веб-браузеру, операционной системе ) необходимо получить доступ к данным, предположительно существующим в резервном хранилище, он сначала проверяет кэш. Если запись может быть найдена с тегом, соответствующим тегу требуемых данных, вместо этого используются данные в записи. Такая ситуация известна как попадание в кэш . Например, программа веб-браузера может проверить свой локальный кэш на диске, чтобы узнать, есть ли у него локальная копия содержимого веб-страницы по определенному URL . В этом примере URL является тегом, а содержимое веб-страницы — данными. Процент обращений, которые приводят к попаданиям в кэш, известен как показатель попаданий или коэффициент попаданий кэша.
Альтернативная ситуация, когда кэш проверяется и обнаруживается, что он не содержит ни одной записи с нужным тегом, называется промахом кэша . Это требует более дорогостоящего доступа к данным из резервного хранилища. После того, как запрошенные данные извлечены, они обычно копируются в кэш, готовые к следующему доступу.
Во время кэш-промаха некоторые другие ранее существовавшие записи кэша обычно удаляются, чтобы освободить место для вновь извлеченных данных. Эвристика, используемая для выбора записи для замены, известна как политика замены . Одна популярная политика замены, наименее недавно использованная (LRU), заменяет самую старую запись, запись, к которой обращались реже, чем к любой другой записи. Более сложные алгоритмы кэширования также учитывают частоту использования записей.
Когда система записывает данные в кэш, она должна в какой-то момент записать эти данные и в резервное хранилище. Время этой записи контролируется тем, что известно как политика записи . Существует два основных подхода к записи: [3]
Кэш обратной записи сложнее реализовать, поскольку ему необходимо отслеживать, какие из его расположений были перезаписаны, и помечать их как грязные для последующей записи в резервное хранилище. Данные в этих расположениях записываются обратно в резервное хранилище только тогда, когда они вытесняются из кэша, процесс, называемый ленивой записью . По этой причине пропуск чтения в кэше обратной записи часто потребует двух обращений к резервному хранилищу памяти для обслуживания: одного для обратной записи и одного для извлечения необходимых данных. Другие политики также могут инициировать обратную запись данных. Клиент может внести много изменений в данные в кэше, а затем явно уведомить кэш о необходимости записать данные обратно.
Поскольку при операциях записи запрашивающей стороне не возвращаются никакие данные, необходимо принять решение о том, будут ли данные загружаться в кэш при промахах записи.
Как политика сквозной записи, так и политика обратной записи могут использовать любую из этих политик промахов записи, но обычно они используются в паре. [4] [5]
Другие сущности, помимо кэша, могут изменять данные в резервном хранилище, в этом случае копия в кэше может стать устаревшей или неактуальной . В качестве альтернативы, когда клиент обновляет данные в кэше, копии этих данных в других кэшах станут устаревшими. Протоколы связи между менеджерами кэша, которые поддерживают согласованность данных, связаны с согласованностью кэша .
При промахе чтения кэша кэши с политикой подкачки по требованию считывают минимальный объем из резервного хранилища. Типичная реализация виртуальной памяти с подкачкой по требованию считывает одну страницу виртуальной памяти (часто 4 КБ) с диска в дисковый кэш в ОЗУ. Типичный ЦП считывает одну строку кэша L2 размером 128 байт из DRAM в кэш L2 и одну строку кэша L1 размером 64 байта из кэша L2 в кэш L1.
Кэши с предварительной выборкой очереди ввода или более общей политикой опережающего подкачки идут дальше — они не только считывают запрошенные данные, но и предполагают, что скоро понадобится следующая порция или две данных, и поэтому заранее извлекают эти данные в кэш. Опережающее подкачка особенно полезно, когда резервное хранилище имеет большую задержку для чтения первой порции и гораздо более короткое время для последовательного чтения следующих нескольких порций, таких как дисковое хранилище и DRAM.
Несколько операционных систем идут дальше с загрузчиком , который всегда предварительно загружает весь исполняемый файл в оперативную память. Несколько кэшей идут еще дальше, не только предварительно загружая весь файл, но и начиная загружать другие связанные файлы, которые могут быть вскоре запрошены, такие как кэш страниц , связанный с предвыборкой , или веб-кэш, связанный с предварительной выборкой ссылок .
Небольшие объемы памяти на ЦП или рядом с ним могут работать быстрее, чем основная память гораздо большего размера . [6] Большинство ЦП с 1980-х годов использовали один или несколько кэшей, иногда в каскадных уровнях ; современные высокопроизводительные встраиваемые , настольные и серверные микропроцессоры могут иметь до шести типов кэшей (между уровнями и функциями). [7] Некоторые примеры кэшей с определенной функцией — это D-кэш , I-кэш и буфер трансляции для блока управления памятью (MMU).
Более ранние графические процессоры (GPU) часто имели ограниченные кэши текстур только для чтения и использовали swizzling для улучшения 2D- локальности ссылок . Промахи кэша могли бы существенно повлиять на производительность, например, если бы не использовалось mip-отображение . Кэширование было важно для использования 32-битных (и более широких) передач для текстурных данных, которые часто были всего лишь 4 бита на пиксель.
По мере развития графических процессоров, поддерживающих вычисления общего назначения на графических процессорах и вычислительных ядрах , они разработали все более крупные и общие кэши, включая кэши инструкций для шейдеров , демонстрируя функциональность, обычно встречающуюся в кэшах ЦП. Эти кэши выросли до обработки примитивов синхронизации между потоками и атомарными операциями и взаимодействуют с MMU в стиле ЦП.
Цифровые сигнальные процессоры также обобщались на протяжении многих лет. Более ранние разработки использовали память scratchpad, питаемую прямым доступом к памяти , но современные DSP, такие как Qualcomm Hexagon, часто включают в себя набор кэшей, очень похожий на CPU (например, модифицированная архитектура Гарварда с общим L2, разделенным L1 I-кэшем и D-кэшем). [8]
Блок управления памятью (MMU), который извлекает записи таблицы страниц из основной памяти, имеет специализированный кэш, используемый для записи результатов трансляций виртуальных адресов в физические адреса . Этот специализированный кэш называется буфером трансляции lookaside (TLB). [9]
Информационно-центрическая сеть (ICN) — это подход к развитию инфраструктуры Интернета от парадигмы, ориентированной на хост, основанной на постоянной связности и принципе сквозного соединения , к сетевой архитектуре, в которой фокусом является идентифицированная информация. Благодаря присущей узлам возможности кэширования в ICN, ее можно рассматривать как слабо связанную сеть кэшей, которая имеет уникальные требования к политикам кэширования. Однако повсеместное кэширование контента представляет собой проблему защиты контента от несанкционированного доступа, что требует дополнительной заботы и решений. [10]
В отличие от прокси-серверов, в ICN кэш представляет собой решение на сетевом уровне. Поэтому он имеет быстро меняющиеся состояния кэша и более высокие скорости поступления запросов; кроме того, меньшие размеры кэша накладывают различные требования на политики вытеснения контента. В частности, политики вытеснения для ICN должны быть быстрыми и легкими. Были предложены различные схемы репликации и вытеснения кэша для различных архитектур и приложений ICN. [ необходима цитата ]
Time aware Least Recently Used (TLRU) [11] — это вариант LRU, разработанный для ситуации, когда хранящееся в кэше содержимое имеет допустимый срок службы. Алгоритм подходит для приложений сетевого кэширования, таких как ICN, сети доставки контента (CDN) и распределенные сети в целом. TLRU вводит новый термин: TTU (время использования). TTU — это временная метка контента/страницы, которая определяет время использования контента на основе местоположения контента и объявления издателя контента. Благодаря этой временной метке на основе местоположения TTU предоставляет локальному администратору больше контроля для регулирования сетевого хранилища.
В алгоритме TLRU, когда поступает фрагмент контента, узел кэша вычисляет локальное значение TTU на основе значения TTU, назначенного издателем контента. Локальное значение TTU вычисляется с использованием локально определенной функции. После вычисления локального значения TTU выполняется замена контента на подмножестве общего контента, хранящегося в узле кэша. TLRU гарантирует, что менее популярный и малоактуальный контент должен быть заменен входящим контентом.
Схема замены кэша Least Frequent Recently Used (LFRU) [12] объединяет преимущества схем LFU и LRU. LFRU подходит для приложений кэширования «внутри сети», таких как ICN, CDN и распределенные сети в целом. В LFRU кэш делится на два раздела, называемых привилегированными и непривилегированными разделами. Привилегированный раздел можно определить как защищенный раздел. Если контент очень популярен, он помещается в привилегированный раздел. Замена привилегированного раздела выполняется следующим образом: LFRU вытесняет контент из непривилегированного раздела, помещает контент из привилегированного раздела в непривилегированный раздел и, наконец, вставляет новый контент в привилегированный раздел. В вышеприведенной процедуре LRU используется для привилегированного раздела, а приближенная схема LFU (ALFU) используется для непривилегированного раздела, отсюда и сокращение LFRU. Основная идея заключается в том, чтобы отфильтровать локально популярный контент с помощью схемы ALFU и поместить популярный контент в один из привилегированных разделов.
В 2011 году использование смартфонов с опциями прогнозирования погоды было чрезмерно обременительным для серверов AccuWeather ; два запроса в пределах одного парка генерировали отдельные запросы. Оптимизация пограничными серверами для усечения координат GPS до меньшего количества десятичных знаков означала, что будут использоваться кэшированные результаты из более раннего запроса. Количество поисков на сервере в день сократилось вдвое. [13]
В то время как кэши ЦП, как правило, полностью управляются аппаратным обеспечением, другие кэши управляются разнообразным программным обеспечением. Кэш страниц в основной памяти, который является примером дискового кэша, управляется ядром операционной системы .
Хотя дисковый буфер , который является неотъемлемой частью жесткого диска или твердотельного накопителя, иногда ошибочно называют «дисковым кэшем», его основными функциями являются последовательность записи и предварительная выборка чтения. Повторные попадания в кэш относительно редки из-за небольшого размера буфера по сравнению с емкостью накопителя. Однако высокопроизводительные контроллеры дисков часто имеют собственный встроенный кэш блоков данных жесткого диска.
Наконец, быстрый локальный жесткий диск может также кэшировать информацию, хранящуюся на еще более медленных устройствах хранения данных, таких как удаленные серверы (веб-кэш) или локальные ленточные накопители или оптические музыкальные автоматы ; такая схема является основной концепцией иерархического управления хранением . Кроме того, быстрые твердотельные накопители на основе флэш-памяти (SSD) могут использоваться в качестве кэшей для более медленных жестких дисков с вращающимися носителями, работая вместе как гибридные диски или твердотельные гибридные диски (SSHD).
Веб-браузеры и веб-прокси-серверы используют веб-кэши для хранения предыдущих ответов от веб-серверов, таких как веб-страницы и изображения . Веб-кэши уменьшают объем информации, которую необходимо передавать по сети, поскольку информация, ранее сохраненная в кэше, часто может быть повторно использована. Это снижает требования к пропускной способности и обработке веб-сервера и помогает улучшить отзывчивость для пользователей сети. [14]
Веб-браузеры используют встроенный веб-кэш, но некоторые интернет-провайдеры (ISP) или организации также используют кэширующий прокси-сервер, представляющий собой веб-кэш, который совместно используется всеми пользователями этой сети.
Другой формой кэширования является кэширование P2P , где файлы, наиболее востребованные одноранговыми приложениями , хранятся в кэше ISP для ускорения P2P-передач. Аналогично существуют децентрализованные эквиваленты, которые позволяют сообществам выполнять ту же задачу для трафика P2P, например, Corelli. [15]
Кэш может хранить данные, которые вычисляются по требованию, а не извлекаются из резервного хранилища. Мемоизация — это метод оптимизации , который сохраняет результаты ресурсоемких вызовов функций в таблице поиска, позволяя последующим вызовам повторно использовать сохраненные результаты и избегать повторных вычислений. Он связан с методологией разработки алгоритмов динамического программирования , которую также можно рассматривать как средство кэширования.
Сеть доставки контента (CDN) — это сеть распределенных серверов, которые доставляют страницы и другой веб-контент пользователю на основе географического местоположения пользователя, источника веб-страницы и сервера доставки контента.
CDN появились в конце 1990-х годов как способ ускорить доставку статического контента, такого как HTML-страницы, изображения и видео. Реплицируя контент на нескольких серверах по всему миру и доставляя его пользователям в зависимости от их местоположения, CDN могут значительно повысить скорость и доступность веб-сайта или приложения. Когда пользователь запрашивает часть контента, CDN проверит, есть ли у него копия контента в кэше. Если это так, CDN доставит контент пользователю из кэша. [16]
Облачный шлюз хранения, также известный как пограничный файлер, представляет собой гибридное облачное устройство хранения, которое подключает локальную сеть к одному или нескольким облачным сервисам хранения , как правило, сервисам хранения объектов , таким как Amazon S3 . Он предоставляет кэш для часто используемых данных, обеспечивая высокоскоростной локальный доступ к часто используемым данным в облачном сервисе хранения. Облачные шлюзы хранения также предоставляют дополнительные преимущества, такие как доступ к облачному объектному хранилищу через традиционные протоколы обслуживания файлов, а также постоянный доступ к кэшированным данным во время сбоев подключения. [17]
Демон BIND DNS кэширует сопоставление доменных имен с IP-адресами , как и библиотека преобразователя.
Операция сквозной записи обычна при работе в ненадежных сетях (например, Ethernet LAN) из-за огромной сложности протокола когерентности, необходимого между несколькими кэшами обратной записи, когда связь ненадежна. Например, кэши веб-страниц и кэши клиентских сетевых файловых систем (например, в NFS или SMB ) обычно доступны только для чтения или сквозной записи специально для того, чтобы сетевой протокол был простым и надежным.
Поисковые системы также часто делают проиндексированные ими веб-страницы доступными из своего кэша. Например, Google предоставляет ссылку «Кэшировано» рядом с каждым результатом поиска. Это может оказаться полезным, когда веб-страницы с веб-сервера временно или постоянно недоступны.
Кэширование базы данных может существенно повысить производительность приложений баз данных , например, при обработке индексов , словарей данных и часто используемых подмножеств данных.
Распределенный кэш [ 18] использует сетевые хосты для обеспечения масштабируемости, надежности и производительности приложения. [19] Хосты могут быть размещены совместно или распределены по разным географическим регионам.
Семантика «буфера» и «кэша» не совсем различна; тем не менее, существуют фундаментальные различия в намерениях между процессом кэширования и процессом буферизации.
По сути, кэширование реализует увеличение производительности для передачи данных, которые передаются повторно. Хотя система кэширования может реализовать увеличение производительности при первоначальной (обычно записи) передаче элемента данных, это увеличение производительности обусловлено буферизацией, происходящей в системе кэширования.
При использовании кэшей чтения элемент данных должен быть извлечен из своего постоянного местоположения по крайней мере один раз, чтобы последующие чтения элемента данных реализовали повышение производительности в силу возможности извлечения из (более быстрого) промежуточного хранилища кэша, а не из местоположения, в котором находятся данные. При использовании кэшей записи повышение производительности записи элемента данных может быть реализовано при первой записи элемента данных в силу того, что элемент данных немедленно сохраняется в промежуточном хранилище кэша, откладывая передачу элемента данных в его постоянное хранилище на более позднем этапе или же выполняясь как фоновый процесс. В отличие от строгой буферизации, процесс кэширования должен придерживаться (потенциально распределенного) протокола когерентности кэша, чтобы поддерживать согласованность между промежуточным хранилищем кэша и местоположением, в котором находятся данные. Буферизация, с другой стороны,
При типичных реализациях кэширования элемент данных, который считывается или записывается в первый раз, фактически буферизуется; а в случае записи, в основном реализуя увеличение производительности для приложения, из которого произошла запись. Кроме того, часть протокола кэширования, где отдельные записи откладываются до пакета записей, является формой буферизации. Часть протокола кэширования, где отдельные чтения откладываются до пакета чтений, также является формой буферизации, хотя эта форма может отрицательно влиять на производительность по крайней мере начальных чтений (даже если она может положительно влиять на производительность суммы отдельных чтений). На практике кэширование почти всегда включает в себя некоторую форму буферизации, в то время как строгая буферизация не включает в себя кэширование.
Буфер — это временное расположение памяти, которое традиционно используется, поскольку инструкции ЦП не могут напрямую адресовать данные, хранящиеся в периферийных устройствах. Таким образом, адресуемая память используется в качестве промежуточного этапа. Кроме того, такой буфер может быть осуществим, когда большой блок данных собирается или разбирается (как того требует устройство хранения) или когда данные могут быть доставлены в ином порядке, чем тот, в котором они были созданы. Кроме того, целый буфер данных обычно передается последовательно (например, на жесткий диск), поэтому сама буферизация иногда увеличивает производительность передачи или уменьшает вариацию или дрожание задержки передачи в отличие от кэширования, где намерение состоит в том, чтобы уменьшить задержку. Эти преимущества присутствуют, даже если буферизованные данные записываются в буфер один раз и считываются из буфера один раз.
Кэш также увеличивает производительность передачи. Часть увеличения также происходит из-за возможности объединения нескольких небольших передач в один большой блок. Но основной прирост производительности происходит из-за того, что есть большая вероятность того, что одни и те же данные будут считаны из кэша несколько раз или что записанные данные вскоре будут считаны. Единственная цель кэша — сократить доступ к базовому более медленному хранилищу. Кэш также обычно представляет собой уровень абстракции , который спроектирован так, чтобы быть невидимым с точки зрения соседних слоев.
На 300–500 миллионов меньше запросов в день обрабатываются серверами AccuWeather