Синхронизация в распределенных системах

(operate independent of events in other processes)
Sometimes need to cooperate/synchronize
For

mutual exclusion
For event ordering (was message x from process P sent before or after message y from process Q?)

ordering is clear because all events are timed by the

same clock
Synchronization in distributed systems is harder
No shared memory
No common clock

исключение
Распределенные транзакции

в системе
Например команда make в OS Unix, которая учитывает время

последней модификации файла при перетрансляции модулей проекта.






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

Системные часы ЭВМ
Атомные часы

как 1/86 400 солнечного дня.
Геометрические построения, необходимые для расчета

солнечного дня, приведены на рисунке.
Период обращения замедляется из-за приливного трения и вязкости атмосферы.
Продолжительность года (время одного оборота вокруг солнца) при этом не изменяется, сутки просто становятся длиннее.

Среднее время по Гринвичу (англ. Greenwich Mean Time, GMT), или гринвичское время — среднее солнечное время меридиана, проходящего через прежнее место расположения Гринвичской королевской обсерватории около Лондона[1].
Ранее, до 1972 года[2], гринвичское время, GMT, считалось точкой отсчёта времени в других часовых поясах[3]. Ныне в этом качестве используется всемирное координированное время, оно же UTC.

памяти.
В состав IBM PC AT входят часы реального времени

Real Time Clock (RTC) и 64 байта неразрушающейся оперативной КМОП памяти (CMOS), питающиеся от автономного источника питания.
При включении ПЭВМ содержимое CMOS анализируется POST, который извлекает из нее конфигурацию системы и текущие дату и время.
Кварцевый генератор имеет частоту 32768 Гц и стабильность работы 10-5

Кварцевый генератор имеет начальную погрешность 30 частей от миллиона (parts per million), то есть 32768Гц*30/1000000=±0,98304Гц.

часы. Физики определили секунду как время, за которое атом цезия-133

совершит ровно 9 192 631 770 переходов. Выбор числа 9 192 631 770 сделал атомную секунду равной средней солнечной секунде в год ее расчета.
В настоящее время около 50 лабораторий по всему миру имеют часы на цезии-133. Периодически каждая лаборатория сообщает в международное бюро мер и весов в Париже, сколько времени на их часах. Международное бюро усредняет их результаты и выдает глобальное время по атомным часам {International Atomic Time, TAI). TAI — это среднее время тиков часов на цезии-133, прошедшее с полуночи 1 января 1958 года (начала времен) и деленное на 9 192 631 770.
Хотя время ТАI весьма стабильно, но имеется серьезная проблема: 86 400 с TAI в настоящее время приблизительно на 3 мс меньше среднего солнечного дня (потому что средний солнечный день все время удлиняется).

секунды (leap seconds) всякий раз, когда разница между временем TAI

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





Она называется универсальным согласованным временем {Universal Coordinated Time, UTC). UTC — это основа всей системы хранения времени в наши дни. Оно, по существу, заменило старый стандарт — среднее время по Гринвичу {Greenwich mean time), которое основывалось на астрономических наблюдениях и расчетах.

коротковолновую радиостанцию с позывными WWV из форта Коллинз (Fort Collins),

штат Колорадо. Радиостанция WWV широковещательно рассылает короткий импульс в начале каждой секунды UTC. Точность самой радиостанции WWV составляет около ±1 мс, но из-за различных атмосферных флуктуации длина сигнала может меняться, так что на практике точность составляет не более ±10 мс.
В Англии станция MSF, работающая из Регби (Rugby), район Варвикшир (Warwickshire), предоставляет похожую службу.
Существуют также станции UTC и в некоторых других странах.
Некоторые спутники Земли также предоставляют службы UTC. Рабочий спутник геостационарного окружения (Geostationary Environment Operational Satellite - GEOS) может предоставлять время UTC с точностью до 0,5 мс, а некоторые другие — и с более высокой точностью.
GPS (Global Positioning System) обеспечивает точность до 20-35 наносекунд.

