Заказ обязательств - Commitment ordering

Заказ обязательств (CO) - это класс интероперабельных сериализуемость методы в контроль параллелизма из базы данных, обработка транзакции, и связанных приложений. Это позволяет оптимистичный (неблокирующие) реализации. С распространением многоядерные процессоры, CO также все чаще используется в параллельное программирование, транзакционная память, и особенно в программная транзакционная память (STM) для достижения сериализуемости оптимистично. CO также является названием итоговой транзакции график (историческая) собственность, которая была первоначально определена в 1988 году под названием динамическая атомарность.^[1] В расписании, совместимом с CO, хронологический порядок событий фиксации транзакций совместим с приоритет порядок соответствующих транзакций. CO - это широкий частный случай сериализуемость конфликта, а эффективные средства (надежный, высокопроизводительный, распределенный и масштабируемый ) достигать глобальная сериализуемость (модульная сериализуемость) в любом наборе систем баз данных, которые, возможно, используют различные механизмы управления параллелизмом (CO также делает каждую систему совместимой с сериализуемостью, если еще не была).

Каждая система базы данных, не соответствующая CO, дополняется компонентом CO (координатор поручения на принятие обязательств - COCO), который упорядочивает события фиксации для соответствия CO без какого-либо вмешательства в операции доступа к данным или других операций транзакции. Таким образом, CO обеспечивает низкие накладные расходы, общее решение для глобальной сериализуемости (и распределенной сериализуемости), что очень важно для глобальный контроль параллелизма (и распределенный контроль параллелизма ) систем с несколькими базами данных и других транзакционные объекты, возможно, сильно распределены (например, внутри облачные вычисления, сеточные вычисления, и сети смартфоны ). An протокол атомарной фиксации (ACP; любого типа) - это фундаментальная часть решения, используемая для разрыва глобальных циклов в графе конфликтов (приоритета, сериализуемости). CO - наиболее общее свойство (a необходимое условие ), который гарантирует глобальную сериализуемость, если задействованные системы баз данных не разделяют информацию управления параллелизмом, кроме сообщений протокола атомарной фиксации (немодифицированных), и не знают, являются ли транзакции глобальными или локальными (системы баз данных автономный). Таким образом, CO (с его вариантами) - единственный общий метод, который не требует обычно дорогостоящего распределения информации управления локальным параллелизмом (например, локальных отношений приоритета, блокировок, временных меток или билетов). Он обобщает популярные сильная строгая двухфазная синхронизация (SS2PL), которое в сочетании с протокол двухфазной фиксации (2PC) - это стандарт де-факто для достижения глобальной сериализуемости между системами баз данных (на основе SS2PL). В результате системы баз данных, совместимые с CO (с любыми разными типами управления параллелизмом), могут прозрачно присоединяться к таким решениям на основе SS2PL для глобальной сериализуемости.

Кроме того, на основе блокировки глобальные тупики решаются автоматически в среде с несколькими базами данных на основе CO, что является важным побочным преимуществом (включая особый случай среды, полностью основанной на SS2PL; ранее незамеченный факт для SS2PL).

Более того, строгий заказ (ШОС; Raz 1991c ), пересечение Строгость и CO, обеспечивает лучшую производительность (более короткое среднее время завершения транзакции и, как следствие, лучшая транзакция пропускная способность ), чем SS2PL, когда присутствуют конфликты чтения-записи (идентичное поведение блокировки для конфликтов записи-чтения и записи-записи; сопоставимые накладные расходы на блокировку). Преимущество SCO особенно важно во время конфликта блокировок. Строгость позволяет SS2PL и SCO использовать одинаковые эффективные восстановление базы данных механизмы.

Существуют два основных обобщающих варианта СО: расширенный CO (ОЭС; Раз 1993a ) и многоверсионный CO (MVCO; Раз 1993б ). Они также обеспечивают глобальную сериализуемость без локального распределения информации управления параллелизмом, могут быть объединены с любым соответствующим управлением параллелизмом и позволяют оптимистичные (неблокирующие) реализации. Оба используют дополнительную информацию для ослабления ограничений CO и достижения лучшего параллелизма и производительности. Порядок голосования (VO или обобщенный CO (GCO); Раз 2009 ) - набор расписания контейнера (свойство) и техника для CO и всех его вариантов. Локальный VO является необходимым условием для обеспечения глобальной сериализуемости, если участники протокола атомарной фиксации (ACP) не разделяют информацию управления параллелизмом (имеют общая автономия свойство). CO и его варианты прозрачно взаимодействуют друг с другом, гарантируя глобальную сериализацию и автоматическое разрешение глобальных тупиков в смешанной, гетерогенной среде с различными вариантами.

Обзор

В Заказ обязательств (CO; Раз 1990, 1992, 1994, 2009 ) свойство расписания также упоминается как Динамическая атомарность (с 1988 г.^[1]), совершить заказ, фиксировать сериализуемость заказа, и высокая восстанавливаемость (с 1991 г.). Последнее название вводит в заблуждение, поскольку CO несовместимо с восстанавливаемость, а термин «сильный» подразумевает частный случай. Это означает, что расписание с сильным свойством восстанавливаемости не обязательно имеет свойство CO, и наоборот.

В 2009 году CO был охарактеризован как основной метод управления параллелизмом вместе с ранее известными (с 1980-х годов) тремя основными методами: Блокировка, Заказ с отметкой времени, и Тестирование графа сериализации, а также как средство взаимодействия систем, использующих различные механизмы управления параллелизмом.^[2]

В система федеративных баз данных или любая другая более свободно определенная система с несколькими базами данных, которые обычно распределяются в сети связи, транзакции охватывают несколько и, возможно, Распределенные базы данных. Обеспечение соблюдения глобальная сериализуемость в такой системе проблематично. Даже если каждое локальное расписание отдельной базы данных является сериализуемым, тем не менее глобальное расписание всей системы не обязательно сериализуемо. Массовый обмен информацией о конфликтах между базами данных для достижения сериализации конфликтов приведет к неприемлемой производительности, в первую очередь из-за компьютера и связи. задержка. Проблема эффективного достижения глобальной сериализуемости была охарактеризована как открыто до публичного раскрытия СО в 1991 г. изобретатель Йоав Раз (Раз 1991a; смотрите также Глобальная сериализуемость ).

Применение CO - это эффективный способ обеспечить глобальную сериализацию конфликтов в распределенной системе, поскольку локальное применение CO в каждой базе данных (или другом транзакционном объекте) также обеспечивает его глобальное применение. Каждая база данных может использовать любой, возможно, другой тип механизма управления параллелизмом. С локальным механизмом, который уже обеспечивает сериализуемость конфликта, принудительное выполнение CO локально не вызывает каких-либо дополнительных прерываний, поскольку принудительное выполнение CO локально не влияет на стратегию планирования доступа к данным механизма (это планирование определяет прерывания, связанные с сериализуемостью; такой механизм обычно не работает). рассмотрите обязательные события или их порядок). Решение CO не требует накладных расходов на связь, поскольку оно использует (без изменений) атомарное обязательство только сообщения протокола, которые уже необходимы каждой распределенной транзакции для достижения атомарности. Протокол атомарной фиксации играет центральную роль в распределенном алгоритме CO, который реализует CO глобально, нарушая глобальные циклы (циклы, охватывающие две или более базы данных) в глобальном графе конфликтов. CO, его частные случаи и его обобщения являются интероперабельными, и достичь глобальной сериализуемости при прозрачном использовании вместе в единой гетерогенной распределенной среде, содержащей объекты с возможно разными механизмами управления параллелизмом. В качестве таких, Заказ обязательств, включая его частные случаи и вместе с его обобщениями (см. варианты CO ниже), обеспечивает общее, высокопроизводительное, полностью распределенное решение (не требуется центральный компонент обработки или центральная структура данных) для гарантии глобальной сериализуемости в гетерогенных средах систем с несколькими базами данных. и другие множественные транзакционные объекты (объекты, состояния которых доступны и изменяются только транзакциями; например, в рамках транзакционные процессы, а также в облачных вычислениях и грид-вычислениях). Решение CO масштабируется вместе с размером сети и количеством баз данных без какого-либо отрицательного воздействия на производительность (при условии, что статистика одной распределенной транзакции, например, среднее количество баз данных, задействованных в одной транзакции, не изменится).

С распространением Многоядерные процессоры Оптимистичный CO (OCO) также все чаще используется для достижения сериализуемости в программной транзакционной памяти, и уже были опубликованы многочисленные статьи и патенты STM, использующие «порядок фиксации» (например, Zhang et al. 2006^[3]).

Решение для заказа с обязательством для глобальной сериализации

Общая характеристика CO

Заказ обязательств (CO) - это частный случай сериализуемости конфликтов. CO может быть обеспечен неблокирующий механизмы (каждая транзакция может выполнить свою задачу без блокировки доступа к данным, что позволяет оптимистичный контроль параллелизма; однако обязательство может быть заблокировано). В CO запланируйте обязательные события '(частичный ) порядок приоритета транзакций соответствует порядку приоритета (частичному) соответствующих транзакций в (направленный ) граф конфликтов (граф приоритетов, граф сериализуемости), вызванный их конфликтующими операциями доступа (обычно операциями чтения и записи (вставки / изменения / удаления); CO также применяется к операциям более высокого уровня, где они конфликтуют, если некоммутативный, а также к конфликтам между операциями над многоверсионными данными).

Определение: заказ на обязательство

Позволять ${\displaystyle T_{1},T_{2}}$ быть двумя преданный идее транзакции в расписании, так что ${\displaystyle T_{2}}$ является в конфликте с ${\displaystyle T_{1}}$ (${\displaystyle T_{1}}$ предшествует ${\displaystyle T_{2}}$). В расписании есть Заказ обязательств (CO) собственность, если за каждые две такие сделки ${\displaystyle T_{1}}$ совершает до ${\displaystyle T_{2}}$ совершает.

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

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

Распределенный алгоритм СО

