Формализм распределённых систем — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Отличия от параллельных систем)
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 2 участников)
Строка 8: Строка 8:
 
Нас интересует взаимодействие между процессами, оно бывает ровно одного вида: посылки сообщений друг другу.
 
Нас интересует взаимодействие между процессами, оно бывает ровно одного вида: посылки сообщений друг другу.
 
С точки зрения внешнего мира процесс считается однопоточным: все отправки/получения сообщений одним процессом линейно упорядочены.
 
С точки зрения внешнего мира процесс считается однопоточным: все отправки/получения сообщений одним процессом линейно упорядочены.
 +
Обычно каждый процесс может послать сообщение каждому, но иногда это ограничивается.
 +
В реальном мире может быть такое, что кому-то отослать сообщение быстрее, чем другому.
  
 
В каждом процессе могут происходить '''события''', обычно обозначаются маленькими латинскими буквами: $a, b, c, d, \dots \in \mathbb E$.
 
В каждом процессе могут происходить '''события''', обычно обозначаются маленькими латинскими буквами: $a, b, c, d, \dots \in \mathbb E$.
Строка 30: Строка 32:
 
Так что в алгоритмах нас интересует не время вычислений, а количество посланных сообщений, причём точное, а не просто асимптотика.
 
Так что в алгоритмах нас интересует не время вычислений, а количество посланных сообщений, причём точное, а не просто асимптотика.
  
Отказ узлов или связи в распределённых системах — обычное дело, это основная сложность разработки распределённых алгоритмов.
+
Отказ узлов или связи в распределённых системах — обычное дело, это '''основная сложность''' разработки распределённых алгоритмов (в отличие от просто параллельных).
 
До билетов про иерархию ошибок мы считаем, что ошибок нет (например, в алгоритмах взаимного исключения).
 
До билетов про иерархию ошибок мы считаем, что ошибок нет (например, в алгоритмах взаимного исключения).
  
Строка 41: Строка 43:
  
 
== Задачи ==
 
== Задачи ==
 +
=== Взаимное исключение ===
 +
 +
Почти как в [[Алгоритмы взаимного исключения|параллельных системах]]:
 +
 +
{{Определение
 +
|definition=
 +
Критическая секция $CS_i$ — это пара из двух событий: $Enter(CS_i), Exit(CS_i) \in E$ (вход и выход из критической секции), при этом $Enter(CS_i) < Exit(CS_i)$ (в частности, они выполняются в одном процессе) и для всех $i$ верно: $Exit(CS_i) \to Enter(CS_{i+1})$ (т.е. критические секции линейно упорядочены).
 +
}}
 +
 +
Это требование ''корректности'' — что алгоритм ''не может допустить''.
 +
Мы здесь нигде не пользовались словом "одновременно".
 +
Более того, нам даже не требуется вводить отдельные события входа/выхода, достаточно уже имеющихся событий отправки/получения сообщений (т.к. в системе ничего кроме сообщений принципиально происходить не может).
 +
 +
Также можно вводить дополнительные требования прогресса (что алгоритм ''должен делать''), но мы это делаем неформально. Можно требовать (от более слабых к более строгим):
 +
 +
# Если "сейчас" ни один процесс в критической секции не находится, но кто-то "хочет" в неё попасть, то хотя бы один процесс рано или поздно туда попадёт.
 +
# "Честность": если процесс хочет попасть в критическую секции, то он рано или поздно туда попадёт независимо от действий остальных (если они, конечно, секцию будут освобождать).
 +
 +
=== Запуск нескольких алгоритмов и перезапуск ===
 +
Некоторые алгоритмы в курсе алгоритмы "одноразовые" (например, достижение консенсуса или снятие согласованного среза).
 +
Чтобы запустить их несколько раз, на практике можно запустить несколько копий алгоритма и к каждому сообщению прикреплять номер копии.
 +
Тогда они будут работать независимо друг от друга и работать корректно, хотя нет никаких гарантий про то, как они будут соотноситься между собой (например, алгоритм, запущенный позже, может завершиться раньше).
 +
 +
Также могут быть тонкости с "запуском" алгоритмов: например, [[алгоритм Чанди-Лампорта]] требует сохранять все отправленные с начала времён сообщения.
 +
 +
Ещё бывают тонкости с конфигурацией и переконфигурацией алгоритмов, особенно актуально для алгоритмов консенсуса, но это всё разбиралось лишь на семинарах.

Текущая версия на 19:30, 4 сентября 2022

Модель

