Making Snapshot Isolation Serializable.

[tengiz]

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

Making Snapshot Isolation Serializable - http://www.cs.umb.edu/~isotest/snaptest/snaptest.pdf.

Abstract.

Snapshot Isolation (SI) is a multi-version concurrency control algorithm that was first described in [BBGMOO95]. SI is attractive because it never delays read operations, not even when concurrent writes are occurring. SI has been implemented by Microsoft Exchange and Oracle (with certain variations), and it provides an isolation level that avoids many of the common concurrency anomalies. SI does not guarantee serializability, however. Like most protocols that fail to guarantee serializabiliy, SI can lead to arbitrarily serious violations of integrity constraints. This results, we suspect, in thousands of errors per day, some of which may be quite damaging. Fortunately, there are some applications where the logic of the programs means that only serializable executions can take place; this is the case with the TPC-C benchmark for example. Motivated by this fact, we present a new theory with which the DBA can examine the program logic of the application to achieve one of the following two goals:

1. To verify that only serializable executions will occur when running on a DBMS which has SI as its concurrency control algorithm.
2. If 1 fails, to modify the application programs so that such serializability will be guaranteed.

Our goal is to bring concurrency safety to the many applications running on systems with SI as the concurrency control mechanism.

[vc]

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

Making Snapshot Isolation Serializable - http://www.cs.umb.edu/~isotest/snaptest/snaptest.pdf.

....

Highly recommended, as well as H. Berenson's critique of the ANSI isolation levels.

I found the article after we'd had our May exchange on isolation levels. The H. Berenson's ctitique and the article (and especially our discussion) convinced me that Oracle indeed does not implement the SERIALIZABLE isolation level de facto although the implementation satisfies the ANSI "phenomenal" definition de jure.

Funnily enough, the cure suggested by the authors is rather trivial and had been used by Oracle developers for quite a while ( SELECT FOR UPDATE, one of the approaches I mentioned during our May discussion).

It may be interesting to know that until version 7.3.3, Oracle had had the configuration parameter 'serializable=true' which was quite a different beast, not at all the same as 'set transaction isolation level serializable'.

'serializable = true' caused a share table lock to be placed whenever a table was READ. It means, if you read a table with serializable=true, no insert/update/delete could be done until you committed. The parameter was deprecated in the subsequent releases I guess due to lack of popular demand ;)

Rgds.

[Merle]

Если кому интересно, вот толковая статья на эту тему.
Making Snapshot Isolation Serializable - http://www.cs.umb.edu/~isotest/snaptest/snaptest.pdf.
....

Конечно интересно, спасибо.. =)

Highly recommended, as well as H. Berenson's critique of the ANSI isolation levels.

I found the article after we'd had our May exchange on isolation levels. The H. Berenson's ctitique and the article (and especially our discussion) convinced me that Oracle indeed does not implement the SERIALIZABLE isolation level de facto although the implementation satisfies the ANSI "phenomenal" definition de jure.

Да, в той же дискуссии и ссылка на эту статью давалась. Опять же если кому интересно, то вот: http://www.inf.uni-konstanz.de/dbis/tea ... itique.pdf

[zVlad]

Tengiz, Ваша ссылка у меня дает: Not Found, Merle, по Вашей ссылке я нашел замечательную статью, которую прочитал на 30% и хотел бы рекомендовать всякому, кто хочет чтобы его называли БД-man. Статья впечатляющая, давно я таких не читал. Поздже выскажу более определенное мнение - сейчас хочу поднять тему, что бы больше людей обратили внимание и почитали.

[tengiz]

Tengiz, Ваша ссылка у меня дает: Not Found, Merle, по Вашей ссылке я нашел замечательную статью, которую прочитал на 30% и хотел бы рекомендовать всякому, кто хочет чтобы его называли БД-man. Статья впечатляющая, давно я таких не читал. Поздже выскажу более определенное мнение - сейчас хочу поднять тему, что бы больше людей обратили внимание и почитали.

Уберите точку в конце URL и всё сразу сработает - http://www.cs.umb.edu/~isotest/snaptest/snaptest.pdf

