Кеш страниц: LRU, FIFO и оптимум Белади

Если ты знаешь, почему алгоритм Белади оптимален, почему LRU и FIFO k-конкурентны, почему лучше k не может ни одно детерминированное правило и почему LFU не конкурентен, листай до «Теперь сам».

Как думаешь, кого выселять

Кеш на три страницы, запросы 1, 2, 3, 1, 4, …. На запросе 4 кеш полон: 1, 2, 3. Кого выселить? Двойку, которую давно не трогали? Тройку, которая пришла последней? Единицу, к которой обращались чаще всех?

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

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

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

LFU - это «убирать папку, которую реже всех открывал за всю жизнь». Папка прошлогоднего отчёта, открытая сто раз в декабре, будет лежать на столе вечно, а две текущие папки будут меняться местами в шкафу при каждом обращении.

Механизм: оптимум, фазы и противник

Алгоритм Белади (1966). При промахе выселить страницу, следующий запрос к которой дальше всех (или которой больше не будет). Он оптимален: если какой-то план выселяет страницу p раньше q, хотя q нужна позже, их можно поменять ролями, и промахов не станет больше. Это доказательство обменом, как у жадных алгоритмов.

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

в фазе k разных страниц  →  LRU промахивается в фазе
                            не больше k раз: загруженная в фазе
                            страница до конца фазы не выселяется
k страниц фазы + первая страница следующей = k + 1 разных
    →  в кеше на k мест любой план промахивается хотя бы раз
       на каждом таком отрезке
итого: LRU <= k · (число фаз) <= k · OPT + k

Для FIFO довод тот же. Сравнение с оптимумом идёт не по запросам, а по фазам: в фазе LRU ошибается до k раз, а оптимум - хотя бы раз на каждом отрезке от второго запроса фазы до первого запроса следующей.

Нижняя граница k. Противник держит k + 1 страниц и каждый раз просит ту, которой нет в кеше алгоритма. Детерминированный алгоритм промахивается на каждом запросе. Оптимум на тех же запросах, выселяя страницу, нужную позже всех, после заполнения кеша промахивается не чаще раза в k запросов. Добавка в пару промахов на заполнение - обычная часть определения: ALG ≤ c · OPT + b.

LFU. Страница 1 запрошена m раз подряд, потом чередуются 2 и 3. При кеше на две страницы LFU держит 1 (частота m) и выселяет 2 ради 3 и 3 ради 2 - промах на каждом запросе. Оптимум выселяет 1 сразу. Отношение растёт вместе с m без ограничения.

Правило

Оптимум при известном будущем - выселять страницу, нужную позже всех (Белади). LRU и FIFO k-конкурентны: в каждой фазе из k разных страниц они промахиваются не больше k раз, а оптимум - хотя бы раз. Ни одно детерминированное правило не лучше k. LFU не конкурентен: старая популярность занимает место навсегда.

Разбор: одна трасса, четыре правила

promahi моделирует кеш на k страниц: при промахе выселяется страница с наименьшим ключом, а ключ зависит от правила. Для LRU - время последнего обращения, для FIFO - время прихода, для LFU - число обращений, для MIN - минус время следующего обращения (выселяется нужная позже всех).

def sled(zaprosy, t, x):
    for u in range(t + 1, len(zaprosy)):
        if zaprosy[u] == x:
            return u
    return len(zaprosy)

def promahi(zaprosy, k, pravilo):
    kesh = []
    poslednij = {}
    prishyol = {}
    chastota = {}
    mimo = 0
    for t in range(len(zaprosy)):
        s = zaprosy[t]
        chastota[s] = chastota.get(s, 0) + 1
        if s not in kesh:
            mimo = mimo + 1
            if len(kesh) == k:
                # выселяется страница с наименьшим ключом
                klyuchi = {}
                for x in kesh:
                    if pravilo == "LRU":
                        klyuchi[x] = poslednij[x]
                    elif pravilo == "FIFO":
                        klyuchi[x] = prishyol[x]
                    elif pravilo == "LFU":
                        klyuchi[x] = chastota[x]
                    else:
                        klyuchi[x] = -sled(zaprosy, t, x)
                zhertva = kesh[0]
                for x in kesh:
                    if klyuchi[x] < klyuchi[zhertva]:
                        zhertva = x
                kesh.remove(zhertva)
            kesh.append(s)
            prishyol[s] = t
        poslednij[s] = t
    return mimo

