Clock-Sweep

Предпосылки: LRU-кэш (проблема contention).

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

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

* — при промахе поиск жертвы может обойти несколько элементов (в худшем случае O(n))

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

        [buf 0]
           ↑
    [buf 7]   [buf 1]

  [buf 6]   ↻   [buf 2]    ← стрелка движется по кругу

    [buf 5]   [buf 3]

        [buf 4]

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

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

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

• index: key → i (номер слота в буфере)
• buffer[i]: {key, value, usage_count, ...}
• clock_hand: указатель, с какого слота начинать поиск жертвы

Алгоритм

При обращении (cache hit):

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

Счётчик ограничен небольшим лимитом (например, PostgreSQL ограничивает usage_count небольшой константой), чтобы элемент, популярный в прошлом, не “застревал” в кэше навечно — та же проблема cache pollution, что у LFU.

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

Фаза вытеснения требует синхронизации вокруг стрелки и выбранного слота и поэтому может создавать contention, но она случается только при промахах.

Пример timeline

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 — кэша страниц диска в разделяемой памяти, где тысячи backend-процессов конкурируют за доступ. Операционные системы применяют аналогичный алгоритм (CLOCK) для page replacement — вытеснения страниц виртуальной памяти на диск.

Классификация алгоритмов вытеснения

Clock-sweep — одна из аппроксимаций LRU. Полная картина алгоритмов вытеснения:

              Алгоритмы вытеснения
                      │
       ┌──────────────┼──────────────┐
       │              │              │
      LRU            LFU          Random
       │
       ├── Точный LRU (список + хеш)
       │   └── Проблема: contention
       │
       └── Аппроксимации LRU
           ├── Clock-Sweep (PostgreSQL)
           ├── CLOCK (оригинальный)
           └── ARC, 2Q, LIRS...

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

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