LINUX.ORG.RU
ФорумTalks

А что за шляпа с CAP теоремой?

 cap теорема, ,


0

1

На русском языке я не то что доказательство найти не могу, но даже формулировку. Да и по английски всё как-то мутно.

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

★★★★★

Ответ на: комментарий от utf8nowhere

Спасибо. Правда я теперь ещё сильнее запутался.

ya-betmen ★★★★★
() автор топика
Ответ на: комментарий от ya-betmen

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

нагуглил только перепечатки переводов перепечаток. Что за фигня?

По-моему, причины две.

1) искать надо было в яндексе

2) поскольку теорема во многом демагогическая/тавтологическая, мало кто уделяет ей внимание, а вот копирайтеры, наоборот, любят

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 3)

почему её применяют только к распределённым системам

Её применяют к любой системе, это архитектурный аналог «Быстро/Дёшево/Качественно – выберите два».

Fafhrd
()
Последнее исправление: Fafhrd (всего исправлений: 1)

Ух ты! Ее можно применить к участковым терапевтам!

Irma ★★
()
Ответ на: комментарий от firkax

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

ya-betmen ★★★★★
() автор топика
Ответ на: комментарий от ya-betmen

поэтому пока не врубаюсь как быть со временем ответа стремящимся к бесконечности

Очевидно же что это практически равнозначно отсутствию ответа.

упростили до мгновенного действия

Данные получены или данные не получены это бинарный предикат. А уж как ты определяешь этот предикат в твоей системе зависит от системы (т.е. по сути от бизнес модели).

no-such-file ★★★★★
()
Последнее исправление: no-such-file (всего исправлений: 1)
Ответ на: комментарий от no-such-file

Тогда, чтобы КАП можно было применять нужно вносить параметр какой-то задержки и из него считать, будет ли выполняться все три условия для системы или нет. Поскольку сейчас если считать бесконечно долгий ответ как ответ, то возможна система удовлетворяющая всем трем условиям. Или я чего-то не понял.

Просто, если идти в обратную сторону и считать, что ответ должен быть мгновенен, то ей ничего не удовлетворяет.

ya-betmen ★★★★★
() автор топика
Ответ на: комментарий от ya-betmen

Поскольку сейчас если считать бесконечно долгий ответ как ответ,

А вы считайте бесконечно долгий ответ как отсутствие ответа

vaddd ★☆
()

нельзя сделать распределённую базу данных, которая всегда отдаёт одинаковые ответы от своих нод, но при этом продолжает работать при нарушениях связи между нодами

Зависит от фактора репликации. Если, допустим, выпало три ноды, а репликация равна пяти, с консистентностью ничего не будет, но просядет производительность - очевидно, что две ноды могут обработать меньше запросов, чем пять.

pekmop1024 ★★★★★
()
Ответ на: комментарий от pekmop1024

Чтобы, собственно, консистентность контролировать и нагрузку распределять, зачастую применяют внешние сервисы, подобные Zookeeper - однако если и кворуму зукипера пришел конец, кластер проще пересобрать с нуля и восстановить из бэкапа.

pekmop1024 ★★★★★
()
Ответ на: комментарий от ya-betmen

Почему очевидно?

Потому что подразумевается, что в примере ноды одинаковые, сферические, в вакууме.

pekmop1024 ★★★★★
()
Ответ на: комментарий от ya-betmen

С того момента, как система перестает удовлетворять требованиям заказчика по времени ответа

vaddd ★☆
()
Ответ на: комментарий от firkax

По-моему, весьма тривиальное утверждение: если связи между нодами нарушены, то синхронизировать их уже полноценно не получится, и надо либо ждать, пока связь починят (база лежит), либо отдавать какие-то несинхронизированные данные.

Можно сделать иммутабельную БД где данные после записи нельзя менять так что прочитать данные можно из любого сервера БД без необходимости связи с остальными. Если связь с некоторыми серверами будет нарушена, то на них могут быть не записаны новые данные и запрос на чтение будет перенаправлен на сервер где есть данные.

X512 ★★★★★
()
Ответ на: комментарий от X512

А можно сделать иммутабельную БД в которой все данные вообще заранее преднастроены. Только это не то, о чём речь.

firkax ★★★★★
()
Ответ на: комментарий от ya-betmen

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

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 1)
Ответ на: комментарий от firkax

Что значит нельзя соединиться после сплита? Можно ли считать, что отказ одной ноды ломает доступность, а отказ сети не ломает?

ya-betmen ★★★★★
() автор топика
Ответ на: комментарий от ya-betmen

