База распределённых систем

Блокчейн это распределённая система с врагами внутри. Прежде чем строить консенсус, надо знать законы, которым подчиняется любая система из многих узлов и ненадёжной сети. Эти законы жёсткие: есть теоремы, доказывающие, что некоторых вещей нельзя добиться вообще. Разберём модели сети и сбоев, теорему CAP, невозможность FLP и понятие финальности, на котором держится вопрос «когда транзакция точно случилась».

Идея

Распределённая система это набор узлов, которые обмениваются сообщениями по сети и вместе изображают один сервис. Сложность вся в одном слове: сеть ненадёжна. Сообщение может потеряться, прийти с задержкой, прийти дважды, прийти не по порядку. Узел может упасть, зависнуть, перезагрузиться с потерей памяти. И ты, глядя на молчащий узел, не можешь отличить «он умер» от «он жив, но сообщение застряло». Это незнание и есть корень всех трудностей.

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

• В синхронной модели есть известный предел задержки: не ответил за T секунд, значит мёртв. Жить в ней легко, но это фантазия, в интернете такой границы нет.
• В асинхронной модели границы нет: медленный узел неотличим от мёртвого. Это честная модель интернета, и она беспощадна.
• На практике берут частично синхронную: сеть обычно ведёт себя хорошо, но иногда нарушает границы. На этой модели стоит большинство реальных протоколов.

Вторая, модель сбоев, и тут проходит граница между обычными системами и блокчейном.

• Отказ узла (crash): узел либо честно работает, либо молча падает. Не врёт. Это мир корпоративных баз данных.
• Пропуск сообщений (omission): промежуточная ступень. Узел жив и честен, но часть сообщений теряет: где-то не ответил, где-то не принял. Со стороны он мигает, то живой, то будто мёртвый, и это коварнее чистого падения. Протоколы, переживающие crash, обычно переживают и omission: потерянное сообщение неотличимо от очень медленного, а с медленными они уже обязаны справляться.
• Византийский сбой (Byzantine): узел может врать, слать разным соседям разное, нарушать протокол как угодно. Это мир публичного блокчейна из прошлого урока, и он на порядок труднее.

Ближайшие уроки это лестница по этим моделям: сначала консенсус против отказов, потом против предательства, потом открытый накамото-консенсус.

Теорема CAP

Теперь первый жёсткий закон. Ты уже встречал его со стороны баз данных в теории распределённых БД, теперь посмотрим со стороны консенсуса. Теорема CAP говорит: из трёх свойств одновременно держатся только два.

• Consistency: любой читающий видит самую свежую запись (как будто узел один).
• Availability: каждый живой узел отвечает на запрос, не зависает.
• Partition tolerance: система продолжает работать, даже когда сеть разорвало на части, которые не слышат друг друга.

Ключ в том, что разрывы сети (P) в реальной системе неизбежны, отказаться от них нельзя. Значит выбор настоящий только между C и A, и только в момент разрыва. Узел на одной стороне разрыва получил запись. Узел на другой стороне об этом не знает. К нему приходит читатель. Два варианта:

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

Третьего нет. И блокчейны отвечают на этот выбор по-разному, в зависимости от консенсуса. Накамото-консенсус (урок про PoW и PoS) выбирает доступность: при разрыве обе половины сети продолжают печь блоки, каждая свою ветку, а когда связь вернётся, более короткая ветка откатится и сеть сойдётся к одной истории. Это AP-система с согласованностью «в итоге» (eventual), и именно поэтому советуют ждать подтверждений: свежий блок может оказаться на ветке, которой суждено умереть. А вот цепи с BFT-финальностью (урок про BFT) выбирают согласованность: Tendermint, потеряв кворум в две трети, честно останавливается и не финализирует ничего, пока сеть не срастётся. Это CP-выбор: лучше замереть, чем зафиксировать две противоречащие истории. Когда сеть цела, доступны и C, и A сразу, теорема говорит только про поведение во время разрыва.

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

Это не абстракция: каждая боевая база уже сделала выбор. AP-системы (Cassandra, Amazon DynamoDB, CouchDB) при разрыве отвечают всегда, даже устаревшим значением, согласованность у них «в итоге» (eventual). С оговоркой про DynamoDB: AP-репутация тянется из статьи Amazon про Dynamo 2007 года, а современный сервис умеет и строго согласованные чтения (strongly consistent reads), если попросить и заплатить задержкой. CP-системы (etcd, ZooKeeper, HBase) при разрыве затыкаются на меньшинстве и отвечают только там, где есть кворум, лишь бы не отдать неверное. Не случайно etcd, на котором держит состояние весь Kubernetes, выбрал CP: лучше отказать в записи, чем потерять кусок кластерной правды.

Сам Brewer спустя двенадцать лет уточнил рамку (статья «CAP Twelve Years Later»): свойства не двоичны, а непрерывны, и выбор C против A возникает только во время разрыва, который для большинства систем редок. Расширение PACELC добивает картину: if Partition выбираешь между A и C, а Else (сеть цела) всё равно платишь, теперь между задержкой (L) и согласованностью (C). Хочешь, чтобы запись считали все реплики до ответа клиенту, плати миллисекундами на каждый запрос. Так что выбор есть всегда, разрыв лишь обостряет его до отказа.