Предисловие переводчика

Роберт Бретл является основателем и главным инженером компании GemStone Systems Inc., в которой в настоящее время он отвечает на разработку и поддержку ООСУБД Facets. За 24 года работы в GemStone он разработал многие ключевые компоненты архитектуры, включая буферизацию страниц, сборку мусора, таблицу объектов, функции поддержки транзакций. Он также руководил разработкой продукта компании GemStone GemFire.

Бретл, главным образом, является инженером и разработчиком. За свою жизнь он был соавтором всего нескольких статей (к наиболее известным относятся "The GemStone Data Management System", "Persistent Java Objects in 3 Tier Architectures", "Reduced-Conflict Objects" и "Achieving High Concurrency in Object Oriented Databases"). Статья, перевод которой предлагается вашему вниманию, чуть ли не первая, написанная Бретлом в одиночку.

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

Прямо замечу, что представляемая вашему вниманию статья не является ровной. В некоторых местах автор недостаточно понятен, иногда хотелось бы видеть большее число обоснований, более точных технических описаний и т.д. Но мне кажется, что все основные идеи понять можно. Если же вы знакомы с методами управления транзакциями в реляционных СУБД, то очень полезно сравнить подходы и подумать, из-за чего в ООСУБД приходится прибегать к таких хитростям.

К сожалению, мне не удалось найти в Internet (в открытом доступе) тексты публикаций, приводимых в списке литературы. Вернее, удалось найти текст только одной публикации, ссылку на который мы публикуем, и рекомендуем ей воспользоваться всем тем, кому интересны объектно-ориентированные базы данных.

Введение

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

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

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

Транзакции

Любое обсуждение транзакций начинается с обеспечения понимания их свойств ACID:

• Atomicy (Атомарность). Транзакция позволяет группировать одно или несколько изменений объектов базы данных для образования атомарной, или неделимой операции. Другими словами, либо выполняются все изменения, либо не выполняется ни одно из них. Если по какой-либо причине транзакция не может быть завершена, то с использованием операции abort, или rollback все объекты, измененные этой транзакцией, могут быть возвращены в состояние, в котором они находились до начала транзакции.
• Consistency (Согласованность). Транзакции всегда оперируют над согласованным видом базы данных, и они всегда оставляют базу данных в согласованном состоянии. Несогласованное состояние, которое может возникнуть в процессе выполнения изменений, является скрытым, так что при фиксации (выполнении операции commit) или аварийном завершении (выполнении операции abort) транзакции база данных всегда остается в согласованном состоянии.
• Isolation (Изоляция). Для каждой транзакции должно создаваться ощущение, что она работает с базой данных в одиночку. Для каждой транзакции являются невидимыми эффекты, производимые над базой данных другими параллельно выполняемыми транзакциями, и эффекты данной транзакции являются невидимыми для других транзакций, пока она не будет зафиксирована.
• Durability (Долговечность). Все эффекты, произведенные над базой данных зафиксированной транзакцией, гарантированно сохраняются в базе данных, даже в случае последующих отказов системы. До фиксации транзакции изменения, выполненные этой транзакцией, не являются долговечными, и не гарантируется их сохранение в случае отказа системы.

Транзакции предоставляют модель программирования для баз данных, где определяется стартовая точка, указываемая командой "transactionBegin", за которой следует последовательность операций над базой данных, завершаемая либо командой "transactionCommit", либо командой "transactionAbort".

Транзакционная модель, поддерживающая все свойства ACID, предоставляет упрощенную среду, в которой у программиста имеется отчетливое понимание того, что следует ожидать от поведения системы.

Управление параллельным доступом

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

В базах данных могут реализовываться различные виды поддержки согласованности и управления параллельным доступом. Для обеспечения согласованности по чтению обычно используются два базовых механизма:

• Гарантированное представление (Guaranteed view) - для всех транзакций гарантируется согласованное представление репозитория объектов, основанное на состоянии базы данных в момент времени начала транзакций. Это характерная особенность базы данных, и ей обладают не все базы данных.
• Блокировки по чтению (Read locks) - программист должен запрашивать блокировки объектов, когда они читаются, чтобы другие пользователи не могли изменять их.

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

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

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

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

