Как стать автором
Обновить
163.63
МойОфис
Платформа для работы с документами и коммуникаций

Как мы создаём почтовую систему нового поколения Mailion. Архитектура кластера DOS

Время на прочтение18 мин
Количество просмотров6.8K

МойОфис продолжает серию статей о корпоративной почтовой системе Mailion (1, 2), разрабатываемой при грантовой поддержке РФРИТ, и входящем в его состав объектном хранилище DOS. Мы уже рассказали об основных оптимизациях DOS, которые позволяют увеличить экономическую эффективность хранения данных, а также коснулись общих принципов построения масштабируемых хранилищ. Сегодня мы поговорим о том, как эти принципы применялись на практике в ходе работ над кластером DOS.


Привет, Хабр, это снова я — Виталий Исаев. В компании МойОфис я работаю над объектным хранилищем DOS, созданным специально для нужд корпоративной почтовой системы Mailion. Ряд оптимизаций в рамках DOS, таких как дедупликация, компрессия и кеширование данных, позволяет снизить потребление дискового пространства и сократить количество операций ввода-вывода. В Mailion на DOS возложено хранение электронных писем, аватаров пользователей, некоторых поисковых индексов и другой информации.

Сервис DOS может быть развёрнут на одном-единственном сервере в standalone режиме... но, разумеется, это решение не будет ни отказоустойчивым, ни масштабируемым. Такими свойствами обладает кластер DOS — и сегодня речь пойдёт о нём. В этом посте мы попытаемся определить место DOS в ландшафте распределённых СУБД и объяснить решения, которые были приняты при проектировании кластерного варианта хранилища.

Данные против метаданных

Впервые термин "объектное хранилище" в смысле, близком к современному, был, по-видимому, использован в 1997 г. группой исследователей, занимавшихся темой масштабирования сетевых файловых систем с помощью Network-Attached Secure Disks (NASD). В архитектуре сетевых файловых систем того времени особая роль отводилась файловому менеджеру – сервису, который преобразовывал клиентские запросы в команды для сетевых дисков, — SCSI-устройств. Весь трафик системы шёл через файловый менеджер — своего рода "бутылочное горлышко" и единую точку отказа. Инновационная идея заключалась в прямом соединении клиентов и сетевых дисков и перенаправлении большей части трафика в обход файлового менеджера. Но для этого авторам NASD пришлось реализовать часть функциональности файлового менеджера (контроль доступа, пространства имён, хранение метаинформации) на стороне сетевого диска. Так и появилось первое объектное хранилище. Каждый NASD-диск обеспечивал доступ клиентов к некоторому пространству имён файлоподобных объектов и при этом абстрагировал клиентов от работы по сложному SCSI-протоколу. Предоставление высокоуровневого API хранения данных стало отличительной чертой интерфейса объектных хранилищ разных поколений.

Важно подчеркнуть, что объект с самого начала рассматривался как совокупность неструктурированных данных (байтовой последовательности произвольной длины) и структурированных метаданных. В S3-совместимых хранилищах у каждого объекта есть обязательные системные метаданные (например: размер, дата создания, MIME-тип) и несколько вариантов клиентских метаданных (произвольные строковые KV-метаданные, пользовательские теги). Между данными и метаданными формируется своеобразная дихотомия. Возникает вопрос – как правильно их хранить?

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

Хранение метаданных в кластере

Во вводной статье мы рассматривали иерархию внутренних сущностей DOS. Большинство из них — виртуальные, и хранятся в слое метаданных. Метаданные трёх верхних уровней — документы, версии документов, чанки — размещены в индексе документов. Ключом индекса документов является хеш от идентификатора документа. Метаданные сегментов хранятся в индексе сегментов. В каждом сегменте записан "адрес" данных в кластере — идентификатор бэкенда, на который было записано тело сегмента. Ключом индекса сегментов является хеш от содержимого сегмента. Физически оба индекса размещены в отдельных column family базы RocksDB, встроенной в каждый из узлов кластера DOS.

Фрагментация метаданных

Объем метаданных, который DOS генерирует для средних и крупных объектов, как правило, на один-два порядка меньше объёма хранимых данных. Метаданные в индексе документов удаляются чаще данных. Поэтому, пользуясь терминологией из предыдущей статьи, можно считать хранилище метаданных DOS медленнорастущей системой. Для фрагментации и масштабирования систем такого класса используется подход DHT, популяризованный Dynamo-подобными KV-хранилищами.

