Статья:
Версионность в Yukon

Автор(ы): Иван Бодягин
Дата: 16.07.2004
Статья рассказывает о поддержке версионности, которая должна появиться в новой версии MS SQL Server — Yukon.

Авторы:
Иван Бодягин (Merle)

Аннотация:
Статья рассказывает о поддержке версионности, которая должна появиться в новой версии MS SQL Server — Yukon.

Здравствуйте, Иван Бодягин (Merle), Вы писали:

ИБM>Статья рассказывает о поддержке версионности, которая должна появиться в новой версии MS SQL Server — Yukon.
Прочитал статью — очень интересно, но есть пара вопросов.
1. По поводу Serializable написано вот что:
Хотя предыдущий уровень изоляции в версионнике устраняет практически все возможные феномены, но, тем не менее, вероятность неупорядоченности по-прежнему остается, поэтому необходимость в данном уровне изоляции сохраняется. В классическом версионнике упорядоченность достигается за счет комбинации snapshot уровня изоляции и фиктивного изменения
Что за "вероятность неупорядоченности" и почему она сохраняется ? Ведь от фантомов snapshot избавляет?
И зачем нужны фиктивные изменения? Я никогда не слышал, чтобы при работе с ораклом приходилось что-то фиктивно менять, а это "версионник".

2. А как добиваются Serializable? Блокируется вся таблица?

Здравствуйте, <Аноним>, Вы писали:
А>Что за "вероятность неупорядоченности" и почему она сохраняется ? Ведь от фантомов snapshot избавляет?
А>И зачем нужны фиктивные изменения? Я никогда не слышал, чтобы при работе с ораклом приходилось что-то фиктивно менять, а это "версионник".
Читай Re[11]: Уровень изолированости транзакций

Автор: Merle
Дата: 27.02.04

Здравствуйте, <Аноним>, Вы писали:

А>2. А как добиваются Serializable? Блокируется вся таблица?

Нет. Блокируется диапазон ключа.

Здравствуйте, Иван Бодягин (Merle), Вы писали:

ИБM>Статья:


ИБM>Авторы:
ИБM> Иван Бодягин (Merle)

ИБM>Аннотация:
ИБM>Статья рассказывает о поддержке версионности, которая должна появиться в новой версии MS SQL Server — Yukon.

Вот же, блин... А где статья то? Чо то я тут у Вас плохо ориентируюсь — нажал на ссылку, окрылась страничка с оглавлением, тыкаю в раздел — она меня перемещает по этой же странице. А где сама статья то?

Здравствуйте, tpg, Вы писали:

tpg>Вот же, блин... А где статья то? Чо то я тут у Вас плохо ориентируюсь — нажал на ссылку, окрылась страничка с оглавлением, тыкаю в раздел — она меня перемещает по этой же странице. А где сама статья то?
Статья в журнале, N6 за 2003 год. На сайте появится месяца через 2.

Сейчас жкрнал предприяте убыточное, и чтобы хоть как-то поднять продажи, было принято решение выкладывать статьи на сайт с задержкой.

Здравствуйте, tpg, Вы писали:

tpg>Вот же, блин... А где статья то? Чо то я тут у Вас плохо ориентируюсь — нажал на ссылку, окрылась страничка с оглавлением, тыкаю в раздел — она меня перемещает по этой же странице. А где сама статья то?

в журнале

Здравствуйте, Аноним, Вы писали:

А>Что за "вероятность неупорядоченности" и почему она сохраняется ? Ведь от фантомов snapshot избавляет?
Немного не так, Snapshot избавляет от фантомных чтений, но ряда других, не столь очевидных проявлений фантомов, и феноменов (аномалий) избежать, используя только Snapshot не получится.
Ссылку на один пример Синклер уже дал. Примечательно то, что в Юконе, при snapshot IL, данный сценарий отработает совершено корректно. И никаких нарушений последовательного выполнения транзакций не произойдет.

Так же, одной из классических аномалий, от которой snapshot не избавляет, и которую можно отнести к разновидности фантомов является Write Skew:
Допустим бизнес-логика требует, чтобы x+y<5, на данный момент x=1 и y=1, далее псевдокод:

-- для всех транзакций
SET TRANSACTION ISOLATION LEVEL SNAPSHOT

-- транзакция 1 (T1)
--
SELECT (X, Y)

-- надо добавить к X два, 
-- проверяем, что X + 2 + Y < 5
--
IF ((X + 2) + Y < 5) -- все в порядке Y(=1) + X(=1+2)<5
    UPDATE SET X=X+2

