Своя СУБД на Haskell · урок 10: vacuum, заморозка и сборка мёртвых версий

Кому это. В прошлом уроке транзакции начали сосуществовать: снимки, эксклюзивные локи строк, детект дедлоков. Движок стал корректным под конкуренцией. Но с уроком 8 в нём копится мусор. DELETE ставит xmax и оставляет версию на странице. UPDATE это пометка старой версии плюс вставка новой. Откатанная вставка оставляет мёртвый кортеж. Удали 300 строк из 400, и таблица не похудеет ни на байт.

Зачем именно Haskell. Сегодня пишем vacuum. Судьба каждой версии (убрать, заморозить, оставить) это чистая функция от реестра статусов, горизонта и самого кортежа, и её результат это тип-сумма из трёх конструкторов. Порядок охранных выражений в ней и есть порядок правил, и его можно проверить таблицей примеров без единой страницы. А проход по куче складывает статистику страниц свёрткой, и уплотнение страницы применяет за один раз уже вычисленный список живых кортежей. Чистое решение, потом одна мутация.

Важно про объём. Это короткий урок: почти вся механика уже готова. Видимость, реестр статусов, снимки и undo-лог есть с урока 8, локи с урока 9. Сегодня новый модуль OurDb.Vacuum, один бит в заголовке кортежа, перепись страницы и метод vacuum у Database. Vacuum в эталоне требует отсутствия открытых транзакций, и это честное упрощение: горизонт по живым снимкам мы посчитаем правильно, но пользоваться им при открытых транзакциях будет упражнение.

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

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

Идея vacuum

Мёртвая версия это кортеж, который не виден и уже не станет виден никакому живому снимку. Таких два рода. Первый: вставка откатанной транзакции. Второй: версия, удалённая зафиксированной транзакцией, чьё удаление видят уже все. Их можно физически стереть.

Горизонт удаляемости это граница, от которой отсчитывают «давно». Нет открытых транзакций, и горизонт это следующий xid: всё зафиксированное удаляемо. Есть, и горизонт это минимальный xmin среди их снимков: старая открытая транзакция держит горизонт и не даёт убрать версии, которые она вправе увидеть.

Заморозка решает отдельную, коварную проблему. xid хранится в заголовке кортежа как u32. Рано или поздно счётчик переполнится и пойдёт по кругу. Тогда древний xmin, раньше «маленький и давно зафиксированный», окажется «большим», то есть будто из будущего, и видимость спрячет вечно живую строку. Это xid-wraparound, и в больших базах это реальная авария: Postgres в такой ситуации останавливает запись. Защита простая: версию, чей xmin старше горизонта (её видят все), помечаем битом frozen, и видимость перестаёт сравнивать её xmin со снимком.

Бит frozen в кортеже

В заголовке кортежа с урока 3 есть 16-битное поле infomask, и в нём занят один бит: «есть NULL-ы». Берём второй.

-- src/OurDb/Constants.hs (добавляем)

-- | Бит infomask: vacuum заморозил версию (урок 10), xmin виден всегда.
infomaskXminFrozen :: Word16
infomaskXminFrozen = 0x0002

-- src/OurDb/Tuple.hs (изменения)

data Tuple = Tuple
  { tupleValues :: ![Value]
  , tupleXmin :: !Int
  , tupleXmax :: !Int
  , -- | xmin заморожен vacuum-ом: версия видна по xmin всегда (урок 10).
    tupleFrozen :: !Bool
  }
  deriving (Eq, Show)

-- | Строка с пустым заголовком (xmin = xmax = 0).
mkTuple :: [Value] -> Tuple
mkTuple values = Tuple values 0 0 False

-- | Та же строка с новым заголовком версии (frozen сбрасывается, как в эталоне).
withHeader :: Int -> Int -> Tuple -> Tuple
withHeader xmin xmax tuple = tuple {tupleXmin = xmin, tupleXmax = xmax, tupleFrozen = False}

freezeTuple :: Tuple -> Tuple
freezeTuple tuple = tuple {tupleFrozen = True}

В типе кортежа флаг это обычное поле Bool, а на диске бит. Сериализация переводит одно в другое в двух местах:

-- src/OurDb/Tuple.hs, serializeTuple (фрагмент)

      infomask =
        (if null nulls then 0 else infomaskHasNull)
          .|. (if tupleFrozen tuple then infomaskXminFrozen else 0)

-- src/OurDb/Tuple.hs, deserializeTuple (фрагмент)

          pure . Right $
            Tuple values (fromIntegral xmin) (fromIntegral xmax) (infomask .&. infomaskXminFrozen /= 0)

withHeader сбрасывает frozen: новая версия, созданная INSERT или UPDATE, всегда начинает незамороженной. Добавление поля в запись ломает все места, где кортеж строится позиционно, и компилятор их перечислит. Это приятная сторона: в TS забытое поле молча стало бы undefined.

Видимость замороженной версии

В isVisible из урока 8 добавляется одно слагаемое:

-- src/OurDb/Snapshot.hs (изменение)

-- | Видна ли версия транзакции self под её снимком. Свои записи видны сразу.
-- Урок 10: версия с поднятым frozen видна по xmin всегда.
isVisible :: Tuple -> Snapshot -> Int -> CommitStatus -> Bool
isVisible tuple snapshot self status = inserterVisible && not deleted
  where
    inserterVisible = tupleFrozen tuple || tupleXmin tuple == self || committedAsOf (tupleXmin tuple) snapshot status
    deleted =
      tupleXmax tuple /= 0
        && (tupleXmax tuple == self || committedAsOf (tupleXmax tuple) snapshot status)