• Выигрывает последний (Last in Wins) - "Выигрывает" последняя из одновременно выполняемых транзакций, пишущая данные, в том смысле, что именно ее изменения сохраняются в базе данных, но это может привести к непредвиденным результатам. Например, пусть пользователь A читает значение объекта O и видит значение 3. Затем одновременно работающий пользователь B изменяет значение объекта O на 7 и фиксирует транзакцию. Тем временем, пользователь A добавляет 1 к значению O (которое он ранее прочитал) и сохраняет результирующее значение 4 в объекте O. В результате обновления пользователя B оказываются потерянными. В большинстве приложений этот метод использовать нельзя.
• Оптимистический метод - Доступ к объектам и их обновление производится в частной области, образуемой в ходе выполнения транзакции. До фиксации транзакции требуется выполнить проверку того, что операции этой транзакции согласуются с операциями других транзакций, зафиксированных после ее начала. Если проверка согласованности не удается, фиксация не производится, и все изменения, совершенные при выполнении транзакции, должны быть аннулированы. Обновляющие транзакции являются "оптимистическими" в том смысле, что они не ожидают частого возникновения конфликтов, и в случае неудачи они готовы снова произвести обновления. Этот метод также называют "Выигрывает первый" ("First in Wins"), поскольку вторая попытка зафиксировать объект может не удаться по причине наличия конфликта с уже зафиксированной транзакцией.
• Пессимистический метод - Для предотвращения выполнения операций чтения или обновления другими транзакциями в период выполнения данной транзакции используются блокировки или упорядочивание по временным меткам. Часто применяется двухфазное блокирование, поскольку это подход является простым и позволяет избежать возникновения проблемы каскадных откатов транзакций.

Во многих объектно-ориентированных приложениях оказывается сложно предсказать, какие объекты будут читаться или изменяться, поскольку поведение метода может зависеть от найденного значения. Например, метод может обнаружить, что на складе осталось мало единиц некоторого товара и вызвать метод reorder для его дополнительного заказа. Метод reorder может быть очень простым, но для его выполнения может потребоваться доступ к ряду объектов поставщиков и определение того, кто из них является наилучшим в данной ситуации. Эта непредсказуемость поведения обычно затрудняет разработку приложений с использованием только пессимистических механизмов управления параллельным доступом, поскольку усложняется управление блокировками и возрастает вероятность синхронизационных тупиков. Поэтому в объектно-ориентированных системах более часто используются оптимистические методы управления параллелизмом.

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

В некоторых базах данных может обеспечиваться несколько уровней требований согласованности:

• При полной согласованности требуется, чтобы для всех объектов, прочитанных или измененных транзакцией, не допускалось их обновление параллельно выполняемой транзакцией, которая фиксируется, когда данная транзакция является активной.
• Уровень параллельности может быть повышен (за счет уменьшения числа неудачных фиксаций) путем выполнения проверок только согласованности по записи, но это следует применять только в тех случаях, когда приложение допускает, что производимое им обновление объекта может основываться на данных, которые могут измениться после их прочтения. Такая возможность используется в приложениях потоков работ, подобных тому, которое описано в [2].

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

Гибридная согласованность

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

Поведенческая согласованность

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

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

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

Начальная идея поведенческого параллелизма происходит из исследований управления параллельным доступом для абстрактных типов данных [5], [8], [10] и семантического управления параллельным доступом [9]. В [9] авторы проводят различие между семантикой транзакций и семантикой данных для определения свойств параллельности. С использованием подхода транзакций свойства параллельности определяются в соответствии с семантикой транзакций и данных, которыми они манипулируют. С использованием подхода данных семантика параллельности на абстрактных типах данных может быть определена в соответствии с операциями типа. При интеграции подхода данных к параллельности в объектную базу данных он может обеспечить единообразное, параллельное поведение объектов, являющееся модульным и децентрализованным. Оно является модульным, потому что класс инкапсулирует сложность параллельного поведения, и оно является децентрализованным, потому что каждый экземпляр класса управляет параллельным доступом к содержащимся данным.

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

