Распределённые алгоритмы

Опубликовано 11 минут на чтение
Оглавление

В этой заметке разбираются базовые понятия и определения, используемые при рассмотрении распределённых систем и алгоритмов, выполняемых на них. Терминология позаимствована из книги Уона Фоккинка «Распределенные алгоритмы. Интуитивный подход»1.

Что такое распределённая система?

Определение распределённой системы базируется на определениях её базовых частей. Подходы же, применяемые в алгоритмах, рассчитанных на распределённое вычисление находят применение и за пределами распределённых систем в их базовом понимании. Поэтому будем понимать определение распредённой системы расширено.

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

Стоит отметить, что процессы не обязательно должны быть запущенны на разных компьютерах, к примеру, выполнение системного вызова по сути является обменом сообщениями с операционной системой, запуск кластера процессов стандартными средствами nodejs или выполнение параллельных вычислений на графическом процессоре тоже можно рассматривать как распределённую систему. Более того, многие среды выполнения имеют встроенные абстракции для создания сложных распределённых систем в рамках одной программы, такие как горутины в языке Go, стримы в языке Java, акторы во многих реализациях. А языке Erlang подобная абстракция позволяет программисту вообще не задумываться на скольких машинах выполняется программа, оперируя кластером компьютеров как единым целым.

Сети и топология

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

Несмотря на подобное упрощение для каналов мы будем выделять следующие характеристики:

  1. Направленность — является ли канал \(pq\) однонаправленным (то есть по нему возможна передача сообщений от процесса \(p\) к процессу \(q\), но не наоборот) или позволяет передавать сообщения в обоих направлениях (как от процесса \(p\) к процессу \(q\), так и в обратном направлении).
  2. Синхронность — совпадает ли отправка с получением по времени, либо же сообщение может некоторое время «существовать» в состоянии передачи, то есть, когда отправка уже завершена, а получение ещё не начато. Подобное поведение возможно при наличии промежуточных устройств в канале связи, способных буферизировать сообщения.
  3. Подтверждение или гарантия доставки — возможность отправителю получить подтверждение доставки сообщения получателю. Обычно это свойство гарантируется протоколом. Также стоит отметить, что асинхронные сети с подтверждением доставки можно представлять как синхронные(?).
  4. Гарантия порядка — гарантия того, что канал ведёт себя по правилу First In First Out, то есть, сообщения будут доставлены в том же порядке, что и были отправлены.
  5. Ограниченное время доставки — канал с ограниченным временем доставки позволяет рассчитывать на то, что сообщение будет доставлено не позднее, чем указанное время. Есть более слабый вариант этой характеристики, называемый, канал с ожидаемым временем доставки, когда вероятность, того, что сообщение будет доставлено с определённой задержкой тем меньше, чем больше это время (однако эта характеристика канала позволяет лишь оценить время выполнения алгоритма, но не влияет на его корректность).

Кроме того, каналы и процессы образуют своего рода (ор)граф сети. То, каким образом связываются процессы сетью, обычно называют топологией сети. Классически выделяют следующие топологии:

  • полносвязанная сеть — между любой парой процессов есть канал связи;
  • дерево — между любой парой процессов есть единственный маршрут, состоящий из каналов связи;
  • (оринетированное) кольцо — все процессы соединены в кольцо или ориентированное кольцо;
  • звезда — одноуровневое дерево;

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

Задачи

Какие же задачи необходимо решать в такого рода системах? Так сложилось, что развитие вычислительных устройств, несмотря на геометрический рост, достигло своего предела в скорости выполнения операций. Уменьшение размеров полупроводников вызывает квантовые эффекты, с которыми мы только учимся работать. Вместо вертикального роста, куда более простым оказался горизонтальный, многоядерные архитектуры процессоров уже давно стали нормой. С другой стороны куда быстрее растут объёмы данных, над которыми необходимо выполнять операции. Хотя объёмы памяти, доступные для современных компьютеров, также растут, часто возникают задачи распределённого хранения и обработки данных. Другой причиной развития распределённых систем стала необходимость отказоустойчивости современных программ. Представьте, если бы данные вашего банка хранились на одном единственном компьютере, который внезапно вышел из строя. Задачи, решаемые распределёнными системами, возникают каждый день, однако, методы и подходы распределённых алгоритмов являются неизменными кирпичами, из которых строятся современные системы. Вот некоторые из них:

  • синхронизация состояния;
  • конкурентный доступ к состоянию;
  • совместное принятие решения;
  • выбор лидера;
  • обнаружение блокировок;
  • обнаружение завершения;
  • маршрутизация сообщений;
  • резервирование данных;
  • устойчивость к сбоям;
  • устойчивость к внедрению злоумышленников;

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

События

