В этой серии мы видели много примеров того, как все может быть сложнее, чем кажется. Мы видели это с неудачей, мы видели это с репликацией. Совсем недавно мы обнаружили, что даже концепция времени более сложна, чем мы могли изначально думать.
Однако, когда вещи, которые, как вы думали, вы знали, кажутся более запутанными, чем когда-либо, иногда ответ прост. Другими словами, мы можем упростить задачу, удалив запутанные части и сократив ее до самых важных частей. Фактически, этот подход - именно то, что сделал один ученый-компьютерщик в конце 70-х, когда он, как и мы, пытался понять, как понять время в распределенной системе.
Предыдущие два сообщения о часах и упорядочивании событий в распределенной системе были построены на теме, которую мы наконец-то готовы раскрыть: логическое время и часы Лампорта! Нам есть о чем поговорить, поэтому мы разложим это между двумя сообщениями. Давайте перейдем к первой части!
Причинность и «случилось раньше»
История логических часов началась в 1978 году, когда в журнале Communications of ACM была опубликована статья, которая вошла в историю. Лесли Лэмпорт, специалист по информатике из Massachusetts Computer Associates, написал о своем исследовании упорядочивания событий в распределенной системе. Эта статья, озаглавленная Время, часы и порядок событий в распределенной системе, станет одной из самых цитируемых работ в области компьютерных наук, а также получит престижную премию Принципы распределенных вычислений. более чем 20 лет спустя.
В статье Лэмпорт описывает, как мы думаем о времени как люди, и почему нам нужно изменить нашу парадигму, когда речь идет о распределенных системах, а также об идее частичного упорядочивания. Он объясняет, что В распределенной системе иногда невозможно сказать, что одно из двух событий произошло первым.
Как цитирует Лэмпорт в своей статье, причина того, что мы заботимся о времени, заключается в том, что мы можем выяснить порядок, в котором что-то происходит. Хотя это, безусловно, труднее (а иногда и невозможно!) Сделать в распределенной системе, наша причина, по которой мы хотим знать порядок некоторых событий в системе, все проистекает из одного и того же желания: мы заботимся о упорядочивание событий, чтобы мы могли определить, как эти события связаны. Когда мы имеем дело с событиями в любой системе, причина, по которой мы действительно хотим их упорядочить, заключается в том, чтобы мы могли видеть цепочку событий в системе. В частности, в распределенной системе это означает, что мы часто пытаемся определить, влияет ли событие на одном узле на событие на другом узле или вызывает его.
Но, как мы убедились в нашем собственном исследовании распределенных систем, эта задача - нелегкая задача. Когда система распределена, нет глобальных часов, что означает, что мы не можем зависеть от какого-либо центрального источника времени. Это также означает, что события в нашей системе не полностью упорядочены, а это означает, что мы не можем быть уверены в том, когда каждое событие в системе произошло. В статье Лэмпорта признаются все эти ограничения и отмечается, насколько сложна эта проблема на самом деле!
Решение Лампорта - изменить наше мышление. Он предлагает новую идею: на самом деле нам не нужно думать о причинно-следственной связи в контексте тотального порядка, чтобы начать. Вместо этого он говорит, что мы можем начать с частичного упорядочивания событий, а затем просто выяснить, какие события произошли до других событий. Как только мы выясним частичный порядок, мы можем превратить его в согласованный тотальный порядок.
Итак, как мы это сделаем? Итак, для начала нам нужно перейти от размышлений о том, когда событие произошло, на то, что событие произошло до.
Переход от «когда» к «до»
Идея о том, что одно событие происходит раньше другого, занимает центральное место в статье Лампорта. Он использует сокращенную запись → для обозначения отношения происходит до или того факта, что одно событие произошло раньше другого. Например, если мы знаем, что одно событие a произошло до другого события, b, то мы можем сказать, что a → b или a произошло до b.
Связь «происходит до» также может применяться транзитивно. Другими словами, мы можем создать цепочку событий, в которой одно событие произошло раньше другого. Если мы скажем, что a → b и b → c, то, используя свойство транзитивности, мы можем сказать, что a → c , или a произошло до c. Как мы могли бы представить, мы могли бы очень легко связать цепочку событий, где одно событие происходит раньше другого, которое происходит раньше другого, и так далее и тому подобное.
Но подождите секунду - мы продолжаем говорить о разных событиях в системе, но мы еще не совсем прояснили, каким может быть событие! Как выясняется, событие в распределенной системе может принимать разные формы. Как известно, в распределенной системе может быть много разных узлов. Каждый узел имеет свои собственные локальные системные часы и способен обрабатывать свои собственные задачи. Однако узлы также могут обмениваться данными друг с другом, отправляя сообщения туда и обратно.
Событие включает в себя все различные вещи, которые могут происходить внутри и между узлами в системе. Событие может быть чем-то, что происходит в отдельном процессе или узле. Событие также включает любые события отправки, когда узел отправляет сообщение другому узлу или процессу. И наоборот, мы также должны учитывать события приема, когда узел получает входящее сообщение из другого места в системе.
В приведенном выше примере мы видим примеры всех трех этих событий. У нас есть два процесса, P и Q. В процессе Q происходит одно событие Q3, не связанное с отправкой или получением каких-либо сообщений. Это наше основное событие, которое указывает, что что-то произошло на узле для процесса Q. Однако у нас также есть несколько событий отправки: P1, Q1, Q4. Все эти события указывают на то, что мы отправляем сообщения из узла в другое место в системе. С другой стороны, P2, P3 и Q2 являются событиями приема, которые указывают, что мы получили какое-то сообщение от другого узла в системе.
Теперь, когда мы понимаем, каким может быть событие в системе, мы можем вернуться к тому, что произошло до отношений. Когда мы говорим, что событие a → b, мы утверждаем, что событие a произошло до b , потому что a произошло до b. Мы можем сказать, что эти два события являются причинно-следственными, где порядок событий зависит от того, одно событие вызывает другое.
Есть несколько правил причинного упорядочивания, которые нам важно понять. Для причинно-следственной связи a → b должна выполняться одна из следующих трех ситуаций:
- События a и b должны происходить в одном и том же процессе , и a должно произойти до того, как в процессе произойдет b.
- События могут происходить в разных процессах, если a является событием отправки. что соответствует b, которое должно быть его событием приема.
- События транзитивно связаны с другим событием в системе, но a все еще происходит до b. Например, если a происходит до c, а c происходит до b, то мы знаем, что а → б.
По мере того, как сообщения перемещаются во времени и пространстве от одного процесса к другому, мы можем начать строить цепочки причинно-следственных событий (также называемые причинными путями) и посмотреть, как разные события проходят через процессы связаны друг с другом. Например, в процессах P и Q, Q1 → P3 (через событие P2) и P1 → Q4 (через события Q2 и Q3).
Наконец, стоит упомянуть, что если два события a и b не происходят друг перед другом, то мы можем сказать, что a ≠ ›b и b ≠ ›a, и что эти два события являются одновременными. Мы рассмотрим это более подробно во второй части этого поста, а пока мы должны просто отметить, что у параллельных событий нет причинных путей от одного к другому.
Логические часы на сцену
В дополнение к идее случилось раньше, еще одна основная концепция, которую Лэмпорт вводит в своей статье, - это логические часы. Как мы уже знаем, каждый узел или процесс в распределенной системе имеет собственное понятие времени или свои собственные локальные часы. Однако взгляд Лампорта на местные часы отличается от того, что мы видели раньше.
Лэмпорт предлагает использовать что-то отличное от обычных физических часов, о которых мы все думаем. Вместо использования физических часов каждого процесса для отслеживания порядка событий мы можем использовать счетчик. Счетчик может начинаться с начального времени (например, 0), и мы можем рассматривать этот счетчик как собственные локальные часы процесса.
Лампорт продолжает эту идею, предлагая, что не только каждый процесс в распределенной системе будет иметь свои собственные часы счетчика, но и каждое событие, которое записывается в процессе, также должно иметь значение на локальных часах этого процесса. Более того, значение каждого из этих событий на часах должно отражать все, что произошло до отношений. Например, если событие a → b, то время, когда произошло событие a, должно быть меньше, чем время на часах для каждого события b произошло; другими словами, clock(a) < clock(b).
Используя базовые счетчики вместо физических часов, Лэмпорт упрощает работу с часами. Эти часы счетчика называются логическими часами. логические часы сильно отличаются от физических часов тем, что в них нет центрального понятия времени, а часы - это просто счетчик, который увеличивается в зависимости от событий в системе.
Каждый процесс в распределенной системе может использовать логические часы для причинного упорядочивания всех событий, которые имеют к нему отношение. Когда в процессе происходят события - будь то события отправки или получения - счетчик часов процесса увеличивается на произвольную величину. Мы узнаем больше о том, как это работает на практике, во второй части этой статьи. Мы также познакомимся с алгоритмом Лампорта для увеличения счетчиков и с тем, как соблюдать причинно-следственные связи между процессами. Так много интересного можно узнать; к счастью, у нас есть больше времени и еще один пост, чтобы все это осветить!
Ресурсы
Удобно, что работа Лампорта над логическими часами и причинным порядком хорошо изучена и написана. Есть много отличных ресурсов, которые знакомят с этими темами с различной степенью сложности. Если вы хотите продолжить чтение, ознакомьтесь с некоторыми из моих любимых ресурсов, которые я перечислил ниже!
- Время, часы и порядок событий в распределенной системе, Лесли Лэмпорт
- Время, часы и порядок событий в районе. Система , Дэн Рубинштейн
- Время и порядок: отметки времени Лампорта, Индранил Гупта
- Логические часы Лэмпорта, Майкл Уиттакер
- Логические часы, профессор Пол Кжижановски