Для анализа согласованности операций объекта может быть организовано расписание перемежающихся операций одновременно выполняемых транзакций. По определению, из коммутативности операций следует то, что в расписании допустимо любое изменение порядка коммутативных операций. Однако для некоммутативных операций порядок операций в расписании определяет возможный результат. Как отмечалось в [10], множество всех возможных расписаний ограничивается моделью системы хранения. В типичной модели подразумевается система хранения с "обновлениями на месте" ("update-in-place"), в которой для обеспечения согласованности используются блокировки. В отличие от этого, система баз данных может быть основана на модели системы хранения, которая не модифицирует объекты "на месте" [3]. Если не производить обновления в месте основного хранения, то операция чтения в транзакции является повторяемой, обеспечивая "гарантированное представление". При использовании оптимистического управления параллельным доступом, когда транзакция пытается зафиксироваться, система проверяет, что набор прочитанных и записанных ею объектов не конфликтует с объектами, прочитанными и записанными другими транзакциями, которые зафиксировались в данном промежутке времени. В соответствии с [4] это классифицируется как "обратная валидация" ("backward validation ").

Чтобы продемонстрировать, как разные модели систем хранения воздействуют на расписания, рассмотрим следующий пример использования мультимножества, простой коллекции объектов. Предположим, что транзакции T1 и T2 стартуют в одно и то же время при пустом мультимножестве B в базе данных. T1 пытается добавить элемент в B, а T2 - удалить этот элемент. Как отмечается в [5], "когда транзакция фиксируется или аварийно заканчивает свое выполнение, известие об этом событии асинхронно распространяется по системе. Шаги "commit" и "abort" расписания представляют поступление такого известия к объекту". Таким образом, результат параллельного выполнения транзакций зависит от того, зафиксирует ли T1 свое добавление до того, как T2 попытается удалить элемент. Если T1 успеет зафиксироваться, то T2 увидит в B элемент и успешно выполнит удаление. Такое расписание не сможет осуществиться в системе, основанной на гарантированном представлении с использованием оптимистического управления параллельным доступом, потому что операция удаления в T2 всегда будет заканчиваться неудачей, поскольку с точки зрения T2 мультимножество B является пустым.

Разработка классов параллельного обновления

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

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

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

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

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

Семантика счетчиков с параллельным обновлением

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

Можно определить, по крайней мере, три вида счетчиков с разной CU-семантикой. Первый вид - это CuCounter со следующей семантикой параллелизма: транзакции, изменяющие значение счетчика, не конфликтуют с другими транзакциями, которые изменяют или читают значение счетчика. Следовательно, две транзакции могут увеличить счетчик объекта CuCounter и смочь успешно зафиксироваться, или же транзакция, читающая счетчик, может успешно зафиксироваться, несмотря на наличие других транзакций, изменяющих счетчик. Этот CuCounter ориентирован на поддержку таких приложений, как в описанном ранее примере складского приложения.

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

Третий вид счетчика, CuAccount, обеспечивает семантику, аналогичную семантике объекта Account, определенного в [5]. При использовании этого счетчика терпят неудачу все некоммутативные операции. Это означает, что транзакция, читающая значение счета, будет конфликтовать с другой транзакцией, увеличивающей или уменьшающей это значение. Как и при использовании CuPositiveCounter, параллельные операции увеличения и уменьшения преуспевают до тех пор, пока счетчик остается положительным. Этот тип счетчика подходит при моделировании финансовых счетов, когда транзакция, читающая значение счетчика, не имеет права на фиксацию, если параллельная транзакция зафиксировала измененное значение счетчика.

Семантика мультимножеств с параллельным обновлением

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

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

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

