Время и глобальное состояние
Время и глобальное состояние определяют, как распределенная система упорядочивает события и рассуждает о своем коллективном состоянии при отсутствии общих часов и мгновенного глобального представления.
Definition
В распределенной системе события происходят в отдельных процессах без общих часов; изучение времени и глобального состояния предоставляет отношения и алгоритмы — логические и векторные часы, снимки и упорядоченную доставку — которые позволяют системе причинно упорядочивать события и фиксировать согласованные глобальные состояния.
Scope
Эта область охватывает логические часы и отношение предшествования (happened-before), синхронизацию физических часов, векторные часы и обнаружение причинности и параллелизма, определение согласованных глобальных снимков, а также гарантии упорядочивания (FIFO, причинное, полное), необходимые для надежной многоадресной рассылки. Вместе эти инструменты позволяют распределенным системам делать осмысленные утверждения о «когда» и «в каком состоянии», несмотря на отсутствие глобальных часов.
Sub-topics
Core questions
- Как можно упорядочить события в разных процессах без общих физических часов?
- Как процесс может определить, являются ли два события причинно связанными или параллельными?
- Как можно записать согласованный глобальный снимок, пока вычисления продолжаются?
- Какие гарантии упорядочивания доставки сообщений необходимы для сохранения причинности?
Key theories
- Отношение предшествования (Happened-before) и логические часы
- Отношение предшествования (happened-before) Лэмпорта определяет частичный причинный порядок событий, а логические (скалярные) часы присваивают временные метки, согласующиеся с ним, предоставляя понятие порядка, не зависящее от часов и достаточное для построения полного порядка для многих протоколов.
- Векторные часы и причинность
- Векторные часы расширяют логические часы таким образом, что сравнение двух временных меток точно определяет, предшествует ли одно событие другому причинно или являются ли они параллельными, что позволяет точно отслеживать причинность.
- Согласованные глобальные снимки
- Алгоритм снимков Чанди-Лэмпорта записывает согласованное глобальное состояние — состояния процессов плюс сообщения в пути — без остановки системы, путем распространения маркеров по каналам.
Clinical relevance
Логические и векторные часы лежат в основе причинной согласованности, обнаружения конфликтов в реплицированных хранилищах и отладки распределенных выполнений; согласованные снимки лежат в основе распределенного контрольного суммирования, обнаружения взаимоблокировок и завершения, а также восстановления после сбоев потоковой обработки.
History
Статья Лэмпорта 1978 года представила логическое время и отношение предшествования (happened-before), что является одним из наиболее цитируемых результатов в информатике; Чанди и Лэмпорт формализовали согласованные глобальные снимки в 1985 году; а Фидж и Маттерн независимо разработали векторные часы в конце 1980-х годов, завершив базовый инструментарий для рассуждений о времени и состоянии.
Key figures
- Leslie Lamport
- K. Mani Chandy
- Colin Fidge
- Friedemann Mattern
Related topics
Seminal works
- lamport1978
- chandy1985
- fidge1988
Frequently asked questions
- Почему распределенные системы не могут просто использовать синхронизированные физические часы?
- Физические часы дрейфуют и не могут быть идеально синхронизированы по сети с переменной задержкой, поэтому порядок событий в реальном времени может быть неоднозначным. Логические и векторные часы вместо этого фиксируют причинный порядок, который действительно важен для корректности.
- Что делает глобальный снимок «согласованным»?
- Снимок является согласованным, если всякий раз, когда он включает получение сообщения, он также включает отправку этого сообщения. Такое состояние могло произойти во время выполнения, хотя ни один отдельный момент никогда не наблюдался глобально.