Оптимальное кэширование: более сложный пример замены - Жадные алгоритмы

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

Задача

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

Именно такая ситуация возникает при работе с иерархиями памяти: существует небольшой объем данных, к которым можно обращаться очень быстро, и большой объем данных, для обращения к которым требуется больше времени; вы должны решить, какие данные следует держать “под рукой”.

Иерархии памяти повсеместно встречались на компьютерах с первых дней их истории. Для начала стоит отметить, что обращения к данным в основной памяти происходят существенно быстрее, чем обращения к данным на жестком диске; с другой стороны, диск обладает много большей емкостью. А это означает, что часто используемые данные лучше хранить в основной памяти и обращаться к диску как можно реже. Тот же принцип на качественном уровне используется встроенными кэшами современных процессоров. Обращение к содержимому осуществляется за несколько тактов, и выборка данных из кэша происходит намного быстрее, чем выборка из основной памяти. Так появляется еще один уровень иерархии; чтение из малого кэша осуществляется быстрее, чем чтение из основной памяти, а последняя работает быстрее диска (но имеет меньший объем). Расширения этой иерархии также встречаются во многих других ситуациях. Например, при работе в браузере диск часто выполняет функции кэша для часто посещаемых веб-страниц, так как чтение данных с диска происходит намного быстрее, чем загрузка по Интернету.

Общим термином “кэширование” называется процесс хранения малых объемов данных в быстрой памяти, чтобы уменьшить время, которое тратится на взаимодействия с медленной памятью. В приведенных примерах встроенный кэш снижает необходимость в выборке данных из основной памяти, основная память выполняет функции кэша для диска, а диск служит кэшем для Интернета. (Подобно тому, как ваш рабочий стол служит кэшем для библиотеки, а отдельные факты, которые вам удается держать в голове без обращения к книге, образуют своего рода кэш для книг на столе.)

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

Конечно, с возникновением проблемы кэширования в разных контекстах приходится учитывать различные факторы, зависящие от технологии. Впрочем, здесь будет использоваться абстрактное представление задачи, лежащее в основе большинства контекстов. В нем рассматривается множество U из n фрагментов данных, хранящихся в основной памяти. Также существует более быстрая память — кэш, способная в любой момент времени хранить k < n фрагментов данных. Будем считать, что кэш изначально содержит множество из к элементов. Мы получаем последовательность элементов данных D = d₁, d₂, ..., d_m из U — это последовательность обращений к памяти, которую требуется обработать; при обработке следует постоянно принимать решение о том, какие к элементов должны храниться в кэше. Запрашиваемый элемент d_i очень быстро читается, если он уже находится в кэше; в противном случае его приходится копировать из основной памяти в кэш и, если кэш полон, вытеснять из него какой-то фрагмент данных, чтобы освободить место для d_i. Такая ситуация называется кэш-промахом; естественно, мы стремимся к тому, чтобы количество промахов было сведено к минимуму.

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

♦ Допустим, имеются три элемента {a, b, c}, размер кэша k = 2 и последовательность

a, b, c, b, c, a, b.

В исходном состоянии кэш содержит элементы а и b. Для третьего элемента последовательности можно вытеснить a, чтобы включить c в кэш; на шестом элементе можно вытеснить c, чтобы вернуть a; таким образом, вся последовательность включает два промаха. Если поразмыслить над этой последовательностью, становится понятно, что любой план вытеснения для этой последовательности должен включать как минимум два промаха.

В условиях реальных вычислений алгоритм управления кэшем должен обрабатывать обращения к памяти d₁, d₂, ..., не располагая информацией о том, какие обращения встретятся в будущем; но для оценки качества алгоритма системные аналитики с первых дней старались понять природу оптимального решения задачи кэширования. Если известна полная последовательность Sобращений к памяти, какой план вытеснения обеспечит минимальное количество кэш-промахов?

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

В 1960-х годах Лес Белади показал, что следующее простое правило всегда приводит к минимальному количеству промахов:

Назовем его “алгоритмом отдаленного использования”. Когда приходит время вытеснить данные из кэша, алгоритм перебирает все элементы в кэше и выбирает тот из них, который будет использоваться как можно позднее.

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

a, b, c, d, a, d, e, a, d, b, c

с k = 3 и элементами {a, b, c}, изначально находящимися в кэше. Правило отдаленного использования создаст план S, которое вытесняет c на четвертом шаге и b на седьмом шаге. Однако существуют и другие планы вытеснения, не уступающие этому. Например, план S', который вытесняет b на четвертом шаге и c на седьмом шаге, обеспечивает такое же количество промахов. Очень легко найти ситуации, в которых планы, построенные по другим правилам, также будут оптимальными; не может ли оказаться, что при такой гибкости отступление от правила отдаленного использования обеспечит реальный выигрыш где-то в конце последовательности? Например, на седьмом шаге нашего примера план S' вытесняет элемент (c), который используется позднее, чем элемент, вытесненный в этой точке алгоритмом отдаленного использования, так как последний вытеснил c ранее.

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

Прежде чем углубляться в анализ, стоит прояснить один важный момент. Все алгоритмы управления кэшем, упоминавшиеся выше, строят планы, которые включают элемент d в кэш на шаге i, если данные d запрашиваются на шаге i и d еще не находится в кэше. Назовем такой план сокращенным — он выполняет минимальный объем работы, необходимый для заданного шага. В общем случае можно представить себе алгоритм, который строит несокращенные планы, а элементы включаются в кэш на тех шагах, на которых они не запрашиваются. Теперь мы покажем, что для любого несокращенного плана существует сокращенный план, который не уступает ему.