Заключительный случай, заслуживающий анализа, проявляется в ситуации, когда несколько транзакций удаляет объекты из CuBag. Как и при добавлении, транзакция, удаляющая объекты из CuBag, не будет конфликтовать с другой транзакцией, которая удаляет другие объекты из CuBag. CuBag достигнет одного и того же состояния независимо от порядка фиксации удалений. Один из случаев, в которых операции удаления не являются коммутативными, возникает тогда, когда две транзакции совместно пытаются удалить больше вхождений некоторого объекта, чем их содержится в CuBag. Например, предположим, что изначально в CuBag содержится четыре вхождения объекта. Одна транзакция пытается удалить три вхождения, а другая - два. Порядок, в котором транзакции пытаются зафиксироваться, определяет то, какая из них окажется успешной. В этом случае для поддержания разумной семантики параллелизма неудачей должна заканчиваться попытка фиксации второй транзакции. В противном случае транзакциям удалось бы успешно удалить большее число вхождений объекта, чем их содержится в CuBag.

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

Семантика словарей с параллельным обновлением

Словарь - это коллекция объектов, доступ к которым производится через явно назначенные ключи или имена. Хэш-словарь - это оптимизированная реализация словаря, в которой для чтения или обновления элемента на основе его ключа используется алгоритм хэширования. Пользователи вставляют или обновляют элемент словаря с использованием метода "put(key, value)". Если данный ключ не присутствует в словаре, добавляется новый элемент. Если ключ уже содержится в словаре, то новое значение заменяет существующее значение с заданным ключом. В словарях также имеются операции для выборки значения с данным ключом и удаления ключа.

Имеются две разновидности словарей с параллельным обновлением с несколько различной семантикой. У одного вида словарей, CuHashDirectory, имеется та же семантика параллелизма, что у словарей в [8], в которых допустимые последовательности операций определяются коммутативностью всех операций чтения и записи. В другом типе словарей, CuHashDictionary, ослабляется требование коммутативности операций чтения и записи одного и того же ключа. Для обоих видов словарей добавление и удаление различных ключей являются коммутативными, так что эти операции логически не конфликтуют. Операции добавления и удаления одного и того же ключа не являются коммутативными внутри одной транзакции, но они коммутативны при выполнении в параллельных транзакциях. Операция удаления того же ключа всегда терпит неудачу, поскольку одна транзакция не видит результатов операции добавления другой транзакции. Следовательно, операции добавления и удаления одного и того же ключа в CuHashDictionary логически не конфликтуют.

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

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

Семантика очередей с параллельным обновлением

Очередь - это коллекция, позволяющая пользователям добавлять и удалять объекты в порядке first-in-first-out (FIFO). Для поддержки абсолютной упорядоченности параллельные транзакции, модифицирующие очередь, должны конфликтовать. Однако, если немного ослабить строгое поведение first-in-first-out, то уровень параллельности может возрасти. Подобной семантикой обладают очередь Weakly FIFO Queue, представленная в [8], и "полуочередь" Semi-Queue, определенная в [10]. Общим свойством этих конструкций является то, что элементы, добавляемые к очереди, обрабатываются "справедливым" образом, т.е. они не будут "застревать" в очереди, а поступят в голову очереди примерно в то же время, что и другие элементы, добавленные успешно зафиксированными параллельными транзакциями.

Независимо от того, является ли очередь абсолютной или нет, операции добавления и удаления не являются коммутативными. Они некоммутативны по той причине, что разные порядки операций приводят к разным результирующим состояниям. Следовательно, для CuQueues коммутативность не может служить основой повышения уровня параллелизма. Вместо этого, для CuQueues определяется следующая семантика параллелизма. Транзакции, добавляющие элементы в очередь, не будут логически конфликтовать с другими транзакциями, добавляющими элементы. Одиночная транзакция, удаляющая объекты из очереди, не будет конфликтовать с другими транзакциями, добавляющими элементы. Логические конфликты действительно возникают, если несколько транзакций пытается выполнить операцию удаления элемента.

Это поведение удаления CuQueue отличается от соответствующего поведения Weakly FIFO Queue Шварца. Основная причина этого отличия кроется в ограничениях используемой системы хранения. В системе, поддерживающей гарантированное представление, несколько параллельно выполняющихся транзакций, которые удаляют элементы из CuQueue, не могут видеть незафиксированное состояние. Поэтому все они будут пытаться удалить один и тот же элемент и столкнутся с конфликтом. Поэтому реализация CuQueue более всего подходит для приложений, в которых имеется много производителей (транзакций, добавляющих элементы в CuQueue) и единственный потребитель (транзакция, удаляющая элементы из CuQueue). Можно построить систему, позволяющую обслуживать двух потребителей путем использования трех CuQueue. Производители сначала добавляют свои элементы в очередь Q1. Затем эти элементы удаляются из Q1 и помещаются либо в Q2, либо в Q3 в зависимости от объема работы или другого критерия обслуживания. Таким образом, отдельные потребители выполняют операции удаления только над одной CuQueue и не испытывают конфликтов.

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

