Случайность против противника: алгоритм с пометками и граница Яо

Если ты знаешь, кого называют «незнающим» противником, как работает алгоритм с пометками и откуда у него гарантия 2Hₖ, и как принцип Яо даёт нижнюю границу Hₖ, листай до «Теперь сам».

Как думаешь, что изменит монетка

Прошлый урок закончился неприятно: против круга из k + 1 страниц любое детерминированное правило промахивается на каждом запросе. Кеш на сто страниц - и в сто раз хуже оптимума. Аренда лыж показала, что монетка снижает отношение с 2 до 1,58. Что она даст кешу?

Ответь себе до чтения: поможет ли случайный выбор жертвы против круга? Противник по-прежнему просит страницы по кругу. Но он больше не знает, какая из них выселена, - и запрос «к только что выселенной» промахивается не всегда, а с вероятностью. Выигрыш оказывается огромным: вместо k - порядка ln k.

На что это похоже

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

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

Механизм: пометки и фазы

Алгоритм с пометками (Фиат и др., 1991):

обращение к странице p:
    p в кеше  → пометить p
    промах    → если все страницы кеша помечены: снять все пометки
                выселить случайную непомеченную; загрузить p; пометить p

Снятие всех пометок начинает новую фазу. Как и у LRU, фаза - наибольший отрезок с k разными страницами; в начале фазы в кеше лежат страницы прошлой фазы.

Откуда 2Hₖ. Страницы фазы делятся на новые (их не было в прошлой фазе) и старые. Пусть новых m. На каждую новую - промах алгоритма. Оптимум за две соседние фазы промахивается хотя бы столько раз, сколько новых во второй из них (в двух фазах вместе больше k разных страниц), поэтому по всем фазам у него не меньше половины суммы новых. Старые страницы промахиваются, только если их случайно выселили до обращения к ним. Самая неудачная очередь обращений: сначала все новые, потом старые по одной. j-я старая страница к моменту обращения выселена с вероятностью не больше m / (k − j + 1): выселено m + промахнувшиеся раньше, и все они выбирались среди непомеченных случайно. Сумма по j даёт m · (Hₖ − Hₘ) ≤ m · (Hₖ − 1), вместе с новыми - m · Hₖ. Против m / 2 у оптимума - отношение 2Hₖ.

Нижняя граница Hₖ (принцип Яо, раздел о случайности). Чтобы доказать, что ни один случайный алгоритм не лучше Hₖ, достаточно предъявить распределение входов, на котором в среднем плох каждый детерминированный. Возьмём запросы к k + 1 странице, каждый - случайная страница. Любой алгоритм держит в кеше k из них, и следующий запрос промахивается с вероятностью 1/(k + 1). Оптимум промахивается раз за фазу, а фаза в среднем длится (k + 1) · Hₖ запросов - столько надо ждать, пока к уже запрошенной странице добавятся остальные k (задача о собирателе купонов). Отношение - Hₖ.

Правило

Против незнающего противника случайный алгоритм с пометками (выселять случайную непомеченную страницу, снимать пометки, когда непомеченных нет) 2Hₖ-конкурентен. По принципу Яо ни один случайный алгоритм не лучше Hₖ: на случайных запросах к k + 1 странице любой детерминированный алгоритм в среднем проигрывает оптимуму в Hₖ раз.

Разбор: круг, который убивал LRU

Тот же круг из k + 1 страниц, восемь оборотов. LRU в прошлом уроке промахивался на всех 32 и 48 запросах, оптимум - 13 и 14 раз. Алгоритм с пометками - двадцать запусков с разными зёрнами, среднее.

import random

def s_pometkami(zaprosy, k, zerno):
    random.seed(zerno)
    kesh = []
    pomecheny = []
    mimo = 0
    for s in zaprosy:
        if s in kesh:
            if s not in pomecheny:
                pomecheny.append(s)
        else:
            mimo = mimo + 1
            if len(kesh) == k:
                svobodnye = []
                for x in kesh:
                    if x not in pomecheny:
                        svobodnye.append(x)
                if len(svobodnye) == 0:
                    pomecheny = []
                    svobodnye = kesh[:]
                kesh.remove(random.choice(svobodnye))
            kesh.append(s)
            pomecheny.append(s)
    return mimo

