Упорядочение обязательств

редактировать

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

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

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

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

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

Содержание

1 Обзор
2 Решение для глобальной сериализации
- 2.1 Общая характеристика CO
- 2.2 Распределенный алгоритм CO
  - 2.2.1 Обеспечение глобального CO
  - 2.2. 2 Точная характеристика тупиковых операций с голосованием в глобальном циклам
- 2.3 Обеспечение локального CO
  - 2.3.1 Общий локальный алгоритм CO
  - 2.3.2 Пример: параллельное программирование и транзакционная память
  - 2.3.3 Соображения по реализации: Координатор заказа на обязательство (COCO)
- 2.4 CO является условием глобальной сериализуемости в автономных системах баз данных
- 2.5 Резюме
3 Распределенная сериализуемость и CO
- 3.1 Распределенный сериализуемый CO
- 3.2 Распределенный оптимистичный CO ( DOCO)
- 3.3 Примеры
  - 3.3.1 Распределенный SS2PL
    - 3.3.1.1 Комментарии
  - 3.3.2 Варианты
  - 3.3.3 Гипотетическая среда с использованием однопоточными ядрами (MuSiC)
4 CO : частные случаи и обобщения
- 4.1 Сильная строгая двухфазная синхронизация (SS2PL)
- 4.2 Строгая CO (SCO)
- 4.3 Оптимистическая CO (OCO)
- 4.4 Расширенный CO (ECO)
  - 4.4.1 Общие характеристики ECO
  - 4.4.2 Алгоритм ECO
- 4.5 Многоверсионный CO (MVC O)
  - 4.5.1 Пример: изоляция моментальных снимков на основе CO (COSI)
- 4.6 CO и его варианты прозрачно совместимости для глобальной сериализуемости
5 Ссылки
6 Сноски
7 Внешние ссылки

Обзор

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

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

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

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

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

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

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

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

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

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

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

Распределенный алгоритм глобального подтверждения.

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

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

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

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

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

Делается следующий вывод:

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

Пусть

T 1, T 2 {\ displaystyle T_ {1}, T_ {2}}

T _ {{1}}, T _ {2}}

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

T 2 {\ displaystyle T_ {2}}

T_{{2}}

является глобальным и конфликтует с

T 1 {\ displaystyle T_ {1}}

T _ {{1}}

(

T 1 {\ displaystyle T_ {1}}

T _ {{1}}

предшествует

T 2 {\ displaystyle T_ {2}}

T_{{2}}

). Затем, если

T 1 {\ displaystyle T_ {1}}

T _ {{1}}

закончился (зафиксирован или прерван) до

T 2 {\ displaystyle T_ {2}}

T_{{2}}

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

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

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

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

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

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

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

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

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

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

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

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

T 1 { \ displaystyle T_ {1}}

T _ {{1}}

к транзакции

T 2 {\ displaystyle T_ {2}}

T_{{2}}

, если выполняются два условия:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выводится следующая теорема:

Общая теорема об алгоритме локального CO

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

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

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

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

См. также

С распространением многоядерных процессоров, варианты общего локального алгоритма CO также все чаще используются в параллельном программировании, транзакционной памяти и особенно в программной транзакционной памяти для достижения сериализации. оптимистично с помощью «порядка фиксации» (например, Рамадан и др. 2009 г., Чжан и др. 2006, фон Парун и др. 2007). Уже опубликованы многочисленные статьи и патенты, связанные с использованием CO.

Рекомендации по реализации: Координатор поручения обязательств (COCO)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Резюме

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

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

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

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

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

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

Распределенную сериализу и CO

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

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

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

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

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

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

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

Тогда

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

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

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

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

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

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

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

Локальные взаимоблокировки не возникают, и
Глобальные (голосование) взаимоблокировки разрешаются автоматически (и все они связаны с сериализуемостью (с неблокирующими конфликтами), а не с блокировкой (с блокирующими и, возможно, неблокирующими конфликтами)).

Таким образом, обработка взаимоблокировок не требуется.

Примеры

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

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

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

T 1 {\ displaystyle T_ {1}}

T _ {{1}}

читает x на A и записывает y в B, то есть

T 1 = R 1A (x) {\ displaystyle T_ {1} = R _ {\ text {1A}} (x)}

{\ displaystyle T_ {1 } = R _ {\ текст {1A}} (x)}

W 1B (y) {\ displaystyle W _ {\ text {1B}} (y)}

{\ displaystyle W_ {\ текст {1B}} (y)}

при использовании нотации, общей для управления параллелизмом.

T 2 {\ displaystyle T_ {2}}

T_{{2}}

читает y на B и записывает x на A, то есть

T 2 = R 2B (y) {\ displaystyle T_ {2} = R _ {\ text {2B}} (y)}

{\ displaystyle T_ {2} = R _ {\ text {2B}} (y)}

W 2A (x) {\ displaystyle W_ {\ text {2A}} (x)}

{\ displaystyle W _ {\ text {2A}} (x)}

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

