Задача о кэше

Формулировка

Пусть задана последовательность из [math]n[/math] запросов к внешней памяти. Необходимо решить для каждого запроса: сохранить его значение в кэш размера [math]k[/math] или оставить его во внешней памяти.

Основные определения

Определение:

Кэш попадание (англ. cache hit) — результат обрабатываемого запроса уже хранится в кэше и его можно вернуть мгновенно.

Определение:

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

Определение:

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

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

Определение:

Онлайн алгоритм (англ. on-line algorithm) — алгоритм, который при обработке запроса не знает следующих запросов.

Определение:

Оффлайн алгоритм (англ. off-line algorithm) — алгоритм, которому на вход даются все запросы сразу.

Определение:

[math]\alpha[/math]-оптимальность — свойство онлайн алгоритма, означающее что время работы этого алгоритма на любых входных данных не более чем в [math]\alpha[/math] раз больше, чем у оптимального оффлайнового алгоритма, с точностью до аддитивной константы.

Проблема детерминированных алгоритмов

Теорема (О нижней оценке):

Любой [math]\alpha[/math]-оптимальный онлайн детерминированный алгоритм кэширования имеет [math]\alpha \geqslant k[/math].

Доказательство:

[math]\triangleright[/math]

Обозначим [math]T_\text{opt}(\sigma)[/math] и [math]T_\text{det}(\sigma)[/math] как время работы оптимального и детерминированного алгоритма на входе [math]\sigma[/math]. По определению [math]\alpha[/math]-оптимальности имеем [math]\forall\sigma \; T_\text{det}(\sigma) \lt \alpha \cdot T_\text{opt}(\sigma) + C[/math]. Покажем, что достаточно построить для любого [math]n[/math] такую последовательность запросов [math]\sigma_n[/math], что [math]T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + C_0[/math]. Так как [math]\lim\limits_{n-\gt \infty}T = \infty[/math], получаем [math]\lim\limits_{n-\gt \infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \geqslant k[/math]. С другой стороны можно подставить в неравенство с квантором значение [math]\sigma_n[/math] и получить [math]T_\text{det}(\sigma_n) \lt \alpha \cdot T_\text{opt}(\sigma_n) + C[/math], а потом снова перейти к пределу [math]\lim\limits_{n-\gt \infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha[/math]. Перепишем неравенства в следующем виде [math]k \leqslant \lim\limits_{n-\gt \infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha[/math], откуда очевидно, что [math]\alpha \geqslant k[/math]. Теперь построим [math]\sigma_n[/math]. В последовательности будем использовать только [math]k + 1[/math] различных запросов. Первыми [math]k[/math] запросами возьмём любые различные, а дальше, каждым следующим запросом поставим тот, результата которого нет в данный момент в кэше детерминированного алгоритма. Это хоть и не явное, но корректное задание последовательности, потому что имея алгоритм, мы можем вычислить каждый запрос в [math]\sigma_n[/math] на основе предыдущих. Очевидно, что [math]T_\text{det}(\sigma_n) = n[/math]. Посмотрим как на входе [math]\sigma_n[/math] будет работать следующий, возможно оптимальный оффлайн алгоритм (индекс mopt). Первые k элементов алгоритм добавит в кэш, так как они все различные. Когда случается промах, алгоритм среди значений в кэше и только что обработанного запроса вытесняет то, которое в последующих запросах встречается первый раз как можно позже или не встречается совсем. При таком выборе, следующий кэш промах случится не менее чем через [math]k[/math] запросов. Предположим, что это не так, и кэш промах случился через [math]m \lt k[/math] запросов. Так как количество различных запросов на 1 больше размера кэша, то этот промах произошёл на запросе, который мы вытеснили из кэша в предыдущий раз. Из [math]m \lt k[/math] следует, что есть запросы, которые мы не встретили среди первых [math]m[/math], а значит их первое вхождение будет после того значения, которое мы вытеснили. Получили противоречие, а значит предположение не верно. Оценим время работы возможно оптимального оффлайн алгоритма [math]T_\text{mopt} \leqslant k + \lceil\frac{n-k}{k+1}\rceil \leqslant \frac{n}{k}[/math]. Последнее неравенство выполнено, т.к. [math]n \gg k[/math]. Очевидно [math]T_\text{opt}(\sigma_n) \leqslant T_\text{mopt}(\sigma_n)[/math], откуда [math]T_\text{opt}(\sigma_n) \leqslant \frac{n}{k}[/math] [math]T_\text{det}(\sigma_n) = n = k \cdot \frac{n}{k} \geqslant k \cdot T_\text{opt}(\sigma_n) \Rightarrow T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + 0[/math] Теорема доказана.

[math]\triangleleft[/math]

Вероятностный алгоритм (англ. random marking algorithm)

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

Когда в кэш поступает запрос:

• Если кэш попадание, то просто помечаем значение.
• Если кэш промах
  1. Если все элементы уже помечены, снимаем пометки со всех значений.
  2. Берём случайное не помеченное значение и вытесняeм его, а новое значение помечаем.

Оценка времени работы алгоритма

Будем рассматривать только те запросы, которые ставят метку в кэше. Из алгоритма понятно, что если запрос не ставит метку, то кэш работает с уже помеченным значением, а значит это кэш попадание. Разобьём эти запросы на фазы так, чтобы границей между фазами был запрос, который сбрасывает все пометки. Так, первый запрос в первой фазе — это первый запрос во всей последовательности, а первый запрос в других фазах — это запрос, выполняющий сброс всех пометок. Пронумеруем фазы от [math]1[/math] до [math]p[/math]. Рассмотрим фазу [math]i[/math]. Разделим все значения на 2 множества: старые — которые были в фазу [math]i-1[/math] и новые — все остальные. Обозначим количество новых значений в фазе [math]i[/math] как [math]m_i[/math]. Тогда количество старых будет [math]k-m_i[/math].

Посчитаем матожидание количества промахов на фазе [math]i[/math]. Оно максимально, когда в фазе сначала идут новые значения, а потом старые, потому что тогда каждое новое значение имеет больший шанс вытеснить старое, и при обращении к нему случится кэш промах. Так как на начало фазы [math]i[/math] в кэше хранятся только значения фазы [math]i-1[/math], то понятно, что все новые запросы фазы [math]i[/math] приведут к кэш промаху. Рассмотрим [math]j[/math]-й среди старых запросов. Посмотрим на те значения фазы [math]i-1[/math], которые к текущему моменту были вытеснены или помечены. Заметим, что если значение было помечено, то его уже невозможно вытеснить, а если было вытеснено, то чтобы его пометить, необходимо вытеснить другое значение. [math]j-1[/math] старых значений пометили сами себя, потому что они были в предыдущей фазе, а [math]m_i[/math] пометить себя не могли, а поэтому вытеснили случайное подмножество из остальных [math]k - (j-1)[/math]. Возможно они вытеснили кого-то из первых [math]j-1[/math] старых значений, которые при обработке вытеснили кого-то другого. Главное, что распределение это не меняет. Вероятность того, что [math]j[/math]-й старый запрос приведёт к кэш промаху, равена тому, что он был вытеснен из кэша [math]P_j = \frac{m_i}{k - (j - 1)}[/math].

В итоге, матожидание времени работы алгоритма не превосходит суммы матожиданий кэш промахов на каждой фазе, которое мы ограничили сверху суммой [math]m_i[/math] и матожиданием промахов на старых значениях.

[math] \begin{align} T_\text{rnd} &\leqslant \sum\limits_{i=1}^p\left(m_i + \sum\limits_{j}E(\text{кэш промах на}\; j)\right) = \\ &= \sum\limits_{i=1}^p\left(m_i + \sum\limits_{j=1}^{k-m_i}\frac{m_i}{k-j+1}\right) = \sum\limits_{i=1}^p m_i\left(1 + \sum\limits_{j=1}^{k-m_i}\frac{1}{k-j+1}\right) = \\ &= \sum\limits_{i=1}^p m_i\left(1 + \sum\limits_{j=m_i+1}^{k}\frac{1}{j}\right) = \sum\limits_{i=1}^p m_i(1 + H_k - H_{m_i+1}) \leqslant \sum\limits_{i=1}^p m_iH_k = H_k\sum\limits_{i=1}^p m_i \end{align} [/math]

Теперь оценим снизу время работы оптимального алгоритма. Рассмотрим фазы [math]i[/math] и [math]i-1[/math]. Среди запросов этих фаз всего [math]k + m_i[/math] различных значений, а потому оптимальный алгоритм обязан промахнуться хотябы [math]m_i[/math] раз.

[math] \begin{align} T_\text{opt} &= \sum\limits_{i=1}^{p}E(\text{кэш промах на}\; i) = \\ &= \frac{1}{2}\left(E(\text{кэш промах на}\; 1) + E(\text{кэш промах на}\; p) + \sum\limits_{i=1}^{p-1}\left(E(\text{кэш промах на}\; i) + E(\text{кэш промах на}\; i+1)\right)\right) \geqslant \\ &\geqslant \frac{1}{2}\sum\limits_{i=1}^{p}m_i \end{align} [/math]

Из полученных оценок не сложно вывести:

[math]T_\text{rnd} \leqslant 2H_k \cdot T_\text{opt}[/math]

Алгоритм является [math]2H_k[/math]-оптимальным, или, что более практично, [math]\mathcal{O}(\ln(k))[/math]-оптимальным.

Источники

• A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, N. E. Young, Competitive Paging Algorithms, Journal of Algorithms 12, 685-699 (1991)
• Lecture notes for Brown CS251 - Randomized paging algorithms