Распределенные системы. Разное

2 Phase Commit

Алгоритм двухфазного коммита — классический централизованный оптимистичный алгоритм распределённого консенсуса из баз данных для подтверждения распределённых транзакций.

После того как мы завершили транзакцию, её надо атомарно подтвердить на всех участниках (participants). У каждой транзакции есть выделенный координатор (transaction coordinator). Алгоритм работает в две фазы:

  1. Запрос (request): координатор спрашивает каждого участника: "готов ли ты очень быстро и гарантированно завершить транзакцию?". Если кто-нибудь ответил "нет", то отменяем транзакцию. Если кто-то отвечает "да", то он должен уметь обеспечить завершение транзакции даже если упадёт и поднимается (например, все данные уже в журнале).
  2. Завершение: координатор принимает решение о закреплении (commit) или отмене (rollback) транзакции и записывает его в свою надёжную память, после чего рассылает всем решение. После рассылки можно сообщить о фиксации транзакции, подтверждения от участников ждать не нужно (но тогда может быть проблема с тем, что следующие чтения из СУБД будут возвращать старые данные, пока не закоммитили).

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

Всего на коммит требуется 3N сообщений (NN — количество участников транзакции) и задержка порядка 3⋅RTT (round-trip time).

Так как это алгоритм консенсуса, к нему применима FLP. Если у нас есть отказы узлов или связи, то 2PC будет ждать, пока связь не восстановится:

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

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

Eventual Consistency

Согласованность в конечном счёте (eventual consistency) — одна из моделей согласованности, используемая в распределённых системах для достижения высокой доступности, в рамках которой гарантируется, что в отсутствии изменений данных, через какой-то промежуток времени после последнего обновления («в конечном счёте») все запросы будут возвращать последнее обновлённое значение.

Пример консистентной в конечном счёте системы — DNS: обновлённая DNS-запись распространяется по серверам в соответствии с настройками интервалов кэширования и, хоть и не моментально, но в конечном счёте все клиенты увидят обновление.

Теорема CAP

Теорема САР (теорема Брюера) — эвристическое утверждение о том, что в любой реализации распределённых вычислений возможно обеспечить не более двух из трёх следующих свойств:

  • Сonsistency(согласованность) — во всех вычислительных узлах в один момент времени данные не противоречат друг другу. При обращении к системе, которая обеспечивает консистентность, вы не получите ответа(получите ошибку), если не будет гарантии, что данные с запрашиваемого узла, совпадают с остальными.
  • Availability(доступность)— любой запрос к распределённой системе завершается корректным откликом, однако без гарантии, что ответы всех узлов системы совпадают. То есть система обязательно вернет какие-то данные, но не факт что они будут актуальными.
  • Partition Tolerance (Устойчивость к разделению системы). Потеря сообщений между компонентами системы (возможно даже потеря всех сообщений) не влияет на работоспособность системы. Здесь очень важный момент состоит в том, что если какие-то компоненты выходят из строя, то это тоже подпадает под этот случай, так как можно считать, что данные компоненты просто теряют связь со всей остальной системой.

В теореме говорится, что если вы строите распределенную систему, то можете удовлетворить только два из вышеупомянутых свойства, т.е. обязательно надо пожертвовать одним из свойств. Главный вопрос, который вызывает недопонимание — это что значит пожертвовать Partition Tolerance.

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

Другими словами, требование partition tolerance для распределённой системы — это не выбор инженера, а просто практическая данность, и выбирать остаётся только между consistency и availability. Даже если инженер упрямо решит построить систему с расчётом на 100% надёжность сети, то при следующем сбое она либо потеряет данные и станет неконсистентной, или не сможет вернуть ответ на запрос, и будет недоступной.

Еще другими словами: Если у вас есть место куда вы пишите и читаете, то в случае сетевого сбоя, вам нужно выбрать либо вы продолжаете читать и писать(availibility) либо вам нужны консистентные данные.

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

Соответственно, если система называет себя CP (т.е. consistency и partition tolerance), то при разрыве (если у нас есть кластер, и он разнесен, например, по двум дата-центрам, и связь рвется между дата-центрами) как ведет себя консистентная система? Она, если мы обращаемся на узел, и узел видит, что он не может надежно обеспечить эту запись, что у него нет, например, связи с большинством узлов системы, то он просто откажет приложению в этой записи, и она не удастся. Когда потом связь восстановится, приложение может попробовать снова и у него может получиться.

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

MapReduce

MapReduce — модель распределённых вычислений, представленная компанией Google, используемая для параллельных вычислений над очень большими, вплоть до нескольких петабайт, наборами данных в компьютерных кластерах.

Работа MapReduce состоит из двух шагов: Map и Reduce, названных так по аналогии с одноименными функциями высшего порядка, map и reduce. На Map-шаге происходит предварительная обработка входных данных. Для этого один из компьютеров (называемый главным узлом — master node) получает входные данные задачи, разделяет их на части и передает другим компьютерам (рабочим узлам — worker node) для предварительной обработки. На Reduce-шаге происходит свёртка предварительно обработанных данных. Главный узел получает ответы от рабочих узлов и на их основе формирует результат — решение задачи, которая изначально формулировалась.

Преимущество MapReduce заключается в том, что он позволяет распределенно производить операции предварительной обработки и свертки. Операции предварительной обработки работают независимо друг от друга и могут производиться параллельно (хотя на практике это ограничено источником входных данных и/или количеством используемых процессоров). Аналогично, множество рабочих узлов может осуществлять свертку — для этого необходимо только чтобы все результаты предварительной обработки с одним конкретным значением ключа обрабатывались одним рабочим узлом в один момент времени. Хотя этот процесс может быть менее эффективным по сравнению с более последовательными алгоритмами, MapReduce может быть применен к большим объёмам данных, которые могут обрабатываться большим количеством серверов. Так, MapReduce может быть использован для сортировки петабайта данных, что займет всего лишь несколько часов. Параллелизм также дает некоторые возможности восстановления после частичных сбоев серверов: если в рабочем узле, производящем операцию предварительной обработки или свертки, возникает сбой, то его работа может быть передана другому рабочему узлу (при условии, что входные данные для проводимой операции доступны).

Дополнительно: