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

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

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

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

Постановка задачи

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

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

Котировки

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

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

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

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

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

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

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

Квазисериализуемость ^[2]
Двухуровневая сериализуемость ^[3]

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

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

Ссылки

^ Амит Шет, Джеймс Ларсон (1990): «Объединенные системы баз данных для управления распределенными, гетерогенными и автономными базами данных». Архивировано 19 октября 2007 г. в Wayback Machine , ACM Computing Surveys , Vol. 22, № 3, стр. 183-236, сентябрь 1990 г. (цитата со стр. 227)
^ Веймин Ду и Ахмед К. Эльмагармид (1989): «Квази-сериализуемость: критерий правильности глобального управления параллелизмом в InterBase». Архивировано 21 декабря 2010 г. в Wayback Machine , Труды пятнадцатой Международной конференции по очень большим базам данных (VLDB). ), 22–25 августа 1989 г., Амстердам, Нидерланды, стр. 347–355, Морган Кауфманн, ISBN 1-55860-101-5
^ Шарад Мехротра, Раджив Растоги, Генри Корт, Авраам Зильбершац (1998): «Обеспечение согласованности в мультибазах данных путем сохранения двухуровневой сериализуемости» , Транзакции ACM в системах баз данных (TODS), Vol. 23, № 2, стр. 199-230, июнь 1998 г. (цитата из аннотации статьи)
^ Грей, Дж .; Хелланд, П.; О'Нил, П .; Шаша, Д. (1996). Опасности репликации и решение . Материалы Международной конференции ACM SIGMOD 1996 года по управлению данными . стр. 173–182. CiteSeerX 10.1.1.43.6498 . дои : 10.1145/233269.233330 .

[1] Амит Шет, Джеймс Ларсон (1990): «Объединенные системы баз данных для управления распределенными, гетерогенными и автономными базами данных». Архивировано 19 октября 2007 г. в Wayback Machine , ACM Computing Surveys , Vol. 22, № 3, стр. 183-236, сентябрь 1990 г. (цитата со стр. 227)

[Du1989-2] Веймин Ду и Ахмед К. Эльмагармид (1989): «Квази-сериализуемость: критерий правильности глобального управления параллелизмом в InterBase». Архивировано 21 декабря 2010 г. в Wayback Machine , Труды пятнадцатой Международной конференции по очень большим базам данных (VLDB). ), 22–25 августа 1989 г., Амстердам, Нидерланды, стр. 347–355, Морган Кауфманн, ISBN 1-55860-101-5

[Shar1998-3] Шарад Мехротра, Раджив Растоги, Генри Корт, Авраам Зильбершац (1998): «Обеспечение согласованности в мультибазах данных путем сохранения двухуровневой сериализуемости» , Транзакции ACM в системах баз данных (TODS), Vol. 23, № 2, стр. 199-230, июнь 1998 г. (цитата из аннотации статьи)

[Gray1996-4] Грей, Дж .; Хелланд, П.; О'Нил, П .; Шаша, Д. (1996). Опасности репликации и решение . Материалы Международной конференции ACM SIGMOD 1996 года по управлению данными . стр. 173–182. CiteSeerX 10.1.1.43.6498 . дои : 10.1145/233269.233330 .

[1]

[2]

[3]

[4]