Что касается "Критики уровней изоляции ANSI" - это классическая статья, которая неоднократно упоминалась на Привете в дискуссиях на тему изоляции в БД. В том числе и с Вашим участием. Между прочим, Harold Berenson и Jim Gray, соавторы этого текста - одни из самых известных в мире экспертов в области обработки транзакций, являлись ключевыми идеологами нового поколения SQL Server, стартовавшего с версии 7.0. Hal Berenson, в частности, руководил разработкой нового процессора запросов - SQL Server Relational Engine.

[zVlad]

Есть и другие ребята, занимающиеся теми же вопросами:

http://www.almaden.ibm.com/u/mohan/ARIES_Impact.html

Но это больше алгоритмы и методы чем научный анализ.

[zVlad]

Восхищение вызванное статьей "A Critique of ...." за выходные поубавилось. И началось думаться что - у теориия свои проблемы, у практики свои.
Но что мне кажется замечательным в этой статье в свете того что я безуспешно пытался донести до присутствующих, так это то, что судя по всему авторы считают что "The ANSI isolatio levels are related to the behavior of lock schedulers", хотя на другой странице эти же авторы пишут: "ANSI SQL .....would admit many different implementatins, not just locking".
Если кто помнит, я утверждал и утверждаю что Оракл не имеет никакого отношения к ANSI ILs. По прочтении статьи я могу добавить, что Оракл - имплементация упрощенного варианта Snapshot Isolation. Да сделанная как с использованием версионности, так и через локинга (боюсь это гремучая смесь).
Еще интересно обратить внимание на особое место Cursor Stability. Для меня - это обасонование того, что уровни изоляции ANSI, DB2, and MS SQL НЕ тождественны друг другу. CS ^== RC.

[Dmitry67]

Еще интересно обратить внимание на особое место Cursor Stability. Для меня - это обасонование того, что уровни изоляции ANSI, DB2, and MS SQL НЕ тождественны друг другу. CS ^== RC.

Бессмыслица
Уровни изоляции ANSI тождественны сами себе и есть лишь математические определение

Сравнивать уровни изоляции конкретных баз между собой можно, но сравнения с ANSI некорректно, как например сравнение компилятора и формального поределения грамматики

Про реализацию уровня изоляции базы и ANSI можно сказать лишь УДОВЛЕТВОРЯЕТ ли данная реализация данному определению ANSI или нет.

[tengiz]

zVlad - опять двадцать пять. Если не верите, что говорят другие - обратитесь к первоисточникам - к стандарту и к документации по конкретным продуктам. Единственное теоретическое отличие READ COMMITTED от CURSOR STABILITY - возможность повторяющего чтения строки под текущей позицией курсра, при условии, что предыдущее чтение не двигало курсор - происходит из довольно размытой абстрактной неоднозначной формулировки ANSI уровня READ COMMITTED (как впрочем и всех остальных уровней, кроме SERIALIZABLE да и то, в строгом буквальном прочтении, а не определённом через остуствие "феноменов", описанных в ANSI) безотносительно к способу чтения данных (через курсор или каким-либо другим способом), т.е. для ANSI READ COMMITTED безразлично, как читаются данные, через явный курсор с оператором FETСH или как-нибудь иначе. Что касается конкретных реализаций, то, например, в SQL Server READ COMMITTED - это в точности то же самое (и функционально, и даже в деталях реализации), что CURSOR STABILITY в DB2.

Вот Вам, кстати, наводящий вопрос, может что-нибудь где-нибудь кликнет, и мы больше не будет тратить время на всякую чепуху по десятому разу: каким образом работает уровень изоляции DB2 CURSOR STABILITY в случаях, когда курсора нет совсем? Например, при выполнении вот такой вот транзакции, состоящей из одного UPDATE:

Code: Select all

UPDATE table1 SET total = (SELECT SUM (amount) FROM table2)

Или вот такой, состоящией из одного INSERT:

Code: Select all

INSERT INTO table1 (total) SELECT SUM (amount) FROM table2

Или вот такой, состоящией из одного DELETE:

Code: Select all

DELETE table1 WHERE total = (SELECT SUM (amount) FROM table2)

