GoProg

 
Топ хэштегов


Архив

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

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

Правила обновления векторных часов

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

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

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

Например, в среде с четырьмя процессорами P0,… P3, процесс P1 будут «владеть» вторым элементом вектора.

Если процесс P0 имеет четыре последовательных события, a, b, c, d, они получат векторные метки времени (1,0,0), (2, 0, 0), (3, 0, 0), (4, 0, 0). Если процесс P2 имеет четыре последовательных события, a, b, c, d, они получат векторные временные метки (0,0,1), (0, 0, 2), (0, 0, 3), (0, 0, 4). Если одно событие на P1 равно (2, 4, 0, 1), то следующим событием на P1 будет (2, 5, 0, 1).

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

Мы можем проиллюстрировать это с помощью следующего псевдокода, где system - это счетчик векторов системы, а received - это полученная временная метка вектора:

for (i=0; i < num_elements; i++) 
  if (received[i] > system[i])
    system[i] = received[i];

Сравнение временных меток

Мы можем определить, являются ли два события одновременными или причинно-следственными, сравнивая их временные метки. Сравнение производится поэлементно, то есть сравниваем значения P0, затем P1 и т. Д.

Две временные метки вектора равны, если каждый соответствующий элемент одного вектора совпадает с другим.

Векторная отметка времени v меньше, чем векторная отметка времени w, если v и w не равны и каждый элемент v меньше или равен соответствующему элементу w:

is_smaller(int v[], w[]) {
	result = true;
	for (i=0; i < num_elements; i++)
		if (v[i] > w[i])
			smaller = false;
	return result;

Два события являются одновременными, если одна временная метка вектора не больше и не меньше, чем другой элемент, при поэлементном сравнении.

Например, события (2, 4, 6, 8) и (3, 4, 7, 9) не являются параллельными (то есть они причинно связаны), потому что каждый элемент первого вектора меньше или равен соответствующему элемент второго вектора.

Векторы (2, 4, 6, 8) и (1, 5, 4, 9) представляют собой одновременные события. Ни один из векторов не меньше и не больше другого. Например, 2> 1 (первый элемент первого вектора больше первого элемента второго вектора), но 4 (второй элемент первого вектора меньше второго элемента второго вектора).

Примеры векторных часов

На рисунке ниже показан тот же набор событий, который мы видели ранее, но с назначениями векторных часов. Событие b - это отправка сообщения на P1. Это сообщение содержит метку времени события b: (2, 0, 0). Событие i - это получение этого сообщения. Если бы я был локальным событием, он получил бы отметку времени (0, 2, 0). Поскольку это получение сообщения, мы проводим поэлементное сравнение значений в полученной метке времени и локальной метке времени, выбирая наивысшее из каждой пары чисел:

Сравните (2, 0, 0) с полученной меткой времени (0, 2, 0).

  • Первый элемент: 2 против 0: 2 больше и побеждает.
  • Второй элемент: 0 против 2: 2 больше и побеждает.
  • Третий элемент: 0 против 0: ничья, поэтому 0 побеждает.

Результирующий вектор, следовательно, (2, 2, 0) присваивается событию i, а также системным часам. Следующее локальное событие на P1 будет помечено (2, 2 + 1, 0) или (2, 3, 0).

Чтобы определить, являются ли два события, V и W, одновременными, выполните поэлементное сравнение соответствующих временных меток. Если каждый элемент временной метки V меньше или равен соответствующему элементу временной метки W, тогда V причинно предшествует W и события не являются параллельными. Если каждый элемент временной метки V больше или равен соответствующему элементу временной метки W, то W причинно предшествует V и события не являются параллельными. Если, с другой стороны, ни одно из этих условий не применяется, и некоторые элементы в V больше, чем другие, а другие меньше, чем соответствующий элемент в W, то события являются параллельными. Мы можем резюмировать это с помощью псевдокода:

isconcurrent(int v[], int w[])
{
  bool greater=false, less=false;

  for (i=0; i < num_elements; i++) 
    if (v[i] > w[i])
      greater = true;
    else (v[i] < w[i])
      less = true;
    if (greater && less)
      return true;
    else
      return false;
}

На рисунке выше отметка времени для e меньше, чем отметка времени для j, потому что каждый элемент в e меньше или равен соответствующему элементу в j. То есть 5 ≤ 6, 1 ≤ 3 и 2 ≤ 2. События причинно связаны и e → j

С другой стороны, события f и m совпадают. Когда мы сравниваем первый элемент f с m, мы видим, что f> m (6> 4). Когда мы сравниваем второй элемент, мы видим, что f = m (1 = 1). Наконец, когда мы сравниваем третий элемент, мы видим, что f (2 ). Из-за этого мы не можем сказать, что вектор для f меньше или больше вектора для m.

Обобщение отметки времени

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

Мы можем заменить вектор набором кортежей, каждый из которых представляет идентификатор процесса и его счетчик:

({P0, 6}, {P1, 3}, {P2, 2})

Когда процесс отправляет вектор, он отправляет весь набор кортежей, которые у него есть. В случае получения вектора - выполняет сравнение, он сравнивает каждую связанную пару. Например, значение P0 будет сравниваться с кортежем, содержащим P0 в полученном векторе. Если в одном из наборов отсутствуют какие-либо идентификаторы процессов, им неявно присваивается значение 0 для сравнения. Результирующий вектор содержит множество всех кортежей.

Например, если у процесса есть системные векторные часы:

({P0, 6}, {P1, 3}, {P2, 2})

и получает значение

({P1, 1}, {P2, 5}, {P3, 8})

Результирующий вектор будет набором всех идентификаторов процессов и их наибольших значений:

({P0, 6}, {P1, 3}, {P2, 5}, {P3, 8})

#IT #векторноевремя #ИТ #распределенныесистемы



Новый комментарий: