От Isolation к Consistency — дорога длиной в 30 лет20.12.2022 06:32

Участвую в стартапе, в котором разрабатывается СУБД нового типа (работает поверх некоторых kv-движков, кардинально расширяя их возможности, про это немного можно прочитать здесь). Для того, чтобы сравнить то, что понемногу получается, с тем, что имеется в индустрии, пришлось на глубоком уровне проработать первоисточники по темам Isolation и Consistency (уточню, что имеется ввиду не та Consistency, что в ACID). Обнаружил интересные нюансы, которые и излагаю в этой статье.

Тезисно:

• Термин Phantom Read является продуктом испорченного телефона
• Смысл понятий Lost Update, Write Skew и Read Skew для разделения уровней изоляций неочевиден и относителен
• Движок, который обеспечивает уровень изоляции Serializable, в распределённом мире может вести себя весьма причудливо, например, всегда возвращать пустой результат для read-only транзакций — и ему за это по стандарту «ничего не будет»
• Strong consistency в Cosmos DB — предел мечтаний? (спойлер: нет)

Ну, и ещё кое-что по мелочи. В конце рассмотрим вот такой венец творения человеческого разума:

Тридцать лет назад появился документ ISO/IEC 9075:1992, Database Language SQL- July 30, 1992 (далее SQL-92). Посмотрим, что там есть интересного, в рамках этой статьи.

Определяются три феномена:

    1) P1 ("Dirty read"): SQL-transaction T1 modifies a row. SQL-
    transaction T2 then reads that row before T1 performs a COMMIT.
    If T1 then performs a ROLLBACK, T2 will have read a row that was
    never committed and that may thus be considered to have never
    existed.

    2) P2 ("Non-repeatable read"): SQL-transaction T1 reads a row. SQL-
    transaction T2 then modifies or deletes that row and performs
    a COMMIT. If T1 then attempts to reread the row, it may receive
    the modified value or discover that the row has been deleted.

    3) P3 ("Phantom"): SQL-transaction T1 reads the set of rows N
    that satisfy some . SQL-transaction T2 then
    executes SQL-statements that generate one or more rows that
    satisfy the  used by SQL-transaction T1. If
    SQL-transaction T1 then repeats the initial read with the same
    , it obtains a different collection of rows.

Пока ничего интересного, за исключением того, что Phantom Read, на самом деле, надо называть просто Phantom.

Стандарт определяет уровень изоляции SERIALIZABLE:

The execution of concurrent SQL-transactions at isolation level SERIALIZABLE is guaranteed to be serializable. A serializable execution is defined to be an execution of the operations of concur rently executing SQL-transactions that produces the same effect as some serial execution of those same SQL-transactions. A serial execution is one in which each SQL-transaction executes to completion before the next SQL-transaction begins.

Иными словами, SERIALIZABLE означает выполнение транзакций таким образом, что эффект эквивалентен их некоторому последовательному выполнению. Как мы увидим далее, строгое следование такому определению имеет весьма тяжёлые последствия в распределённых системах (и не только в них).

Кроме того, в стандарте можно найти удивительный тезис:

    Significant new features are:
    ...
    15)Support for transaction consistency levels,      

Удивительный он потому, что далее в тексте нет ничего про transaction consistency levels, по всей видимости, авторы имели ввиду «SQL-transaction isolation levels». Тем не менее, отметим смешение понятий Сonsistency и Isolation.

Идём дальше.

A Critique of ANSI SQL Isolation Levels, Jun 1995, Microsoft Research — совместная работа Microsoft, Sybase и UMass (University of Massachusetts Amherst), опубликованная в 1995 году. В ней авторы критикуют ANSI X3.135–1992 (он же ISO 9075:1992) и предлагают улучшения и дополнения. Несмотря на почтенный возраст, работа ключевая, именно её определения постоянно используют и пересказывают (например, тут).

Авторы предлагают весьма полезную нотацию:

Histories consisting of reads, writes, commits, and aborts can be written in a shorthand notation: «w1[x]» means a write by transaction 1 on data item x (which is how a data item is «modified»), and «r2[x]» represents a read of x by transaction 2. Transaction 1 reading and writing a set of records satisfying predicate P is denoted by r1[P] and w1[P] respectively. Transaction 1«s commit and abort (ROLLBACK) are written «c1» and «a1», respectively.

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

