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

Пара слов о LDAP

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 была принята в качестве стандарта в конце девяностых. С тех пор протокол стал важной составляющий современной ИТ-инфраструктуры.

Руководитель отдела технической экспертизы компании Avanpost Максим Тарасов
Фото предоставлено компанией Avanpost

Реализация LDAP в Avanpost DS

На сегодняшний день существует множество реализаций 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 на BadgerDB

Для построения 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, и по второй части этого ключа извлечь ключ целевой записи (а затем и саму запись).

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

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

Что дальше

Мы успешно использовали BadgerDB для построения иерархической структуры данных каталога LDAP и поискового механизма. Но мы планируем продолжить работу над своим поисковым движком.

Автор: руководитель отдела технической экспертизы компании Avanpost Максим Тарасов