В вычислительной технике кэш ( / 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 в стиле ЦП.
Цифровые сигнальные процессоры за прошедшие годы получили аналогичные обобщения. В более ранних разработках использовалась блокнотная память, питаемая прямым доступом к памяти , но современные DSP, такие как Qualcomm Hexagon, часто включают в себя набор кэшей, очень похожий на ЦП (например, модифицированная Гарвардская архитектура с общим L2, разделенным I-кэшем L1 и D-кэшем). [8]
Блок управления памятью (MMU), который извлекает записи таблицы страниц из основной памяти, имеет специализированный кэш, используемый для записи результатов преобразования виртуального адреса в физический адрес . Этот специализированный кеш называется резервным буфером трансляции (TLB). [9]
Информационно-ориентированные сети (ICN) — это подход к развитию инфраструктуры Интернета от парадигмы, ориентированной на хост, основанной на постоянном подключении и сквозном принципе , к сетевой архитектуре, в которой фокусом является идентифицированная информация (или контент или данные). Благодаря присущей узлам ICN возможности кэширования ее можно рассматривать как слабосвязанную сеть кэшей, к которой предъявляются уникальные требования политики кэширования. Однако повсеместное кэширование контента создает проблему защиты контента от несанкционированного доступа, которая требует особого внимания и решений. [10]
В отличие от прокси-серверов, в ICN кэш является решением сетевого уровня. Следовательно, он имеет быстро меняющиеся состояния кэша и более высокую скорость поступления запросов; более того, меньшие размеры кэша дополнительно налагают иные требования к политике удаления контента. В частности, политика выселения для ICN должна быть быстрой и упрощенной. Были предложены различные схемы репликации и вытеснения кэша для различных архитектур и приложений ICN.
Функция «Наименее недавно использованное с учетом времени» (TLRU) [11] представляет собой вариант LRU, разработанный для ситуации, когда содержимое, хранящееся в кэше, имеет действительный срок жизни. Алгоритм подходит для приложений сетевого кэша, таких как ICN, сети доставки контента (CDN) и распределенные сети в целом. TLRU вводит новый термин: TTU (время использования). TTU — это отметка времени контента/страницы, которая определяет время использования контента на основе местоположения контента и объявления издателя контента. Благодаря этой метке времени, основанной на местоположении, TTU предоставляет локальному администратору больше контроля над сетевым хранилищем.
В алгоритме TLRU при поступлении части контента узел кэша вычисляет локальное значение TTU на основе значения TTU, назначенного издателем контента. Локальное значение TTU рассчитывается с использованием локально определенной функции. После расчета локального значения TTU замена контента выполняется для подмножества общего контента, хранящегося в узле кэша. TLRU гарантирует, что менее популярный и малозначимый контент будет заменен входящим контентом.
Схема замены кэша наименее частого использования в последнее время (LFRU) [12] сочетает в себе преимущества схем LFU и LRU. LFRU подходит для приложений кэширования «внутри сети», таких как ICN, CDN и распределенные сети в целом. В LFRU кеш разделен на два раздела, которые называются привилегированными и непривилегированными. Привилегированный раздел можно определить как защищенный раздел. Если контент пользуется большой популярностью, он помещается в привилегированный раздел. Замена привилегированного раздела выполняется следующим образом: LFRU удаляет содержимое из непривилегированного раздела, перемещает содержимое из привилегированного раздела в непривилегированный раздел и, наконец, вставляет новое содержимое в привилегированный раздел. В описанной выше процедуре LRU используется для привилегированного раздела, а аппроксимированная схема LFU (ALFU) используется для непривилегированного раздела, отсюда и аббревиатура LFRU. Основная идея состоит в том, чтобы отфильтровать локально популярный контент с помощью схемы ALFU и поместить популярный контент в один из привилегированных разделов.
В 2011 году использование смартфонов с функцией прогноза погоды приводило к чрезмерной нагрузке на серверы AccuWeather ; два запроса в одном парке будут генерировать отдельные запросы. Оптимизация пограничных серверов для усечения координат GPS до меньшего количества десятичных знаков означала, что будут использоваться кэшированные результаты предыдущего запроса. Количество обращений к серверу в день сократилось вдвое. [13]
Хотя кэши ЦП обычно полностью управляются аппаратным обеспечением, другими кэшами управляет разнообразное программное обеспечение. Кэш страниц в основной памяти, который является примером дискового кеша, управляется ядром операционной системы .
Хотя дисковый буфер , который является неотъемлемой частью жесткого или твердотельного диска, иногда ошибочно называют «дисковым кэшем», его основными функциями являются упорядочивание записи и предварительная выборка чтения. Повторные попадания в кэш относительно редки из-за небольшого размера буфера по сравнению с емкостью диска. Однако высокопроизводительные дисковые контроллеры часто имеют собственный встроенный кэш блоков данных жесткого диска.
Наконец, быстрый локальный жесткий диск может также кэшировать информацию, хранящуюся на даже более медленных устройствах хранения данных, таких как удаленные серверы (веб-кэш), локальные ленточные накопители или оптические музыкальные автоматы ; такая схема является основной концепцией иерархического управления хранилищем . Кроме того, быстрые твердотельные накопители на основе флэш-памяти (SSD) можно использовать в качестве кэшей для более медленных жестких дисков с вращающимися носителями, работая вместе как гибридные диски или твердотельные гибридные диски (SSHD).
Веб-браузеры и веб-прокси-серверы используют веб-кеши для хранения предыдущих ответов от веб-серверов, таких как веб-страницы и изображения . Веб-кеши уменьшают объем информации, которую необходимо передать по сети, поскольку информацию, ранее хранившуюся в кеше, часто можно использовать повторно. Это снижает требования к пропускной способности и обработке веб-сервера, а также помогает улучшить скорость реагирования для пользователей Интернета. [14]
Веб-браузеры используют встроенный веб-кэш, но некоторые интернет-провайдеры (ISP) или организации также используют кеширующий прокси-сервер, который представляет собой веб-кэш, общий для всех пользователей этой сети.
Другой формой кеша является P2P-кэширование , при котором файлы, которые наиболее востребованы одноранговыми приложениями, хранятся в кеше интернет-провайдера для ускорения P2P-передачи. Аналогичным образом существуют децентрализованные эквиваленты, которые позволяют сообществам выполнять ту же задачу для P2P-трафика, например Corelli. [15]
Кэш может хранить данные, которые вычисляются по требованию, а не извлекаются из резервного хранилища. Мемоизация — это метод оптимизации , который сохраняет результаты вызовов ресурсоемких функций в справочной таблице, позволяя последующим вызовам повторно использовать сохраненные результаты и избегать повторных вычислений. Это связано с методологией разработки алгоритмов динамического программирования , которую также можно рассматривать как средство кэширования.
Сеть доставки контента (CDN) — это сеть распределенных серверов, которые доставляют страницы и другой веб-контент пользователю в зависимости от географического местоположения пользователя, происхождения веб-страницы и сервера доставки контента.
CDN появились в конце 1990-х годов как способ ускорить доставку статического контента, такого как HTML-страницы, изображения и видео. Реплицируя контент на нескольких серверах по всему миру и доставляя его пользователям в зависимости от их местоположения, CDN могут значительно повысить скорость и доступность веб-сайта или приложения. Когда пользователь запрашивает часть контента, CDN проверит, есть ли у него копия контента в его кеше. Если это так, CDN доставит контент пользователю из кэша. [16]
Шлюз облачного хранилища, также известный как пограничный файловер, представляет собой гибридное облачное устройство хранения, которое подключает локальную сеть к одной или нескольким службам облачного хранения , обычно службам объектного хранения , таким как Amazon S3 . Он обеспечивает кэширование часто используемых данных, обеспечивая высокоскоростной локальный доступ к часто используемым данным в службе облачного хранения. Шлюзы облачного хранилища также предоставляют дополнительные преимущества, такие как доступ к хранилищу облачных объектов через традиционные протоколы обслуживания файлов, а также постоянный доступ к кэшированным данным во время сбоев подключения. [17]
Демон BIND DNS кэширует сопоставление доменных имен с IP-адресами , как и библиотека преобразователя.
Операция сквозной записи распространена при работе в ненадежных сетях (например, локальной сети Ethernet) из-за огромной сложности протокола согласованности, необходимого между несколькими кэшами обратной записи, когда связь ненадежна. Например, кэши веб-страниц и кэши сетевой файловой системы на стороне клиента (например, в NFS или SMB ) обычно доступны только для чтения или со сквозной записью специально для обеспечения простоты и надежности сетевого протокола.
Поисковые системы также часто делают проиндексированные веб-страницы доступными из своего кеша. Например, Google предоставляет ссылку «Кэшировано» рядом с каждым результатом поиска. Это может оказаться полезным, когда веб-страницы с веб-сервера временно или постоянно недоступны.
Кэширование базы данных может существенно повысить производительность приложений баз данных , например, при обработке индексов , словарей данных и часто используемых подмножеств данных.
Распределенный кэш [18] использует сетевые хосты для обеспечения масштабируемости, надежности и производительности приложения. [19] Хосты могут быть расположены рядом или разбросаны по разным географическим регионам.
Семантика «буфера» и «кэша» не совсем различна; даже в этом случае существуют фундаментальные различия между процессом кэширования и процессом буферизации.
По сути, кэширование обеспечивает повышение производительности при многократной передаче данных. Хотя система кэширования может реализовать увеличение производительности при первоначальной (обычно записи) передаче элемента данных, это увеличение производительности происходит из-за буферизации, происходящей в системе кэширования.
При использовании кэшей чтения элемент данных должен быть извлечен из своего постоянного местоположения хотя бы один раз, чтобы последующие чтения элемента данных реализовали повышение производительности благодаря возможности извлечения из (более быстрого) промежуточного хранилища кэша, а не из местонахождение данных. При использовании кэшей записи повышение производительности записи элемента данных может быть реализовано при первой записи элемента данных благодаря тому, что элемент данных немедленно сохраняется в промежуточном хранилище кэша, откладывая передачу элемента данных в его постоянное хранилище на момент более поздний этап или же происходит как фоновый процесс. В отличие от строгой буферизации, процесс кэширования должен придерживаться протокола согласованности (потенциально распределенного) кэша, чтобы поддерживать согласованность между промежуточным хранилищем кэша и местом, где находятся данные. С другой стороны, буферизация
В типичных реализациях кэширования элемент данных, который читается или записывается впервые, фактически буферизуется; а в случае записи, главным образом, реализуя повышение производительности приложения, из которого произошла запись. Кроме того, часть протокола кэширования, в которой отдельные записи откладываются до пакета записей, является формой буферизации. Часть протокола кэширования, в которой отдельные чтения откладываются до пакета чтений, также является формой буферизации, хотя эта форма может отрицательно повлиять на производительность, по крайней мере, начальных операций чтения (хотя она может положительно повлиять на производительность суммы операций чтения). человек читает). На практике кэширование почти всегда включает в себя ту или иную форму буферизации, тогда как строгая буферизация не предполагает кэширования.
Буфер — это временная ячейка памяти, которая традиционно используется, поскольку инструкции ЦП не могут напрямую обращаться к данным, хранящимся на периферийных устройствах. Таким образом, адресная память используется как промежуточный этап. Кроме того, такой буфер может быть целесообразным, когда большой блок данных собирается или разбирается (как того требует устройство хранения) или когда данные могут доставляться в порядке, отличном от того, в котором они создаются. Кроме того, весь буфер данных обычно передается последовательно (например, на жесткий диск), поэтому буферизация сама по себе иногда увеличивает производительность передачи или уменьшает колебания или дрожание задержки передачи, в отличие от кэширования, где цель состоит в том, чтобы уменьшить задержку. Эти преимущества присутствуют, даже если буферизованные данные записываются в буфер один раз и один раз считываются из буфера.
Кэш также увеличивает производительность передачи. Частично увеличение также связано с возможностью объединения нескольких мелких переводов в один большой блок. Но основной прирост производительности происходит потому, что существует большая вероятность того, что одни и те же данные будут прочитаны из кэша несколько раз или что записанные данные вскоре будут прочитаны. Единственная цель кэша — уменьшить доступ к базовому, более медленному хранилищу. Кэш также обычно представляет собой уровень абстракции , который спроектирован так, чтобы быть невидимым с точки зрения соседних слоев.
Серверы AccuWeather обрабатывают на 300–500 миллионов меньше запросов в день.