Авторы отказываются называть ранее определенные феномены «феноменами», давая им название «аномалии», и дают такую формализацию в своей нотации:

Под феноменами подразумеваются истории более общего характера, которые могут привести к аномалиям, и, соответственно, они должны исключаться «на корню» движками БД. Работа (пере)определяет шесть феноменов и вводит две новых аномалии:

• P0 (Dirty Write)
• P1 (Dirty Read)
• P2 (Fuzzy or Non-Repeatable Read)
• P3 (Phantom)
• P4 (Lost Update)
• P4C (Cursor Lost Update)
• A5A (Read Skew)
• A5B (Write Skew)

Этот список кочует из статьи в статью с различными искажениями, сокращениями и дополнениями. Ччтобы перестать играть в «испорченный телефон», кратко рассмотрим, как всё обстоит на самом деле.

P0 (Dirty Write)

Этот феномен отсутствует в SQL-92, определяется так:

w1[x]...w2[x]...((c1 or a1) and (c2 or a2) in any order)

Т.е. нельзя менять то, что кто-то сейчас меняет. Такая история (феномен) может привести к аномалии:

w1[x=1]...w2[x=2]...w2[y=2]...c2...w1[y=1]...c1

• На базу наложено ограничение целостности x == y
• Первая транзакция записывает в x и y значение 1, вторая — значение 2
• В результате x == 2, y == 1, что нехорошо
• Авторы считают, что любой уровень изоляции из SQL-92 должен исключать Dirty Write

P1 (Dirty Read)

Формализация определения из стандарта:

A1: w1[x]...r2[x]...(a1 and c2 in either order)

Т.е. первая транзакция пишет в x и далее непременно должна откатиться, тем самым оставляя вторую с аномальным результатом чтения.

Критики утверждают, что на вопрос надо смотреть шире:

P1: w1[x]...r2[x]...(c1 or a1)

Нельзя читать то, что кто-то одновременно пишет, независимо от успешности пишущей транзакции. Почему так? Переводим 40 между счетами, на каждом исходно по 50, одновременно читая остатки на счетах:

H1: r1[x=50]...w1[x=10]...r2[x=10]...r2[y=50]...c2...r1[y=50]...w1[y=90]...c1

• T2 получает аномальный баланс 60
• Историю невозможно сериализовать, т.е. не существует последовательности из заданных транзакций, которая даёт такой же результат
• История не содержит никаких феноменов из SQL-92

Как можно убедиться в истинности последнего утверждения?

• A1 требует отката транзакции — в истории отсутствует
• A2 требует двойного чтения одной и той же переменной — в истории отсутствует
• A3 требует операции над множеством — в истории отсутствует

Ч.Т. Д. (ну, или Q.E. D. — кому что милее).

В общем, — «резать, не дожидаясь перитонита». Замечу, что в приводимой ранее статье в качестве Dirty Read рассматривается аномалия, а не феномен.

P2 (Fuzzy or Non-Repeatable Read)

Формализация определения из стандарта:

A2: r1[x]...w2[x]...c2...r1[x]...c1

Т.е. первая транзакция читает значение, вторая его «портит» и завершается, затем первая повторяет чтение, получая результат, отличный от результата первого чтения.

Критики утверждают, что на вопрос надо смотреть шире:

P2: r1[x]...w2[x]...(c1 or a1)

Т.е. нельзя менять то, что кто-то читает. Вторая транзакция вроде как не мешает первой, Non-Repeatable Read отсутствует, в чем проблема?! Опять с переводом денег:

H2: r1[x=50]...r2[x=50]...w2[x=10]...r2[y=50]...w2[y=90]...c2...r1[y=90]...c1

• T1 получает аномальный баланс 140
• Историю невозможно сериализовать
• История не содержит феноменов из SQL-92

P3 (Phantom)

То, что ошибочно называют Phantom Read. Формализация определения из стандарта:

A3: r1[P]...w2[y in P]...c2...r1[P]...c1

Т.е. читаем множество P, затем его «портим» и повторно читаем «порченное». «Попортить» можно как вставкой нового элемента, в результате чего он пополнит собой множество, так и обновлением существующего, так что он «перейдет» в множество.

Критики утверждают, что на вопрос надо смотреть шире:

P3: r1[P]...w2[y in P]...(c1 or a1)

• Аргументация та же, что и для P2

P4 (Lost Update)

В стандарте отсутствует, предлагается такая формулировка:

P4: r1[x=1]...w2[x=10]...w1[x=1+1]...c1

Тут Т1 «перетирает» записанное T2 значение.

• В таком виде смысла не имеет, так как содержит в себе феномен P0 (Dirty Write, w2[x=10]...w1[x=1+1]), который, по замыслу авторов, должен исключаться любым уровнем изоляции
• Можно переписать так: r1[x=1]...w2[x=10]...c2...w1[x=1+1]...c1
• Теперь внутри P2: r1[x=1]...w2[x=10]
• Неочевидный нюанс — нестандартный уровень изоляции Snapshot предотвращает P4, но не P2 (см. далее)

P4C (Cursor Lost Update)

В стандарте отсутствует, предлагается такая формулировка:

rc1[x=1]...w2[x=10]...w1[x=1+1]...c1

Здесь под rc подразумевается операция чтения через курсор, смысл феномена — запретить менять переменную, на которой находится курсор

• История предотвращается нестандартным уровнем изоляции Cursor Stability
• Я бы записал как: rc1[x=1]...w2[x=10]...c2...w1[x=1+1]...c1
  
  • Иначе опять имеет место P0
• Можно менять то, что не под курсором: rc1[x]...rc1[y]...w2[x]...c2...w1[y]...c1

A5A (Read Skew)

В стандарте отсутствует, предлагается такая формулировка:

r1[x]...w2[x]...w2[y]...c2...r1[y]...(c1 or a1)

Здесь происходит чтение согласованных значений, одно из которых в процессе чтения «портит» другая транзакций, чтение получается «кривое», прочитанные значения — несогласованные.

Пример истории с проблемой, опять переводим 40 между счетами с начальным остатком в 50:

H2: [x=50, y=50]...r1[x=50]...w2[x=10]...w2[y=90]...c2...r1[y=90]...(c1 or a1)

• T1 получает аномальный баланс 140
• Внутри аномалии содержится P2: (r1[x]...w2[x])
• Уровень изоляции, предотвращающий A5A, но не P2 — Snapshot (см. далее)

A5B (Write Skew)

В стандарте отсутствует, предлагается такая формулировка:

r1[x]...r2[y]...w1[y]...w2[x]...(c1 and c2 occur)

Имеем два согласованных значения, T1 пишет второе, исходя из прочитанного первого. Одновременная T2 делает наоборот, результирующие значения в базе несогласованные.

Пример с деньгами тут уже не подходит, пусть у нас ограничение целостности x*2 <= y, x=3, y=4, история:

[x=3, y=4]...r1[x=3]...r2[y=4]...w1[y=6]...w2[x=2]...c1...c2...[x=2, y=6]

• В истории содержится P2: r1[x=3]...w2[x=2]
• Отсутствует уровень изоляции, предотвращающий A5B, но не P2

Рассмотрим ещё уровень изоляции Snapshot; и с этой работой — всё.

Snapshot Isolation

Уровень изоляции Snapshot определяется такими требованиями:

• Updates by other transactions active after the transaction StartTimestamp are invisible to the transaction
• A transaction running in Snapshot Isolation is never blocked attempting a read
• The transaction’s writes (updates, inserts, and deletes) will also be reflected in this snapshot
• The transaction successfully commits only if no other transaction T2 with a Commit-Timestamp in T1«s execution interval [StartTimestamp, Commit-Timestamp] wrote data that T1 also wrote
  
  • Firstcommitter-wins prevents lost updates (phenomenon P4)

Ну т.е. читаем всегда то, что было на момент начала транзакции, если есть с кем-то конфликт по записи, то одна из транзакций откатывается.

Посмотрим, как обстоят дела с A2/P2 (Non-Repeatable Read):

A2: r1[x]...w2[x]...c2...r1[x]...c1

• Если подходить строго, то в таком виде история не предотвращается
• Можно сформулировать с учётом версий: r1[x1]...w2[x2]...c2...r1[x2]...c1 — вот такие истории, действительно, не допускаются

P2: r1[x]...w2[x]...(c1 or a1)

• Такие истории Snapshot допускает

Аналогично обстоят дела с A3/P3, предотвращается A3:

