При одновременном управлении базами данных , [1] [2] обработке транзакций (управлении транзакциями) и различных транзакционных приложениях (например, транзакционной памяти [3] и программной транзакционной памяти ), как централизованных, так и распределенных , расписание транзакций сериализуется , если их результат (например, результирующее состояние базы данных) равно результату ее транзакций, выполняемых последовательно, т.е. без перекрытия во времени. Транзакции обычно выполняются одновременно (они перекрываются), поскольку это наиболее эффективный способ. Сериализуемость является основным критерием правильности выполнения параллельных транзакций . Он считается высшим уровнем изоляции между транзакциями и играет важную роль в управлении параллелизмом . По существу, он поддерживается во всех системах баз данных общего назначения. Сильная строгая двухфазная блокировка (SS2PL) — популярный механизм сериализуемости, используемый в большинстве систем баз данных (в различных вариантах) с момента их появления в 1970-х годах.
Теория сериализуемости обеспечивает формальную основу для размышлений и анализа сериализуемости и ее методов. Хотя он носит математический характер, его основы неофициально (без математических обозначений) представлены ниже.
Сериализуемость расписания означает эквивалентность (по результату, состоянию базы данных, значениям данных) последовательному расписанию (т.е. последовательному, без перекрытия транзакций во времени) с одинаковыми транзакциями. [ нужна цитата ]
Серийность означает, что транзакции не перекрываются во времени и не могут мешать друг другу, т.е. существует полная изоляция между собой. Любой порядок транзакций является законным, если между ними не существует зависимостей, что и предполагается (см. комментарий ниже).
Сериализуемость используется для поддержания данных в элементе данных в согласованном состоянии. Сериализуемость — это свойство расписания транзакций (истории). Это основной критерий правильности расписания параллельных транзакций, поэтому он поддерживается во всех системах баз данных общего назначения. Расписания, которые не подлежат сериализации, могут привести к ошибочным результатам; что может быть чрезвычайно вредным при работе с деньгами в банках.
Если приложение запрашивает какой-либо конкретный порядок между некоторыми транзакциями, то он применяется независимо от базовых механизмов сериализации. Эти механизмы обычно безразличны к какому-либо конкретному порядку и генерируют некоторый непредсказуемый частичный порядок , который обычно совместим с несколькими последовательными порядками этих транзакций. Этот частичный порядок является результатом порядка планирования операций доступа к данным параллельных транзакций, который зависит от многих факторов.
Основной характеристикой транзакции базы данных является атомарность , что означает, что она либо фиксируется , т. е. все результаты ее операций вступают в силу в базе данных, либо прерывается (откатывается), при этом результаты всех ее операций не оказывают никакого влияния на транзакцию базы данных. база данных (семантика транзакции «все или ничего»). Во всех реальных системах транзакции могут быть прерваны по многим причинам, и сама по себе сериализуемость недостаточна для корректности. Расписания также должны обладать свойством восстанавливаемости (после прерывания). Возможность восстановления означает, что зафиксированные транзакции не считывают данные, записанные прерванными транзакциями (эффекты которых не существуют в результирующих состояниях базы данных). Хотя в настоящее время во многих приложениях возможность сериализации намеренно подвергается риску для повышения производительности (только в тех случаях, когда корректность приложения не страдает), нарушение возможности восстановления может быстро нарушить целостность базы данных, а также целостность результатов транзакций, внешних по отношению к базе данных. Расписание со свойством восстанавливаемости ( восстанавливаемое расписание) «восстанавливается» после прерываний само по себе, т. е. прерывания не наносят ущерба целостности зафиксированных транзакций и результирующей базы данных. Это неверно без возможности восстановления, когда вероятные нарушения целостности (приводящие к неправильным данным базы данных) требуют специальных, обычно ручных, корректирующих действий в базе данных.
Реализация возможности восстановления в ее общей форме может привести к каскадному прерыванию : прерывание одной транзакции может привести к необходимости прервать вторую транзакцию, затем третью и так далее. Это приводит к потере уже частично выполненных транзакций, а также может привести к снижению производительности. Предотвращение каскадных прерываний (ACA или Cascadeless) — это особый случай возможности восстановления, который точно предотвращает такие явления. Часто на практике используется особый случай ACA: строгость . Строгость обеспечивает эффективное восстановление базы данных после сбоя.
Обратите внимание, что свойство восстанавливаемости необходимо, даже если сбой базы данных не произошел и восстановление базы данных после сбоя не требуется. Скорее, это необходимо для правильной автоматической обработки прерываний, которые могут быть не связаны с сбоем базы данных и восстановлением после сбоя.
Ослабленная сериализуемость позволяет контролировать нарушения сериализуемости для достижения более высокой производительности. Более высокая производительность означает лучшую скорость выполнения транзакций и более короткое среднее время ответа на транзакцию (продолжительность транзакции). Расслабленная сериализуемость используется, когда абсолютная корректность недавно измененных данных не требуется (например, при получении списка продуктов). Изоляция моментальных снимков — это распространенный метод упрощенной сериализации.
Ослабление распределенной сериализуемости часто необходимо для эффективной крупномасштабной репликации данных , поскольку использование одной атомарной распределенной транзакции для синхронизации нескольких реплик может привести к недоступности компьютеров и сетей , что приведет к аварийному завершению работы. [4] Оптимистическая репликация — это распространенный метод ослабления распределенной сериализуемости, который ставит под угрозу конечную согласованность .
Классы расписаний, определенные свойствами ослабленной сериализуемости , либо содержат класс сериализуемости, либо несравнимы с ним.
Механизмы, обеспечивающие сериализуемость, должны выполняться в реальном времени или почти в реальном времени, пока транзакции выполняются с высокой скоростью. Чтобы удовлетворить этому требованию, используются особые случаи сериализуемости, достаточные условия сериализуемости, которые можно эффективно обеспечить.
Существует два основных типа сериализуемости: сериализуемость представлений и сериализуемость конфликтов . Сериализуемость представления соответствует общему определению сериализуемости, данному выше. Сериализуемость конфликтов — это широкий частный случай, т. е. любое расписание, которое можно сериализовать по конфликтам, также сериализуемо по представлениям, но не обязательно наоборот. Сериализуемость конфликтов широко используется, поскольку ее легче определить, и она охватывает значительную часть сериализуемых в представлении расписаний. Определение сериализуемости представления расписания является NP-полной проблемой (класс задач, известные решения которых требуют только сложных вычислений и требуют слишком много времени).
Операции с данными выполняются по чтению или записи (запись: вставка , обновление или удаление ). Две операции конфликтуют , если они относятся к разным транзакциям с одним и тем же элементом данных (элементом данных) и хотя бы одна из них — write . Каждая такая пара конфликтующих операций имеет тип конфликта : это либо чтение-запись , либо запись-чтение , либо конфликт запись-запись . Говорят, что транзакция второй операции в паре конфликтует с транзакцией первой операции. Более общее определение конфликтующих операций (также для сложных операций, каждая из которых может состоять из нескольких «простых» операций чтения/записи) требует, чтобы они были некоммутативными (изменение их порядка также меняет их общий результат). Каждая такая операция сама по себе должна быть атомарной (с использованием надлежащей системной поддержки), чтобы ее можно было считать операцией проверки коммутативности. Например, операции чтения-чтения коммутативны (в отличие от чтения-записи и других возможностей), и поэтому чтение-чтение не является конфликтом. Еще один более сложный пример: операции увеличения и уменьшения счетчика являются операциями записи (обе изменяют счетчик), но их не нужно считать конфликтующими (тип конфликта записи-записи), поскольку они коммутативны (таким образом, увеличение-уменьшение не является конфликт; например, уже поддерживался в «быстром пути» старой IBM IMS ). При проверке эквивалентности последовательному расписанию важен только приоритет (порядок времени) в парах конфликтующих (некоммутативных) операций, поскольку разные расписания, состоящие из одних и тех же транзакций, могут трансформироваться один в другой путем изменения порядков между операциями разных транзакций ( чередование различных транзакций), а также поскольку изменение порядка коммутативных операций (неконфликтных) не меняет общий результат последовательности операций, т. е. результат расписания (результат сохраняется за счет изменения порядка между неконфликтующими операциями, но обычно не тогда, когда порядок изменения конфликтующих операций). Это значит, что если расписание можно преобразовать в любое последовательное расписание, не меняя порядков конфликтующих операций (но изменяя порядки неконфликтных, сохраняя при этом порядок операций внутри каждой транзакции), то результат обоих расписаний один и тот же, и расписание по определению сериализуема по конфликтам.
Конфликты являются причиной блокировки транзакций и задержек (нематериализованных конфликтов) или отмены транзакций из-за предотвращения нарушения сериализуемости. Обе возможности снижают производительность. Таким образом, уменьшение количества конфликтов, например, за счет коммутативности (если это возможно), является способом повышения производительности.
Транзакция может выдать/запросить конфликтующую операцию и вступить в конфликт с другой транзакцией, пока ее конфликтующая операция задерживается и не выполняется (например, блокируется блокировкой ) . Только выполненные ( материализованные ) конфликтующие операции имеют отношение к сериализуемости конфликтов (подробнее см. ниже).
Граф приоритетов , также называемый графом конфликтов [5] и графом сериализуемости, используется в контексте управления параллелизмом в базах данных . [6] Это ориентированный граф , представляющий приоритет транзакций в расписании, отражаемый приоритетом конфликтующих операций в транзакциях. Расписание является сериализуемым для конфликтов тогда и только тогда, когда его график приоритета зафиксированных транзакций является ациклическим .
Граф приоритета для расписания S содержит:
Механизмы, обеспечивающие сериализуемость, обычно не поддерживают граф приоритетов как структуру данных, а скорее неявно предотвращают или разрывают циклы (например, SS2PL ниже).
Сильная строгая двухфазная блокировка (SS2PL) — это распространенный механизм, используемый в системах баз данных с первых дней их существования в 1970-х годах (хотя «SS» в названии SS2PL более новый) для обеспечения как сериализуемости конфликтов, так и строгости (особый случай возможность восстановления, которая позволяет эффективно восстанавливать базу данных после сбоя) расписания. В соответствии с этим механизмом каждый элемент данных блокируется транзакцией перед доступом к нему (в любой операции чтения или записи): элемент помечается и связывается с блокировкой определенного типа в зависимости от выполняемой операции (и конкретной реализации транзакции). ; существуют различные модели с разными типами блокировок; в некоторых моделях блокировки могут менять тип в течение жизни транзакции). В результате доступ другой транзакции может быть заблокирован, как правило, в случае конфликта (блокировка задерживает или полностью предотвращает материализацию конфликта и его отражение в графе приоритетов путем блокировки конфликтующей операции), в зависимости от типа блокировки и конфигурации другой транзакции. тип операции доступа. Использование механизма SS2PL означает, что все блокировки данных от имени транзакции снимаются только после завершения транзакции (либо фиксации, либо отмены).
SS2PL — это также имя результирующего свойства расписания, которое также называется строгостью . SS2PL — это особый случай ( собственное подмножество ) двухфазной блокировки (2PL).
Взаимная блокировка транзакций приводит к тупику , при котором выполнение этих транзакций останавливается и завершение не может быть достигнуто. Таким образом, тупиковые ситуации необходимо разрешить, чтобы завершить выполнение этих транзакций и освободить соответствующие вычислительные ресурсы. Взаимная блокировка — это отражение потенциального цикла в графе приоритетов, который мог бы произойти без блокировки при материализации конфликтов. Взаимная блокировка разрешается путем прерывания транзакции, связанной с таким потенциальным циклом, и разрыва цикла. Часто выявляется с помощью графа ожидания (графа конфликтов, заблокированных блокировками от материализации; его также можно определить как граф нематериализованных конфликтов; нематериализованные конфликты не отражаются в графе приоритета и не влияют на сериализуемость), который указывает, какая транзакция «ожидает» снятия одной или нескольких блокировок, посредством которой другая транзакция или транзакции, а цикл в этом графе означает тупик. Прерывания одной транзакции за цикл достаточно, чтобы разорвать цикл. Транзакции, прерванные из-за разрешения взаимоблокировки, перезапускаются и немедленно выполняются снова.
Другие известные механизмы включают:
Вышеуказанные методы (конфликтной) сериализуемости в их общей форме не обеспечивают восстанавливаемости. Для повышения возможности восстановления необходимы специальные улучшения.
Методы управления параллелизмом делятся на три основных типа:
Основным отличием типов приемов являются типы конфликтов, которые они порождают. Пессимистический метод блокирует транзакционную операцию при конфликте и генерирует нематериализованный конфликт, а оптимистический метод не блокирует и генерирует материализованный конфликт. Полуоптимистический метод порождает оба типа конфликтов. Оба типа конфликтов генерируются хронологическим порядком вызова транзакционных операций, независимо от типа конфликта. Цикл зафиксированных транзакций (с материализованными конфликтами) в графе приоритетов (графе конфликтов) представляет собой нарушение сериализуемости, и его следует избегать для поддержания сериализуемости. Цикл (нематериализованных) конфликтов в графе ожидания представляет собой тупиковую ситуацию, которую следует разрешить путем разрыва цикла. Оба типа циклов возникают в результате конфликтов и должны быть разорваны. При любом типе метода конфликты должны обнаруживаться и учитываться с одинаковыми накладными расходами как для материализованных, так и для нематериализованных конфликтов (обычно с использованием таких механизмов, как блокировка, либо с блокировкой для блокировок, либо без блокировки, но с записью конфликта для материализованных конфликтов). В методе блокировки обычно переключение контекста происходит в случае конфликта с (дополнительными) издержками. В противном случае вычислительные ресурсы, связанные с заблокированными транзакциями, останутся бездействующими и неиспользованными, что может быть худшей альтернативой. Когда конфликты возникают нечасто, оптимистические методы обычно имеют преимущество. При различных нагрузках транзакций (сочетании типов транзакций) один тип метода (т. е. оптимистический или пессимистический) может обеспечить лучшую производительность, чем другой.
Если классы расписания не являются по своей сути блокирующими (т. е. они не могут быть реализованы без блокировки операций доступа к данным; например, 2PL, SS2PL и SCO выше; см. диаграмму), они также могут быть реализованы с использованием оптимистических методов (например, сериализуемости, возможности восстановления).
Многоверсионное управление параллелизмом (MVCC) сегодня является распространенным способом повышения параллелизма и производительности за счет создания новой версии объекта базы данных каждый раз, когда объект записывается, и разрешения операций чтения транзакций нескольких последних соответствующих версий (каждого объекта). в зависимости от метода планирования. MVCC можно комбинировать со всеми перечисленными выше методами сериализации (кроме SerializableSI, который изначально основан на MVCC). Он используется в большинстве продуктов СУБД общего назначения.
MVCC в настоящее время особенно популярен благодаря методу смягченной сериализуемости (см. выше) изоляции моментальных снимков (SI), который обеспечивает лучшую производительность, чем большинство известных механизмов сериализуемости (за счет возможного нарушения сериализуемости в некоторых случаях). SerializableSI , который является эффективным усовершенствованием SI, делающим его сериализуемым, предназначен для предоставления эффективного сериализуемого решения. SerializableSI был проанализирован [7] [8] с помощью общей теории MVCC.
Распределенная сериализуемость — это сериализуемость расписания транзакционной распределенной системы (например, системы распределенных баз данных ). Такая система характеризуется распределенными транзакциями (также называемыми глобальными транзакциями ), т.е. транзакциями, которые охватывают компьютерные процессы (абстракция процесса в общем смысле, зависящая от вычислительной среды; например, поток операционной системы ) и, возможно, сетевые узлы. Распределенная транзакция включает в себя более одной из нескольких локальных субтранзакций , каждая из которых имеет состояния, описанные выше для транзакции базы данных. Локальная субтранзакция включает в себя один процесс или несколько процессов, которые обычно выходят из строя вместе (например, в одном ядре процессора ). Распределенные транзакции подразумевают необходимость в протоколе атомарной фиксации для достижения консенсуса между его локальными субтранзакциями о том, следует ли их фиксировать или прерывать. Такие протоколы могут варьироваться от простого (однофазного) установления связи между процессами, которые терпят сбой вместе, до более сложных протоколов, таких как двухфазная фиксация , для обработки более сложных случаев сбоя (например, сбоя процесса, узла, связи и т. д.). Распределенная сериализуемость является основной целью контроля правильности распределенного параллелизма . С распространением Интернета , облачных вычислений , сетевых вычислений и небольших портативных мощных вычислительных устройств (например, смартфонов ) потребность в эффективных методах распределенной сериализации для обеспечения корректности внутри и между распределенными приложениями, по-видимому, возрастает.
Распределенная сериализуемость достигается за счет реализации распределенных версий известных централизованных методов. [1] [2] Как правило, все такие распределенные версии требуют использования информации о конфликтах (материализованных или нематериализованных конфликтах или, что то же самое, о приоритете транзакций или информации о блокировке; обычно используется сериализуемость конфликтов), которая генерируется не локально, а скорее в различных процессах и удаленных местах. Таким образом, необходимо распределение информации (например, отношения приоритета, информация о блокировке, временные метки или билеты). Когда распределенная система имеет относительно небольшой масштаб и задержки сообщений в системе невелики, методы централизованного управления параллелизмом можно использовать без изменений, в то время как определенные процессы или узлы в системе управляют соответствующими алгоритмами. Однако в крупномасштабной системе (например, грид- и облачной ) из-за распределения такой информации обычно возникает существенное снижение производительности, даже когда в первую очередь используются распределенные версии методов (по сравнению с централизованными). из-за задержки компьютера и связи . Кроме того, когда такая информация распространяется, соответствующие методы обычно плохо масштабируются. Хорошо известным примером проблем масштабируемости является распределенный менеджер блокировок , который распределяет информацию о блокировках (нематериализованных конфликтах) по распределенной системе для реализации методов блокировки.