292
правки
Изменения
Новая страница: «В распределённых системах могут быть разные гарантии порядка доставки отправленных соо…»
В распределённых системах могут быть разные гарантии порядка доставки отправленных сообщений.
Более того: иногда программисты могут неявно предполагать тот или иной порядок и очень удивляться, когда он нарушается.
Мы рассматриваем четыре гарантии порядка сообщений, от более слабых к более сильным:
# Асинхронная передачи: никаких гарантий, только exactly-once delivery
# FIFO (First In First Out order)
# Причинно-согласованный порядок (causally consistent ordering, от слова cause, а не casual)
# Синхронный порядок
Можно использовать различные алгоритмы, чтобы получить из более слабой гарантии более сильную.
При добавлении multicast/broadcast сообщений возникают свои проблемы, там нужно смотреть на [[общий порядок сообщений]].
== FIFO ==
Не существует пары сообщений $m, n \in M$ таких, что $snd(m) < snd(n) \land rcv(n) < rcv(m)$ (тут $<$ работает только если два события произошли в одном процессе).
Переформулировка: для каждой упорядоченной пары процессов $(A, B)$ сообщения приходят к $B$ в том же порядке, в котором они отправлены $A$.
Пример нарушения:
[[Файл:distributed-order-fifo-wrong.png|400px]]
== Причинно-согласованный порядок ==
Как FIFO, только вместо $<$ написали $\to$: не существует пары сообщений $m, n \in M$ таких, что $snd(m) \to snd(n) \land rcv(n) \to rcv(m)$.
Пример нарушения (пара сообщений $m=(a, b)$ и $n=(d, e)$):
[[Файл:distributed-order-cc-wrong.png|400px]]
=== Неверная переформулировка ===
На лекции не было, но может казаться правдоподобным.
Если есть события $a, a', b, b'$, причём $a<a'$, $proc(b)=proc(b')$ (взяли пару процессов и два события в каждом), $a\to b$ и $a' \to b'$ (взяли цепочки сообщений между ними), то $b < b'$ (порядок сообщений не меняется).
Проблема в том, что $a \to b$ может начаться не с сообщения, а с нескольких переходов внутри $proc(a)$:
<pre>
P --a---a'--x----
\ \
Q -------b'---b--
</pre>
Более того: иногда программисты могут неявно предполагать тот или иной порядок и очень удивляться, когда он нарушается.
Мы рассматриваем четыре гарантии порядка сообщений, от более слабых к более сильным:
# Асинхронная передачи: никаких гарантий, только exactly-once delivery
# FIFO (First In First Out order)
# Причинно-согласованный порядок (causally consistent ordering, от слова cause, а не casual)
# Синхронный порядок
Можно использовать различные алгоритмы, чтобы получить из более слабой гарантии более сильную.
При добавлении multicast/broadcast сообщений возникают свои проблемы, там нужно смотреть на [[общий порядок сообщений]].
== FIFO ==
Не существует пары сообщений $m, n \in M$ таких, что $snd(m) < snd(n) \land rcv(n) < rcv(m)$ (тут $<$ работает только если два события произошли в одном процессе).
Переформулировка: для каждой упорядоченной пары процессов $(A, B)$ сообщения приходят к $B$ в том же порядке, в котором они отправлены $A$.
Пример нарушения:
[[Файл:distributed-order-fifo-wrong.png|400px]]
== Причинно-согласованный порядок ==
Как FIFO, только вместо $<$ написали $\to$: не существует пары сообщений $m, n \in M$ таких, что $snd(m) \to snd(n) \land rcv(n) \to rcv(m)$.
Пример нарушения (пара сообщений $m=(a, b)$ и $n=(d, e)$):
[[Файл:distributed-order-cc-wrong.png|400px]]
=== Неверная переформулировка ===
На лекции не было, но может казаться правдоподобным.
Если есть события $a, a', b, b'$, причём $a<a'$, $proc(b)=proc(b')$ (взяли пару процессов и два события в каждом), $a\to b$ и $a' \to b'$ (взяли цепочки сообщений между ними), то $b < b'$ (порядок сообщений не меняется).
Проблема в том, что $a \to b$ может начаться не с сообщения, а с нескольких переходов внутри $proc(a)$:
<pre>
P --a---a'--x----
\ \
Q -------b'---b--
</pre>
