Семантика очередей с параллельным обновлением
Очередь - это коллекция, позволяющая пользователям добавлять и удалять объекты в порядке first-in-first-out (FIFO). Для поддержки абсолютной упорядоченности параллельные транзакции, модифицирующие очередь, должны конфликтовать. Однако, если немного ослабить строгое поведение first-in-first-out, то уровень параллельности может возрасти. Подобной семантикой обладают очередь Weakly FIFO Queue, представленная в [], и "полуочередь" Semi-Queue, определенная в []. Общим свойством этих конструкций является то, что элементы, добавляемые к очереди, обрабатываются "справедливым" образом, т.е. они не будут "застревать" в очереди, а поступят в голову очереди примерно в то же время, что и другие элементы, добавленные успешно зафиксированными параллельными транзакциями.
Независимо от того, является ли очередь абсолютной или нет, операции добавления и удаления не являются коммутативными. Они некоммутативны по той причине, что разные порядки операций приводят к разным результирующим состояниям. Следовательно, для CuQueues коммутативность не может служить основой повышения уровня параллелизма. Вместо этого, для CuQueues определяется следующая семантика параллелизма. Транзакции, добавляющие элементы в очередь, не будут логически конфликтовать с другими транзакциями, добавляющими элементы. Одиночная транзакция, удаляющая объекты из очереди, не будет конфликтовать с другими транзакциями, добавляющими элементы. Логические конфликты действительно возникают, если несколько транзакций пытается выполнить операцию удаления элемента.
Это поведение удаления CuQueue отличается от соответствующего поведения Weakly FIFO Queue Шварца. Основная причина этого отличия кроется в ограничениях используемой системы хранения. В системе, поддерживающей гарантированное представление, несколько параллельно выполняющихся транзакций, которые удаляют элементы из CuQueue, не могут видеть незафиксированное состояние. Поэтому все они будут пытаться удалить один и тот же элемент и столкнутся с конфликтом.
Поэтому реализация CuQueue более всего подходит для приложений, в которых имеется много производителей (транзакций, добавляющих элементы в CuQueue) и единственный потребитель (транзакция, удаляющая элементы из CuQueue). Можно построить систему, позволяющую обслуживать двух потребителей путем использования трех CuQueue. Производители сначала добавляют свои элементы в очередь Q1. Затем эти элементы удаляются из Q1 и помещаются либо в Q2, либо в Q3 в зависимости от объема работы или другого критерия обслуживания. Таким образом, отдельные потребители выполняют операции удаления только над одной CuQueue и не испытывают конфликтов.
Для поддержания порядка, в котором объекты добавляются в очередь, без ощущения конфликтов в каждый элемент очереди включается временная метка. Это позволяет транзакции, выполняющей удаление из очереди, выбирать элемент с наиболее старой временной меткой. В системах, основанных на использовании гарантированных представлений, транзакции могут видеть только зафиксированные результаты, поэтому транзакция может удалить элемент, зафиксированный прежде того элемента, который в действительности добавлялся в очередь в более раннее время.
В настоящее время CuQueues используются в многочисленных производственных приложениях. В одном из приложений CuQueues используются для обмена объектами между разъединенными серверами. Это позволяет распределенным базам данных совместно использовать объекты путем помещения объектов в CuQueue другого сервера, не конфликтуя с серверами, делающими то же самое. Каждому серверу приписывается CuQueue, и он потребляет из нее объекты. Сервер может помещать объекты в любое число CuQueue других серверов. В другом приложении клиенты помещают объекты в одну CuQueue, которая используется для сбора данных для генерации отчетов. Генератор отчетов удаляет объекты из CuQueue, когда требуется отчет.
