Why Sybase/SQL Server/DB2 SERIALIZABLE is not serializable

[tengiz]

Now, this is interesting. I'd readily admit that I may be completely wrong here but my recollection is that at least Sybase had claimed that strict 2PL is what its implementation was.

У меня опять появляется ощущение, что из-за вольностей с терминологией и аббревиатурами мы не понимаем, что мы обсуждаем. Поэтому давайте я попробую привести всё к общему знаменателю:

* 2PL - это 2 phase locking protocol, суть которого в том, что стратегия работы с блокировками состоит в друх фазах: фаза накопления блокировок и фаза освобождения блокировок. Фазы обязаны сделовать именно в этом порядке. Точка. Больше ничего 2PL не утверждает.

* Что конкретно блокировать и в каких случаях - это уже слегка другая история - но одно свойство протокола всегда остаётся в силе: вне зависимости от наличия или отсутствия предикатных блокировок, индексных блокировок, многоуровневых блокировок, блокировок диапазонов ключей, etc. суть 2PL всегда одна и таже - две чёткие фазы работы с блокировками строго следующие друг за другом - начало транзакции, накопление блокировок, затем освобождение блокировок и конец транзакции.

* Есть как минимум две разновидности 2PL протокола - Conservative a.k.a Static 2PL и Strict 2PL:

- Conservative/Static 2PL: все объекты, участвующие в транзакции известны заранее, поэтому все необходимые блокировки берутся сразу одним махом (первая фаза), затем делаются все необходимые манипуляции с данными, как только работа с каким-то подмножеством данных завершается (так как заранее всё известно, то мы точно знаем, что в этой транзакции это подмножествно данных никогда больше трогаться не будет), блокировки, ассоциированные с этим подможеством, могут быть немедленно освобождены (началась вторая фаза), к концу работы транзакции все блокировки постепенно освобождаются. Ни одна из известных мне популярных коммерческих SQL СУБД (включая Sybase) эту разновидность 2PL не использует и никогда не использовала.

- Strict 2PL: заранее ничего не известно, ни набор операций, ни множество объектов затронутых операциями, поэтому блокировки набираются по мере необходимости, и освобождаются только при явном конце транзакции. Все известные мне коммерческие SQL СУБД (включая Sybase) используют эту разновидность 2PL. Ещё раз специально оговариювась, разновидности 2PL не имеют отношения к тому, что конкретно блокируется - объекты, предикаты, ключи, диапазоны и пр. Суть протокола - две фазы работы с любыми блокировками.

Отсюда вопрос:

vc, когда Вы говорите S2PL - Вы что имеете в виду Static 2PL (это как я Вас понимал, но теперь уже сомневаюсь) или Strict 2PL? И почему Вы жёстко увязываете 2PL с тем, что блокируется?

[vc]

Now, this is interesting. I'd readily admit that I may be completely wrong here but my recollection is that at least Sybase had claimed that strict 2PL is what its implementation was.

....

- Strict 2PL: заранее ничего не известно, ни набор операций, ни множество объектов затронутых операциями, поэтому блокировки набираются по мере необходимости, и освобождаются только при явном конце транзакции. Все известные мне коммерческие SQL СУБД (включая Sybase) используют эту разновидность 2PL. Ещё раз специально оговариювась, разновидности 2PL не имеют отношения к тому, что конкретно блокируется - объекты, предикаты, ключи, диапазоны и пр. Суть протокола - две фазы работы с любыми блокировками.

Отсюда вопрос:

vc, когда Вы говорите S2PL - Вы что имеете в виду Static 2PL (это как я Вас понимал, но теперь уже сомневаюсь) или Strict 2PL? И почему Вы жёстко увязываете 2PL с тем, что блокируется?

I've always meant Strict 2PL. (as I wrote in the message you've quoted). Sorry for any possible ambiguity, it's entirely my fault.

И почему Вы жёстко увязываете 2PL с тем, что блокируется?

I don't. I've just been saying that Strict 2PL when applied to r/w operations over some data items (the traditional serializabilty subject) guarantees serializable histories for static data sets without requiring any additional mechanism like index range locking.

[tengiz]

I've just been saying that Strict 2PL when applied to r/w operations over some data items (the traditional serializabilty subject) guarantees serializable histories for static data sets without requiring any additional mechanism like index range locking.

vc, но это верно только для практичевски неприменимого подможества SQL операций, о чём у нас идёт речь уже вторую страницу. И дело не только в ограничениях на предикаты, как Вы полагаете. Дело в динамическом характере транзакций - если бы можно было увидеть всю транзакцию целиком, то тогда можно было бы ещё что-то разумное попробовать сделать - но это нереально для современных интерактивных систем, когда транзакция типично состоит из более, чем одного шага взаимодействия СУБД с клиентским приложением. И даже в том случае, если бы это было так, всё равно есть неопределённость связанная с тем, что поток выполнения транзакций может зависеть от данных, прочитанных транзакцией.

[tengiz]

И ещё пара слов насчёт того, как старый Sybase (и, соответственно, SQL Server до версии 6.5 включительно) мог обеспечивать строгую сериализуемость без специальных усилий на реализацию предикатных блокировок (когда у этих продуктов ещё не было row/key-level блокировок, а минимальной единицей блокирования была страница). Дело в том, что физическая структура индексов со связами между соседними логическими страницами фактически реализует диапазонные блокировки, когда это необходимо. Протоколы блокировок для serializable, в результате, были гениально простыми, практически не отличались от протокола дла repeatable read и были заметно проще для понимания, чем те, что используются сейчас в современных версиях SQL Server, DB2 или Sybase.

[vc]

I've just been saying that Strict 2PL when applied to r/w operations over some data items (the traditional serializabilty subject) guarantees serializable histories for static data sets without requiring any additional mechanism like index range locking.

vc, но это верно только для практичевски неприменимого подможества SQL операций, о чём у нас идёт речь уже вторую страницу. .

I quite agree that the SQL subset amenable to serialization theory is rather tiny. However, the current serialization theory is the best we have. It has nothing to say about predicates; the seriliazability theorem does not take into consideration phantoms at all, etc. One cannot claim that some locking scheduler has a firm theoretical foundation without reformulating the statement in terms of the rather limited current serializability theory or extending the latter properly to permit a statement like that. Probably I should have said this from the very beginning and just refused to discuss the SQL statements you've presented as intractable by the theory -- we would not have wasted all those pages ;)

Speaking of key range locking, as far as I am aware, there is no formal proof yet that key range locking ensures serilizability (I am pretty sure it does). At least the DB2 key range locking implementation does not comply with Strict 2PL due to the fact that locking a key on delete does not last until commit (which may be OK but there is no proof that it's OK). See Mohan, C., "Concurrency Control and Recovery Methods for B+-Tree Indexes: ARIES/KVL and ARIES/IM".

As to SQL Server 2K, it appears that its REPEATABLE READ is just a faithful implementation of Strict 2PL with all the problems thereof. Its SERIALIZABLE merely adds key range locking if possible or table locking otherwise in order to ensure serializable histories. These last remarks are simply a call for criticism/clarification ;)

[vc]

И ещё пара слов насчёт того, как старый Sybase (и, соответственно, SQL Server до версии 6.5 включительно) мог обеспечивать строгую сериализуемость без специальных усилий на реализацию предикатных блокировок (когда у этих продуктов ещё не было row/key-level блокировок, а минимальной единицей блокирования была страница).

Yeah, that's the one (Sybase) I had to deal with quite a while ago. It was very much serializable being serial most of the time.

[tengiz]

However, the current serialization theory is the best we have. It has nothing to say about predicates; the seriliazability theorem does not take into consideration phantoms at all, etc. One cannot claim that some locking scheduler has a firm theoretical foundation without reformulating the statement in terms of the rather limited current serializability theory or extending the latter properly to permit a statement like that.

vc, я так и не пойму, какие формальные доказательства корректности 2PL с предикатными блокировками Вы ищете. Частный случай реализации предикатных блокировок в виде блокировок диапазонов ключей прекрасно ложится на классическую теорию расширенную для многуровневых блокировок, и её выводы немедленно распространяются на такие системы.

Позволю себе напомнить, что с точки зрения протокола использующего диапазонные блокировки, ресурсом, на который можно наложить блокировку, кроме собственно значения ключа, является такой полуинтервал - (предыдущее значение ключа, значение ключа], включая и "логически", но не физически удалённые ключи и диапазоны ими порождаемые. Соответственно, объектом манипуляции с точки зрения операций блокирования, чтения и записи тоже является диапазон ключа. Особенностью таких диапазонов является тот факт, что любой индекс содержит как минимум один полуинтервал - (минус бесконечность, максимально возможное значение ключа] в случае когда индекс пуст. Добавление реальных записей в индекс всего лишь дробит исходный полуинтервал. Собственно ключ считается ресурсом, подчинённым диапазону (который подчинён странице, etc.), что сразу сводит такую схему к обычным многоуровневым блокировкам.

Кроме того вот уже почти как 15 лет назад появилось расширение формальной теории на многуровневые транзакции - что по факту и происходит когда используется multigranular locking в сочетании с механизмом "коротких" блокировок aka latches и где "внутренние" транзакции могут быть зафиксированы до того, как это сделает главная транзакция и для некоторых из ресурсов которых возможно немедленное освобождение блокировок. Возможно именно это Вас и смутило в работе Мохана.

