Рандомизация кэширования - Рандомизированные алгоритмы

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

Задача

Для начала вспомним задачу поддержания кэша из главы 4. В простейшей конфигурации рассматривается процессор, основная память которого состоит из n адресов; процессор также оснащен кэшем на k ячеек памяти, к которым можно обращаться очень быстро. В ячейках кэша могут храниться копии k элементов из основной памяти, и при обращении к адресу памяти процессор сначала проверяет кэш, чтобы узнать, нельзя ли быстро получить необходимые данные. Если нужный элемент присутствует в кэше, обращение называется попаданием. Если же элемент в кэше отсутствует, то обращение называется кэш-промахом. В случае промаха обращение занимает намного больше времени; более того, один из элементов, находящихся в кэше, необходимо вытеснить, чтобы освободить место для нового элемента. (Будем считать, что кэш постоянно заполнен.)

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

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

На практике чаще всего применяется политика, при которой вытесняется элемент, использовавшийся ранее других (то есть элемент с самой ранней временной меткой последнего обращения); эта политика обозначается аббревиатурой LRU (Least-Recently-Used). Эмпирическое обоснование LRU заключается в том, что для алгоритмов характерна локальность обращений: обычно они многократно используют одни и те же данные в течение некоторого времени. Если к элементу данных давно не было ни одного обращения, весьма вероятно, что к нему в ближайшем будущем обращений не будет.

Здесь мы оценим быстродействие разных политик вытеснения без каких-либо предположений (например, локальности) относительно последовательности запросов. Для этого мы сравним число кэш-промахов, характерных для политики вытеснения σ, с минимальным количеством кэш-промахов, возможных для σ. Последняя величина будет обозначаться f(σ); это количество кэш-промахов достигается с оптимальной политикой отдаленного использования. Сравнение политик вытеснения с оптимумом идейно близко к предоставлению гарантий быстродействия для аппроксимирующих алгоритмов, как было сделано в главе 11. Однако обратите внимание на одно интересное различие: причина, по которой оптимум не достигался в аппроксимационном анализе из этой главы (в предположении P ≠ NP), заключалась в том, что алгоритмы ограничивались требованием о полиномиальном времени выполнения; с другой стороны, сейчас политики вытеснения ограничиваются фактом неизвестности обращений, которые могут поступить в будущем.

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

Сначала мы покажем, что количество кэш-промахов при политике LRU для любой последовательности обращений ограничивается примерно оптимумом, умноженным на k. Затем при помощи рандомизации будет разработана версия LRU, предоставляющая экспоненциально усиленную границу своего быстродействия: количество промахов в ней никогда не превышает оптимум более чем в O(log k) раз.

Разработка класса алгоритмом маркировки

Границы как политики LRU, так и ее рандомизированного варианта следуют из общего шаблона построения оперативных политик вытеснения — класса политик, называемого алгоритмами маркировки. В их основе лежит следующая идея: чтобы обеспечить хорошие показатели по сравнению с эталоном f(σ), необходима политика вытеснения, которая учитывает различия между двумя возможностями: (a) в недавнем прошлом последовательность обращений содержала более k разных элементов; или (b) в недавнем прошлом последовательность обращений поступила исключительно из множества, содержащего не более k элементов. В первом случае мы знаем, что значение f(σ) должно увеличиться, так как ни один алгоритм не может обратить более kразных элементов без кэш-промаха. Но во втором случае может оказаться, что σ проходит через длинную серию, в которой оптимальный алгоритм вообще не приводит к промахам. В этом случае наша политика должна принять меры к тому, чтобы количество промахов было минимальным.

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

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

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

(13.34) Политика LRU является алгоритмом маркировки.

Анализ алгоритмов маркировки

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