Пусть S — план, который может не являться сокращенным. Новый план — сокращение S — определяется следующим образом: на каждом шаге i, на котором S включает в кэш незапрошенный элемент d, наш алгоритм построения “притворяется”, что он это делает, но в действительности оставляет d в основной памяти. Фактически d попадает в кэш на следующем шаге j после того, как элемент d был запрошен. В этом случае кэш-промах, инициированный на шаге j, может быть отнесен на счет более ранней операции с кэшем, выполненной S на шаге i. Следовательно, мы приходим к следующему факту:

(4.11) Сокращенный план заносит в кэш не больше элементов, чем план S.

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

Доказательство оптимальности алгоритма отдаленного использования

Воспользуемся методом замены для доказательства оптимальности алгоритма отдаленного использования. Рассмотрим произвольную последовательность обращений к памяти D; пусть S_FFобозначает план, построенный алгоритмом отдаленного использования, а S* — план с минимально возможным количеством промахов. Сейчас мы постепенно “преобразуем” S в S_FF, обрабатывая одно решение по вытеснению за раз, без увеличения количества промахов.

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

(4.12) Пусть S — сокращенный план, который принимает те же решения по вытеснению, что и S_FF, в первых j элементах последовательности для некоторого j. Тогда существует сокращенный план S', который принимает те же решения, что и S_FF, в первых j + 1 элементах и создает не больше промахов, чем S.

Доказательство. Рассмотрим (j + 1)-е обращение к элементу d = d_j+1. Так как S и S_FF до этого момента были согласованы, содержимое кэша в них не различается. Если d находится в кэше в обоих планах, то решения по вытеснению не требуются (оба плана являются сокращенными), так что S согласуется с S_FF на шаге j + 1, и, следовательно, S' = S. Аналогичным образом, если элемент d должен быть включен в кэш, но S и S_FF вытеснят один и тот же элемент, чтобы освободить место для d, и снова S' = S.

Итак, интересная ситуация возникает тогда, когда d необходимо добавить в кэш, причем для этого S вытесняет элемент f а S_FF вытесняет элемент е ≠ f. Здесь S и S_FF уже не согласуются к шагу j + 1, потому что у S в кэше находится е, а у S_FF в кэше находится f. А это означает, что для построения S' необходимо сделать что-то нетривиальное.

Сначала нужно сделать так, чтобы план S' вытеснял е вместо f. Затем нужно убедиться в том, что количество промахов у S' не больше S. Простым решением было бы согласование S' с S в оставшейся части последовательности; однако это невозможно, так как S и S', начиная с этого момента, имеют разное содержимое кэша. Поэтому мы должны постараться привести кэш S' в такое же состояние, как у S, не создавая ненужных промахов. Когда содержимое кэша будет совпадать, можно будет завершить построение S', просто повторяя поведение S.

А если говорить конкретнее, от запроса j + 2 и далее S' ведет себя в точности как S, пока впервые не будет выполнено одно из следующих условий:

(i) Происходит обращение к элементу g ≠ е, f который не находится в кэше S, и S вытесняет е, чтобы освободить для него место. Так как S' и S различаются только в е и f это означает, что gтакже не находится в кэше S'; тогда из S' вытесняется f и кэши S и S' совпадают. Таким образом, в оставшейся части последовательности S' ведет себя точно так же, как S.

(ii) Происходит обращение к f и S вытесняет элемент е'. Если е' = е, все просто: S' просто обращается к f из кэша, и после этого шага кэши S и S' совпадают. Если е' ≠ е, то S' также вытесняет е' и добавляет е из основной памяти; в результате S и S' тоже имеют одинаковое содержимое кэша. Однако здесь необходима осторожность, так как S' уже не является сокращенным планом: элемент е переносится в кэш до того, как в нем возникнет прямая необходимость. Итак, чтобы завершить эту часть построения, мы преобразуем S' в сокращенную форму используя (4.11); количество элементов, включаемых S', при этом не увеличивается, и S' по-прежнему согласуется с S_FF на шаге j + 1.

Итак, в обоих случаях мы получаем новый сокращенный план S', который согласуется с S_FF на первых j + 1 элементах и обеспечивает не большее количество промахов, чем S. И здесь принципиально (в соответствии с определяющим свойством алгоритма отдаленного использования) то, что один из этих двух случаев возникнет до обращения к е. Дело в том, что на шаге j + 1 алгоритм отдаленного использования вытеснил элемент (е), который понадобится в самом отдаленном будущем; следовательно, обращению к е должно предшествовать обращение к f, и тогда возникнет ситуация (ii). ■

Этот результат позволяет легко завершить доказательство оптимальности. Мы начнем с оптимального плана S* и воспользуемся (4.12) для построения плана S₁, который согласуется с S_FF на первом шаге. Затем мы продолжаем применять (4.12) индуктивно для j = 1, 2, 3, ..., m, строя планы S, согласующиеся с S_FF на первых j шагах. Каждый план не увеличивает количество промахов по сравнению с предыдущим, а по определению S_m = S_FF, поскольку планы согласуются на всей последовательности.

Таким образом, получаем:

(4.13) S_FF порождает не больше промахов, чем любой другой план S* а следовательно, является оптимальным.

Расширения: кэширование в реальных рабочих условиях

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

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

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

Спустя долгое время после практического принятия алгоритма LRU Слитор и Тарьян показали, что для эффективности LRU можно предоставить теоретический анализ, ограничивающий количество промахов относительно алгоритма отдаленного использования. Мы рассмотрим этот анализ, равно как и анализ рандомизированной разновидности LRU, при возвращении к задаче кэширования в главе 13.