При разработке кластера DOS было принято решение воспользоваться хорошо проверенным способом организации DHT — консистентным хешированием. В DOS применяется вариация консистентного хеширования, в которой непрерывное кольцо хешей заменяется на кольцо диапазонов (partition ring). Всё пространство возможных ключей индекса заранее делится на большое количество виртуальных нод (в DOS по умолчанию 2^16), и каждый сервер кластера получает некоторое их подмножество. При добавлении нового или выходе из строя имеющегося сервера запускается процесс решардинга, и виртуальные ноды равномерно перераспределяются между серверами.

Работа с виртуальными нодами очень удобна: при перестроениях кластера всегда понятно, какие диапазоны ключей переезжают с одного узла на другой, и можно просто создать в RocksDB итератор по указанному диапазону, чтобы переместить эти ключи. А большое количество виртуальных нод помогает выровнять нагрузку между серверами.

Для распределения виртуальных нод между серверами в DOS изначально использовался базовый алгоритм, напоминающий решето Эратосфена. Он поддерживал ключевое свойство консистентного хеширования (O(K/N) перемещений в среднем), но приводил к разбалансировке кластера. Коэффициент вариации Сv среднего количества виртуальных нод, приходящихся на один сервер, был прямо пропорционален количеству серверов, достигая 47% для N = 10 и 98% для N = 50. Иными словами, чем больше серверов добавлялось в кластер, тем сильнее становились диспропорции между отдельными машинами. Мы попробовали некоторые из опубликованных в последние годы алгоритмов консистентного хеширования — jump consistent hash, multi-probe consistent hashing, — и остановились на последнем. Данный алгоритм позволяет удерживать Сv не выше 25% для всех разумных значений N.

CP или AP?

Отказоустойчивость метаданных в DOS обеспечивается с помощью репликации. Каждая запись индекса хранится в кластере в нескольких копиях. Количество копий регулируется глобальной настройкой фактора репликации RF (по умолчанию 3). Preference list выбирается точно так же, как в Dynamo, путём движения по кольцу хешей по часовой стрелке с выбором RF уникальных узлов.

Репликация метаданных осуществляется по leaderless-схеме. Каждый из узлов системы способен обрабатывать запросы на чтение и на запись любых объектов. В системе не существует единой точки отказа, которая обладала бы знанием о размещении метаданных в кластере: эта информация доступна каждому узлу. Благодаря этому достигается максимальный уровень производительности и отказоустойчивости.

И репликация, и фрагментация реализованы абсолютно прозрачно для клиента. Он работает с кластером DOS точно так же, как с одиночной инсталляцией, и может отправлять запросы любому узлу кластера. Логика работы с репликами скрыта внутри узла-обработчика запроса.

Шардирование и репликация индексов в DOS с помощью partition ring. Для простоты количество виртуальных нод снижено до 8, физических узлов — 7, фактор репликации — 3. Для сохранения документа клиент обращается к произвольному узлу кластера (1), тот проверяет, в какой диапазон кольца попадает данный идентификатор (2). Оказывается, что за данный диапазон отвечают реплики [3, 4, 5] (3). Узел-обработчик пользовательского запроса отправляет команды на сохранение данного ключа всем репликам (4) и дожидается ответа (5). Итоговый ответ отправляется клиенту (6).
Шардирование и репликация индексов в DOS с помощью partition ring. Для простоты количество виртуальных нод снижено до 8, физических узлов — 7, фактор репликации — 3. Для сохранения документа клиент обращается к произвольному узлу кластера (1), тот проверяет, в какой диапазон кольца попадает данный идентификатор (2). Оказывается, что за данный диапазон отвечают реплики [3, 4, 5] (3). Узел-обработчик пользовательского запроса отправляет команды на сохранение данного ключа всем репликам (4) и дожидается ответа (5). Итоговый ответ отправляется клиенту (6).

