Глобальная сериализуемость

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

В системе баз данных объединения или любой другой системе с несколькими базами данных с более широким определением, которые обычно распределены в сети связи, транзакции охватывают несколько (и, возможно, распределенных ) баз данных. Обеспечение глобальной сериализуемости в такой системе, где разные базы данных могут использовать разные типы управления параллелизмом, проблематично. Даже если каждое локальное расписание отдельной базы данных сериализуемо, глобальное расписание всей системы не обязательно сериализуемо. Массовые обмены информацией о конфликтах между базами данных для достижения сериализации конфликтов на глобальном уровне могут привести к неприемлемой производительности, в первую очередь из-за задержки компьютера и связи. Эффективное достижение глобальной сериализуемости с помощью различных типов управления параллелизмом открыто в течение нескольких лет. Упорядочивание по обязательствам (или Заказ по обязательствам; CO), метод сериализации, публично представленный в 1991 г. компанией Digital Equipment Corporation (DEC), обеспечивает эффективное общее решение для глобального (конфликта ) сериализуемость в любом наборе систем баз данных и других, возможно, с другими механизмами управления параллелизмом. CO не нуждается в распространении информации о конфликтах, а скорее использует уже необходимые (немодифицированные) сообщения протокола без какой-либо дополнительной связи между базами данных. Он также допускает оптимистичные (неблокирующие) реализации. CO обобщает строгую двухфазную блокировку (SS2PL), которая в сочетании с протоколом двухфазной фиксации (2PC) является стандартом де-факто для достижения глобального возможность сериализации в системах баз данных (на основе SS2PL). В результате системы баз данных, совместимые с CO (с любыми различными типами управления параллелизмом), могут прозрачно присоединяться к существующим решениям на основе SS2PL для глобальной сериализуемости. То же самое относится и ко всем другим системам с несколькими (транзакционными) объектами, которые используют атомарные транзакции и нуждаются в глобальной сериализуемости для корректности (см. Примеры выше; в настоящее время такая потребность не меньше, чем с системами баз данных, источником атомарных транзакций).

Наиболее важными аспектами CO, которые делают его уникальным эффективным общим решением для глобальной сериализуемости, являются следующие:

1. Полная интеграция с низкими накладными расходами с любым механизмом управления параллелизмом, без изменения планирования или блокировки операций какой-либо транзакции
2. Неоднородность : глобальная сериализуемость достигается в нескольких (например, системах управления базами данных ) с разными (любыми) механизмами управления параллелизмом, без вмешательства в механизмы '
3. Модульность : Транзакционные объекты могут быть добавлены и удалены прозрачно.
4. Автономность транзакционных объектов: Нет необходимости в конфликте или эквивалентном распределении информации (например, локальные отношения приоритета, блокировки, временные метки или билеты; ни один объект не нуждается в информации другого объекта).
5. Масштабируемость : при "обычных" глобальных транзакциях, размер компьютерной сети и количество транзакционных объектов могут неограниченно увеличиваться с n o влияние на производительность и
6. Автоматическое разрешение глобальной взаимоблокировки.

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

• 1 Глобальная проблема сериализуемости
  • 1.1 Постановка проблемы
  • 1.2 Расценки
  • 1.3 Предлагаемые решения
  • 1.4 Технологические перспективы
• 2 Решение для заказа с обязательством
• 3 Ослабление глобальной сериализуемости
• 4 ссылки

Постановка проблемы

Трудности, описанные выше, превращаются в следующую проблему:

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

Цитаты

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

• «Без знаний о локальных, а также глобальных транзакциях маловероятно, что можно будет эффективно управлять глобальным параллелизмом. при условии... Дополнительные сложности возникают, когда разные компонентные СУБД [системы управления базами данных] и FDBMS [системы управления федеративными базами данных] поддерживают разные механизмы параллелизма... Маловероятно, что теоретически элегантное решение, обеспечивающее сериализуемость конфликтов без ущерба для производительности (т. е. параллелизм и / или время ответа) и доступность существует ».

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

• «Управление транзакциями в гетерогенной распределенной системе баз данных - сложная проблема. Основная проблема заключается в том, что каждая из локальных систем управления базами данных может использовать разные типы схем управления параллелизмом. Интеграция этой сложной проблемы, усугубляемой если мы хотим сохранить локальную автономию каждой из локальных баз данных и разрешить параллельное выполнение локальных и глобальных транзакций. Одно простое решение - ограничить глобальные транзакции доступом только для извлечения. Однако проблема надежного управления транзакциями в общий случай, когда глобальным и локальным транзакциям разрешены как чтение, так и запись данных, все еще открыт."

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

Даже в более поздние годы, после публичного представления общего решения упорядочения обязательств в 1991 году, проблема все еще считалась неразрешимой:

• «Мы представляем модель транзакции для систем с несколькими базами данных с автономными компонентными системами., придумал гетерогенные трехуровневые транзакции. Стало очевидно, что в такой системе невозможно согласовать требования по обеспечению полных свойств ACID и полной локальной автономии... "

Цитата выше взята из статья 1997 года, предлагающая упрощенное решение глобальной сериализуемости (см. Ослабление глобальной сериализуемости ниже) и ссылки на статьи Commitment ordering (CO). Решение CO эффективно поддерживает как полные свойства ACID, так и полную локальную автономию, а также удовлетворяет другим требованиям, изложенным выше в разделе Описание проблемы, и, по-видимому, было неправильно понято.

Подобное мышление мы видим также в следующей цитате из статьи 1998 года:

• «Концепция сериализуемости была традиционно принятым критерием корректности в системах баз данных. Однако в системах с несколькими базами данных (MDBS), обеспечивая глобальную сериализуемость является сложной задачей. Трудность возникает из-за неоднородности протоколов управления параллелизмом, используемых участвующими локальными системами управления базами данных (СУБД), и стремлением сохранить автономность локальных СУБД. В целом, решения проблемы глобальной сериализуемости приведет к выполнению с низкой степенью параллелизма. Альтернатива, ослабленная сериализуемость, может привести к несогласованности данных. "

Также в цитированной выше статье предлагается упрощенное решение глобальной сериализуемости, ссылаясь на работу CO. Решение CO для глобальной сериализуемости как мосты между различными протоколами управления параллелизмом, без существенного сокращения параллелизма (и обычно незначительное, если оно вообще есть), и поддерживает автономность локальных СУБД. Очевидно, и здесь CO было неправильно понято. Это недоразумение продолжается до 2010 года в учебнике некоторых из тех же авторов, где подчеркивается и подробно описывается та же самая упрощенная техника глобальной сериализуемости, двухуровневая сериализуемость, а CO вообще не упоминается.

С другой стороны, следующая цитата по CO появляется в книге 2009 года:

• «Не все алгоритмы управления параллелизмом используют блокировки... Три других метода - это упорядочивание временных меток, тестирование графа сериализации и упорядочение фиксации. Упорядочивание временных меток назначает каждой транзакции метку времени и гарантирует, что конфликтующие операции выполняются в порядке меток времени. Тестирование графа сериализации отслеживает конфликты и обеспечивает ацикличность графа сериализации. Порядок фиксации обеспечивает согласованность конфликтующих операций с относительным порядком, в котором их транзакции фиксируются, что может обеспечить взаимодействие систем, использующих различные механизмы управления параллелизмом ».

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

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

Характеристики и свойства решения CO обсуждаются ниже.

Предлагаемые решения

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

• Глобальный граф конфликтов (граф сериализуемости, граф приоритета ) проверка
• Распределенная Двухфазная блокировка (Распределенная 2PL)
• Распределенный Порядок временных меток
• Билеты (локальные логические временные метки, которые определяют локальные общие заказы и распространяются для определения глобального частичного порядка транзакций)
• Упорядочивание обязательств

Технологическая перспектива

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

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

