Управление конкурентным доступом к базам данных: упорядочение фиксаций (Commit Ordering)

Введение

Техника управления конкурентным доступом к базам данных

Порядок фиксации (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; Raz 1993b). Они также обеспечивают глобальную сериализуемость без распространения информации о локальном управлении конкурентным доступом, могут быть объединены с любым соответствующим управлением конкурентным доступом и позволяют реализовывать оптимистичные (неблокирующие) подходы. Оба используют дополнительную информацию для ослабления ограничений CO и достижения лучшей параллельности и производительности. Порядок голосования (VO или обобщенный CO (GCO); Raz 2009) — это набор расписаний (свойство) и техника для CO и всех его вариантов. Локальный VO необходим для гарантии глобальной сериализуемости, если участники протокола атомарной фиксации (ACP) не обмениваются информацией об управлении конкурентным доступом (обладают свойством обобщенной автономии). CO и его варианты взаимодействуют прозрачно, гарантируя глобальную сериализуемость и автоматическое разрешение глобальных взаимоблокировок в смешанной, гетерогенной среде с различными вариантами.

Commitment ordering (CO) is a class of interoperable serializability techniques in concurrency control of databases, transaction processing, and related applications. It allows optimistic (non blocking) implementations. With the proliferation of multi core processors, CO has also been increasingly utilized in concurrent programming, transactional memory, and software transactional memory (STM) to achieve serializability optimistically. CO is also the name of the resulting transaction schedule (history) property, defined in 1988 with the name dynamic atomicity. In a CO compliant schedule, the chronological order of commitment events of transactions is compatible with the precedence order of the respective transactions. CO is a broad special case of conflict serializability and effective means (reliable, high performance, distributed, and scalable) to achieve global serializability (modular serializability) across any collection of database systems that possibly use different concurrency control mechanisms (CO also makes each system serializability compliant, if not already). Each not CO compliant database system is augmented with a CO component (the commitment order coordinator—COCO) which orders the commitment events for CO compliance, with neither data access nor any other transaction operation interference. As such, CO provides a low overhead, general solution for global serializability (and distributed serializability), instrumental for global concurrency control (and distributed concurrency control) of multi database systems and other transactional objects, possibly highly distributed (e. g., within cloud computing, grid computing, and networks of smartphones). An atomic commitment protocol (ACP; of any type) is a fundamental part of the solution, utilized to break global cycles in the conflict (precedence, serializability) graph. CO is the most general property (a necessary condition) that guarantees global serializability, if the database systems involved do not share concurrency control information beyond atomic commitment protocol (unmodified) messages and have no knowledge of whether transactions are global or local (the database systems are autonomous). Thus CO (with its variants) is the only general technique that does not require the typically costly distribution of local concurrency control information (e. g., local precedence relations, locks, timestamps, or tickets). It generalizes the popular strong strict two phase locking (SS2PL) property, which in conjunction with the two phase commit protocol (2PC), is the de facto standard to achieve global serializability across (SS2PL based) database systems. As a result, CO compliant database systems (with any different concurrency control types) can transparently join such SS2PL based solutions for global serializability. In addition, locking based global deadlocks are resolved automatically in a CO based multi database environment, a vital side benefit (including the special case of a completely SS2PL based environment; a previously unnoticed fact for SS2PL). Furthermore, strict commitment ordering (SCO; Raz 1991c), the intersection of Strictness and CO, provides better performance (shorter average transaction completion time and resulting in better transaction throughput) than SS2PL whenever read write conflicts are present (identical blocking behavior for write read and write write conflicts; comparable locking overhead). The advantage of SCO is especially during lock contention. Strictness allows both SS2PL and SCO to use the same effective database recovery mechanisms. Two major generalizing variants of CO exist, extended CO (ECO; Raz 1993a) and multi version CO (MVCO; Raz 1993b). They also provide global serializability without local concurrency control information distribution, can be combined with any relevant concurrency control, and allow optimistic (non blocking) implementations. Both use additional information for relaxing CO constraints and achieving better concurrency and performance. Vote ordering (VO or Generalized CO (GCO); Raz 2009) is a container schedule set (property) and technique for CO and all its variants. Local VO is necessary for guaranteeing global serializability if the atomic commitment protocol (ACP) participants do not share concurrency control information (have the generalized autonomy property). CO and its variants inter operate transparently, guaranteeing global serializability and automatic global deadlock resolution together in a mixed, heterogeneous environment with different variants.

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

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