Введение репликации заставляет обратиться к выбору модели согласованности. С самого начала DOS разрабатывался как основное хранилище почтовой системы Mailion. Заметим, что парты электронных писем — иммутабельные сущности. Отправленное или поступившее письмо хранится в системе в неизменном виде на протяжении всего жизненного цикла. А иммутабельность (наряду с copy-on-write, мультиверсионностью и отказом от прямого удаления данных) является излюбленным приёмом проектирования систем с согласованностью в конечном счёте. Таким образом, сам характер поступающих данных подталкивает DOS к тому, чтобы быть базой класса AP в терминах CAP. А благодаря отказу от сильной согласованности появляется возможность увеличить производительность и доступность. Однако в итоге от DOS потребовалось более гибкое решение.

Модели согласованности, репликация и упорядоченность операций в кластере

Один из главных аргументов критиков CAP-теоремы — сведение всего многообразия моделей согласованности к двум противоположным вариантам: сильной согласованности и согласованности в конечном счёте. Однако за пределами этих рамок существует большое количество моделей, часто встречающихся в практике. Обзорные публикации последних лет (1, 2, 3) различают до 50 вариантов согласованности. Модель согласованности, упорядоченность операций над объектом в распределённой системе, а также режим репликации — тесно связанные понятия. Ниже мы покажем, что DOS позволяет клиенту подбирать комбинацию этих параметров под свои потребности.

Версии документа

Базовой функцией DOS является хранение объектов, а наиболее часто используемыми методами API — запись и чтение.

Клиенты DOS, отвечающие за сохранение писем, заинтересованы в возможности параллельной записи по одному и тому же ключу. Это бывает полезно при обработке массовых рассылок, когда одновременно отправляется или принимается большое количество одинаковых по содержанию писем, и разные инстансы клиентского сервиса могут вести параллельную запись по одному и тому же идентификатору. Чтобы избежать блокировки документа на время записи его новой версии (этот потоковый процесс может продолжаться неограниченно долго), DOS реализует запись в виде неблокирующей append-операции. В результате у одного документа может появиться несколько версий с совпадающим содержимым и временем создания, но разными идентификаторами.

Чтобы прочитать конкретную версию конкретного документа, в запросе на чтение нужно указать идентификаторы документа и его версии. Но среди клиентов есть те, которые при чтении версий документов не могут указать идентификатор версии, а хотят извлекать просто последнюю по времени записанную версию. Это требует упорядочивания версий одного документа по времени. Поскольку в распределённой системе нельзя опираться на астрономическое время, используется время логическое. Каждой версии в момент записи присваивается значение логического времени в формате векторных часов. В кластере DOS время идёт вперёд по мере записи новых версий документов: при обработке запроса на запись, узел-обработчик инкрементирует на единицу свой счётчик в структуре векторных часов.

Векторные часы обладают важным свойством: для них определено отношение happened-before. Это позволяет ввести причинную упорядоченность и причинную согласованность для версий одного документа. По запросу клиента узел-обработчик запроса может отсортировать версии документа по логическому времени создания и вернуть либо самую последнюю версию, если её можно однозначно определить, либо ошибку, свидетельствующую о конфликте между несколькими последними версиями.

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

Причинная согласованность — достаточно сильная модель согласованности, а сильные модели включают в себя гарантии более слабых. Если в системе обеспечивается причинная согласованность данных, это означает, что автоматически обеспечивается и read-your-writes согласованность, а нарушение read-your-writes согласованности означает отказ от причинной согласованности. Мы воспользуемся read-your-writes моделью для того, чтобы рассмотреть компромиссы, возникающие при синхронизации реплик индекса в момент записи и чтения данных.

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

Представим следующую последовательность действий конкретного клиента над определённым документом:

  1. Запись версии A документа.

  2. Запись версии B документа.

  3. Чтение последней записанной версии.

Рассмотрим выполнение этой последовательности операций в трёх различных режимах репликации метаданных. Режим репликации задаётся клиентом с помощью параметра SUCCESS_COPIES_NUM. Он определяет минимальное количество реплик индекса N, которые должны прислать свои ответы, прежде чем клиенту отправится агрегированный ответ от узла-обработчика запроса. Остальные реплики могут либо прислать ответ позже, либо совсем не ответить из-за сетевых проблем — это уже не важно для итогового ответа клиенту. Однако есть одно исключение — в запросах на чтение из индекса единичная ошибка отсутствия метаданных на реплике не всегда фатальна: клиент получит эту ошибку только в том случае, если её вернут сразу E реплик.