Имеется несколько независимых процессов, обычно обозначаются большими латинскими буквами: $P, Q, R, \dots \in \mathbb P$. Происходящее внутри процесса нас не интересует: там может быть сложная многопоточная система или простой цикл; может быть детерминированным, а может кидать монетку.

Процессы могут посылать друг другу сообщения, обычно обозначаются $m \in \mathbb M$ (с индексами). Нас интересует взаимодействие между процессами, оно бывает ровно одного вида: посылки сообщений друг другу. С точки зрения внешнего мира процесс считается однопоточным: все отправки/получения сообщений одним процессом линейно упорядочены. Обычно каждый процесс может послать сообщение каждому, но иногда это ограничивается. В реальном мире может быть такое, что кому-то отослать сообщение быстрее, чем другому.

В каждом процессе могут происходить события, обычно обозначаются маленькими латинскими буквами: $a, b, c, d, \dots \in \mathbb E$. Можно узнать процесс, в котором произошло событие: $proc(e) \in \mathbb P$ (такая нотация встречается редко). Если $e$ и $f$ произошли в одном процессе, то одно из двух произошло первым, обозначается $e < f$.

Каждому сообщению соответствуют ровно два события: отправка сообщения $snd(m) \in \mathbb E$ и его получение $rcv(m) \in \mathbb E$. Другие события нас не интересуют.

Happens-before (произошло-до)

Транзитивное замыкание:

  • Если $e < f$, то $e \to f$
  • Для любого сообщения $m$: $snd(m) \to rcv(m)$

События $a$ и $c$, не связанные отношением произошло-до, называются параллельными.

"Времени" или "глобального времени" в распределённых системах не существует. Следствие: слова "одновременно" и "текущий момент" запрещены, если только не подкрепляются определением на основе "произошло-до". Можно почитать Justin Sheehy. 2015. There is No Now. Queue 13, 3, Pages 20 (March 2015), 8 pages. DOI: https://doi.org/10.1145/2742694.2745385

Отличия от параллельных систем

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

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

Из-за сети сообщения могут идти непонятно сколько времени (в том числе на практике). В синхронных системах гарантируется, что каждое сообщение либо доходит за некоторое константное время $C$, либо теряется. В асинхронных системах сообщения могут идти сколь угодно долго. До билетов про синхронные системы мы считаем всё асинхронным. На практике же везде ставят таймаут, превращая систему в синхронную.

Дополнительные сложности возникает с порядком сообщений: как между процессами (отсутствует, FIFO), так и глобально во всей системе (отсутствует, casual ordering, synchronous ordering), глобально во всей системе с учётом multicast-broadcast (отсутствует, casual total order).

Задачи

Взаимное исключение

Почти как в параллельных системах:


Определение:
Критическая секция $CS_i$ — это пара из двух событий: $Enter(CS_i), Exit(CS_i) \in E$ (вход и выход из критической секции), при этом $Enter(CS_i) < Exit(CS_i)$ (в частности, они выполняются в одном процессе) и для всех $i$ верно: $Exit(CS_i) \to Enter(CS_{i+1})$ (т.е. критические секции линейно упорядочены).


Это требование корректности — что алгоритм не может допустить. Мы здесь нигде не пользовались словом "одновременно". Более того, нам даже не требуется вводить отдельные события входа/выхода, достаточно уже имеющихся событий отправки/получения сообщений (т.к. в системе ничего кроме сообщений принципиально происходить не может).

Также можно вводить дополнительные требования прогресса (что алгоритм должен делать), но мы это делаем неформально. Можно требовать (от более слабых к более строгим):

  1. Если "сейчас" ни один процесс в критической секции не находится, но кто-то "хочет" в неё попасть, то хотя бы один процесс рано или поздно туда попадёт.
  2. "Честность": если процесс хочет попасть в критическую секции, то он рано или поздно туда попадёт независимо от действий остальных (если они, конечно, секцию будут освобождать).

Запуск нескольких алгоритмов и перезапуск

Некоторые алгоритмы в курсе алгоритмы "одноразовые" (например, достижение консенсуса или снятие согласованного среза). Чтобы запустить их несколько раз, на практике можно запустить несколько копий алгоритма и к каждому сообщению прикреплять номер копии. Тогда они будут работать независимо друг от друга и работать корректно, хотя нет никаких гарантий про то, как они будут соотноситься между собой (например, алгоритм, запущенный позже, может завершиться раньше).

Также могут быть тонкости с "запуском" алгоритмов: например, алгоритм Чанди-Лампорта требует сохранять все отправленные с начала времён сообщения.

Ещё бывают тонкости с конфигурацией и переконфигурацией алгоритмов, особенно актуально для алгоритмов консенсуса, но это всё разбиралось лишь на семинарах.