-- в этот момент стартует вторая транзакция
-- которой, в свою очередь, надо к Y добавить 2, естественно с проверкой.
--
SELECT (X, Y)

IF (X + (Y + 2) < 5) -- тоже все в порядке Y(=1+2) + X(=1)<5
    UPDATE SET Y=Y+2 -- так как SELECT(X, Y) выбрал последнюю 
                     -- зафиксированную версию X (=1)

-- ну и фиксируем обе транзакции в произвольном порядке.
-- 
COMMIT    -- T1

COMMIT    -- T2

В многоверсионной истории это выглядит примерно так:
R1(x,y),W1(x),R2(x,y),W2(y),C1..,C2
Как нетрудно догадаться, в результате этих упражнений X+Y будет равно 6, что не соответствует никакому сценарию последовательного выполнения этих транзакций.


А>И зачем нужны фиктивные изменения? Я никогда не слышал, чтобы при работе с ораклом приходилось что-то фиктивно менять, а это "версионник".
Ну, все-таки, Оракл не совсем версионник и в силу этого у него есть хинт FOR UPDATE, как раз для таких случаев, как Write Skew. Если в примере, приведенном выше, выборку SELECT (x,y), в Оракле, делать с хинтом FOR UPDATE, то все сразу станет мягким и шелковистым. Эффект от выполнения этих транзакций всегда будет строго последовательным.
Но, честные версионники такой возможности не имеют, например, в InterBase'е, на сколько мне известно, чтобы избежать подобных аномалий необходимо делать фиктивный update X и Y в обеих транзакциях, перед тем, как считывать их значения.
Если же взять первый пример, ссылку на который дал Sinclair, то там не спасет и FOR UPDATE, и фиктивный UPDATE.
В силу отсутствия предикатных блокировок у всех известных мне версионников, в том сценарии поможет только блокировка всей таблицы.

А>2. А как добиваются Serializable? Блокируется вся таблица?
Вся таблица блокируется только в случае отсутствия индексов, если же находится подходящий индекс, то блокируется диапазон значений (Key Range Lock), что гораздо эффективнее.
Впрочем, подходящую ссылку так же уже привели..

Здравствуйте, Merle, Вы писали:

M>Здравствуйте, tpg, Вы писали:

tpg>>Вот же, блин... А где статья то? Чо то я тут у Вас плохо ориентируюсь — нажал на ссылку, окрылась страничка с оглавлением, тыкаю в раздел — она меня перемещает по этой же странице. А где сама статья то?
M>Статья в журнале, N6 за 2003 год. На сайте появится месяца через 2.

M>Сейчас жкрнал предприяте убыточное, и чтобы хоть как-то поднять продажи, было принято решение выкладывать статьи на сайт с задержкой.

СЭНГЗ! Бум ждать...

Здравствуйте, tpg, Вы писали:

M>>Сейчас жкрнал предприяте убыточное, и чтобы хоть как-то поднять продажи, было принято решение выкладывать статьи на сайт с задержкой.
tpg>СЭНГЗ! Бум ждать...

Так может лучше на журнал подписаться?

Здравствуйте, Иван Бодягин (Merle), Вы писали:

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

ИБM>Во всех предыдущих версиях Microsoft SQL Server механизм подобной регулировки был основан на блокировках. Однако в новой версии (кодовое название Yukon) будет введена поддержка другого механизма, основанного на контроле версий (multiversioning). В дальнейшем два этих подхода я буду называть версионным и блокировочным соответственно.


Мне кажется, здесь есть некоторая неточность в формулировках, хотя и общепринятая.
"Блокировочник" — это действительно тип планирощика транзакций (transaction sheduler), т.е действительно механизм регулирующий "очередность" транзакций.
"Контроль версий" — это механизм контроля версий и он не имеет прямого отношения к типу шедулера.


Если рассматривать типы планировщиков транзакций то можно наверное выделить следующие группы:

1.Блокирующие:

1.1 Протокол двухфазного блокирования (Two phase locking (2PL))

2. Не блокирующие:

2.1 Упорядочевание на основе временных меток.( Timestamp ordering (TO) )
2.2 Проверка корректности графа транзакций ( Serialization graph testing (SGT))

Механизм контроля версий (MVC) может быть добавлен к любому планировщику транзакций в целях минимизации количества конфликтных ситуаций требующих ожидания/отката за счет затрат на необходимость хранить версии данных. Например:

TO+MVC : InterBase

(2PL + TO) + MVC : Oracle (смешанный механиз шедулера, можно рассматривать как TO для чтения и 2PL для записи).

