Поддержка эквивалентности предопределенному порядку следования
Поскольку недерминированные аспекты современных систем проистекают из неточности ограничений сериализуемости ACID, для достижения полностью предсказуемого поведения мы требуем, чтобы допустимое поведение было эквивалентно одному предопределенному последовательному выполнению.
Простейшим способом, за счет которого протокол управления параллелизмом мог бы гарантировать эквивалентность некоторому порядку выполнения {T0, T1, ..., Tn, было бы устранение всякого параллелизма и выполнение транзакций по очереди в указанном порядке. Однако при наличии современных многоядерных машин схемы, допускающие простой большей части процессоров, очевидно, приводят к неоптимальному использованию компьютерных ресурсов и, соответственно, плохой производительности.
К счастью, можно использовать блокировки, чтобы допустить некоторую параллельность, по-прежнему гарантируя эквивалентность предопределенному порядку следования. Эквивалентности предопределенному порядку следования (равно как и освобождения от тупиковых ситуаций) можно достичь путем ограничения набора допустимых планов выполнения теми, которые обладают следующими свойствами:
-
Упорядоченные блокировки (ordered locking). Для любой пары транзакций Ti и Tj, запрашивающих блокировку некоторой записи r, если i < j, то Ti должна запросить свою блокировку раньше, чем это сделает Tj.
-
Выполнение вплоть до завершения (execution to completion). Каждая транзакция, поступающая в систему, должна продолжать выполняться вплоть до своего завершения – пока она либо не зафиксируется, либо не завершится аварийным образом вследствии детерминированной логики программы. Поэтому, если завершение транзакции по какой-либо причине задерживается (например, из-за аппаратного отказа в пределах системы, поддерживающей реплику базы данных), то система должна поддерживать эту транзакцию активной до тех пор, пока она не завершится, или пока сама эта система-реплика не будет ликвидирована – даже если другие транзакции ожидают освобождения блокировок, удерживаемых блокированной транзакцией.
На практике упорядоченное блокирование обычно реализуется таким образом, что от транзакций требуется запрос всех блокировок сразу после входа в систему, хотя существуют классы транзакций, для которых это может оказаться невозможным. Мы подробно анализируем эти случаи в подразделе 4.2. Однако для целей сравнения, описываемого в следующем разделе, мы рассматриваем очень упрощенную реализацию такой схемы.
Это известный метод предупреждения тупиковых ситуаций. Примером системы, в которой блокировки производятся таким образом, является Postgres-R [13].
В некоторых ситуациях – например, в тех случаях, когда транзакция детерминированным образом застопоривается – может оказаться разумным временно переключиться на традиционную схему выполнения и репликации. Нахождение бесшовной модели переключения "на лету" моделей выполнения может стать увлекательным предметом будущих исследований.