Допустимые значения SUCCESS_COPIES_NUM:

  1. ANY, N = 1, E = RF;

  2. QUORUM, N = E = RF/2 + 1;

  3. EVERY, N = RF, E = 1.

Соблюдение и нарушение read-your-writes согласованности при различных способах организации репликации метаданных.
Соблюдение и нарушение read-your-writes согласованности при различных способах организации репликации метаданных.

В двух первых вариантах репликации (SUCCESS_COPIES_NUM = EVERY, SUCCESS_COPIES_NUM = QUORUM) read-your-writes согласованность соблюдается, потому что множества реплик, синхронно обрабатывающих запросы на запись и на чтение, всегда пересекаются, и в их пересечении всегда находится реплика с последней записанной версией.

В последнем варианте (SUCCESS_COPIES_NUM = ANY) запрос на чтение может быть обработан узлом, на который последняя версия документа ещё не была реплицирована. Этот узел вернёт клиенту устаревшие метаданные, а read-your-write согласованность будет нарушена. Ограничение, согласно которому каждая операция клиента должна выполняться над множеством реплик, содержащих историю предыдущих операций клиента, известно как sticky availability. И согласованность в конечном счёте, и read-your-writes согласованность являются sticky available моделями. Применение параметра SUCCESS_COPIES_NUM = ANY может нарушать sticky availability и, как следствие, обе упомянутые модели согласованности.

Счётчик копий версии документа

Каждая версия документа в DOS имеет свой собственный счётчик копий. Благодаря ему работает механизм верхнеуровневой дедупликации: при поступлении данных, совпадающих с данными, уже когда-то записанными в кластер, продвинутые клиенты с помощью метода IncrementCopies могут просто увеличивать количество копий у имеющихся версий документов вместо того, чтобы записывать новые. Этот приём экономит не только дисковое пространство и IO, но и сетевой трафик внутри дата-центра.

Значение счётчика важно и для сборщика мусора по индексу документов: он просматривает каждую версию каждого документа и удаляет версии, не имеющие копий, и версии с истекшим TTL. Чтобы сборщик мусора случайно не удалил нужные данные, он должен опираться на согласованное между репликами значение счётчика копий. Сборщик мусора захватывает эксклюзивную распределённую блокировку на документ и поочерёдно проверяет каждую версию документа. Если значение счётчика копий версии равно нулю либо истёк её TTL, версия документа удаляется. Точно такой же подход использует сборщик мусора по индексу сегментов, только вместо счётчиков копий проверяются счётчики ссылок на сегмент со стороны документов.

Сериализуемость операций над счётчиками копий версий одного документа. Клиент декрементирует счётчик копий версии документа (1). Спустя какое-то время DOS в фоновом режиме запускает сборщик мусора, который захватывает блокировки на документ на всех трёх репликах (2). Пока сборщик мусора работает с документом, от клиента приходит параллельный запрос на инкремент счётчика копий, но он не может захватить блокировку (3). Подсистема ретраев на стороне узла-обработчика запроса через некоторое время выполняет делает повторную попытку операции (4), блокировку удаётся захватить, но оказывается, что такой версии больше не существует (5) — её физически удалил cборщик мусора.
Сериализуемость операций над счётчиками копий версий одного документа. Клиент декрементирует счётчик копий версии документа (1). Спустя какое-то время DOS в фоновом режиме запускает сборщик мусора, который захватывает блокировки на документ на всех трёх репликах (2). Пока сборщик мусора работает с документом, от клиента приходит параллельный запрос на инкремент счётчика копий, но он не может захватить блокировку (3). Подсистема ретраев на стороне узла-обработчика запроса через некоторое время выполняет делает повторную попытку операции (4), блокировку удаётся захватить, но оказывается, что такой версии больше не существует (5) — её физически удалил cборщик мусора.

Благодаря эксклюзивным блокировкам удаётся достичь сериализуемости операций над счётчиками копий. Для того чтобы блокировка считалась захваченной, достаточно ответа простого большинства реплик индекса, поэтому операции инкремента и удаления разрешены со значением SUCCESS_COPIES_NUM не ниже QUORUM. Сборщик мусора работает только с EVERY, так как на него возложены некоторые дополнительные операции, для которых критично получить ответы всех реплик.

Управление компромиссами распределённых систем

Теорема PACELC констатирует, что в распределённых базах помимо компромисса между согласованностью (C) и доступностью (A) существует ещё один — между согласованностью (C) и временем отклика (L). Первый становится особенно актуален во время инфраструктурных проблем (P), второй — в условиях, когда всё работает (E). Многие современные базы данных стараются предоставить клиенту возможность управления данными компромиссами. DOS не является исключением: с помощью параметра SUCCESS_COPIES_NUM клиент задаёт целый комплекс параметров, в конечном итоге влияющих на результат и длительность обработки запроса. Сам DOS в своих внутренних процессах также опирается на SUCCESS_COPIES_NUM.

Может показаться, что запись и чтение данных с параметром SUCCESS_COPIES_NUM = ANY может привести к разнообразным проблемам. Однако ставка на низкое время отклика в ущерб согласованности вполне оправдана в случае, если данные иммутабельны или изменяются очень редко, либо допустима ситуация, когда данные не видны сразу же после записи. Сервисы бэкенда Mailion используют комбинированный подход: пишут данные с SUCCESS_COPIES_NUM = QUORUM, а читают с SUCCESS_COPIES_NUM = ANY. Это делает запись более надёжной, а чтение более быстрым. Учитывая то, что в Mailion чтение преобладает над записью в соотношении 5:1, такая настройка ещё и оптимизирует чтение.

Восстановление согласованности реплик индекса

Выше мы показали, что в некоторых ситуациях DOS обрабатывает модифицирующие запросы в частично асинхронном режиме. Клиент может получить успешный ответ на запрос даже если большинство реплик вышло из строя. Разумеется, это приводит к нарушению согласованности реплик индексов. Однако метаданные спроектированы таким образом, что практически всегда можно слить записи разошедшихся реплик в единый результат.

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

  1. У версий документов может быть установлен абсолютный или относительный TTL. Абсолютный TTL задаётся в момент создания версии документа и не изменяется. Относительный TTL объекта реализуется в виде простого поля int64, в котором хранится последнее время доступа к объекту в UTC. Для разрешения конфликтов относительного TTL используется простая стратегия LWW.

  2. Счётчик копий версии документа имплементирован CRDT-типом PN-Counter. Операция слияния для него определена на уровне типа.

  3. На версию документа может быть установлена пометка BrokenMark, свидетельствующая о потере данных. С помощью этой пометки DOS сигнализирует клиенту о том, что он может записать новую версию с теми же данными и неявно, за счёт блочной дедупликации, восстановить старую версию. При слиянии экземпляров записей действует простое правило: если хоть у одного экземпляра BrokenMark установлена, то она будет установлена и у результата слияния.

Слияние записей в индексе документов.
Слияние записей в индексе документов.

Индекс сегментов устроен значительно сложнее. Счётчики ссылок популярных сегментов могут сильно разрастаться. По достижении предельного размера они разбиваются на шарды, хранящиеся по отдельности в дереве, узлами и листьями которого являются отдельные записи индекса. Подробное описание процесса разрешения конфликтов в иерархических сегментах выходит за рамки данной статьи, но в его основе лежат всё те же CRDT и подход copy-on-write.

В DOS предусмотрено несколько механизмов восстановления согласованности реплик. Основная роль отводится тяжеловесному фоновому процессу, который итерируется по всем ключам индекса каждой из реплик, читает локальное значение и значения в удалённых репликах, и при обнаружении расхождений объединяет и перезаписывает записи во всех репликах. В последнее время постепенно внедряется и второй подход, подразумевающий восстановление согласованности метаданных в момент обращения к ним. Например, при чтении данных сейчас исправляются некоторые типы расхождений в индексе сегментов.

Процессы синхронизации реплик индексов в DOS обязательно продолжат своё развитие. Мы с большим энтузиазмом смотрим в сторону деревьев Меркла и асинхронных протоколов противодействия энтропии.

Хранение данных в кластере

Данных много, данные непрерывно поступают и очень редко удаляются. Рост кластера DOS, добавление к нему новых серверов и дисков в первую очередь обусловлен ростом слоя хранения данных. Пользуясь терминологией из предыдущей статьи, этот слой следует рассматривать как систему неограниченного объёма.

Конечно, отказоустойчивость такого объёма данных возможно обеспечить путём репликации и достижения двухкратной или даже трёхкратной избыточности, однако системы, построенные на подобном принципе, имеют более низкую экономическую эффективность. На помощь приходит кодирование Рида-Соломона. Оно позволяет добиться достаточного уровня отказоустойчивости при меньшей избыточности.