Для описания функционирования распределённых систем удобно использовать такое понятие как событие. Событием будем называть изменение состояния системы. События бывают следующих видов:

  • внутреннее (internal) событие изменения внутреннего состояния одного из процессов системы;
  • отправка (send) событие отправки сообщения от одного процесса другому;
  • получение (receive) событие получения процессом сообщения, ранее отправленного ему другим процессом;

Каузуальный порядок

События, происходящие в распределённой системе, имеют частичный порядок: каузуальный порядок или порядок причинности. Так при передачи сообщение от одного процесса другому, событие отправки предшествует событию получения. Событие же изменения внутреннего состояния в следствии получения сообщения, наступает позже получения. Таким образом мы можем частично упорядочить события. Например, пусть процесс \(p\) отправил процессу \(q\) сообщение \(\langle +1 \rangle\), а затем отправил процессу \(r\) сообщение \(\langle -1 \rangle\). Получив сообщение \(\langle +1 \rangle\), процесс \(q\) увеличил счётчик в своём внутреннем состоянии на единицу, а процесс \(r\), получив сообщение \(\langle -1 \rangle\), уменьшил свой счётчик. Тогда, мы имеем следующие произошедшие события:

  1. процесс \(p\) отправил процессу \(q\) сообщение \(\langle +1 \rangle\) (send);
  2. процесс \(p\) отправил процессу \(r\) сообщение \(\langle -1 \rangle\) (send);
  3. процесс \(q\) получил от процесса \(p\) сообщение \(\langle +1 \rangle\) (receive);
  4. процесс \(r\) получил от процесса \(p\) сообщение \(\langle -1 \rangle\) (receive);
  5. процесс \(q\) изменил внутреннее состояние (internal);
  6. процесс \(r\) изменил внутреннее состояние (internal);

При этом мы можем утверждать, что событие 2 произошло позже, чем событие 1 (\(1 \prec 2\)), событие 3 произошло позже события 1 (\(1 \prec 3\)), но при этом мы не можем ничего сказать про порядок событий 2 и 3.

graph LR A(1: p send q) --> B(2: p send r) A --> C(3: q receive by p) B --> D(4: r receive by p) C --> E(5: q change state) D --> F(6: r change state)
Рис. 1.

Будем говорить, что событие \(a\) каузуально предшествует событию \(b\) (\(a \prec b\)), если выполнено одно из следующих условий:

  • оба события произошли в одном процессе и событие \(a\) произошло раньше события \(b\);
  • \(a\) является событием отправки сообщения, а \(b\) — событием получения этого сообщения;
  • существует событие \(c\), такое что: \(a \prec c\) и \(c \prec b\) (правило транзитивности);

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

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

Вычислением распределённого алгоритма будем называть последовательность смены конфигураций системы. Вычисление может быть конечным или бесконечным. Но, если вернуться к примеру выше, где процесс \(p\) отправлял сообщения процессам \(q\) и \(r\), то надо заметить, что приведённый порядок лишь один из возможных. Действительно, утверждая, что событие 1 предшествует событию 2, мы ничего не можем сказать про порядок событий 2 и 3. Такие события называются независимыми, несравнимыми или параллельными. Таким образом, мы можем записать следующее вычисление, результат которого будет эквивалентен приведённому выше:

  1. процесс \(p\) отправил процессу \(q\) сообщение \(\langle +1 \rangle\) (send);
  2. процесс \(q\) получил от процесса \(p\) сообщение \(\langle +1 \rangle\) (receive);
  3. процесс \(q\) изменил внутреннее состояние (internal);
  4. процесс \(p\) отправил процессу \(r\) сообщение \(\langle -1 \rangle\) (send);
  5. процесс \(r\) получил от процесса \(p\) сообщение \(\langle -1 \rangle\) (receive);
  6. процесс \(r\) изменил внутреннее состояние (internal);

Упорядочивание параллельных событий называется сериализацией (serialization). Количество возможных вариантов сериализации таких событий комбинаторно возрастает с ростом параллельных событий(?). При этом алгоритм должен корректно вести себя для любого варианта сериализации. Таким образом множество конфигураций образует ориентированный граф, где каждая дуга \((\gamma\delta)\) предполагает возможное событие в системе, переводящее её из конфигурации \(\gamma\) в конфигурацию \(\delta\) и называется переходом из конфигурации \(\gamma\) в конфигурацию \(\delta\).

Таким образом поведение распределённой системы можно описать следующей тройкой:

  • множество конфигураций \(\Gamma\);
  • бинарное отношение перехода \(\to\), определённого на множестве \(\Gamma\);
  • множество начальных конфигураций \(I \subseteq \Gamma\).

Тройку \((\Gamma, \to, I)\) будем называть системой переходов.

Конфигурацию будем называть терминальной, если не существет исходящего из неё перехода. Тогда вычисление можно определить как маршрут в орграфе \((\Gamma, \to)\), начинающийся в вершине из множества \(I\) и заканчивающийся в терминальной вершине, либо зацикливающийся для бесконечного вычисления.

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

Логические часы