И ещё одно замечание: эта статья - это критика определения уровня изоляций в ANSI, которые фактически базируются на предположении эталонности блокировочной реализации системы обработки транзакций (что, разумеется, отражало реальность в те времена, когда комитет работал над первым стандартом). Но на момент написания статьи список "феноменов", упоминаемых в стандарте, был уже давным-давно неполон, поэтому результирующие уровни изоляции тоже оказались неточными и неадекватными реальной жизни. Что касается злополучного CURSOR STABILITY - то авторы статьи пишут не о том, как этот уровень изоляции ложится в стандарт, а о том, что определения уровней изоляции в стандарте следует изменить так, чтобы не было неоднозначности. Т.е. их таблицы, где CURSOR STABILITY и READ COMMITTED не одно и то же - это не то, как это есть в стандарте, а то, как это должно быть в стандарте, на взгляд авторов. А по факту, стандарт до сих пор так и не изменён. Хотя уже давно пора.

[zVlad]

zVlad - опять двадцать пять. ..............

Вот Вам, кстати, наводящий вопрос, может что-нибудь где-нибудь кликнет, и мы больше не будет тратить время на всякую чепуху по десятому разу: каким образом работает уровень изоляции DB2 CURSOR STABILITY в случаях, когда курсора нет совсем? Например, при выполнении вот такой вот транзакции, состоящей из одного UPDATE:

Code: Select all

UPDATE table1 SET total = (SELECT SUM (amount) FROM table2)

Или вот такой, состоящией из одного INSERT:

Code: Select all

INSERT INTO table1 (total) SELECT SUM (amount) FROM table2

Или вот такой, состоящией из одного DELETE:

Code: Select all

DELETE table1 WHERE total = (SELECT SUM (amount) FROM table2)

............

First and last partions of your posting I will respond tonight.

DB2 Cursor Stability will work absolutely the same way as for just:

SELECT SUM (amount) FROM table2

Point of your question is not clear for me (I believe for you too). Sub-SELECT in all of your examples will be served by DB2 as a single SELECT. Cursor Stability doen't mean we have to open explicitly cursor in program in order to employ this set of rules called as IL CS. When we submit any SELECT (regardless as a separate SQL statement or as a part of others) and ask DB2 to apply rules, related to what we call CS, DB2 will just do it for us.

[tengiz]

Point of your question is not clear for me (I believe for you too)...

What's the difference between DB2 CURSOR STABILITY and ANSI READ COMMITTED if there is no explicit cursor involved? I hope this would sound clear enough for you.

[zVlad]

zVlad - опять двадцать пять. ........ Единственное теоретическое отличие READ COMMITTED от CURSOR STABILITY - возможность повторяющего чтения строки под текущей позицией курсра, при условии, что предыдущее чтение не двигало курсор - происходит из довольно размытой абстрактной неоднозначной формулировки ANSI уровня READ COMMITTED (как впрочем и всех остальных уровней, кроме SERIALIZABLE да и то, в строгом буквальном прочтении, а не определённом через остуствие "феноменов", описанных в ANSI) безотносительно к способу чтения данных (через курсор или каким-либо другим способом), т.е. для ANSI READ COMMITTED безразлично, как читаются данные, через явный курсор с оператором FETСH или как-нибудь иначе. Что касается конкретных реализаций, то, например, в SQL Server READ COMMITTED - это в точности то же самое (и функционально, и даже в деталях реализации), что CURSOR STABILITY в DB2.

.........

According to article "A Critique of ....": "...CS is designed to prevent the lost update phenomenon (P4)."... "P4 is possible at the READ COMMITTED....."

Possibly, I don't know, to underline this difference, IBM calls ANSI RC as a CS in DB2.

[tengiz]

According to article "A Critique of ....": "...CS is designed to prevent the lost update phenomenon (P4)."... "P4 is possible at the READ COMMITTED....."

Well, the bad news is that there is no such thing as P4 in ANSI standard. Therefore, as far as the standard is concerned, there is no difference between DB2 CURSOR STABILITY and ANSI READ COMMITTED because there is no way to measure any. And again, the paper says how it should be, but not how it is, and the "critique" part of it concerns the current ANSI standard. Is it clear now?

Possibly, I don't know, to underline this difference, IBM calls ANSI RC as a CS in DB2.

This might have been a reasonable suggestion, ... only if they didn't have to invent non-standard names for ANSI REPEATABLE READ (== DB2 READ STABILITY) and ANSI SERIALIZABLE (== DB2 REPEATABLE READ). Why?

[zVlad]

Еще интересно обратить внимание на особое место Cursor Stability. Для меня - это обасонование того, что уровни изоляции ANSI, DB2, and MS SQL НЕ тождественны друг другу. CS ^== RC.