поэтому пока не врубаюсь как быть со временем ответа стремящимся к бесконечности.

Очевидно, под availability понимается какое-то адекватное время ответа, когда просто данные достаются из стораджа, и система не ждет, пока восстановится связность в кластере.

goingUp ★★★★★
()
Ответ на: комментарий от goingUp

Вот селект из обычной базы может занимать десятки минут. Это можно считать адекватным временем ответа?

ya-betmen ★★★★★
() автор топика
Последнее исправление: ya-betmen (всего исправлений: 1)
Ответ на: комментарий от ya-betmen

Или я чего-то не понял

Ты не понял что утверждение относительно. Например у тебя распределённая система и синхронизация занимает 10 минут. А ответ при этом допустимо получать в течение часа. Но тогда с этой точки зрения у тебя не распределённая система. Т.к. синхронизация относительно времени ответа «мгновенная» (просто потому что все события которые занимают меньше часа «мгновенные», т.е. эффективно невидимые для того кто посылает запрос).

no-such-file ★★★★★
()
Последнее исправление: no-such-file (всего исправлений: 3)
Ответ на: комментарий от ya-betmen

Если в двух половинах базы были разные записи то они могут конфликтовать. И даже не обязательно конфликтовать, просто в одной половине кто-то мог прочесть старые данные после того как во второй половине уже записали новые, а во второй - другие старые данные после того как из обновила первая. Слить всё это назад в единый поток исполнения бесшовно не получится. То есть отказ сети либо ломает доступность (ждёшь пока сеть починится), либо ломает консистентность между нодами и консистентность глобального потока исполнения.

firkax ★★★★★
()
Ответ на: комментарий от no-such-file

Но если сеть между нодами падает, это ж может продолжаться и дольше.

ya-betmen ★★★★★
() автор топика
Ответ на: комментарий от ya-betmen

Либо ждать и висеть, либо не ждать и получить рассинхрон.

firkax ★★★★★
()
Ответ на: комментарий от ya-betmen

Вот селект из обычной базы может занимать десятки минут. Это можно считать адекватным временем ответа?

Уже писали, если такое время устраивает заказчика, то наверное да. Но обычно кластер с высокой доступностью строят не для того, чтобы ждать результаты запросов по полчаса, так что вопрос чисто теоретический.

Если я буду висеть не присылая ответ в ожидании пока ноды синкнуться?

А если нода сдохла вместе с жестким диском?

goingUp ★★★★★
()

эвристическое утверждение

А потому что это на самом деле не теорема, в википедии всё правильно сказано. Ни чёткой формулировки, ни доказательств нет.

oldstable
()
Ответ на: комментарий от ya-betmen

Возможно и было, но я попыток не видел. Все её и воспринимают как сугубо эмпирическую штуку.

oldstable
()
Последнее исправление: oldstable (всего исправлений: 1)

Это не теорема в математическом плане, а скорее гипотеза, подкреплённая эмпирическими свидетельствами.

Вариантов распределённых систем на самом деле много, и многое зависит от точных определений и требований к разным аспектам. «Кому и кобыла невеста», как говорится.

Хороший обзор тут:

https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed/

Плюс за практическими советами по распределённым системам тебе сюда: https://jepsen.io/consistency

deadman ★★
()
Последнее исправление: deadman (всего исправлений: 1)

доказательство найти не могу

Потому что в общем случае она не верна.

Итак, формулировка теоремы

В любой реализации распределённых вычислений возможно обеспечить не более двух из трёх следующих свойств:

    согласованность данных (англ. consistency) — во всех вычислительных узлах в один момент времени данные не противоречат друг другу;
    доступность (англ. availability) — любой запрос к распределённой системе завершается корректным откликом, однако без гарантии, что ответы всех узлов системы совпадают;
    устойчивость к разделению (англ. partition tolerance) — расщепление распределённой системы на несколько изолированных секций не приводит к некорректности отклика от каждой из секций.

Для ее опровержения достаточно построить опроверкающий пример.

Рассмотрим сеть из узлов с полностью локализованными данными, то есть такой, в которой каждый узел работает только со своими данными и у каждого узла свой набор клиентов.

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

Что и требовалось доказать.

Psilocybe ★★★★
()
Последнее исправление: Psilocybe (всего исправлений: 1)
Ответ на: комментарий от Psilocybe

Рассмотрим сеть из узлов с полностью локализованными данными, то есть такой, в которой каждый узел работает только со своими данными и у каждого узла свой набор клиентов.

Как это относится к распределённым вычислениям?

alex1101
()
Закрыто добавление комментариев для недавно зарегистрированных пользователей (со score < 50)