Технологические приложения и решения спутниковой системы синхронизации GPS Beidou (служба синхронизации)

Технологические приложения и решения спутниковой системы синхронизации GPS Beidou (служба синхронизации)

Распределенная система определяется Таненбаумом: «Распределенная система — это группа независимых компьютеров, которые кажутся пользователям единой, связанной системой в книге «Распределенные системы — принципы и парадигмы».

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

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

0.Каталог

X. Блокчейн и распределенные системы

1. Введение (синхронизация и общий обзор процесса)

2. Синхронизация часов

2–1. Физические часы (часы и смещение часов)

2–2. Алгоритм синхронизации часов (Протокол сетевого времени (NTP)/алгоритм Беркли)

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

3–1. Логические часы Лэмпорта (полностью упорядоченная многоадресная рассылка)

3–2. Векторные часы (многоадресная рассылка причинно-следственной связи)

4. Эксклюзивный контроль

4–1. централизованный алгоритм

4–2. децентрализованный алгоритм

4–3. Распределенный алгоритм

5. Алгоритм выборов

5–1. алгоритм хулигана

5–2. кольцевой алгоритм

6. Блокчейны и синхронизация как распределенные системы

6–1. Блокчейн и синхронизация часов (блокчейн и физические/логические часы)

6–2. Блокчейн и эксклюзивный алгоритм управления (алгоритм эксклюзивного управления в PoW•PoS•BFT)

6–3. Блокчейн и алгоритм выбора лидера (алгоритм выбора лидера в PoW•PoS•BFT)

1. Введение (синхронизация и общий обзор процесса)

В отличие от централизованных систем, в распределенных системах договориться о времени непросто.

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

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

В этой статье синхронизация между узлами будет объяснена в следующем порядке.

Как происходит синхронизация часов?

Метод относительного упорядочения с использованием логических и векторных часов.

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

Об алгоритмах выбора лидера в распределенных системах

2. Синхронизация часов

2–1. Физические часы.

Часы и перекос часов

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

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

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

Время в реальном мире изначально основывалось на средней солнечной секунде, но теперь время 9 192 631 770 переходов цезия-133 определяется как 1 секунда и определяет Международное атомное время и Всемирное координированное время (UTC). Чтобы предоставить UTC тем, кому нужно точное время, используется WWV, и время предоставляется с точностью ± 10 миллисекунд.

2–2. Алгоритм синхронизации часов.

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

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

Определим H как количество прерываний в секунду (количество тактов), вызванных вибрациями кристалла, подсчитываемых каждой машиной, и обозначим C как значение этих часов. Пусть Cp(t) представляет значение часов машины, когда время UTC равно t.

Если p определяется как максимальная скорость дрейфа, которая определяет величину допустимого отклонения тактового сигнала, то предполагается, что он работает в следующем диапазоне.

1-p 《= dC/dt 《= 1+p

То есть после того, как прошло At секунд с момента предыдущей синхронизации, два тактовых сигнала разделяются не более чем на 2pΔt.

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

Протокол сетевого времени (NTP)

Распространенный среди многих протоколов метод, впервые предложенный [Cristian, 1989], представляет собой метод связи с клиент-сервером. Поскольку сервер времени имеет приемник WWV или точные часы, он может предоставить текущее время. При общении с сервером важно задержать сообщение о задержке распространения сообщения, но оценив задержку, здесь можно минимизировать ошибки. В настоящее время известно, что NTP способен достигать точности в диапазоне от 1 до 50 миллисекунд.

Алгоритм Беркли

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

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

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

3–1. Логические часы Лэмпорта.

Для синхронизации логических часов Лэмпорт определяет отношение, называемое «случается раньше». Выражение a → b означает «a происходит раньше b», что означает, что событие происходит первым, а затем все процессы соглашаются, что событие b произойдет. До. Эту связь можно непосредственно наблюдать в следующих двух ситуациях.

Если a и b — события одного и того же процесса и a происходит до b, то a → b истинно.

2. Если a — событие сообщения, отправленного одним процессом, а b — событие этого сообщения, полученного другим процессом, то то же самое справедливо и для a → b. Невозможно получить сообщение до его отправки, даже если это одновременно займет конечное ненулевое количество времени.