В DOS версии документов разделяются на чанки, а чанки делятся на сегменты. Из d сегментов данных с помощью кодирования Рида-Соломона генерируются p избыточных сегментов. Сегменты, принадлежащие одному чанку, сохраняются в единственном экземпляре на независимых узлах системы хранения так, чтобы даже в случае потери любых p узлов была возможность восстановить и вернуть клиенту запрошенный объект.

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

Иллюстрация работы балансировщика бэкендов. В кластере 5 узлов, каждый из которых содержит по 2 бэкенда, d + p = 6. Поступившая версия документа состоит из 6 сегментов, из которых 3 ранее уже встречались в кластере. Новые сегменты сохраняются на бэкендах с наибольшим количеством свободного дискового пространства. Для одного из сегментов, ранее существовавших в кластере, придётся сделать дополнительную копию, чтобы соблюсти гарантии отказоустойчивого хранения.
Иллюстрация работы балансировщика бэкендов. В кластере 5 узлов, каждый из которых содержит по 2 бэкенда, d + p = 6. Поступившая версия документа состоит из 6 сегментов, из которых 3 ранее уже встречались в кластере. Новые сегменты сохраняются на бэкендах с наибольшим количеством свободного дискового пространства. Для одного из сегментов, ранее существовавших в кластере, придётся сделать дополнительную копию, чтобы соблюсти гарантии отказоустойчивого хранения.

Дедупликация в сочетании с требованием соблюдения гарантий хранения добавляет новые грани проблеме размещения данных в кластере. При записи объекта строится специальная карта размещения сегментов. Вполне возможно, что некоторые сегменты уже были ранее сохранены на различных бэкендах кластера. Если фактическое расположение таких сегментов позволяет сохранить новый чанк с гарантиями хранения, то в бэкенды дописываются лишь новые сегменты. В противном случае некоторые из старых сегментов приходится сохранять повторно. В DOS отказоустойчивость приоритетнее дедупликации, поэтому наиболее популярные сегменты в кластере могут встречаться в нескольких экземплярах.

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

В настоящее время мы активно работаем над оптимизацией алгоритмов размещения данных.

Топология кластера

В завершение коснёмся общих принципов организации кластера. Каждый узел кластера DOS реализуется в виде одиночного процесса операционной системы и включает в себя три GRPC-сервиса, работающих на независимых эндпойнтах: публичный сервис, обслуживающий запросы клиентов к API, и служебные сервисы роутинга и репликации.

Подсистема роутинга

Независимые узлы DOS объединяются в кластер путём обмена хартбит-сообщениями по Gossip-протоколу роутинга. На старте узлы подключаются друг к другу, каждый раз формируя случайный неориентированный граф. Количество рёбер в графе невелико: для стабильного функционирования кластера из N узлов достаточно 2N сетевых соединений по протоколу роутинга.

Каждый узел с определённой периодичностью рассылает хартбит-сообщения соседним узлам, с которыми у него есть соединения. Каждый сосед пересылает его сообщение тем из своих соседей, которые это сообщение еще не принимали. В состав сообщения включается актуальная статистика узла и локальное значение векторных часов. Так информация о состоянии члена кластера быстро распространяется по всему кластеру.

Входящая в состав каждого узла подсистема роутинга аккумулирует информацию о составе и статистике кластера и поставляет её внутренним потребителям. Когда к кластеру добавляется новый узел, роутинг отправляет команду на перестроение кольца диапазонов, использующегося для фрагментации индексов. А оперативная статистика кластера, агрегируемая роутингом, используется балансировщиком бэкендов.

Также в подсистеме роутинга реализован простой детектор отказов. Его имплементация очень близка к алгоритму идеального детектора невизантийских отказов в синхронных сетях, представленному в монографии Кристиана Качина, Рашида Гуерру и Луиса Родригеса. Когда какой-то узел P в течение определённого времени не получает хартбит-сообщений от узла Q, то P начинает считать узел Q временно потерянным. Пока что P не исключает Q из своего кольца диапазонов индексов, но информирует балансировщик бэкендов о том, что новые сегменты сохранять на Q нельзя. После этого, если в течение длительного времени Q так и не присылает хартбиты, P считает Q полностью потерянным и удаляет всю информацию о Q из своих подсистем.