tupleFrozen tuple || стоит первым, и || ленив: для замороженной версии сравнение xmin со снимком не вычисляется вовсе. Заморозка касается только вставки: проверка удаления осталась прежней. Замороженную версию можно удалить и обновить как обычную, xmax у неё работает по старым правилам.

Горизонт удаляемости

Горизонт считает менеджер транзакций: он единственный знает снимки открытых транзакций.

-- src/OurDb/Txn.hs (добавляем)

-- | Горизонт vacuum (RecentGlobalXmin, урок 10): без открытых транзакций следующий xid,
-- иначе минимум snapshot.xmin по открытым.
vacuumHorizon :: TxnManager -> IO Int
vacuumHorizon tm = do
  state <- readState tm
  pure (minimum (tsNextXid state : [snapXmin (activeSnapshot a) | a <- IM.elems (tsActive state)]))

Одна строка, и minimum по непустому списку: следующий xid в голове гарантирует, что список никогда не пуст, а значит, minimum не упадёт. snapXmin в снимке мы завели ещё в уроке 8 «для vacuum», вот он и пригодился. Состояние читается одним readTVarIO, поэтому горизонт считается по согласованной картине: никакая транзакция не «проскочит» между чтением счётчика и карты.

Вердикт: чистая функция и тип-сумма

Теперь сердце урока. Заведи модуль src/OurDb/Vacuum.hs.

-- src/OurDb/Vacuum.hs

-- | Vacuum (урок 10). MVCC копит мусор: DELETE ставит xmax, UPDATE это xmax старой версии
-- плюс новая. Vacuum удаляет версии, мёртвые для всех живых снимков, уплотняет данные на
-- странице, замораживает старые xmin (защита от xid-wraparound) и возвращает место.
--
-- Инвариант: номер слота живого кортежа сохраняется (RID стабилен, индекс не протухает),
-- мёртвый слот становится DEAD_SLOT и больше не переиспользуется.
module OurDb.Vacuum
  ( VacuumStats (..)
  , Verdict (..)
  , classify
  , runVacuum
  , addStats
  , zeroStats
  ) where

data Verdict = Remove | Freeze | Keep
  deriving (Eq, Show)

-- | Судьба версии. Remove: вставка откатана, либо удаление зафиксировано и ушло за
-- горизонт. Freeze: живая, xmin зафиксирован и за горизонтом, ещё не заморожена.
classify :: CommitStatus -> Int -> Tuple -> Verdict
classify status horizon tuple
  | statusOf status (tupleXmin tuple) == Aborted = Remove
  | tupleXmax tuple /= 0 && statusOf status (tupleXmax tuple) == Committed && tupleXmax tuple < horizon = Remove
  | not (tupleFrozen tuple)
      && tupleXmin tuple /= 0
      && statusOf status (tupleXmin tuple) == Committed
      && tupleXmin tuple < horizon =
      Freeze
  | otherwise = Keep

Тип Verdict это три конструктора без полей, и в этом его ценность. В TS вердикт был бы строкой или числом, и опечатка в 'remov' прошла бы тихо. Здесь неполный case по Verdict поймает -Wall, а сравнение == Freeze проверит компилятор.

Охранные выражения проверяются сверху вниз, и порядок здесь это порядок правил.

• Вставка откатана. Автор версии получил Aborted. Такую версию не видел и не увидит никто, кроме, может быть, самого откатившего, которого больше нет. Убрать. Сюда же попадает незнакомый xid выше водяного знака: statusOf считает его откатанным, это мы решили в уроке 8.
• Удаление зафиксировано и ушло за горизонт. xmax есть, его транзакция зафиксирована, и xid меньше горизонта: все живые снимки видят удаление. Убрать.
• Живая, давняя, не замороженная. Не замороженная, xmin не сентинел 0, автор зафиксирован и за горизонтом. Заморозить.
• Всё остальное. Оставить как есть.

Обрати внимание на случай «удалена, но удаление ещё не за горизонтом, а вставка за ним». Первые два правила не сработали, третье сработает: такая версия заморозится, хотя у неё есть xmax. Это правильно. Старые снимки ещё видят её живой, и xmin у неё давно зафиксирован. Заморозка трогает только вставочную половину видимости, а удаление по-прежнему решает xmax. В тесте ниже это verdict 2 8 == Freeze.

Раз вердикт чистый, правила проверяются таблицей примеров:

-- test/Lesson10VacuumSpec.hs (фрагмент)

    it "classify: откатанная вставка и ушедшее за горизонт удаление мертвы, старый xmin замораживается" $ do
      let status = commitStatusFrom [(2, Committed), (3, Aborted), (4, Committed), (8, Committed)]
          verdict xmin xmax = classify status 5 (Tuple [VInt 1] xmin xmax False)
      verdict 3 0 `shouldBe` Remove
      verdict 2 4 `shouldBe` Remove
      verdict 2 8 `shouldBe` Freeze -- удаление за горизонтом ещё видно старым снимкам
      verdict 8 0 `shouldBe` Keep
      classify status 5 (Tuple [VInt 1] 2 0 True) `shouldBe` Keep

Горизонт 5. Вставка xid 3 откатана: убрать. Вставка 2, удаление 4 (оба зафиксированы, 4 меньше 5): убрать. Вставка 2, удаление 8 (8 за горизонтом, старые снимки ещё видят строку): заморозить, xmin давний. Вставка 8 (за горизонтом): оставить. Уже замороженная: оставить, повторно замораживать нечего.

Попробуй сам на виджете: двигай горизонт и смотри, как меняются вердикты версий.