LDAP-каталог на BadgerDB — опыт Avanpost

LDAP — это набор правил для обращений к службе каталогов, который появился в качестве легковесной замены решениями для работы со стандартом X.500. По словам одного из соавторов — инженера Колина Роббинса — история протокола берет начало в 1988 году. На тот момент специалист занимался разработкой собственного агента для каталога X.500 Quipu — DISH. Идея заключалась в том, чтобы контролировать каталог из оболочки Unix. Для этих целей Колин решил использовать именованные каналы и реализовал простой текстовый протокол.

Свою работу Колин направил Маршаллу Роузу, чтобы сделать код частью компонента Quipu в среде ISO Development Environment (ISODE). Однако Роузу не понравилась идея именованных каналов; он решил перестроить протокол для работы поверх TCP/IP. Результатом совместной работы двух инженеров стала служба ассистента каталога DASED. Но что интересно, параллельно с ними программист Тим Хоус реализовал собственный протокол для доступа к каталогам X.500, который назвал DIXIE.

DASED и DIXIE были направлены для стандартизации в IETF, где их объединили под одним названием — LDAP. А Тим Хоус написал технический отчет, описывающий особенности реализации. Третья и последняя на сегодняшний день версия LDAP была принята в качестве стандарта в конце девяностых. С тех пор протокол стал важной составляющий современной ИТ-инфраструктуры.

На сегодняшний день существует множество реализаций LDAP, в том числе открытые — например, OpenLDAP. И выстраивая собственную службу каталогов Avanpost DS, мы вполне могли обратиться к какому-нибудь существующему решению. Однако не стали использовать open source компоненты, чтобы исключить риски появления вредоносных закладок.

Но если мы не заимствуем код, это не значит, что мы не можем позаимствовать некоторые интересные идеи. Так, при построении Avanpost DS мы ориентировались на архитектуру ApacheDS — открытой реализации LDAP-сервера на Java — и реализовали многослойную структуру приложения: Network → DirectoryService → Interceptors → Partitions.

Такая структура позволила разделить «зоны ответственности» и упростить расширение функциональности системы. Так, при добавлении нового протокола приходится менять только слой Network, при добавлении бизнес-логики — слой Interceptors, а при использовании новой БД — слой Partitions.

LDAP-каталог в Avanpost DS выстроен поверх BadgerDB. Здесь сразу отвечу на два вопроса:

• Почему не реляционная СУБД? LDAP-каталог должен эффективно работать с данными, представленными как деревья, особенно по части поиска в подобных структурах. А отражение иерархий в реляционных базах связано с трудностями — они попросту не заточены под работу с деревьями. Да, приемлемой работы можно добиться с помощью комбинаций индексов (например, B-tree, GIST и JSONB/GIN), но тогда встает идеологическая проблема: LDAP-каталоги являются более низкоуровневым решением, чем реляционные БД. Можно сказать, что такая архитектура не будет оптимальной.
• Почему именно BadgerDB? Мы рассматривали несколько хранилищ. Остановились на BadgerDB, потому что эта СУБД использует LSM-деревья — структуры данных для эффективной записи и поиска пар типа «ключ — значение». При этом ключи хранятся в дереве, а значения — в отдельном журнале. Такой подход позволяет снизить нагрузку на систему. Особенно в контексте работы с SSD и большим количеством операций параллельного чтения.

В то же время BadgerDB устойчива к сбоям и управляет сборкой мусора. Так, мы можем эффективно работать с журналом значений без ухудшения в производительности системы. Кроме того, согласно некоторым бенчмаркам, BadgerDB от 1,7 до 22,3 раз быстрее, чем альтернативы — LMDB и BoltDB — на задачах произвольной записи.

Для построения LDAP-каталога нам нужно было не только представить данные в виде иерархии, но и реализовать поисковый механизм для оперативного извлечения данных из любой части дерева с учетом фильтра.

В основу поискового движка легли две идеи: побайтовая лексикографическая сортировка и индексирование.

Это — основа иерархической структуры LDAP-каталога. BadgerDB основан на LSM-деревьях, которые периодически пишут данные в сортированные таблицы строк (Sorted String Table). И СУБД извлекает данные с помощью итераторов, которые имеют доступ к этим таблицам.

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

Перед нами стояла задача побора ключей таким образом, чтобы они отражали иерархическую структуру. Поэтому в качестве ключей мы использовали обратные уникальные имена записей в каталоге (Distinguished Name). В записи LDAP эти имена представляют собой путь к объектам в иерархии.

dc=example, dc=com
dc=com, dc=example, ou=Users
dc=com, dc=example, ou=Users, cn=ben.gunn
dc=com, dc=example, ou=Users, cn=john.silver

Так, при поиске с параметрами ou=Users, dc=example, dc=com мы бы никак не могли бы сканировать записи из подкаталога ou=Computers, dc=example, dc=com.

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

Под индексированием мы понимаем генерацию дополнительных ключей, которые позволяют по заданному значению параметра найти целевую запись.
Например, для индексирования записи с ключом cn=john.silver, ou=Users, dc=example, dc=com, у которой email=john.silver@piratecrew.com
можно добавить индексную запись вида:
email=john.silver@piratecrew.com; dc=com, dc=example, ou=Users, cn=john.silver

Так, при поиске записей по фильтру, содержащему индексированный атрибут, появляется возможность сначала с помощью итератора проверить индексные записи, которые начинаются с ключа email=john.silver, и по второй части этого ключа извлечь ключ целевой записи (а затем и саму запись).

В итоге при добавлении записи в каталог происходит следующее:

• Запись проверяется по схеме, сопоставляются разрешенные атрибуты для указанных классов, проверяются классы и синтаксис. Непосредственно схема хранится в памяти.
• Формируется список индексируемых атрибутов. Чем реже встречается атрибут, тем выгоднее его индексировать. Если запись содержит атрибут, который нужно индексировать, то генерируются дополнительные индексные записи.
• Сама запись сериализуется и добавляется в каталог, ее ключ — обратное уникальное имя. При поиске записи учитывается ее положение в иерархической структуре каталога, а также индексные записи ее атрибутов, в зависимости от поискового фильтра.

Avanpost — российский вендор-новатор в области идентификационных данных. Продукты Avanpost разработаны для использования в высоконагруженных средах с применением технологий распределенных вычислений, кластеризации, балансировки нагрузки, автоматического масштабирования, шардинга и т. д. Архитектура продуктов предполагает использование в отказоустойчивых геораспределенных инфраструктурах; компания реализует проекты, где продукты включены в Mission critical и Business critical контуры. Разработка ведется с помощью двух современных технологических стеков: PostgreSQL/.Net Core/EF/Akka.Net/Angular — для продуктов со сложной бизнес-логикой; GoLang/BadgerDB/GRPC/Vue.js — для высокопроизводительных сервисов.