Локальные суб-транзакции
УзелТранзакция	A	B
$T 1 {\ displaystyle T_ {1}}$ $T _ {{1}}$	$T 1A = R 1A (x) {\ displaystyle T _ {\ text {1A}} = R _ {\ text {1A}} (x)}$ ${\ displaystyle T _ {\ text {1A}} = R _ {\ text {1A}} (x)}$	$T 1B = W 1B (y) {\ displaystyle T _ {\ text {1B}} = W _ {\ text {1B}} (y)}$ ${\ displaystyle T _ {\ text {1B}} = W _ {\ text {1B}} (y)}$
$T 2 {\ displaystyle T_ {2}}$ $T_{{2}}$	$T 2A = W 2A (x) {\ displaystyle T _ {\ text {2A}} = W _ {\ text {2A}} (x)}$ ${\ displaystyle T _ {\ text {2A}} = W _ {\ текст {2A}} (x)}$	$T 2B = R 2B (y) {\ displaystyle T _ {\ text {2B}} = R _ {\ text {2B}} (y)}$ ${\ displaystyle T _ {\ text {2B}} = R _ {\ text {2B}} ( y)}$

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

R 1A (x) {\ displaystyle R _ {\ text {1A}} (x)}

{\ displaystyle R _ {\ text {1A}} (x)}

R 2B ( y) {\ displaystyle R _ {\ text {2B}} (y)}

{\ displaystyle R _ {\ text {2B}} (y)}

(также

R 2B (y) {\ displaystyle R _ {\ text {2B}} (y)}

{\ displaystyle R _ {\ text {2B}} (y)}

R 1A (x) {\ displaystyle R _ {\ text {1A}} (x)}

{\ displaystyle R _ {\ text {1A}} (x)}

возможно)

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

T 1A {\ displaystyle T _ {\ text {1A}}}

{\ displaystyle T_ {\ text {1A}}}

готово (выполнение завершено) и проголосовано (в атомарном обязательстве)

T 1B {\ displaystyle T _ {\ text {1B}}}

{\ displaystyle T _ {\ text {1B}}}

запущен и заблокирован (нематериализованная конфликтная ситуация; голосование по ней невозможно)

T 2B {\ displaystyle T_ { \ text {2B}}}

{\ displaystyle T _ {\ text { 2B}}}

готов и проголосовало

T 2A {\ displaystyle T _ {\ text {2A}}}

{\ displa ystyle T _ {\ text {2A}}}

запущен и заблокирован (нематериализованный конфликт ; нет голоса).

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

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

Варианты

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

Ситуации тупика при голосовании
Случай	Узел. A	Узел. B	Возможное расписание	Материализованные. конфликты. в цикле	Не-. материализованные. конфликты	$T 1A = R 1A (x) {\ displaystyle T _ {\ text {1A}} = R _ {\ text {1A}} (x)}$ ${\ displaystyle T _ {\ text {1A}} = R _ {\ text {1A}} (x)}$	$T 1B = W 1B (y) {\ displaystyle T _ {\ text {1B}} = W _ {\ text {1B}} (y)}$ ${\ displaystyle T _ {\ text {1B}} = W _ {\ text {1B}} (y)}$	$T 2A = W 2A (x) {\ displaystyle T _ {\ text {2A}} = W _ {\ text {2A}} (x)}$ ${\ displaystyle T _ {\ text {2A}} = W _ {\ текст {2A}} (x)}$	$T 2B = R 2B (y) {\ displaystyle T _ {\ text {2B}} = R _ {\ текст {2B}} (y)}$ ${\ displaystyle T _ {\ text {2B}} = R _ {\ text {2B}} ( y)}$
1	SS2PL	SS2PL	$R 1A (x) R 2B (y) {\ displaystyle R _ {\ text {1A}} (x) R _ {\ text {2B}} (y)}$ ${\ displaystyle R _ {\ text {1A}} (x) R _ {\ text {2B}} (y)}$	0	2	Ready. Проголосовал	Running. (Blocked)	Running. (Blocked)	Ready. Проголосовал
2	SS2PL	SCO	$R 1A (x) R 2B (y) W 1B (y) {\ displaystyle R _ {\ text {1A}} (x) R _ {\ text {2B}} (y) W _ {\ text {1B}} (y)}$ ${\ displaystyle R _ {\ text {1A}} (x) R _ {\ text {2B}} (y) W _ {\ text {1B}} (y) }$	1	1	Ready. Voted	Ready. Голосо вание заблокировано	Выполняется. (Заблокировано)	Готов. Проголосовал
3	SCO	SS2PL	$R 1A (Икс) R 2B (Y) W 2A (x) {\ Displaystyle R _ {\ text {1A}} (x) R _ {\ text {2B}} (y) W _ {\ text {2A}} (x)}$ ${\ displaystyle R _ {\ text {1A}} (x) R _ {\ text {2B}} ( y) W _ {\ text {2A}} (x)}$	1	1	Готов. Проголосовал	Работает. ( Заблокировано)	Готов. Голосование заблокировано	Готово. Проголосовало
4	SCO	SCO	$R 1A (x) R 2B (y) W 1B (y) W 2A (x) {\ displaystyle R _ {\ text {1A}} (x) R _ {\ text {2B}} (y) W _ {\ text {1B}} (y) W _ {\ text {2A}} (x)}$ ${\ displaystyle R _ {\ text {1A}} (x) R _ {\ text {2B}} (y) W _ {\ text {1B}} (y) W _ {\ text {2A}} (x)}$	2	0	ГотовГолосовал	Готов. Голосование заблокировано	Готов. Голосование заблокировано	Готово. Проголосовано

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

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

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

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

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

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

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

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