Полностью распределенный Заказ по всему миру Существует алгоритм обеспечения соблюдения, который использует локальный CO каждой участвующей базы данных и требует только (немодифицированных) сообщений протокола атомарной фиксации без дальнейшего обмена данными. Распределенный алгоритм представляет собой комбинацию локальных (для каждой базы данных) процессов алгоритма CO и протокола атомарной фиксации (который может быть полностью распределен). Протокол атомарной фиксации важен для обеспечения атомарности каждой распределенной транзакции (для принятия решения о фиксации или прерывании it; эта процедура всегда выполняется для распределенных транзакций, независимо от управления параллелизмом и CO). Типичным примером протокола атомарной фиксации является протокол двухфазной фиксации, который устойчив ко многим типам сбоев системы. В надежной среде или когда процессы обычно терпят неудачу вместе (например, в одном и том же Интегральная схема ), может использоваться более простой протокол для атомарной фиксации (например, простое рукопожатие участвующих процессов распределенной транзакции с некоторым произвольным, но известным специальным участником, координатором транзакции, т. е. типом однофазная фиксация протокол). Протокол атомарного обязательства достигает консенсуса среди участников относительно того, следует ли совершить или же прервать распределенная (глобальная) транзакция, охватывающая этих участников. Важным этапом в каждом таком протоколе является ДА голос (явное или неявное) каждым участником, что означает обязательство участника с правом голоса подчиняться решению протокола: зафиксировать или прервать выполнение. В противном случае участник может в одностороннем порядке прервать транзакцию, явно проголосовав НЕТ. Протокол совершает транзакцию только в том случае, если от все участников (таким образом, пропущенный голос обычно считается НЕТ), в противном случае протокол прерывает транзакцию. Различные протоколы атомарной фиксации различаются только своей способностью обрабатывать различные ситуации отказа вычислительной среды, а также объемами работы и другими вычислительными ресурсами, необходимыми в разных ситуациях.

Полное решение CO для глобальной сериализуемости основано на том факте, что в случае отсутствия голоса для распределенной транзакции протокол атомарной фиксации в конечном итоге прерывает эту транзакцию.

Обеспечение глобального CO

В каждой системе базы данных локальный алгоритм CO определяет необходимый порядок фиксации для этой базы данных. Согласно описанию CO, приведенному выше, этот порядок зависит от локального порядка приоритета транзакций, который является следствием механизмов планирования доступа к локальным данным. Соответственно, голосование ДА в протоколе атомарной фиксации запланировано для каждой (не отмененной) распределенной транзакции (в дальнейшем «голосование» означает голосование ДА). Если между двумя транзакциями существует отношение приоритета (конфликт), то голосование за вторую не будет проводиться до того, как первая будет завершена (зафиксирована или прервана), чтобы предотвратить возможное нарушение порядка фиксации протоколом атомарной фиксации. Такое может произойти, поскольку порядок фиксации в протоколе не обязательно совпадает с порядком голосования. Если отношения приоритета не существует, голосование может проводиться одновременно по обоим. Этот стратегия порядка голосования гарантирует, что протокол атомарной фиксации поддерживает порядок фиксации, и это необходимое условие для обеспечения глобального CO (и локального CO базы данных; без него могут быть нарушены как глобальный CO, так и локальный CO (свойство, означающее, что каждая база данных соответствует CO)).

Однако, поскольку системы баз данных планируют свои транзакции независимо, возможно, что порядки приоритета транзакций в двух или более базах данных несовместимы (не существует глобального частичного порядка, который может вставлять соответствующие местные частичные заказы вместе). Заказы с приоритетом CO также являются облиго-заказами. Когда участвующие базы данных в одной и той же распределенной транзакции не имеют совместимых локальных порядков приоритета для этой транзакции («не зная» этого; обычно между системами баз данных отсутствует координация при конфликтах, поскольку необходимая коммуникация является массовой и неприемлемо снижает производительность), это означает, что транзакция находится в глобальном цикле (включающем две или более баз данных) в глобальном графе конфликтов. В этом случае протокол атомарной фиксации не сможет собрать все голоса, необходимые для фиксации этой транзакции: стратегия порядка голосования выше, по крайней мере, одна база данных отложит голосование за эту транзакцию на неопределенный срок, чтобы соответствовать своему собственному порядку фиксации (приоритета), поскольку она будет ожидать завершения другой, предшествующей транзакции в этом глобальном цикле, отложенной на неопределенное время другой базой данных с другой порядок. Это означает голосованиетупик Ситуация с базами данных в этом цикле. В результате протокол в конечном итоге прервет некоторую тупиковую транзакцию в этом глобальном цикле, поскольку в каждой такой транзакции отсутствует хотя бы один голос участника. Выбор конкретной транзакции в цикле, которая должна быть прервана, зависит от политик прерывания протокола атомарной фиксации (a тайм-аут механизм является обычным, но он может привести к более чем одному необходимому прерыванию за цикл; как предотвращение ненужных прерываний, так и сокращение времени прерывания могут быть достигнуты с помощью специального механизма прерывания для CO). Такое прерывание нарушит глобальный цикл, связанный с этой распределенной транзакцией. За тупиковую транзакцию и, возможно, другие транзакции, конфликтующие с тупиковой (и, следовательно, заблокированной), можно будет проголосовать бесплатно. Стоит отметить, что каждая база данных, вовлеченная в тупиковую ситуацию с голосованием, продолжает регулярно голосовать за транзакции, которые не конфликтуют с ее заблокированной транзакцией, обычно это почти все незавершенные транзакции. Таким образом, в случае несовместимых локальных (частичных) поручений на фиксацию никаких действий не требуется, поскольку протокол атомарной фиксации разрешает их автоматически, прерывая транзакцию, которая является причиной несовместимости. Это означает, что указанное выше стратегия порядка голосования также достаточное условие для обеспечения Global CO.

Сделан следующий вывод:

• Стратегия упорядочивания голосования для Global CO Enforcing Теорема

Позволять ${\displaystyle T_{1},T_{2}}$ быть неопределенными (ни подтвержденными, ни прерванными) транзакциями в системе базы данных, которая обеспечивает выполнение CO для локальных транзакций, так что ${\displaystyle T_{2}}$ является Глобальный и в конфликте с ${\displaystyle T_{1}}$ (${\displaystyle T_{1}}$ предшествует ${\displaystyle T_{2}}$). Затем, имея ${\displaystyle T_{1}}$ закончился (зафиксирован или прерван) до ${\displaystyle T_{2}}$ проголосовало за совершение ( стратегия порядка голосования) в каждой такой системе баз данных в среде с несколькими базами данных является необходимое и достаточное условие для обеспечения Global CO (условие гарантирует Global CO, без которого оно может быть нарушено).

Комментарии:

1. В стратегия порядка голосования который обеспечивает глобальный CO, называется ${\displaystyle CD^{3}C}$ в (Раз 1992 ).
2. Свойство Local CO глобального расписания означает, что каждая база данных соответствует CO. Из части обсуждения необходимости выше непосредственно следует, что теорема верна также при замене «Global CO» на «Local CO», когда присутствуют глобальные транзакции. Вместе это означает, что Global CO гарантирована если и только если Гарантируется локальный CO (что неверно для сериализуемости глобального конфликта и сериализуемости локального конфликта: глобальный подразумевает локальный, но не наоборот).

Global CO подразумевает глобальную сериализуемость.

В Глобальный алгоритм CO включает обеспечение (локального) CO в каждой участвующей системе баз данных путем упорядочивания фиксации локальных транзакций (см. Обеспечение соблюдения СО на местном уровне ниже) и соблюдение стратегия порядка голосования в теореме выше (для глобальных транзакций).

Точная характеристика тупиков голосования по глобальным циклам

Вышеупомянутый процесс устранения глобального цикла посредством тупик при голосовании можно подробно объяснить следующим наблюдением:

Во-первых, для простоты предполагается, что каждая транзакция достигает состояния готовности к фиксации и оценивается по крайней мере одной базой данных (это означает, что блокировки блокировками не происходит). график "дождитесь голосования для подтверждения" как ориентированный граф с транзакциями в качестве узлов и направленное ребро от любой первой транзакции ко второй транзакции, если первая транзакция блокирует голосование для фиксации второй транзакции (в противоположность традиционному направлению ребра в график ожидания ). Такая блокировка происходит только в том случае, если вторая транзакция конфликтует с первой транзакцией (см. Выше). Таким образом, этот график «ожидания голосования для фиксации» идентичен графу глобального конфликта. Цикл на графике «ожидание голосования для фиксации» означает тупик в голосовании. Следовательно, есть тупик в голосовании тогда и только тогда, когда в графе конфликтов есть цикл. Локальные циклы (ограниченные одной базой данных) устраняются механизмами локальной сериализуемости. Следовательно, остаются только глобальные циклы, которые затем удаляются протоколом атомарной фиксации, когда он прерывает тупиковые транзакции с отсутствующими (заблокированными) соответствующими голосами.

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

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

• Определение: расширенный граф конфликтов

An расширенный граф конфликтов это граф конфликтов с добавленными ребрами: в дополнение к исходным ребрам существует направленное ребро из транзакции ${\displaystyle T_{1}}$ к сделке ${\displaystyle T_{2}}$ если соблюдены два условия:

1. ${\displaystyle T_{2}}$ заблокирован блокировкой доступа к данным, применяемой ${\displaystyle T_{1}}$ (блокировка предотвращает конфликт ${\displaystyle T_{2}}$ с ${\displaystyle T_{1}}$ от материализации и имеют преимущество в обычном графе конфликтов), и
2. Эта блокировка не прекратится раньше ${\displaystyle T_{1}}$ заканчивается (фиксируется или прерывается; верно для любого CO на основе блокировки)

График также можно определить как союз из (регулярных) граф конфликтов с (обратным краем, обычным) график ожидания

Комментарии:

1. Здесь, в отличие от обычного графа конфликтов, у которого есть ребра только для материализованных конфликтов, все конфликты, как материализованные, так и нематериализованные, представлены ребрами.
2. Обратите внимание, что все новые кромки - это все (обращенные к обычным) кромки график ожидания. В график ожидания можно определить также как граф нематериализованных конфликтов. По общепринятым соглашениям направление кромки в граф конфликтов определяет временной порядок между конфликтующими операциями, который противоположен временному порядку, определяемому ребром в график ожидания.
3. Обратите внимание, что такой глобальный граф содержит (встроил) все регулярные локальные (обратные ребра) ждать графы, а также могут включать глобальные циклы на основе блокировки (которые не могут существовать в локальных графах). Например, если все базы данных в глобальном цикле основаны на SS2PL, то все связанные ситуации блокировки голосования вызваны блокировками (это классическая и, вероятно, единственная глобальная тупиковая ситуация, рассматриваемая в литературе по исследованию баз данных). Это случай глобального тупика, когда каждая связанная база данных создает часть цикла, но полный цикл не находится ни в каком локальном графе ожидания.

В присутствии CO расширенный граф конфликтов на самом деле (перевернутый край) график ожидания локальной фиксации и голосования: Ребро существует от первой транзакции, локальной или глобальной, до второй, если вторая ожидает завершения первой, чтобы проголосовать за нее (если она глобальная) или локально зафиксирована (если локальная). Все глобальные циклы (в двух или более базах данных) на этом графике генерируют тупики голосования. Глобальные циклы графа обеспечивают полную характеристику тупиков при голосовании и могут включать любую комбинацию материализованных и нематериализованных конфликтов. Только циклы (только) материализованных конфликтов также являются циклами обычного графа конфликтов и влияют на сериализуемость. Один или несколько (связанных с блокировкой) нематериализованных конфликтов в цикле не позволяют ему быть циклом в обычном графе конфликтов и превращают его в тупик, связанный с блокировкой. Все глобальные циклы (тупики голосования) должны быть разорваны (разрешены) как для поддержания глобальной сериализуемости, так и для разрешения глобальных тупиковых ситуаций, связанных с блокировкой доступа к данным, и действительно все они нарушаются протоколом атомарной фиксации из-за отсутствия голосов при тупиковой ситуации с голосованием.