for k in [3, 5]:
    po_krugu = []
    for povtor in range(8):
        for stranica in range(1, k + 2):
            po_krugu.append(stranica)
    vsego = 0
    for zerno in range(1, 21):
        vsego = vsego + s_pometkami(po_krugu, k, zerno)
    h = 0
    for i in range(1, k + 1):
        h = h + 1 / i
    print(k, len(po_krugu), vsego / 20, round(2 * h, 3))

3 32 21.45 3.667
5 48 24.7 4.567

Столбцы: k, число запросов, среднее число промахов, гарантия 2Hₖ. При k = 3 - 21,45 промаха против 32 у LRU, отношение к оптимуму 21,45 / 13 ≈ 1,65. При k = 5 - 24,7 против 48, отношение 24,7 / 14 ≈ 1,76. LRU на этом круге был хуже оптимума в 2,5 и 3,4 раза, и с ростом k разрыв растёт линейно, а у пометок - как логарифм.

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

Разбор: принцип Яо в цифрах

Две тысячи случайных запросов к k + 1 странице. LRU - представитель детерминированных алгоритмов (любой другой в среднем промахивается так же: каждый раз с вероятностью 1/(k + 1)). Оптимум - алгоритм Белади.

import random

def lru(zaprosy, k):
    kesh = []
    mimo = 0
    for s in zaprosy:
        if s in kesh:
            kesh.remove(s)
        else:
            mimo = mimo + 1
            if len(kesh) == k:
                kesh.pop(0)
        kesh.append(s)
    return mimo

def belady(zaprosy, k):
    kesh = []
    mimo = 0
    for t in range(len(zaprosy)):
        s = zaprosy[t]
        if s not in kesh:
            mimo = mimo + 1
            if len(kesh) == k:
                dalshe = -1
                zhertva = kesh[0]
                for x in kesh:
                    u = t + 1
                    while u < len(zaprosy) and zaprosy[u] != x:
                        u = u + 1
                    if u > dalshe:
                        dalshe = u
                        zhertva = x
                kesh.remove(zhertva)
            kesh.append(s)
    return mimo

random.seed(1)
for k in [3, 5]:
    zaprosy = []
    for i in range(2000):
        zaprosy.append(random.randint(1, k + 1))
    a = lru(zaprosy, k)
    b = belady(zaprosy, k)
    h = 0
    for i in range(1, k + 1):
        h = h + 1 / i
    print(k, a, b, round(a / b, 2), round(h, 2))

3 500 273 1.83 1.83
5 348 147 2.37 2.28

При k = 3 - 500 промахов из 2000, ровно четверть, как и 1/(k + 1). Оптимум - 273. Отношение 1,83 - совпадает с H₃ = 1 + 1/2 + 1/3. При k = 5: 348 (около шестой части) против 147, отношение 2,37 при H₅ ≈ 2,28 - на конечной случайной последовательности отношение колеблется вокруг предела.

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

Что ломается без этого

Ждут от случайности защиты от «знающего» противника. Если противник видит, какую страницу выселили, и выбирает следующий запрос по ней, случайность не помогает: граница снова k. Гарантия 2Hₖ - против противника, записавшего запросы заранее. В жизни запросы почти всегда не зависят от монеток кеша.

Путают ожидание с гарантией на каждый прогон. 2Hₖ - про среднее по монеткам; отдельный прогон может промахнуться больше.

Берут случайное выселение без пометок. Простой «выселить случайную» конкурентен с отношением k, как LRU: без пометок он может выселить только что нужную страницу. Пометки - это память о том, что страница уже понадобилась в этой фазе.

Зачем это в работе

Случайное выселение - не только теория: Redis при нехватке памяти выбирает жертву из небольшой случайной выборки ключей, и это приближение LRU с защитой от худших шаблонов. Процессорные кеши часто используют псевдослучайную замену. Доказательство 2Hₖ объясняет, почему это разумно: случайность ломает шаблоны доступа, на которых детерминированные правила промахиваются каждый раз, - циклические проходы по массиву чуть больше кеша.

Теперь сам

1. Кеш на 4 страницы. Какова гарантия алгоритма с пометками и нижняя граница для случайных алгоритмов?
2. Запросы - случайные среди 11 страниц, кеш на 10. С какой вероятностью промахивается любой алгоритм на каждом запросе?
3. Почему принцип Яо разрешает доказывать границу для случайных алгоритмов, рассматривая только детерминированные?