A database system in a multidatabase environment is assumed. From a software architecture point of view, a CO component that implements the generic CO algorithm locally, the Commitment Order Coordinator (COCO), can be designed straightforwardly as a mediator between a (single) database system and an atomic commitment protocol component (Raz 1991b). However, the COCO is typically an integral part of the database system. The COCO's functions are to vote to commit on ready global transactions (the processing has ended) according to the local commitment order, to vote to abort on transactions for which the database system has initiated an abort (the database system can initiate abort for any transaction, for many reasons), and to pass the atomic commitment decision to the database system. For local transactions (when can be identified), no voting is needed. For determining the commitment order, the COCO maintains an updated representation of the local conflict graph (or local augmented conflict graph for capturing also locking deadlocks) of the undecided (neither committed nor aborted) transactions as a data structure (e. g., utilizing mechanisms similar to locking for capturing conflicts, but with no data access blocking). The COCO component has an interface with its database system to receive "conflict," "ready" (the processing has ended; readiness to vote on a global transaction or commit a local one), and "abort" notifications from the database system. It also interfaces with the atomic commitment protocol to vote and receive the atomic commitment protocol's decision on each global transaction. The decisions are delivered from the COCO to the database system through their interface, as well as local transactions' commit notifications, at a proper commit order. The COCO, including its interfaces, can be enhanced, if it implements another variant of CO (see below) or plays a role in the database's concurrency control mechanism beyond voting in atomic commitment. The COCO also guarantees CO locally in a single, isolated database system with no interface with an atomic commitment protocol.

Разделение данных (x на A; y на B) важно, поскольку без него, например, к x можно получить прямой доступ из B. Если транзакция выполняется на B одновременно с транзакциями и и напрямую записывает x, то без распределенного менеджера блокировок, блокировка на чтение x, удерживаемая на A, не видна на B и не может заблокировать эту запись (или сигнализировать о материализованном конфликте для неблокирующей версии CO; см. ниже). Таким образом, сериализуемость может быть нарушена. Благодаря разделению данных, к x нельзя получить прямой доступ из B. Однако функциональность не ограничена, и транзакция, выполняемая на B, все еще может отправить запрос на запись или чтение x (хотя это и нетипично). Этот запрос передается локальной субтранзакции транзакции на A (которая создается, если она еще не существует), которая, в свою очередь, отправляет этот запрос локальному менеджеру данных на A.

Варианты 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, описанном выше, пусто из-за блокировок, и, следовательно, такой алгоритм в этом случае не нужен. Система управления базой данных может голосовать за транзакцию сразу после перехода в состояние "готовности", то есть после завершения выполнения задачи локально. Блокировки транзакции освобождаются системой управления базой данных только после решения протокола атомарной фиксации, и таким образом, условие в вышеупомянутой теореме Global CO соблюдается автоматически. Если система управления базой данных использует локальный механизм таймаута для разрешения (локальных) взаимоблокировок SS2PL, то откат заблокированных транзакций нарушает не только потенциальные локальные циклы в глобальном графе конфликтов (фактические циклы в расширенном графе конфликтов), но и потенциальные глобальные циклы системы управления базой данных как побочный эффект, если механизм отката протокола атомарной фиксации относительно медленный. Такие независимые откаты несколькими сущностями обычно могут приводить к ненужным отменам более чем одной транзакции в глобальном цикле. Ситуация иная для механизмов, основанных на графе ожидания: они не могут идентифицировать глобальные циклы, и протокол атомарной фиксации разорвёт глобальный цикл, если возникшая в результате голосования взаимоблокировка не будет разрешена ранее в другой базе данных. Локальные SS2PL в сочетании с атомарной фиксацией, обеспечивающей глобальную сериализуемость, также могут быть выведены напрямую: все транзакции, включая распределённые, подчиняются правилам 2PL (SS2PL). Механизм протокола атомарной фиксации здесь не нужен для достижения консенсуса по фиксации, а скорее для точки синхронизации на завершении второй фазы. Вероятно, по этой причине, без учёта механизма голосования по атомарной фиксации, автоматическое разрешение глобальных взаимоблокировок не было замечено до появления CO.

Strong Strict Two Phase Locking (SS2PL; also referred to as Rigorousness or Rigorous scheduling) means that both read and write locks of a transaction are released only after the transaction has ended (either committed or aborted). The set of SS2PL schedules is a proper subset of the set of CO schedules. This property is widely utilized in database systems, and since it implies CO, databases that use it and participate in global transactions generate together a serializable global schedule (when using any atomic commitment protocol, which is needed for atomicity in a multi database environment). No database modification or addition is needed in this case to participate in a CO distributed solution: The set of undecided transactions to be aborted before committing in the local generic CO algorithm above is empty because of the locks, and hence such an algorithm is unnecessary in this case. A transaction can be voted on by a database system immediately after entering a "ready" state, i. e., completing running its task locally. Its locks are released by the database system only after it is decided by the atomic commitment protocol, and thus the condition in the Global CO enforcing theorem above is kept automatically. If a local timeout mechanism is used by a database system to resolve (local) SS2PL deadlocks, then aborting blocked transactions breaks not only potential local cycles in the global conflict graph (real cycles in the augmented conflict graph), but also database system's potential global cycles as a side effect, if the atomic commitment protocol's abort mechanism is relatively slow. Such independent aborts by several entities typically may result in unnecessary aborts for more than one transaction per global cycle. The situation is different for a local wait for graph based mechanisms: Such cannot identify global cycles, and the atomic commitment protocol will break the global cycle, if the resulting voting deadlock is not resolved earlier in another database. Local SS2PL together with atomic commitment implying global serializability can also be deduced directly: All transactions, including distributed, obey the 2PL (SS2PL) rules. The atomic commitment protocol mechanism is not needed here for consensus on commit, but rather for the end of phase two synchronization point. Probably for this reason, without considering the atomic commitment voting mechanism, automatic global deadlock resolution has not been noticed before CO.