Подсистема репликации

Узнав друг о друге с помощью подсистемы роутинга, узлы кластера организуют полносвязную сеть соединений по протоколу репликации. O(N^2) соединений в кластере — это много, однако в ходе обработки запросов узлы обмениваются огромным количеством информации, поэтому мы сочли наличие прямой связи между каждой парой узлов гарантией низкого времени отклика.

Сам протокол близок к классическому варианту 2PC с одним значительным отличием – отсутствием персистентного журнала транзакций. На каждом из узлов кластера есть локальные ресурсы (данные, метаданные) и механизм управления параллелизмом 2PL, синхронизирующий доступ к этим ресурсам с помощью блокировок. По протоколу репликации узел-обработчик запроса получает доступ к блокировкам и ресурсам удаленного члена кластера и организует распределённую транзакцию поверх нескольких членов кластера, участвующих в обработке данного запроса.

При работе по протоколу репликации с индексами помимо обычных операций (запись, чтение и удаление) для внутренней бизнес-логики DOS доступна операция слияния (merge). Она поддерживается на уровне RocksDB, и именно благодаря ей реализована неблокирующая запись в DOS. Запись объекта выглядит не как read-modify-write операция, а просто как добавление в документ небольшого "приращения" (новой версии) без его предварительного вычитывания. Точно так же добавляются новые ссылки в индекс сегментов.

Общая топология кластера и схема размещения данных и метаданных (пример). В кластере 7 узлов, каждый из которых содержит по 2 HDD для размещения бэкендов и по 1 SSD для размещения индексов, фактор репликации – 3, d + p = 2 + 1. Запись  версии документа средних размеров потребует сохранить в кластере 3 экземпляра записи индекса документов, 9 экземпляров записей индекса сегментов, а также 3 тела сегмента. Размещение записей индекса определяется кольцом диапазонов, размещение тел сегментов – балансировщиком по бэкендам.
Общая топология кластера и схема размещения данных и метаданных (пример). В кластере 7 узлов, каждый из которых содержит по 2 HDD для размещения бэкендов и по 1 SSD для размещения индексов, фактор репликации – 3, d + p = 2 + 1. Запись версии документа средних размеров потребует сохранить в кластере 3 экземпляра записи индекса документов, 9 экземпляров записей индекса сегментов, а также 3 тела сегмента. Размещение записей индекса определяется кольцом диапазонов, размещение тел сегментов – балансировщиком по бэкендам.

Заключение

В статье мы рассмотрели основные принципы построения кластера DOS и выяснили, что хранилище использует разные механизмы масштабирования и обеспечения отказоустойчивости для слоёв данных и метаданных.

Слой хранения данных в DOS постоянно растёт, при этом сами данные иммутабельны и хранятся в кластере в единственном экземпляре, но с гарантиями возможности восстановления даже в случае отказа нескольких узлов кластера. Клиент имеет возможность выбирать желаемый уровень отказоустойчивости и экономической эффективности для всей инсталляции, управляя параметрами кодирования Рида-Соломона.

Слой хранения метаданных в DOS растёт гораздо медленнее и организован в DHT с помощью консистентного хеширования. Отказоустойчивость метаданных обеспечивается репликацией. Устанавливая количество синхронно отвечающих реплик индекса, клиент DOS может выбирать модель согласованности метаданных и управлять компромиссами между согласованностью и доступностью, согласованностью и временем отклика.

Узлы кластера собираются в одноранговую сеть и поддерживают между собой связи по протоколам роутинга и репликации. Благодаря неблокирующей записи в индексы DOS хорошо переносит ситуацию с параллельным сохранением одних и тех же данных, что нередко случается в почтовых системах.

Формат статьи не позволил в деталях рассказать про организацию распределённых транзакций и блокировок, а также про механизм разрешения конфликтов индекса. Мы обязательно продолжим освещать эти темы в дальнейших публикациях. Если вы увлечены распределёнными системами и базами данных, приходите к нам работать!

Теги:
Хабы:
Всего голосов 14: ↑14 и ↓0+14
Комментарии3

Публикации

Информация

Сайт
myoffice.ru
Дата регистрации
Дата основания
2013
Численность
1 001–5 000 человек
Местоположение
Россия
Представитель
МойОфис

Истории