WWV, то задачей является синхронизация с ней всех остальных машин.
Если

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

что каждая машина имеет таймер, который инициирует прерывание Н раз

в секунду.
Обозначим значение часов машины р — Cp(t). В идеальном мире мы можем считать, что Cp(t) = t для всех р и всех t. Другими словами, dC/dt — точно единица.
Теоретически таймер с H= 60 должен генерировать 216 000 тиков в час. На практике относительная ошибка, допустимая в современных микросхемах таймеров, составляет порядка 10-5. Это означает, что конкретная машина может выдать значение в диапазоне от 215 998 до 216 002 тиков в час.
Пусть имеется константа r (максимальная скорость дрейфа часов системы):
1-r<=dC/dt<= 1+r
В этих пределах таймер может считаться работоспособным.

разные стороны за время А^ после синхронизации, разница между их

показаниями может быть не более чем 2r·Δt.
Если разработчики операционной системы хотят гарантировать, что никакая пара часов не сможет разойтись более чем на Δt, то синхронизация часов должна производиться не реже, чем каждые Δt /2р с.
Различные алгоритмы отличаются точностью определения момента проведения повторной синхронизации.

синхронизацию с реальным временем UTC.
Попытаться обеспечить максимально возможную синхронизацию узлов

друг с другом, даже в ущерб синхронизацией с UTC.
Обеспечить синхронизацию достаточную для обеспечения правильного взаимодействия узлов друг с другом на основе сохранения правильного порядка обмена сообщениями.
В этом случае говорят о логических часах РС.

по UTC в пределах 1-50мс. Используется в сетях TCP/IP.
Для синхронизации

используется иерархия пассивных серверов NTP
Алгоритм Беркли:
Цель: обеспечить синхронизацию часов узлов друг с другом (внутренняя синхронизация)
Для синхронизации используются активные сервера времени периодически опрашивающие узлы.
Reference broadcast synchronization (RBS) (Опорная широковещательная синхронизация)
Цель: обеспечить синхронизацию часов узлов друг с другом в беспроводной сети

(stratum). Ярус 0 представлен эталонными часами. За эталон берется сигнал

GPS (Global Positioning System) или службы ACTS (Automated Computer Time Service). На нулевом ярусе NTP-серверы не работают.
NTP-серверы яруса 1 получают данные о времени от эталонных часов. NTP-серверы яруса 2 синхронизируются с серверами яруса 1. Всего может быть до 15 ярусов.
NTP-серверы и NTP-клиенты получают данные о времени от серверов яруса 1, хотя на практике NTP-клиентам лучше не делать этого, поскольку тысячи индивидуальных клиентских запросов окажутся слишком большой нагрузкой для серверов яруса 1. Лучше настроить локальный NTP-сервер, который ваши клиенты будут использовать для получения информации о времени.

Время представляется в системе NTP 64-битным числом (8 байт), состоящим из 32-битного счётчика секунд и 32-битного счётчика долей секунды, позволяя передавать время в диапазоне 232 секунд, с теоретической точностью 2−32 секунды.

всех остальных машин значения их часов (а).
Демон получает ответы машин

(б).
Демон времени сообщает всем, как следует подвести их часы (в)

реже, чем каждые 2r·Δt с, каждая машина посылает серверу времени

сообщение, запрашивая текущее время.





Когда отправитель получает ответ, он может просто выставить свои часы в значение CUTC . Однако такой алгоритм имеет две проблемы:
Главную – время идет только вперед .
Второстепенную – ответное сообщение поступает с не нулевой задержкой.

проблемы состоит в измерении величины задержки передачи по сети.
Для повышения

точности Кристиан предложил производить не одно измерение, а серию. Все измерения, в которых разность Т1-Т0 превосходит некоторое пороговое значение, отбрасываются как ставшие жертвами перегруженной сети, а потому недостоверные. Оценка делается по оставшимся замерам, которые могут быть усреднены для получения наилучшего значения.