В настоящее время CuQueues используются в многочисленных производственных приложениях. В одном из приложений CuQueues используются для обмена объектами между разъединенными серверами. Это позволяет распределенным базам данных совместно использовать объекты путем помещения объектов в CuQueue другого сервера, не конфликтуя с серверами, делающими то же самое. Каждому серверу приписывается CuQueue, и он потребляет из нее объекты. Сервер может помещать объекты в любое число CuQueue других серверов. В другом приложении клиенты помещают объекты в одну CuQueue, которая используется для сбора данных для генерации отчетов. Генератор отчетов удаляет объекты из CuQueue, когда требуется отчет.

Методы реализации

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

Множества чтения параллельных изменений

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

Журнал Redo

В реализации CU-объектов, даже если возникает конфликт, высокоуровневая семантика может позволить продолжить работу, если имеется возможность гарантировать, что база данных останется в согласованном состоянии. Для порождения согласованного вида базы данных транзакция, испытывающая конфликт, должна интегрировать изменения других транзакций со своими собственными изменениями. Однако повторное проигрывание операций может потерпеть неудачу, если другая транзакция зафиксирует изменение, делающее недействительной одну и повторно выполняемых операций. Если операция CU-объекта не может быть успешно воспроизведена, это связано с действительным конфликтом согласованности, и транзакция оказывается неспособной к фиксации. Это происходит вследствие того, что при обнаружении физического конфликта воспроизводятся только операции, которые изначально были успешно выполнены. Например, предположим, что транзакция Tl пытается удалить последнее вхождение объекта X из CuBag. Может случиться так, что первой свое удаление X зафиксирует другая транзакция T2. Когда Tl пытается зафиксироваться, она испытывает физический конфликт, который старается разрешить. Tl обновляет свое представление CuBag и повторно выполняет операции. Повторная попытка удаления X потерпит неудачу, поскольку X уже не содержится в CuBag, и, следовательно, попытка фиксации провалится. Чтобы обеспечить возможность повторного выполнения операций при обнаружении физического конфликта, можно реализовать журнал redo для фиксации информации об изменения, выполненных над некоторыми CU-объектами. Журнал redo аналогичен "намерениям", описанным в [5]. Однако в дополнение к фиксации изменений CU-объекта журнал redo может также содержать результаты операций чтения. Это делается для поддержки таких CU-объектов, как CuAccount и CuHashDirectory, для которых операции чтения должны быть повторяемыми, поскольку на основе прочитанного значения может быть выполнена сложная операция.

Решения с разделением

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

1. Для операций, осуществляющих доступ к содержимому объекта, корневой объект отвечает за сбор содержимого подкомпонентов для получения агрегатного содержимого.
2. Для операций, обновляющих содержимое объекта, корневой объект определяет, какие подкомпоненты реально модифицируются.

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

Одним из примеров разделения является реализация CuHashDictionary. В этом случае сама хэш-таблица обеспечивает естественное разделение данных. Каждый элемент таблицы представляет собой кластерный бакет, и только для операций над одним и тем же кластерным бакетом требуется анализ их CU-поведения.

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

Третий пример разделения можно найти в реализации CuQueue. Обычно для очереди поддерживаются указатели на голову и хвост. Рассмотрим взамен этого CuQueue, которая содержит ссылки на два отдельных объекта, в одним из которых инкапсулируется ссылка на голову, а в другом - на хвост. При использовании этой структуры производители обновляют только промежуточный объект-голову, а потребители - только промежуточный объект-хвост. Таким образом, одиночные производитель и потребитель могут работать с очередью без каких-либо конфликтов "запись-запись". Если с CuQueue параллельно работает несколько производителей, то при возникновении конфликта "запись-запись" над промежуточным объектом для разрешения конфликта можно повторно выполнить операцию добавления элемента и сохранить CuQueue в согласованном состоянии.

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

