Семантика словарей с параллельным обновлением
Словарь - это коллекция объектов, доступ к которым производится через явно назначенные ключи или имена. Хэш-словарь - это оптимизированная реализация словаря, в которой для чтения или обновления элемента на основе его ключа используется алгоритм хэширования. Пользователи вставляют или обновляют элемент словаря с использованием метода "put(key, value)". Если данный ключ не присутствует в словаре, добавляется новый элемент. Если ключ уже содержится в словаре, то новое значение заменяет существующее значение с заданным ключом. В словарях также имеются операции для выборки значения с данным ключом и удаления ключа.
Имеются две разновидности словарей с параллельным обновлением с несколько различной семантикой. У одного вида словарей, CuHashDirectory, имеется та же семантика параллелизма, что у словарей в [], в которых допустимые последовательности операций определяются коммутативностью всех операций чтения и записи. В другом типе словарей, CuHashDictionary, ослабляется требование коммутативности операций чтения и записи одного и того же ключа. Для обоих видов словарей добавление и удаление различных ключей являются коммутативными, так что эти операции логически не конфликтуют. Операции добавления и удаления одного и того же ключа не являются коммутативными внутри одной транзакции, но они коммутативны при выполнении в параллельных транзакциях. Операция удаления того же ключа всегда терпит неудачу, поскольку одна транзакция не видит результатов операции добавления другой транзакции. Следовательно, операции добавления и удаления одного и того же ключа в CuHashDictionary логически не конфликтуют.
Для обоих видов словарей параллельные добавления одного и того же ключа не являются коммутативными. Поэтому, если две транзакции добавляют элемент с одним и тем же ключом, то попытка фиксации первой транзакции закончится успешно, а вторая испытает логический конфликт. Аналогично, коммутативными не являются параллельные удаления одного и того же ключа, так что одна из транзакций, пытающаяся выполнить операцию удаления, будет испытывать конфликт.
При поддержке такой семантики CuHashDictionary (или CuHashMap) подходит для приложений, для которых конфликты чтения-записи не являются существенными. Например, CuHashDictionary можно использовать как совместно используемое пространство имен, когда транзакции помещают объекты в словарь, чтобы сделать их видимыми для других транзакций. В приложениях, в которых пользователи рассчитывают на добавление в словарь различных элементов и не желают конфликтовать с теми, кто производит выборку из словаря, применение CuHashDictionary может повысить пропускную способность. CuHashDictionary подходит для приложений, в которых транзакция не должна успешно завершаться, если прочитанное по ключу значение модифицировано другой зафиксированной транзакцией.
