Раздел 10 · Databases

Своя СУБД на Haskell · урок 7: журнал упреждающей записи и восстановление

senior~90 мин

без входаВойди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти

Своя СУБД на Haskell · урок 7: журнал упреждающей записи и восстановление

Кому это. К этому уроку у тебя собран целый движок на Haskell. В уроке 6 появилась верхняя половина: каталог, binder, планировщик, операторы Volcano поверх Stream. CREATE TABLE, INSERT, SELECT ... WHERE и EXPLAIN уже бегут. Но убей процесс посреди работы, открой базу снова, и часть строк пропадёт.

Зачем именно Haskell. Сегодня закрываем половину этой дыры через журнал упреждающей записи и фазу восстановления. На Haskell здесь видны три вещи. Первая: контрольную сумму CRC-32 мы пишем сами, поверх ByteString, потому что основная библиотека ourdb собирается только из boot-пакетов GHC (base, bytestring, containers, stm, text), а пакетов zlib и digest среди них нет. Вторая: кодек журнала это чистые функции над байтами, а всё, что трогает файл и счётчики, живёт в IO отдельным менеджером. Граница проходит ровно там, где начинается файл. Третья: fsync в base нет вообще. hFlush отдаёт байты операционной системе, но не устройству, поэтому порт зовёт fsync(2) через FFI, и сегодня станет понятно, почему без этого журнал врал бы.

Важно про объём. Это первый из двух уроков про долговечность. Сегодня механика журнала и redo на самом простом пути: одиночная вставка в режиме autocommit. Транзакций, отката и удаления через версии ещё нет, это следующий урок. Эталон examples/our-db/haskell содержит движок уже после урока 11, поэтому модули журнала (OurDb.Crc32, OurDb.Wal) и примитивы файла мы берём оттуда дословно, а связку движка (журнал для кучи, хуки пула, recover, openDatabase) показываем срезом этапа 7, как в решении этапа: без фильтра по COMMIT, без checkpoint и без no-steal, они придут в уроке 8.

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

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

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

Что теряется при падении

Вспомни путь вставки. INSERT зовёт Heap.insertTuple, та кладёт кортеж в страницу буферного пула и отпускает её через unpinPage pool pageId True, то есть грязной. Грязная страница на диск сразу не идёт: пул сбрасывает её лениво, при вытеснении или по flushAll. Для скорости это правильно, диск медленный. Для долговечности смертельно: между вставкой и сбросом страница живёт только в памяти. Процесс убили, и строка исчезла, хотя клиенту мы уже ответили INSERT 0 1.

Решение в журнале. Идея write-ahead такая: перед тем как менять данные, опиши изменение маленькой записью в отдельном файле и форсни на диск журнал. Журнал пишется только в конец, это дёшево, а страницы данных пусть сбрасываются лениво, как раньше. Упали? При старте читаем журнал и заново применяем (redo) всё, что журнал успел зафиксировать, а страницы нет.

Формат записи

Запись журнала самоописывающая: заголовок фиксированной формы, переменный payload и контрольная сумма в хвосте. Формат общий для всех портов ourdb и описан в examples/our-db/SPEC.md, поэтому журнал, записанный TS-движком, читает Haskell-движок и наоборот.

lsn u64 | prev_lsn u64 | xid u32 | type u16 | length u32 | payload | crc32 u32
└──────────────── заголовок, 26 байт ───────────────────┘

Все числа little-endian. Длина заголовка лежит в OurDb.Constants как walRecordHeaderSize = 26. Типы записей опишем перечислением, но в файле лежит голый u16, поэтому перевод делаем в обе стороны явно.

-- src/OurDb/Wal.hs (начало модуля)

-- | Коды типов зафиксированы навсегда; 6 (бывший физический DELETE) снят и не
-- переиспользуется, поэтому CHECKPOINT и SET_XMAX не сдвигаются.
data WalType = WalBegin | WalCommit | WalAbort | WalCreate | WalInsert | WalCheckpoint | WalSetXmax
  deriving (Eq, Show, Enum, Bounded)

walTypeCode :: WalType -> Word16
walTypeCode = \case
  WalBegin -> 1
  WalCommit -> 2
  WalAbort -> 3
  WalCreate -> 4
  WalInsert -> 5
  WalCheckpoint -> 7
  WalSetXmax -> 8