Выводится следующее:

Теорема MuSiC

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

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

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

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

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

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

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

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

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

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

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

Strict CO (SCO)

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

Strict Commitment Ordering (SCO; (Raz 1991c)) является пересечением строгости (особый случай возможности восстановления) и CO, и обеспечивает верхнюю Можно использовать аналогичные механизмы, используемые для популярных SS2PL с накладными расходами.

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

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

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

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

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

Оптимистический CO (OCO)

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

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

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

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

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

T 1, T 2 {\ displaystyle T_ {1}, T_ {2}}

T _ {{1}}, T _ {2}}

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

T 1 {\ displaystyle T_ {1}}

T _ {{1}}

до

T 2 {\ displaystyle T_ {2 }}

T_{{2}}

(

T 1 {\ displaystyle T_ {1}}

T _ {{1}}

предшествует

T 2 {\ displaystyle T_ {2}}

T_{{2}}

, возможно, транзитивно, косвенно). В расписании есть свойство Расширенное упорядочение обязательств (ECO), если для каждых двух таких транзакций

T 1 {\ displaystyle T_{1}}

T _ {{1}}

фиксируется до

T 2 { \ displaystyle T_ {2}}

T_{{2}}

фиксирует.

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

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

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

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

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

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

Алгоритм ECO

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

Условие обеспечения Global ECO можно резюмировать аналогично CO:

Теорема о стратегии упорядочивания стратегии Global ECO Enforcing Vote

Пусть

T 1, T 2 {\ displaystyle T_ {1}, T_ {2 }}

T _ {{1}}, T _ {2}}

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

Т 1 {\ displaystyle T_ {1}}

T _ {{1}}

до

T 2 {\ displaystyle T_ {2}}

T_{{2}}

. Затем, если

T 1 {\ displaystyle T_ {1}}

T _ {{1}}

закончился (зафиксирован или прерван) до

T 2 {\ displaystyle T_ {2}}

T_{{2}}

, будет проголосовано за обязательство в каждой такой системе баз данных в среде с базами данных является и достаточным условием для обеспечения Global ECO (условие гарантирует Global ECO, которое может быть нарушено без этого).

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

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

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

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

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

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

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

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

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

Комментарий : Теперь система баз данных с одной версией, совместимая с 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); см. также Создание сериализуемой изоляции моментальных снимков ( и ссылки там) для анализа конфликтов в 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 любого варианта имеет одну и ту же роль для определения позиции каждой глобальной транзакции (транзакции, охватывающей две или более базы данных) в локальном поручении на обязательство, то есть для определения того, когда настала очередь транзакции голосовать. локально в протоколе атомарной фиксации. Таким образом, все варианты CO демонстрируют одинаковое поведение в отношении связывания атомов. Это означает, что все они могут взаимодействовать через атомарную фиксацию (с использованием одних и тех же программных интерфейсов, обычно предоставляемых как services, некоторые уже стандартизированы для атомарной фиксации, в первую очередь для двухфазной фиксации протокол, например, X / Open XA ) и прозрачно могут использоваться вместе в любой распределенной среде (в то время как каждый вариант CO может быть связан с любым релевантным типом механизма управления локальным параллелизмом).

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

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

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

Теорема о взаимодействии вариантов CO

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

Ссылки

Раз, Йоав (август 1992 г.), «Принцип упорядочивания по обязательствам или гарантия сериализуемости в гетерогенной среде Несколько автономных менеджеров ресурсов, использующих атомную приверженность " (PDF), Материалы восемнадцатой Международной конференции по очень большим базам данных, Ванкувер, Канада, стр. 292–312 (также DEC-TR 841, Digital Equipment Corporation, ноябрь 1990 г.)
Раз, Йоав (сентябрь 1994 г.), «Сериализуемость по обязательству», Письма об обработке информации, 51 (5): 257–264, doi : 10.1016 / 0020-0190 (94) 90005-1
Раз, Йоав (июнь 2009 г.), Теория приверженности Упорядочивание: Резюме, получено 11 ноября 2011 г.
Раз, Йоав (ноябрь 1990 г.), О значении приверженности заказу (PDF), Digital Equipment Corporation
Йоав Раз (1991a): патенты США 5,504,899 (ECO) 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 г.)

Сноски

Внешние ссылки

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