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