Комментарий: Это наблюдение также объясняет правильность Расширенный CO (ECO) ниже: Порядок голосования глобальных транзакций должен соответствовать порядку в графе конфликтов с блокировкой голосования, если между двумя глобальными транзакциями существует отношение порядка (путь в графе). За локальные транзакции голосование не проводится, и их (локальные) фиксации не блокируются в случае конфликтов. Это приводит к таким же тупиковым ситуациям голосования и, как результат, к процессу исключения глобального цикла для ОЭС.

В голосование-тупик Ситуацию можно резюмировать следующим образом:

• Теорема CO о голосовании и тупике

Пусть среда с несколькими базами данных включает CO-совместимую (что исключает местные циклы) системы баз данных, которые обеспечивают выполнение каждой, Глобальный CO (используя условие из теоремы выше). Затем голосование-тупик происходит тогда и только тогда, когда глобальный цикл (охватывает две или более базы данных) существует в Глобальный расширенный граф конфликтов (также блокировка блокировкой доступа к данным представлена ​​ребром). Если цикл не прерывается никаким прерыванием, то все глобальные транзакции на нем участвуют в соответствующем тупике голосования, и в конечном итоге голос каждого блокируется (прямо или косвенно блокировкой доступа к данным); если локальная транзакция находится в цикле, в конечном итоге ее (локальная) фиксация блокируется.

Комментарий: Может произойти редкая ситуация тупика голосования (из-за отсутствия заблокированных голосов), когда ни одна из систем баз данных, участвующих в этих транзакциях, не проголосует ни за какую транзакцию в соответствующем цикле. Это может произойти, когда локальные суб-транзакции многопоточный. Самая высокая вероятность такого редкого события включает две транзакции в двух одновременных противоположных циклах. Такие глобальные циклы (тупиковые ситуации) перекрываются с локальными циклами, которые разрешаются локально и, таким образом, обычно разрешаются локальными механизмами без привлечения атомарной фиксации. Формально это также глобальный цикл, но практически он является локальным (части локальных циклов генерируют глобальный; чтобы убедиться в этом, разделите каждую глобальную транзакцию (узел) на локальные суб-транзакции (каждая из частей ограничена одной базой данных); направленное ребро существует между транзакциями, если существует ребро между любыми соответствующими локальными суб-транзакциями; цикл является локальным, если все его ребра происходят из цикла между суб-транзакциями одной и той же базы данных, и глобальным, если нет; глобальный и локальный могут перекрываться: один и тот же цикл между транзакциями может быть результатом нескольких различных циклов между суб-транзакциями и быть как локальным, так и глобальным).

Также делается вывод о следующем частном случае, основанном на блокировках:

• Теорема глобального тупика, основанная на блокировке CO

В CO-совместимой системе с несколькими базами данных глобальный тупик на основе блокировки, включающий как минимум одну блокировку доступа к данным (нематериализованный конфликт) и две или более системы баз данных, является отражением глобального цикла в Глобальный расширенный граф конфликтов, что приводит к тупику голосования. Такой цикл не является циклом в (регулярном) Граф глобального конфликта (который отражает только материализованные конфликты, поэтому такой цикл не влияет на сериализуемость ).

Комментарии:

1. Любая блокировка (край) в цикле, не связанная с блокировкой доступа к данным, является прямой блокировкой голосования или локальной фиксации. Все тупики голосования разрешены (почти все по Атомарное обязательство; см. комментарий выше), включая этот тип на основе блокировки.
2. Глобальные взаимоблокировки на основе блокировок могут быть сгенерированы также в полностью распределенной среде на основе SS2PL (особый случай на основе CO), где все блокировки голосования (и тупики голосования) вызваны блокировками доступа к данным. Многие исследовательские статьи в течение многих лет посвящены разрешению таких глобальных тупиков, но ни одна из них (кроме статей CO) не известна (по состоянию на 2009 год), чтобы заметить это. атомарное обязательство автоматически разрешает их. Такие автоматические разрешения регулярно происходят незамеченными во всех существующих системах с несколькими базами данных на основе SS2PL, часто в обход специальных механизмов разрешения.

Голосование-тупик - это ключ к работе распределенной CO.

Устранение глобального цикла (здесь разрешение тупика голосования атомарное обязательство), и повторное выполнение результирующих прерванных транзакций занимает много времени, независимо от используемого контроля параллелизма. Если базы данных планируют транзакции независимо, глобальные циклы неизбежны (в полной аналогии с циклами / взаимоблокировками, генерируемыми в локальном SS2PL; при распределении любая координация планирования транзакций или операций приводит к нарушению автономности и, как правило, также к значительному снижению производительности). Однако во многих случаях их вероятность может быть очень низкой за счет внедрения рекомендаций по проектированию баз данных и транзакций, которые уменьшают количество конфликтов, связанных с глобальной транзакцией. Это, в первую очередь, за счет правильной обработки горячих точек (объекты базы данных с частым доступом) и предотвращения конфликтов за счет использования коммутативности, когда это возможно (например, при широком использовании счетчиков, как в финансах, и особенно при многотранзакционных операциях). счетчики накопления, которые обычно являются горячими точками).

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

Обеспечение соблюдения СО на местном уровне

Заказ обязательств может выполняться локально (в одной базе данных) с помощью специального алгоритма CO или любого алгоритма / протокола, который обеспечивает любой особый случай CO. Важным таким протоколом, широко используемым в системах баз данных, который генерирует расписание CO, является сильный строгий двухфазная синхронизация протокол (SS2PL: «снимать блокировки транзакции только после того, как транзакция была либо зафиксирована, либо прервана»; см. ниже). SS2PL - это правильное подмножество пересечения 2PL и строгость.

Общий локальный алгоритм CO

А общий локальный алгоритм CO (Раз 1992; Алгоритм 4.1) - это алгоритм, не зависящий от деталей реализации, который обеспечивает именно свойство CO. Он не блокирует доступ к данным (неблокирующий) и заключается в прерывании определенного набора транзакций (только при необходимости) после фиксации транзакции. Он прерывает (однозначно определенный в любой момент времени) минимальный набор других нерешенных (ни подтвержденных, ни прерванных) транзакций, которые выполняются локально и могут вызвать нарушение сериализуемости в будущем (может позже генерировать циклы зафиксированных транзакций в графе конфликтов; это набор ABORT зафиксированной транзакции T; после фиксации T никакая транзакция в ABORT во время фиксации не может быть зафиксирована, и все они обречены на прерывание). Этот набор состоит из всех нерешенных транзакций с направленными ребрами в графе конфликтов к зафиксированной транзакции. Размер этого набора не может увеличиваться, когда эта транзакция ожидает фиксации (в состоянии готовности: обработка завершена), и обычно уменьшается во времени по мере принятия решения по ее транзакциям. Таким образом, если в реальном времени существуют ограничения для завершения этой транзакции, желательно подождать с фиксацией этой транзакции и позволить этому набору уменьшиться в размере. Если локально существует другой механизм сериализуемости (который устраняет циклы в локальном графе конфликтов) или если цикл, включающий эту транзакцию, не существует, набор в конечном итоге будет пустым, и прерывание элемента набора не требуется. В противном случае набор будет стабилизироваться с транзакциями в локальных циклах, и для разрыва циклов потребуется прерывание элементов набора. Поскольку в случае конфликтов CO генерируется блокировка при фиксации, локальные циклы в увеличивает граф конфликтов (см. выше) указывают на локальные взаимоблокировки и методы разрешения взаимоблокировок, как в SS2PL можно использовать (например, как тайм-аут и график ожидания). Местный цикл в расширенный граф конфликтов с хотя бы одним нематериализованным конфликтом отражает тупик на основе блокировки. Приведенный выше локальный алгоритм, примененный к локальному расширенному графу конфликтов, а не к обычному локальному графу конфликтов, включает общий улучшенный локальный алгоритм CO, механизм исключения единого локального цикла, как для гарантии локальной сериализуемости, так и для обработки локальных взаимоблокировок на основе блокировки. На практике всегда используется дополнительный механизм управления параллелизмом, даже исключительно для обеспечения возможности восстановления. Общий алгоритм CO не влияет на стратегию планирования доступа к локальным данным, когда он работает вместе с любым другим механизмом управления локальным параллелизмом. Он влияет только на порядок фиксации, и по этой причине ему не нужно прерывать большее количество транзакций, чем необходимо для предотвращения нарушения сериализуемости любым комбинированным локальным механизмом управления параллелизмом. Чистым эффектом CO может быть, самое большее, задержка событий фиксации (или голосование в распределенной среде) для соблюдения необходимого порядка фиксации (но не больше задержки, чем его особые случаи, например, SS2PL, и на в среднем значительно меньше).

Делается следующая теорема:

• Теорема об общем локальном CO-алгоритме

При работе отдельно или вместе с любым механизмом управления параллелизмом в системе базы данных тогда

1. В Общий локальный алгоритм CO гарантирует (местный) CO (график, соответствующий CO).
2. В Общий улучшенный локальный алгоритм CO гарантирует разрешение взаимоблокировок на основе (локального) CO и (локального) блокировки.

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

Пример: параллельное программирование и транзакционная память

Смотрите также Параллельное программирование и транзакционная память

С распространением многоядерных процессоров варианты общего алгоритма локального CO также все чаще используются в параллельном программировании, Транзакционная память и особенно в программной транзакционной памяти для достижения оптимистической сериализуемости с помощью «порядка фиксации» (например, Ramadan et al. 2009,^[4] Zhang et al. 2006 г.,^[3] фон Парун и др. 2007 г.^[5]). Уже опубликованы многочисленные статьи и патенты, связанные с использованием CO.

Соображения по внедрению: Координатор поручений на обязательства (COCO)