Поскольку антецедентное отношение находится в переходном отношении, если a→b и b→c, можно доказать, что a→c. Если события x,y происходят в разных процессах, которые не обмениваются сообщениями, то ни x→y, ни y→x не являются истинными, и эти события считаются одновременными. (Предыдущие отношения неизвестны.)

Используя логические часы, относительное время измеряется путем выделения согласованного времени C(a) всем процессам для каждого события a. Если эти значения времени a → b, исправьте их, добавив положительные значения ко времени так, чтобы C(a) ≧ C(b). Присвоив значения времени, как показано на рисунке ниже, вы сможете уловить взаимосвязь, которая имела место ранее.

В логических часах Лэмпорта, если a→b, можно доказать, что C(a) «C(b), но если C(a) «C(b), то a→b не обязательно верно. Другими словами, a→b — необходимое условие для C(a)

полностью упорядоченная многоадресная рассылка

Дополнительную информацию см. в статье «Согласованность распределенной системы».

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

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

3–2. Векторные часы.

Используя векторные часы, можно уловить причинно-следственные связи, которые невозможно уловить с помощью логических часов Лэмпорта. Предположим, что векторный тактовый сигнал события a равен VC(a), затем выполните следующие шаги, чтобы сделать a→b необходимым и достаточным условием для VC(a)≥VC(b).

Перед отправкой сообщения по сети узел Pi добавляет 1 к векторным часам VCi [i] или управляет некоторыми внутренними событиями.

2. Если процесс Pi отправляет сообщение m в Pj, то Pi устанавливает временную метку вектора m ts(m), равную VCi, после выполнения предыдущего шага.

3. Когда сообщение m получено, процесс Pj выполняет шаг 1, передает сообщение приложению, а затем обновляет свои собственные векторные часы для каждого k следующим образом: VCj [k] ← max {VCj [k], ts(m) [к]}.

причинно-следственная многоадресная рассылка

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

Сравнивая значения векторных часов и улавливая связь того, что произошло раньше, с конкретным событием x, другие события можно классифицировать на прошлые события, одновременные события и будущие события. Например, на приведенном выше рисунке, когда событие d используется в качестве контрольной точки, прошлые события — это a, b, c, i, одновременные события — это j, l, m, а будущие события — это f, g, h.

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

4. Эксклюзивный контроль

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

Алгоритмы распределенного эксклюзивного управления можно разделить на следующие два типа.

Решение на основе токенов

подход, основанный на разрешениях

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

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

4–1. Централизованный алгоритм.

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

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

4–2. Децентрализованный алгоритм.

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

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

4–3. Распределенные алгоритмы.

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

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

1. Если получатель не обращается к ресурсу и не пытается получить доступ к ресурсу, получатель возвращает отправителю сообщение ОК.

2. Если получатель уже обращается к ресурсу, не отвечайте и выполните запрос из очереди.

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

Очевидно, что этот алгоритм будет работать нормально, если он не конфликтует, как процесс 1 или 2. Даже в случае конфликта доступ предоставляется только одному процессу.

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

При сравнении каждого алгоритма ситуация становится следующей.

5. Алгоритм выборов лидера

Многие распределенные алгоритмы требуют специального процесса с лидером в роли координатора или инициатора. Какой процесс является лидером и может ли уникальный процесс быть лидером — важный вопрос, над которым исследователи боролись на протяжении последних нескольких десятилетий.

5–1. Алгоритм травли.

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

• P отправляет сообщение ELECTION всем процессам с более высоким значением, чем он сам.

• Если никто не отвечает, П побеждает на выборах и становится координатором.

• Если ответ приходит от процесса с более высоким значением, чем P, он будет заменен. Работа П окончена.

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

5–2. Кольцевой алгоритм.

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

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

6. Блокчейны и синхронизация как распределенные системы

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

6–1. Блокчейн и синхронизация часов.

Блокчейн и логические часы