A3: r1[P1]...w2[y in P2]...c2...r1[P2]...c1

но не P3:

P3: r1[P1]...w2[y in P2]...(c1 or a1)

A5A (Read Skew) предотвращается в формулировке:

• r1[x1]...w2[x2]...w2[y2]...c2...r1[y2]...(c1 or a1)

Исходя из вышесказанного Table 4, похоже, содержит ошибку:

• Отношение P2 и Shapshot должно быть «Sometimes Possible», т.е. A2 невозможно, а вот P2 — вполне

Табличку я бы переписал в таком виде:

• Если рассматривать феномены так, как они определены в SQL-92, то Lost Update и Read Skew не имеют смысла для разделения уровней изоляции, т.к. они эквивалентны (в указанном смысле) A2
• Если рассматривать феномены так, как это делают «критики», то для разделения уровней изоляции не имеют смысла Read Skew (эквивалентен Lost Update) и Write Skew (эквивалентен Fuzzy Read)
• Что такое Sometimes Possible для Cursor Stability — не осилил

Идем дальше.

Работа [ABAISO] профессора D. Abadi интересна следующим:

Во-первых, личностью профессора:

He is best-known for the development of the storage and query execution engines of the C-Store (column-oriented database) prototype, which was commercialized by Vertica and eventually acquired by Hewlett-Packard in 2011, for his HadoopDB research on fault tolerant scalable analytical database systems which was commercialized by Hadapt and acquired by Teradata in 2014, and deterministic, scalable, transactional, distributed systems such as Calvin which is currently being commercialized by Fauna

Во-вторых, тем, что ничего нового из этой статьи мы не узнаем, несмотря на то, что статья датируется 2019 годом:

There are many, many problems with how the SQL standard defines these isolation levels. Most of these problems were already pointed out in 1995, but inexplicably, revision after revision of the SQL standard have been released since that point without fixing these problems.

Не зря, выходит, так вдумчиво читали критику стандарта — это актуально и в нынешнем тысячелетии. Есть, правда, нюанс — телефон таки испортился и Phantom превратился в Phantom Read.

Напоследок стоит отметить определение понятия Perfect Isolation:

The key point for our purposes is that we are defining «perfect isolation» as the ability of a system to run transactions in parallel, but in a way that is equivalent to as if they were running one after the other. In the SQL standard, this perfect isolation level is called serializability.

В статье [ABACASER] Профессор демонстрирует, что в распределенных системах уровень изоляции Serializable — далеко не предел мечтаний, всё не так, как в старые добрые времена мейнфреймов, монолитов и вертикального масштабирования:

In the good old days of having a «database server» which is running on a single physical machine, serializable isolation was indeed sufficient, and database vendors never attempted to sell database software with stronger correctness guarantees than SERIALIZABLE. However, as distributed and replicated database systems have started to proliferate in the last few decades, anomalies and bugs have started to appear in applications even when running over a database system that guarantees serializable isolation. As a consequence, database system vendors started to release systems with stronger correctness guarantees than serializable isolation, which promise a lack of vulnerability to these newer anomalies. In this post, we will discuss several well known bugs and anomalies in serializable distributed database systems, and modern correctness guarantees that ensure avoidance of these anomalies.

Для распределенных систем придумали One Copy Serializability (1SR), в работе [YB] он определяется так:

The One Copy Serializability [7] is the highest correctness criterion for replica control protocols… In order to achieve this correctness criterion, it is required that interleaved execution of transactions on replicas be equivalent to serial execution of those transactions on one copy of a database.

Ну т.е. опять требуется эквивалентность некоторому последовательному выполнению, в этот раз требование относится к транзакциям в распределенных системах. Всё ли хорошо в системе, которая удовлетворяет 1SR? Нет, не всё., Профессор приводит три аномалии, используя такую терминологию:

The next few sections describe some forms of time-travel anomalies that occur in distributed and/or replicated systems, and the types of application bugs that they may cause.

1. Immortal Write (Бессмертная Запись)

Пользователь меняет своё отображаемое имя, Daniel => Danny => Danger:

• История в реальном времени: w1[x=Daniel]...c1...w2[x=Danny]...c2...w3[x=Danger]...c3
• История в журнале 1SR-системы: w1[x=Daniel]...w3[x=Danger]...w2[x=Danny]

