Распределенные системы предлагают нам возможность решать проблемы, которые мы не могли решить с помощью одной машины. Однако недавно я с болью осознал, что каждое решение проблемы влечет за собой ряд новых проблем и соображений, которые необходимо учитывать.
В сфере распределенных систем одна из самых больших проблем, с которыми мы сталкиваемся по поводу одной машинной системы, - это попытка сохранить правильную временную шкалу событий. Это необходимо по разным причинам - одна из самых важных - это понимание порядка и причинности событий в вашей системе. Это то, что позволяет проводить анализ при оценке того, почему ваша система выполнила определенное действие.
Например, если вы хотите узнать, почему определенное значение было записано в вашу базу данных, вы можете найти серию событий, ведущих к моменту создания запроса INSERT. Затем вы можете разместить эти события в хронологическом порядке, используя их временные метки, переходя от последнего к самому старому, чтобы понять причинно-следственную связь действий, ведущих к записи окончательного значения [Рисунок 1].
Когда у нас есть одна машина, график событий создать относительно легко, даже если у нас есть несколько процессов (потоков), создающих события. Это связано с тем, что все события в процессах используют одни и те же P hysical Clock. Когда каждое из этих событий регистрирует время, в которое оно было выполнено, мы можем гарантировать при построении временной шкалы, что все события будут размещены в правильном порядке относительно друг друга. Это связано с тем, что одни и те же P hysical Clock используются для всех временных меток, обеспечивая единое глобальное представление времени [рисунок 2].
Однако, когда мы переходим к распределенной системе, мы больше не можем полагаться на это свойство. Давайте рассмотрим наш предыдущий пример, чтобы доказать это. Если у нас есть события, ведущие к INSERT, которые теперь происходят на нескольких машинах, каждая со своими локальными часами, и мы используем временные метки для размещения событий в хронологическом порядке, теперь мы должны гарантировать, что часы всех машин имеют точное время. Это известно как наличие глобальных часов, и этого нелегко добиться в распределенной системе [рисунок 3].
Вместо этого распределенная система действительно имеет приблизительное значение P физического времени на всех своих машинах. Приближение может быть достаточно хорошим, если события происходят нечасто, поскольку вы всегда сможете расположить события в правильном хронологическом порядке, пока часы каждой машины остаются синхронизированными в пределах некоторого приемлемого порога. Хотя для большинства распределенных систем это недостаточно хорошая гарантия. Следовательно, мы должны найти виртуальный способ выражения времени между машинами, чтобы мы могли сохранить возможность помещать события в точную временную шкалу. Это понятие логических часов.
Логические часы относятся к реализации протокола на всех машинах в вашей распределенной системе, чтобы машины могли поддерживать согласованный порядок событий в течение некоторого виртуального промежутка времени. Это более формально определено как способ размещения событий в некотором промежутке времени, поэтому следующее свойство всегда будет истинным:
Даны 2 события (e1, e2), где одно вызвано другим (e1 способствует возникновению e2). Тогда отметка времени «вызванного» события (e1) меньше, чем у другого события (e2).
Для обеспечения этой функции любые логические часы должны обеспечивать 2 правила:
Правило 1: это определяет, как локальный процесс обновляет свои собственные часы при возникновении события.
Правило 2: определяет, как локальный процесс обновляет свои собственные часы, когда он получает сообщение от другого процесса. Это можно описать как то, как процесс приводит свои локальные часы в соответствие с информацией о глобальном времени.
Самая простая реализация этого метода - Скалярное время. В этом представлении каждый процесс поддерживает локальные часы, которые изначально установлены на 0. Затем он обеспечивает следующую реализацию 2 правил:
Правило 1: перед выполнением события (исключая событие получения сообщения) увеличьте локальные часы на 1.
local_clock = local_clock + 1
Правило 2: при получении сообщения (сообщение должно включать значение локальных часов отправителя) установите локальные часы на максимум из полученного значения часов и значения локальных часов. После этого увеличьте локальные часы на 1 [рисунок 4].
1. local_clock = max (локальные_clock, полученные_clock)
2. local_clock = local_clock + 1
3. сообщение становится доступным.
Мы видим, что Скалярное время обеспечивает в конечном итоге согласованное состояние времени. Это означает, что могут быть места, где зарегистрированное время различается между процессами, но, учитывая конечный промежуток времени, процессы сходятся в едином представлении точного времени. Причиной этого является тот факт, что внутренние события в процессе (которые применяют Правило 1) теряют согласованность в отношении одновременных событий в другом процессе (красные события на рисунке 4). Это связано с использованием одного числа как для наших глобальных, так и для локальных часов во всех процессах. Чтобы стать причинно-связным, нам нужен способ представления местного и глобального времени по отдельности. Здесь на помощь приходят векторные часы.
Векторные часы расширяют понятие скалярного времени, чтобы обеспечить причинно-следственную связь с миром. Это означает, что, посмотрев на часы, мы можем увидеть, повлияло ли одно событие на другое (вызвало) другое. При таком подходе каждый процесс хранит вектор (список целых чисел) с целым числом для каждых локальных часов каждого процесса в системе. Если есть N процессов, каждый процесс будет поддерживать вектор размера N. Для процесса (Pi) с вектором (v) Векторные часы реализуют правила логических часов следующим образом:
Правило 1: перед выполнением события (исключая событие получения сообщения) процесс Pi увеличивает значение v [i] в своем локальном векторе на 1. Это элемент в векторе, который относится к процессору. (i) местные часы.
локальный_вектор [я] = локальный_вектор [я] + 1
Правило 2: при получении сообщения (сообщение должно включать вектор отправителя) перебрать каждый элемент в отправленном векторе и сравнить его с локальным вектором, обновляя локальный вектор до максимума каждого элемента. . Затем увеличьте локальные часы в векторе на 1 [рисунок 5].
1. для k = от 1 до N: local_vector [k] = max (local_vector [k], sent_vector [k])
2. local_vector [i] = local_vector [i] + 1.
3. сообщение становится доступным.
Векторные часы обеспечивают причинно-следственный порядок событий, однако за это приходится платить. Вы можете видеть, что нам нужно отправлять весь вектор каждому процессу для каждого отправленного сообщения, чтобы синхронизировать векторные часы. При большом количестве процессов этот метод может стать чрезвычайно дорогостоящим, так как отправляемый вектор чрезвычайно велик. По сравнению с упомянутой первоначальной реализацией векторных часов было внесено много улучшений, в частности:
- Дифференциальный метод Сингала – Кшемкаляни [1]: этот подход улучшает механизм передачи сообщений, отправляя только обновления векторных часов, которые произошли с момента последнего сообщения, отправленного из Процесса (i) → Процесс (j). Это резко уменьшает размер отправляемого сообщения, но требует хранения O (n²). Это связано с тем, что теперь каждый узел должен помнить для каждого другого процесса состояние вектора в последнем отправленном сообщении. Это также требует передачи сообщений FIFO между процессами, поскольку это зависит от гарантии знания того, какое сообщение было отправлено последним, и если сообщения приходят не по порядку, это будет невозможно.
- Метод прямой зависимости Фаулера-Цваенепола [2]: этот метод дополнительно уменьшает размер сообщения, отправляя только одно значение часов отправляющего процесса с сообщением. Однако это означает, что процессы не могут знать свои транзитивные зависимости при рассмотрении причинности событий. Чтобы получить полное представление обо всех зависимостях, которые приводят к определенному событию, необходимо выполнить автономный поиск по процессам.
В заключение мы видим, что когда мы переходим к распределенной системе, поддержание порядка становится сложной проблемой. Чтобы решить эту проблему, мы должны создать искусственное представление о времени, известное как логическое время. Есть много решений, которые обеспечивают реализацию логического времени. Скалярные часы предлагают наивное решение проблемы, обеспечивая в конечном итоге согласованный порядок событий. Векторные часы затем основываются на этой технике, разделяя локальные и глобальные часы процессов, что означает, что порядок событий может быть причинно согласован. Кроме того, в векторные часы внесены улучшения для повышения их производительности за счет увеличения объема памяти или необходимости выполнения анализа причинно-следственной связи в автономном режиме.
Эта статья основана на книге «Распределенные вычисления: принципы, алгоритмы и системы» [3], которую я настоятельно рекомендую прочитать.
Надеюсь, вам понравилось читать. :)
Использованная литература:
[1]: Сингхал, М. и Кшемкаляни, А.Д., 1992. Эффективная реализация векторных часов. Письма об обработке информации, 43 (1), стр. 47–52.
[2]: Fowler, J. и Zwaenepoel, W., 1990, May. Причинно-распределенные точки останова. В Распределенные вычислительные системы, 1990. Труды., 10-я Международная конференция по (стр. 134–141). IEEE.
[3]: Кшемкаляни, А.Д. и Сингхал, М., 2011. Распределенные вычисления: принципы, алгоритмы и системы. Издательство Кембриджского университета.