walTypeFromCode :: Word16 -> Maybe WalType
walTypeFromCode code = lookup code [(walTypeCode t, t) | t <- [minBound .. maxBound]]

-- | Разобранная запись. Тип хранится сырым кодом: декодер журнала его не проверяет.
data WalRecord = WalRecord
  { recLsn :: !Word64
  , recPrevLsn :: !Word64
  , recXid :: !Int
  , recType :: !Word16
  , recPayload :: !BS.ByteString
  }
  deriving (Eq, Show)

Почему walTypeCode написан руками, а не через fromEnum? Потому что коды не идут подряд: номер 6 сознательно пропущен, физического DELETE в журнале не будет, удаление станет записью SET_XMAX. С fromEnum пропуск пришлось бы изображать фиктивным конструктором. Обратную функцию walTypeFromCode мы получаем бесплатно: deriving (Enum, Bounded) даёт [minBound .. maxBound], то есть список всех конструкторов, и из него строится таблица соответствий. Добавишь конструктор, и обе стороны обновятся сами, а -Wall напомнит дописать ветку в walTypeCode.

В самой записи тип хранится сырым Word16, а не WalType. Это решение про контракт: декодер журнала проверяет только целостность (длина, CRC), а смысл записи решает recovery. Запись с незнакомым кодом из будущей версии формата не должна ронять чтение всего файла, она просто пропустится веткой _ при redo.

lsn это номер записи, монотонный. prev_lsn пригодится в следующем уроке для цепочки записей одной транзакции, сегодня пишем 0. xid это номер транзакции, а строгие поля (!) нужны, чтобы разобранная запись не таскала за собой невычисленные куски буфера.

CRC-32 своими руками

Контрольная сумма ловит оборванную или побитую запись. Если процесс убили посреди записи, последняя запись окажется неполной, CRC-32 не сойдётся, и мы её отбросим. В Node эту сумму даёт zlib.crc32, в Go hash/crc32. В Haskell есть пакеты digest и zlib, но среди boot-пакетов GHC их нет, а раннер курса собирает основную библиотеку ourdb только из boot-пакетов. Поэтому пишем табличный CRC сами, это тридцать строк.

-- src/OurDb/Crc32.hs

-- | CRC-32 IEEE (как zlib.crc32, полином 0xEDB88320, отражённый) руками, без zlib.
-- Таблица на 256 значений строится один раз и лежит в ByteString по 4 байта на элемент:
-- boot-пакеты курса не включают array, а список с (!!) был бы квадратичным.
module OurDb.Crc32 (crc32) where

import Data.Bits (complement, shiftL, shiftR, xor, (.&.), (.|.))
import qualified Data.ByteString as BS
import qualified Data.ByteString.Builder as B
import qualified Data.ByteString.Lazy as BL
import qualified Data.ByteString.Unsafe as BU
import Data.Word (Word32, Word8)

crc32 :: BS.ByteString -> Word32
crc32 = complement . BS.foldl' step 0xFFFFFFFF
  where
    step crc byte = (crc `shiftR` 8) `xor` entry (fromIntegral ((crc `xor` fromIntegral byte) .&. 0xFF))

entry :: Int -> Word32
entry index = foldr (\i acc -> acc `shiftL` 8 .|. fromIntegral (at (4 * index + i))) 0 [0 .. 3]
  where
    at :: Int -> Word8
    at = BU.unsafeIndex table