Использование CU-объектов позволяет разработчикам приложений создавать приложения с параллельным доступом без потребности написания специального кода для избегания конфликтов согласованности. Хотя функциональная семантика CU-объектов легко понимается и соответствует поведению соответствующих традиционных конструкций, разработчики должны понять семантику параллельности CU-объектов, прежде чем слепо применять их во всех ситуациях. Иногда конфликты, возникающие при параллельной работе, являются желательными, и до использования CU-объектов программистам следует тщательно проанализировать требования к своим приложениям.

Еще одним соображением по поводу использования CU-объектов являются соответствующие затраты времени и памяти. В большинстве случаев использование CU-объекта вовлекает создание и поддержку дополнительных объектов, остающихся невидимыми для пользователей. При реализации CU-объекта возникает несколько объектов-подкомпонентов. Эти подкомпоненты могут занимать память, объем которой пропорционален максимальному числу пользователей. Кроме того, на поддержку подкомпонентов тратится время при модификации CU-объекта. Если используется журнал redo, то создаются дополнительные временные объекты для поддержки истории операций над CU-объектом.

Несмотря на затраты памяти и времени, преимуществом CU-объектов является то, что они допускают более высокий уровень параллелизма, чем оптимистический и пессимистический подходы. В некоторых случаях использование CU-объектов позволило повысить пропускную способность на 14-37% без увеличения загрузки ЦП системы.

Заключение

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

• Гарантированные представления - согласованные чтения
• Оптимистическое управление параллелизмом - обратная валидация
• Поддержка нескольких подходов к параллелизму в основной базе данных
• Активные базы данных - поддержка выполнения операций объектов

В некоторых приложениях для комбинирования оптимистического и пессимистического механизмов управления параллелизмом с целью повышения общего уровня параллелизма можно использовать паттерн "сторожевых объектов".

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

Более подробную информацию об объектно-ориентированной базе данных, в которой реализован ряд классов с параллельным обновлением, описанных в этой статье, см. на http://www.facetsodb.com.

Литература

[1]	Almarode, J. and Bretl, R.: "Reduced-Conflict Objects." JOOP 10 (8): 40-44 (1998)
[2]	Beck, B., and Hartley, S.: "Persistent Storage for a Workflow Tool Implemented in Smalltalk:", Conference on Object Oriented Programming Systems Languages and Applications, ACM Press, 1994
[3]	Bretl, B., et al.: "The GemStone Data Management System" in Object-Oriented Concepts, Databases, and Applications, edited by Kim and Lochovsky, ACM Press, 1989.
[4]	Harder, T.: "Observations on Optimistic Concurrency Control Schemes", Information Systems, Vol. 9, June 1984.
[5]	Herlihy, M.: "Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types", ACM Transactions on Database Systems, Vol. 15, No.1, March 1990."Indexed Associative Access" in GemStone Programming Guide, Chapter 9, Servio Corporation, 1994, http://www.cs.brown.edu/~mph/Herlihy90a/p96-herlihy.pdf
[6]	Maier, D. and Stein, J.: "Development and Implementation of an Object-Oriented DBMS" in Research Directions in Object-Oriented Programming, edited by Shriver and Wegner, MIT Press, 1987.
[7]	Maier, D. and Stein, J.: "Indexing in an Object-Oriented DBMS", Proceedings International Workshop on Object-Oriented Database Systems, September 1986.
[8]	Schwarz, P. and Spector, A.: "Synchronizing Shared Abstract Types", ACM Transactions on Computing Systems, Vol. 13, No.1, August 1984.
[9]	Skarra, A. and Zdonik, S.: "Concurrency Control and Object-Oriented Databases" in Object-Oriented Concepts, Databases, and Applications, edited by Kim and Lochovsky, ACM Press, 1989.
[10]	Weihl, W. E.: "Local Atomicity Properties: Modular Concurrency Control for Abstract Data Types", ACM Transactions on Programming Languages and Systems, Vol. 11. No.2, April 1989.