В Yukon, на сколько я понял из статьи, "Версионность" это как и в Oracle смешанный механизм шедулера
(2PL + TO) + MVC.

Здравствуйте, KisA, Вы писали:

KA>"Контроль версий" — это механизм контроля версий и он не имеет прямого отношения к типу шедулера.
Ну почему? Совершенно самостоятельный тип шедулера...

KA>Если рассматривать типы планировщиков транзакций то можно наверное выделить следующие группы:
Ну если выделять неблокирующий отдельно, то наверное так, но какой в этом смысл?
Хотя помторюсь, MVC совершенно самостоятельный механизм и вполне может быть реализован отдельно.
Другое дело, что практически ни один механизм в реальных серверах в чистом виде не применяется, возможно из-за этого и путаница...

Здравствуйте, Merle, Вы писали:

M>Здравствуйте, KisA, Вы писали:

KA>>"Контроль версий" — это механизм контроля версий и он не имеет прямого отношения к типу шедулера.
M>Ну почему? Совершенно самостоятельный тип шедулера...
Смотрим Бернштайна (Concurency control and recovery in database systems ), глава 4, NON-LOCKING SHEDULERS:

4.1 Introduction 113
4.2 Timestamp Ordering (TO) 114
4.3 Serialization Graph Testing (SGT) 121
4.4 Certifiers 128
4.5 Integrated Schedulers 132

Мултиверсионного шедулера не видим.

из 4.5 :

The schedulers we have seen so far synchronize conflicting operations by one
of three mechanisms: 2PL, TO, or SGT. There are other schedulers that use
combinations of these techniques to ensure that transactions are processed in
an SR manner.

Т.е синхронизация конфликтных ситуаций осуществляется по одному из 3-х указанных механизмов, или их комбинации.

Смотрим там же в главе 5 ( MULTIVERSION CONCURRENCY CONTROL ):

S.1 Introduction 143
5.2 Multiversion Serializability Theory:’ 146
5.3 Muitiversion Timestamp Ordering 153
5.4 Multiversion Two Phase Locking 156
5.5 A Multiversion Mixed Method 160

из 5.3 :

We can define schedulers for multiversion concurrency control based on each
of the three basic types of schedulers: 2PL, TO, and SGT.

Опять же MVC везде базируется на одном из шедулеров, а не как самостоячтельный механизм.

из 5.5:

As we have seen, multiversions give the scheduler more flexibility in scheduling
Reads.

MVC служит дополнительным механизмом для шедулеров с целью придания им "гибкости".

Здравствуйте, KisA, Вы писали:

KA>Мултиверсионного шедулера не видим.
Ok, уболтал...
В конце-концов Берншнтайну можно верить, он один из тех, кто его придумал..

KA>Опять же MVC везде базируется на одном из шедулеров, а не как самостоячтельный механизм.
Однако в других, более поздних работах, как мне помнится, MVC фигурирует, сам по себе, хотя обычно под этим понимают TO+MVC, если следовать классификации Бернштайна.

Здравствуйте, Merle

Вы знаете, я проверила в Юконе этот пример. Он вполне успешно работает: одна из транзакций откатывается.
Поэтому вопрос, — от каких таких аномалий snapshot не избавляет, остается открытым.


M>Так же, одной из классических аномалий, от которой snapshot не избавляет, и которую можно отнести к разновидности фантомов является Write Skew:
M>Допустим бизнес-логика требует, чтобы x+y<5, на данный момент x=1 и y=1, далее псевдокод:
M>

M>-- для всех транзакций
M>SET TRANSACTION ISOLATION LEVEL SNAPSHOT

M>-- транзакция 1 (T1)
M>--
M>SELECT (X, Y)

M>-- надо добавить к X два, 
M>-- проверяем, что X + 2 + Y < 5
M>--
M>IF ((X + 2) + Y < 5) -- все в порядке Y(=1) + X(=1+2)<5
M>    UPDATE SET X=X+2

M>-- в этот момент стартует вторая транзакция
M>-- которой, в свою очередь, надо к Y добавить 2, естественно с проверкой.
M>--
M>SELECT (X, Y)

M>IF (X + (Y + 2) < 5) -- тоже все в порядке Y(=1+2) + X(=1)<5
M>    UPDATE SET Y=Y+2 -- так как SELECT(X, Y) выбрал последнюю 
M>                     -- зафиксированную версию X (=1)

M>-- ну и фиксируем обе транзакции в произвольном порядке.
M>-- 
M>COMMIT    -- T1

M>COMMIT    -- T2
M>