trassa = [1, 2, 3, 1, 4, 1, 2, 5, 1, 2, 3, 4, 5, 1, 2, 1, 3, 1, 4, 2]
for pravilo in ["LRU", "FIFO", "LFU", "MIN"]:
    print(pravilo, promahi(trassa, 3, pravilo))

LRU 14
FIFO 13
LFU 11
MIN 10

Двадцать запросов, кеш на три страницы. Оптимум - 10 промахов. LFU на этой трассе лучший из онлайн-правил (11): страница 1 действительно популярна и действительно нужна. LRU - худший (14). Если бы выбор правила решался одной трассой, победил бы LFU - и это была бы ошибка, которую показывает следующий разбор.

Разбор: противник для каждого правила

Те же функции. Сначала круг из k + 1 страниц, восемь оборотов - противник для LRU и FIFO. Потом противник для LFU: страница 1 запрошена m раз, потом m раз пара 2, 3; кеш на две страницы.

def sled(zaprosy, t, x):
    for u in range(t + 1, len(zaprosy)):
        if zaprosy[u] == x:
            return u
    return len(zaprosy)

def promahi(zaprosy, k, pravilo):
    kesh = []
    poslednij = {}
    prishyol = {}
    chastota = {}
    mimo = 0
    for t in range(len(zaprosy)):
        s = zaprosy[t]
        chastota[s] = chastota.get(s, 0) + 1
        if s not in kesh:
            mimo = mimo + 1
            if len(kesh) == k:
                # выселяется страница с наименьшим ключом
                klyuchi = {}
                for x in kesh:
                    if pravilo == "LRU":
                        klyuchi[x] = poslednij[x]
                    elif pravilo == "FIFO":
                        klyuchi[x] = prishyol[x]
                    elif pravilo == "LFU":
                        klyuchi[x] = chastota[x]
                    else:
                        klyuchi[x] = -sled(zaprosy, t, x)
                zhertva = kesh[0]
                for x in kesh:
                    if klyuchi[x] < klyuchi[zhertva]:
                        zhertva = x
                kesh.remove(zhertva)
            kesh.append(s)
            prishyol[s] = t
        poslednij[s] = t
    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)
    print(k, len(po_krugu), promahi(po_krugu, k, "LRU"),
          promahi(po_krugu, k, "FIFO"), promahi(po_krugu, k, "MIN"))
for m in [5, 20]:
    zaprosy = [1] * m
    for povtor in range(m):
        zaprosy = zaprosy + [2, 3]
    print(m, promahi(zaprosy, 2, "LFU"), promahi(zaprosy, 2, "LRU"),
          promahi(zaprosy, 2, "MIN"))

3 32 32 32 13
5 48 48 48 14
5 11 3 3
20 41 3 3

Круг из четырёх страниц при кеше на три: 32 запроса, LRU и FIFO промахиваются все 32 раза, оптимум - 13. Круг из шести страниц при кеше на пять: 48 против 14. Отношение растёт вместе с k, как и обещает нижняя граница: на круге оптимум промахивается примерно раз в k запросов.

Противник для LFU: при m = 5 - 11 промахов против 3 у LRU и оптимума, при m = 20 - 41 против 3. LFU выиграл на первой трассе и проигрывает здесь во сколько угодно раз. LRU на тех же запросах сразу отпустил страницу 1, как и оптимум.

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

Выбирают политику кеша по одной трассе. LFU на обычной трассе выглядит лучше LRU, а на смене режима работы - катастрофа: вчерашние горячие данные не уходят.

Удивляются, что LRU «в k раз хуже оптимума». Это худший случай на специальной последовательности. На реальных запросах с локальностью LRU близок к оптимуму, а если дать ему чуть больше памяти, чем оптимуму, гарантия резко улучшается: при k местах против h у оптимума - k/(k − h + 1) (Слейтор, Тарьян, 1985). Вдвое больший кеш - отношение не больше двух.

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

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

Кеш страниц ОС, буферный пул базы данных, CDN, кеш в памяти приложения - везде есть выбор политики выселения. LRU и его приближения (часы, LRU-K, 2Q, ARC) - стандарт ровно потому, что у LRU доказанный худший случай, а у LFU его нет. Знание нижней границы k объясняет, почему циклический проход больше кеша убивает производительность при любой из обычных политик, и подсказывает лечение: не политика, а больше памяти или другой порядок обхода.

Теперь сам

1. Кеш на две страницы, запросы 1, 2, 3, 1, 2, 3. Сколько промахов у LRU и у MIN?
2. Почему алгоритм Белади нельзя использовать в настоящем кеше?
3. Кеш на 100 страниц. Какое наибольшее отношение к оптимуму может получить LRU и на каком входе?