[vc]

vc, я так и не пойму, какие формальные доказательства корректности 2PL с предикатными блокировками Вы ищете. Частный случай реализации предикатных блокировок в виде блокировок диапазонов ключей прекрасно ложится на классическую теорию расширенную для многуровневых блокировок, и её выводы немедленно распространяются на такие системы.

For example, it's assumed that generic predicate locking happens "all at once" for a given predicate while with key range locking a transaction may take a partial set of S index range locks, then collide with another transaction performing a row update, and would need to wait, whilst some other transactions' X lock attempts may wait on the first transaction's S locks gotten so far. As far as I know, there is no rigorous treatment of this scenario as yet.

Кроме того вот уже почти как 15 лет назад появилось расширение формальной теории на многуровневые транзакции - что по факту и происходит когда используется multigranular locking в сочетании с механизмом "коротких" блокировок aka latches и где "внутренние" транзакции могут быть зафиксированы до того, как это сделает главная транзакция и для некоторых из ресурсов которых возможно немедленное освобождение блокировок. Возможно именно это Вас и смутило в работе Мохана.

Yeah, he talks about latching the index leaf node until a insert/delete completes but again in an informal way.

To put it simply, there is no "extended locking theorem" proof that takes into account key range locking explicitly. What we have now is just the simple stuff about Strict 2PL ensuring serializability for static databases. If I am wrong and there is some formal treatment of time-extended index-based locking, please point me to the text.

[tengiz]

vc,

Позволю себе повторить, что формальная теория многоуровневых транзакций существует уже лет 15 (я знаю как минимум две работы - Бернштайна и Пападимитриу). Одним из известных результатов является тот простой факт, что элементарные действия на любом уровне выполнения транзаций необязательно должны быть атомарными, а на самом деле могут быть суб-транзакциями, дробимыми на более мелкие действия, которые, в свою очередь, тоже могут представлять из себя сложные действия. Разумеется при соблюдении некоторых формальностей. Обновление и независимая фиксация некоторых изменений в отдельных страницах до конца работы основной пользовательской транзкции - один из примеров такого элементарного действия, не сводящегося к атомарной операции.

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

Как только доберусь до работы - постараюсь найти и выложить ссылки на соответствующие тексты.

P.S. Похоже у Вас уже не осталось сомнений в том, классическая теория полноценно применима к предикатным блокировкам тоже (для чего всего лишь нужно в словаре вместо data item говорить data set defined by a predicate) - судя по последнему сообщению единственная проблема - сводимость неатомарного накопления диапазонных блокировок к предикатным.

[vc]

судя по последнему сообщению единственная проблема - сводимость неатомарного накопления диапазонных блокировок к предикатным.

That's the main problem, yes. Informally, I was convinced when I read Mohan's stuff some years ago that key range locking does what it claims to do. I'd like to see a formal proof. Until I see one, I imagine it's more correct to say that key range locking sometimes produces the same results as straight predicate locking would. It's incorrect to say that key range locking is an implementation of some useful predicate locking functionality subset until there is a formal proof of this statement. I'd also be happy with a proof that key range locking (without any refernce to predicate locking) ensures only serializable schedules. So far I have not seen one.

I've just taken a look at Bernstein's online book and could not find any discussion of PL or key-range locking (unless I missed something which very well may be the case).

My interest, although strong, is purely theoretical since I cannot get too excited with key-range locking that appears to be the sate-of-the-art even today, 20 years after it was conceived. It's a clever idea, no doubt, but its dependency on having indexes diminishes its practicality in too many cases.

Let me also apologize for the usual detour our conversation took. When you posted the original two SQLs, I'd realized that that they cannot be handled as stated by a vanilla Strict 2PL scheduler and I had been trying, several times, to re-state them so that they produced conflicting operations in order to be amenable to Strict 2PL. Now, I do not think it was a correct approach to the problem. As I said before, a correct response should have been that the statements cannot be analyzed within the confines of the traditional serializability theory.

[tengiz]

That's the main problem, yes. Informally, I was convinced when I read Mohan's stuff some years ago that key range locking does what it claims to do. I'd like to see a formal proof. Until I see one, I imagine it's more correct to say that key range locking sometimes produces the same results as straight predicate locking would. It's incorrect to say that key range locking is an implementation of some useful predicate locking functionality subset until there is a formal proof of this statement. I'd also be happy with a proof that key range locking (without any refernce to predicate locking) ensures only serializable schedules. So far I have not seen one.

Вот обещанные ссылки на работы по формализму применяемому для многоуровневых транзакций (где атомарные действия на одном уровне являются на самом деле многошаговой суб-тразнакцией на следующем):

1. A theoretical foundation of multi-level concurrency control by Gerhard Weikum - June 1985 - Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems.

2. A model for concurrency in nested transactions systems - Catriel Beeri, Philip A. Bernstein, Nathan Goodman - April 1989 - Journal of the ACM (JACM), Volume 36 Issue 2.

Работу Papadimitriou я пока не нашёл, но попробую ещё поискать. Также Вам может быть интересно найти вот такую статью с глубокомысленным названием:

Bernstein, P.A., N. Goodman, and M.Y. Lai, "Laying Phantoms to Rest (by Understanding the Interactions Between Schedulers and Translators in a Database System)," Proc. 1981 IEEE COMPSAC Conf., Oct. 1981.

I've just taken a look at Bernstein's online book and could not find any discussion of PL or key-range locking (unless I missed something which very well may be the case).

Если речь идёт о Concurrency Control and Recovery in Database Systems - то я думаю, что требовать слишком многого от университеского учебника (пусть даже и одного из самых лучших) не стоит. Тем не менее, предикатные блокировки там обсуждаются, а также и реализация их частного случая посредством индексных (не диапазонных) блокировок.

My interest, although strong, is purely theoretical since I cannot get too excited with key-range locking that appears to be the sate-of-the-art even today, 20 years after it was conceived. It's a clever idea, no doubt, but its dependency on having indexes diminishes its practicality in too many cases.

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

Let me also apologize for the usual detour our conversation took. When you posted the original two SQLs, I'd realized that that they cannot be handled as stated by a vanilla Strict 2PL scheduler and I had been trying, several times, to re-state them so that they produced conflicting operations in order to be amenable to Strict 2PL. Now, I do not think it was a correct approach to the problem. As I said before, a correct response should have been that the statements cannot be analyzed within the confines of the traditional serializability theory.

Давайте всё же попробуем эти примеры ещё раз препарировать: vanilla Strict 2PL scheduler прекрасно позволяет провести анализ любых сценариев. Именно это я пытался сделать, подразумевая по умолчанию, что мы друг друга понимаем. Единственное уточнение - как я уже говорил - замените все упоминания data item/object на data set defined by a predicate во всех операциях (read, write, lock), обобщите понятие конфликта на наличие пересечения data sets defined by predicates, сведите SQL insert/delete/update к data set write / data set state change - больше ничего делать не нужно. Проблема аккуратного учёта фатномов волшебным образом испарится. Формальная часть с доказательствами корректности алгоритмов 2PL без циклов абсолютно не менятся при этой замене.

[Dmitry67]

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

Интересно что это не афишируется BOL и об этом вообще мало кто из практиков знает

Многие маленькие таблицы не индексируют 'потому что так все равно мало записей'
Исли ьаблица меняется то... особенно полезно индексировать пустые таблицы

[tengiz]

Интересно что это не афишируется BOL и об этом вообще мало кто из практиков знает

"А Вас, Штирлиц, я попрошу остаться..." (с)

Похоже, что мы Вас и Вашу контору вычислили . Наблюдательный alex_127 раскопал в отчёте троих наших коллег, съездивших на SIGMOD в Париж, подозрительно знакомые "вести с полей", а точнее вопросы и пожелания троих представителей некоего тамошнего ISV...

Что касается BOL и афиширования - если я правильно помню, есть несколько публичных whitepapers на тему оптимизации приложений на SQL Server, где эта тема подробно разбирается для любознательных практиков. Другое дело - и с этим я полностью согласен, хотя наши попытки что-то изменить пока не увенчались успехом, - информация и BOL и вообще online документация организованы крайне неудобно.

[katit]

информация и BOL и вообще online документация организованы крайне неудобно.

<off>
BOL организован лучше всего осталього (IMO)
Я-бы сказал что очень удобно
</off>

[tengiz]

BOL организован лучше всего осталього (IMO)

То, что остальное ещё хуже, чем BOL я вполне могу согласиться

Вы когда-нибудь видели документацию по SQL Server 6.0/6.5, а ещё лучше, документацию по версии 4.21? Так вот, по сравнению с теми книгами то что сейчас - это просто набор статей сваленных в кучу и кое-как связанных ссылками. После внимательного ознакомления в течение длительного времени вполне можно с этим освоиться, но система, согласно которой структурирован материал в BOL, настолько перпедникулярна моей логике, что я до сих пор тупо смотрю в оглавлене не зная куда точно мне нужно ткнуться, чтобы найти ответы на время от времени возникающие у меня вопросы на темы, напрямую не связанные с функциональностью сервера, за которую я непосредственно отвечаю. В итоге мне проще пройтись по коридорам, найти нужного мне человека или группу людей и выпытать у них как точно работает та или иная фича.