Оригинал: Achieving High Concurrency In Object Oriented Databases
Роберт Бретл (Robert Bretl)
Перевод - Сергей Кузнецов
Бретл, главным образом, является инженером и разработчиком. За свою жизнь он был соавтором всего нескольких статей (к наиболее известным относятся "The GemStone Data Management System", "Persistent Java Objects in 3 Tier Architectures", "Reduced-Conflict Objects" и "Achieving High Concurrency in Object Oriented Databases"). Статья, перевод которой предлагается вашему вниманию, чуть ли не первая, написанная Бретлом в одиночку.
В последние годы мне не попадались статьи, посвященные специфическим методам, которые используются в объектно-ориентированных базах данных. Казалось, что в этой, не слишком процветающей в последние годы области давно все ясно и понятно. Тем интереснее узнать из первых рук ведущего разработчика о хитростях, к которым приходится прибегать при управлении транзакциями в ООСУБД, чтобы достигать хорошего уровня параллельности (кстати, в переводе используется термин "параллельность" как эквивалент англоязычного термина "concurrency", что не совсем точно; к сожалению, лучшего варианта я не знаю).
Прямо замечу, что представляемая вашему вниманию статья не является ровной. В некоторых местах автор недостаточно понятен, иногда хотелось бы видеть большее число обоснований, более точных технических описаний и т.д. Но мне кажется, что все основные идеи понять можно. Если же вы знакомы с методами управления транзакциями в реляционных СУБД, то очень полезно сравнить подходы и подумать, из-за чего в ООСУБД приходится прибегать к таких хитростям.
К сожалению, мне не удалось найти в Internet (в открытом доступе) тексты публикаций, приводимых в списке литературы. Вернее, удалось найти текст только одной публикации, ссылку на который мы публикуем, и рекомендуем ей воспользоваться всем тем, кому интересны объектно-ориентированные базы данных.
Объектные базы данных очень хорошо подходят для хранения сложных моделей данных, но обычно разработчику приложения приходится решать, как масштабировать приложение, чтобы оно эффективно поддерживало одновременную работу многих пользователей. Назначение этой статьи состоит в том, чтобы проанализировать различные методы, которые можно использовать в объектно-ориентированных базах данных для достижения высокого уровня параллельности доступа.
Сначала в статье предоставляется предварительная информация о транзакциях и нескольких методах управления параллельным доступом, затем анализируются различия между физической и логической согласованностью. Наконец, вводится несколько специализированных классов-контейнеров, чтобы показать, как можно реализовать логическую (поведенческую) согласованность, а также то, как можно использовать эти классы для совершенствования параллелизма доступа и упрощения разработки приложений.
Транзакции предоставляют модель программирования для баз данных, где определяется стартовая точка, указываемая командой "transactionBegin", за которой следует последовательность операций над базой данных, завершаемая либо командой "transactionCommit", либо командой "transactionAbort".
Транзакционная модель, поддерживающая все свойства ACID, предоставляет упрощенную среду, в которой у программиста имеется отчетливое понимание того, что следует ожидать от поведения системы.
В базах данных могут реализовываться различные виды поддержки согласованности и управления параллельным доступом. Для обеспечения согласованности по чтению обычно используются два базовых механизма:
Если для приложения требуется согласованное представление для некоторых только читающих транзакций, например, генерирующих отчеты или собирающих данные для их представления на дисплее клиента, то обычно лучше подходит база данных, поддерживающая гарантированное представление, потому что:
Если приложение пишется таким образом, что все операции обновления или записи в одновременно выполняющихся транзакциях производятся над разъединенными множествами объектов, то конфликты не существуют, и транзакции могут быть успешно зафиксированы без какого-либо дополнительного управления параллельным доступов, снижающего производительность. Однако так бывает редко, и в большинстве приложений должна использоваться какая-либо форма управления параллельным доступом, обеспечивающая успешную фиксацию транзакций.
Для управления согласованность по обновлению в базе данных имеются три основных метода:
Во многих объектно-ориентированных приложениях оказывается сложно предсказать, какие объекты будут читаться или изменяться, поскольку поведение метода может зависеть от найденного значения. Например, метод может обнаружить, что на складе осталось мало единиц некоторого товара и вызвать метод reorder для его дополнительного заказа. Метод reorder может быть очень простым, но для его выполнения может потребоваться доступ к ряду объектов поставщиков и определение того, кто из них является наилучшим в данной ситуации. Эта непредсказуемость поведения обычно затрудняет разработку приложений с использованием только пессимистических механизмов управления параллельным доступом, поскольку усложняется управление блокировками и возрастает вероятность синхронизационных тупиков. Поэтому в объектно-ориентированных системах более часто используются оптимистические методы управления параллелизмом.
Одним из ключевых аспектов оптимистического подхода является обнаружение конфликтов. Нарушения согласованности обычно подразделяются на нарушения по чтению и нарушения по записи. Согласованность по чтению гарантирует, что данные, читаемые при выполнении данной, не изменяются другой транзакцией, пока данная транзакция является активной (в промежутке времени от начала транзакции до ее фиксации). Это называется конфликтами Read/Write, поскольку чтения текущей транзакции конфликтуют с записями других транзакций. Согласованность по записи гарантирует, что объект, измененный при выполнении данной транзакции, не изменяется другой транзакцией, пока данная транзакция является активной. Эти конфликты называются конфликтами Write/Write, поскольку записи текущей транзакции конфликтуют с записями других транзакций.
В некоторых базах данных может обеспечиваться несколько уровней требований согласованности:
Также важно учитывать гранулярность механизма управления параллельным доступом. Некоторые системы стремятся оптимизировать проверки путем выполнения их на элементах, гранулированных должным образом, например, на страницах, в которых располагаются объекты. Это может повысить производительность в случаях, когда объекты кластеризуются таким образом, что объекты, которые могли бы привести к конфликту, находятся в разных страницах. Хотя этот подход и возможен, часто он оказывается очень неуклюжим, и в общем случае "мелкозернистая" проверка согласованности на индивидуальных объектах позволяет поддерживать более высокий уровень параллельности выполнения операций обновления.
В этих приложениях данные обычно представляются как простой тип, для которого единственными допустимыми операциями являются чтение и запись. С этой точки зрения, данные существуют как атомарные сущности, независимо от того контекста, в котором они используются, и низкоуровневые операции либо читают, либо записывают данные. Аналогично, механизм управления параллельным доступом отслеживает чтения и записи одновременно выполняемых транзакций для определения того, не возникает ли конфликт.
В объектных базах данных может обеспечиваться механизм, отличный от проверки согласованности по чтению/записи, поскольку манипулирование объектами производится на более высоком семантическом уровне, чем у данных, которые в них инкапсулируются. Операции (поведение) объектов может быть гораздо более сложным, чем простые чтения и записи. За счет тщательного определения семантики поведения объектов и понимания видимости побочных эффектов во многих ситуациях конфликтов согласованности можно избежать. Кроме того, при возникновении конфликта для разрешения низкоуровневого конфликта по чтению/записи можно использовать высокоуровневое поведение объектов, наряду с поддержкой согласованности объектов. Объекты, поддерживающие поведенческую параллельность, могут повысить пропускную способность транзакций за счет увеличения числа операций, одновременно выполняемых над базой данных. Путем построения инструментального набора повторно используемых объектных классов, поддерживающих операции параллельного обновления, можно серьезно упростить разработку приложений с высоким уровнем параллелизма.
Начальная идея поведенческого параллелизма происходит из исследований управления параллельным доступом для абстрактных типов данных [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 является пустым.
Чтобы можно было расширить механизм распознавания физических конфликтов с целью реализации классов параллельных обновлений, основная объектная база данных должна быть активной, т.е. она должна поддерживать выполнение операций объектов, чтобы можно было раскрывать высокоуровневую семантику при попытках фиксации объектов в базе данных. Пассивные объектные базы данных, в которых поддерживаются только операции запросов и обновления над основным хранилищем объектов, было бы трудно расширить для обеспечения поведенческого параллелизма, потому что они не могут выполнять методы, требуемые для реализации поведенческой семантики.
При разработке CU-классов важно использовать неблокирующий подход, потому что блокировка объектов навязывает упорядочивание транзакций и снижает уровень доступности объектов, что приводит к уменьшению пропускной способности. В результате, для достижения оптимальной производительности требуется оптимистический механизм управления параллельным доступом. Общий подход к разработке CU-классов состоит в том, чтобы разработать такую физическую структуру объекта, чтобы между операциями реже возникали физические конфликты, и разрешать физические конфликты, выявляемые во время проверок согласованности фиксации, путем использования высокоуровневой семантики для слияния изменений от текущей транзакции с изменениями, ранее зафиксированными другими параллельно выполняемыми транзакциями.
Еще одним важным вопросом по поводу CU-классов является то, применимы ли они в приложениях, в которых конфликты чтения-записи считаются важными. Для приложений, в которых конфликты чтения-записи являются важными, должны потерпеть неудачу все некоммутативные операции, в то время как в приложениях, в которых конфликты чтения-записи могут допускаться без потери согласованности, терпят неудачу только некоммутативные операции записи, и конфликты чтения-записи могут игнорироваться. Например, в складском приложении может потребоваться отслеживать число изделий в складской ячейке. Некоторые транзакции выполняют операции добавления изделий в складскую ячейку, когда изделия получаются от производителя и сохраняются на складе. Другие транзакции удаляют изделия из складских ячеек, когда они заказываются розничными торговцами и уходят со склада. Приложение, которое поддерживает число изделий в складской ячейке, характеризуется большим числом операций небольшого уменьшения и небольшим числом операций крупного увеличения в течение каждого дня, а также единственной операцией чтения для определения того, нужно ли приобретать дополнительные изделия. Для операции чтения не требуется предотвращение параллельной модификации, поскольку гарантированное представление обеспечит получение оставшегося числа изделий, достаточно точного для целей закупки. В этом случае игнорирование конфликтов чтения-записи предоставляет преимущество для производительности, поскольку большее число расписаний считается допустимым. Кроме того, реализация CU-классов с использованием этой семантики является более эффективным, поскольку требуется разрешать меньшее число физических конфликтов.
В следующих разделах определяется несколько CU-классов. Для каждого CU-класса определяются его функциональная семантика, а также вид приложений, на поддержку которых рассчитан этот класс. Семантика параллельности каждого CU-класса описывается в виде последовательности операций, которые являются или не являются коммутативными. Наконец, приводится пример приложения, для которого уместно использование определенного CU-класса.
Можно определить, по крайней мере, три вида счетчиков с разной CU-семантикой. Первый вид - это CuCounter со следующей семантикой параллелизма: транзакции, изменяющие значение счетчика, не конфликтуют с другими транзакциями, которые изменяют или читают значение счетчика. Следовательно, две транзакции могут увеличить счетчик объекта CuCounter и смочь успешно зафиксироваться, или же транзакция, читающая счетчик, может успешно зафиксироваться, несмотря на наличие других транзакций, изменяющих счетчик. Этот CuCounter ориентирован на поддержку таких приложений, как в описанном ранее примере складского приложения.
Второй вид счетчика - это CuPositiveCounter. При использовании этого счетчика параллельные транзакции могут изменять счетчик без конфликтов, пока в результате операций модификации значение счетчика не становится отрицательным. Если транзакция уменьшает счетчик объекта CuPositiveCounter такого, что значение его счетчика стало бы после этого отрицательным, как только стали бы видимыми зафиксированные изменения другой транзакции, то фиксация данной транзакции не разрешается. При работе с CuPositiveCounter читающие и пишущие транзакции не конфликтуют.
Третий вид счетчика, CuAccount, обеспечивает семантику, аналогичную семантике объекта Account, определенного в [5]. При использовании этого счетчика терпят неудачу все некоммутативные операции. Это означает, что транзакция, читающая значение счета, будет конфликтовать с другой транзакцией, увеличивающей или уменьшающей это значение. Как и при использовании CuPositiveCounter, параллельные операции увеличения и уменьшения преуспевают до тех пор, пока счетчик остается положительным. Этот тип счетчика подходит при моделировании финансовых счетов, когда транзакция, читающая значение счетчика, не имеет права на фиксацию, если параллельная транзакция зафиксировала измененное значение счетчика.
Для некоторых приложений операции добавления и удаления объектов из CuBag также являются коммутативными. Если некоторая транзакция добавляет в CuBag один объект, а другая транзакция удаляет из CuBag другой объект, то порядок фиксации изменений этими транзакциями не имеет значения. Следовательно, ни одна из транзакций не столкнется с конфликтом. Транзакции, удаляющие объекты из CuBag, не конфликтуют с транзакциями, добавляющими объекты в CuBag, если удаляемые объекты разъединены с добавляемыми объектами.
Интересный случай возникает при анализе добавления и удаления единственного вхождения объекта в CuBag. Внутри одной транзакции операции добавления и удаления одного и того же объекта не являются коммутативными в соответствии с семантикой операции удаления. Например, если удаление происходит после добавления, то операция выполняется успешно. Если же удаление выполняется до добавления объекта, то операция удаления терпит неудачу, поскольку объект не присутствует в CuBag. Однако когда эти операции выполняются в параллельных транзакциях, они являются коммутативными. Эти операции являются коммутативными, поскольку операция удаления всегда терпит неудачу, независимо от порядка, в котором транзакции пытаются фиксироваться. Так происходит из-за того, что добавление объекта является невидимым для транзакции, пытающейся его удалить.
Заключительный случай, заслуживающий анализа, проявляется в ситуации, когда несколько транзакций удаляет объекты из CuBag. Как и при добавлении, транзакция, удаляющая объекты из CuBag, не будет конфликтовать с другой транзакцией, которая удаляет другие объекты из CuBag. CuBag достигнет одного и того же состояния независимо от порядка фиксации удалений. Один из случаев, в которых операции удаления не являются коммутативными, возникает тогда, когда две транзакции совместно пытаются удалить больше вхождений некоторого объекта, чем их содержится в CuBag. Например, предположим, что изначально в CuBag содержится четыре вхождения объекта. Одна транзакция пытается удалить три вхождения, а другая - два. Порядок, в котором транзакции пытаются зафиксироваться, определяет то, какая из них окажется успешной. В этом случае для поддержания разумной семантики параллелизма неудачей должна заканчиваться попытка фиксации второй транзакции. В противном случае транзакциям удалось бы успешно удалить большее число вхождений объекта, чем их содержится в CuBag.
CuBag ориентированы на поддержку приложений, в которых несколько транзакций пишет (добавляют или удаляют объекты) в мультимножество, а параллельным читающим транзакциям не запрещается фиксация из-за параллельно производимых изменений мультимножества. Например, приложениям может понадобиться сохранять коллекцию всех экземпляров некоторого класса. Сохранение коллекции всех экземпляров обычно делается путем определения переменной класса, или статического поля, в котором сохраняется коллекция объектов, и экземпляры добавляются к коллекции при их создании. В этой ситуации CuBag полезны для предотвращения конфликтов между несколькими создателями экземпляров. Другим примером является приложение, собирающее данные о финансовых операциях для их статистической обработки в конце дня. В этом сценарии несколько пользователей может добавлять свои записи в CuBag, не испытывая конфликтов.
Имеются две разновидности словарей с параллельным обновлением с несколько различной семантикой. У одного вида словарей, CuHashDirectory, имеется та же семантика параллелизма, что у словарей в [8], в которых допустимые последовательности операций определяются коммутативностью всех операций чтения и записи. В другом типе словарей, CuHashDictionary, ослабляется требование коммутативности операций чтения и записи одного и того же ключа. Для обоих видов словарей добавление и удаление различных ключей являются коммутативными, так что эти операции логически не конфликтуют. Операции добавления и удаления одного и того же ключа не являются коммутативными внутри одной транзакции, но они коммутативны при выполнении в параллельных транзакциях. Операция удаления того же ключа всегда терпит неудачу, поскольку одна транзакция не видит результатов операции добавления другой транзакции. Следовательно, операции добавления и удаления одного и того же ключа в CuHashDictionary логически не конфликтуют.
Для обоих видов словарей параллельные добавления одного и того же ключа не являются коммутативными. Поэтому, если две транзакции добавляют элемент с одним и тем же ключом, то попытка фиксации первой транзакции закончится успешно, а вторая испытает логический конфликт. Аналогично, коммутативными не являются параллельные удаления одного и того же ключа, так что одна из транзакций, пытающаяся выполнить операцию удаления, будет испытывать конфликт.
При поддержке такой семантики CuHashDictionary (или CuHashMap) подходит для приложений, для которых конфликты чтения-записи не являются существенными. Например, CuHashDictionary можно использовать как совместно используемое пространство имен, когда транзакции помещают объекты в словарь, чтобы сделать их видимыми для других транзакций. В приложениях, в которых пользователи рассчитывают на добавление в словарь различных элементов и не желают конфликтовать с теми, кто производит выборку из словаря, применение CuHashDictionary может повысить пропускную способность. CuHashDictionary подходит для приложений, в которых транзакция не должна успешно завершаться, если прочитанное по ключу значение модифицировано другой зафиксированной транзакцией.
Независимо от того, является ли очередь абсолютной или нет, операции добавления и удаления не являются коммутативными. Они некоммутативны по той причине, что разные порядки операций приводят к разным результирующим состояниям. Следовательно, для CuQueues коммутативность не может служить основой повышения уровня параллелизма. Вместо этого, для CuQueues определяется следующая семантика параллелизма. Транзакции, добавляющие элементы в очередь, не будут логически конфликтовать с другими транзакциями, добавляющими элементы. Одиночная транзакция, удаляющая объекты из очереди, не будет конфликтовать с другими транзакциями, добавляющими элементы. Логические конфликты действительно возникают, если несколько транзакций пытается выполнить операцию удаления элемента.
Это поведение удаления CuQueue отличается от соответствующего поведения Weakly FIFO Queue Шварца. Основная причина этого отличия кроется в ограничениях используемой системы хранения. В системе, поддерживающей гарантированное представление, несколько параллельно выполняющихся транзакций, которые удаляют элементы из CuQueue, не могут видеть незафиксированное состояние. Поэтому все они будут пытаться удалить один и тот же элемент и столкнутся с конфликтом. Поэтому реализация CuQueue более всего подходит для приложений, в которых имеется много производителей (транзакций, добавляющих элементы в CuQueue) и единственный потребитель (транзакция, удаляющая элементы из CuQueue). Можно построить систему, позволяющую обслуживать двух потребителей путем использования трех CuQueue. Производители сначала добавляют свои элементы в очередь Q1. Затем эти элементы удаляются из Q1 и помещаются либо в Q2, либо в Q3 в зависимости от объема работы или другого критерия обслуживания. Таким образом, отдельные потребители выполняют операции удаления только над одной CuQueue и не испытывают конфликтов.
Для поддержания порядка, в котором объекты добавляются в очередь, без ощущения конфликтов в каждый элемент очереди включается временная метка. Это позволяет транзакции, выполняющей удаление из очереди, выбирать элемент с наиболее старой временной меткой. В системах, основанных на использовании гарантированных представлений, транзакции могут видеть только зафиксированные результаты, поэтому транзакция может удалить элемент, зафиксированный прежде того элемента, который в действительности добавлялся в очередь в более раннее время.
В настоящее время CuQueues используются в многочисленных производственных приложениях. В одном из приложений CuQueues используются для обмена объектами между разъединенными серверами. Это позволяет распределенным базам данных совместно использовать объекты путем помещения объектов в CuQueue другого сервера, не конфликтуя с серверами, делающими то же самое. Каждому серверу приписывается CuQueue, и он потребляет из нее объекты. Сервер может помещать объекты в любое число CuQueue других серверов. В другом приложении клиенты помещают объекты в одну CuQueue, которая используется для сбора данных для генерации отчетов. Генератор отчетов удаляет объекты из CuQueue, когда требуется отчет.
При использовании этого метода вероятность параллельного доступа уменьшается путем разработки такого критерия выбора подкомпонентов, при котором становится маловероятно, что две параллельные транзакции будут модифицировать один и тот же подкомпонент.
Одним из примеров разделения является реализация 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. |
По материалам портала CIT FORUM