Предполагается, что система баз данных находится в среде с несколькими базами данных. Из программная архитектура с точки зрения компонента CO, который реализует общий алгоритм CO локально, Координатор поручений (COCO), можно просто спроектировать как посредник между (единой) системой базы данных и компонентом протокола атомарной фиксации (Раз 1991б ). Однако COCO обычно является неотъемлемой частью системы базы данных. Функции COCO состоят в том, чтобы голосовать за фиксацию готовых глобальных транзакций (обработка завершена) в соответствии с локальным порядком фиксации, за прерывание транзакций, для которых система базы данных инициировала прерывание (система базы данных может инициировать прерывание для любой транзакции, по многим причинам) и передать решение об атомарной фиксации системе баз данных. Для локальных транзакций (если их можно идентифицировать) голосование не требуется. Для определения порядка фиксации COCO поддерживает обновленное представление локального графа конфликтов (или локального расширенного графа конфликтов для захвата также блокирующих взаимоблокировок) нерешенных (ни зафиксированных, ни прерванных) транзакций в виде структуры данных (например, с использованием механизмов, подобных запирание для захвата конфликтов, но без блокировки доступа к данным). Компонент COCO имеет интерфейс со своей системой базы данных для получения уведомлений «конфликт», «готов» (обработка завершена; готовность проголосовать за глобальную транзакцию или зафиксировать локальную) и «прервать» уведомления из системы базы данных. Он также взаимодействует с протоколом атомарной фиксации для голосования и получения решения протокола атомарной фиксации по каждой глобальной транзакции. Решения доставляются из COCO в систему баз данных через их интерфейс, а также уведомления о фиксации локальных транзакций в надлежащем порядке фиксации. COCO, включая его интерфейсы, может быть расширен, если он реализует другой вариант CO (см. Ниже) или играет роль в механизме управления параллелизмом базы данных, помимо голосования в атомарной фиксации.

COCO также гарантирует локальный CO в единой изолированной системе базы данных без интерфейса с протоколом атомарной фиксации.

CO - необходимое условие глобальной сериализуемости в автономных системах баз данных.

Если базы данных, которые участвуют в распределенных транзакциях (т. Е. Транзакциях, охватывающих более одной базы данных), не используют никакой совместно используемой информации управления параллелизмом и используют немодифицированные сообщения протокола атомарной фиксации (для достижения атомарности), тогда поддержание (локальное) заказ на обязательство или один из его обобщающих вариантов (см. ниже) - необходимое условие для обеспечения глобальной сериализуемости (метод доказательства можно найти в (Раз 1992 ), и другой метод доказательства этого в (Раз 1993a )); это также достаточное условие. Это математический факт, полученный из определений сериализуемость и сделка. Это означает, что при несоблюдении CO, глобальная сериализуемость не может быть гарантирована при этом условии (условие отсутствия обмена информацией управления локальным параллелизмом между базами данных, кроме сообщений протокола атомарной фиксации). Атомарное обязательство - это минимальное требование для распределенной транзакции, поскольку оно требуется всегда, что подразумевается определением транзакции.

(Раз 1992 ) определяет автономность базы данных и независимость в соответствии с этим требованием без использования дополнительных местных знаний:

• Определение: (на основе контроля параллелизма) автономная система баз данных

Система баз данных - это Автономный, если он не делится с какой-либо другой организацией какой-либо информацией управления параллелизмом, кроме немодифицированной протокол атомарной фиксации Сообщения. Кроме того, он не использует для управления параллелизмом какую-либо дополнительную локальную информацию, помимо конфликтов (последнее предложение не отображается явно, а скорее подразумевается дальнейшим обсуждением в Раз 1992 ).

Используя это определение, можно сделать следующие выводы:

• CO и теорема о глобальной сериализуемости

1. Соответствие CO каждого автономный система базы данных (или объект транзакции) в среде с несколькими базами данных является необходимое условие для обеспечения глобальной сериализуемости (без CO глобальная сериализуемость может быть нарушена).
2. Соответствие CO каждой системы баз данных - это достаточное условие для обеспечения глобальной сериализуемости.

Однако приведенное выше определение автономии подразумевает, например, что транзакции планируются таким образом, что локальные транзакции (ограниченные одной базой данных) не могут быть идентифицированы как таковые с помощью автономной системы баз данных. Это реалистично для некоторых транзакционных объектов, но слишком ограничительно и менее реалистично для систем баз данных общего назначения. Если автономия дополняется способностью идентифицировать локальные транзакции, то соответствие более общему свойству, Заказ с расширенным обязательством (ECO, см. Ниже), делает ECO необходимым условием.

Только в (Раз 2009 ) понятие Обобщенная автономия отражает предполагаемое понятие автономии:

• Определение: обобщенная автономия

Система баз данных имеет Обобщенная автономия свойство, если он не разделяет с какой-либо другой системой базы данных какую-либо информацию о локальном параллелизме, помимо (немодифицированных) сообщений протокола атомарной фиксации (однако может использоваться любая локальная информация).

Это определение, вероятно, является самым широким из возможных в контексте управления параллелизмом базы данных, и оно делает CO вместе с любым из его (полезно: Распределение информации управления параллелизмом) обобщающими вариантами (порядок голосования (VO); см. Варианты CO ниже) необходимое условие глобальной сериализуемости (т. е. объединение CO и его обобщающих вариантов является необходимым набором VO, который может включать также новые неизвестные полезные обобщающие варианты).

Резюме

В Заказ обязательств (CO) решение (метод) для глобальной сериализуемости можно резюмировать следующим образом:

Если каждый база данных (или любой другой транзакционный объект) в среде с несколькими базами данных соответствует CO, т. е. распределяет обязательства своих локальных транзакций и свои голоса по (глобальным, распределенным) транзакциям в атомарное обязательство протокол по локальному (к базе данных) частичный заказ индуцированный локальным графом конфликтов (графом сериализуемости) для соответствующих транзакций, то Глобальный CO и Глобальная сериализуемость гарантированы. Соответствие CO базы данных может быть эффективно достигнуто с любым локальным сериализуемость конфликта основанный на механизме управления параллелизмом, не влияющий ни на процесс выполнения транзакции, ни на планирование, ни на его прерывание. Также не нарушается автономность базы данных. Единственные незначительные накладные расходы - это обнаружение конфликтов (например, как при блокировке, но без блокировки доступа к данным; если они еще не обнаружены для других целей), а также упорядочивание голосов и фиксаций локальных транзакций в соответствии с конфликтами.

Расписание классов сдерживания: Стрелка от класса A к классу B указывает, что класс A строго содержит B; отсутствие направленного пути между классами означает, что классы несопоставимы. Недвижимость по сути блокирующий, если это может быть выполнено только путем блокировки операций доступа к данным транзакции до тех пор, пока определенные события не произойдут в других транзакциях. (Раз 1992 )

В случае несовместимых частичных порядков двух или более баз данных (глобальный частичный порядок не может вставлять соответствующие локальные частичные порядки вместе), создается глобальный цикл (охватывающий две базы данных или более) в глобальном графе конфликтов. Это вместе с CO приводит к циклу заблокированных голосов и голосованиетупик происходит для баз данных в этом цикле (однако разрешенное одновременное голосование в каждой базе данных, как правило, почти для всех невыполненных голосов, продолжает выполняться). В этом случае протокол атомарной фиксации не может собрать все голоса, необходимые для заблокированных транзакций в этом глобальном цикле, и, следовательно, протокол прерывает некоторую транзакцию с отсутствующим голосом. Это прерывает глобальный цикл, тупик голосования устраняется, и соответствующие заблокированные голоса могут быть выполнены. Разрыв глобального цикла в глобальном графе конфликтов гарантирует, что сохраняется как глобальная CO, так и глобальная сериализуемость. Таким образом, в случае несовместимых локальных (частичных) поручений на фиксацию никаких действий не требуется, поскольку протокол атомарной фиксации разрешает их автоматически, прерывая транзакцию, которая является причиной несовместимости. Кроме того, также возможны глобальные взаимоблокировки из-за блокировки (глобальные циклы в расширенный граф конфликтов с хотя бы одной блокировкой доступа к данным) приводят к тупикам при голосовании и разрешаются автоматически с помощью того же механизма.

Местный CO является необходимым условием гарантии Глобальная сериализуемость, если задействованные базы данных не разделяют никакой информации управления параллелизмом, кроме (немодифицированных) сообщений протокола атомарной фиксации, то есть если базы данных автономный в контексте управления параллелизмом. Это означает, что каждое решение глобальной сериализуемости для автономных баз данных должно соответствовать CO. В противном случае глобальная сериализуемость может быть нарушена (и, следовательно, очень быстро может быть нарушена в высокопроизводительной среде).

Раствор CO масштабируется с размером сети и количеством баз данных без потери производительности при использовании общая распределенная архитектура атомарных обязательств.

Распределенная сериализуемость и CO

Распределенный CO

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

Распространенный способ достижения распределенной сериализуемости в (распределенная) система принадлежит распределенный менеджер блокировок (DLM). DLM, которые передают информацию о блокировках (нематериализованном конфликте) в распределенной среде, обычно страдают от компьютера и связи задержка, что снижает производительность системы. CO позволяет достичь распределенной сериализуемости в очень общих условиях, без диспетчера распределенных блокировок, демонстрируя преимущества, уже исследованные выше для сред с несколькими базами данных; в частности: надежность, высокая производительность, масштабируемость, возможность использования оптимистичный контроль параллелизма при желании, отсутствие связи, связанной с информацией о конфликте, по сети (которая вызывает накладные расходы и задержки), а также автоматическое распределенное разрешение тупиков.

Все распределенные транзакционные системы полагаться на какой-то протокол атомарной фиксации для координации атомарности (будь то фиксация или прерывание) между процессами в распределенная транзакция. Кроме того, обычно восстанавливаемые данные (т.е. данные, находящиеся под контролем транзакций, например, данные базы данных; не путать с восстанавливаемость свойство расписания) напрямую доступны с помощью одного менеджер транзакционных данных компонент (также называемый менеджер ресурсов), который обрабатывает локальные суб-транзакции (часть распределенной транзакции в одном месте, например, в сетевом узле), даже если к этим данным косвенно обращаются другие объекты в распределенной системе во время транзакции (т.е. косвенный доступ требует прямого доступа через локальная суб-транзакция). Таким образом, восстанавливаемые данные в распределенной транзакционной системе обычно распределяются между менеджерами транзакционных данных. В такой системе эти менеджеры транзакционных данных обычно включают участников протокола атомарной фиксации системы. Если каждый участник соответствует CO (например, используя SS2PL, COCOs или их комбинацию; см. Выше), тогда вся распределенная система обеспечивает CO (согласно приведенным выше теоремам; каждый участник может считаться отдельным транзакционным объектом), и, таким образом, (распределенная) сериализуемость. Более того: когда CO используется вместе с протоколом атомарной фиксации, также распределенные тупики (т. е. взаимоблокировки, охватывающие два или более менеджеров данных), вызванные блокировкой доступа к данным, разрешаются автоматически. Таким образом, делается следующее следствие:

• Теорема распределенной сериализуемости на основе CO

