МойОфис продолжает цикл публикаций (1, 2) о разработке корпоративной почтовой системы нового поколения Mailion, которая реализуется при грантовой поддержке РФРИТ. В состав Mailion входит объектное хранилище DOS; в предыдущей статье мы рассмотрели его общую архитектуру и ключевые оптимизации, повышающие экономическую эффективность хранения данных. Сегодня мы переходим к одной из самых сложных и увлекательных тем в области разработки баз данных — проблеме масштабирования.
Хабр, привет! Меня зовут Виталий Исаев, в компании МойОфис я отвечаю за разработку объектного хранилища DOS. Лишь в небольших, не рассчитанных на высокую нагрузку проектах можно хранить данные на одном сервере (пусть даже очень мощном). Во всех остальных случаях необходимо использовать горизонтально масштабируемые (scale-out) хранилища. В этом материале я расскажу об общих принципах проектирования систем подобного класса.
Принципы построения распределённых баз данных
Что такое распределённая база данных
Классические реляционные системы управления базами данных, доминировавшие на рынке в 1970-2000 гг., проектировались в ожидании, что мощности единственного сервера будет достаточно для хранения всей информации. Однако бурное развитие Интернета заставило искать пути преодоления этого ограничения и активизировало исследования в области распределённых систем и баз данных.
В своей классической монографии Тамир Ёсу и Патрик Вальдуриес определяют распределённую базу данных как набор из нескольких логически взаимосвязанных баз данных, расположенных в узлах распределённой системы. Элементы распределённой системы автономны, не имеют прямого доступа к состоянию друг друга и вынуждены обмениваться сообщениями, что привносит накладные расходы на коммуникацию.
Для распределённых СУБД характерны такие приёмы организации хранения данных, как фрагментация и репликация.
Ключевые компромиссы
Распределённые СУБД обладают массой полезных свойств:
Прозрачность. Интерфейсы одиночной и распределённой СУБД с точки зрения клиента ничем не отличаются. От пользователя скрыты подробности сетевых ошибок, возникающих при взаимодействии узлов, равно как и сам факт существования такой сети. Пользователь ничего не знает о фрагментации и распределении данных между узлами и работает с данными так, как будто в системе хранится лишь одна их копия.
Отказоустойчивость. Хранение данных в нескольких копиях нивелирует проблему единой точки отказа. В зависимости от конфигурации, распределённая СУБД может продолжить работу при выходе из строя одного или нескольких узлов.
Повышенная по сравнению с одиночными СУБД производительность за счёт эффекта локальности данных и распараллеливания нагрузки по узлам кластера при обработке запросов.
Масштабируемость. Архитектура распределённых СУБД позволяет быстро адаптироваться к увеличению количества данных и пользовательских запросов путём добавления новых узлов.
Однако эти свойства не достаются просто так. Сеть, по которой узлы обмениваются сообщениями, может выйти из строя, а нарушение коммуникации между узлами вследствие network partition (P) способно привести копии данных на некоторых узлах в несогласованное состояние. В этой ситуации СУБД может либо попытаться продолжить обработку запросов силами оставшихся узлов, но при этом нарушить линеаризуемость, либо же прекратить обработку запросов, чтобы линеаризуемость сохранить. Таким образом, в распределённых СУБД доступность (availability, A) и согласованность (consistency, C) данных всегда находятся в противоречии друг с другом. Это наблюдение было сформулировано в 2000 г. Эриком Брюером в широко известной CAP-теореме.
Несмотря на то, что в последующие годы CAP-теорема часто подвергалась критике за размытость формулировок, в сообществе разработчиков баз данных сложилась устойчивая классификация кластерных СУБД на CP- и AP-базы. CP-базы поддерживают свойство линеаризуемости, но жертвуют доступностью. Как правило, разработчики приложений начинают с того, что требуют от СУБД линеаризуемости (потому что так гораздо проще писать прикладной код), однако столкнувшись с производительностью CP-баз, начинают снижать требования к согласованности. Благодаря тому, что AP-базы реализуют более слабые модели согласованности, повышаются их доступность и производительность.
В качестве развития CAP-теоремы можно упомянуть PACELC-теорему, представленную Даниэлем Абади в 2012 г. Действительно, при возникновении сетевых проблем (P) СУБД должна выбирать между доступностью (A) и согласованностью данных (C). Но в нормальном режиме работы (else, E), когда проблем нет, существует не менее важный компромисс между временем отклика (latency, L) и согласованностью данных (С). Его причина заключается в репликации: синхронная модификация данных сразу во всех репликах — дорогая операция, но всегда можно снизить время отклика, выполняя обновление некоторых реплик асинхронно. PACELC-теорема даёт более гибкую классификацию: к классам AP, CP добавляются EL и EC, и оказывается, что многие распределённые СУБД могут относиться сразу к нескольким из этих классов. Tunable consistency — один из трендов развития современных распределённых СУБД.
Наконец, стоит упомянуть о новейших СУБД, которые позиционируют себя в качестве продуктов, сумевших преодолеть фундаментальное разделение на классы AP и CP. Одной из первых стала глобально распределённая СУБД Spanner от Google. Технически Spanner относится к классу CP, но за счёт высокой доступности (99,99999%) выглядит для конечных пользователей как база теоретически невозможного класса CAP. Высокая доступность достигается за счёт огромных инвестиций в инфраструктуру (в 2019 г. Google потратил $13 млрд. на строительство новых ЦОД). Узлы Spanner общаются не через Интернет, а через частную глобальную сеть Google с резервированными линиями связи между дата-центрами. Для упорядочения транзакций Spanner использует сервис глобально синхронизированных часов TrueTime, который опирается на атомные часы и спутники GPS, что позволяет достичь точность на 1-2 порядка выше, чем у NTP. Все эти технические новшества помогают Google выстроить инфраструктуру с чрезвычайно низкой вероятностью network partition, но при этом делают Spanner неотделимым от этой (очень дорогой) инфраструктуры.
СУБД Spanner вдохновила создателей таких СУБД с открытым исходным кодом, как CocroachDB и TiDB. Но очевидно, что столь же эффективными последователи Spanner могут быть только при условии высокой доступности и больших вложений в инфраструктуру, которые едва ли могут быть обеспечены пользователями этих продуктов. Например, CocroachDB тоже нуждается в глобальной синхронизации, и его авторы даже выпустили разъяснения о том, как CocroachDB пытается обойтись без атомных часов. Нам же важно ещё раз подчеркнуть, что CAP-теорема не опровергнута.
Фрагментация данных
Большого внимания требуют технологии горизонтальной фрагментации и распределения данных по узлам распределённой СУБД. Алгоритм фрагментации должен:
Предоставлять возможность быстрого определения узла, ответственного за хранение данных. Эта операция выполняется при обработке любых клиентских запросов и должна быть реализована оптимально.
Способствовать правильной балансировке нагрузки в системе. Наиболее продвинутые техники должны учитывать топологию дата-центра, возможную гетерогенность инфраструктуры, различия в мощности серверов, объёмы дисков и другие параметры.
Обеспечивать масштабирование системы.
Последнее требование стоит рассмотреть особо. Создатель Elliptics Евгений Поляков в одном из своих выступлений делит крупные СХД на две группы: системы ограниченного объёма и неограниченного объёма. Каждую из них отличает свой собственный подход к фрагментации и масштабированию.
Системы ограниченного объёма и медленнорастущие системы
В таких системах существует определённый баланс между запросами на запись и на удаление данных, поэтому они либо совсем не растут, либо растут очень медленно. Чаще всего хранение данных в них организовано с помощью DHT. Каждый узел системы является шардом, то есть отвечает за хранение какого-то подмножества ключей. Каждый из шардов обрабатывает запросы на чтение старых ключей и на запись новых ключей из своего диапазона. Масштабирование DHT осуществляется за счёт добавления в кластер новых узлов (шардов). После этого выполняется ребалансировка данных между шардами для того, чтобы данные были распределены по кластеру в соответствии с новой картой размещения. Ребалансировка помогает выровнять нагрузку на члены кластера и решить проблему горячих точек. Однако провести эту ресурсоёмкую операцию можно далеко не всегда: иногда узким местом становятся диски, а иногда и сеть, особенно если речь идёт о кросс-датацентровой инсталляции СУБД.
Для организации DHT используются специальные алгоритмы фрагментации, которые минимизируют перемещение данных между узлами при ребалансировке. На конференции Highload-2016 они подробно рассматривались Константином Осиповым @kostja и Алексеем Рыбаком @fisher. Наибольшего внимания на сегодняшний день заслуживают два метода: табличная функция и консистентное хеширование.
Табличная функция
Метод фрагментации через табличную функцию построен на двух отображениях:
Ключ данных -> виртуальная нода (virtual node).
Виртуальная нода -> идентификатор физического узла.
Сначала весь диапазон ключей разбивается на большое количество виртуальных нод: каждая виртуальная нода должна быть небольшой, чтобы относящиеся к ней данные можно было сравнительно легко перемещать между физическими узлами. Второе отображение задаётся в виде таблицы, в которой написано, какими виртуальными нодами владеет тот или иной физический узел. Если требуется провести ребалансировку, задаётся новое отображение виртуальных нод в идентификаторы физических узлов, рассчитывается разница между двумя отображениями, и виртуальные ноды, поменявшие расположение в кластере, перемещаются между узлами.
Метод табличной функции очень гибок и позволяет администраторам настроить любое размещение данных в кластере. Это одновременно является и минусом: неправильная табличная функция может привести к огромным дисбалансам нагрузки. Ещё одним недостатком считается привнесение глобального состояния — таблицы, отображающей виртуальные ноды в физические узлы: в распределённой системе введение глобального состояния всегда сопряжено с проблемами. В некоторых архитектурах эта проблема решается с помощью отдельного сервиса, консистентно хранящего это отображение: все запросы начинают проходить через этот сервис, что приводит к появлению горячей точки в системе.
Консистентное хеширование
Консистентный хеш — математическая функция, которая принимает ключ данных, количество физических узлов в системе и возвращает идентификатор узла, ответственного за хранение данных. Если количество физических узлов в системе изменилось, функция учитывает это и выдаёт новое разбиение. Благодаря функции стоимость перемещения ключей при изменении состава кластера составляет в среднем O(K/N), где K — количество ключей, N — количество узлов, тогда как для обычной хеш-таблицы она возрастает до O(K). Побочный эффект хеширования —перемешивание ключей и, как следствие, выравнивание нагрузки внутри кластера.
Имплементация алгоритмов консистентного хеширования почти всегда строится на абстракции кольца хешей. Все возможные значения хеширующей функции "сворачиваются" в кольцо, при итерации по которому за самым старшим из возможных значений хеша будет следовать самое младшее значение. Физические узлы также размещаются на этом кольце и делят его на диапазоны: в зону ответственности физического узла входят все хеши, располагающиеся на кольце по часовой стрелке после точки его размещения. Когда в систему добавляется новый узел, он получает место на кольце и забирает часть диапазона, ранее принадлежавшего другому физическому узлу. Ребалансировка данных выполняется полным проходом по всем ключам старого узла, вычислением хеша каждого из ключей и перемещением нужных ключей на новый узел.
В чистом виде алгоритм консистентного хеширования используется редко: в большинстве случаев приходится вводить виртуальные ноды, а значит, снова хранить глобальное состояние. Одной из первых распределённых СУБД, использовавших консистентный хеш для фрагментации данных, стала Amazon Dynamo (не путать с Amazon DynamoDB). Дизайн этой СУБД был опубликован в 2007 г. и оказал большое влияние на Cassandra, Riak и многие другие NoSQL-базы. Интересно, что у разработчиков Cassandra несколько раз менялось отношение к количеству виртуальных нод: сначала оно совпадало с количеством физических узлов, затем было резко увеличено, затем несколько снижено.
Системы неограниченного объёма
К системам такого класса относятся любая почта, файловое хранилище или фотохостинг. Информация в них постоянно хранится и постоянно добавляется. Удаление не компенсирует поступления новых данных. В какой-то момент объёмы и скорость накопления информации превышают возможности ребалансировки. Поэтому в подобных системах от неё лучше отказаться совсем. Вместо этого стоит просто перенаправить на новые узлы кластера все вновь поступающие данные. Это приводит к тому, что данные фрагментируются не по значению ключа, как в DHT, а фактически по времени их записи в систему.
Авторы MinIO, ранее работавшие над GlusterFS, поняли, что ребалансировка на объёмах более одного петабайта — рискованное мероприятие, поэтому в MinIO горизонтальное масштабирование достигается с помощью добавления не узлов (в архитектуре MinIO это потребовало бы ребалансировки), а сразу новых кластеров, и работы группы кластеров в режиме федерации.
Репликация данных
Мартин Клеппман в своей монографии о высоконагруженных системах приводит три основных причины появления репликации в распределённых СУБД:
Снижение времени отклика за счёт хранения данных в географическом регионе нахождения пользователей.
Повышение отказоустойчивости системы.
Повышение пропускной способности системы при обработке запросов на чтение.
Для репликации изменений данных между узлами распределённой СУБД, как правило, применяется одна из трёх схем: с одним ведущим узлом (single-leader), с несколькими ведущими узлами (multi-leader) и без ведущего узла (leaderless).
Репликация с одним ведущим узлом (single-leader)
Данный вид репликации является одним из наиболее распространённых в современном вебе. Лидер обрабатывает клиентские запросы, сохраняет данные у себя и отправляет обновление на ведомые узлы.
Протокол репликации при этом может быть синхронным или асинхронным. Синхронная репликация в CP-системах гарантирует строгую согласованность данных на репликах, но приводит к низкой доступности системы в целом. Если хотя бы один ведомый узел выходит из строя, это полностью блокирует обработку запросов, модифицирующих данные. Асинхронная репликация в AP-системах позволяет репликам отставать от лидера. Время отклика снижается, а доступность системы возрастает за счёт увеличения риска потери данных.
Между крайними вариантами синхронной и асинхронной репликации существует несколько компромиссных схем. Например, в распределённом реплицированном хранилище DRBD по усмотрению администратора кластера может применяться полусинхронная репликация: обработка запроса на запись блокируется до того момента, пока запись не будет произведена на диск лидера и не будет доставлена в буфер оперативной памяти (но не на диск) ведомого узла. Такой подход сильно снижает вероятность потери данных, но не исключает её полностью.
В облачном хранилище Windows Azure Storage и экспериментальной KV базе Hibari используется цепная репликация. Лидер и ведомые узлы выстраиваются в цепочку. На ближайший ведомый узел лидер реплицирует данные синхронно, а дальше данные распространяются уже асинхронно.
Репликация с несколькими ведущими узлами (multi-leader)
Этот вариант считается более экзотическим. Он встречается в ситуациях, когда необходимо, чтобы данные отказоустойчиво хранились в нескольких дата-центрах. В каждом ЦОД работает свой собственный лидер, обрабатывающий клиентские запросы. Лидер осуществляет синхронную репликацию на ведомые узлы в рамках своего дата-центра и, как правило, асинхронную репликацию лидерам в других ЦОД. Такая схема позволяет продолжать работу при выходе из строя сразу целого дата-центра. Она применяется, например, в платёжной системе «Мир»: для репликации между кластерами PostgreSQL, расположенными в разных дата-центрах, используется Kafka.
Точно в таких же терминах можно описать взаимодействие облачного сервиса и десктопных или мобильных клиентов, в которых происходит оффлайн-редактирование данных, или процесс совместного редактирования одного документа.
Существование нескольких лидеров привносит новую проблему – конфликты записи, поскольку лидеры могут параллельно обрабатывать модифицирующие запросы по одному ключу. Учитывая, что репликация между узлами такой системы почти всегда асинхронная, конфликты обнаруживаются также асинхронно, когда ошибку записи пользователю возвращать уже поздно. Поэтому необходимо заранее продумывать стратегию разрешения конфликтов.
Например, для этого можно привлечь пользователя, возвращая ему массив конфликтующих значений при первой попытке чтения ключа (конечно, это потребует от СУБД поддержки мультиверсионности). Пользователь должен выбрать нужное значение и перезаписать его.
Также есть несколько стратегий автоматического разрешения конфликтов: от самых простых (LWW) до глубоко продвинутых (CRDT, Operational transformation). Продвинутые стратегии вызывают большой интерес у разработчиков коллаборативных систем. На конференции Hydra 2020 Мартин Клеппман проводил сравнительный анализ различных имплементаций CRDT в применении к задаче совместного редактирования текста. Алгоритм operational transformation используется в текстовом редакторе компании МойОфис.
Репликация без ведущего узла (leaderless)
Для достижения максимальной доступности и производительности применяется репликация без ведущего узла. Каждому узлу распределённой СУБД разрешается обрабатывать запросы на запись. Более того, поскольку такие СУБД обычно настраиваются на высокую доступность, узлы могут обрабатывать запросы на запись, даже если некоторые из их соседей по кластеру не работают. По этой причине расхождение и отставание реплик в leaderless-системе становится обыденным явлением. Чтобы защититься от чтения устаревших данных, в таких системах обычно применяются кворумные операции: клиенты отправляют запросы на чтение и на запись одновременно в несколько реплик, при этом соблюдается соотношение:
где W и R — множества реплик, ответивших на запросы на запись и чтение данных, N — общее количество реплик.
В пересечении W и R обязательно найдётся реплика с наиболее актуальным значением запрашиваемого ключа. Пользуясь одним из механизмов разрешения конфликтов, среди множества значений клиент сможет найти актуальное.
В системах с репликацией без ведущего узла, как правило, используется самая слабая модель согласованности — согласованность в конечном счёте. Для того чтобы реплики СУБД всё-таки сходились, применяются две техники:
Разрешение конфликтов при чтении. Обращаясь к различным репликам, клиент может обнаружить расхождения и актуализировать записи в отставших репликах.
Фоновые процессы противодействия энтропии. В распределённую СУБД вводятся различные акторы, которые занимаются поиском расхождений между репликами. Часто для этого используются такие специальные структуры данных, как деревья Меркла. Данный подход считается более сложным, но и более надёжным, поскольку в отличие от первого проверяет согласованность холодных данных, которые давно никем не читались. В чём-то процесс противодействия энтропии напоминает data scrubbing в RAID-массивах корпоративного уровня.
Как и в случае с консистентным хешированием, системы с репликацией без ведущего узла стали активно развиваться после появления Amazon Dynamo. К настоящему моменту сформировался целый класс Dynamo-подобных СУБД: к нему относятся Cassandra, Riak и Voldemort и другие базы.
Заключение
В этой статье мы рассмотрели основные проблемы, с которыми сталкиваются разработчики распределённых СУБД. При проектировании новой системы подобного класса стоит начать с CAP-теоремы и принять решения по ключевым компромиссам, неизбежно присущим распределённым системам. Что важнее: согласованность или доступность, согласованность или время отклика? После этого нужно определиться, будет ли система постоянно расти или же её размеры будут ограничены. Эта информация поможет определить оптимальный способ масштабирования системы и подскажет правильный выбор моделей фрагментации и репликации данных в кластере.
Опираясь на рассмотренные механизмы, в следующей статье мы подробно расскажем об архитектуре кластера объектного хранилища DOS.
Если вам интересны распределённые системы и архитектура баз данных, приходите к нам работать!