Рассмотрим произвольный алгоритм маркировки, работающий с последовательностью обращений σ. Для анализа представим оптимальный алгоритм кэширования, который работает с σ параллельно с этим алгоритмом разметки и обеспечивает общую стоимость f(σ). Предположим, последовательность σ состоит из r фаз, определяемых алгоритмом маркировки. Чтобы упростить рассмотрение анализа, мы “дополним” последовательность с в начале и в конце дополнительными обращениями: никаких лишних кэш-промахов в оптимальном алгоритме они не создадут (то есть не приведут к увеличению f(σ)), поэтому любая граница, доказанная для эффективности алгоритма маркировки относительно оптимума дополненной последовательности, также будет применима к σ. А конкретно перед первой фазой вставляется “фаза 0”, в которой запрашиваются все элементы, изначально находящиеся в кэше. Это никак не влияет на стоимость алгоритма маркировки или оптимального алгоритма. Также можно представить, что за завершающей фазой r следует эпилог, в котором каждый элемент, находящийся в кэше оптимального алгоритма, запрашивается дважды по кругу. Значение f(σ) при этом не увеличивается, а к концу второго прохода в алгоритме маркировки каждый элемент будет находиться в кэше и каждый будет помечен.

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

Деление последовательности обращений σ на фазы играет ключевую роль для получения границ. Прежде всего, история фазы с точки зрения алгоритма маркировки выглядит так: в начале фазы все элементы не помечены. Любой элемент, к которому происходит обращение в фазе, помечается маркером и затем остается в кэше в оставшейся части фазы. В ходе фазы количество помеченных элементов растет с 0 до k, а следующая фаза начинается с обращения к (k + 1)-му элементу, отличному от всех помеченных. Некоторые выводы из этого описания представлены в следующем утверждении:

(13.35) В каждой фазе σ содержит обращения ровно к k разным элементам. Последующая фаза начинается с обращения к другому (k + 1)-му элементу.

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

(13.36) Алгоритм маркировки порождает не более k промахов за фазу и не более kr промахов за все r фаз.

Для нижней границы оптимума имеется следующий факт:

(13.37) Оптимум порождает не менее r - 1 промахов. Другими словами, f(σ) ≥ r - 1.

Доказательство. Рассмотрим любую фазу, кроме последней, в ситуации непосредственно после первого обращения (к элементу s) в этой фазе. В настоящий момент s находится в кэше, поддерживаемом оптимальным алгоритмом, и из (13.35) следует, что в оставшейся части этой фазы произойдут обращения к k - 1 другим элементам, а в первом обращении следующей фазы также произойдет обращение к k-му другому элементу. Обозначим S это множество из k элементов, отличных от s. Заметим, что по крайней мере один из элементов S в настоящее время не находится в кэше, поддерживаемом оптимальным алгоритмом (так как после s остается место только для k - 1 других элементов), и в оптимальном алгоритме при первом обращении к этому элементу произойдет кэш-промах.

Итак, мы показали, что для каждой фазы j < r последовательность от второго обращения в фазе j до первого обращения в фазе j + 1 приводит по крайней мере к одному промаху в оптимуме. В сумме это дает по крайней мере r - 1 промахов. ■

Объединяя (13.36) и (13.37), мы получаем следующие гарантии эффективности:

(13.38) Для любого алгоритма маркировки количество кэш-промахов для любой последовательности с не превышает k ∙ f(σ) + k.

Доказательство. Количество кэш-промахов, порожденных алгоритмом маркировки, не превышает

где последнее неравенство следует из (13.37). ■

Обратите внимание: “+k” в границе (13.38) представляет собой аддитивную константу, не зависящую от длины последовательности обращений σ, поэтому ключевым аспектом границы является множитель k относительно оптимума. Чтобы понять, что этот множитель k является лучшей возможной границей для некоторых алгоритмов маркировки (и для LRU в частности), рассмотрим поведение LRU для последовательности обращений, в которой k + 1 элементов многократно запрашиваются по кругу. LRU каждый раз будет вытеснять элемент, который понадобится только на следующем шаге, а следовательно, породит промах при каждом обращении. (Такая чудовищная неэффективность кэширования может проявиться на практике ровно по той же причине: программа выполняет цикл, который чуть-чуть велик для кэша.) С другой стороны, оптимальная политика — вытеснение элемента, который потребуется в самом отдаленном будущем, — порождает промах только через каждые k шагов, так что LRU порождает в k раз больше промахов, чем оптимальная политика.

Разработка рандомизированного алгоритма маркировки

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

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

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

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