-- | Значение таблицы для байта n: 8 сдвигов с условным xor полинома.
table :: BS.ByteString
table = BL.toStrict (B.toLazyByteString (foldMap (B.word32LE . make) [0 .. 255]))
  where
    make :: Word32 -> Word32
    make n = iterate shift n !! 8
    shift c = if c .&. 1 == 1 then 0xEDB88320 `xor` (c `shiftR` 1) else c `shiftR` 1
{-# NOINLINE table #-}

Разберём снизу вверх, это хороший пример того, как Haskell решает задачу «посчитай один раз и храни».

Таблица. Для каждого байта n от 0 до 255 делаем 8 шагов: младший бит единица, значит сдвиг вправо и xor с полиномом 0xEDB88320, иначе просто сдвиг. iterate shift n !! 8 читается буквально: бесконечный список n, shift n, shift (shift n), ... и восьмой его элемент. Ленивость тут к месту: вычислятся ровно девять элементов, остальные никогда. Каждое из 256 значений пишется через Builder как 4 байта little-endian, и таблица целиком становится строгим ByteString на 1024 байта.

Почему ByteString, а не массив. Обычный выбор для такой таблицы это Data.Array или Data.Vector.Unboxed, но пакетов array и vector в наборе раннера нет. Список с !! дал бы O(n) на каждое обращение, то есть 256 шагов на каждый байт журнала. ByteString это непрерывный кусок памяти с индексом за O(1), и BU.unsafeIndex читает байт без проверки границ. Здесь unsafe честный: индекс 4 * index + i по построению лежит в [0, 1023], потому что index это младший байт (.&. 0xFF), а i от 0 до 3. entry собирает четыре байта обратно в Word32 той же раскладкой little-endian.

NOINLINE и CAF. table это верхнеуровневое значение без аргументов, в GHC такое называется CAF. Оно вычисляется лениво при первом обращении и дальше живёт в памяти: ленивость даёт нам «ленивую инициализацию» бесплатно, без флагов и IORef. Прагма NOINLINE страхует от того, чтобы оптимизатор подставил определение table в entry и построил таблицу заново на каждом вызове.

Сам проход. BS.foldl' это строгая свёртка по байтам: начальное значение 0xFFFFFFFF, на каждом байте сдвиг на 8 и xor со значением таблицы, а в конце complement. Штрих в foldl' важен: ленивая foldl накопила бы цепочку из миллиона отложенных step и сосчитала бы её только в конце, с риском переполнить стек. Это ровно та ловушка из урока о ленивости в бою, только в миниатюре.

Проверить реализацию можно на стандартном контрольном значении: CRC-32 строки "123456789" равен 0xCBF43926. В ghci это одна строка: crc32 "123456789" с OverloadedStrings, и полезно один раз сверить её глазами, прежде чем доверять журналу.

Кодек записи

Кодек чистый: на входе значения, на выходе байты, и наоборот. Никакого IO.

-- src/OurDb/Wal.hs (продолжение)

encodeRecord :: Word64 -> Word64 -> Int -> Word16 -> BS.ByteString -> BS.ByteString
encodeRecord lsn prevLsn xid code payload = body <> build (B.word32LE (crc32 body))
  where
    body =
      build $
        B.word64LE lsn <> B.word64LE prevLsn <> B.word32LE (fromIntegral xid) <> B.word16LE code
          <> B.word32LE (fromIntegral (BS.length payload)) <> B.byteString payload

Builder из bytestring это моноид кусков байт: <> склеивает их без копирования, а build (наш помощник из OurDb.Bytes, BL.toStrict . B.toLazyByteString) один раз материализует результат. Порядок байт виден в имени каждой функции: word64LE, word32LE. Тело считаем один раз, по нему CRC, и сумму дописываем в хвост.

Разбор интереснее: он должен пережить мусор в конце файла.

-- src/OurDb/Wal.hs (продолжение)

-- | Все целые записи и смещение сразу за последней. Останавливается на первой оборванной
-- или повреждённой: писатель один, поэтому рваная запись всегда последняя.
decodeWal :: BS.ByteString -> ([WalRecord], Int)
decodeWal bytes = go 0 []
  where
    total = BS.length bytes
    go offset acc
      | offset + walRecordHeaderSize > total = (reverse acc, offset)
      | otherwise = case runGetAt header bytes offset of
          Left _ -> (reverse acc, offset)
          Right (lsn, prevLsn, xid, code, len) ->
            let bodyEnd = offset + walRecordHeaderSize + len
                recordEnd = bodyEnd + 4
                body = BS.take (bodyEnd - offset) (BS.drop offset bytes)
                stored = runGetAt getU32LE bytes bodyEnd
             in if len > pageSize || recordEnd > total || stored /= Right (crc32 body)
                  then (reverse acc, offset)
                  else
                    let record = WalRecord lsn prevLsn (fromIntegral xid) code (BS.drop walRecordHeaderSize body)
                     in go recordEnd (record : acc)
    header = (,,,,) <$> getU64LE <*> getU64LE <*> getU32LE <*> getU16LE <*> (fromIntegral <$> getU32LE)

Заголовок разбирается одним аппликативным выражением: (,,,,) <$> getU64LE <*> ... читает пять полей подряд и складывает их в кортеж. Get из OurDb.Bytes проверяет границы и при выходе за конец возвращает Left, а не роняет процесс. Это важно именно здесь: обрывок заголовка в хвосте файла должен стать «конец журнала», а не исключение.

Дальше три причины остановиться. Длина больше страницы: в поле длины мусор. Запись не помещается до конца файла: её оборвали на полуслове. CRC не сошёлся: байты побиты. Писатель у журнала один и пишет только в конец, поэтому испорченной может быть лишь последняя запись, и всё, что до неё, достоверно.

go копит записи в аккумуляторе в обратном порядке и разворачивает список один раз в конце: дописывать в голову списка дёшево, в хвост дорого. Вторая половина результата это смещение сразу за последней целой записью. С него менеджер журнала продолжит писать, затерев огрызок. BS.take и BS.drop не копируют байты, они дают срез того же буфера, поэтому проход по журналу не аллоцирует ничего, кроме записей.

Payload-кодеки

Сегодня нужны два payload-а: CREATE (DDL проигрывается при старте, чтобы пересобрать каталог) и INSERT (образ кортежа плюс его адрес).

-- src/OurDb/Wal.hs (продолжение)

data InsertPayload = InsertPayload {ipRelationId :: !Int, ipPageId :: !Int, ipSlot :: !Int, ipImage :: !BS.ByteString}
  deriving (Eq, Show)

-- | Таблица в CREATE-записи: id отношения и её DDL (урок 8 сложит их в снимок каталога).
data CheckpointTable = CheckpointTable {ctRelationId :: !Int, ctSql :: !Text}
  deriving (Eq, Show)

u32 :: Int -> B.Builder
u32 = B.word32LE . fromIntegral

getInt32 :: Get Int
getInt32 = fromIntegral <$> getU32LE

encodeInsertPayload :: InsertPayload -> BS.ByteString
encodeInsertPayload (InsertPayload rel page slot image) =
  build (u32 rel <> u32 page <> B.word16LE (fromIntegral slot) <> B.byteString image)

decodeInsertPayload :: BS.ByteString -> Either Text InsertPayload
decodeInsertPayload = runGet (InsertPayload <$> getInt32 <*> getInt32 <*> (fromIntegral <$> getU16LE) <*> getRest)

encodeCreatePayload :: CheckpointTable -> BS.ByteString
encodeCreatePayload (CheckpointTable rel sql) = build (u32 rel <> B.byteString (utf8 sql))

decodeCreatePayload :: BS.ByteString -> Either Text CheckpointTable
decodeCreatePayload = runGet (CheckpointTable <$> getInt32 <*> (fromUtf8 <$> getRest))

CREATE несёт id отношения и DDL-строку, тот канонический SQL, который печатает prettyPrint из урока 5. Тип для неё взят CheckpointTable: пара «таблица и её DDL» в следующем уроке понадобится и в снимке каталога при checkpoint, и заводить второй одинаковый тип незачем. INSERT несёт id, адрес (pageId, slot) и сам образ сериализованного кортежа. Образ это физическое логирование: redo просто положит байты обратно.

Посмотри на декодеры: это та же аппликативная запись, что и у заголовка, InsertPayload <$> getInt32 <*> ..., конструктор записи применяется к четырём разборам по очереди. Результат Either Text: битый payload это значение, а не исключение, и решать, что с ним делать, будет recovery.

WalManager: файл, хвост в памяти и fsync

Теперь сторона IO. Менеджер журнала держит дескриптор файла и четыре изменяемые ячейки.

-- src/OurDb/Wal.hs (продолжение)

data WalManager = WalManager
  { walHandle :: !Handle
  , walWriteOffset :: !(IORef Int)
  , walNextLsn :: !(IORef Word64)
  , walFlushedLsn :: !(IORef Word64)
  , -- | Ещё не сброшенные записи, новые первыми.
    walPending :: !(IORef [BS.ByteString])
  }

-- | Открыть журнал и продолжить нумерацию после существующих целых записей.
openWal :: FilePath -> IO WalManager
openWal path = do
  handle <- openUnlocked path
  (records, validEnd) <- decodeWal <$> readWhole handle
  let maxLsn = if null records then 0 else recLsn (last records)
  WalManager handle <$> newIORef validEnd <*> newIORef (maxLsn + 1) <*> newIORef maxLsn <*> newIORef []

readWhole :: Handle -> IO BS.ByteString
readWhole handle = do
  size <- hFileSize handle
  hSeek handle AbsoluteSeek 0
  BS.hGet handle (fromIntegral size)

-- | Все целые записи журнала с диска (для recovery).
walReadAll :: WalManager -> IO [WalRecord]
walReadAll wal = fst . decodeWal <$> readWhole (walHandle wal)

openWal читает существующий файл целиком, разбирает его чистым decodeWal и продолжает нумерацию lsn с последней целой записи: журнал переживает перезапуски, номера не сбрасываются. Смещение для дозаписи это validEnd, поэтому огрызок оборванной записи будет затёрт первой же новой. Конструктор собирается аппликативно: WalManager handle <$> newIORef ... <*> newIORef ..., по ячейке на поле.

-- src/OurDb/Wal.hs (продолжение)

-- | Дописать запись в память, вернуть присвоенный lsn. На диск она пока не идёт.
walAppend :: WalManager -> Int -> WalType -> BS.ByteString -> Word64 -> IO Word64
walAppend wal xid kind payload prevLsn = do
  lsn <- readIORef (walNextLsn wal)
  writeIORef (walNextLsn wal) (lsn + 1)
  modifyIORef' (walPending wal) (encodeRecord lsn prevLsn xid (walTypeCode kind) payload :)
  pure lsn

-- | Сбросить накопленные записи на диск и форсировать (fsync).
walFlush :: WalManager -> IO ()
walFlush wal = do
  pending <- readIORef (walPending wal)
  when (not (null pending)) $ do
    let batch = BS.concat (reverse pending)
    offset <- readIORef (walWriteOffset wal)
    hSeek (walHandle wal) AbsoluteSeek (fromIntegral offset)
    BS.hPut (walHandle wal) batch
    writeIORef (walWriteOffset wal) (offset + BS.length batch)
    writeIORef (walPending wal) []
  fsyncHandle (walHandle wal)
  readIORef (walNextLsn wal) >>= writeIORef (walFlushedLsn wal) . subtract 1

-- | Правило write-ahead: журнал durable до указанного lsn.
walFlushUpTo :: WalManager -> Word64 -> IO ()
walFlushUpTo wal lsn = do
  flushed <- readIORef (walFlushedLsn wal)
  when (flushed < lsn) $ walFlush wal

closeWal :: WalManager -> IO ()
closeWal = hClose . walHandle

walAppend ничего не пишет на диск: кодирует запись чистым encodeRecord и кладёт её в голову списка walPending. Список «новые первыми» это та же идиома, что в decodeWal: (x :) за O(1), а reverse один раз при сбросе. modifyIORef' со штрихом строгий, иначе в ячейке копилась бы цепочка отложенных (:).

walFlush склеивает накопленное одним BS.concat, пишет одним hPut по сохранённому смещению, обнуляет хвост и только потом зовёт fsyncHandle. Последней строкой поднимается walFlushedLsn: всё, что получило номер до этого момента, теперь на устройстве. walFlushUpTo это правило write-ahead в две строки: если просят долговечность до некоторого lsn, а мы туда ещё не дотянулись, форсим.

Заметь, что walAppend здесь в IO, хотя трогает только память. В Effect-порту этого же урока ровно на этом месте пришлось делить API на синхронную часть и Effect. В Haskell такого выбора нет: чтение и запись IORef это уже IO, а чистая часть журнала (кодек) и так вынесена в отдельные функции без IO вовсе. Граница «чистое против мира» проходит не между методами менеджера, а между encodeRecord/decodeWal и WalManager.

Где живёт fsync

Две функции, на которых держится вся долговечность, лежат в OurDb.Disk: ими же пользуется файл страниц из урока 1.

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

foreign import ccall unsafe "fsync" c_fsync :: CInt -> IO CInt

-- | Открыть файл на чтение и запись, создать при отсутствии, без усечения.
--
-- GHC держит на открытых файлах блокировку "один писатель на процесс", и повторное
-- открытие падает с "resource busy". ourdb, как и эталон на fd, полагается на свою
-- дисциплину, а тесты падения переоткрывают файлы, которые держит "упавший" экземпляр,
-- поэтому блокировку GHC снимаем сразу после открытия.
openUnlocked :: FilePath -> IO Handle
openUnlocked path = do
  handle <- openBinaryFile path ReadWriteMode
  hSetBuffering handle NoBuffering
  handleToFd handle >>= FD.release
  pure handle

-- | fsync(2): Handle без буфера уже отдал байты ОС, осталось форсировать их на устройство.
fsyncHandle :: Handle -> IO ()
fsyncHandle handle = do
  hFlush handle
  fd <- handleToFd handle
  throwErrnoIfMinus1_ "fsync" (c_fsync (FD.fdFD fd))

Здесь три слоя буферов, и важно не спутать их. Первый это буфер самого Handle в куче Haskell. Его мы отключаем через hSetBuffering handle NoBuffering, а hFlush на всякий случай сбрасывает остаток: после него байты отданы операционной системе. Второй слой это page cache ядра: write вернулся, байты в памяти ядра, но не на диске. Выключи питание, и они пропадут. Документация hFlush честно говорит только о буфере Handle, про устройство она ничего не обещает. Третий шаг это fsync(2): системный вызов, который возвращается, только когда данные файла переданы устройству.

В base нет функции hSync, поэтому порт объявляет fsync через FFI одной строкой foreign import ccall unsafe. unsafe тут означает не «опасно», а «вызов не зовёт обратно Haskell-код», поэтому GHC может обойтись без дорогого перехода между рантаймами. handleToFd достаёт из Handle файловый дескриптор, FD.fdFD даёт голое число для C. throwErrnoIfMinus1_ превращает код возврата -1 в исключение IOError с текстом errno: упавший fsync нельзя молча проглотить, иначе движок скажет клиенту «готово» про данные, которых на диске нет.

Вторая тонкость про openUnlocked. GHC держит на каждом открытом на запись файле блокировку «один писатель на процесс»: второй openFile того же пути из того же процесса падает с resource busy. Для движка это лишнее, у него своя дисциплина доступа. А тесты падения как раз открывают второй экземпляр базы на том же каталоге, не закрыв первый, будто процесс убили. Поэтому сразу после открытия блокировка снимается через FD.release. Это одно из немногих мест, где порт отличается от эталона на TS, и в README.md эталона оно отмечено отдельно.

Страница помнит свой redo: insertTupleAt

При восстановлении redo должен положить кортеж ровно в тот слот, что записан в журнале, а не «куда влезет». У страницы из урока 1 был insertTuple, который сам выбирает следующий слот. Redo нужен адресный вариант.

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

-- | Положить кортеж в конкретный слот (redo восстановления, урок 7). Пропущенные слоты
-- остаются нулями (мёртвыми), поэтому пропуск незафиксированной записи не сдвигает соседей.
insertTupleAt :: Page -> Int -> BS.ByteString -> IO ()
insertTupleAt page slot bytes = do
  tupleOffset <- subtract (BS.length bytes) <$> getUpper page
  copyInto page tupleOffset bytes
  setUpper page tupleOffset
  setSlot page slot tupleOffset
  let neededLower = headerSize + (slot + 1) * slotSize
  lower <- getLower page
  when (neededLower > lower) $ setLower page neededLower

Байты ложатся у upper, слот указывает на них, lower поднимается ровно настолько, чтобы покрыть указанный слот. Промежуточные слоты остаются нулями, то есть мёртвыми (deadSlot = 0). Это нужно для верности redo: если между двумя вставками в журнале есть пропуск (в следующем уроке так будет с откатанной вставкой), redo обязан сохранить исходные номера слотов, иначе RID сдвинутся и индекс начнёт врать.

дальше после входа

Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.

Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.

войти