Пусть распределенная транзакционная система (например, распределенная база данных система) содержат менеджеры транзакционных данных (также называемый менеджеры ресурсов), которые управляют всеми системными восстанавливаемые данные. Менеджеры данных соответствуют трем условиям:

1. Раздел данных: Восстанавливаемые данные разделены между менеджерами данных, то есть каждый восстанавливаемый элемент данных (элемент данных) управляется одним менеджером данных (например, как обычно в Общая архитектура; даже копии одного и того же элемента данных в разных менеджерах данных физически различны, воспроизведен).
2. Участники протокола атомарной фиксации: Эти менеджеры данных являются участниками системного протокола атомарных обязательств для координации атомарности распределенных транзакций.
3. Соответствие CO: Каждый такой диспетчер данных соответствует требованиям CO (или некоторым вариантам CO; см. Ниже).

потом

1. Вся распределенная система гарантирует (распределенный CO и) сериализуемость, и
2. На основе доступа к данным распределенные тупики (взаимоблокировки с участием двух или более менеджеров данных с хотя бы одним нематериализованным конфликтом) разрешаются автоматически.

Более того: менеджеры данных, соответствующие требованиям CO, являются необходимое условие для (распределенной) сериализуемости в системе, удовлетворяющей условиям 1, 2 выше, когда менеджеры данных автономный, то есть не делятся информацией управления параллелизмом, кроме неизмененных сообщений протокола атомарной фиксации.

Эта теорема также означает, что когда SS2PL (или любой другой вариант CO) используется локально в каждом диспетчере транзакционных данных, и каждый диспетчер данных имеет исключительный контроль над своими данными, диспетчер распределенных блокировок (который часто используется для обеспечения выполнения распределенного SS2PL) не требуется. для распределенного SS2PL и сериализуемости. Это применимо к широкому спектру распределенных транзакционных приложений, которые можно легко спроектировать в соответствии с условиями теоремы.

Распределенный оптимистичный CO (DOCO)

Для реализации распределенного оптимистического CO (DOCO) общий алгоритм локального CO используется во всех участниках протокола атомарной фиксации в системе без блокировки доступа к данным и, следовательно, без локальных взаимоблокировок. Из предыдущей теоремы вытекает следующее следствие.

• Распределенная оптимистическая теорема CO (DOCO)

Если используется DOCO, то:

1. Никаких локальных тупиковых ситуаций не происходит, и
2. Глобальные (голосующие) взаимоблокировки разрешаются автоматически (и все они связаны с сериализацией (с неблокирующими конфликтами), а не с блокировкой (с блокирующими и, возможно, также неблокирующими конфликтами)).

Таким образом, обработка тупиковых ситуаций не требуется.

Примеры

Распределенный SS2PL

Распределенная система баз данных, использующая SS2PL находится на двух удаленных узлах, A и B. Система базы данных имеет два менеджеры транзакционных данных (менеджеры ресурсов), по одному на каждом узле, и данные базы данных разделены между двумя менеджерами данных таким образом, что каждый имеет исключительный контроль над своей собственной (локальной для узла) частью данных: каждый обрабатывает свои собственные данные и блокируется без каких-либо знаний на другом менеджере. Для каждой распределенной транзакции такие менеджеры данных должны выполнять доступный протокол атомарной фиксации.

Две распределенные транзакции, ${\displaystyle T_{1}}$ и ${\displaystyle T_{2}}$, работают одновременно, и оба обращаются к данным x и y. x находится под исключительным контролем менеджера данных на A (менеджер B не может получить доступ к x), а y под этим контролем на B.

${\displaystyle T_{1}}$ читает x на A и записывает y на B, т. е. ${\displaystyle T_{1}=R_{\text{1A}}(x)}$ ${\displaystyle W_{\text{1B}}(y)}$ при использовании обозначений, общих для управления параллелизмом.

${\displaystyle T_{2}}$ читает y на B и записывает x на A, т.е. ${\displaystyle T_{2}=R_{\text{2B}}(y)}$ ${\displaystyle W_{\text{2A}}(x)}$

Соответствующие локальные суб-транзакции на A и B (части ${\displaystyle T_{1}}$ и ${\displaystyle T_{2}}$ на каждом из узлов) следующие:

Локальные суб-транзакции

Узел Сделка	А	B
${\displaystyle T_{1}}$	${\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}$	${\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}$
${\displaystyle T_{2}}$	${\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}$	${\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}$

Система баз данных график в определенный момент времени происходит следующее:

${\displaystyle R_{\text{1A}}(x)}$ ${\displaystyle R_{\text{2B}}(y)}$

(также ${\displaystyle R_{\text{2B}}(y)}$ ${\displaystyle R_{\text{1A}}(x)}$ возможно)

${\displaystyle T_{1}}$ держит блокировку чтения на x и ${\displaystyle T_{2}}$ держит блокировку чтения на y. Таким образом ${\displaystyle W_{\text{1B}}(y)}$ и ${\displaystyle W_{\text{2A}}(x)}$ заблокированы совместимость блокировки правила SS2PL и не могут быть выполнены. Это ситуация распределенного тупика, которая также является тупиком голосования (см. Ниже) с распределенным (глобальным) циклом длины 2 (количество ребер, конфликтов; 2 - наиболее частая длина). Локальные суб-транзакции находятся в следующих состояниях:

${\displaystyle T_{\text{1A}}}$ является готовы (казнь закончилась) и проголосовал (в атомарном обязательстве)

${\displaystyle T_{\text{1B}}}$ является Бег и заблокирован (нематериализованная конфликтная ситуация; голосование по ней невозможно)

${\displaystyle T_{\text{2B}}}$ является готовы и проголосовал

${\displaystyle T_{\text{2A}}}$ является Бег и заблокирован (нематериализованный конфликт; нет голосования).

Поскольку протокол атомарной фиксации не может получать голоса за заблокированные суб-транзакции (тупик с голосованием), он в конечном итоге прервет некоторую транзакцию с отсутствующим голосом (голосами) на тайм-аут, либо ${\displaystyle T_{1}}$, или же ${\displaystyle T_{2}}$, (или оба, если таймауты очень близки). Это разрешит глобальный тупик. Оставшаяся транзакция будет завершена, за нее проголосуют и она будет зафиксирована. Прерванная транзакция немедленно перезапущен и повторно казнен.

Комментарии

1. Раздел данных (x на A; y на B) важен, поскольку без него, например, к x можно будет получить доступ непосредственно из B. Если транзакция ${\displaystyle T_{3}}$ работает на B одновременно с ${\displaystyle T_{1}}$ и ${\displaystyle T_{2}}$ и напрямую записывает x, тогда без диспетчера распределенных блокировок блокировка чтения для x удерживается ${\displaystyle T_{1}}$ на A не отображается на B и не может блокировать запись ${\displaystyle T_{3}}$ (или сигнализировать о материализованном конфликте для неблокирующего варианта CO; см. ниже). Таким образом, сериализуемость может быть нарушена.
2. Из-за разделения данных к x нельзя получить доступ напрямую из B. Однако функциональность не ограничена, и транзакция, выполняющаяся на B, по-прежнему может выдавать запрос записи или чтения x (не часто). Этот запрос передается в локальную суб-транзакцию транзакции в A (которая создается, если она еще не существует), которая выдает этот запрос локальному диспетчеру данных в A.

Вариации

В приведенном выше сценарии оба конфликта нематериализованный, а глобальный тупик в голосовании отражается как цикл в глобальном график ожидания (но не в глобальном граф конфликтов; видеть Точная характеристика тупиков голосования по глобальным циклам над). Однако система базы данных может использовать любой вариант CO с точно такими же конфликтами и ситуацией тупика голосования и тем же разрешением. Конфликты могут быть либо материализованный или же нематериализованныйв зависимости от используемого варианта CO. Например, если ШОС (ниже) используется системой распределенной базы данных вместо SS2PL, тогда два конфликта в примере: материализованный, все локальные суб-транзакции находятся в готовы состояний, и блокировка голосования происходит в двух транзакциях, по одной на каждом узле, потому что правило голосования CO применяется независимо как к A, так и к B: из-за конфликтов ${\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}$ не голосовал раньше ${\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}$ заканчивается, и ${\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}$ не голосовал раньше ${\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}$ заканчивается, что является тупиком голосования. Теперь граф конфликтов имеет глобальный цикл (все конфликты материализуются), и снова он разрешается протоколом атомарной фиксации, и сохраняется распределенная сериализуемость. Маловероятно для системы распределенных баз данных, но возможно в принципе (и происходит в мультибазах), A может использовать SS2PL, а B использует SCO. В этом случае глобальный цикл не находится ни в графе ожидания, ни в графе сериализуемости, но все еще находится в расширенный граф конфликтов (союз двух). Различные комбинации приведены в следующей таблице:

Голосование-тупиковые ситуации

Дело	Узел А	Узел B	Возможный график	Материализованный конфликты на цикле	Не- материализованный конфликты	${\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}$	${\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}$	${\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}$	${\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}$
1	SS2PL	SS2PL	${\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)}$	0	2	Готовый Проголосовал	Бег (Заблокировано)	Бег (Заблокировано)	Готовый Проголосовал
2	SS2PL	ШОС	${\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)}$	1	1	Готовый Проголосовал	Готовый Голосование заблокировано	Бег (Заблокировано)	Готовый Проголосовал
3	ШОС	SS2PL	${\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{2A}}(x)}$	1	1	Готовый Проголосовал	Бег (Заблокировано)	Готовый Голосование заблокировано	Готовый Проголосовал
4	ШОС	ШОС	${\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)W_{\text{2A}}(x)}$	2	0	Готовый Проголосовал	Готовый Голосование заблокировано	Готовый Голосование заблокировано	Готовый Проголосовал

Комментарии:

1. Конфликты и, следовательно, циклы в расширенный граф конфликтов определяются только транзакциями и их первоначальным планированием, независимо от используемого управления параллелизмом. С любым вариантом СО, любым глобальный цикл (т.е. охватывает две базы данных или более) вызывает тупик при голосовании. Различные варианты CO могут отличаться в зависимости от того, является ли определенный конфликт материализованный или же нематериализованный.
2. Возможны некоторые ограниченные изменения порядка операций в приведенных выше расписаниях, ограниченные порядками внутри транзакций, но такие изменения не изменяют остальную часть таблицы.
3. Как отмечалось выше, только случай 4 описывает цикл в (обычном) графе конфликтов, который влияет на сериализуемость. Случаи 1-3 описывают циклы глобальных взаимоблокировок на основе блокировки (существует по крайней мере одна блокировка блокировки). Все типы циклов одинаково разрешаются протоколом атомарной фиксации. Случай 1 - это распространенный распределенный SS2PL, используемый с 1980-х годов. Однако известно, что ни в одной исследовательской статье, кроме статей CO, по состоянию на 2009 г. не было замечено этого автоматического разрешения глобальной блокировки.
4. Случай 4 выше также является примером типичного тупика голосования, когда Распределенный оптимистичный CO (DOCO) (то есть случай 4 не изменяется, когда Optimistic CO (OCO; см. ниже) заменяет SCO как на A, так и на B): блокировка доступа к данным не происходит, и существуют только материализованные конфликты.

