Buffer Pool и Clock-sweep: как мы боремся с cache pollution и p99 latency

Один аналитик с одним SELECT count(*) FROM orders способен серьёзно ухудшить p99 latency всего OLTP-трафика. Пока скан читает таблицу страница за страницей, Buffer Pool заполняется «холодными» данными, горячие OLTP-страницы вытесняются, и после окончания скана приложение тянет данные с диска вместо кэша — ровно до тех пор, пока hot working set не прогреется заново. Это классический cache pollution, и с ним рано или поздно сталкивается любая СУБД с честным LRU.

В предыдущей статье мы разобрали API-контракты между слоями OLTP-ядра, USDT/eBPF-наблюдаемость и Adaptive Tuning. Сейчас — разбор Buffer Pool: почему Clock-sweep лучше LRU для конкурентной среды, как BufferRing изолирует сканы от горячего рабочего набора, и почему no-steal это не выбор стиля, а вопрос корректности recovery.

Здесь описана текущая реализация: что работает в коде, какие компромиссы зафиксированы как MVP, где что-то не готово — скажем прямо. За рамками статьи намеренно остаются sharded buffer pool, алгоритмы GCLOCK / CLOCK-Pro / ARC, полный Resource Broker с динамическим перераспределением памяти и bulk write маршрут — это отдельные задачи, у каждой свой дизайн-документ.

Что реализовано на момент публикации: Clock-sweep в основном BufferPool; BufferRing (BulkRead path) в HeapStore::seq_scan_with_strategy; BackpressureCoordinator с тремя источниками давления; все метрики из §7. Что ещё не готово: SQL-планировщик пока не переключает seq_scan на BulkRead автоматически; счётчик clock_sweep_evictions_total в основном пуле ещё не добавлен.

---

1. Cache pollution: почему наивная LRU умирает на смешанной нагрузке

Классический сценарий, который ломает любую базу с честным LRU. У вас есть OLTP-приложение: 99% запросов это короткие точечные чтения по индексу, hot working set спокойно влезает в Buffer Pool, hit ratio под 99%, p99 latency предсказуемая. И тут приходит аналитик и запускает безобидный SELECT count(*) FROM orders или генератор отчётов из BI-системы.

Что происходит дальше с LRU-кэшем:

1. Полный скан читает таблицу страница за страницей.

2. Каждая прочитанная страница помещается в Buffer Pool.

3. Поскольку страница «свежая», LRU держит её сверху списка.

4. Hot OLTP-страницы (например, корни B-tree-индексов) выталкиваются вниз и эвиктятся.

5. После окончания скана hit ratio резко падает, запросы начинают идти в I/O, p99 уезжает на порядок-полтора вверх.

Это и есть cache pollution. Самое неприятное в нём это асимметрия: один аналитик с одним «непринципиальным» запросом способен существенно ухудшить tail latency для всего OLTP-трафика — на время, которое займёт прогрев hot working set заново через random reads с диска.

Корень проблемы в том, что LRU исходит из неявного предположения «недавно прочитанное скоро снова понадобится» (recency = utility). Для OLTP с типичным паттерном Парето (20% страниц получают 80% обращений) это в среднем верно. Для последовательного скана это предположение ровно наоборот: страница уже не понадобится никогда, мы прошли её один раз и идём дальше. LRU не различает эти два случая, потому что у него нет информации о намерении (intent) обращения, только сам факт.

Из этого следуют две архитектурные задачи, которые мы решали:

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

2. Дать сканам отдельный кэш-маршрут (cache bypass), чтобы они не мешали основному рабочему набору.

Обе задачи решаются разными механизмами. Разберём их по очереди.

---

2. Clock-sweep: как мы выбираем жертву

Для основного Buffer Pool мы реализовали Clock-sweep (он же CLOCK, second-chance). Это классика, обкатанная десятилетиями в PostgreSQL и BSD VM, и она нам подходит по нескольким причинам:

• Дешёвое обновление при попадании в кэш. Достаточно выставить один бит (ref_bit = true). Никаких перевешиваний узлов в связном списке, как у honest LRU.

• Эвикция амортизирована. Жертва ищется только в момент, когда нужно освободить место под новую страницу. До этого мы вообще не платим за поддержание порядка.