Частой задачей в распределённой системе является поддержание некоторой абстракции для восстановления каузуального порядка событий. Эта задача возникает из того ограничения, что в системе из нескольких компьютеров трудно поддерживать единое абсолютное время. Не смотря на технологии синхронизации часов, такие как NTP, компьютеры могут «дрейфовать» по времени. (Хотя, есть системы опирающиеся на синхронное абсолютное время5) С другой стороны для многих задач и нет необходимости в абсолютном времени, требуется лишь разрешить каузуальный порядок событий. Такая абстракция называется логические часы: логическими часами будем называть отображение \(С\) действующее из множества событий в частично упорядоченное множество, сохраняющее порядок (изотонное или монотонное отображение):

\[ a \prec b \Rightarrow C(a) < C(b). \]

Одним из вариантов построения логических часов являются часы Лэмпорта6: каждому событию в соответствие ставится длинная самой длинной цепочки каузуально упорядоченных событий, предшествующих ему. То есть в приведённом выше примере, внутреннему событию \(a\) изменения состояния процесса \(q\) каузуально предшествует два события: отправка и получение сообщения, а внутреннему событию \(b\) изменения состояния процесса \(r\) каузуально предшествует три события: две отправки и одно получение. Другими словами \(LC(a) = 2\), а \(LC(b) = 3\), где \(LC\) — часы Лэмпорта.

Часы Лэмпорта удовлетворяют определению логических часов, но имеют один существенный недостаток: они могут упорядочивать параллельные события. Действительно, события \(a\) и \(b\) являются параллельными, то есть мы не можем утверждать, что одно из них обязательно должно наступить раньше другого. Однако, если ориентироваться на часы Лэмпорта, получается, что событие \(b\), наступило позже события \(a\). Другими словами, часы Лэмпорта являются монотонным отображением, но не изоморфным.

Для получения изоморфизма, можно воспользоваться векторными часами: каждому событию в соответствии ставится вектор, где каждому процессу системы \(p_i\) сопоставлена \(i\)-я компонента, которая равна количеству событий этого процесса, каузуально предшествующих данному событию. Например, пусть процессу \(p\) будем сопоставлять нулевую компоненту, процессу \(q\) — первую, а \(r\) — вторую. Тогда значение векторных часов для события \(a\) будет равно вектору \((1, 1, 0)\), а \(V\!C(b) = (2, 0, 1)\). Сравнивать же получившиеся вектора будем по следующему правилу:

\[ (k_0, k_1, \ldots, k_{N-1}) \leqslant (\ell_0, \ell_1, \ldots, \ell_{N-1}) \iff k_i \leqslant \ell_i, \forall i = 0, \ldots, N-1 \]

Утверждения

Говоря о конфигурациях распределённой системы, можно ввести такое понятие как утверждение — предикат относительно конфигурации, то есть отображение множества \(\Gamma\) в двоеточие \(\{0, 1\}\) (будем говорить, что утверждение \(P\) выполнено для конфигурации \(\gamma\), если \(P(\gamma) = 1\), иначе будем говорить, что утверждение не выполнено).

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

Будем называть утверждение инвариантом, если оно выполнено для всех начальных конфигураций, а также, если оно выполнено для конфигурации \(\gamma\) и существует переход \(\gamma \to \delta\), то оно выполнено и для конфигурации \(\delta\). Очевидно, что инвариант является свойством безопасности, но наоборот(?).

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

Управляющий и базовый алгоритмы

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

Задания

  1. Подумайте, каким образом можно поддерживать часы Лэмпорта в распределённой системе? Сыграйте втроём или вчетвером в «подкидного», где каждое взятие или выкладывание карты на стол является событием. Посчитайте значение часов Лэмпорта для каждого события партии.
  2. Докажите, что векторные часы являются изоморфизмом.

Вопросы

  1. ^ Как асинхронную сеть с подтверждением можно свести к синхронной?
  2. ^ Сколько существует вариантов сериализации событий, приведённых на рисунке 1?
  3. ^ Придумайте свойство безопасности, не являющееся инвариантом.

  1. Уон Фоккинк Распределенные алгоритмы. Интуитивный подход — СПб.: Питер, 2016 — 272 с. ↩︎

  2. https://ru.wikipedia.org/wiki/Конечный_автомат ↩︎

  3. https://ru.wikipedia.org/wiki/Сетевая_модель_OSI ↩︎

  4. Блог Афира, где он публикует результаты тестов распределённых систем на соответствие заявленным гарантиям: https://aphyr.com/ ↩︎

  5. Облачная база данных Spanner, разработанная внутри Google, опирается на атомные часы, находящиеся в непосредственной близости от каждого сервера https://cloud.google.com/spanner/docs/true-time-external-consistency ↩︎

  6. Lamport L. Time, clocks, and the ordering of events in a distributed systems — Communications of the ACM, 1978 — Vol. 21 — P. 558–565. ↩︎