Гипотетическая среда с несколькими однопоточными ядрами (MuSiC)

Комментарий: Хотя приведенные выше примеры описывают реальное рекомендуемое использование CO, этот пример является гипотетическим и предназначен только для демонстрации.

Некоторые экспериментальные резидентные базы данных с распределенной памятью поддерживают многопоточные транзакционные среды (MuSiC). «Однопоточный» относится к транзакции. потоки только и серийный оформление сделок. Целью является возможное увеличение производительности на несколько порядков (например, H-Store^[6] и VoltDB ) относительно обычного выполнения транзакции в нескольких потоках на одном ядре. В том, что описано ниже, MuSiC не зависит от способа распределения ядер. Они могут проживать в одном Интегральная схема (чип), или во многих микросхемах, возможно, географически распределенных на многих компьютерах. В такой среде, если восстанавливаемые (транзакционные) данные разделены между потоками (ядрами) и реализованы обычным способом для распределенного CO, как описано в предыдущих разделах, то DOCO и строгость существуют автоматически. Однако у этой простой реализации такой среды есть недостатки, и ее практичность в качестве универсального решения сомнительна. С другой стороны, огромный прирост производительности может быть достигнут в приложениях, которые в большинстве ситуаций могут обойти эти недостатки.

Комментарий: Простая реализация MuSiC, описанная здесь (которая использует, например, как обычно в распределенном CO, блокировку голосования (и потока транзакций) в протоколе атомарной фиксации, когда это необходимо), предназначена только для демонстрации и имеет нет соединения к реализации в H-Store или любом другом проекте.

В среде MuSiC локальные расписания серийный. Таким образом, как локальный Оптимистический СО (ОСО; см. Ниже), так и Глобальная стратегия распределения голосов при принудительном голосовании условия для протокола атомарной фиксации выполняются автоматически. Это приводит как к распределенному соответствию CO (и, следовательно, к распределенной сериализуемости), так и к автоматическому глобальному разрешению тупиков (голосование).

Кроме того, также местные Строгость автоматически следует в последовательном расписании. По теореме 5.2 в (Раз 1992; стр. 307), когда применяется стратегия упорядочивания голосов CO, также гарантируется Global Strictness. Обратите внимание, что серийный локально - это единственный режим, который позволяет сочетать строгость и «оптимизм» (без блокировки доступа к данным).

Сделан следующий вывод:

• Теорема MuSiC

В средах MuSiC, если восстанавливаемые (транзакционные) данные разделены между ядрами (потоками), то оба

1. ОСО (и подразумевается Сериализуемость; то есть DOCO и распределенная сериализуемость)
2. Строгость (позволяя эффективное восстановление; 1 и 2 подразумевают строгую СО - см. SCO ниже) и
3. (голосование) разрешение тупика

автоматически существуют глобально с неограниченной масштабируемостью по количеству используемых ядер.

Комментарий: Однако могут существовать два основных недостатка, требующие особого внимания:

1. Локальные суб-транзакции глобальной транзакции блокируются до фиксации, в результате чего соответствующие ядра простаивают. Это существенно снижает загрузку ядра, даже если планирование локальных суб-транзакций пытается выполнить их все с близостью по времени, почти вместе. Это можно преодолеть, отключив выполнение от фиксации (с некоторым протоколом атомарной фиксации) для глобальных транзакций за счет возможных каскадных прерываний.
2. увеличение количества ядер для заданного количества восстанавливаемых данных (размера базы данных) уменьшает средний объем (секционированных) данных на ядро. Это может сделать некоторые ядра простаивающими, а другие очень загруженными, в зависимости от распределения использования данных. Кроме того, локальная (для ядра) транзакция может стать глобальной (многоядерной) для достижения необходимых данных с дополнительными накладными расходами. Таким образом, по мере увеличения количества ядер объем и тип данных, назначаемых каждому ядру, должны быть сбалансированы в соответствии с их использованием, чтобы ядро ​​не было перегружено, чтобы стать узким местом, не становилось слишком часто простаивающим или недостаточно используемым в загруженной системе. Еще одно соображение - поместить в один и тот же основной раздел все данные, к которым обычно обращается одна и та же транзакция (если возможно), чтобы максимизировать количество локальных транзакций (и минимизировать количество глобальных распределенных транзакций). Это может быть достигнуто путем периодического перераспределения данных между ядрами на основе балансировки нагрузки (балансировка доступа к данным) и шаблонов использования данных транзакциями. Другой способ значительно смягчить этот недостаток - правильная физическая репликация данных между некоторыми основными разделами таким образом, чтобы глобальные транзакции только для чтения, возможно (в зависимости от шаблонов использования) полностью избегались, а изменения репликации синхронизировались с помощью специального механизма фиксации.

Варианты СО: частные случаи и обобщения

Особые классы свойств расписания (например, SS2PL и SCO ниже) строго содержатся в классе CO. Обобщающие классы (ECO и MVCO) строго содержат класс CO (т.е. включают также расписания, которые не соответствуют требованиям CO). Обобщающие варианты также гарантируют глобальную сериализуемость без распространения информации управления локальным параллелизмом (каждая база данных имеет общая автономия свойство: он использует только локальную информацию), ослабляя ограничения CO и используя дополнительную (локальную) информацию для лучшего параллелизма и производительности: ECO использует знания о локальных транзакциях (т. е. ограниченных одной базой данных), а MVCO использует доступность версий данных значения. Как и CO, оба обобщающих варианта неблокирующий, не мешают планированию операций какой-либо транзакции и могут быть легко объединены с любым соответствующим механизмом управления параллелизмом.

Период, термин Вариант CO в целом относится к CO, ECO, MVCO или комбинации каждого из них с любым соответствующим механизмом или свойством управления параллелизмом (включая ECO на основе нескольких версий, MVECO). Никакие другие обобщающие варианты (которые гарантируют глобальную сериализуемость без локального распределения информации управления параллелизмом) не известны, но могут быть обнаружены.

Сильная строгая двухфазная синхронизация (SS2PL)

Основная статья: Двухфазная блокировка

Сильная строгая двухфазная синхронизация (SS2PL; также упоминается как Строгость или же Строгое планирование) означает, что блокировки и чтения, и записи транзакции снимаются только после того, как транзакция завершилась (либо зафиксирована, либо прервана). Набор расписаний SS2PL представляет собой правильное подмножество набора расписаний CO. Это свойство широко используется в системах баз данных, и, поскольку оно подразумевает CO, базы данных, которые используют его и участвуют в глобальных транзакциях, вместе создают сериализуемое глобальное расписание (при использовании любого протокола атомарной фиксации, который необходим для атомарности в среде с несколькими базами данных). В этом случае для участия в распределенном решении CO не требуется никаких изменений или дополнений базы данных: набор нерешенных транзакций, которые должны быть прерваны перед фиксацией в локальный общий алгоритм CO выше пусто из-за блокировок, и, следовательно, такой алгоритм в данном случае не нужен. Система баз данных может проголосовать за транзакцию сразу после перехода в состояние «готово», то есть выполнения своей задачи локально. Его блокировки снимаются системой базы данных только после того, как это решено протоколом атомарной фиксации, и, следовательно, условие в Глобальная теорема обеспечения соблюдения СО выше сохраняется автоматически. Если система базы данных использует механизм локального тайм-аута для разрешения (локальных) взаимоблокировок SS2PL, то прерывание заблокированных транзакций нарушает не только потенциальные локальные циклы в глобальном графе конфликтов (реальные циклы в расширенном графе конфликтов), но также потенциальные глобальные циклы системы баз данных. циклов как побочный эффект, если атомарное обязательство механизм прерывания протокола относительно медленный. Такие независимые прерывания несколькими объектами обычно могут привести к ненужным прерываниям для более чем одной транзакции за глобальный цикл. Иная ситуация для местного график ожидания механизмы на основе: они не могут идентифицировать глобальные циклы, и протокол атомарной фиксации нарушит глобальный цикл, если возникший тупик голосования не будет разрешен ранее в другой базе данных.

Локальный SS2PL вместе с атомарным обязательством, подразумевающим глобальную сериализуемость, также можно вывести напрямую: все транзакции, включая распределенные, подчиняются 2PL (SS2PL) правила. Механизм протокола атомарной фиксации здесь нужен не для консенсуса по фиксации, а скорее для завершения точки синхронизации второй фазы. Вероятно, по этой причине, без учета механизма голосования атомарного обязательства, автоматическое разрешение глобального тупика не было замечено до CO.

Строгий СО (SCO)

Конфликт чтения-записи: SCO Vs. SS2PL. Продолжительность транзакции T2 больше с SS2PL, чем с SCO. SS2PL задерживает операцию записи w2 [x] для T2 до тех пор, пока T1 не зафиксируется, из-за блокировки x T1 после операции чтения r1 [x]. Если для достижения состояния готовности для транзакции T2 после начала операции записи w2 [x] требуется t единиц времени, то T2 фиксирует t единиц времени после того, как T1 зафиксирует. Однако SCO не блокирует w2 [x], и T2 может выполнить фиксацию сразу после фиксации T1. (Raz 1991c )

Заказ строгих обязательств (ШОС; (Raz 1991c )) - пересечение строгость (частный случай восстанавливаемости) и CO, и обеспечивает верхнюю границу параллелизма расписания, когда существуют оба свойства. Это может быть реализовано с использованием механизмов блокировки (блокировки), аналогичных тем, которые используются в популярном SS2PL, с аналогичными накладными расходами.

В отличие от SS2PL, SCO не блокирует конфликт чтения-записи, но, возможно, вместо этого блокирует фиксацию. SCO и SS2PL имеют идентичное поведение блокировки для двух других типов конфликтов: запись-чтение и запись-запись. В результате SCO имеет более короткие средние периоды блокировки и больший параллелизм (например, моделирование производительности одной базы данных для наиболее значимого варианта замки с упорядоченным разделением, который идентичен SCO, ясно показывают это с примерно 100% выигрышем для некоторых транзакционных нагрузок; также для идентичных транзакционных нагрузок SCO может достигать более высокой скорости транзакций, чем SS2PL раньше замок взбучка происходит). Больше параллелизма означает, что с заданными вычислительными ресурсами больше транзакций выполняется за единицу времени (более высокая скорость транзакций, пропускная способность ), а средняя продолжительность транзакции короче (более быстрое завершение; см. диаграмму). Преимущество SCO особенно важно во время конфликта блокировок.

