В чем разница между линеаризуемостью и сериализуемостью?
В чем разница между линеаризуемостью и сериализуемостью (в контексте Java)? Можете ли вы объяснить разницу между ними на примере или дать хорошую ссылку?
6 ответов
Главное различие между ними заключается в том, что сериализуемость является глобальным свойством; свойство всей истории операций / транзакций. Линеаризуемость является локальной собственностью; свойство отдельной операции / транзакции. Другое отличие состоит в том, что линеаризуемость включает в себя понятие реального времени, а сериализуемость - нет: точка линеаризации операции должна находиться между временем ее вызова и откликом. (См. Тим Харрис: Транзакционная память, 2ed. См. Слайды Херлихи из "Искусства многопроцессорного программирования", раздел о линеаризации, которые доступны здесь, для некоторых примеров и доказательств.
Оба свойства нацелены на одну и ту же цель: последовательная согласованность. Из статьи Херлихи:
Большая часть работы с базами данных и распределенными системами использует сериализуемость в качестве основного условия корректности для параллельных вычислений. В этой модели транзакция является потоком управления, который применяет конечную последовательность примитивных операций к набору объектов, совместно используемых с другими транзакциями. История является сериализуемой, если она эквивалентна истории, в которой транзакции выполняются последовательно, т.е. без чередования. (Неполный) порядок приоритета может быть определен для неперекрывающихся пар транзакций очевидным образом. История строго сериализуема, если порядок транзакций в последовательной истории совместим с порядком их приоритета...
... Линеаризуемость можно рассматривать как особый случай строгой сериализуемости, когда транзакции ограничены одной операцией, примененной к одному объекту. Тем не менее, это ограничение одной операции имеет далеко идущие практические и формальные последствия, давая линеаризуемым вычислениям иной вид по сравнению с их сериализуемыми аналогами. Непосредственным практическим следствием является то, что механизмы управления параллелизмом, подходящие для сериализуемости, обычно не подходят для линеаризуемости, потому что они вносят ненужные издержки и накладывают ненужные ограничения на параллелизм.
Рекомендации:
Харрис, Тим, Джеймс Ларус и Рави Раджвар: транзакционная память, 2ed. Обобщающие лекции по компьютерной архитектуре. Morgn & Claypool, 2010. ISBN 9781608452354. URL: http://www.morganclaypool.com/doi/abs/10.2200/S00272ED1V01Y201006CAC011?journalCode=cac
Херлихи, Морис и Жанетт Винг: Линеаризуемость: условие корректности для параллельных объектов. ACM Trans. Prog. Lang. и сис. Том 12, № 3, июль 1990 г., стр. 463-492. URL http://www.cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf
Пападимитриу, Христос: Сериализуемость одновременных обновлений базы данных. Журнал ACM Vol 26. № 4. Октябрь 1979, с. 631-653. URL http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-210.pdf
Херлихи, Морис и Нир Шавит: искусство многопроцессорного программирования. Elsevier, 2008. ISBN 978-0-12-370591-4. URL: http://www.elsevier.com/wps/find/bookdescription.cws_home/714091/description Слайды PPT по линеаризуемости находятся здесь: http://pub.ist.ac.at/courses/ppc10/slides/Linearizability.pptx
Аттия, Хагит и Дженнифер Уэлч: последовательная согласованность и линеаризуемость. ACM Транзакции на компьютерных системах Vol. 12, No. 2, May 1994, Pages 91-122. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4969&rep=rep1&type=pdf
Больше деталей:
Если вы действительно заботитесь об этом, прочитайте статью с введенными определениями. Для линеаризуемости это Linearizability: условие корректности для параллельных объектов, Herlihy и Wing. Это плотно, но стоит внимания. Обратите внимание, что в сообществе программной транзакционной памяти остается открытым вопрос, является ли линеаризуемость правильной целью / свойством, к которому нужно стремиться.
Сериализуемость заключается в том, что результат совокупности операций / "система" выражается в виде определенного порядка ("как если бы выполнение имело место в определенном порядке...") всех операций. Линеаризуемость - это свойство одного подмножества операций в системе... операция / набор операций являются линеаризуемыми, если они кажутся другим операциям, как если бы они произошли в определенный момент (логического) времени по отношению к другим. Каноническим документом здесь является Papadimitriou, Сериализуемость одновременных обновлений базы данных.
Думайте об "атомарной операции", когда вы думаете о "линеаризуемости". (Набор) операций линеаризуются, когда они (кажется) происходят атомарно по отношению к другим частям системы. Распространенная формулировка "создайте иллюзию, что каждая операция вступает в силу мгновенно между ее вызовом и ответом". Формулировка линеаризуемости обусловлена Херлихи, который подчеркивает, что это локальное свойство, в отличие от других видов последовательных свойств согласованности, таких как "сериализуемость", которые являются глобальными.
Питер Бейлис предлагает отличное объяснение:
"В простом английском языке при линеаризуемости записи должны выглядеть мгновенно. Неточно, после завершения записи все последующие чтения (где" позже "определяется временем начала настенных часов) должны возвращать значение этой записи или значение более поздняя запись. Как только чтение возвращает определенное значение, все последующие чтения должны возвращать это значение или значение более поздней записи. "
"Сериализуемость - это гарантия транзакций или групп из одной или нескольких операций над одним или несколькими объектами. Она гарантирует, что выполнение набора транзакций (обычно содержащих операции чтения и записи) для нескольких элементов эквивалентно некоторому последовательному выполнению (всего упорядочение) сделок ".
См. Ответ @ andersoj для ясного описания различия между сериализуемостью и линеаризуемостью.
Это только косвенно относится к параллельному программированию на Java. В общем, параллельная Java-программа не должна иметь сериализуемую или линеаризуемую историю. В таких случаях сериализуемость обычно достаточна для "корректности" программы (Java или иным образом), хотя для конкретных задач может потребоваться более сильное свойство линеаризуемости. Но так или иначе, именно проблема определяет правильность, а не Java.
Проверьте объяснение Википедии:
http://en.wikipedia.org/wiki/Linearizability
Это также может немного сбивать с толку, потому что мы также используем термин сериализация для обозначения преобразования класса в поток данных для хранения или передачи по сети.
Представьте, что ваша распределенная система работает на 3 машинах (3 реплики). Мы просто хотим записать и прочитать значение ключа "A".
Линеаризуемый
В этой модели наша система будет работать следующим образом: как только запись (A) будет выполнена, мы сможем прочитать последнее значение из любой из трех реплик. Это означает, что как только действие (запись/чтение) выполнено, его влияние видно для всех будущих действий во всей системе (например, атомарная операция).
Здесь порядок действий не имеет значения. Итак, на самом деле мы хотим писать и читать, но система может читать и писать, и это нормально, и она по-прежнему будет Линеаризуемой. Алгоритмы Paxos/Raft обеспечивают это для транзакции для большинства узлов.
Сериализуемый
В этой модели все реплики (машины) будут обрабатывать действия/события в одном и том же порядке. Таким образом, если одна из реплик записывает (A) и читает (A), другие реплики будут делать это в том же порядке.
Здесь можно получить устаревшие данные из других реплик. Скажем, replica_1 записывает (A). Чтение (A) из реплики_1 вернет последнее значение, но если мы прочитаем из реплики_2, мы можем получить старое значение. Единственная гарантия заключается в том, что всякий раз (без ограничения по времени) replica_2 будет обрабатываться в том же порядке - запись, а затем чтение. Zookeeper обеспечивает это.
Это хороший блог, чтобы узнать больше об этом -http://www.bailis.org/blog/linearizability-versus-serializability/
Дайте мне знать, если мое понимание неверно. Рад учиться и расти!
Хороший способ понять это - взглянуть на эту проблему с точки зрения базы данных. (Я знаю, что вы просите контекст java, извините)
Предположим, вы являетесь базой данных. Вы принимаете несколько транзакций, работающих на одном объекте одновременно, но у вас есть только один единственный рычаг диска.
Когда вы получили несколько транзакций одновременно, вам придется каким-то образом изменить порядок этих операций внутри транзакций, чтобы ваш плохой дисковый манипулятор мог обрабатывать их одну за другой.
Сериализуемый
у вас есть возможность переупорядочить эти транзакции, чтобы казалось, что они происходят последовательно (одна за другой). Как вы понимаете, это не всегда возможно, если вы принимаете произвольные транзакции (например, одну неверную транзакцию за последние 10 лет). Поэтому, естественно, вы применяете некоторые ограничения или механизмы предотвращения конфликтов, после чего вы можете сказать: "Я сериализуемый!:)" .
Линеаризуемый
Вам не только нужно делать то, что serializationнужно сделать. Вы также внимательно посмотрите на эти транзакции. И очень постарайтесь переупорядочить эти транзакции последовательным образом, не нарушая семантический порядок транзакций. Как вы могли заметить,semantic orderэто ключ. В основном, чтобы утверждать, что выlinearizable, вам нужно будет предположить / найти linearizationpoint для каждой транзакции, а затем заказать их в соответствии с linearizationpoint.
Таким образом, универсальная база данных RDMS редко говорит HeyI'm linearizable!. Но это не редкость, если вы работаете с базой данных типа ключ-значение.
например, в качестве базы данных KV вы можете сказать "Я linearizable!", если вы можете readвсегда будет получать последнюю возможную запись. (предполагая момент отправки ответа наread операция - это linearizationpointЗвучит банально, но будет серьезной проблемой, если вы используете распределенную базу данных KV. Также обратите внимание, чтоserializability не требует от вас предоставления такой же гарантии.