Анализ рандомизированного алгоритма маркировки

Теперь нам хотелось бы получить для рандомизированного алгоритма маркировки границу более сильную, чем (13.38); но для этого придется немного усложнить анализ из (13.36) и (13.37). Дело в том, что существуют последовательности σ с r фазами, для которых рандомизированный алгоритм маркировки действительно можно заставить порождать kr промахов — представьте последовательность, в которой никогда не повторяются элементы. Однако для таких последовательностей оптимум будет порождать много более r - 1 промахов. Необходимо каким-то образом сблизить верхнюю и нижнюю границы на основании структуры последовательности.

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

Вспомните описание одной фазы, которое привело к (13.35): в начале фазы ни один элемент не помечен, и фаза содержит обращения к k разным элементам, каждый из которых переходит из непомеченного состояние в помеченное при первом обращении. Пусть для этих k обращений к непомеченным элементам в фазе j величина с_j обозначает количество обращений к свежим элементам.

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

Доказательство. Пусть f_j(σ) обозначает количество промахов, порожденных оптимальным алгоритмом в фазе j, и Из (13.35) известно, что в любой фазе j существуют обращения к k разным элементам. Более того, по нашему определению свежих элементов, в фазе j + 1 выдаются обращения к с_j + 1 дальнейшим элементам; таким образом, между фазами j и j + 1 происходят обращения к минимум k + с_j+1 разных элементов. Отсюда следует, что оптимальный алгоритм должен порождать не менее с_j+1 промахов во время фаз j и j + 1 и Условие выполняется даже для j = 0, так как оптимальный алгоритм порождает с₁ промахов в фазе 1. Следовательно, имеем

Но левая сторона не превышает а правая сторона равна

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

(13.40) Для каждой последовательности обращений σ выполняется

Доказательство. Вспомните, что с_j обозначает количество обращений в фазе j к свежим элементам. В этой фазе выдаются k обращений к непомеченным элементам, и каждый непомеченный элемент является либо свежим, либо устаревшим, поэтому в фазе j должно быть k - с_j обращений к непомеченным устаревшим элементам.

Обозначим X_j количество промахов, порожденных рандомизированным алгоритмом маркировки в фазе j. Каждое обращение к свежему элементу приводит к гарантированному промаху для рандомизированного алгоритма маркировки; так как свежий элемент не был помечен в предыдущей фазе, он не может находиться в кэше, когда он запрашивается в фазе j. Следовательно, рандомизированный алгоритм маркировки порождает минимум с_j промахов в фазе j из-за обращений к свежим элементам.

Напротив, с устаревшими элементами дело обстоит сложнее. Фаза начинается с k устаревших элементов в кэше; это элементы, с которых в начале фазы была массово снята пометка. При обращении к устаревшему элементу s возникает проблема: не был ли он вытеснен ранее в этой фазе рандомизированным алгоритмом маркировки и не вызовет ли он теперь промах для возвращения? Какова вероятность того, что i-е обращение к устаревшему элементу (допустим, s) приведет к промаху? Предположим, в этой фазе было c ≤ c_j обращений к свежим элементам. Тогда кэш содержит c ранее свежих элементов, которые сейчас помечены, i - 1 ранее устаревших элементов, которые теперь помечены, и k - c - i + 1 элементов, устаревших и не помеченных в этой фазе. Но всего существует k - i + 1 элементов, которые все еще остаются устаревшими; и поскольку ровно k - c - i + 1 из них находятся в кэше, остальные c там находиться не могут. Каждый из k - i + 1 устаревших элементов с равной вероятностью может отсутствовать в кэше, поэтому s отсутствует в кэше на данный момент с вероятностью — Это вероятность промаха при обращении к s. Суммируя по всем обращениям к непомеченным элементам, получаем

Таким образом, общее ожидаемое количество кэш-промахов, порожденных рандомизированным алгоритмом маркировки, равно

Объединяя (13.39) и (13.40), мы немедленно приходим к следующей гарантии эффективности:

(13.41) Ожидаемое количество промахов, порожденных рандомизированным алгоритмом маркировки, не превышает