• Аппроксимация LRU. Страницы, к которым обращались часто, переживают несколько проходов «стрелки» и фактически защищены, как горячие записи в LRU.

Структура данных в нашем BufferPool устроена просто: словарь pages: HashMap<PageId, Page>, стабильный массив frames: Vec<PageId> (физический порядок «циферблата») и позиция стрелки clock_hand: usize. У каждой страницы есть ref_bit, pin_count и флаг dirty. Псевдокод эвикции (см. реальную реализацию):

fn evict_for_insert(&mut self, max_cached_pages: usize) {    // ...    let mut scans_left = self.frames.len().saturating_mul(4).max(1);    while evicted < to_evict && scans_left > 0 && !self.frames.is_empty() {        scans_left -= 1;        if self.clock_hand >= self.frames.len() { self.clock_hand = 0; }        let pid = self.frames[self.clock_hand];        let p = self.pages.get_mut(&pid).unwrap();        // Second chance: страница "горячая", снимаем бит и идём дальше.        if p.ref_bit {            p.ref_bit = false;            self.clock_hand = (self.clock_hand + 1) % self.frames.len();            continue;        }        // Никогда не вытесняем pinned/dirty страницы (no-evict-dirty на eviction-пути).        if p.pin_count != 0 || p.dirty {            self.clock_hand = (self.clock_hand + 1) % self.frames.len();            continue;        }        // Эвикция.        self.pages.remove(&pid);        self.frame_remove(pid);        evicted += 1;    }}

Что здесь важно с точки зрения корректности:

1. Bounded scan. Лимит frames.len() * 4 гарантирует, что метод не зациклится, если все страницы заняты (pinned или dirty). В худшем случае мы вернём управление, не освободив все места, и выше по стеку это превратится в backpressure (об этом ниже).

2. No-evict-dirty. dirty страница никогда не выбирается жертвой: эвикция и flush это разные механизмы, и они ортогональны (см. §5). Важное разграничение: это не то же самое, что классический no-steal — тот запрещает записывать на диск страницы с незакоммиченными изменениями и относится к flush-пути, а не к eviction-пути (подробно в §4.2). В нашем MVP оба ограничения действуют одновременно: no-evict-dirty на eviction-пути и no-steal на flush-пути.

3. Pin count как hard barrier. Если страница залочена для активной транзакции, её невозможно вытолкнуть никаким алгоритмом эвикции, точка.

2.1. Почему именно Clock, а не GCLOCK / CLOCK-Pro / ARC

Честный ответ: потому что это MVP-выбор для correctness-first фазы. Clock даёт хорошую базовую производительность и крайне маленькую поверхность ошибок. Алгоритмы вроде GCLOCK (с usage_count > 1) или CLOCK-Pro (отдельный список тестируемых страниц) дают лучший hit ratio на отдельных классах нагрузки, но добавляют состояние, которое надо корректно обновлять под конкурентным доступом и протестировать property-based на инвариантах.

Возможность апгрейда до GCLOCK или CLOCK-Pro зафиксирована в дизайн-документе, и мы вернёмся к ней, когда будут стабильные бенчмарки и trace-данные с реальных нагрузок. Архитектурно это ровно одна точка изменения, функция evict_for_insert. До тех пор любое усложнение алгоритма было бы premature optimization.

Стоит оговориться: basic CLOCK хорошо справляется с классическим OLTP-паттерном Парето, но на нагрузках с выраженным скользящим временным окном доступа (например, time-series с rolling window) CLOCK-Pro даёт заметно лучший hit ratio — именно потому что умеет различать «горячее прямо сейчас» и «горячее ещё недавно». Насколько этот разрыв существенен на реальной смешанной нагрузке — покажут trace-данные.

2.2. Замечание про конкурентность

Сейчас весь BufferPool живёт за единым Mutex на уровне StorageEngine. Это сознательно простая модель для MVP: легко доказать корректность, легко тестировать, понятная семантика. Мы знаем, что для масштабирования на десятки ядер потребуется шардирование (sharded buffer pool с независимой CLOCK-стрелкой на шард, как в InnoDB), и это явно зафиксировано в дизайн-документе как следующий шаг. Но шардирование — отдельная задача со своими подводными камнями (балансировка между шардами, корректное взаимодействие с дроп-таблицами, метрики per-shard), и её мы оставляем на отдельный релиз. Пока мы не упёрлись в Mutex на бенчмарках, мы не оптимизируем то, что не является узким местом.

На практике порог, при котором mutex на Buffer Pool становится видимым узким местом, сильно зависит от соотношения read/write, размера страниц и scheduler affinity — в разных системах эта точка оказывается где-то между 8 и 32+ параллельными писателями, и она нелинейно зависит от процента dirty-страниц в пуле.

---

3. BufferRing: cache bypass для последовательных сканов

Clock-sweep сам по себе не решает проблему cache pollution. Он лишь делает выбор жертвы дешевле, чем у LRU. Если последовательный скан натащит в пул тысячи страниц с ref_bit = true, через одну прокрутку стрелки они станут кандидатами на эвикцию, и в эту же эвикцию попадут хот-страницы, у которых ref_bit тоже успел сброситься между обращениями.

Чтобы изолировать последовательные сканы от основного пула, мы реализовали отдельную структуру, BufferRing. Это маленький фиксированный кольцевой буфер (по умолчанию 32 страницы, диапазон [4, 256]), куда складываются страницы при сканах с явной подсказкой BufferAccessStrategy::BulkRead. Развилка выглядит так:

BufferAccessStrategy    │    ├─ Normal   ──▶  BufferPool   CLOCK-sweep · pin / unpin · no-steal    │                    │    └─ BulkRead ──▶  BufferRing   32 слота FIFO · read-only · свой на каждый скан                         │                   Дисковый I/O

Hot OLTP-страницы остаются в основном пуле и не страдают от того, что параллельно идёт full table scan. Сканы крутятся в своём маленьком кольце и эвиктят только друг друга.

pub enum BufferAccessStrategy {    /// Обычный OLTP-доступ: страницы идут через основной BufferPool.    Normal,    /// Bulk read: страницы идут через BufferRing,    /// основной пул не трогаем.    BulkRead,    /// Bulk write (зарезервировано под будущие COPY/INSERT batch).    BulkWrite,}

Ring устроен максимально просто: HashMap<PageId, Vec<u8>> и VecDeque<PageId> для FIFO-порядка. При переполнении выбрасываем самую старую страницу (FIFO eviction), без записи на диск, потому что страницы скана read-only по контракту. Каждый scan создаёт свой ring, никакой shared mutability, что снимает класс багов с конкурентным доступом полностью.

Сам seq_scan_with_strategy(BulkRead) теперь работает в streaming-режиме: страницы подгружаются on-demand через StreamingRingPageProvider и пробрасываются итератору, не накапливаясь в памяти. В одной из ранних реализаций ring пытался предзагрузить весь скан и падал на больших таблицах с потерей хвостовых страниц; это исправлено и закрыто property-тестами на произвольный размер таблицы.

Контракт жёсткий и проверяется property-тестами:

• ring_size < 4 или > 256: clamping с warning-записью в лог (fail-safe, не fail-closed: скан всё равно должен отработать).

• Дублирующая вставка той же страницы: no-op (нельзя случайно вытолкнуть страницу при повторном обращении в том же скане).

• Страницы из ring никогда не утекают в основной пул и наоборот.

Метрики: buffer_ring_evictions_total (FIFO-эвикции внутри одного ring), buffer_ring_active_slots (агрегированная ёмкость по всем активным ring-буферам в инстансе) и счётчики жизненного цикла buffer_ring_created_total / buffer_ring_dropped_total. По ним оператор видит и долгоживущие протечки ring-буферов (created сильно опережает dropped), и фактическую конкуренцию за слоты под нагрузкой.

3.1. Честная оговорка: где это работает сейчас

В текущем коде ядра ring уже подключён в HeapStore::seq_scan_with_strategy(BulkRead). Однако SQL-планировщик сейчас по умолчанию использует обычный путь через основной пул. Переход на BulkRead для полных сканов таблицы будет включаться отдельным изменением — с эвристикой «если ожидаемый объём скана > X% от размера пула, переключаться на BulkRead». Это типичный пример, когда нижний слой движка готов раньше, чем оптимизатор научится им пользоваться; мы писали сначала контракт и фундамент, а потом заводим вызывающую сторону.

Кроме того, для значительной части холодных чтений в нашем StorageEngine есть и другой механизм: read_page_bytes_verify читает страницу с диска во временный буфер и не вставляет её в основной BufferPool, если её там не было. Это даёт нам ещё одну точку cache bypass на самом нижнем уровне I/O, её используют, например, проверки целостности и фоновая телеметрия. Идея та же: «прочитал и забыл», без побочного эффекта на hot working set.

3.2. Три bypass-маршрута: сравнение свойств

---

4. Pinning, RAII и no-steal: почему мы никогда не эвиктим dirty

Клиентский код, который работает со страницей, делает это через PinnedPage<'a>, RAII-обёртку над пином. Семантика проста:

let page = engine.pin_page(page_id);// ...работаем со страницей...// Drop автоматически уменьшает pin_count.

Важная деталь: пиннинг в Buffer Pool это просто инкремент рефкаунта, у него нет режимов Shared или Exclusive. Логические блокировки на запись и чтение живут уровнем выше, в LockManager, и применяются к транзакционным сущностям, а не к физическим страницам в памяти. Пиннинг и блокировки решают разные задачи: пиннинг защищает страницу от вытеснения из пула пока с ней работают, а LockManager обеспечивает изоляцию транзакций.

Пока хотя бы один поток держит PinnedPage, страница архитектурно неприкосновенна для эвикции: evict_for_insert пропускает её по pin_count != 0. Это даёт единственно правильную семантику для конкурентного доступа: пока вы работаете со страницей, никто не может выдернуть её из-под вас и подменить байты.

4.1. Эвикция и flush: разные инварианты

Помимо pin_count, у нас есть отдельный набор инвариантов в eligible_to_flush (для writeback) и в evict_for_insert (для эвикции). Они частично пересекаются, но решают разные задачи:

• Эвикция не имеет права выбирать pinned ИЛИ dirty страницу. То, что мы не вытесняем dirty без записи, это просто корректность: иначе мы потеряли бы изменения. Из этого следует, что грязная страница должна сначала пройти через Checkpoint Worker (или явный flush_some_eligible), и только после успешного fsync WAL и pwrite самой страницы она снова становится кандидатом на эвикцию.

• Flush не имеет права записывать страницу, если выполнено хотя бы одно из условий: pin_count != 0, страница содержит изменения незакоммиченной транзакции, page_lsn > txlog_durable_lsn (нарушение WAL-before-data) или страница попадает под backup fence.

4.2. No-steal через O(1) проверку HashSet

Второй пункт из списка выше это и есть классический no-steal в терминологии учебников по транзакционным БД. Точное определение no-steal: грязные страницы с изменениями незакоммиченных транзакций не должны попадать на диск. Зачем: если такая страница уехала на диск, а транзакция потом откатилась или упала, на восстановлении придётся применять UNDO к данным, которые уже физически переписаны, что требует совершенно другой схемы recovery (в стиле ARIES с UNDO-фазой, обязательной для штатного перезапуска).

В нашей реализации no-steal обеспечивается одной строкой в eligible_to_flush:

if uncommitted_pages.contains(&pid) {    return Err(FlushSkipReason::Uncommitted);}

uncommitted_pages это глобальный HashSet<PageId>, в который менеджер транзакций добавляет страницу при первой стейджинг-записи и удаляет при коммите или откате. Стоимость проверки на каждой итерации flush-цикла это O(1). Альтернативный подход (сканировать pending_by_txn по всем активным транзакциям) был бы O(N_txns) и заметно хуже под смешанной нагрузкой с большим числом параллельных писателей. Решение получилось элегантным именно потому, что задача чётко разделена: транзакционный слой ведёт ровно одну глобальную структуру, а flush-путь её только читает.

Зачем нам no-steal: наиболее прямолинейная альтернатива — steal-with-sync-flush — означала бы, что в нашей реализации обычное чтение страницы могло бы внезапно инициировать синхронный fsync в том же потоке, который просто хотел сделать SELECT. Это классический источник микроостановок, которые отлично прячутся под средней латентностью и убийственно влияют на p99/p99.9. Мы не хотим, чтобы пользовательский поток «случайно» стал backpressure-агентом для фонового checkpoint.

Оговорка, которую стоит держать в голове: no-steal создаёт своё давление при длинных batch-транзакциях с большим uncommitted write-set — пул быстро заполняется dirty-страницами, эвикция встаёт, и backpressure ударяет уже по новым писателям, а не по background flush. Это компромисс, а не бесплатная защита.

---

5. Checkpoint vs eviction: ортогональность и почему Unified Storage упрощает дело

В классической архитектуре с per-table файлами Checkpoint это координационная задача с N степенями свободы: какие таблицы флашить первыми, как балансировать I/O между разными файловыми дескрипторами, как избегать write amplification, когда несколько dirty страниц соседствуют логически, но физически лежат в разных файлах.

В нашей модели Unified Storage (общий формат, общий брокер ресурсов, единая адресация страниц через PageId = [table_id:16][local_page_id:48]) Checkpoint Worker имеет принципиально более простую работу:

1. Он берёт dirty_queue из BufferPool (мы поддерживаем его как побочную структуру: VecDeque<PageId> плюс HashSet для дедупликации).

2. Для каждой страницы проверяет eligible_to_flush (WAL durable LSN, отсутствие пина, отсутствие backup fence).

3. Группирует записи по физическому файлу tablespace и пишет батчами с нужным приоритетом I/O.

4. После успешной записи отдаёт страницу обратно в общий пул, теперь она снова clean и снова кандидат на эвикцию.

Никакой глобальной блокировки, никакого «остановись, мир, пока я снимаю чекпоинт». Чекпоинт это просто ещё один потребитель того же I/O-бюджета, которым рулит IoAdvisor (см. предыдущую статью): при приближении к лимиту IOPS он плавно троттлится, чтобы не отбирать пропускную способность у транзакционных I/O пользователя.

Что критично с точки зрения консистентности, так это инвариант WAL-before-data: ни одна dirty страница не может быть записана на диск раньше, чем соответствующая WAL-запись стала durable. Этот инвариант проверяется именно в eligible_to_flush, а не в самом writeback. Такое разнесение защиты означает, что даже если кто-то по ошибке вызовет pwrite напрямую, не пройдя через стандартный путь, мы это поймаем на самом раннем шаге.

---

6. Backpressure: что происходит, когда писатели быстрее, чем диск

Допустим, нагрузка на запись внезапно выросла: dirty pages накапливаются, Checkpoint Worker не успевает, эвикция не может найти clean+unpinned страницу, потому что почти всё либо dirty, либо pinned. Что должно произойти?

Без координации — ничего хорошего. Исторически в storage-слое было три независимых места, где система «давила» на писателей: лимит uncommitted-страниц в Buffer Pool, глубина I/O-очереди и hard cap на max_cached_pages. Каждое работало само по себе, каждое сигнализировало своей метрикой. Когда оператор видел торможение, у него не было единственного ответа на вопрос «почему»: надо было проверять три разных дашборда. Это честный провал наблюдаемости.

Сейчас все три механизма сведены в один BackpressureCoordinator. Каждый источник остаётся изолированной реализацией трейта BackpressureSource, но все они вычисляются через одну точку и репортят в одну метрику — у оператора есть однозначный ответ на вопрос «почему база сейчас тормозит мою запись».

1. UncommittedPagesSource. Сравнивает фактическую долю фреймов с uncommitted page-image deltas с порогом buffer_pool.uncommitted_pages_ratio_hard. При превышении источник возвращает Throttle (в режиме block) или Reject (в режиме fail_fast). Лучше предсказуемо замедлиться, чем выйти за пределы памяти и схватить OOM.

2. WalQueueSource. Проверяет глубину high-priority I/O-очереди. Когда demand-чтения OLTP начинают её насыщать, координатор объявляет Throttle, и низкоприоритетные потребители (prefetch, фоновая warm-up-загрузка) автоматически зажимаются. Логика проста: если пользовательский запрос ждёт I/O, ни один спекулятивный prefetch не имеет права съесть его слот на диске.

3. BufferPoolSource. Введён вместе с hard cap на max_cached_pages. Возвращает Throttle, когда хотя бы один писатель уже припаркован на capacity-cv (condition variable — переменная ожидания, на которой спит поток, ожидающий свободного слота в пуле), и Reject, когда пул ушёл в degraded-режим (любая попытка эвикции встретила полностью pinned набор фреймов — явный сигнал утечки пинов).

Решения координатора объединяются по жёсткому правилу Reject > Throttle > Pass: любой источник, говорящий «отказать прямо сейчас», немедленно выигрывает. Все решения экспортируются в Prometheus как backpressure_throttle_decisions_total{source, decision} (счётчик) плюс backpressure_active_sources (gauge). Само ожидание под backpressure размечается через WaitEvent::BackpressureThrottle в общей таксономии событий ожидания (см. §7), а гистограмма времени ожидания на capacity-cv — buffer_pool_waiter_wait_seconds.

Эта схема является прямым следствием нашего глобального принципа Restrictive by Default (мы разбирали его в первых статьях): когда система упирается в ресурс, она не должна тихо деградировать в надежде «как-нибудь разгрести». Она должна предсказуемо притормозить и громко сигнализировать.

---

7. Observability: как смотреть в Buffer Pool снаружи

Метрики разбиты на два слоя: здоровье пула (кэш, dirty, эвикция) и backpressure с ожиданиями (кто давит и сколько ждут).

Здоровье пула

Backpressure и ожидания

Помимо метрик, у нас по-прежнему работает USDT-инфраструктура из прошлой статьи. Любая операция чтения или записи страницы проходит через WaitEvent::PageRead или WaitEvent::PageWrite, и оператор может в любой момент подключить bpftrace, чтобы построить распределение задержек I/O в микросекундах прямо на живой базе:

bpftrace -e 'usdt:/usr/bin/oltp_server:engine:io_end { @io_lat = hist(arg1); }'

7.1. Оговорка про метрики

Сейчас у нас нет отдельного счётчика clock_sweep_evictions_total для основного пула, мы инкрементируем только метрики ring eviction. Как только мы получим первые значимые цифры с production-style нагрузок, добавим как минимум счётчик эвикций и гистограмму «сколько шагов прошла стрелка до нахождения жертвы». Именно эта гистограмма является лучшим косвенным индикатором того, что пул работает «впритык»: если каждая эвикция требует много обходов, значит, у нас много dirty/pinned страниц и backpressure уже близко.

---

8. Известный технический долг

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

• Sharded buffer pool. Единый Mutex — осознанный MVP-выбор. Триггер для шардирования — измеримый lock contention в perf-lab на 32+ ядрах; пока его нет, оптимизировать нечего.

• Sub-pools per page size. PageId = [table_id:16][local_page_id:48] архитектурно готов к маршрутизации в разные саб-кэши, но сейчас PAGE_SIZE = 16384 захардкожен глобально. Изменение требует миграции формата.

• clock_sweep_evictions_total. Этого счётчика ещё нет (см. §7.1). Он нужен: гистограмма «шагов стрелки до жертвы» — лучший ранний индикатор приближающегося backpressure.

---

9. Заключение

Buffer Pool — одно из тех мест, где разница между «работает» и «работает предсказуемо под смешанной нагрузкой» составляет, наверное, 90% реальной сложности OLTP-движка. Алгоритм эвикции в учебнике помещается на полстраницы; обвязка вокруг него (изоляция сканов, no-steal-политика, корректное взаимодействие с чекпоинтом, backpressure, pin counts, RAII на стороне клиентского кода) — это ещё несколько тысяч строк кода и отдельные слои тестов.

Для MVP мы выбирали последовательно: Clock-sweep вместо CLOCK-Pro/ARC, BufferRing вместо умных политик внутри основного пула, явный no-steal вместо steal-with-sync-flush, единый Mutex вместо ранней оптимизации в шардированный пул. Каждый выбор — осознанный отказ от «красивого» в пользу «доказуемо корректного». Принцип прост: сначала убедиться, что система делает правильное, и только потом думать, как сделать это быстрее.

Дальше по плану: первые масштабные бенчмарки на смешанной нагрузке — в первую очередь сценарий «полный скан плюс OLTP-трафик», именно ради которого и писался BufferRing. Затем детальный разбор SQL-совместимости с PostgreSQL и материал о том, как Adaptive Tuning координирует память между Buffer Pool и кэшем выполнения без разрушения cache locality.