Строгое СО (СКО)

Строгое упорядочение обязательств (SCO; (Raz 1991c)) является пересечением строгости (частный случай восстановления) и CO и определяет верхнюю границу параллелизма расписания при наличии обоих свойств. Его можно реализовать с использованием блокирующих механизмов (блокировок), аналогичных используемым в популярном SS2PL, с сопоставимыми накладными расходами. В отличие от SS2PL, SCO не блокирует при конфликте чтения-записи, но может блокировать при фиксации изменений. SCO и SS2PL демонстрируют идентичное поведение блокировки для двух других типов конфликтов: запись-чтение и запись-запись. В результате SCO характеризуется более короткими средними периодами блокировки и более высоким уровнем параллелизма (например, симуляции производительности одной базы данных для наиболее значимого варианта блокировок с упорядоченным совместным использованием, идентичного SCO, наглядно это демонстрируют, показывая прирост примерно в 100% для некоторых рабочих нагрузок; также, при идентичных рабочих нагрузках SCO может достигать более высокой скорости обработки транзакций, чем SS2PL, до возникновения "треша" блокировок). Более высокий параллелизм означает, что при заданных вычислительных ресурсах за единицу времени завершается больше транзакций (более высокая скорость транзакций, пропускная способность), а средняя продолжительность транзакции сокращается (более быстрое завершение; см. график). Преимущество SCO особенно заметно при высокой конкуренции за блокировки. Теорема о производительности SCO против SS2PL SCO обеспечивает более короткое среднее время завершения транзакции, чем SS2PL, при наличии конфликтов чтения-записи. В противном случае SCO и SS2PL идентичны (демонстрируют идентичное поведение блокировки при конфликтах записи-чтения и записи-записи). SCO столь же практичен, как и SS2PL, поскольку, помимо сериализуемости, обеспечивает и строгость, которая широко используется в качестве основы для эффективного восстановления баз данных после сбоев. Механизм SS2PL можно легко преобразовать в SCO для повышения производительности без изменения методов восстановления. Описание реализации SCO можно найти в (Perrizo и Tatarinov 1998). См. также Полуоптимистичный планировщик базы данных. SS2PL является собственным подмножеством SCO (что является еще одним объяснением того, почему SCO менее ограничивающий и обеспечивает более высокий уровень параллелизма, чем SS2PL).

Strict Commitment Ordering (SCO; (Raz 1991c)) is the intersection of strictness (a special case of recoverability) and CO, and provides an upper bound for a schedule's concurrency when both properties exist. It can be implemented using blocking mechanisms (locking) similar to those used for the popular SS2PL with similar overheads. Unlike SS2PL, SCO does not block on a read write conflict but possibly blocks on commit instead. SCO and SS2PL have identical blocking behavior for the other two conflict types: write read, and write write. As a result, SCO has shorter average blocking periods, and more concurrency (e. g., performance simulations of a single database for the most significant variant of locks with ordered sharing, which is identical to SCO, clearly show this, with approximately 100% gain for some transaction loads; also for identical transaction loads SCO can reach higher transaction rates than SS2PL before lock thrashing occurs). More concurrency means that with given computing resources more transactions are completed in time unit (higher transaction rate, throughput), and the average duration of a transaction is shorter (faster completion; see chart). The advantage of SCO is especially significant during lock contention. The SCO Vs. SS2PL Performance Theorem
SCO provides shorter average transaction completion time than SS2PL, if read write conflicts exist. SCO and SS2PL are identical otherwise (have identical blocking behavior with write read and write write conflicts). SCO is as practical as SS2PL since as SS2PL it provides besides serializability also strictness, which is widely utilized as a basis for efficient recovery of databases from failure. An SS2PL mechanism can be converted to an SCO one for better performance in a straightforward way without changing recovery methods. A description of an SCO implementation can be found in (Perrizo and Tatarinov 1998). See also Semi optimistic database scheduler. SS2PL is a proper subset of SCO (which is another explanation why SCO is less constraining and provides more concurrency than SS2PL).

Оптимистическая ОК (ОК)

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

Пример: CO-изоляция (COSI)

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