Clock-Sweep

Предпосылки: LRU-кэш (порядок по давности на списке + хеш-индекс; LFU и его cache pollution; contention при многопоточном доступе), ссылки, атомарная операция, оценка сложности O(…).

← LRU-кэш | Граф →

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

Дорого здесь не само вытеснение, а то, что обычное чтение трогает общую структуру. Что если при обращении ничего не переставлять, а только оставлять на элементе метку «меня недавно трогали» — а порядок вытеснения восстанавливать лениво, лишь когда понадобится освободить место? Тогда чтение перестаёт конкурировать за общий список. Эту идею и реализует clock-sweep, ценой того, что вытеснение становится приблизительным.

Контракт операций — тот же get/put, что у LRU-кэша:

Операция	Сигнатура	Сложность
Получить значение	get(key) → value	O(1)
Записать значение	put(key, value)	O(1) при попадании в свободный слот

Контракт тот же, что у LRU-кэша, но вытеснение приблизительное. Название «clock» — от стрелки, движущейся по кругу, как часовая; «sweep» — от «сметания» единиц со счётчиков. Второе имя — Second-Chance Algorithm: элемент с ненулевым счётчиком получает «второй шанс».

Элементы кэша лежат в массиве слотов, и по этому массиву ходит по кругу одна стрелка (clock_hand) — как часовая по циферблату:

        [slot 0]
           ^
   [slot 7]   [slot 1]

  [slot 6]  (*)  [slot 2]   (*) -- стрелка идёт по кругу
                            и сметает счётчики
    [slot 5]   [slot 3]

        [slot 4]

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

Вместо точного порядка по давности каждый элемент хранит небольшой счётчик usage_count — метку «как часто его трогали». При обращении счётчик увеличивается, при поиске жертвы — постепенно уменьшается. Это и есть та самая «метка вместо перестановки»: обращение правит только поле самого элемента, а не общий список.

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

Где берётся O(1) доступ по ключу

Clock-sweep — это политика вытеснения: она отвечает на вопрос «кого заменить», но не на вопрос «как найти по ключу».

Чтобы get(key) оставался O(1), нужен отдельный индекс «ключ → номер слота» (как и в LRU-кэше — обычно хеш-таблица). Тогда у структуры три части:

• index: отображение «ключ → номер слота в массиве»;
• buffer[i]: сам слот с полями {key, value, usage_count};
• clock_hand: номер слота, с которого стрелка начнёт следующий поиск жертвы.

Обращение и поиск жертвы

При обращении (попадание в кэш, cache hit):

1. Находим слот по ключу через индекс: i = index[key].
2. Возвращаем buffer[i].value.
3. Атомарно увеличиваем buffer[i].usage_count, но не выше потолка-лимита (насыщение: дальше лимита счётчик не растёт).

Никаких перестановок в общей структуре порядка (как в LRU со списком) — правится только локальная метка использования. Зачем счётчику потолок, станет видно, когда стрелка начнёт его уменьшать.

При поиске жертвы (промах, cache miss — нужного ключа в кэше нет):

Если свободного слота нет, надо кого-то вытеснить — освободить слот под новый элемент. Стрелка идёт по кругу и «сметает» счётчики: у кого счётчик уже ноль — тот и жертва, у остальных счётчик уменьшается на единицу (это и есть «второй шанс»):

loop:
  element = buffer[clock_hand]
  if element.usage_count == 0:
    victim = element            # нашли жертву
    break
  else:
    element.usage_count -= 1    # тратим "второй шанс"
    clock_hand = (clock_hand + 1) % capacity   # шаг по кругу

Здесь capacity — число слотов, а % capacity заворачивает стрелку с последнего слота обратно на нулевой, замыкая круг. Эта фаза правит общую стрелку и выбранный слот, поэтому требует синхронизации и может создавать contention — но случается она только при промахах, а не на каждом обращении.

Как счётчик меняется во времени

Один элемент проживает чередование обращений (счётчик растёт) и проходов стрелки (счётчик падает), пока не дойдёт до нуля и не станет кандидатом на вытеснение:

T=0: элемент загружен,      usage_count = 1
T=1: обращение,             usage_count = 2
T=2: обращение,             usage_count = 3
T=3: стрелка прошла,        usage_count = 2
T=4: стрелка прошла,        usage_count = 1
T=5: обращение,             usage_count = 2
T=6: стрелка прошла,        usage_count = 1
T=7: стрелка прошла,        usage_count = 0 -> кандидат на вытеснение

Почему потолок счётчика — маленькое число

Теперь видно, зачем счётчику нужен потолок. Без него элемент, у которого однажды накопилось usage_count = 1000, потребует 1000 проходов стрелки, чтобы дойти до нуля и быть вытесненным, — даже если он давно никому не нужен. С потолком в 5 хватит максимум 5 проходов: кэш быстро адаптируется, когда обращения смещаются на другие элементы.

Потолок счётчика и стрелка, уменьшающая его при проходе, вместе дают decay (затухание): прошлая популярность не защищает элемент навечно. Именно decay снимает cache pollution, которым страдает LFU (там старый высокий счётчик блокирует вытеснение давно бесполезного элемента): здесь, если элемент перестали трогать, его счётчик неизбежно дойдёт до нуля независимо от того, сколько обращений было раньше.

Где теряется точность

Два элемента, оба usage_count = 1:

Элемент A: последнее обращение 10 секунд назад
Элемент B: последнее обращение 1 секунду назад

LRU знает: вытеснить A (он давнее)
Clock-sweep: видит только счётчики, выберет того, до кого стрелка дойдёт первой

Clock-sweep не различает элементы с одинаковым счётчиком: счётчик грубее, чем точная отметка времени. Это приемлемая потеря точности в обмен на масштабируемость.

Сравнение подходов

Аспект	LRU	LFU	Clock-Sweep
При обращении	4 записи указателей + блокировка	Обновление счётчика	Атомарный инкремент
Точность	Точный порядок по времени	Точный счётчик за всё время	Приблизительный
Cache pollution	Нет	Да (старый счётчик блокирует новые элементы)	Нет (затухание)
Contention	При каждом обращении	При каждом обращении	Только при вытеснении
Масштабируемость	Хуже	Хуже	Лучше

Операция	LRU	Clock-Sweep
Обращение	O(1) + блокировка	O(1), атомарный инкремент
Вытеснение	O(1)	O(n) в худшем случае*

* — в худшем случае стрелка обойдёт все слоты; на практике при нормальной нагрузке — несколько слотов.

Где используется

PostgreSQL использует clock-sweep для shared buffers — кэша страниц диска в разделяемой памяти, где тысячи серверных процессов конкурируют за доступ. Операционные системы применяют тот же по сути алгоритм (CLOCK) для вытеснения страниц виртуальной памяти на диск.

Место среди алгоритмов вытеснения

Clock-sweep — одна из приближённых версий LRU: она аппроксимирует «вытесняй давно не используемое», не платя за точный порядок. Рядом стоят точный LRU (список + хеш, дорогой из-за contention), LFU (по частоте) и тривиальный Random (случайная жертва). Существуют и более изощрённые приближения LRU — ARC, 2Q, LIRS; в этой заметке они не разбираются, важно лишь, что clock-sweep — самое дешёвое из таких приближений.

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

Sources

• PostgreSQL docs (current): https://www.postgresql.org/docs/current/buffer-manager.html
• PostgreSQL source: https://github.com/postgres/postgres/blob/master/src/backend/storage/buffer/README

---

← LRU-кэш | Граф →