синхронизация по UTC, можно предложить использование нескольких приемников WWV, GEOS

или других источников UTC.
Однако из-за врожденной неточности самих источников времени и флуктуации на пути сигнала лучшее, что могут сделать операционные системы, — это установить интервал, в который попадает UTC. В основном различные источники точного времени будут порождать различные диапазоны, и машины, к которым они присоединены, должны прийти к какому-то общему соглашению.
Чтобы достичь этого соглашения, каждый процессор с источником UTC может периодически делать широковещательную рассылку своих данных, например, точно в начале каждой минуты по UTC.
Но печально то, что задержка между посылкой и приемом будет зависеть от длины кабеля и числа маршрутизаторов, через которые должен будет пройти пакет. Эти значения различны для каждой пары (источник UTC, процессор). Будут также играть свою роль и другие факторы, так что точной синхронизации добиться не удастся.

часов с точностью до нескольких миллисекунд по UTC.
Традиционный подход состоит

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

считали, что сейчас 10:00, даже если на самом деле сейчас

10:02. Так, для некоторого класса алгоритмов подобная внутренняя непротиворечивость имеет гораздо большее значение, чем то, насколько их время близко к реальному. Для таких алгоритмов принято говорить о логических часах (logical clocks).
В своей классической статье Лампорт (Lamport) показал, что хотя синхронизация часов возможна, она не обязательно должна быть абсолютной.

названием «происходит раньше». Выражение а→b читается как «а происходит раньше

b» и означает, что все процессы согласны с тем, что первым происходит событие а, а позже — событие b, Отношение «происходит раньше» непосредственно исполняется в двух случаях.
Если а и b — события, происходящие в одном и том же процессе, и а происходит раньше, чем b, то отношение а → Ь истинно.
Если а — это событие отсылки сообщения одним процессом, а b — событие получения того же сообщения другим процессом, то отношение а → Ь также истинно.

Три процесса, каждый с собственными часами, которые ходят с разной
скоростью (а).



Подстройка часов по алгоритму Лампорта (б)

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

какой именно процесс выполняет эти специальные действия, главное, чтобы он вообще существовал.
Роль координатора может выполнять любой процесс.
Любой процесс может инициировать процедуру выборов.
Каждый процесс имеет некоторый уникальный номер.
В общем, алгоритмы голосования пытаются найти процесс с максимальным номером и назначить его координатором. Алгоритмы различаются способами поиска координатора.

отвечает на запросы, он инициирует голосование. Процесс, например Р, проводит

голосование следующим образом.
1. Р посылает всем процессам с большими, чем у него, номерами сообщение
ГОЛОСОВАНИЕ.
2. Далее возможно два варианта развития событий:
если никто не отвечает, Р выигрывает голосование и становится координатором;
если один из процессов с большими номерами отвечает, он становится координатором, а работа Р на этом заканчивается.
В любой момент процесс может получить сообщение ГОЛОСОВАНИЕ от одного из своих коллег с меньшим номером. По получении этого сообщения получатель посылает отправителю сообщение ОК, показывая, что он работает и готов стать координатором.
Затем получатель сам организует голосование. В конце концов, все процессы, кроме одного, отпадут, этот последний и будет новым координатором. Он уведомит о своей победе посылкой всем процессам сообщения, гласящего, что он новый координатор и приступает к работе.

завис.
Процесс 4 первым замечает это и посылает сообщение ГОЛОСОВАНИЕ

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

процессы физически или логически упорядочены, так что каждый из процессов

знает, кто его преемник.