• ШОС Vs. Теорема производительности SS2PL

SCO обеспечивает более короткое среднее время завершения транзакции, чем SS2PL, если существуют конфликты чтения-записи. В остальном SCO и SS2PL идентичны (имеют идентичное поведение блокировки при конфликтах записи-чтения и записи-записи).

SCO так же практичен, как SS2PL, поскольку, как SS2PL, он обеспечивает помимо сериализуемости еще и строгость, которая широко используется в качестве основы для эффективного восстановления баз данных после сбоя. Механизм SS2PL можно преобразовать в механизм SCO для повышения производительности простым способом без изменения методов восстановления. Описание реализации SCO можно найти в (Perrizo and Tatarinov 1998).^[7] Смотрите также Полуоптимистичный планировщик базы данных.

SS2PL является правильным подмножеством SCO (что является еще одним объяснением того, почему SCO менее ограничивает и обеспечивает больший параллелизм, чем SS2PL).

Оптимистичный CO (OCO)

Для реализации Оптимистичный заказ обязательств (OCO) общий алгоритм локального CO используется без блокировки доступа к данным и, следовательно, без локальных взаимоблокировок. OCO без ограничений планирования транзакций или операций охватывает весь класс CO и не является частным случаем класса CO, а скорее является полезным вариантом CO и характеристикой механизма.

Расширенный CO (ECO)

Общая характеристика ОЭС

Заказ с расширенными обязательствами (ЭКО; (Раз 1993a )) обобщает CO. Когда локальные транзакции (транзакции, ограниченные одной базой данных) можно отличить от глобальных (распределенных) транзакций (транзакций, охватывающих две базы данных или более), порядок фиксации применяется только к глобальным транзакциям. Таким образом, для локального (для базы данных) расписания, имеющего свойство ECO, хронологический (частичный) порядок событий фиксации только глобальных транзакций (неважно для локальных транзакций) согласуется с их порядком на соответствующем локальном графе конфликтов.

• Определение: заказ с расширенным обязательством

Позволять ${\displaystyle T_{1},T_{2}}$ быть двумя преданными Глобальный транзакции в расписании, так что направленный путь несостоявшихся транзакций существует в граф конфликтов (граф приоритета ) из ${\displaystyle T_{1}}$ к ${\displaystyle T_{2}}$ (${\displaystyle T_{1}}$ предшествует ${\displaystyle T_{2}}$, возможно переходно, косвенно). В расписании есть Заказ с расширенным обязательством (ЭКО) собственность, если за каждые две такие сделки ${\displaystyle T_{1}}$ совершает до ${\displaystyle T_{2}}$ совершает.

Распределенный алгоритм, гарантирующий глобальное ECO, существует. Что касается CO, то алгоритму нужны только (немодифицированные) сообщения протокола атомарной фиксации. Чтобы гарантировать глобальную сериализуемость, каждая база данных должна также гарантировать сериализуемость конфликтов собственных транзакций с помощью любого (локального) механизма управления параллелизмом.

• Теорема ECO и глобальной сериализуемости

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

См. Доказательство необходимости в (Раз 1993a ).

Это условие (ECO с локальной сериализуемостью) слабее, чем CO, и допускает больший параллелизм за счет немного более сложного локального алгоритма (однако практической разницы в накладных расходах с CO не существует).

Когда предполагается, что все транзакции являются глобальными (например, если нет информации о локальных транзакциях), ECO сокращается до CO.

Алгоритм ECO

Перед тем, как глобальная транзакция будет зафиксирована, общий локальный (для базы данных) алгоритм ECO прерывает минимальный набор нерешенных транзакций (ни зафиксированных, ни прерванных; либо локальные транзакции, либо глобальные, которые выполняются локально), что в дальнейшем может вызвать цикл в граф конфликтов. Этот набор прерванных транзакций (не уникальных, в отличие от CO) можно оптимизировать, если каждой транзакции назначен вес (который может определяться важностью транзакции и вычислительными ресурсами, уже вложенными в текущую транзакцию; оптимизация может быть выполнена , например, уменьшением Максимальный поток в сетях проблема (Раз 1993a )). Как и для CO, такой набор зависит от времени и со временем становится пустым. Практически почти во всех необходимых реализациях транзакция должна быть зафиксирована только тогда, когда набор пуст (и никакая оптимизация набора не применима). Локальный (в базе данных) механизм управления параллелизмом (отдельный от алгоритма ECO) гарантирует, что локальные циклы устранены (в отличие от CO, который сам по себе подразумевает сериализуемость; однако практически также для CO используется механизм локального параллелизма, по крайней мере, для обеспечить возможность восстановления). Локальные транзакции всегда могут быть зафиксированы одновременно (даже если существует отношение приоритета, в отличие от CO). Когда локальный частичный порядок общих транзакций (который определяется графом локальных конфликтов, теперь только с возможными временными локальными циклами, поскольку циклы устраняются с помощью механизма локальной сериализуемости) позволяет, также можно проголосовать за одновременное выполнение глобальных транзакций ( когда все их транзитивно (косвенно) предшествующие (через конфликт) Глобальный транзакции фиксируются, в то время как транзитивно предшествующие локальные транзакции могут находиться в любом состоянии. Это по аналогии с более сильным условием одновременного голосования распределенного CO алгоритма, когда все транзитивно предшествующие транзакции должны быть зафиксированы).

Условие гарантии Глобальный ОЭС можно резюмировать аналогично CO:

• Теорема о глобальной стратегии ОЭС в отношении порядка проведения голосования

Позволять ${\displaystyle T_{1},T_{2}}$ быть нерешительным (ни совершено, ни прервано) глобальные транзакции в системе базы данных, которая обеспечивает локальную сериализуемость, так что направленный путь несостоявшихся транзакций существует в граф локальных конфликтов (что самой базы данных) из ${\displaystyle T_{1}}$ к ${\displaystyle T_{2}}$. Затем, имея ${\displaystyle T_{1}}$ закончился (зафиксирован или прерван) до ${\displaystyle T_{2}}$ проголосовало за обязательство, в каждой такой системе баз данных в среде с несколькими базами данных необходимое и достаточное условие для обеспечения Global ECO (условие гарантирует Global ECO, без которого оно может быть нарушено).

Global ECO (все глобальные циклы в глобальном графе конфликтов удаляются атомарным обязательством) вместе с локальной сериализуемостью (т.е. каждая система базы данных поддерживает локальную сериализуемость; все локальные циклы удаляются) подразумевают глобальную сериализуемость (все циклы удаляются). Это означает, что если каждая система баз данных в среде с несколькими базами данных обеспечивает локальную сериализуемость ( любой механизм) и обеспечивает соблюдение стратегия порядка голосования в теореме выше (обобщение стратегии упорядочивания голосов CO), то Глобальная сериализуемость гарантируется (больше не требуется локальный CO).

Как и в случае CO, ОЭС голосование-тупик Ситуацию можно резюмировать следующим образом:

• Теорема ОЭС о тупике голосования

Пусть среда с несколькими базами данных включает системы баз данных, которые обеспечивают выполнение обеих Глобальный ОЭС (используя условие из теоремы выше) и сериализуемость локального конфликта (что устраняет локальные циклы в глобальном графе конфликтов). Затем голосование-тупик происходит тогда и только тогда, когда глобальный цикл (охватывает две или более базы данных) существует в Глобальный расширенный граф конфликтов (также блокировка блокировкой доступа к данным представлена ​​ребром). Если цикл не прерывается никаким прерыванием, то все глобальные транзакции на нем участвуют в соответствующем тупике голосования, и в конечном итоге голос каждого из них блокируется (прямо или косвенно блокировкой доступа к данным). Если локальная транзакция находится в цикле, она может находиться в любом не отмененном состоянии (запущено, готово или зафиксировано; в отличие от CO блокировка локальной фиксации не требуется).

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

Многоверсионный СО (MVCO)

Заказ мультиверсионных обязательств (MVCO; (Раз 1993б )) является обобщением CO для баз данных с многоверсионные ресурсы. С такими ресурсами транзакции только для чтения не блокировать и не блокироваться для повышения производительности. В настоящее время использование таких ресурсов является обычным способом увеличения параллелизма и производительности путем создания новой версии объекта базы данных при каждой записи объекта и разрешения операций чтения транзакций нескольких последних релевантных версий (каждого объекта). MVCO подразумевает Возможность сериализации с одной копией (1SER или 1SR), который является обобщением сериализуемость для многоверсионных ресурсов. Как и CO, MVCO не является блокирующим и может быть объединен с любым подходящим многоверсионным механизмом управления параллелизмом, не мешая ему. В представленной базовой теории для MVCO конфликты обобщены для разных версий одного и того же ресурса (в отличие от более ранних многоверсионных теорий). Для разных версий хронологический порядок конфликтов заменяется порядком версий и, возможно, обратным, с сохранением обычных определений для конфликтующих операций.Результаты для обычного и расширенного графов конфликтов остаются неизменными, и, как и в случае с CO, существует распределенный алгоритм принудительного применения MVCO, теперь для смешанной среды с ресурсами как с одной версией, так и с несколькими версиями (теперь одна версия является особым случаем многоверсии. ). Что касается CO, алгоритм MVCO требует только (без изменений) атомарное обязательство сообщения протокола без дополнительных служебных данных. Глобальные взаимоблокировки на основе блокировок переводятся в тупиковые ситуации при голосовании и разрешаются автоматически. По аналогии с CO справедливо следующее:

• MVCO и глобальная теорема о сериализуемости с одной копией

1. Соответствие MVCO каждого автономный система баз данных (или транзакционный объект) в смешанной среде с несколькими версиями баз данных с одной версией и несколькими версиями является необходимое условие для обеспечения глобальной сериализуемости в одну копию (1SER).
2. Соответствие MVCO каждой системы баз данных - это достаточное условие для обеспечения Global 1SER.
3. Глобальные взаимоблокировки на основе блокировки разрешаются автоматически.

Комментарий: Теперь система баз данных с одной версией, совместимая с CO, автоматически становится также совместимой с MVCO.

MVCO может быть дополнительно обобщен для использования обобщения ECO (MVECO).

Пример: изоляция моментальных снимков на основе CO (COSI)

