Классика баз данных - статьи

       

Родственные исследования


Системы баз данных, в которых обеспечиваются более строгие гарантии сериализуемости, чем эквивалентность некоторому порядку следования, существуют более трех десятилетий. Например, предлагалось гарантировать эквивалентность заданному порядку временных меток транзакций с использованием разновидности схемы управления параллелизмом с упорядочиванием на основе временных меток, называемой консервативной схемой упорядочивания по временным меткам (conservative T/O) [3]. (Позже эту схему стали называть "предельной консервативной схемой временных меток" ("ultimate conservative T/O" )[5], чтобы отличать ее от других схем управления параллелизмом с упорядочиванием по временным меткам, в которых допускается аварийное завершение транзакций и переупорядочивание.) Conservative T/O задерживает выполнение любой операции над базой данных до тех пор, пока заведомо не будут выполнены все потенциально конфликтующие операции с меньшими значениями временных меток. Как правило, это реализуется за счет того, что планировщик операций ожидает получения сообщений от всех возможных источников транзакций, а затем планирует выполнение операции чтения или записи с наименьшей временной меткой среди всех источников.

Эта бесхитростная реализация чрезмерно консервативна, поскольку, как правило, сериализует все операции записи в базу данных. Однако можно добиться дополнительного параллелизма метода разбиения транзакций на классы, использованного в SDD-1 [6], где каждая транзакция включалась в некоторый класс транзакций, и только для потенциально конфликтующих классов транзакций требовалась консервативная обработка. Такому подходу способствует заблаговременное объявление наборов чтения и записи транзакций. В нашей работе совершенствуются эти старые методы для обеспечения эквивалентности одному порядку следования. Однако мы решили реализовать свою детерминированную систему баз данных с использованием техники блокировок и оптимистических методов, позволяющих обойтись без заблаговременного знания наборов чтения и записи, поскольку в большинстве современных систем баз данных управление параллелизмом основывается на технике блокировок, а не технике временных меток.


Теоретическое обоснование того, что детерминированное выполнение внутри каждой системы, содержащей реплику базы данных, облегчает активную репликацию, можно найти в работе Шнейдера (Schneider) [23]. В этой работе демонстрируется, что если каждая система, содержащая реплику базы данных, получает транзакции в одном и том же порядке и обрабатывает их детерминированным, последовательным образом, то все реплики останутся согласованными. К сожалению, то требование, что каждая система с репликой базы данных выполняет транзакции с использованием одного потока управления, для сегодняшних высокопараллельных систем баз данных не является реалистичным. К аналогичному выводу пришли и Хименес-Перис (Jimenez-Peris) и др. [11]. Поэтому они применили детерминированный планировщик потоков управления, позволяющей системе с репликой базы данных выполнять транзакции с использованием нескольких потоков управления. Каждый поток управления одинаково планируется в каждой системе-реплике (с тщательным учетом возможности чередования работы локальных потоков управления с работой, возникающей в результате получения сообщений от других серверов в ходе выполнения распределенных транзакций). Наша работа отличается от работы Хименеса-Периса и др., поскольку мы допускаем произвольное планирование потоков управления (что обеспечивает планировщику большую гибкость и позволяет незамедлительно обрабатывать приходящие сетевые сообщения, а не ждать, пока не завершится работа локальных потоков управления) и обеспечиваем детерминизим за счет изменения протокола управления параллелизмом в системе баз данных.

В недавней работе Басиле (Basile) и др. [1] подход Хименеса-Периса и др. расширяется за счет перехвата запросов взаимного исключения (mutex), поступающих от потоков управления перед тем, как они обращаются к совместно используемым данным. Это позволяет повысить уровень параллелизма, позволяя планировать произвольным образом потоки управления, в которых не производится доступ к одним и тем же данным.


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

Идея упорядочивания тразакций и предоставлении блокировок на запись в соответствии с этим порядком была представлена в работе Кемме (Kemme) и Алонсо (Alonso) [13]. Наша работа отличается от предложенного ими подхода тем, что в нашем случае не используются теневые копии (shadow copy), и требуется всего лишь надежный протокол обмена груповыми сообщениями, гарантирующий порядок их доставки, при посылке сообщений от препроцессора к базе данных – никогда внутри многораздельных транзакций, поскольку в детерминированной системе это привело бы к недопустимо долгим интервалам удержания блокировок. Кроме того, мы обрабатываем зависимые транзакции с использованием оптимистического метода.

Гарсиа-Молина (Garcia-Molina) и Салем (Salem) [9] заметили, что использование систем баз данных в основной памяти (main memory database system) приводит к убыстрению транзакций и снижению вероятности конфликтов блокировок. Кроме того, они утверждают, что во многих случаях лучше всего выполнять транзакции полностью последовательно и полностью избегать накладных расходов блокировок. В нашей работе приходится не только учитывать, что транзакции над данными основной памяти выполняются быстрее транзакций, которым приходится обращаться к дискам, но и принимать во внимание, что продолжительность некоторых транзакций увеличивается из-за потребности в передачи и приеме сетевых сообщений (требуемых для выполнения распределенных транзакций). Кроме того, мы не требуем, чтобы транзакции выполнялись последовательно (хотя обеспечиваем эквивалентность заданному порядку следования); несколько разных транзакций может параллельно выполняться в нескольких потоках управления.

Уитни (Whitney) и др. [26], Пачитти (Pacitti) и др. [18], Стоунбрейкер (Stonebraker) и др. [24] и Джонс (Jones) и др. [12] предлагают обрабатывать транзакции в распределенных системах баз данных без управления параллелизмом путем последовательного выполнения транзакций в одном потоке управления на каждом узле (где в некоторых случаях узел может являться одним ядром процессора в многоядерном сервере [24]).


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

Разработчики решений уровня промежуточного программного обеспечения (middleware), таких как, например, разработка компании xkoto (недавно поглощенной компанией Teradata) и Tashkent-API [8], пытаются производить репликацию в нескольких системах баз данных путем выполнения в каждой системе одних и тех же транзакций в одном и том же порядке. Однако поскольку системы баз данных не обеспечивают эквивалентности какому-либо заданному порядку следования, в этих системах middleware для предотвращения расхождения реплик снижается уровень параллелизма транзакций, отправляемых в системы баз данных, что потенциально приводит к понижению пропускной способности. Наше решение реализуется внутри баз данных, что позволяет избежать чрезмерной сложности систем, основанных на промежуточном программном обеспечении.

Тэй (Tay) и др. с использованием детальной аналитической модели сравнивают традиционную динамическую схему блокировок со статической схемой (когда все блокировки в транзакции запрашиваются при ее начале) [25]. Однако в случае статической схемы, если невозможно получить все блокировки сразу, транзакция аварийно завершается и запускается заново (и, следовательно, протокол не является детерминированным). Кроме того, эта модель не работает в том случае, когда местоположение данных, которые требуется блокировать, заранее не известно.


Содержание раздела