Что означает термин "линеаризуемая операция" в распределенных системах?
Мой вопрос возник во время чтения книги Мартина Клеппмана, "Высоконагруженные приложения. Программирование, масштабирование, поддержка", ISBN 978-5-4461-0512-0 столкнулся с непонятным для меня моментом на стр. 383. рис 9.4
В первой половине страницы автор говорит про затемненный прямоугольник и говорит, что эта операция нелинеризуема. Мне непонятно, а почему?
До стр.383 автор поясняет, что означает термин "линеаризуемая операция". Он поясняет это путем приведения примеров с операциями чтения и записи пересекающихся во времени:
- После того как операция записи получила подтверждение об успехе, с этого момента все операции чтения получают уже новое
- Также автор приводит слова, что во время операции записи есть момент, когда старое значение атомарно меняется на новое и клиент инициировавший операцию записи еще не получил подтверждение, а клиенты с запросами на чтение уже получают новое значение
Возвращаясь к рис.9.4 на стр.383 мне непонятнен момент, а почему автор делает акцент именно на клиенте B ? Ведь до этого произошел момент, когда клиент C сменил с помощью операции cas(x,2,4) сменил 2 на 4, что привело к тому что клиент A прочитал уже новое значение 4. Клиент А, как и клиент B тоже выполняется конкурентно! Почему автор ничего не сказал про клиента A , но про клиента B, который находится в такой же ситуации, что и клиент A вдруг говорит, что его операция чтения нелинеаризуема.
Слова автора "В отсутствие других запросов было бы хорошо, если бы чтение B вернуло 2" вообще сбивают с толку! Почему хорошо?
Ответы (1 шт):
В книге под рисунком 9.4 как раз есть определение чем отличается сериализуемость от линеаризуемости. Как раз на это понимание и стоит сделать упор.
TL;DR Точка линеаризации это некоторый момент в операции (даже в атомарной), после которого всей прочей системе видно новое значение переменной. Если какому-то отдельному ресурсу (потоку/сервису), это новое значение не видно (а кому-то другому видно), значит система нелиниарзуема.
Пояснение
В интернете есть полно научных определений этим терминам, постараюсь пояснить простым языком, опуская детали.
Любая функция (даже будь она атомарной), это некий набор операций.
Возьмём для примера функцию CAS (Compare and swap). С одной стороны она считается атомарной, да она выполняет 3 операции: читает значение по адресу, сравнивает его с ожидаемым значением и затем: если ожидаемое значение соответствует прочитанному, она перезаписывает значение по адресу. Для современных процессоров это обычно одна инструкция (не будем вдаваться в подробности) и она действительно атомарна (выполнится как будто за раз).
Только дело в том, что эта операция, в реальном времени, выполнится не за мгновение, а за некоторое время. Ведь нужно подготовить стек вызовов, загрузить данные из памяти, вплоть до того, что электрические сигналы проходят по плате. Все эти долгие подготовительные процессы, отнимают много времени, а сама операция записи выполняется довольно быстро. Но тогда получается, что CAS можно во времени представлять не как единое целое, а как что-то, что может длиться довольно долго.
Теперь представим что у нас есть 3 обработчика, первый пытается с помощью CAS выполнить запись, только этот обработчик очень медленный и операция CAS (для простоты понимания) выполняется за 1 секунду (1000 мс). Но новое значение (допустим мы это явно знаем) можно будет прочитать после 555мс, а вот всё остальное время нужно в служебных целях (подготовить, очистить, записать что-то). А два другие пытаются читать информацию (допустим чтение исполняется за 100мс). Все они работают параллельно.
Сериализуемость - это возможность системы поставить операции так, как будто это некоторая транзакция. Т.е. строгое выполнение операций друг-за другом, как если бы они выполнялись на одном потоке. Тогда по сути такой проблемы бы и не было, мы могли бы явно разместить:
write (1000ms) - read (100ms) - read (100ms)
Но формально компилятор может расставить это как:
read (100ms) - write (1000ms) - read (100ms)
На подобие транзакции, мы выполняем операции, но коммит происходит только после того как мы полностью завершили операцию.
Но здесь получается мы засинхронизировали нашу систему и для выполнения ей потребуется 1200мс (что долго).
Линеаризуемость - это ослабленное (relaxed) понятие сериализуемости. Мы знаем что операция выполняется не за мгновение, а есть некоторая точка (момент) в реальном времени, когда система начинает видеть новое значение. Но сама операция при этом может быть ещё не завершена. Это будет точкой линеаризации.
Конкретно про рисунок:
Клиент C делает запись cas(x, 2, 4). Она срабатывает.
В это время, Клиент A выполняет read(x). Тут так совпало что точка линеаризуемости (когда данные видны) операции read(x) стоит после того как сработал cas(x, 2, 4), поэтому он уже получил значение read(x) = 4.
Далее, после чтения read(x) Клиентом А, Клиент В тоже читает тот же самый read(x), его точка линеаризации стоит после cas и после read Клиентом А. Однако, по какой-то причине Клиент B получает read(x) = 2, но мы явно знаем, что read(x) клиента B, случился после read(x) Клиента A. Значит у Клиента B, тоже должно быть значение read(x) = 4, но по какой-то причине у Клиента В неправильная информация (возможно x прилетел из кэша Клиента В, так как он делал запись до этого, а может ещё что-то произошло), но в итоге мы получили что получили, а значит в общей системе есть момент, где чтение происходит не из актуальных данных, которые видят все, а из каких-то локальных.