Бессмыслица
Уровни изоляции ANSI тождественны сами себе и есть лишь математические определение

Сравнивать уровни изоляции конкретных баз между собой можно, но сравнения с ANSI некорректно, как например сравнение компилятора и формального поределения грамматики

Про реализацию уровня изоляции базы и ANSI можно сказать лишь УДОВЛЕТВОРЯЕТ ли данная реализация данному определению ANSI или нет.

ANSI - это стандарт, это не математическое определение. Стандарт для того и создан, чтобы различные поставщики могли кратко объяснить потребителю в рамках какого стандарта их изделие позиционируется и как. Есть еще понятие эталон, но оно уж никак не вяжется с областью программных продуктов, покрайней мере на данном этапе развития.
Вот конкретные базы между собой сравнивать как оказалось затруднительно (за исключением тривиального совпадения). Особенно, если они построены на совершенно различных принципах, а сравниваться нужно через один единственный стандарт. При этом еще селс-персоны везде лезут со своими советами.
Это верно насчет того, что единственное что можно сказать - это соответствует или нет та или иная реализация стандарту. При этом сами реализации могут сильно разниться между собой. Как оказалось (см. Tengiz) CS в DB2 и Read Committed в MS SQL - это одно и тоже. Удовлетворяя RC ANSI оба удовлетворяют также более жестким ограничениям, которые стандартом не определены.
Стандарт видимо для того и создавался, чтобы отсечь явно дефектные реализации (методом запрета) не навязывая при этом ограничений для творчества - поэтому он (SQL-92) может и не обновляется так долго. Хотя я тут открыл для себя, что есть оказывается Entry, Intermediate и Future (?) levels, а также SQL3 (?). Кстати в доках по DB2 никогда (практически) не упоминается ANSI SQL. Идет простое описания того что есть DB2.

[zVlad]

According to article "A Critique of ....": "...CS is designed to prevent the lost update phenomenon (P4)."... "P4 is possible at the READ COMMITTED....."

Well, the bad news is that there is no such thing as P4 in ANSI standard. Therefore, as far as the standard is concerned, there is no difference between DB2 CURSOR STABILITY and ANSI READ COMMITTED because there is no way to measure any. And again, the paper says how it should be, but not how it is, and the "critique" part of it concerns the current ANSI standard. Is it clear now?

Possibly, I don't know, to underline this difference, IBM calls ANSI RC as a CS in DB2.

This might have been a reasonable suggestion, ... only if they didn't have to invent non-standard names for ANSI REPEATABLE READ (== DB2 READ STABILITY) and ANSI SERIALIZABLE (== DB2 REPEATABLE READ). Why?

Стандарт не есть догма, но руководство к действию. Мне то clear, clear ли Вам, Tengiz, что не все что круглое и зеленое это мячик, это может быть и арбуз, например.
Насчет имен, уместно было бы прояснить, а что было invented первым по времени: уровни изоляции, определенные в DB2 или ANSI SQL92 ILs?
У С.J. Date в книге "A Guide to DB2" (многим хорошо знакомая) издана в 1984 году (русский перевод 1988 год), читаем:

" .... Имеются два возможных значения этого параметра: RR и CS, причем RR - значение которое принимается по умолчанию......транзакция, оперирующая на уровне изоляции RR, может вести себя совершенно так, как если бы она исполнялась в системе с единственным пользователем."
Т.е. RR у Date - это не ANSI RR. Да, с тех пор появился стандарт и наука ушла далеко вперед, но впервые слово "колесо" произнесено было в ИБМ и там не видят смысла колесо называть "кругом".

[tengiz]

zVlad - ну а тогда об чём собственно спорите-то? Те же яйки, вид сбоку - разные имена для одного и того же, пусть даже и нечётко определённого, и поэтому ещё более интересного. Конечно, IBM - признанный пионер в обработке транзакций, да и много ещё где. И что из этого следует?

В общем, аминь.

P.S. А Snapshot у ORACLE (как и у Postgress) - образцово-показательный. Абсолютно безупречный. Блокировки вместо обнаружения конфликтов при commit - всего лишь альтернативная реализация. Во многих смыслах более оптимальная, чем чистая ловля конфликтов записи. Но функционально совершенно экливалентная.

[zVlad]