Изоляция моментальных снимков на основе CO (COSI) - пересечение Изоляция снимков (SI) с MVCO. SI - это мультиверсионный контроль параллелизма Этот метод широко используется благодаря хорошей производительности и сходству с сериализуемостью (1SER) в нескольких аспектах. Теория (Raz 1993b) для MVCO, описанная выше, используется позже в (Fekete et al. 2005) и других статьях по SI, например, (Cahill et al. 2008);^[8] смотрите также Создание сериализуемой изоляции моментального снимка и ссылки там), для анализа конфликтов в SI, чтобы сделать его сериализуемым. Метод, представленный в (Cahill et al. 2008), Изоляция сериализуемых снимков (SerializableSI), модификация SI с низкими накладными расходами, обеспечивает хорошие результаты по производительности по сравнению с SI, с небольшим штрафом за обеспечение сериализуемости. Другой метод, объединяющий SI с MVCO (COSI), также делает SI сериализуемым с относительно низкими накладными расходами, аналогично объединению общего алгоритма CO с механизмами единой версии. Кроме того, результирующая комбинация COSI, совместимая с MVCO, позволяет системам баз данных, совместимым с COSI, взаимодействовать и прозрачно участвовать в решении CO для распределенной / глобальной сериализуемости (см. Ниже). Помимо накладных расходов необходимо также количественно сравнить поведение протоколов. С одной стороны, все сериализуемые расписания SI могут быть преобразованы в MVCO с помощью COSI (с помощью возможных задержек фиксации при необходимости) без прерывания транзакций. С другой стороны, SerializableSI, как известно, без необходимости прерывает и перезапускает определенные проценты транзакций также в сериализуемых расписаниях SI.

CO и его варианты прозрачно совместимы для глобальной сериализации

С CO и его вариантами (например, SS2PL, SCO, OCO, ECO и MVCO выше) глобальная сериализуемость достигается через атомарное обязательство распределенные алгоритмы на основе протоколов. Для CO и всех его вариантов протокол атомарной фиксации является инструментом для устранения глобальных циклов (циклов, охватывающих две или более баз данных) в глобальный расширенный (а значит, и обычный) граф конфликтов (неявно; реализация глобальной структуры данных не требуется). В случае несовместимых локальных поручений на обязательство в двух или более базах данных (когда нет глобальных частичный заказ может вставлять соответствующие локальные частичные порядки вместе), или тупик голосования, связанный с блокировкой доступа к данным, оба предполагающие глобальный цикл в глобальном расширенном графе конфликтов и пропущенные голоса, протокол атомарной фиксации прерывает такой цикл, прерывая нерешенную транзакцию на нем (см. Распределенный алгоритм СО над). Различия между различными вариантами существуют только на локальном уровне (в участвующих системах баз данных). Каждый локальный экземпляр CO любого варианта имеет одну и ту же роль для определения позиции каждой глобальной транзакции (транзакции, охватывающей две или более базы данных) в локальном поручении на обязательство, то есть для определения того, когда настала очередь транзакции голосовать. локально в протоколе атомарной фиксации. Таким образом, все варианты CO демонстрируют одинаковое поведение в отношении связывания атомов. Это означает, что все они могут взаимодействовать через атомарное обязательство (с использованием одних и тех же программных интерфейсов, обычно предоставляемых как Сервисы, некоторые уже стандартизированный для атомных обязательств, в первую очередь для двухфазная фиксация протокол, например, X / Открыть XA ) и прозрачно могут использоваться вместе в любой распределенной среде (в то время как каждый вариант CO может быть связан с любым соответствующим типом механизма управления локальным параллелизмом).

Таким образом, любая отдельная глобальная транзакция может участвовать одновременно в базах данных, которые могут использовать каждый, возможно, другой вариант CO (при одновременном выполнении процессов в каждой такой базе данных и одновременном выполнении локальных и других глобальных транзакций в каждой такой базе данных). Протокол атомарной фиксации безразличен к CO и не делает различий между различными вариантами CO. Любой глобальный цикл сгенерированный в расширенном глобальном графе конфликтов может охватывать базы данных различных вариантов CO и генерировать (если не прерывается каким-либо локальным прерыванием) тупик голосования, который разрешается атомарным обязательством точно так же, как в среде с одним вариантом CO. местные циклы (теперь, возможно, со смешанными материализованными и нематериализованными конфликтами, как сериализуемость, так и взаимоблокировки блокировки доступа к данным, например SCO) разрешаются локально (каждый с помощью собственных локальных механизмов соответствующего варианта экземпляра).

Порядок голосования (VO или обобщенный CO (GCO); Раз 2009 ), объединение CO и всех его вышеупомянутых вариантов, является полезной концепцией и методом глобальной сериализуемости. Чтобы соответствовать VO, локальная сериализуемость (в ее самой общей форме, основанная на коммутативности и включая многоверсионность) и стратегия порядка голосования (голосование в порядке местного приоритета).

Объединяя результаты для CO и его вариантов, можно сделать следующий вывод:

• Теорема совместимости вариантов CO

1. В среде с несколькими базами данных, где каждая система базы данных (объект транзакции) совместима с некоторым свойством варианта CO (совместимость с VO), любая глобальная транзакция может одновременно участвовать в базах данных, возможно, различных вариантов CO, и гарантируется глобальная сериализуемость (достаточное условие для глобальной сериализуемости; и глобальная сериализуемость с одной копией (1SER) для случая, когда существует многоверсионная база данных).
2. Если только локальная (для системы базы данных) информация управления параллелизмом используется каждой системой баз данных (каждая имеет общая автономия собственность, обобщение автономия), то соответствие каждого (любому) свойству варианта CO (соответствие VO) является необходимое условие для обеспечения глобальной сериализуемости (и Global 1SER; в противном случае они могут быть нарушены).
3. Кроме того, в такой среде глобальные взаимоблокировки, связанные с блокировкой доступа к данным, разрешаются автоматически (каждая такая взаимоблокировка генерируется глобальным циклом в расширенный граф конфликтов (т.е. тупик при голосовании; см. выше), включая как минимум одну блокировку доступа к данным (нематериализованный конфликт) и две системы баз данных; таким образом, это не цикл в обычном графе конфликтов и не влияет на сериализуемость).

Рекомендации

• Раз, Йоав (август 1992 г.), «Принцип упорядочивания обязательств или гарантии сериализуемости в гетерогенной среде нескольких автономных менеджеров ресурсов, использующих атомарные обязательства» (PDF), Материалы восемнадцатой Международной конференции по очень большим базам данных, Ванкувер, Канада, стр. 292–312. (также DEC-TR 841, Корпорация цифрового оборудования, Ноябрь 1990 г.)
• Раз, Йоав (сентябрь 1994 г.), "Сериализуемость посредством упорядочения обязательств", Письма об обработке информации, 51 (5): 257–264, Дои:10.1016/0020-0190(94)90005-1
• Раз, Йоав (июнь 2009 г.), Теория упорядочивания обязательств: резюме, получено 11 ноября, 2011
• Раз, Йоав (ноябрь 1990 г.), О значении упорядочивания обязательств (PDF), Digital Equipment Corporation
• Йоав Раз (1991a): патенты США 5 504 899 (ЭКО) 5 504 900 (CO) 5 701 480 (MVCO)
• Йоав Раз (1991b): «Координатор порядка выполнения обязательств (COCO) менеджера ресурсов, или архитектура для распределенного управления параллелизмом на основе упорядочения обязательств», DEC-TR 843, Digital Equipment Corporation, декабрь 1991 г.
• Йоав Раз (1991c): «Порядок строгих обязательств на основе блокировки, или Как улучшить параллелизм в диспетчерах ресурсов на основе блокировки», DEC-TR 844, декабрь 1991 г.
• Йоав Раз (1993a): «Заказ с расширенным обязательством или гарантия глобальной сериализуемости путем применения селективности порядка подтверждения к глобальным транзакциям». Труды двенадцатого симпозиума ACM по принципам систем баз данных (PODS), Вашингтон, округ Колумбия, стр. 83-96, май 1993 г. (также DEC-TR 842, ноябрь 1991 г.)
• Йоав Раз (1993b): «Распределенное управление параллелизмом на основе упорядочения обязательств для объединения ресурсов с одной и несколькими версиями». Труды третьего международного семинара IEEE по вопросам исследований в области инженерии данных: совместимость в системах с несколькими базами данных (RIDE-IMS), Вена, Австрия, стр. 189-198, апрель 1993 г. (также DEC-TR 853, июль 1992 г.)

Сноски

1. Алан Фекете, Нэнси Линч, Майкл Мерритт, Уильям Вейл (1988): Блокировка на основе коммутативности для вложенных транзакций (PDF) MIT, лаборатория LCS, Технический отчет MIT / LCS / TM-370, август 1988 г.
2. Филип А. Бернштейн, Эрик Новичок (2009): Принципы обработки транзакций, 2-е издание В архиве 2010-08-07 на Wayback Machine, Морган Кауфманн (Эльзевьер), июнь 2009 г., ISBN  978-1-55860-623-4 (страницы 145, 360)
3. Лингли Чжан, Винод К. Гровер, Майкл М. Магрудер, Дэвид Детлефс, Джон Джозеф Даффи, Гетц Грефе (2006): Порядок фиксации транзакции программного обеспечения и управление конфликтами Патент США 7711678, выдан 04.05.2010.
4. Хани Э. Рамадан, Индраджит Рой, Морис Херлихи, Эммет Витчел (2009): «Фиксация конфликтующих транзакций в STM» (PDF^{[постоянная мертвая ссылка ]}) Материалы 14-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования (PPoPP '09), ISBN  978-1-60558-397-6
5. Кристоф фон Праун, Луис Сезе, Калин Каскаваль (2007) «Неявный параллелизм с упорядоченными транзакциями» (PDF ), Материалы 12-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования (PPoPP '07), ACM New York © 2007, ISBN  978-1-59593-602-8 doi 10.1145 / 1229428.1229443
6. Роберт Каллман, Хидеаки Кимура, Джонатан Наткинс, Эндрю Павло, Алекс Расин, Стэнли Здоник, Эван Джонс, Ян Чжан, Сэмюэл Мэдден, Майкл Стоунбрейкер, Джон Хагг, Дэниел Абади (2008): «H-Store: высокопроизводительная распределенная система обработки транзакций в основной памяти», Материалы VLDB 2008 г., страницы 1496 - 1499, Окленд, Новая Зеландия, август 2008 г.
7. Перризо, Уильям; Татаринов, Игорь (11 ноября 1998 г.). Полуоптимистичный планировщик базы данных на основе порядка фиксации. 1998 Международная конференция по компьютерным приложениям в промышленности и технике. Лас Вегас. С. 75–79. CiteSeerX  10.1.1.53.7318.
8. Майкл Дж. Кэхилл, Уве Рем, Алан Д. Фекете (2008): «Сериализуемая изоляция для баз данных моментальных снимков», Материалы международной конференции ACM SIGMOD 2008 г. по управлению данными, стр. 729-738, Ванкувер, Канада, июнь 2008 г., ISBN  978-1-60558-102-6 (Премия SIGMOD 2008 за лучшую работу

внешняя ссылка

• Страница заказа обязательств Йоава Раза