Классика баз данных - статьи




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


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

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

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


Содержание  Назад  Вперед