Здравствуйте, меня зовут Дмитрий Карловский и я.. обычно пишу статьи с ответами, но на этот раз я, наоборот, буду задавать много вопросов, о которых вы даже не задумывались.
Далее будет много и фундаментальной теории, и мелких технических деталей. Так что приглашаю специалистов по криптографии, безопасности, хранению, обработке и синхронизации данных вместе размять наши мозговые косточки.
Цели
Сперва ограничим область, в которой будем искать Святой Грааль работы с данными. Пользователь работает с некоторым интерфейсом, через который он вводит и смотрит самые разнообразные данные. Кроме того, есть потребность, чтобы с теми же данными в то же время могли работать и другие пользователи, и разнообразные сервисы, но строго в рамках некоторой системы прав.
Так как устройства пользователей выходят в онлайн в разное время, мы не можем ограничиваться прямым соединением между ними, поэтому нужны специальные узлы, называемые серверами, основная задача которых быть всё время онлайн. Часть из них (хранилища) ещё и хранит данные, чтобы они были доступны в любое время. А часть (сервисы) - занимается их обработкой и связью со внешним миром.
Сейчас мы сконцентрируемся на OLTP проблематике, то есть на работе с исходными данными: их надёжном хранении и распространении в реальном времени. OLAP же задачи по агрегации данных могут быть реализованы отдельным независимым слоем через сервисы.
Давайте пофантазируем, какими качествами обладала бы идеальная архитектура работы с данными:
Durable. Сбои на любом узле или между ними не должны приводить к потере данных или нарушению их целостности.
Available. Медленное или отсутствующее соединение между любыми узлами не должно влиять на возможность полноценной работы с данными. Вплоть до полного офлайна.
Decentralized. Не должно быть единой точки отказа, компрометация или недоступность которой сломает всю систему обмена данными.
Real-Time. Всё должно не просто летать, но мы должны в реальном времени видеть изменения, внесённые на других узлах. А не спустя час и лишь после перезагрузки.
Secure. Компрометация любых промежуточных узлов не должна давать несанкционированного доступа на чтение/изменение, что позволяет безопасно обмениваться данными даже по небезопасным каналам связи.
❔ Звучит амбициозно, нереалистично, абсурдно? А что если я скажу, что это не просто возможно, но уже и можно пощупать своими руками?
Но не будем спешить - сперва немного теории..
Модель данных
Так или иначе все модели баз данных сводятся к 3 категориям:
Табличные (строчные, колоночные), где данные организованы в двумерные структуры.
Иерархические (словарные, древовидные, документные), где произвольный документ хранится по составному первичному ключу.
Сетевые (объектные, графовые), где данные образуют сеть с прямыми ссылками между узлами, которые группируются в кластеры разных размеров.
Так или иначе, все табличные модели требуют для эффективной работы древовидные вручную задаваемые индексы. Запросы не через индексы, а через сканирование всей таблицы, настолько не эффективны, что являются табу. Ну а дерево является частным случаем графа. То есть сетевая модель является наиболее универсальной и гибкой. Остановимся на ней.
Все данные образуют единый огромный граф. Реплицировать его целиком между всеми репликами может быть сложно, а то и не возможно, если данных слишком много. Поэтому нужно шардирование, то есть хранение разных данных на разных группах узлов. При этом связанные узлы желательно хранить рядом и реплицировать атомарно, поэтому такие узлы объединяют в кластеры, которые мы будем называть лендами (land), чтобы не было путаницы.
Таким образом полный идентификатор узла складывается из двух идентификаторов:
Глобальный идентификатор ленда.
Локальный идентификатор узла в ленде.
Если локальный идентификатор узла пустой, то считаем его корневым узлом ленда. Если узлы в ленде образуют от такого корня дерево без внешних ссылок, то получается эквивалент документа из документных СУБД.
Упаковывая в такую модель таблицу, мы сами решаем как группировать в ленды те или иные данные: по строкам, по колонкам, а то и всю таблицу целиком в один ленд.
Индексы в реляционных СУБД - это деревья из так называемых корзин. В сетевой модели мы сами строим такие деревья из лендов и ищем через них данные. То есть все запросы всегда идут через такой аналог индекса, без неожиданного полного сканирования.
❔ Достаточно ли такой модели для всего? Может стоит выстроить из лендов какую-то иерархию или ещё что?
Если же говорить о прикладной модели, то сущность, например, составляется из списка узлов (по одному на каждое поле), плюс каждое значение поля представляет из себя некоторую иерархию узлов.
Децентрализация
Тренд последнего сезона - концепция local-first, предполагающая построение архитектуры не по клиент-серверной модели, где мы доверяем серверу, но не доверяем клиенту, а предполагающая работу с локальным хранилищем, которое конвергентно (то есть без откатов состояния) синхронизируется с другими узлами. Возможно это благодаря алгоритмам бесконфликтного слияния, о типах которых я рассказывал в докладе «Консистентно о Консенсусе»:
Мы возьмём, конечно, самый продвинутый - неупорядоченную конвергентность (CvRDT), где состояние представляется набором юнитов, каждый из которых хранит как сам кусочек данных, так и различную мета информацию: кто автор, где находится, когда создан и тд. Эти юниты можно гроздями насыпать из разных источников, а они самоупорядочиваются, образуя объединённое состояние.
Но для децентрализации этого мало, так как в такое состояние может писать кто угодно, что угодно, от чьего угодно имени. Чтобы это предотвратить, часто используют проверку прав (авторизацию) и авторства (аутентификацию) на сервере - центральном доверенном звене, через которое проходит весь трафик. И даже если это звено представляет из себя не один сервер, а группу, оно от этого не перестаёт быть единой точкой отказа:
Её компрометация позволяет вносить в базу любые изменения от имени любого пользователя.
Её недоступность не позволяет узлам, имеющим прямое соединение, обмениваться данными.
Её пропускная способность является бутылочным горлышком для всего трафика.
Безопасность
Для настоящей децентрализаци не хватает ещё и концепции нулевого доверия - модели безопасности, где никакой узел не доверяет никакому другому и перепроверяет все поступающие к нему данные. Она не исключает существование изолированного периметра, как дополнительной меры безопасности, но не полагается на него для обеспечения своих гарантий, что позволяет не бояться сливов.
❔ Но как проверять поступающие извне данные, когда мы доверяем только себе?
Тут на помощь к нам приходит асимметричная криптография: верифицируя цифровые подписи мы можем проверять авторство изменений. А зная автора, легко можно проверять и права на внесение изменений.
С правами на чтение всё немного сложнее - тут не достаточно простой верификации, ведь имея контроль над узлом её легко отключить. Тут уже спасает end-to-end шифрование, раскрывающее секретный ключ только тому, кому предоставляется доступ на чтение, но никакому другому промежуточному узлу.
? А что если.. сразу сделать базу открытой всем ветрам, чтобы даже надежды не было, что база не утечёт?
Так как юниты данных шифроваться и подписываться могут лишь на конечных узлах, где доступен приватный ключ, то мы получаем довольно жёсткое ограничение на алгоритмы работы с данными - они не должны менять ни сами данные, ни их мета-данные. То есть юниты должны оставаться неизменными даже после слияния изменений разных пользователей в одно общее состояние. Тут половина бесконфликтных структур данных дружно выходит из чата.
Криптография
Из современных популярных алгоритмов асимметричной криптографии можно выделить семейство, основанное на элллиптической кривой 25519:
И всё бы хорошо, но в браузерах до сих пор нет их нативной поддержки, а JS-библиотеки работают на порядок медленнее и раздувают бандл на десятки килобайт. Из доступных в браузере самая ресурсоэкономная эллиптическая кривая - P-256 и соответствующие ей алгоритмы:
Используя общий секрет уже можно шифровать данные через AES в режиме CBC, имеющего следующие особенности:
Нет аутентификации, но она нам тут и не нужна, так как уже достигается через цифровую подпись.
Скрывает точную длину открытого текста, так как длина закрытого текста получается кратной размеру блока в 16 байт.
Не увеличивает размер текста на длину вектора инициализации и тега аутентификации, если не считать 1 байт для длины паддинга.
❔ Возможно вы знаете алгоритм шифрования, который лучше подойдёт для нашей задачи?
По размерам получается относительно компактно:
Приватный ключ |
32 байта |
Публичный ключ |
64 байта |
Цифровая подпись |
64 байта |
Общий секрет |
32 байта |
Блок шифра |
16 байт |
И если размеры ключей не столь важны, а секрет можно спокойно обрезать до нужной длины, то размер подписи имеет существенное значение. Если нам надо сохранить лишь 1 бит информации, то добавлять к нему в 512 раз больше бит для аутентификации кажется сильно избыточным. Ну ладно, в байтах разница будет уже в 64 раза, но это тоже довольно не мало.
❔ А есть ли алгоритмы, дающие меньшие размеры подписей, сохраняющие при этом достойный уровень криптостойкости?
Я нашёл только скупую информацию о BN-254, имеющего следующие характеристики:
Приватный ключ |
32 байта |
Публичный ключ |
64 байта |
Цифровая подпись |
32 байта |
Криптостойкость |
Многообещающе! К тому же тут есть возможность агрегировать несколько ключей/подписей в один/одну. Но.. с реализациями тут совсем всё плохо.
❔ Не хочет ли кто-то заморочиться над компактной и шустро реализацией BN254 на TS?
Размеры
Ну да ладно, булевы значения не так уж часто встречаются. Куда чаще это текст, разбитый на токены. Минимальный семантически значимый размер токена - это слово. Его имеет смысл всегда заменять атомарно.
А вот изменения в разных словах, внесённые разными пользователями, обычно не связаны и не должны конфликтовать друг с другом. То есть каждый токен должен описываться отдельным независимым юнитом, хранящим как сами данные, так и мета-информацию об их положении, авторе и пр.
Давайте прикинем, сколько нам надо места для хранения одного слова. Для этого возьмём распределение слов по длинам в русском языке:
Учитывая, что каждая русская буква в UTF-8 занимает 2 байта, получаем среднюю длину слова порядка 20 байт.
❔ Стоит ли делать юниты фиксированной или переменной длины?
Переменная длина позволяет более плотно упаковывать информацию. С другой стороны, фиксированная длина имеет больше преимуществ:
Всегда заранее понятно сколько памяти надо на них выделять.
Юниты можно быстро обновлять на месте не боясь налезть на соседние.
Юниты получаются всегда выровненными по границам физических блоков памяти, что упрощает и ускоряет работу с ними.
Основные физические блоки можно выделить следующие:
Машинное слово - единица обработки в процессоре. Сейчас это обычно 8 байт.
Кеш-линия процессора - единица атомарной работы с памятью. Сейчас это обычно 64 байта.
Страница памяти - единица надёжного ввода/вывода между памятью, файловой системой, накопителем и пр. В современных реалиях точно можно рассчитывать на 4КБ.
Учитывая, что одна кэш-линия у нас уходит на цифровую подпись, имеет смысл выделить две кэш-линии для всего юнита, то есть 128 байт.
Соотношение размера юнита к собственно данным в байтах таким образом будет в среднем 6 для русского слова и 128 для булевого значения.
Идентификаторы
Так как у нас децентрализация, то мы не можем себе позволить выделенный сервер, который бы выдавал нам последовательные короткие идентификаторы. Каждый узел, независимо от других, должен иметь возможность сгенерировать идентификатор с пренебрежимо малой вероятностью коллизии. То есть это должна быть квази-рандомная последовательность байт. И чем короче будет эта последовательность, тем больше места в юните останется для прикладных данных.
❔ Сколько байт необходимо и достаточно для идентификаторов?
Так как часто идентификаторы надо представлять в удобном для пользователя текстовом виде, то они будут часто преобразовываться в одно из base64 представлений, которое даёт 4 байта из каждых 3. И если мы хотим максимально эффективное использование каждого символа в идентификаторе, то он должен быть кратен 4 в текстовом виде или 3 в бинарном.
Давайте воспользуемся формулой приближённого вычисления максимального числа генераций с вероятностью коллизии не более заданной:
вероятность \ байт |
4 |
6 |
8 |
9 |
12 |
один на миллион |
92 |
23_726 |
6_074_002 |
97_184_040 |
398_065_829_050 |
один на миллиард |
2 |
750 |
192_076 |
3_073_228 |
12_587_944_155 |
Учитывая, что на земле уже почти 10 миллиардов человек, то 9 байт на всех явно не хватит. Понятное дело, что далеко не все будут нашими пользователями, ну так и на каждого человека потребуется далеко не один идентификатор, ведь у него может быть несколько девайсов, профилей и тп, которые с точки зрения системы буду отдельными субъектами, которых мы будем называть лордами.
В общем, кажется 12 байт для идентификации лорда нам всё же хватит. Но просто на рандом мы полагаться не можем - надо как-то подтвердить владение этим идентификатором. Поэтому рандомно мы будем генерировать приватный ключ, из него публичный, а из него уже вырезать 12 байт в качестве идентификатора.
Ещё один бонус такой генерации идентификатора - некоторая ресурсоёмкость этого процесса. То есть нельзя просто взять и мгновенно "застолбить" все возможные идентификаторы - нужно совершить некоторую работу. И наличие приватного ключа - это доказательство проделанной работы (Proof of Work).
Однако, это не очень большая работа, поэтому добавим для публичных ключей ещё одно условие: он должен начинаться с байта 0xFF. Это условие повышает стоимость генерации ключа в 256 раз. На практике это занимает в среднем несколько десятков миллисекунд, что не сильно влияет на UX, но делает не выгодной спам-атаку.
❔ Достаточно ли требовать фиксированный префикс публичного ключа для PoW генерации нового идентификатора или стоит насыпать ещё и хешей?
Однако, порой необходимо разом создать много однотипных лендов, тогда имеет смысл использовать идентификатор лорда как префикс, к которому добавлять ещё и 6-байтный идентификатор арии (area) - такие ленды уже захватываются мгновенно.
Ленды имеет смысл оставлять относительно не большими, чтобы их синхронизация происходила быстро, и не требовала загрузки больших объёмов лишних данных, помимо тех, что нам интересны. Например, в 1 МБ у помещается 8192 юнита по 128 байт каждый. Стоит проектировать структуру группировки узлов по лендам так, чтобы в каждом из них было не более нескольких тысяч юнитов.
Соответственно и требования к идентификаторам в рамках одного ленда существенно ниже. Более того, так как ленд синхронизируется целиком, то при генерации локального идентификатора узла, можно сразу проверять его на коллизии. То есть для локальных идентификаторов хватит и 6 байт.
Итого, максимальный глобальный идентификатор узла получается как 12 байт лорда, 6 байт арии, 6 байт узла = 24 байт в бинарном виде, или 32 байта в base64 представлении.
Типизация
Данные, записываемые в юнит, сохраняются атомарно и разные версии никак не мёржатся - значение либо одно, либо другое. Например, если один пользователь ввёл один номер телефона, а другой - иной, то было бы странно получить несуществующий номер вместо одного из этих двух. Однако, в случае параграфа текста, было бы классно не терять правки каждого пользователя и объединять их. Если только это не криптографический сертификат..
Короче, тех же строк нам нужно как минимум 2 типа:
Атомарная. Хранится как один юнит.
Конвергентная. Хранится как список юнитов, каждый из которых представляет атомарную подстроку.
❔ Какие типы данных нужно поддержать в юнитах?
Я бы выделил как минимум следующие 16 (слева указан их tip, сохраняемый в метаданных):
? nil - просто нет данных, они стёрты.
? bin - некоторый абстрактный бинарник (до 32 байт влезает в один юнит).
? bool - булево значение.
1️⃣ int - 64-битное целое число со знаком.
? real - 64-битное вещественное число.
? ints - массив целых чисел (до 4 влезает в один юнит).
✨ reals - массив вещественных чисел (до 4 влезает в один юнит).
? ref - Ссылка на узел/ленд/арию/лорда (24 байта).
? str - UTF-8 строка.
⏰ time - момент времени в ISO8601 представлении.
? dur - временная продолжительность в ISO8601 представлении.
? range - временной интервал в ISO8601 представлении.
? json - JSON объект.
? jsan - JSON массив.
? dom - DOM в XML представлении.
? tree - абстрактное синтаксическое дерево.
Так же введём понятие тэга (tag), позволяющее сохранить в метаданных интерпретацию юнитов, вложенных в данный:
? Term - вложенные не предполагаются (как, например, для токена текста).
? Solo - внутри ожидается один (первый) юнит - характерно для атомарных регистров.
? Vals - внутри ожидается список юнитов - это различные списки.
? Keys - внутри ожидается список юнитов в каждом из которых тоже ожидаются юниты - это различные словари.
И этих примитивов уже достаточно, чтобы собрать различные конвергентные структуры: от плоского текста до объектной модели документа.
Так, например, представляется конвергентный JSON:
А так уже конвергентный DOM:
Обратите внимание, что DOM, например, может быть интерпретирован как JSON и наоборот. Это значит, что когда у нас в базе уже что-то лежит, один пользователь это редактирует, а другой одновременно меняет тип, то значение не исчезает бесследно и не выдаётся ошибка - показывается более-менее адекватный результат реинтерпретации.
Более того, разные пользователи могут одновременно редактировать такие структуры смотря на них через призму разных типов, и их изменения будут мёржиться. Например, такая ситуация возможна, когда часть узлов уже используют новую версию приложения, а часть ещё старую.
Фактически, это слабая типизация на уровне базы данных. И это крутая фича, позволяющая приложению не падать: что бы кто в неё ни записал - получим мы тот тип, который ожидаем.
Соответственно на уровне кода мы уже описываем эти ожидания в виде строго типизированной схемы. Пример на TypeScript:
class Article extends Dict.with({ // структура с полями
title: Atom_str, // атомарная строка
body: Text, // конвергентный текст
links: Refs_to( ()=> Article ) // список ссылок на иные статьи
})
При чтении данные по максимуму приводятся к заданной схеме, чтобы в базе ни лежало, а при записи база обновляется минимально инвазивно, сохраняя то, про что эта схема не знает. Это даёт и прямую и обратную совместимость при изменении схемы.
❔ Возможно ли внутреннюю модель сделать ещё более универсальной, чтобы реинтерпретация давала ещё более ожидаемые результаты?
Авторизация
При децентрализации, права на запись проверяются не каким-то выделенным сервисом, а каждым участником сети независимо. Тут нам бы помогли смарт-контракты, однако:
Их поддержку сложно реализовать, что усложняет портирование.
Они относительно медленно работают.
В них легко допустить фатальную ошибку.
Для их написания нужна высокая квалификация.
Нам бы что-то попроще - такую систему прав, чтобы она была легко понимаема кем угодно, но при этом была достаточно гибка для создания широкого спектра приложений.
Сперва определимся с гранулярностью прав. При синхронизации ленда у нас должна быть вся необходимая информация для того, чтобы принять новые юниты от другого пира или отклонить их. То есть ленд должен быть полностью самодостаточным в этом плане. Но если выдавать права отдельно для каждого узла или даже юнита, то это будет довольно большая избыточность.
Мы пока остановимся на гранулярности до ленда. Хочешь отдельный набор прав для какого-то поля сущности - выноси его в отдельный ленд. Получаются "лишние" ленды, с независимой атомарностью. Кроме того, динамическое изменение набора прав сопряжено с необходимостью серьёзно менять структуру базы данных и код работы с ней.
❔ Выглядит как-то не очень красиво. Есть ли более элегантное решение?
Базово можно выделите следующие уровни прав:
?
nil- нельзя ни писать, ни читать.?
get- можно только читать.?
reg- можно читать и авторизовываться, но не вносить изменения.✍
mod- можно читать и менять что угодно, кроме прав.?
law- можно делать всё, и даже выдавать права.
Права могут быть выданы как конкретному пиру, так и всем по умолчанию. Если по умолчанию нет права на чтения, то весь ленд автоматически шифруется.
❔ Достаточно ли такой системы прав или чего-то не хватает?
Теперь определимся с источником власти на ленд. Варианта я вижу два:
Префикс автора в идентификаторе ленда. Тогда эта власть получается не отчуждаема, что не очень подходит для совместной работы с общими ресурсами, ведь создатель ресурса остаётся его владельцем навсегда. А идентификаторы выходят ещё более 12 байт. Зато получение такого ленда быстрое и синхронное.
Захват ленда временным лордом и настройка нужных прав. За каждым лордом закрепляется ленд с тем же идентификатором (home) - на него у лорда полные права. Тогда лорды и ленды разделяют единое пространство идентификаторов в 12 байт, а автор может иметь пониженные права для свежесозданного ленда. Все арии этого ленда наследуют от него права. Получение такого ленда уже является относительно долгим и асинхронным.
Оба варианта имеют свои важные достоинства и серьёзные ограничения, так что имеет смысл поддержать оба варианта.
Коммуникация
Архитектурно можно выделить 3 типа протоколов коммуникации между 2 узлами:
Sending - узлы посылают друг другу разные данные (message, event, packet), не особо беспокоясь об их доставке. Каждый узел должен быть готов обработать любые типы сообщений. Подходит для онлайн-трансляций, но не для баз данных.
Calling - узлы посылают друг другу запросы (request, query) и ждут на них ответы (response, report). Каждый узел вынужден поддерживать множество типов запросов, каждому из которых соответствует свой тип ответа. Запрос может не дойти и тогда его надо повторить. Ответ может не дойти и тогда повторный запрос должен быть проигнорирован. Автор запроса может быть перезагружен, но запрос не должен потеряться, пока не получен ответ. Обработчик запроса может упасть и запрос должен быть направлен другому узлу. Запросы нельзя переупорядочивать - они должны быть обработаны в том же порядке, что и созданы. Обеспечение всех этих гарантий - весьма не простая задача.
Syncing - узлы обмениваются информацией о том, что у них есть (face, digest), а потом начинают слать недостающую партнёру информацию (diff, delta) по мере её появления. Это крайне простой и надёжный механизм работы, гарантирующий доставку всех данных до каждого узла даже в условиях регулярного обрыва связи.
Мы, конечно же, остановимся на последнем варианте:
Ситуация со множеством узлов имеет свои особенности. Прямые соединения всех со всеми не разумно, так как общее число соединений растёт квадратично от числа узлов.
Например, уже для 100 узлов, потребовалось бы устанавливать порядка 5 тысяч соединений для синхронизации. И каждому узлу пришлось бы делать броадкаст - рассылать все свои изменения другим 99 узлам.
Понятное дело, что это не очень эффективно и на определённых масштабах сможет парализовать любую сетевую инфраструктуру. К тому же не все узлы вообще смогут установить прямое соединение.
Поэтому часто можно встретить использование gossip протокола - рандомизированного каскадного мультикаста. Но он не гарантирует доставку за конечное число шагов. Зато можно быть уверенными, что к одному и тому же узлу одна и та же информация прилетит по многу раз с разных сторон.
Хочется чего-то более детерминированного, быстрого, экономного, но при этом достаточно надёжного. Заметим, что если топология нашей сети будет представлять дерево, информация от любого узла легко сможет дойти до любого другого ровно по одному пути без дублирования.
Но деревья бывают разные. Чем выше дерево (вырожденный случай - все узлы в одну длинную ветку), тем больше промежуточных узлов, тем большая будет задержка синхронизации. Чем ниже дерево (вырожденный случай - топология звезды с одним узлом к которому подключены все остальные), тем меньше промежуточных узлов, тем меньше задержка, но больше нагрузка на эти промежуточные узлы и риск их полного выхода из строя.
❔ Как сохранять связность сети в условиях динамического состава участников, удерживая их в составе живого дерева разумно минимальной высоты?
Мне пока что на ум приходит следующий простой алгоритм:
В базе лежит упорядоченный список узлов, готовых выступать серверами.
Остальные (клиентские) узлы подключается к первому же серверу из списка.
Если подключиться не удалось (узел упал или не держит нагрузку), то подключается к следующему.
И так до конца списка, а потом с начала.
Если соединение удалось, но потом оборвалось - подключение начинается уже с него, а не начала списка.
Каждый сервер находит себя в списке серверов, и использует список узлов после себя так же как клиентский узел.
В результате мы получаем несколько больших, соединённых друг с другом, звёзд, и длинный хвост резервных реплик, на случай повышения нагрузки или даже падения первых узлов.
На нижней схеме вы видите случай, когда второй узел не выдержал нагрузки и временно упал, поэтому первый подключился к третьему, который принял на себя часть нагрузки со второго, что позволило тому вернуться в строй.
Разумеется, если реплицировать все данные между всеми узлами, то на них быстро кончится память. Нет смысла создавать так много копий одних и тех же данных. Поэтому по мере роста с числа серверов можно будет уже разделать всю сеть на подсети, раскидывая данные по ним исходя из идентификаторов лендов. На той же диаграмме можно заметить 2 непересекающихся подсети, каждая из которых синхронизирует свою половину данных.
Хранение
Писать данные прямо в файл было бы слишком просто. А вдруг мы упадём по среди записи? А вдруг отключат свет? А вдруг потоп? Для безопасной записи обычно используют разные хитрые техники дублирования информации:
WAL (Write Ahead Log). Сначала пишем в отдельный лог (UNDO или REDO), что хотим сделать, потом делаем, затем помечаем, что сделали. При перезапуске повторяем незаконченные изменения (или откатываем сделанные).
COW (Copy On Write). Вместо изменения существующих данных, новая версия записывается в свободное место и меняются все ссылки на данные. Когда на участок файла не остаётся ссылок - он освобождается для будущих записей. При перезапуске собирается мусор от незаконченных транзакций.
LSS (Log Structured Storage). Вообще отказываемся от изменений в пользу добавления записей в бесконечно растущий структурированный лог. При перезапуске лог обрезается до последнего зафиксированного изменения.
Сравним, насколько хорошо они справляются с разными аномалиями при проведении транзакции:
Аномалии |
WAL |
COW |
LSS |
RAW |
Повреждение при записи |
✅ |
✅ |
✅ |
✅ |
Неатомарная транзакция |
✅ |
❌ |
✅ |
❌ |
Повреждение накопителя |
❌ |
❌ |
⭕ |
❌ |
Шифрация трояном |
❌ |
❌ |
❌ |
❌ |
Легенда: ✅ полная защита, ⭕ нужны ухищрения, ❌ беззащитность.
Как видно из таблицы, как бы мы ни извращались, а одной реплики катастрофически мало для гарантии сохранности данных.
Я так же добавил сюда и RAW (Replicated Atomic Writes) - обновление данных на месте атомарными порциями не более 4КБ, чтобы точно укладываться в гарантии атомарности как операционных, так и файловых систем. Мы можем себе это позволить, так как в 4КБ помещается ровно 32 юнита. А вот блобы сохраняются по хешу, так что они всегда неизменны, и если при чтении хеши не совпадают, то они игнорируются полностью.
Использование RAW позволяет очень быстро писать данные, без дублирования на том же узле. Вместо этого, дублирование происходит на репликах, которые всё равно нужны для надёжности, какой бы подход к хранению на одном узле мы ни использовали. Например, добавим репликацию с контролем аутентификации и авторизации:
Аномалии |
WAL |
COW |
LSS |
RAW |
Повреждение при записи |
✅ |
✅ |
✅ |
✅ |
Неатомарная транзакция |
✅ |
❌ |
✅ |
❌ |
Повреждение накопителя |
✅ |
✅ |
✅ |
✅ |
Шифрация трояном |
✅ |
✅ |
✅ |
✅ |
Однако, всё равно остаётся риск, что узел, вносящий изменения, не успеет ни записать, ни реплицировать все изменения из транзакции, от чего она так и останется в системе применённой лишь частично.
❔ Возможно ли обеспечить для подхода RAW и атомарность транзакций?
Мне видится такой путь:
Отсылаем на реплику дельту.
Дожидаемся от неё подтверждение, что дельта применена.
Обновляем данные в хранилище.
В случае падения, получаем недостающие данные с реплики.
Но в офлайне это не поможет. Для него нужно сохранять новые данные в лог, словно бы это была реплика. А при сохранении данных в основное хранилище или подключении реплики и отсылке данных ей, чистить и этот лог.
Вот чёрт, кажется мы изобрели WAL. Но только не постоянный, а резервный.
ACID
Основные требования к СУБД образуют аббревиатуру ACID. Разберём их по отдельности..
Atomicity
Все изменения вносятся в памяти узла, а потом атомарно сбрасываются на диск и одновременно отсылаются другим пирам, которые атомарно применяют их в памяти, одновременно сбрасывая на диск и отсылая дальше.
Важно отметить, что откаты не предусмотрены концептуально: если какой-то узел увидел какие-то изменения, то их примут и все остальные узлы.
Consistency
Так как все изменения вносятся независимо, а потом автоматически объединяются, возможно образование несогласованного состояния. Простой пример:
Однако, тут спасает подход Read-Repair: несогласованное состояние приводится к согласованному при чтении благодаря дополнительной мета-информации.
В примере с Алисой и Бобом достаточно разорвать родственную связь, время внесения которой оказалось раньше.
❔ Существуют ли такие не консистентные состояние, которые не возможно было бы восстановить при чтении?
Isolation
Каждый узел меняет своё локальное состояние в синхронной манере. Остальным узлам изменения становятся доступны лишь после синхронизации, которая приостанавливается на время внесения узлом изменений.
Durability
Любые повреждения хранилища приводят лишь к игнорированию сломанных юнитов. При синхронизации они прилетают с других узлов, если те их видели.
Jepsen
Классификация Jepsen призвана упорядочить гарантии, которые дают разные СУБД. К сожалению, помимо запутанности, в ней присутствует и ряд сомнительных моментов. Поэтому я позволил себе её немного отрефакторить, сделав более ясной и непротиворечивой:
Как видно, CRUS даёт максимальные гарантии при сохранении доступности:
-
Repeatable Read. Все транзакции производятся в локальной копии и лишь по завершении уже синхронизируются с другими узлами. В других СУБД тот же эффект достигается за счёт Snapshot Isolation или Client-Side Transactions.
Важно отметить, что в общем случае невозможно предотвратить Lost Update, не жертвуя доступностью. Тем не менее за счёт микрогранулярности хранения данных, вероятность такой аномалии концептуально ниже, чем у других СУБД.
-
Causal. Разница между узлами применяется атомарно и естественным образом содержит все исторические эффекты.
Важно отметить, что независимо внесённые разными узлами изменения могут прийти в разном порядке, однако результат их слияния будет идентичен.
❔ Нет ли существенных изъянов в представленной классификации? Или может быть не хватает чего-то важного?
CAP / PACELS
CAP-теорема гласит, что невозможно обеспечить и распределённость и актуальность, и доступность одновременно. То есть проектируя распределённую систему приходится выбирать, чем из этих важных качеств пожертвовать:
Либо жертвуем доступностью, и тогда при разделении сети часть узлов или даже все они превращаются в тыкву, так как не могут гарантировать, что содержат все последние изменения.
Либо жертвуем актуальностью, и тогда при разделении сети узлы будут возвращать возможно устаревшие данные.
Либо жертвуем распределённостью, и тогда держим все данные на одном единственном узле.
Отметим, однако, что недоступная система - штука бесполезная, полагаться на бесперебойность работы одного узла слишком самонадеянно, а неактуальность данных - обычное дело в реальном мире. Поэтому лучше пожертвовать актуальностью (AP - доступность при разделении), но при этом понимать, что рано или поздно все обновления всё равно прилетят.
PACELS-теорема развивает проблематику CAP, предлагая выбор между задержками и актуальностью, когда разделения сети нет.
Важно отметить, что с прикладной точки зрения достаточно долгая задержка неотличима от разделения сети. И если мы будем гнаться за актуальностью, то на большом числе высоко нагруженных узлов, подключённых по не самым быстрым каналам связи, задержки быстро станут неприемлемыми. А лавинный эффект может приводить и к собственно разделению сети ввиду падения узлов. Поэтому тут тоже отдаём предпочтение доступности (PA/EL - минимизация задержки и гарантия доступности).
Заключение
Это далеко не все вопросы, которыми я задаюсь. Но для начала дискуссии, думаю хватит.
Больше подробностей по разрабатываемой базе данных вы можете найти на её сайте: crus.hyoo.ru. Там есть и технические детали, и инструкции, и браузер по базе, и авто админка, и майнер crus-ивых идентификаторов, и мониторинг потребления ресурсов.
Но важно понимать, что всё это является плодом ещё не законченной научно-исследовательской работы без сколь-либо серьёзной практики внедрения. Так что нам нужна ваша помощь в проверке жизнеспособности как заложенных в неё идей вообще, так и конкретной реализации в частности.
Думаю это одна из последних моих обстоятельных статей на Хабре. Всё же отношение этой площадки к авторам довольно скверное, а аудитория, мягко выражаясь, не особо благодарная. Подобные статьи давно уже не имеют шансов выбраться на главную. По моей карме заметно, что мне тут не рады: уже есть ограничения на комментарии, а скоро я не смогу публиковать и статьи.
Если вы хотите быть в курсе новостей касательно моих научных исследований, инновационных разработок и просто безумных идей, то подписывайтесь на канал mam_mol в телеграме. Посты там выходят редко, но метко. Вот лишь часть наиболее интересных материалов от меня:
А вот, что у меня есть ближайших планах:
Простое и понятное объяснение CRDT со сравнительным анализом всех типов алгоритмов, включая самые сложные для CRDT - упорядоченные структуры.
Построение открытой коллаборативной платформы на базе CRUS-DB: от мессенджера и коллаборативного редактора до системы контроля версий и децентрализованного хостинга.
Всё это тесно интегрированно друг с другом и системой монетизации поощряющей авторов и подкрепляющей рекомендации рублём.
Разработка легковесного веб-движка для 3D игр со мгновенным запуском и стабильными 60 FPS.
Всё это, разумеется, на $mol. И уже даже есть прототипы. Если интересна вся эта наркомания, то заглядывайте к нам на форум: h_y_o_o. Там вы с большей вероятностью найдёте ответ, чем на Хабре или в личке.
С вами был дракон гильдии Гипер Дев, Дмитрий Карловский.
Актуальный оригинал на $hyoo_page.