M>В многоверсионной истории это выглядит примерно так:
M>R1(x,y),W1(x),R2(x,y),W2(y),C1..,C2
M>Как нетрудно догадаться, в результате этих упражнений X+Y будет равно 6, что не соответствует никакому сценарию последовательного выполнения этих транзакций.

Здравствуйте, PCherkasova, Вы писали:

PC>Вы знаете, я проверила в Юконе этот пример. Он вполне успешно работает: одна из транзакций откатывается.
Приведите пожалуйста код примера, видимо Вы что-то упустили... Напоминаю, что для корректной эмуляции именно версионного поведения для Юкона должны быть в наличии подходящие индексы, в статье я описывал этот момент (Иначе Юкон принимает за конфликт любое изменение данных в таблице).
К сожалению сейчас Юкона или другого версионника под рукой нет, как доберусь обязательно приведу рабочий пример.

PC>Поэтому вопрос, — от каких таких аномалий snapshot не избавляет, остается открытым.
Например еще от таких (Описан еще у Тома Кайта, если мне никто не изменяет):

--- Опять псевдокод
--- может существовать только одна запись x=1 или x=2

create table a (x int)

-- start T1, session 1
set transaction isolation level snapshot
begin
    delete from a where x in (1,2)
    insert into a (x) values(1)

-- start T2, session 2
set transaction isolation level snapshot
begin 
    delete from a where x in (1,2)
    insert into a (x) values(2)
commit    

-- commit T1, session 1
commit

select * from a

Предупреждаю сразу, Юкон этот фокус не пропустит, поскольку его snapshot несколько строже "классического", ввиду наличия предикатных блокировок но любой другой версионник даже глазом не моргнет. Более того, версионник не спасут и блокировочные хинты (типа FOR UPDATE), и фиктивные апдейты, только полная блокировка таблицы...

Здравствуйте, PCherkasova, Вы писали:

PC>Поэтому вопрос, — от каких таких аномалий snapshot не избавляет, остается открытым.
Вот пример скрипта для Юкона, который демонстрирует эту аномалию:

--- Допустим сумма всех записей в таблице должна быть меньше 6.

-- инициализируем
--
ALTER DATABASE Northwind SET ALLOW_SNAPSHOT_ISOLATION ON
 
drop table tbl
Create table tbl(x int)
create unique index ix on tbl(x)

insert into tbl (x)
select 1 union
select 2 

---- Первая транзакция в первой сессии.
----
set transaction isolation level snapshot
begin tran
    if (select sum(x) from tbl) + 2 < 6 begin
         update tbl set x=x+2 where x=2
    end
        
---- Вторая транзакция во второй сессии.
----
set transaction isolation level snapshot
begin tran
    if (select sum(x) from tbl) + 2 < 6 begin
         update tbl set x=x+2 where x=1
    end        
        
---- Далее в произвольном порядке

-- сессия 1
commit tran

-- сессия 2
commit tran

---- Смотрим результат:
select * from tbl 
3
4

3 + 4 = 7, чего никак не может быть при каком угодно последовательном выполнении этих транзакций.
Так что вопрос по поводу неизбавления от аномалий можете закрывать...
Вот, кстати, любопытная статья в том числе и с описаниями возможных аномалий, среди которых есть и продемонстрированная здесь — "Wrte Skew" A Critique of ANSI SQL Isolation Levels
Была еще одна, со строгим доказательством и обоснованием, в каких случаях и почему Snapshot не спасает, и когда необходимо применять хинты и фиктивные update для обеспечения согласованности в тех системах, которые не поддерживают честного Serializability (помоему там предлагался даже универсальный алгоритм по анализу запросов и выявлению подобных аномалий), но ссылок я сходу не нашел, найду выложу...

Здравствуйте, Merle, Вы писали:

M>Вот пример скрипта для Юкона, который демонстрирует эту аномалию:
M> ......
M>Так что вопрос по поводу неизбавления от аномалий можете закрывать...

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

Здравствуйте, Merle,

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

Здравствуйте, Merle,

я писала:
PC>Я подумала, что этот пример очень нежизненный. Странно индексировать уникальным ключем поле, над которым необходимо выполнять операции аггрегирования, а потом еще и обновлять с помощью арифметических действий.
PC>Возможно, Microsoft и прав, что пошел на такой копромисс.

Я была неправа. На самом деле, для уровня snapshot все плохо. Потому что сериализуемость также нарушается, если обращаться к записи по индексированному уникальному ключу, а проверять и обновлять неиндексированное значение:

if (select sum(val) from tbl) + 2 < 6
begin
update tbl set val=val+2 where x=2
end