Кому нужна линеаризуемость?

Я читал о различиях между сериализуемостью и линеаризуемостью , которые являются критериями согласованности для реплицируемых систем, таких как реплицируемые базы данных. Однако я не знаю, в каких случаях потребуется линеаризуемость, даже если она сильнее, чем сериализуемость.

Не могли бы вы придумать сценарии, где такое сильное свойство действительно было бы необходимо?

Рассмотрим конструкцию параллельных структур данных без ожидания (или без блокировки, что является более слабым). В этом сценарии, как правило, требуется линеаризуемость, хотя в некоторых случаях производительность и масштабируемость могут быть улучшены путем удовлетворения более слабого условия корректности. Полезна ли реализация, удовлетворяющая такому слабому условию, как правило, зависит от приложения. Напротив, линеаризуемая реализация всегда применима, потому что дизайнеры могут рассматривать ее как атомарную.

Более того, линеаризуемость является неблокирующим свойством: полная операция (определенная для всех состояний объекта) никогда не требуется для блокировки. Вместо этого Serializability не является неблокирующим свойством. Поэтому для повышения степени параллелизма разработчики параллельных структур данных всегда полагаются на линеаризуемость.

За последние 15 лет я перечитывал Херлихи и Винг много раз. Это очень трудно читать. И это прискорбно, потому что, хотя есть некоторые тонкости по краям, основная идея на самом деле вполне разумна.

Вкратце: линеаризуемость подобна сериализуемости, но с дополнительным требованием, чтобы сериализация учитывала дополнительные ограничения порядка между транзакциями. Цель состоит в том, чтобы позволить вам строго рассуждать об отдельной атомарной структуре данных, а не рассуждать обо всей системе сразу.

Также легко добиться линеаризации: просто свяжите мьютекс с объектом, который вы хотите линеаризовать. Каждая транзакция в этом объекте начинается с блокировки мьютекса и заканчивается разблокировкой мьютекса.

Вот определения, которые я буду использовать:

Система является сериализуемой, если задан набор транзакций над набором данных, любой результат выполнения транзакций такой же, как если бы транзакции были выполнены в некотором последовательном порядке, а операции внутри каждой транзакции содержатся в их транзакции в заказе. указывается кодом транзакции.

Сериализуемость не допускает появления чередования операций между различными транзакциями и требует, чтобы выбранный порядок транзакций удовлетворял причинности (если транзакция A записывает значение x, а транзакция B считывает значение x, записанное A, тогда транзакция A должна предшествовать транзакции B в выбранный серийный заказ.) Но он ничего не говорит о каких-либо других ограничений на порядок транзакций (в частности, он ничего не говорит о процессах и порядке, в котором процессы воспринимают события).

Есть еще одна связанная идея, которая добавляет ограничения относительно порядка, в котором процессы выполняют операции (но не говорит о транзакциях только отдельных операций чтения / записи):

Система является последовательной последовательностью, если результат любого выполнения такой же, как если бы операции всех процессов были выполнены в некотором последовательном порядке, и операции каждого отдельного процесса появляются в этой последовательности в порядке, указанном его программой. ( Лампорт, «Как создать многопроцессорный компьютер, который правильно выполняет многопроцессорные программы», IEEE T Comp 28: 9 (690-691), 1979 ).

В определении последовательной согласованности подразумевается, что мы принимаем только последовательные порядки, когда для каждой области памяти (объекта) индуцированный последовательный порядок операций подчиняется правилу, согласно которому значение, возвращаемое каждой операцией чтения в расположение, xдолжно быть тем же значением, которое было записано непосредственно предшествующая операция записи в местоположение xв последовательном порядке.

Линеаризуемость имеет благие намерения: (а) объединить понятие транзакций (от сериализации) с понятием, что процессы ожидают завершения операций, которые они выдают, в порядке (от последовательной согласованности) и (б) сужения критериев корректности, чтобы говорить о каждом объект в изоляции, а не заставлять вас рассуждать о системе в целом. (Я хотел бы сказать, что реализация моего объекта является правильной даже в системе, где есть другие объекты, которые не являются линеаризуемыми.) Я полагаю, что Херлихи и Винг, возможно, пытались строго определить монитор .

Часть (а) является «простой»: последовательное требование, подобное согласованности, должно заключаться в том, чтобы транзакции с объектом, выданным каждым процессом, появлялись в результирующей последовательности в порядке, указанном программой. Похожим на сериализацию требованием было бы, чтобы все транзакции на объекте были взаимоисключающими (могут быть сериализованы).

Сложность проистекает из цели (б) (способность говорить о каждом объекте независимо от всех других).

В системе с несколькими объектами возможно, что операции над объектом B накладывают ограничения на порядок, в котором мы считаем, что операции были вызваны на объекте A. Если мы смотрим на всю историю системы, то мы будем ограничены определенными последовательными порядками, и нужно будет отвергнуть других. Но мы хотели критерии корректности, которые мы могли бы использовать изолированно (рассуждая о том, что происходит с объектом А, не обращаясь к истории глобальной системы).

Например: предположим, что я пытаюсь спорить о правильности объекта A, который является очередью, предположим, что объект B является местом в памяти, и предположим, что у меня есть следующие истории выполнения: Поток 1: A.enqueue (x), A. dequeue () (возвращает y). Поток 2: A.enqueue (y), A.dequeue () (возвращает x). Существует ли чередование событий, которое позволило бы правильно реализовать эту очередь? Да:

Thread 1                           Thread 2
A.enqueue(x)                       ...
...                                A.enqueue(y)
...                                A.dequeue() (returns x)
A.dequeue(y) (returns y)           ...

Но что теперь, если история ( включая объект B ): B начинается со значения 0. Поток 1: A.enqueue (x), A.dequeue () (возвращает y), B.write (1). Поток 2: B.read () (возвращает 1) A.enqueue (y), A.dequeue () (возвращает x).

Thread 1                           Thread 2
A.enqueue(x)                       ...
A.dequeue() (returns y)            ...                       (uh oh!)
B.write(1)                         ...
...                                B.read() (returns 1)
...                                A.enqueue(y)
...                                A.dequeue() (returns x)

Теперь мы хотели бы, чтобы в нашем определении «правильности» говорилось, что эта история указывает на то, что либо наша реализация A содержит ошибки, либо наша реализация B содержит ошибки, потому что не существует сериализации, которая «имеет смысл» (либо Thread 2 должен прочитать значение из B, которое еще не было записано, или Поток 1 должен удалить из A значение, которое еще не было помещено в очередь.) Таким образом, в то время как наша первоначальная сериализация транзакций на A казалась разумной, если бы наша реализация допускает историю, подобную второй, тогда она явно неверна.

Таким образом, ограничения, которые добавляет линеаризация, вполне разумны (и необходимы даже для простых структур данных, таких как очереди FIFO.) Это такие вещи, как: «ваша реализация должна запретить dequeue () значение, которое не будет помещено в очередь () до тех пор, пока в течение некоторого времени будущее." Линеаризуемость довольно проста (и естественна) для достижения: просто ассоциируйте мьютекс с вашим объектом, и каждая транзакция начинается с блокировки и заканчивается разблокировкой. Рассуждение о линеаризуемости начинает усложняться, когда вы пытаетесь реализовать свою атомарность с помощью неблокирующих, без блокировок или без ожидания процедур вместо простых мьютексов.

Если вас интересуют некоторые ссылки на литературу, я обнаружил следующее (хотя я думаю, что обсуждение «реального времени» - это одна из «красных селедок», которые затрудняют линеаризуемость по сравнению с необходимостью.) Https: // stackoverflow.com/questions/4179587/difference-between-linearizability-and-serializability

Во-первых, линеаризуемость и сериализуемость не сопоставимы напрямую. Как показано в таблице ниже, основное отличие состоит в том, что с левой стороны все отдельные операции являются атомарными (например, наличие java synchronizedвокруг каждой операции. С правой стороны единица атомарности - это транзакция; отдельная операция не является атомарной). Вот почему Serializability всегда была частью литературы по базам данных, в то время как левая сторона была предметом литературы по процессорной памяти (чтение / запись является атомарной). Оригинальные хранилища Key-Value (такие как dbm и memcached) начинался с левой стороны (get / put является атомарным), но более новые поддерживают транзакции (например, гаечный ключ Google).

OBJ. операции атомарные | Транзакции атомарные
-------------------------------- + ----------------- ----------------
Линеаризуемость |
Последовательная последовательность | Сериализуемость
Причинная последовательность
Согласованность кэша |

Для линеаризации требуется, чтобы система объектов в параллельном параметре работала идентично последовательной системе, которая обрабатывает одну операцию (пару запрос / ответ) за раз - в параллельном юниверсе - таким образом, чтобы (а) клиенты в обеих вселенных видят абсолютно одинаковые ответы (б) временной порядок сохраняется (подробнее об этом ниже).

Определение сериализуемости, как и последовательная согласованность, требует только первого критерия.

Сохранение временного порядка означает следующее: если A: x.op1 () (A - клиент, x - объект, а op1 - операция), завершенная до начала другой операции B: y.op2 (), то в последовательном юниверсе - запросы обрабатываются в том же порядке. Это не требуется в последовательной согласованности (SC); объекту разрешено ставить в очередь запрос клиента, отвечать клиенту, а затем оценивать его позже. Кроме того, объект может обрабатывать более поздний запрос от другого клиента вне очереди, оценивая его перед тем, как перейти к первому.

Несохранение временного порядка является проблемой. После того, как A: x.op1 (), предположим, что A поднял трубку и сказал об этом B, затем B вызвал вызов x.op2 (). Система не может узнать об этой причинно-следственной цепочке событий, поскольку второй шаг включал в себя сообщение, не отслеживаемое системой. Во многих реальных случаях вполне разумно предположить, что A, как только x ответил на него, вызов B может полагаться на обновленное состояние. Если временный порядок не сохранился, A и B ожидают сюрприза. Этого не произойдет в линеаризуемой системе.

Вторым приятным свойством сохранения временного порядка является локальность и композиционность: система, построенная из линеаризуемых объектов, сама линеаризуема. Таким образом, вместо одного монолитного хранилища значений ключей вы можете разделить его на множество отдельных разделов, каждый из которых управляется своим собственным сервером KV-хранилища; если каждый из них является линеаризуемым, вся база данных функционирует как одно линеаризуемое монолитное хранилище KV без дополнительных усилий.