Про Транзакции
Sep. 22nd, 2011 12:43 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sassa_nfНичё я не разродился бложить. Просто в свете дискуссий на тему транзакций, БД, локов и прочаго, решил поделиться "конспектом лекций", накопившимся за последние годы.
disclaimer: Все умные мысли ниже принадлежат Jim Starkey и Maurice Herlihy, unless specified otherwise; все глупости - мои личные. Почему нужно курить траву из рук этих двух дядек - это вы уж сами погуглите как-нибудь.
Извините, я не могу так ладно и стройно рассказать, как J.S.
Basic Stuff about Transactions
Транзакции являются способом реализации ACID. Мы ещё слышим одобрительные возгласы по поводу BASE вытесняющем ACID, но мне кажется проблемы с масштабированием ACID чаще путают с проблемами с locking databases. Когда речь заходит о MVCC, народ как-то не до конца понимает всю глубину этой технологии. Википедию о MVCC читать вредно; начать хотя бы с заявления, что транзакции должны быть serialized (unless уже исправлено).
Начнём с каверзного вопроса: "когда транзакция B видит результаты транзакции A?" Зависимо от образования, люди дают разные неправильные ответы. В основном люди ссылаются на обозначение "когда транзакция А закончилась". А когда транзакция A должна закончиться? Но ведь нету такого "должна" в транзакции A! Значит, БД имеет право закончить транзакцию A когда угодно. Очень ленивая БД может и вовсе никому не сказать, что commit закончился, пока её кто-то не спросит.
Так вот, вот это последнее "пока её кто-то не спросит" и есть правильный ответ.
Можете рассматривать транзакцию, как подобие synchronized блока. Когда лок отпущен, изменения, произведённые внутри блока, должны стать видимы, а до того - не обязаны (хотя и могут быть). А когда лок должен быть отпущен? Когда вы помечаете в коде закрывающую скобку блока, ещё не факт, что JVM решит отпустить лок именно тогда, но об этом можно ещё мнооого писать.
consistency
BASE "продаётся" как БД с eventual consistency. Что это за зверь такой, eventual consistency? Кто это самое consistency восстанавливает? update либо consistent (соответствует ограничениям схемы), либо нет. Например, consistent update - это когда список никогда не превращается в кольцо. Если ваша БД или приложение позволяет создать кольцо (в BASE), значит, никаких constraints нет, и зачем говорить о consistency. Так и говорите, что all updates are eventually visible to everyone. Это другое дело. И ACID такое может делать самым естественным образом. Другое дело, что никто так не делает. Ну, никто, кроме J. S. Как? look for inspiration в coherency protocols, memory models и HTM.
Вот, допустим, в транзакции A в строку "Иван Топорищев" добавили к 10 на балансе счёта 100. А в транзакции B из строки "Иван Топорищев" прочитали баланс 10. Когда B должна увидеть эти 100? А никогда, если это всё, что транзакции A и B сделали. Потому что такое поведение не нарушает consistency. Может, такое поведение нарушает least surprise principle, но это другой вопрос, и все БД стремятся его понизить.
Для того, чтобы заставить транзакцию B увидеть 100, нужно, чтобы транзакции A и B модифицировали ещё что-то общее - что создаст каузальную связь - например, в голову приходят такие вещи, как autoincrement. Вообще-то, поле autoincrement - это геморрой. (Что делать с autoincrement, если транзакция got rolled back?) Поэтому гуглите, что делает CREATE SEQUENCER.
lost update
Критики могут возразить "какое же consistency, если update распространяется так лениво? А вдруг ленивость update приведёт к inconsistent update?" Не получим ли мы lost update? Ну, во-первых, lost update можно получить и с лочной реализацией транзакций. Объяснение этому феномену вы можете найти, ответив на вопрос: Что должно вернуть select *, если есть конкурентно выполняемые транзакции, добавляющие строки в таблицу? Или: почему мы проверили java.util.Vector.size() и вынули ровно столько элементов, а Vector всё ещё не empty?
А во-вторых, каузальная связь между обозреваемыми значениями и есть та вещь, которая гарантирует consistency. Если транзакция B может видеть 10 на счету "Иван Топорищев" "после" завершения транзакции A, и успешно commit транзакцию B, значит, вид вселенной из B и её изменения не нарушают consistency.
Так что, изречение "update будет lost" нужно заменить на вопрос "будет update lost?" Это задача coherency protocol.
coherency protocol
Смотрим, как решают вопрос consistency другие. Многокорник в наши дни содержит кэши. Так вот, кэши - это и есть состояния view (транзакция лочной БД плохо подходит, а вот транзакция MVCC БД ложится на это понятие очень хорошо). В процессорах без поддержки hardware transactional memory каждая операция с памятью является атомарной - можете рассматривать их как такие себе малюсенькие транзакции. Каждое значение может иметь две версии: старая и нынешняя. Скажем, в терминах MESI протокола, MES соответствуют "нынешняя", а I - "старая". Значения в состоянии "I" могут быть выброшены из кэша. Если значение находится в кэше одного процессора, оно в состоянии E. Если значение было с поры прочтения модифицировано, оно переходит в состояние M - это служит сигналом memory managerу, что нужно следить обращениями к соответствующей ячейке памяти другими процессорами и устройствами. Когда значение существует в кэшах более одного процессора, оно у обоих находится в состоянии S.
Допустим, один из процессоров решает изменить значение в состоянии S. При этом он просто сообщает остальным, что теперь у них у всех это значение в состоянии I, а своё новое значение переводит в состояние M.
Так что, совсем не обязательно лочить весь мир, чтобы update цену Kindle. update никогда не lost, но и каждый update не обязательно останавливает весь мир. И те процессоры, у которых цена Kindle уже в регистрах, продолжат свою работу, игнорируя изменения в кэше. И consistency при этом либо не нарушается, либо ошибка в конкурентном алгоритме. Последнее решается путём synchronized = сериализацией транзакций. Но это не обязательное условие. Можно написать корректный конкурентный алгоритм и без synchronized. Всегда.
HTM
Hardware Transactional Memory - это MESI+T. Каждое значение может иметь три версии: старая, нынешняя и будущая. В процессоре есть несколько новых инструкций. Значение может находиться в состояниях MESI, и может находиться в состояниях TM, TE, TS, TI. Значения в состоянии TI не выбрасываются из кэша, в отличие от значений в состоянии I. Значения в состоянии TE, TS работают, как E, S соответственно. Значения в состоянии TM не навязывают модифицированное значение другим процессорам (изменения в транзакции изолированы от других транзакций), т.к. это "будущая" версия значения.
Чтобы значение попало в состояние TE или TS, нужно выполнить tload вместо обычного load. Чтобы значение перешло в состояние TM, нужно, чтобы было выполнено store в значение в состоянии TE или TS, или tstore. Чтобы значение перешло в состояние TI, нужно, чтобы процессор получил сигнал invalidation от другого процессора - т.е. какой-то другой процессор успешно завершил свою транзакцию (или сделал non-transactional store). В то время, как чтение значений в состоянии I приводит к общению с другими процессорами, чтобы получить up-to-date копию, значения в состоянии TI доступны для чтения без такого общения (транзакция продолжает наслаждаться своим видом на вселенную, даже если процессору уже известно, что в итоге будет rollback).
Флаг T не сбрасывается, пока процессор не выполнит rollback или успешный commit. rollback просто молча переводит все значения TM, TI в состояние I, а у TE, TS просто сбрасываем флаг T. Программа может запросить validate, который вернёт true, только если в кэше нет значений в состоянии TI (это такой сервис, чтобы long-running transaction могла решить "свалить" не доходя до commit).
commit проходит успешно и сбрасывает флаг T у всех значений, если в кэше нет значений в состоянии TI. Значения, которые были TM, становятся в состоянии M и вызывают invalidation этого значения у других процессоров. Заметьте, программы на других процессоры не знают, что транзакция завершилась - они продолжают успешно читать "старое" значение из своих TI. Успех транзакции - это локально обозреваемое явление. Об успехе транзакции в другом процессоре станет известно только когда commit или validate fails.
Замените процессоры на распределённые ноды and you get the picture.
serialization
Ещё один stumbling block, на который напарываются многие, это восприятие БД, как "состояние предметной области". Отсюда и растут ноги у сериализации, как необходимого способа перевести предметную область в новое состояние.
А вот нету его, этого состояния. БД - это журчащий поток, в нём всё течёт и меняется. Да, можно говорить об эталонной последовательности и о сериализации как мериле корректности поведения БД. Но задача БД - это enforce schema constraints = data consistency.
Где-то так.
disclaimer: Все умные мысли ниже принадлежат Jim Starkey и Maurice Herlihy, unless specified otherwise; все глупости - мои личные. Почему нужно курить траву из рук этих двух дядек - это вы уж сами погуглите как-нибудь.
Извините, я не могу так ладно и стройно рассказать, как J.S.
Basic Stuff about Transactions
Транзакции являются способом реализации ACID. Мы ещё слышим одобрительные возгласы по поводу BASE вытесняющем ACID, но мне кажется проблемы с масштабированием ACID чаще путают с проблемами с locking databases. Когда речь заходит о MVCC, народ как-то не до конца понимает всю глубину этой технологии. Википедию о MVCC читать вредно; начать хотя бы с заявления, что транзакции должны быть serialized (unless уже исправлено).
Начнём с каверзного вопроса: "когда транзакция B видит результаты транзакции A?" Зависимо от образования, люди дают разные неправильные ответы. В основном люди ссылаются на обозначение "когда транзакция А закончилась". А когда транзакция A должна закончиться? Но ведь нету такого "должна" в транзакции A! Значит, БД имеет право закончить транзакцию A когда угодно. Очень ленивая БД может и вовсе никому не сказать, что commit закончился, пока её кто-то не спросит.
Так вот, вот это последнее "пока её кто-то не спросит" и есть правильный ответ.
Можете рассматривать транзакцию, как подобие synchronized блока. Когда лок отпущен, изменения, произведённые внутри блока, должны стать видимы, а до того - не обязаны (хотя и могут быть). А когда лок должен быть отпущен? Когда вы помечаете в коде закрывающую скобку блока, ещё не факт, что JVM решит отпустить лок именно тогда, но об этом можно ещё мнооого писать.
consistency
BASE "продаётся" как БД с eventual consistency. Что это за зверь такой, eventual consistency? Кто это самое consistency восстанавливает? update либо consistent (соответствует ограничениям схемы), либо нет. Например, consistent update - это когда список никогда не превращается в кольцо. Если ваша БД или приложение позволяет создать кольцо (в BASE), значит, никаких constraints нет, и зачем говорить о consistency. Так и говорите, что all updates are eventually visible to everyone. Это другое дело. И ACID такое может делать самым естественным образом. Другое дело, что никто так не делает. Ну, никто, кроме J. S. Как? look for inspiration в coherency protocols, memory models и HTM.
Вот, допустим, в транзакции A в строку "Иван Топорищев" добавили к 10 на балансе счёта 100. А в транзакции B из строки "Иван Топорищев" прочитали баланс 10. Когда B должна увидеть эти 100? А никогда, если это всё, что транзакции A и B сделали. Потому что такое поведение не нарушает consistency. Может, такое поведение нарушает least surprise principle, но это другой вопрос, и все БД стремятся его понизить.
Для того, чтобы заставить транзакцию B увидеть 100, нужно, чтобы транзакции A и B модифицировали ещё что-то общее - что создаст каузальную связь - например, в голову приходят такие вещи, как autoincrement. Вообще-то, поле autoincrement - это геморрой. (Что делать с autoincrement, если транзакция got rolled back?) Поэтому гуглите, что делает CREATE SEQUENCER.
lost update
Критики могут возразить "какое же consistency, если update распространяется так лениво? А вдруг ленивость update приведёт к inconsistent update?" Не получим ли мы lost update? Ну, во-первых, lost update можно получить и с лочной реализацией транзакций. Объяснение этому феномену вы можете найти, ответив на вопрос: Что должно вернуть select *, если есть конкурентно выполняемые транзакции, добавляющие строки в таблицу? Или: почему мы проверили java.util.Vector.size() и вынули ровно столько элементов, а Vector всё ещё не empty?
А во-вторых, каузальная связь между обозреваемыми значениями и есть та вещь, которая гарантирует consistency. Если транзакция B может видеть 10 на счету "Иван Топорищев" "после" завершения транзакции A, и успешно commit транзакцию B, значит, вид вселенной из B и её изменения не нарушают consistency.
Так что, изречение "update будет lost" нужно заменить на вопрос "будет update lost?" Это задача coherency protocol.
coherency protocol
Смотрим, как решают вопрос consistency другие. Многокорник в наши дни содержит кэши. Так вот, кэши - это и есть состояния view (транзакция лочной БД плохо подходит, а вот транзакция MVCC БД ложится на это понятие очень хорошо). В процессорах без поддержки hardware transactional memory каждая операция с памятью является атомарной - можете рассматривать их как такие себе малюсенькие транзакции. Каждое значение может иметь две версии: старая и нынешняя. Скажем, в терминах MESI протокола, MES соответствуют "нынешняя", а I - "старая". Значения в состоянии "I" могут быть выброшены из кэша. Если значение находится в кэше одного процессора, оно в состоянии E. Если значение было с поры прочтения модифицировано, оно переходит в состояние M - это служит сигналом memory managerу, что нужно следить обращениями к соответствующей ячейке памяти другими процессорами и устройствами. Когда значение существует в кэшах более одного процессора, оно у обоих находится в состоянии S.
Допустим, один из процессоров решает изменить значение в состоянии S. При этом он просто сообщает остальным, что теперь у них у всех это значение в состоянии I, а своё новое значение переводит в состояние M.
Так что, совсем не обязательно лочить весь мир, чтобы update цену Kindle. update никогда не lost, но и каждый update не обязательно останавливает весь мир. И те процессоры, у которых цена Kindle уже в регистрах, продолжат свою работу, игнорируя изменения в кэше. И consistency при этом либо не нарушается, либо ошибка в конкурентном алгоритме. Последнее решается путём synchronized = сериализацией транзакций. Но это не обязательное условие. Можно написать корректный конкурентный алгоритм и без synchronized. Всегда.
HTM
Hardware Transactional Memory - это MESI+T. Каждое значение может иметь три версии: старая, нынешняя и будущая. В процессоре есть несколько новых инструкций. Значение может находиться в состояниях MESI, и может находиться в состояниях TM, TE, TS, TI. Значения в состоянии TI не выбрасываются из кэша, в отличие от значений в состоянии I. Значения в состоянии TE, TS работают, как E, S соответственно. Значения в состоянии TM не навязывают модифицированное значение другим процессорам (изменения в транзакции изолированы от других транзакций), т.к. это "будущая" версия значения.
Чтобы значение попало в состояние TE или TS, нужно выполнить tload вместо обычного load. Чтобы значение перешло в состояние TM, нужно, чтобы было выполнено store в значение в состоянии TE или TS, или tstore. Чтобы значение перешло в состояние TI, нужно, чтобы процессор получил сигнал invalidation от другого процессора - т.е. какой-то другой процессор успешно завершил свою транзакцию (или сделал non-transactional store). В то время, как чтение значений в состоянии I приводит к общению с другими процессорами, чтобы получить up-to-date копию, значения в состоянии TI доступны для чтения без такого общения (транзакция продолжает наслаждаться своим видом на вселенную, даже если процессору уже известно, что в итоге будет rollback).
Флаг T не сбрасывается, пока процессор не выполнит rollback или успешный commit. rollback просто молча переводит все значения TM, TI в состояние I, а у TE, TS просто сбрасываем флаг T. Программа может запросить validate, который вернёт true, только если в кэше нет значений в состоянии TI (это такой сервис, чтобы long-running transaction могла решить "свалить" не доходя до commit).
commit проходит успешно и сбрасывает флаг T у всех значений, если в кэше нет значений в состоянии TI. Значения, которые были TM, становятся в состоянии M и вызывают invalidation этого значения у других процессоров. Заметьте, программы на других процессоры не знают, что транзакция завершилась - они продолжают успешно читать "старое" значение из своих TI. Успех транзакции - это локально обозреваемое явление. Об успехе транзакции в другом процессоре станет известно только когда commit или validate fails.
Замените процессоры на распределённые ноды and you get the picture.
serialization
Ещё один stumbling block, на который напарываются многие, это восприятие БД, как "состояние предметной области". Отсюда и растут ноги у сериализации, как необходимого способа перевести предметную область в новое состояние.
А вот нету его, этого состояния. БД - это журчащий поток, в нём всё течёт и меняется. Да, можно говорить об эталонной последовательности и о сериализации как мериле корректности поведения БД. Но задача БД - это enforce schema constraints = data consistency.
Где-то так.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2011-09-28 09:52 pm (UTC)А потом пришли программисты и сказали - нам всё это нафик не нужно, это сложно и долго, а времени на всё это менеджмент всё равно не выделит - и написали себе свои базы с блэкджеком и шлюхами.
no subject
Date: 2011-09-30 09:11 am (UTC)