Войти
В управлении параллелизмом баз данных, обработка транзакций (транзакция управления) и различные транзакционные приложения (например, транзакционная память и программная транзакционная память ), как централизованные, так и распределенные, транзакция расписание является сериализуемым, если его результат (например, результирующее состояние базы данных) равен результату его транзакций, выполняемых последовательно, то есть без перекрытия во времени. Транзакции обычно выполняются одновременно (они перекрываются), поскольку это наиболее эффективный способ. Сериализуемость - это главный критерий корректности одновременного выполнения транзакций. Он считается наивысшим уровнем изоляции между транзакциями и играет важную роль в управлении параллелизмом. Таким образом, он поддерживается во всех системах баз данных общего назначения. Сильная строгая двухфазная блокировка (SS2PL) - популярный механизм сериализуемости, используемый в большинстве систем баз данных (в различных вариантах) с момента их появления в 1970-х годах.
Теория сериализуемости предоставляет формальную основу для рассуждений и анализа сериализуемости и ее методов. Хотя это математический характер, его основы неформально (без математических обозначений) представлены ниже.
Сериализуемость используется для сохранения данных в элементе данных в согласованном состоянии. Сериализуемость - это свойство транзакции расписание (история). Он относится к свойству изоляции транзакции базы данных.
Расписания, которые не могут быть сериализованы, могут привести к ошибочным результатам. Хорошо известные примеры - транзакции, которые дебетуют и кредитуют счета деньгами: если связанные расписания не сериализуемы, то общая сумма денег может не сохраниться. Деньги могут исчезнуть или появиться из ниоткуда. Это, а также нарушения возможно необходимых других сохранений инварианта вызваны записью одной транзакции, а также "наступлением" и стиранием того, что было записано другой транзакцией, прежде чем оно станет постоянным в базе данных. Этого не происходит, если сохраняется сериализуемость.
Если какой-либо конкретный порядок между некоторыми транзакциями запрашивается приложением, то он применяется независимо от основных механизмов сериализуемости. Эти механизмы обычно безразличны к какому-либо конкретному заказу и генерируют непредсказуемый частичный заказ, который обычно совместим с множественными последовательными заказами этих транзакций. Этот частичный порядок является следствием порядка планирования операций доступа к данным параллельных транзакций, которые зависят от многих факторов.
Основной характеристикой транзакции базы данных является атомарность, что означает, что она либо фиксируется, то есть результаты всех ее операций вступают в силу в базе данных, либо прерывается (откат), результаты всех его операций не влияют на базу данных (семантика транзакции «все или ничего»). Во всех реальных системах транзакции могут прерваться по многим причинам, и сама по себе сериализуемость недостаточна для корректности. Расписания также должны обладать свойством восстанавливаемости (от прерывания). Восстанавливаемость означает, что зафиксированные транзакции не читали данные, записанные прерванными транзакциями (чьи эффекты не существуют в результирующих состояниях базы данных). Хотя сериализуемость в настоящее время специально скомпрометирована во многих приложениях для повышения производительности (только в тех случаях, когда корректность приложения не пострадает), нарушение восстанавливаемости быстро нарушит целостность базы данных, а также результаты транзакций, внешних по отношению к базе данных. Расписание со свойством восстанавливаемости (восстанавливаемое расписание) «восстанавливается» после прерывания само по себе, то есть прерывания не нарушают целостность зафиксированных транзакций и результирующей базы данных. Это неверно без возможности восстановления, когда вероятные нарушения целостности (приводящие к неверным данным базы данных) требуют специальных, обычно ручных корректирующих действий в базе данных.
Реализация возможности восстановления в ее общей форме может привести к каскадному прерыванию: прерывание одной транзакции может привести к необходимости прервать вторую транзакцию, затем третью и т. Д. Это приводит к потере уже частично выполненных транзакций и может также привести к снижению производительности. Предотвращение каскадных прерываний (ACA, или безкаскадность) - это особый случай возможности восстановления, который точно предотвращает такие явления. Часто на практике используется особый случай ACA: Строгость. Строгость позволяет эффективно восстанавливать базу данных после сбоя.
Обратите внимание, что свойство восстанавливаемости необходимо, даже если не происходит сбоя базы данных и не требуется восстановление базы данных после сбоя. Скорее, это необходимо для правильной автоматической обработки прерываний, которые могут быть не связаны с отказом базы данных и восстановлением после сбоя.
Во многих приложениях, в отличие от финансов, абсолютная корректность не требуется. Например, при получении списка продуктов в соответствии со спецификацией в большинстве случаев не имеет большого значения, если продукт, данные которого были обновлены недавно, не отображается в списке, даже если он соответствует спецификации. Обычно он появляется в таком списке при повторной попытке через некоторое время. Коммерческие базы данных обеспечивают управление параллелизмом с целым рядом уровней изоляции, которые на самом деле (контролируемые) нарушения сериализуемости для достижения более высокой производительности. Более высокая производительность означает лучшую скорость выполнения транзакций и меньшее среднее время отклика транзакции (продолжительность транзакции). Изоляция моментальных снимков - это пример популярного, широко используемого эффективного метода расслабленной сериализуемости со многими характеристиками полной сериализуемости, но все же недостаточным для некоторых и непригодным во многих ситуациях.
Другой распространенной в настоящее время причиной ослабления распределенной сериализуемости (см. Ниже) является требование доступности интернет-продуктов и услуг. На это требование обычно отвечает крупномасштабная репликация данных . Простое решение для синхронизации обновлений реплик одного и того же объекта базы данных - это включение всех этих обновлений в одну атомарную распределенную транзакцию. Однако со многими репликами такая транзакция очень велика и может охватывать достаточно нескольких компьютеров и сетей, так что некоторые из них, вероятно, будут недоступны. Таким образом, такая транзакция, скорее всего, завершится прерыванием и не достигнет своей цели. Следовательно, Оптимистическая репликация (Ленивая репликация) часто используется (например, во многих продуктах и услугах Google, Amazon, Yahoo, и т.п.), в то время как сериализуемость ослаблена и скомпрометирована для конечной согласованности. Опять же, в этом случае релаксация выполняется только для приложений, которые, как ожидается, не пострадают от этой техники.
Классы расписаний, определяемые свойствами ослабленной сериализуемости, либо содержат класс сериализуемости, либо несовместимы с ним.
Механизмы, обеспечивающие сериализуемость, должны выполняться в реальном времени или почти в реальном времени, пока транзакции выполняются с высокой скоростью. Чтобы удовлетворить это требование, используются особые случаи сериализуемости, достаточные условия сериализуемости, которые могут быть эффективно реализованы.
Существует два основных типа сериализуемости: сериализуемость представления и сериализуемость конфликта. Сериализуемость представления соответствует общему определению сериализуемости, данному выше. Сериализуемость конфликтов - это широкий частный случай, то есть любое расписание, которое сериализуемо конфликтами, также может сериализоваться по просмотру, но не обязательно наоборот. Конфликт-сериализуемость широко используется, потому что ее легче определить и она охватывает значительную часть сериализуемых представлений расписаний. Определение возможности сериализации представлений расписания - это проблема NP-complete (класс проблем, у которых есть только трудные для вычисления и требующие чрезмерно много времени известные решения).
Операции с данными читаются или записываются (запись: либо вставка, либо изменение, либо удаление). Две операции конфликтуют, если они относятся к разным транзакциям с одним и тем же элементом данных (элементом данных), и хотя бы одна из них является записью. Каждая такая пара конфликтующих операций имеет тип конфликта: это конфликт чтения-записи, или записи-чтения, или конфликт записи-записи. Говорят, что транзакция второй операции в паре противоречит транзакции первой операции. Более общее определение конфликтующих операций (также для сложных операций, каждая из которых может состоять из нескольких «простых» операций чтения / записи) требует, чтобы они были некоммутативными (изменение их порядка также изменяет их объединенный результат). Каждая такая операция должна быть атомарной сама по себе (с использованием надлежащей системной поддержки), чтобы считаться операцией для проверки коммутативности. Например, операции чтения-чтения являются коммутативными (в отличие от чтения-записи и других возможностей), и поэтому чтение-чтение не является конфликтом. Другой более сложный пример: операции увеличения и уменьшения счетчика являются операциями записи (обе изменяют счетчик), но не должны считаться конфликтующими (тип конфликта записи-записи), поскольку они коммутативны (таким образом, увеличение-уменьшение не является конфликт, например, уже поддерживался в старом IBM IMS "fast path" ). Только приоритет (временной порядок) в парах конфликтующих (некоммутативных) операций важен при проверке эквивалентности последовательному расписанию, поскольку разные расписания, состоящие из одних и тех же транзакций, могут быть преобразованы из одного в другой, изменяя порядок между операциями разных транзакций ( чередование различных транзакций), и поскольку изменение порядка коммутативных операций (неконфликтных) не меняет общий результат последовательности операций, то есть результат расписания (результат сохраняется за счет изменения порядка между неконфликтными операциями, но обычно не когда порядок изменения конфликтующих операций). Это означает, что если расписание может быть преобразовано в любое последовательное расписание без изменения порядков конфликтующих операций (но с изменением порядков неконфликтных операций с сохранением порядка операций внутри каждой транзакции), то результат обоих расписаний будет одинаковым, и расписание по определению сериализуемо конфликтно.
Конфликты являются причиной блокировки транзакций и задержек (нематериализованные конфликты) или отмены транзакций из-за предотвращения нарушения сериализуемости. Обе возможности снижают производительность. Таким образом, уменьшение количества конфликтов, например, за счет коммутативности (когда это возможно), является способом повышения производительности.
Транзакция может выполнить / запросить конфликтующую операцию и вступить в конфликт с другой транзакцией, пока ее конфликтующая операция задерживается и не выполняется (например, блокируется блокировкой ). Только выполненные (материализованные) конфликтующие операции имеют отношение к сериализуемости конфликтов (подробнее см. Ниже).
Соответствие расписанию сериализуемости конфликтов можно проверить с помощью графа приоритета (граф сериализуемости, граф сериализации, конфликт график) для совершенных транзакций расписания. Это ориентированный граф, представляющий приоритет транзакций в расписании, что отражено в приоритете конфликтующих операций в транзакциях.
Следующее наблюдение является ключевой характеристикой сериализуемости конфликтов :
Циклы зафиксированных транзакций можно предотвратить, прервав нерешенную (ни подтвержденную, ни прерванную)) транзакция в каждом цикле в графе приоритета всех транзакций, который в противном случае может превратиться в цикл зафиксированных транзакций (и зафиксированная транзакция не может быть прервана). Одна транзакция, прерванная за цикл, и требуется, и ее количество достаточно, чтобы прервать и исключить цикл (возможны и другие прерывания, которые могут произойти при некоторых механизмах, но не являются необходимыми для сериализуемости). Вероятность генерации цикла обычно невелика, но, тем не менее, такая ситуация тщательно обрабатывается, как правило, со значительными накладными расходами, поскольку требуется корректность. Транзакции, прерванные из-за предотвращения нарушения сериализуемости, перезапускаются и немедленно выполняются снова.
Механизмы обеспечения сериализуемости обычно не поддерживают граф приоритета как структуру данных, а скорее неявно предотвращают или прерывают циклы (например, SS2PL ниже).
Сильная строгая двухфазная блокировка (SS2PL) - распространенный механизм, используемый в системах баз данных с момента их появления в 1970-х годах («SS» в названии SS2PL означает новее), чтобы обеспечить как сериализуемость конфликтов, так и строгость (особый случай восстанавливаемости, который позволяет эффективно восстанавливать базу данных после сбоя) расписания. В соответствии с этим механизмом каждая база данных блокируется транзакцией до того, как она получит к ней доступ (в любой операции чтения или записи): элемент помечен и связан с lock определенного типа в зависимости от выполняемой операции. (и конкретная реализация транзакции; существуют различные модели с разными типами блокировки; в некоторых моделях блокировки могут изменять тип в течение жизни транзакции). В результате доступ другой транзакции может быть заблокирован, как правило, в случае конфликта (блокировка задерживает или полностью предотвращает материализацию конфликта и отражается в графе приоритета путем блокировки конфликтующей операции), в зависимости от типа блокировки и другой транзакции. тип операции доступа. Использование механизма SS2PL означает, что все блокировки данных от имени транзакции снимаются только после того, как транзакция завершилась (зафиксирована или прервана).
SS2PL - это также имя результирующего свойства расписания, которое также называется строгостью. SS2PL - это особый случай (собственное подмножество ) Двухфазная блокировка (2PL)
Взаимная блокировка между транзакциями приводит к тупиковой ситуации, когда выполнение этих транзакций застопорился и не может быть достигнуто. Таким образом, необходимо разрешить тупиковые ситуации, чтобы завершить выполнение этих транзакций и освободить связанные вычислительные ресурсы. Тупиковая ситуация - это отражение потенциального цикла в графе приоритета, который произошел бы без блокировки при материализации конфликтов. Тупиковая ситуация разрешается путем прерывания транзакции, связанной с таким потенциальным циклом, и разрыва цикла. Это часто обнаруживается с помощью графа ожидания (графа конфликтов, заблокированных блокировками от материализации; его также можно определить как граф нематериализованных конфликтов; не материализованные конфликты не отражаются в граф приоритета и не влияет на сериализуемость), который указывает, какая транзакция «ожидает» освобождения одной или нескольких блокировок, посредством которых другая транзакция или транзакции, а цикл в этом графе означает тупик. Прервать одну транзакцию за цикл достаточно, чтобы разорвать цикл. Транзакции, прерванные из-за разрешения тупиковых ситуаций, перезапускаются и немедленно выполняются снова.
Другие известные механизмы включают:
Вышеупомянутые (конфликтующие) методы сериализуемости в их общей форме не обеспечивают возможности восстановления. Для повышения восстанавливаемости необходимы специальные улучшения.
Методы управления параллелизмом бывают трех основных типов:
Основными различиями между типами техники являются: типы конфликтов, которые они порождают. Пессимистический метод блокирует операцию транзакции при конфликте и генерирует нематериализованный конфликт, тогда как оптимистический метод не блокирует и порождает материализованный конфликт. Полуоптимистический метод порождает оба типа конфликтов. Оба типа конфликтов генерируются хронологическим порядком, в котором вызываются операции транзакции, независимо от типа конфликта. Цикл зафиксированных транзакций (с материализованными конфликтами) в графе приоритета (графе конфликтов) представляет собой нарушение сериализуемости, и его следует избегать для поддержания сериализуемости. Цикл (нематериализованных) конфликтов в графе ожидания представляет собой тупиковую ситуацию, которая должна быть разрешена путем разрыва цикла. Оба типа цикла являются результатом конфликтов и должны быть прерваны. При любом типе техники конфликты следует обнаруживать и учитывать с аналогичными накладными расходами как для материализованных, так и для нематериализованных конфликтов (обычно с использованием таких механизмов, как блокировка, при этом либо блокировка для блокировок, либо не блокировка, а запись конфликта для материализованных конфликтов). В методе блокировки обычно переключение контекста происходит при конфликте с (дополнительными) накладными расходами. В противном случае вычислительные ресурсы, связанные с заблокированными транзакциями, останутся простаивающими, неиспользованными, что может быть худшей альтернативой. Когда конфликты не возникают часто, оптимистические методы обычно имеют преимущество. При разных нагрузках транзакций (смешение типов транзакций) один тип техники (т. Е. Оптимистичный или пессимистический) может обеспечить лучшую производительность, чем другой.
Если классы расписания не являются по своей сути блокирующими (т. Е. Они не могут быть реализованы без блокировки операций доступа к данным; например, 2PL, SS2PL и SCO выше; см. Диаграмму), они также могут быть реализованы с использованием оптимистических методов (например, Сериализуемость, восстанавливаемость).
Мульти -версия управления параллелизмом (MVCC) - это распространенный сегодня способ повышения параллелизма и производительности путем создания новой версии объекта базы данных каждый раз, когда объект записывается, и разрешения операций чтения транзакций нескольких последних релевантных версий (каждого объекта), в зависимости от метода планирования. MVCC можно комбинировать со всеми перечисленными выше методами сериализации (за исключением SerializableSI, который изначально основан на MVCC). Он используется в большинстве СУБД общего назначения.
MVCC особенно популярен в настоящее время благодаря методу ослабленной сериализуемости (см. Выше) Изоляция моментальных снимков (SI), который обеспечивает лучшую производительность, чем большинство известных механизмов сериализуемости (за счет возможного нарушения сериализуемости в определенных случаи). SerializableSI, который является эффективным усовершенствованием SI, чтобы сделать его сериализуемым, предназначен для обеспечения эффективного сериализуемого решения. SerializableSI был проанализирован с помощью общей теории MVCC
Распределенная сериализуемость - сериализуемость расписания транзакции распределенная система (например, система распределенная база данных ). Такая система характеризуется распределенными транзакциями (также называемыми глобальными транзакциями), то есть транзакциями, которые охватывают компьютерные процессы (абстракция процесса в общем смысле, в зависимости от вычислительной среды; например, операционная система поток ) и, возможно, сетевые узлы. Распределенная транзакция включает в себя более одной из нескольких локальных суб-транзакций, каждая из которых имеет состояния, как описано выше для транзакции базы данных. Локальная суб-транзакция состоит из одного процесса или нескольких процессов, которые обычно не работают вместе (например, в одном ядре процессора ). Распределенные транзакции подразумевают необходимость в протоколе атомарной фиксации для достижения консенсуса среди своих локальных суб-транзакций относительно того, следует ли зафиксировать или прервать. Такие протоколы могут варьироваться от простого (однофазного) подтверждения связи между процессами, которые не работают вместе, до более сложных протоколов, таких как двухфазная фиксация, для обработки более сложных случаев сбоя (например, процесс, узел, связь и т.д. отказ). Распределенная сериализуемость - основная цель управления распределенным параллелизмом для обеспечения корректности. С распространением Интернета, облачных вычислений, грид-вычислений и небольших портативных мощных вычислительных устройств (например, смартфонов,) потребность в эффективных методах распределенной сериализуемости для обеспечения корректности в распределенных приложениях и между ними, похоже, возрастает.
Распределенная сериализуемость достигается за счет реализации распределенных версий известных централизованных методов. Как правило, все такие распределенные версии требуют использования информации о конфликте (материализованных или нематериализованных конфликтов или, что то же самое, о приоритете транзакции или информации о блокировании; обычно используется сериализуемость конфликтов), которая генерируется не локально, а скорее в разных процессах, и удаленная локации. Таким образом, необходимо распространение информации (например, отношения приоритета, информация о блокировках, временные метки или билеты). Когда распределенная система имеет относительно небольшой масштаб и задержки сообщений в системе невелики, методы централизованного управления параллелизмом можно использовать без изменений, в то время как определенные процессы или узлы в системе управляют соответствующими алгоритмами. Однако в крупномасштабной системе (например, сетке и облаке) из-за распределения такой информации обычно возникает значительное снижение производительности, даже когда используются распределенные версии методов (по сравнению с централизованными), в первую очередь из-за компьютера и связи задержки. Кроме того, когда такая информация распространяется, связанные методы обычно плохо масштабируются. Хорошо известным примером проблем масштабируемости является распределенный менеджер блокировок , который распределяет информацию о блокировках (нематериализованных конфликтах) по распределенной системе для реализации методов блокировок.