Наблюдаем анахронизм (time-travel anomaly) — значение Danger было послано последним, но движок БД в силу каких-то причин переставил w3 на второе место. Причиной может быть, например, рассинхронизация часов на серверах или же некие «соображения» движка БД по оптимизации времени выполнения транзакций. От такой «перестановки» требования Serializability никак не нарушаются, так что движок в своем праве поступать таким образом.

2. Stale Read (Несвежее Чтение)

Пишем в некоторую переменную 50, затем 0, потом читаем, ожидая 0:

• История в реальном времени: w1[x=50]...с1...w2[x=0]...c2...r3...c3
• История в журнале 1SR-системы: w1[x=50]...r3[x=50]...w2[x=0]

Кластер БД опять «переставил» транзакции, внезапно получаем 50.

3. Causal Reverse (Обратная Причинность, «реверс козла»)

Ситуация: пользователь имеет 1.000.000 на счету x и 0 на счету y. Читаем остатки, снимаем в банкомате 1.000.000 со счета x и затем кладем миллион на счет y.

• История в реальном времени: r1[x, y]...w2[x=0]...c2...w3[y=1.000.000]...c3...с1
• История в журнале 1SR-системы: w3[y=1.000.000]...r1[x=1.000.000, y=1.000.000]...w2[x=0]

БД опять повела себя дерзко и переставила r1 на второе место, так что r1 «вычитала» по миллиону с обоих счетов.

Утверждается, что такая аномалия возможна в CockroachDB (aka CRDB) из-за особенностей системы (STRONG PARTITION SERIALIZABLE) и нерешаемой проблемы с синхронизацией часов: «this enables a read (in CockroachDB«s case, this read has to be sent to the system before the two write transactions) to potentially see the write of the later transaction, but not the earlier one».

С негодованием отвергнем CockroachDB? Мне кажется, не стоит, работая с другими системами, мы можем просто пребывать в счастливом неведении о тех ужасах, что происходят под «распределенным капотом».

Гарантии свободной от «ужасов» системы Профессор называет Strict Serializability (т.е. Строго-Совершенная Изоляция, да) и выделяет такие ступеньки на пути к идеалу:

• Strong Session Serializable: система гарантирует Strict Serializability в рамках сессии, иначе 1SR
  
  • Очевидная реализация это маршрутизация «sticky session», т.е. все запросы с одинаковой сессией направляются к одному и тому же узлу
• Strong Write Serializable: система гарантирует Strict Serializability для пишущих транзакций, read-only транзакции довольствуются уровнем 1SR
  
  • Очевидная реализация — это кластер с одной master-репликой, на которой можно менять данные, и множеством read-only реплик
• Strong Partition Serializable: cистема гарантирует Strict Serializability в рамках разделов
  
  • Именно такой подход, к слову, принят в CocroachDB и в нашем стартапе
  • Можно использовать shard в качестве partition, но у нас, к примеру, не так, и partition включает в себя множество shard

В заключении Профессор приводит табличку:

Идем дальше.

«Суха теория, мой друг, но древо жизни зеленеет». Сильные духом могут почитать [COSMOS], Microsoft, Consistency levels in Azure Cosmos DB, 2022, здесь ограничусь перечислением Consistency levels, принятых в этой СУБД:

• Strong (Сильная)
• Bounded staleness ([baʊndɪd ˈsteɪlnəs], Запаздывание, Ограниченное устаревание, Ограниченная несвежесть)
  
  • Т.е. читатель может получить несвежие данные, но их запаздывание ограничено по времени и/или по количеству операций
• Session (Сеанс, Сессионная)
• Consistent prefix ([kənˈsɪstənt ˈpriːfɪks], Согласованный префикс)
  
  • This guarantee says that if a sequence of writes happens in a certain order, then anyone reading those writes will see them appear in the same order [CLEPP] (порядок соблюдается, но читаем с произвольным запаздыванием)
• Eventual (Итоговая, Светлое будущее)
  
  • Когда-то всё будет хорошо

Для Strong дается такая картинка:

Т.е. пишем в одну зону, в других читаем без всяких time-travel аномалий.

Вроде как Strong аналогична Strict Serializable у Профессора и c Cosmos DB всё хорошо, так? Нет, не так…

Может показаться, что всё очень запутано

© Habrahabr.ru