18c0693f

Доводы в пользу недетерминизма


Прежде чем приводить доводы в пользу запрета недерминированного поведения в системах баз данных, важно заново рассмотреть аргументы в пользу его допущения.

Хорошая транзакционная система баз данных должна быть быстрой, гибкой и отказоустойчивой. Особо важной считается способность транзакционных систем обеспечивать высокие уровни изоляции, поддерживая при этом оптимальное использование компьютерных ресурсов. Также желательна поддержка по существу произвольных определяемых пользователями транзакций, представляемых на развитом и выразительном языке запросов.

Исторически решения многих проблем разработки таких систем в очень значительной степени основывались на обсуждавшихся ранее либеральных ограничениях сериализации. Чтобы проиллюстрировать значимость переупорядочивания транзакций для достижения этих целей, рассмотрим гипотетическую транзакционную систему баз данных, работающую под типичной транзакционной рабочей нагрузкой. Когда транзакция поступает в систему, ей назначается поток управления, в котором выполняются операции, составляющие эту транзакцию. В частности, в этом потоке управления запрашиваются нужные блокировки, а при фиксации транзакции накопленные блокировки освобождаются. Предположим, что эта гипотетическая система хорошо спроектирована, что в ней используются безупречная схема управления буферами, эффективный менеджер блокировок, поддерживается высокий уровень локальности, так что хорошо работает кэш. Тогда большинство транзакций выполняется очень быстро, удерживая свои блокировки в течение минимального времени. Конфликты по поводу блокировок возникают редко, и транзакции завершаются после сразу после входа в систему, обеспечивающую отличную пропускную способность.

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

T0: read(A); write(B); read(X);

T1: read(B); write(C); read(Y);

T2: read(C); write(D); read(Z);

Если T0 откладывается при попытке прочитать X, то T1 не получит блокировку по чтению записи B и не сможет продолжать выполняться. В детерминированной системе T2 застрянет вслед за T1 из-за наличия зависимости "чтение-запись" на записи C. Но если мы можем изменить порядок следования, эквивалентность которому будет обеспечиваться, T2 сможет получить требуемую блокировку записи C (поскольку транзакция T1 заблокировалась до того, как запросила блокировку C) и завершить свое выполнение, заняв место перед T0 и T1 в эквивалентном порядке следования. Следовательно, если система требует эквивалентности только некоторому последовательному порядку выполнения, не обязательно тому порядку, в котором транзакции поступают в систему, простаивающие ресурсы можно немедленно начать эффективно использовать для выполнения T2.

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



В своем эксперименте мы реализовали простую рабочую нагрузку, в которой каждая транзакция обращается к 10 записям базы данных, содержащей 106 записей. После поиска каждой требуемой записи во вторичном индексе запрашивается ее блокировка, и запись обновляется. Транзакции являются достаточно короткими: по нашим измерениям, блокировки освобождаются примерно через 30 микросекунд после удовлетворения запроса последней из них. Выполнение рабочей нагрузки происходит в благоприятных условиях до тех пор, пока через одну секунду после начала работы в системе не появляется транзакция, которая запрашивает 10 блокировок, после чего полностью блокируется на одну секунду. После этого она активизируется, освобождает свои блокировки и фиксируется. Мы измеряли пропускную способность каждой системы как функцию от времени, а также вероятность того, что новая поступающая в систему транзакция не сможет полностью выполниться из-за конфликта блокировок. При использовании детерминированной схемы все 10 блокировок каждой транзакции запрашиваются сразу после входа транзакции в систему, а в традиционной системе блокировки запрашиваются последовательно, и выполнение транзакции приостанавливается, если очередную блокировку получить не удалось. В традиционной схеме также реализуется выявление тупиковых ситуаций на основе таймаутов: любая транзакция (кроме первой, медленной транзакции), которая не выполняется в течение заданного промежутка времени, аварийно завершается и запускается заново. Подробности об экспериментальной установке см. в приложении.



Рис.1. Измеренные вероятность конфликта блокировок и транзакционная пропускная способность за интервал времени в три секунды. Две транзакции конфликтуют с вероятностью 0,01%, 0,1% и 1% соответственно.

На рис. 1 показаны результаты нашего исследования застопоренного поведения при разных вероятностях конфликтов блокировок. На графиках показаны вероятности того, что поступающие транзакции не смогут сразу завершиться, а также общая транзакционная пропускная способность как функция от времени.


Отчетливо видны три основных вида поведения:



Этот эксперимент ясно показывает, что в случаях, в которых возможны тупики или приостановка транзакций по каким-то другим причинам, схемы выполнения, обеспечивающие эквивалентность некоторому предопределенному порядку следования, непригодны.Следовательно, в эпоху, когда операции чтения с диска произвольным образом влияют на время выполнения транзакций, единственным жизнеспособным вариантом является недетерминированная схема переупорядочивания транзакций.