Когда один из процессов обнаруживает, что координатор не функционирует, он строит сообщение ГОЛОСОВАНИЕ, содержащее его номер процесса, и посылает его своему преемнику.
Если преемник не работает, отправитель пропускает его и переходит к следующему элементу кольца или к следующему, пока не найдет работающий процесс.
На каждом шаге отправитель добавляет свой номер процесса к списку в сообщении, активно продвигая себя в качестве кандидата в координаторы.
В конце концов, сообщение вернется к процессу, который начал голосование.
В этот момент тип сообщения изменяется на КООРДИНАТОР и вновь отправляется по кругу, на этот раз с целью сообщить всем процессам, кто стал координатором (элемент списка с максимальным номером) и какие процессы входят в новое кольцо.

Когда два процесса, 2 и 5, одновременно
обнаруживают, что предыдущий координатор, процесс 7, перестал работать.
Каждый из них строит сообщение ГОЛОСОВАНИЕ и запускает это сообщение в путь по кольцу независимо от другого.
Оба выбирают 6: [5,6,0,1,2,3,4] [2,3,4,5,6,0,1]

процессов, обычно проще всего программировать, используя критические области.
Когда процесс

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

в распределенных системах состоит в том, чтобы использовать методы их

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

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

системе. То есть в любой паре событий, например отправки сообщений,

должно быть однозначно известно, какое из них произошло первым. Алгоритм Лампорта, является одним из способов введения подобной упорядоченности и может быть использован для расстановки отметок времени распределенных взаимных исключений.
Когда процесс собирается войти в критическую область, он создает сообщение, содержащее имя критической области, свой номер и текущее время. Затем он отсылает это сообщение всем процес-сам, концептуально включая самого себя. Посылка сообщения, как предполагается, надежная, то есть на каждое письмо приходит подтверждение в получении. Вместо отдельных сообщений может быть использована доступная надежная групповая связь.
Когда процесс получает сообщение с запросом от другого процесса, действие, которое оно производит, зависит от его связи с той критической областью, имя которой указано в сообщении.

критической области и не собирается туда входить, он отсылает отправителю

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

войти в одну и ту же критическую область (а).
Процесс 0

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

ответить на запрос. Это молчание будет воспринято (неправильно) как отказ

в доступе и блокирует все последующие попытки всех процессов войти в какую-либо из критических областей.
Этот алгоритм может быть исправлен так, что когда приходит запрос, его получатель посылает ответ всегда, разрешая или запрещая доступ. Всякий раз, когда запрос или ответ утеряны, отправитель выжидает положенное время и либо получает ответ, либо считает, что получатель находится в нерабочем состоянии. После получения запрещения отправитель ожидает последующего сообщения ОК
Другая проблема этого алгоритма состоит в том, что либо должны использоваться примитивы групповой связи, либо каждый процесс должен поддерживать список группы самостоятельно, обеспечивая внесение процессов в группу, удаление процессов из группы и отслеживание сбоев. Метод наилучшим образом работает, когда группа процессов мала, а членство в группе постоянно и никогда не меняется.
В распределенном алгоритме все процессы вынуждены участвовать во всех решениях, касающихся входа в критические области. Если один из процессов оказывается неспособным справиться с такой нагрузкой, маловероятно, что возымеет успех попытка их всех сделать то же самое параллельно.
Алгоритм можно модифицировать так, чтобы разрешить процессу вход в критическую область после того, как он соберет разрешения простого большинства, а не всех остальных процессов.
Несмотря на все возможные улучшения, этот алгоритм остается более медленным, более сложным, более затратным и менее устойчивым, чем исходный централизованный алгоритм.

назначается его положение в кольце. При инициализации кольца процесс О

получает маркер, или токен (token).
Маркер циркулирует по кольцу. Он передается от процесса k процессу k+ 1 (это модуль размера кольца) сквозными сообщениями. Когда процесс получает маркер от своего соседа, он проверяет, не нужно ли ему войти в критическую область.
Если это так, он входит в критическую область, выполняет там всю необходимую работу и покидает область. После выхода он передает маркер дальше.
Входить в другую критическую область, используя тот же самый маркер, запрещено.
Если процесс, получив от соседа маркер, не заинтересован во входе в критическую область, он просто передает этот маркер дальше.