Во-первых, подумайте, можно ли использовать физические данные в блокчейне. часы, чтобы понять соотношение абсолютного времени. Как упоминалось в главе 2, каждый узел, участвующий в сети, не всегда поддерживает правильную часы, и должен быть перекос часов. Поскольку среднее время генерации блокчейна Биткойн составляет 10 минут, даже определенная степень большого отклонения часов считается приемлемой. Однако сложно синхронизировать каждую фигуру, когда узлы разбросаны по всему миру. часы, а также могут быть узлы, маскирующиеся под часы. Введя Протокол сетевого времени (NTP) для повторной синхронизации правильного времени между узлами — сложная технология.

округ Блокчейн и логические часы

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

Как описано в [Биткойн: одноранговая электронная денежная система Сатоши Накамото], каждый узел, который выполняет операцию записи блока в качестве майнера, выполняет свою собственную роль сервера временных меток. Каждая временная метка образует цепочку, включая предыдущую временную метку в свой хэш. Однако нет никакой гарантии, что эти узлы поддерживают правильные физические часы. Числовое значение временной метки, то есть порядок и время каждой транзакции, относительно неоднозначно.

Из-за такой неоднозначности часов возможна двойная оплата. Однако в блокчейне Биткойна законной является только самая длинная цепочка, а неправильные транзакции отбрасываются после вторичной проверки. Следовательно, порядок блоков однозначно определяется во времени. По мере увеличения каждой временной метки предыдущая временная метка усиливается.

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

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

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

6–2. Блокчейн и эксклюзивные алгоритмы управления.

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

Эксклюзивный алгоритм управления PoW·PoS

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

• Решение на основе токенов

• Решения на основе разрешений

PoW и PoS основаны на разрешениях, и можно сказать, что это механизм, аналогичный распределенному алгоритму. Итак, когда вы получите доступ к ресурсу? Да, просто когда находишь случайное число.

В PoW допустимая операция записи нового блока может быть выполнена только тогда, когда найден одноразовый номер с хешем, за которым следует 0, за которым следует n из 0. Майнер, выполняющий операцию, транслирует ее всем майнерам и делится ею.

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

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

Эксклюзивный алгоритм управления типа BFT

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

В типе BFT только один узел с именем Proposer, Orderer и т. д. имеет право генерировать новые блоки. При создании блока вы можете собрать голоса всех участвующих нод и получить согласие более 2/3, прежде чем получите право на создание нового блока. Здесь необходимо согласиться, что причина более чем 2/3, а не большинства, заключается в борьбе с византийскими ошибками, подробно об этом вопросе рассказано в статье «Отказоустойчивость в распределенных системах».

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

6–3. Блокчейн и алгоритм выбора лидеров.

PoW, PoS и алгоритмы выбора лидеров

Алгоритм выбора лидера на блокчейне аналогичен механизму алгоритма эксклюзивного управления. В Биткойне алгоритм, используемый для выбора лидера, то есть узла, создающего новые блоки, — PoW.

PoW позволяет добавлять блок в качестве хорошего лидера, обеспечивая сеть Биткойн узлами с вычислительной сложностью и возможностью обнаружения nonce. Каждый майнер, который станет лидером, будет пытаться внести свой вклад в сеть Биткойн, потому что легче заранее синхронизироваться с узлом, который первым обнаруживает nonce, и начать поиск nonce следующего блока, и с большей вероятностью будет вознаграждено. Хотя существует проблема, заключающаяся в том, что цепочка полностью разветвлена ​​хардфорками, синхронизация как распределенной системы в сети блокчейн достигается путем подготовки очень простой структуры стимулов, основанной на теории игр.

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

Будущее PoS будет введено в будущем, что позволит расставить приоритеты в генерации блоков для узлов с большими запасами монет в качестве лидеров. Это алгоритм, который решает/улучшает проблему PoW, когда необходимая мощность становится огромной и уязвимой для атак 51%. Это алгоритм выборов, основанный на теории игр. Если узел содержит большое количество монет, он не будет предпринимать вредоносных действий, таких как повреждение сети.

BFT и алгоритм выбора лидера

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

В HyperLedger, принятом PBFT, в качестве Заказчиков будут регистрироваться только учреждения, которые изначально заслуживают доверия. Но это централизованный метод выбора лидеров, который явно отличается от распределенной системы.

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