zVlad - ну а тогда об чём собственно спорите-то? Те же яйки, вид сбоку - разные имена для одного и того же, пусть даже и нечётко определённого, и поэтому ещё более интересного. Конечно, IBM - признанный пионер в обработке транзакций, да и много ещё где. И что из этого следует?

В общем, аминь.

P.S. А Snapshot у ORACLE (как и у Postgress) - образцово-показательный. Абсолютно безупречный. Блокировки вместо обнаружения конфликтов при commit - всего лишь альтернативная реализация. Во многих смыслах более оптимальная, чем чистая ловля конфликтов записи. Но функционально совершенно экливалентная.

Может быть. Вопрос как этот образцово-показательный подход с точки зрения реализации? Многие красивые математические теории не реализуемы на имеющиеся вычислителях.
Такая вот шальная мысль пришла, навеяная Вашим Tengiz:
" .... А по факту, стандарт до сих пор так и не изменён. Хотя уже давно пора." - представим мы - это ANSI. Как бы дОлжено изменить формулировки в отношении ILs. И что самое главное - как после этого будут выглядеть участники рынка БД?
Видимо нужно прописать все вновь открытые феномены (пришло сразу в голову - потерянные апдейты, но оказалась они уже были известны Дейту в 80х). Надо посмотреть вновь статью и определить какие новые феномены были открыты. Далее, добавить CS? Или заменить RC на CS? Оракл начинает испытывать проблемы с идентификацией в стандарте.
Наверное дать толкование блокировочникам и версионникам, а также ввести уровень SI для версионников будет оптимальным изменением стандарта? Опять Ораклу придется менять доки и переучивать своих последователей.
Что делать-то, Tengiz?

[tengiz]

Как бы дОлжено изменить формулировки в отношении ILs. И что самое главное - как после этого будут выглядеть участники рынка БД?... Видимо нужно прописать все вновь открытые феномены (пришло сразу в голову - потерянные апдейты, но оказалась они уже были известны Дейту в 80х). Надо посмотреть вновь статью и определить какие новые феномены были открыты.

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

Далее, добавить CS? Или заменить RC на CS? Оракл начинает испытывать проблемы с идентификацией в стандарте... Наверное дать толкование блокировочникам и версионникам, а также ввести уровень SI для версионников будет оптимальным изменением стандарта? Опять Ораклу придется менять доки и переучивать своих последователей.

Да нет, не начнёт. Это почему вдруг? Оракловский SERIALIZABLE - это и есть SNAPSHOT в чистом виде. Если дырка в стандарте, позволившая ORACLE именовать это уровень SERIALIZABLE, наконец закроется, то ничего страшного не произойдёт. В доках они честно писали и пишут, что их SERIALIZABLE отвечает одному из определений ANSI (гарантирует остутствие всех феноменов, описанных в стандарте), но не отвечает альтернативному определению в том же ANSI, а также тому самому главному, принятому в формальной теории. Поэтому в их доках с незапамятных времён есть рекомендации о том, когда и как нужно применять трюки с искусственными конфликами записи, SELECT FOR UPDATE и ручными блокировками. Не все их правда внимательно читают... Но, винить за это ORACLE уже не совсем правильно.

Что делать-то, Tengiz?

А как же насчёт "кто виноват"?

P.S.

...представим мы - это ANSI.

Да у меня в чуть ли не в кабинетах по соседству члены ANSI SQL комитета сидят, так что...

[tengiz]

Оракловский SERIALIZABLE - это и есть SNAPSHOT в чистом виде. Если дырка в стандарте, позволившая ORACLE именовать это уровень SERIALIZABLE, наконец закроется, то ничего страшного не произойдёт.

Oops! - Эта конкретная дырка в стандарте уже закрыта в SQL99 и неоднозначного толкования SERIALIZABLE уже нет.

<added>

"The exclusion of these phenomena for SQL-transactions executing at isolation level SERIALIZABLE is a consequence of the requirement that such transactions be serializable."

А также и дырка, связанная с P4. Хоть понятие феномена P4 ("Lost updates") отсутствует в SQL99, в тексте документа, тем не менее, специально оговаривается, что "The four isolation levels guarantee that each SQL-transaction will be executed completely or not at all, and that no updates will be lost." Поэтому как ни крути, IBM CS вполне официально и реально тождественно теперешнему ANSI READ COMMITTED.

</added>