1. не мешает ни одной операции транзакции, в частности, не блокирует, не ограничивает и не задерживает любую операцию доступа к данным (чтение или запись) как для локальных, так и для глобальных транзакций (и, следовательно, не вызывает лишних прерываний); таким образом, обеспечивает бесшовную интеграцию с любым механизмом управления параллелизмом.
2. допускает оптимистичные реализации (неблокирующие, то есть без блокировки доступа к данным).
3. допускает гетерогенность : Глобальная сериализуемость достигается для нескольких с разными (любыми) механизмами управления параллелизмом без вмешательства в операции механизмов.
4. допускает модульность : Транзакционные объекты могут добавляться и удаляться прозрачно.
5. обеспечивает полную поддержку транзакций ACID.
6. поддерживает автономность каждой базы данных и не требует какого-либо распределения информации управления параллелизмом (например, отношения локального приоритета, блокировки, отметки времени или билеты).
7. не требует каких-либо знаний о транзакциях.
8. не требует дополнительных затрат на связь, поскольку он использует только уже необходимые немодифицированные сообщения протокола (любой такой протокол; использование отказоустойчивый протоколы атомарных обязательств и системы баз данных делают решение CO отказоустойчивым).
9. автоматически разрешает глобальные взаимоблокировки из-за блокировки.
10. эффективно масштабируется с размером компьютерной сети и количеством баз данных, почти без какого-либо отрицательного влияния на производительность, поскольку каждая глобальная транзакция обычно ограничивается определенным относительно небольшим количеством баз данных и сетевых узлов.
11. не требует дополнительных операций искусственного доступа к транзакциям (например, «взять отметку времени » или «взять билет "), что обычно приводит к дополнительным искусственным конфликтам, уменьшающим параллелизм.
12. требует небольших накладных расходов.

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

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

Большинство существующих систем баз данных, включая все основные коммерческие системы баз данных, основаны на строгой строгой двухфазной блокировке (SS2PL) и уже совместимы с CO. Таким образом, они могут участвовать в решении на основе CO для глобальной сериализуемости в средах с несколькими базами данных без каких-либо изменений (за исключением популярного многоверсионности, где следует учитывать дополнительные аспекты CO). Достижение глобальной сериализуемости в базах данных на основе SS2PL с использованием атомарной фиксации (в основном с использованием двухфазной фиксации, 2PC) использовалось в течение многих лет (т. Е. С использованием одного и того же решения CO для конкретного особого случая; однако нет ссылок известный до CO, который замечает автоматическое глобальное разрешение тупиков в этом особом случае с помощью процесса исключения глобального цикла augmented-конфликт-graph протокола атомарной фиксации). Практически все существующие среды обработки распределенных транзакций и вспомогательные продукты полагаются на SS2PL и обеспечивают 2PC. Фактически SS2PL вместе с 2PC стали стандартом де-факто. Это решение представляет собой однородное управление параллелизмом, субоптимальное (когда требуются и Сериализуемость, и Строгость ; см. Строгое обязательное упорядочение ; SCO), но все же достаточно эффективное в большинстве случаев, иногда за счет увеличенной вычислительной мощности, необходимой относительно оптимальной. (Однако для повышения производительности используется ослабленная сериализуемость всякий раз, когда это позволяют приложения). Он обеспечивает взаимодействие между SS2PL-совместимыми системами баз данных различных типов, то есть допускает неоднородность в аспектах, отличных от управления параллелизмом. SS2PL является очень ограничивающим свойством расписания и «берет верх» в сочетании с любым другим свойством. Например, в сочетании с любым оптимистическим свойством результат больше не оптимистичен, а скорее характерен для SS2PL. С другой стороны, CO вообще не меняет шаблоны планирования доступа к данным, и любые характеристики объединенного свойства остаются неизменными. Поскольку также CO использует атомарное обязательство (например, 2PC) для достижения глобальной сериализуемости, как это делает SS2PL, любая CO-совместимая система базы данных или транзакционный объект может прозрачно присоединяться к существующим средам на основе SS2PL, использовать 2PC и поддерживать глобальную сериализуемость без каких-либо изменений среды. Это делает CO прямым, естественным обобщением SS2PL для любой системы баз данных, основанной на сериализуемости конфликтов, для всех практических целей.

Упорядочивание обязательств было довольно широко известно в сообществах обработки транзакций и баз данных в Digital Equipment Corporation (DEC) с 1990 года. конфиденциальность компании в связи с процессами патентования. CO была раскрыта за пределами DEC в ходе лекций и распространения технических отчетов среди исследователей баз данных в мае 1991 года, сразу после первой подачи патента. Многие исследователи баз данных неправильно понимали его спустя годы после его появления, о чем свидетельствуют приведенные выше цитаты из статей 1997–1998 годов, в которых упоминаются статьи о порядке выполнения обязательств. С другой стороны, CO широко использовался как решение для глобальной сериализуемости в работах, а в последнее время в соответствующем Re: GRIDiT, который представляет собой подход к управлению транзакциями в конвергентной Grid. вычисления и Облачные вычисления. Смотрите больше в.

Для ослабленной глобальной сериализуемости были разработаны некоторые методы (т. Е. Они не гарантируют глобальной сериализуемости; см. Также Ослабление сериализуемости ). Среди них (с несколькими публикациями для каждой):

• Квази-сериализуемость
• Двухуровневая сериализуемость

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

Другой распространенной причиной ослабления глобальной сериализуемости в настоящее время является требование доступности продуктов в Интернете и услуг. На это требование обычно отвечает крупномасштабная репликация данных . Простое решение для синхронизации обновлений реплик одного и того же объекта базы данных - это включение всех этих обновлений в одну атомарную распределенную транзакцию. Однако со многими репликами такая транзакция очень велика и может охватывать несколько компьютеров и сетей, причем некоторые из них, вероятно, будут недоступны. Таким образом, такая транзакция, скорее всего, завершится прерыванием и не достигнет своей цели. Следовательно, Оптимистическая репликация (Ленивая репликация) часто используется (например, во многих продуктах и ​​услугах Google, Amazon, Yahoo, и тому подобное), в то время как глобальная сериализуемость ослаблена и скомпрометирована для конечной согласованности. В этом случае релаксация выполняется только для приложений, которые, как ожидается, не пострадают.

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