Раздел 10 · Databases

Своя СУБД на Haskell · урок 9: конкуренция, блокировки и дедлоки

senior~80 мин

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

Своя СУБД на Haskell · урок 9: конкуренция, блокировки и дедлоки

Кому это. В прошлом уроке у движка появились транзакции и MVCC. DELETE стал журналируемой пометкой xmax, видимость считает чистая функция по снимку, COMMIT форсит журнал, ROLLBACK идёт по undo-логу. Но транзакция была одна: сессионный BEGIN на весь движок, и множество active в снимке всегда пустое.

Зачем именно Haskell. Сегодня транзакции начинают сосуществовать. Появится begin, который возвращает хэндл транзакции, и несколько таких хэндлов могут чередовать операторы. Заработает snapshot isolation, а для записи появится менеджер блокировок с детектом дедлоков. На Haskell менеджер блокировок это учебный пример приёма «чистое ядро, тонкая граница». Все переходы (взять лок, отпустить, найти цикл) это чистые функции над неизменяемой структурой, их тесты вообще не трогают IO. А граница с миром это одна STM-транзакция над TVar. И в ней спрятана главная тонкость урока: конфликт надо вернуть значением из транзакции, а не бросить исключение внутри неё. Иначе STM откатит то самое ребро графа ожидания, ради которого всё затевалось.

Важно про объём и честность. Почти весь фундамент готов: версии, видимость, снимок, менеджер транзакций. Сегодня мы снимаем ограничение и достраиваем сбоку новый модуль OurDb.Lock, пару строк в операторах и хэндл транзакции в Database. Две вещи сделаны ради паритета с однопоточным эталоном на TS, и о них надо сказать сразу. Первая: занятый лок не ждёт, а сразу даёт LockWaitError, оператор падает, транзакция остаётся жива. Вторая: перед движком стоит один мьютекс, и публичные операции идут строго по одной. Почему так, и что понадобилось бы для настоящего ожидания, разберём в конце.

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

┌────────────────────────────────────────────────┐
│  Бинарный протокол + 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
└────────────────────────────────────────────────┘

Две стороны конкуренции

У безопасной конкуренции две стороны, и их важно не путать.

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

Вторая это запись. Тут MVCC мало: если две транзакции меняют одну строку, одно изменение потеряется (lost update). Решение в два слоя. Эксклюзивный лок строки сериализует писателей: пока A держит строку, B на ней ждать не может, и получает отказ. А write-write конфликт (строку уже изменила транзакция, зафиксировавшаяся после моего снимка) ловится проверкой xmax и даёт ошибку сериализации.

Снимок наполняется сам

Начнём с приятного: чтобы заработала изоляция снимков, в менеджере транзакций менять нечего. Вот captureSnapshot из прошлого урока, без изменений:

-- src/OurDb/Txn.hs (написано в уроке 8, читаем заново)

-- | Снимок: активны все открытые кроме самой себя; xmax это self.
captureSnapshot :: Int -> TmState -> Snapshot
captureSnapshot self state =
  let active = IS.delete self (IM.keysSet (tsActive state))
   in Snapshot (minimum (self : IS.toList active)) self active

Он всегда собирал active из ключей карты открытых транзакций. В прошлом уроке открыта была одна, и после IS.delete self множество пустело. Открой две, и снимок второй запишет первую в active. А committedAsOf уже это учитывает:

-- src/OurDb/Snapshot.hs (тоже из урока 8)

committedAsOf :: Int -> Snapshot -> CommitStatus -> Bool
committedAsOf x snapshot status =
  x /= 0 && statusOf status x == Committed && x < snapXmax snapshot && not (IS.member x (snapActive snapshot))

not (IS.member x (snapActive snapshot)) и есть изоляция. Даже если x уже зафиксирована, но на момент моего снимка была активной, её изменения в мой снимок не пролезут. Если A взяла снимок до старта B, то B за границей snapXmax. Если после, то B попала в active. Вся изоляция снимков это условие, написанное заранее, и чистая функция с неизменяемым снимком: снимок A физически не может поменяться, пока B коммитит, потому что это значение, а не ссылка на общий объект.

Менеджер блокировок: чистое ядро

Заведи модуль src/OurDb/Lock.hs. Это сердце урока, и он умещается на экран. Сначала состояние:

-- src/OurDb/Lock.hs

