Викиконспекты - Вклад участника [ru]

CAP теорема

2019-06-04T10:21:36Z

91.132.204.29:

[[Категория: Параллельное программирование]]
'''CAP-теорема''' — утверждение о том, что в распределённых системах нельзя одновременно добиться трёх свойств:
* '''C'''onsistency — на всех ''не отказавших'' узлах одинаковые (с точки зрения пользователя) данные одинаковы
* '''A'''vailability — запросы ко всем ''не отказавшим'' узлам возвращают ответ
* '''P'''artition tolerance — даже если связь в системе стала нестабильной (вплоть до разделения системы на куски), но узлы работают, то система в целом продолжает работать

Формально мы это не формулировали и не доказывали.
Оригинальная формулировка — Brewer's Conjecture (2000), а формализовано в работе Gilbert & Lynch (2004).
Там есть много тонкостей с тем, что такое "не отказавший узел", "одинаковые данные", "разрыв связи", "система продолжает работать", "когда система всё-таки окончательно ломается и считается недоступной" и тому подобное.

Для общей эрудиции выглядят неплохо статьи<ref>http://blog.thislongrun.com/2015/04/the-unclear-cp-vs-ca-case-in-cap.html</ref><ref>https://habr.com/ru/post/322276/</ref>

== Классификация алгоритмов ==
А вот алгоритмы, которые удовлетворяют хотя бы двум свойствам, можно нарисовать на диаграмма Венна:

[[Файл:Distributed-cap.png|400px]]

Дальше идут объяснения с лекции, они отличаются в разных источниках (например, где-то 2PC идёт вместе с Paxos в CP, а не в CA<ref>http://www.cedanet.com.au/ceda/fallacies/cap-theorem.php</ref>), а где-то совпадают с лекцией<ref>http://book.mixu.net/distsys/single-page.html#the-cap-theorem</ref>, а где-то считают, что не-partition tolerance не нужно<ref>https://codahale.com/you-cant-sacrifice-partition-tolerance/</ref>.
* Если мы хотим согласованность и доступность, то используем [[2 Phase Commit|протокол двухфазного коммита]]: он гарантирует нам согласованное состояние глобально во всей системе и мы всегда можем обслуживать запросы (если только не упал узел с соответствующими данными). Но если потерялась связь (а узлы не упали), то какие-то запросы нельзя обработать, потому что часть данных может быть в одной половине, а часть в другой. Каждый кусок всё ещё будет работать по отдельности, но глобальные транзакции выполнять мы не сможем.
* Иногда нам не так важна согласованность и мы согласны на простую eventual consistency — это когда информация может быть доступна не сразу везде, а только через какое-то время, если система здорова. Сюда идут [[gossip-протоколы]].
* Если мы хотим согласованность и толерантность к разделению, то надо жертвовать доступностью. Например, при помощи Paxos мы можем хранить все данные сразу на всех узлах, но тогда узлы, оказавшиеся в меньшинстве, ничего сделать не могут.

CAP теорема

2019-06-04T10:21:18Z

91.132.204.29:

[[Категория: Параллельное программирование]]
'''CAP-теорема''' — утверждение о том, что в распределённых системах нельзя одновременно добиться трёх свойств:
* '''C'''onsistency — на всех ''не отказавших'' узлах одинаковые (с точки зрения пользователя) данные одинаковы
* '''A'''vailability — запросы ко всем ''не отказавшим'' узлам возвращают ответ
* '''P'''artition tolerance — даже если связь в системе стала нестабильной (вплоть до разделения системы на куски), но узлы работают, то система продолжает работать

Формально мы это не формулировали и не доказывали.
Оригинальная формулировка — Brewer's Conjecture (2000), а формализовано в работе Gilbert & Lynch (2004).
Там есть много тонкостей с тем, что такое "не отказавший узел", "одинаковые данные", "разрыв связи", "система продолжает работать", "когда система всё-таки окончательно ломается и считается недоступной" и тому подобное.

Для общей эрудиции выглядят неплохо статьи<ref>http://blog.thislongrun.com/2015/04/the-unclear-cp-vs-ca-case-in-cap.html</ref><ref>https://habr.com/ru/post/322276/</ref>

== Классификация алгоритмов ==
А вот алгоритмы, которые удовлетворяют хотя бы двум свойствам, можно нарисовать на диаграмма Венна:

[[Файл:Distributed-cap.png|400px]]

Дальше идут объяснения с лекции, они отличаются в разных источниках (например, где-то 2PC идёт вместе с Paxos в CP, а не в CA<ref>http://www.cedanet.com.au/ceda/fallacies/cap-theorem.php</ref>), а где-то совпадают с лекцией<ref>http://book.mixu.net/distsys/single-page.html#the-cap-theorem</ref>, а где-то считают, что не-partition tolerance не нужно<ref>https://codahale.com/you-cant-sacrifice-partition-tolerance/</ref>.
* Если мы хотим согласованность и доступность, то используем [[2 Phase Commit|протокол двухфазного коммита]]: он гарантирует нам согласованное состояние глобально во всей системе и мы всегда можем обслуживать запросы (если только не упал узел с соответствующими данными). Но если потерялась связь (а узлы не упали), то какие-то запросы нельзя обработать, потому что часть данных может быть в одной половине, а часть в другой. Каждый кусок всё ещё будет работать по отдельности, но глобальные транзакции выполнять мы не сможем.
* Иногда нам не так важна согласованность и мы согласны на простую eventual consistency — это когда информация может быть доступна не сразу везде, а только через какое-то время, если система здорова. Сюда идут [[gossip-протоколы]].
* Если мы хотим согласованность и толерантность к разделению, то надо жертвовать доступностью. Например, при помощи Paxos мы можем хранить все данные сразу на всех узлах, но тогда узлы, оказавшиеся в меньшинстве, ничего сделать не могут.

CAP теорема

2019-06-04T10:20:52Z

91.132.204.29: /* Классификация алгоритмов */

[[Категория: Параллельное программирование]]
'''CAP-теорема''' — утверждение о том, что в распределённых системах нельзя одновременно добиться трёх свойств:
* '''C'''onsistency — на всех ''не отказавших'' узлах одинаковые (с точки зрения пользователя) данные
* '''A'''vailability — запросы ко всем ''не отказавшим'' узлам возвращают ответ
* '''P'''artition tolerance — даже если связь в системе стала нестабильной (вплоть до разделения системы на куски), то система продолжает работать

Формально мы это не формулировали и не доказывали.
Оригинальная формулировка — Brewer's Conjecture (2000), а формализовано в работе Gilbert & Lynch (2004).
Там есть много тонкостей с тем, что такое "не отказавший узел", "одинаковые данные", "разрыв связи", "система продолжает работать", "когда система всё-таки окончательно ломается и считается недоступной" и тому подобное.

Для общей эрудиции выглядят неплохо статьи<ref>http://blog.thislongrun.com/2015/04/the-unclear-cp-vs-ca-case-in-cap.html</ref><ref>https://habr.com/ru/post/322276/</ref>

== Классификация алгоритмов ==
А вот алгоритмы, которые удовлетворяют хотя бы двум свойствам, можно нарисовать на диаграмма Венна:

[[Файл:Distributed-cap.png|400px]]

Дальше идут объяснения с лекции, они отличаются в разных источниках (например, где-то 2PC идёт вместе с Paxos в CP, а не в CA<ref>http://www.cedanet.com.au/ceda/fallacies/cap-theorem.php</ref>), а где-то совпадают с лекцией<ref>http://book.mixu.net/distsys/single-page.html#the-cap-theorem</ref>, а где-то считают, что не-partition tolerance не нужно<ref>https://codahale.com/you-cant-sacrifice-partition-tolerance/</ref>.
* Если мы хотим согласованность и доступность, то используем [[2 Phase Commit|протокол двухфазного коммита]]: он гарантирует нам согласованное состояние глобально во всей системе и мы всегда можем обслуживать запросы (если только не упал узел с соответствующими данными). Но если потерялась связь (а узлы не упали), то какие-то запросы нельзя обработать, потому что часть данных может быть в одной половине, а часть в другой. Каждый кусок всё ещё будет работать по отдельности, но глобальные транзакции выполнять мы не сможем.
* Иногда нам не так важна согласованность и мы согласны на простую eventual consistency — это когда информация может быть доступна не сразу везде, а только через какое-то время, если система здорова. Сюда идут [[gossip-протоколы]].
* Если мы хотим согласованность и толерантность к разделению, то надо жертвовать доступностью. Например, при помощи Paxos мы можем хранить все данные сразу на всех узлах, но тогда узлы, оказавшиеся в меньшинстве, ничего сделать не могут.