взаимного исключения обеспечивают одновременный доступ не более чем одного процесса

к совместно используемым ресурсам.
Транзакции, в общем, также защищают общие ресурсы от одновременного доступа нескольких параллельных процессов.
Однако транзакции могут и многое другое:
Они превращают процессы доступа и модификации множества элементов данных в одну атомарную операцию;
Если процесс во время транзакции решает остановиться на полпути и повернуть назад, все данные восстанавливаются с теми значениями и в том состоянии, в котором они были до начала транзакции.

из характерных свойств транзакции. Говоря более конкретно, транзакции:
атомарны (atomic) —

для окружающего мира транзакция неделима;
непротиворечивы (consistent) — транзакция не нарушает инвариантов системы;
изолированы (isolated) — одновременно происходящие транзакции не влияют друг на друга;
долговечны (durable) — после завершения транзакции внесенные ею изменения становятся постоянными.
На эти свойства часто ссылаются по их первым буквам — ACID.

имеют одно ограничение - они не могут даватьчастичного результата в

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

записью.

рабочее пространство, содержащее все файлы, к которым он хочет получить

доступ.
Пока транзакция не завершится или не прервется, все операции чтения и записи будут происходить не в файловой системе, а в закрытом рабочем пространстве.
Это утверждение прямо приводит нас к первому методу реализации — созданию для процесса, в момент начала транзакции, закрытого рабочего пространства.

Индекс файла и дисковые блоки для файла из трех блоков (а).
Ситуация после того,
как транзакция модифицировала блок 0 и добавила блок 3 (б).
Ситуация после подтверждения транзакции {в)

же, где находятся, но перед тем, как какой-либо блок действительно

будет изменен, в журнал заносится запись со сведениями о том, какая транзакция вносит изменения, какой файл и блок изменяются, каковы прежние и новые значения.
Только после успешной записи в журнал изменения вносятся в файл.
Листинг 5.3. Транзакция
X = 0:
У = 0:
BEGINJRANSACTION:
X = X + 1:
У = У + 2;
X = у * у:
ENDJRANSACTION;

Для каждой из трех инструкций тела транзакции до начала ее выполнения создается запись в журнале, которая содержит прежнее и новое значения, разделенные косой чертой:
- содержимое журнала перед выполнением первой инструкции (х=х+1:):
[х=0/1]
- содержимое журнала перед выполнением второй инструкции (у=у+2:):
[х=0/1]
[у=0/2]
- содержимое журнала перед выполнением третьей инструкции (х=у*у;):
[х=0/1]
[у=0/2]
[х=1/4]

чтобы позволить нескольким транзакциям выполняться одновременно, но таким образом, чтобы

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

На самом верхнем уровне находится менеджер транзакций.
На среднем уровне – планировщик.
В самом низу – менеджер данных.

Он обрабатывает примитивы транзакций, преобразуя их в запросы к планировщику.

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

выполнения многочисленных транзакций до тех пор, пока они изолированы друг

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

выполнением транзакций — это блокировка (locking).
При двухфазной блокировке (Two-Phase Locking,

2PL), планировщик сначала, на фазе подъема {growingphase), устанавливает все необходимые блокировки, а затем, на фазе спада {shrinking phase), снимает их.

При 2PL выполняются три правила:
Проверка не конфликтует ли эта операция с другими уже заблокированными операциями.
Планировщик никогда не снимает блокировку с элемента х, если менеджер сообщает, что он выполняет операцию с х.
Когда планировщик снимает блокировку с операции установленную по требованию транзакции Т, он никогда не делает новую блокировку по требованию этой транзакции.

Доказано, что если все транзакции используют двухфазную блокировку, любой план, сформированный путем перекрытия этих транзакций, сериализуем. В этом причина популярности двухфазной блокировки.