Своя СУБД на Haskell · урок 2: буферный пул

Кому это. Ты прошёл урок 1: у тебя есть Page поверх ForeignPtr и DiskManager, который двигает 8192 байта между файлом и памятью. Сегодня между движком и диском встанет кэш. Тот же урок есть в TS-треке, и алгоритм здесь дословно тот же. Отличается то, как Haskell держит изменяемое состояние: записи кадров неизменяемы и лежат в Seq за IORef, каждое изменение кадра это явная функция Frame -> Frame, а сами страницы остаются общими изменяемыми буферами.

Важно про код. Как и в прошлый раз, ты пишешь реализацию с нуля, а каждый листинг взят из эталона на Haskell. Буферный пул это первый слой, где появляется нетривиальная политика (вытеснение), и пройти её пальцами полезнее, чем прочитать. Структуры из containers (Seq, IntMap) разобраны в уроке про containers и vector, освежи его, если Seq.adjust' выглядит незнакомо.

Где мы в движке

┌────────────────────────────────────────────────┐
│  Бинарный протокол + TCP-сервер                  │  урок 11
├────────────────────────────────────────────────┤
│  Исполнитель (Volcano) + EXPLAIN                 │  урок 6
│  Парсер, лексер, pretty-printer                  │  урок 5
├────────────────────────────────────────────────┤
│  Vacuum                                          │  урок 10
│  Блокировки (2PL), граф ожидания                 │  урок 9
│  MVCC, менеджер транзакций                       │  урок 8
│  WAL (журнал, redo, recovery)                    │  урок 7
├────────────────────────────────────────────────┤
│  B+Tree индекс                                   │  урок 4
│  Куча (slotted pages, seq scan)                  │  урок 3
├────────────────────────────────────────────────┤
│  Буферный пул (кэш страниц, вытеснение)           │  урок 2  ← мы здесь
│  DiskManager (страницы поверх файла)              │  урок 1
└────────────────────────────────────────────────┘

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

Зачем вообще кэшировать страницы

Представь seq scan по таблице из урока 3: движок читает страницу 0, потом 1, потом 2. Без кэша каждое чтение это системный вызов и поход на устройство. Но нагрузка почти никогда не равномерна. У данных есть локальность: одни страницы (корень индекса, верхушка популярной таблицы) читаются постоянно, другие почти никогда. Если горячую страницу прочитать с диска один раз и дальше держать в памяти, тысячи следующих обращений к ней станут бесплатными.

Это и есть работа буферного пула: кэш фиксированного числа страниц. Когда движок просит страницу, пул сначала смотрит, нет ли её уже в памяти (это попадание), и только если нет, идёт на диск (промах). Память не бесконечна, поэтому кадров ограниченное число. Когда все заняты и нужно место под новую страницу, пул выбирает жертву и вытесняет её. Вся сложность в одном вопросе: какую страницу вытеснить, чтобы не выкинуть ту, что вот-вот понадобится снова.

Pin и dirty: два флага кадра

Прежде чем выбирать жертву, надо понять, какие страницы трогать нельзя. Если куча сейчас читает кортежи прямо из буфера страницы, а пул в этот момент вытеснит её и прочитает в тот же кадр другую страницу, куча увидит чужие байты. Поэтому, пока со страницей работают, она закреплена.

Pin это счётчик, а не замок. Закрепление говорит одно: “эту страницу сейчас используют, не вытесняй”. Несколько читателей могут держать pin на одну страницу одновременно, поэтому это число, а не флаг. Закончив, каждый делает unpin, и когда счётчик падает до нуля, страница снова кандидат на вытеснение. Не путай pin с блокировками транзакций из урока 9: pin живёт, пока идёт работа с буфером, и не имеет отношения к изоляции.

Второй флаг кадра это dirty. Кадр грязный, если страницу в памяти изменили и она разошлась с диском. Чистый кадр можно выбросить молча. Грязный перед вытеснением надо записать. Поэтому unpin принимает флаг: тот, кто менял страницу, сообщает об этом, отпуская её.

Clock: дешёвое приближение LRU

Идеальная политика вытеснения это выкинуть страницу, к которой дольше всего не обращались. Это LRU. Его проблема в цене: чтобы знать порядок, надо при каждом обращении двигать страницу в голову списка. Это изменение общей структуры на каждое попадание.

Clock приближает LRU почти бесплатно. Кадры расставлены по кругу, по ним ходит стрелка. У каждого кадра один ссылочный бит. Обращение к странице просто поднимает бит, списки двигать не надо. Когда нужна жертва, стрелка идёт по кругу:

• кадр запинен, пропускаем, его трогать нельзя;
• у кадра поднят ref-бит, он получает второй шанс: гасим бит и идём дальше;
• первый кадр с погашенным битом и без pin это жертва.

За один полный проход стрелка гасит все поднятые биты, поэтому за два прохода жертва найдётся, если хоть один кадр не запинен. Страница, к которой обращались недавно, переживёт хотя бы один проход. Ровно эту схему, clock-sweep, использует buffer manager в Postgres.

Поиграй с этим вживую. Кнопки сверху запрашивают страницу (fetch и сразу unpin, типичный паттерн чтения). Следи за стрелкой ▼, ref-битами и счётчиками внизу. Запроси одну страницу дважды и посмотри, как поднятый бит спасает её. Запинь кадр и убедись, что стрелка его обходит. Пометь кадр грязным и поймай момент, когда его перед вытеснением пишут на диск.

Если повозился, ты увидел три морали урока. Повторное обращение поднимает ref-бит, и страница получает второй шанс. Запиненный кадр стрелка пропускает, сколько ни проси новые страницы. Грязную жертву перед вытеснением сбрасывают на диск, а чистую выкидывают молча. Теперь запрограммируем.