Глобальные снимки состояния и их состояние

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

Definition

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

Scope

Эта тема охватывает понятие согласованного глобального состояния и разреза, который его определяет, алгоритм снимков Чанди-Лампорта на основе маркеров и его допущения (FIFO-каналы, надежная доставка), а также применение снимков для обнаружения стабильных свойств, таких как завершение и обнаружение взаимоблокировок, а также для распределенного контрольного суммирования и восстановления.

Core questions

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

Key theories

Согласованные разрезы

Глобальное состояние соответствует разрезу последовательностей событий процессов; разрез является согласованным тогда и только тогда, когда он замкнут относительно отношения «произошло до», гарантируя, что ни одно сообщение не будет получено до того, как оно будет отправлено в записанном состоянии.

Алгоритм снимков Чанди-Лампорта

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

Обнаружение стабильных свойств

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

Clinical relevance

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

History

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

Key figures

• K. Mani Chandy
• Leslie Lamport
• Friedemann Mattern

Seminal works

• chandy1985
• mattern1989
• lynch1996

Frequently asked questions

Требуется ли приостановка системы для создания снимка?

Нет. Алгоритм Чанди-Лампорта записывает согласованное глобальное состояние, пока вычисление продолжается, путем распространения маркеров по каналам; записанное состояние является одним из тех, в которых система могла находиться, хотя она никогда не была глобально остановлена.