CRDT, RON и Сети Данных
Эта статья о следующем эволюционном шаге в развитии систем обработки данных. Тема амбициозная, поэтому расскажу сначала немного о себе. Вот уже больше 10 лет я работаю над проектами в области CRDT и синхронизации данных. За это время успел поработать на университеты, стартапы YCombinator и известные международные компании. Мой проект последние три года — Replicated Object Notation, новый формат представления данных, сочетающий возможности объектной нотации (как JSON или YAML), сетевого протокола и оплога/бинлога. Вы могли слышать про другие проекты, работающие в том же направлении, например, Datanet, Automerge и другие. Также вы могли читать Local-first software, это наиболее полный манифест данного направления Computer Science. Авторы — замечательный коллектив Ink&Switch, включая широко нам известного по «Книге с Кабанчиком» М.Клеппманна. Или вы, возможно, слушали мои выступления по этой теме на различных конференциях.
Идеи этой статьи перекликаются с тем, что пишет последние годы Pat Helland: Immutability Changes Everything и др. Они смежны с проектами IPFS и DAT, к которым я имею отношение.
Итак. Классические БД выстроены на линейном логе операций (WAL). От этого лога выстроены транзакции, от него же выстроена репликация master-slave. Теория репликации с линейным логом написана ещё в начале 1980-х с участием небезызвестного Л. Лампорта. В классических legacy системах с одной большой центральной базой данных всё это работает хорошо. Так работают Oracle, Postresql, MySQL, DB2 и прочие классические SQL БД. Так работают и многие key-value БД, например, LevelDB/RocksDB.
Но линеаризация не масштабируется. Когда система становится распределённой, всё это начинает ломаться. Образно говоря, линейная система — это что-то вроде греческой фаланги. Нужно, чтобы все шли ровно, а для этого хорошо, чтобы земля была везде ровной. Так получается не всегда: где-то электричество отключили, а где-то сеть медленная. Хотя в системе Google Spanner и было показано, что с достаточно большим бюджетом землю можно сделать ровной абсолютно везде, мы всё же отметим, что Google тоже бывает отключается целиком по совершенно смешным причинам.
Из россиян этот тезис в своих докладах развивал Бартунов. Чтобы такую систему отмасштабировать, добавляется асинхронный механизм связи. Очередь сообщений, например, на сегодняшний день является типовым решением. Или же промежуточным вариантом, когда в центр ставится линейная Kafka в качестве мастера.
Из популярных систем заметным исключением является Cassandra. За счёт отката к last-write-wins консистентности она может работать совершенно анархически, то есть без учёта порядка записи. Это прекрасно подходит для хранения слабоструктурированных данных, например, адресных книжек с айфонов. Apple очень любит Cassandra.
Но между линеаризацией и полной анархией есть один интересный уровень: Causal consistency, или причинно-следственная целостность. Это примерно то же, что и happened-before в Computer Science или геометрия Минковского в физике. Это и конус прошлого, и конус будущего, и транзитивность причинно-следственных связей. Это максимально строгая модель, которая ещё согласуется с физикой распределённых систем. В отличие от линеаризации, она допускает наличие параллельных, не влияющих друг на друга событий. В то же время она предусматривает и строгий порядок — там, где он имеет смысл.
Единственное, что теория баз данных долго игнорировала этот замечательный уровень консистентности, и в полной мере его возможности стали раскрываться только с появлением CRDT (Conflict-Free Replicated Data Types). Эта теория подразумевает, что каждая структура данных существует во множестве реплик. Связь между репликами есть не всегда, поэтому изменения иногда приходится мержить. В отличие от git, CRDT структуры данных всегда можно помержить автоматически. В остальном же, git — очень хороший пример для объяснения свойств CRDT хранилищ:
1. Они также хранят всю историю (возможен аудит),
2. данные становится очень сложно потерять, и
3. появляется возможность работать с данными локально и мержить результат.
RON это нотация, максимально удобная для представления CRDT объектов. В RON есть 4 типа атомов: UUID, INT, STRING, FLOAT. Набор атомов называется RON tuple. А RON операция это tuple с парой UUID метаданных. В этой паре, один UUID это собственный идентификатор операции, а второй указывает на другую, ранее созданную операцию. Благодаря этим айдишникам и ссылкам, из операций можно собирать любые структуры данных. Примерно как из кусочков LEGO, если бы они ещё были пронумерованы, чтобы точно ничего не перепуталось.
Продолжая аналогию с git, в RON сама концепция бранчей/веток обобщается до такой степени, что уже практически всё состоит из веток. Сам RON построен на операциях, хотя и притворяется объектной нотацией изо всех сил. Поэтому в основе любая реплика — это лог операций, как и в обычной БД. Однако этот лог упорядочен частично по happened-before, и между разными репликами порядок операций может отличаться. C некоторой точки лога мы можем ответвить новую версию, новый бранч. Точно так же мы можем «привить» другую ветку к нашей (смержиться). В этой схеме и база данных, и бранч выглядят одинаково, как ветки. И одинаково мы их можем мержить. Будь это другая версия данных или же другой набор данных — это всё равно ветки оплога. Например, если в нашу БД включён справочник «курс валют», это будет отдельная маленькая ветка, которую мы постоянно подмёрживаем в нашу базу.
Каждая ветка — это частично упорядоченное множество операций. Над этими множествами мы можем производить все обычные операции. Merge — это объединение; общий предок — это пересечение; diff — это XOR. Получается, что БД может выглядеть, как матрёшка, ведь возможна вложенность. БД может быть сведением разных БД или поправками (бранчем) другой БД. Или всё это вместе. Связь между репликами, что важно, не теряется, т. е. всё можно мержить обратно в оригинал при желании. Алгебраично!
Единственная проблема — сделать, чтобы это всё достаточно быстро работало и не занимало много места. В частности, для этого у RON помимо текстовой формы есть более эффективные бинарные варианты RONv и RONp. Но и БД не ограничивается оплогом: она на нём строится, как дом на фундаменте.
А теперь главный вопрос — зачем? Зачем разрабатывать новые БД на новых принципах, когда старые вроде бы нормально работают?
Во-первых, сети данных обеспечивают связность без централизации. Поясню на примере медицинских БД. Допустим, вам не повезло прокатиться на скорой в Петербурге, а ваши медицинские документы в Екатеринбурге. Такое случается. Хотелось бы, конечно, чтобы документы синхронизировались в реальном времени — и теперь, и потом, когда вы вернётесь в Екатеринбург.
Конечно, тут можно создать единую центральную медицинскую БД имени депутата Яровой. Но что делать, когда произойдёт какой-нибудь сбой? Останавливать медицину? Когда Google или Amazon уходят в оффлайн, много чего перестаёт работать. И потом, центральная БД безусловно однажды утечёт в паблик. Конечно, интересно почитать, как Алексея Навального трижды отравили химическим оружием агенты ФСБ. Но я не настолько бессмертный и хотел бы, чтобы в здравоохранении работали более надёжные и безопасные информационные системы.
Второй аспект — это локальная доступность. Даже Google или Amazon уходят порой в оффлайн. Если же данные находятся в локальной сети или непосредственно на устройстве, то они перестанут быть доступны только при поломке сети и устройства. А тогда всё равно всё работать перестанет, как ни крути. Также синхронизируемая реплика на устройстве будет работать и в поле, и в тайге, и чёрти где в промзоне. Это актуально для промышленных применений.
Третий аспект — коллаборативность. Благодаря автоматическому мержу CRDT является на сегодня наиболее удобной технологией для реализации коллаборативных приложений. В эпоху коронавируса это более чем актуально!
Четвертый аспект — это разумные требования консистентности. Анархия в стиле Cassandra — это, конечно, перебор. Но и линейность лога даже в финансовых системах имеет ограниченную ценность. Как показано в исследовании ACIDRain, в реальных ACID/SQL системах линеаризация сегодня используется в качестве фетиша. Фактически, используемые настройки изоляции транзакций позволяют различные эксплуатируемые аномалии, и фактически безопасность реализуется другими методами. А если бизнес-логика говорит с БД по RPC, то тут уж вовсе говорить не о чем.
Пятый аспект — это целостность данных. Если мы задумаемся, как гарантируется целостность данных в классическом блокчейне, мы поймём, что это простое голосование (по PoW или PoS). В сетях данных реализуемы глобальная перекрёстная подпись и массивное якорение. Это как в git, но только глобально. Эти инструменты гораздо более могучи, чем PoW. На сегодняшний день сравнимая степень защиты есть разве только у ядра Linux. Если задуматься, то в эпоху deep fake вообще может стать невозможным отличить реальность от иллюзии без помощи криптографии. Мы стали слишком зависимы от электронных средств коммуникации. Но это утверждение, конечно, заслуживает отдельной статьи.
Подытожу.
В современном мире разных баз данных не много, а очень много, и мы критически от них зависим. RON позволяет объединить данные в единую живую сеть, не стаскивая их в единый датацентр и не создавая единой точки отказа (SPoF). Это основные преимущества централизации, без характерных сопутствующих недостатков.
Хранение и передача, БД и сеть — это две стороны одной медали, и нам нужна вся медаль, а не стороны.
Если вас заинтересовала эта тема, следите за проектом RON (ru, en), там скоро релиз документации новой версии. Что интересно, документация готовится в системе контроля версий DaRWiN, которая работает на оплоге RON.