-- | LockManager (урок 8): строгий 2PL. Транзакция берёт эксклюзивный лок ресурса при
-- записи и держит до commit/abort. На конфликте ребро добавляется в граф ожидания и
-- ищется цикл: цикл это дедлок (DeadlockError, жертва запросивший), иначе would-block
-- (LockWaitError: падает statement, ребро ожидания живёт до commit/abort).
--
-- Состояние это чистая структура с чистыми переходами; граница с миром это одна STM-
-- транзакция над TVar. Ошибка возвращается значением, а не throwSTM: исключение в STM
-- откатило бы и запись ребра, а эталон его сохраняет.
module OurDb.Lock
  ( LockManager
  , LockState
  , newLockManager
  , acquire
  , release
  , acquirePure
  , releasePure
  , emptyLockState
  ) where

import Control.Concurrent.STM
import Control.Exception (throwIO)
import qualified Data.IntMap.Strict as IM
import qualified Data.IntSet as IS
import qualified Data.Map.Strict as M
import qualified Data.Set as S
import Data.Text (Text)
import qualified Data.Text as T
import OurDb.Error (DbError (..))

data LockState = LockState
  { -- | Ресурс -> владелец (эксклюзивно).
    lsOwners :: !(M.Map Text Int)
  , -- | Транзакция -> ресурсы, которыми она владеет.
    lsHeld :: !(IM.IntMap (S.Set Text))
  , -- | Граф ожидания: ожидающий -> те, кого он ждёт.
    lsWaitsFor :: !(IM.IntMap IS.IntSet)
  }

newtype LockManager = LockManager (TVar LockState)

emptyLockState :: LockState
emptyLockState = LockState M.empty IM.empty IM.empty

newLockManager :: IO LockManager
newLockManager = LockManager <$> newTVarIO emptyLockState

Три карты. lsOwners говорит, кто держит ресурс (ресурс это текстовый ключ строки, "relationId:page:slot"). lsHeld это обратный индекс: что держит транзакция, чтобы на COMMIT отпустить всё одним проходом. lsWaitsFor это граф ожидания: ожидающий указывает на тех, кого он ждёт. Конструктор LockManager не экспортируется, наружу видно только TVar за newtype и функции над ним.

Теперь переходы. Это чистые функции, и в этом весь фокус.

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

acquirePure :: Int -> Text -> LockState -> (Either DbError (), LockState)
acquirePure xid resource state = case M.lookup resource (lsOwners state) of
  Just owner | owner /= xid ->
    let waiting = state {lsWaitsFor = IM.insertWith IS.union xid (IS.singleton owner) (lsWaitsFor state)}
     in if hasCycle xid (lsWaitsFor waiting)
          then
            ( Left (DeadlockError (T.pack ("deadlock: транзакция " <> show xid <> " откатывается (ждала " <> show owner <> ")")))
            , waiting {lsWaitsFor = IM.adjust (IS.delete owner) xid (lsWaitsFor waiting)}
            )
          else (Left (LockWaitError ("ресурс " <> resource <> " занят транзакцией " <> T.pack (show owner))), waiting)
  _ ->
    ( Right ()
    , state
        { lsOwners = M.insert resource xid (lsOwners state)
        , lsHeld = IM.insertWith S.union xid (S.singleton resource) (lsHeld state)
        }
    )

releasePure :: Int -> LockState -> LockState
releasePure xid state =
  LockState
    { lsOwners = foldr (M.update (\owner -> if owner == xid then Nothing else Just owner)) (lsOwners state) held
    , lsHeld = IM.delete xid (lsHeld state)
    , lsWaitsFor = IM.map (IS.delete xid) (IM.delete xid (lsWaitsFor state))
    }
  where
    held = maybe [] S.toList (IM.lookup xid (lsHeld state))

Прочитай подпись acquirePure: на входе xid, ресурс и старое состояние, на выходе пара из исхода и нового состояния. Это форма s -> (a, s), та же, что у State-монады. Три исхода.

  • Ресурс свободен или уже мой. Регистрируем владение в обеих картах и возвращаем Right (). Повторный захват своего лока проходит по этой же ветке и ничего не меняет по смыслу: M.insert перезапишет того же владельца, S.union не задвоит ресурс.
  • Ресурс чужой, цикла нет. Добавляем ребро «я жду владельца» и возвращаем Left LockWaitError. Новое состояние с ребром тоже возвращаем. Ребро нужно сохранить: следующий запрос, возможно от другой транзакции, должен увидеть, что я жду.
  • Ресурс чужой, и с новым ребром в графе появился цикл. Это дедлок, жертвой становится запросивший. Его ребро к владельцу убираем (IM.adjust (IS.delete owner)), иначе цикл остался бы в графе и ловил бы всех следующих, и возвращаем Left DeadlockError.

releasePure на COMMIT или ABORT снимает всё, что держала транзакция, удаляет её исходящие рёбра и стирает её из чужих списков ожидания. M.update с функцией, возвращающей Nothing, удаляет ключ, но только если владелец и правда я: защита от рассинхрона двух карт.

Поиск цикла это обычный обход в глубину:

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

-- | Есть ли цикл в графе ожидания, достижимый из start (поиск в глубину).
hasCycle :: Int -> IM.IntMap IS.IntSet -> Bool
hasCycle start graph = go IS.empty [start]
  where
    go _ [] = False
    go visited (node : stack) =
      let targets = maybe [] IS.toList (IM.lookup node graph)
          fresh = filter (`IS.notMember` visited) targets
       in start `elem` targets || go (foldr IS.insert visited fresh) (fresh ++ stack)

Нас интересует не любой цикл, а только проходящий через start: именно его новое ребро могло замкнуть круг, остальные циклы (если бы они были) поймали бы раньше. Стек это список, посещённые это IntSet. Обход ленивый в хорошем смысле: || не вычисляет правую часть, как только нашёл start среди соседей.

Граница с миром: одна STM-транзакция

Вот и вся «нечистая» часть менеджера:

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

-- | Взять эксклюзивный лок. Повторный захват своим владельцем это no-op.
acquire :: LockManager -> Int -> Text -> IO ()
acquire (LockManager var) xid resource =
  atomically (stateTVar var (acquirePure xid resource)) >>= either throwIO pure

-- | Освободить все локи и рёбра ожидания транзакции (на commit/abort).
release :: LockManager -> Int -> IO ()
release (LockManager var) xid = atomically (modifyTVar' var (releasePure xid))

stateTVar :: TVar s -> (s -> (a, s)) -> STM a берёт ровно форму acquirePure: прочитать состояние, применить чистый переход, записать новое состояние, вернуть исход. Всё это одна атомарная транзакция. Исход выходит из atomically как обычное значение Either DbError (), и только снаружи, уже в IO, either throwIO pure превращает Left в исключение.

Почему не так?

-- так НЕ делаем
acquireWrong (LockManager var) xid resource = atomically $ do
  (outcome, next) <- acquirePure xid resource <$> readTVar var
  writeTVar var next
  either throwSTM pure outcome

Выглядит аккуратнее: ошибка прямо в транзакции. Но throwSTM внутри atomically откатывает все записи этой транзакции, и исключение вылетает так, будто транзакции не было. Это сильная сторона STM, о ней рассказывал урок про STM: исключение не оставляет память полупропатченной. Здесь же она работает против нас. Состояние с новым ребром ожидания не запишется, граф останется без ребра «A ждёт B», и когда позже B попросит строку A, цикла никто не увидит. Вместо DeadlockError будет вечная пара LockWaitError в обе стороны.

Получается правило, полезное далеко за пределами СУБД: если неудачный исход должен оставить след в состоянии, возвращай его значением из транзакции и бросай уже снаружи. Исключение внутри STM означает «ничего не было», а нам нужно «было, и вот что получилось».

Ошибки конкуренции

Для всех трёх видов ошибки в типе DbError есть свои конструкторы:

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

data DbError
  = SqlError !Int !Text
  | EngineError !Text
  | UniquenessError !Text
  | -- | Write-write конфликт под snapshot isolation (урок 8).
    SerializationError !Text
  | -- | Лок занят без цикла ожидания: падает statement, транзакция жива (урок 8).
    LockWaitError !Text
  | -- | Цикл в графе ожидания: запросившая транзакция это жертва (урок 8).
    DeadlockError !Text
  | StorageError !Text
  deriving (Eq, Show)

instance Exception DbError where
  displayException = T.unpack . errorMessage

Один тип с конструкторами вместо иерархии классов эталона. Проверка «это ошибка дедлока?» это сопоставление с образцом, а в уроке 11 сессия переведёт каждый конструктор в свой SQLSTATE-код.

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

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

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

войти