И снова здравствуйте! Многие знают, что тема создания домена в Linux-инфраструктурах, подобного MS Active Directory, – одна из наиболее сложных в текущей стратегии изменения инфраструктур крупных компаний. Компания Avanpost начала разработку своей службы каталогов задолго до того, как это стало мейнстримом, и первичной нашей целью было создание службы для масштабных Linux-инфраструктур, которая позволила бы централизованно управлять правами администраторов и технологических учетных записей на серверах. Время внесло коррективы в наши планы разработки и позиционирование продукта, но основные архитектурные идеи сохранились с первого концепта. Собственно, ими мы и хотим начать делиться, учитывая множество вопросов, поступающих от действующих и потенциальных клиентов, партнеров и просто интересующихся.

Один из краеугольных камней и первый вопрос к нашему продукту – использование BadgerDB в качестве бэкенда хранения данных каталога. Сегодня один из бэкенд разработчиков Avanpost DS расскажет, как мы «приземлили» LDAP-каталог на KV-хранилище.

Требования к базе данных для LDAP-каталога

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

LDAP (Lightweight Directory Access Protocol) — это протокол для поиска и управления данными в каталогах. Каталоги в этом контексте представляют собой специализированные базы данных, содержащие информацию о различных объектах, таких как пользователи, устройства, группы и другие элементы сети [ 1 ]. LDAP применяют при централизованном управлении данными, аутентификации пользователей (например, для входа в системы или приложения), управлении доступом (контроль прав пользователей), хранении контактной информации и интеграции с различными сервисами для упрощения административных задач. LDAP обеспечивает эффективный и безопасный доступ к этой информации.

В LDAP-каталоге данные организованы в иерархическом (древоподобном) виде, что значительно отличается от плоской структуры, используемой в традиционных реляционных базах данных. Это означает, что данные в LDAP хранятся в виде дерева с узлами, и каждый узел может содержать другие узлы (или элементы). Такая организация данных предоставляет удобный способ для их поиска, управления и категоризации.

LDAP-каталоги используются для хранения информации, которая обновляется сравнительно нечасто, но к которой осуществляется постоянный доступ. В таких системах операции чтения происходят значительно чаще, чем записи, — иногда в 1000-10000 раз. Это связано с тем, что информация в каталоге обычно используется для быстрого поиска и идентификации данных, что требует регулярного обращения, но при этом сами данные меняются редко [ 2 ].

Из вышеизложенного можно выделить ключевые требования к базе данных, которая будет использоваться для реализации LDAP-каталога:

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

2. Высокая производительность при операциях чтения.  

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

3. Поддержка эффективных операций записи с добавлением, удалением и изменением данных. 

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

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

Помимо понятных технических требований, у нас также были продуктовые, относящиеся, в первую очередь, к способам поставки и развертывания продукта в on-premise инфраструктурах заказчиков:

1. Отсутствие дополнительных требований к окружению.

2. Отсутствие дополнительных требований к сетевому взаимодействию.

3. Управляемая репликация: мы заранее планировали реализовать ее самостоятельно, понимая что механизмы большинства СУБД не удовлетворят требованиям к синхронизации контроллеров домена.

4. Лицензионная чистота: мы не нарушали и не нарушаем международное авторское право, отчасти по принципиальным соображениям и с целью сохранения возможности продажи на западных рынках.

Можно ли использовать привычные реляционные базы данных в качестве основной базы данных для LDAP-каталога?

Теоретически это возможно, и даже на практике существуют решения, такие как проект LDAP-PG [3] . Однако, с учетом некоторых аспектов, использование реляционных баз данных для LDAP-каталогов может быть не оптимальным. Рассмотрим два ключевых момента:

1. Структура данных. Как мы уже обсуждали, LDAP использует иерархическую модель для организации данных, в то время как реляционные базы данных используют таблицы. Отражение иерархической структуры в реляционных базах может привести к определенным трудностям, так как они не предназначены для эффективной работы с данными, организованными в виде деревьев.
    
2. Идеологический аспект. Даже если с помощью различных комбинаций индексов (например, B-tree + GIST + JSONB/GIN, как в упомянутом проекте) удается адаптировать реляционные базы под задачи LDAP, существует и другой момент. Большинство современных баз данных поддерживают LDAP-аутентификацию, что подтверждает, что LDAP каталоги представляют собой, во-первых, отдельную систему, а, во-вторых, более низкоуровневое решение, по сравнению с реляционными базами данных.
    

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

Графовые базы данных

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

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

BadgerDB – быстрое KV хранилище на основе LSM-tree 

LSM-деревья (Log-Structured Merge Trees) — это структуры данных, которые широко используются в хранилищах для эффективной записи и поиска пар ключ-значение. Они организуют данные в несколько уровней: записи сначала попадают в память, а затем сбрасываются на диск в виде SSTable (Sorted String Table). Главные преимущества LSM-деревьев заключаются в высокой скорости записи и эффективности при обработке больших объемов информации. Однако у этой технологии есть и недостатки: операции слияния (compaction), при которых данные с разных уровней объединяются, могут сильно нагружать систему. Также операции чтения могут быть медленными, так как данные могут быть разбросаны по нескольким уровням, что требует дополнительных затрат времени на их сканирование.

BadgerDB — это база данных, использующая LSM-деревья, но с улучшенным дизайном, который решает некоторые из этих проблем. Сами разработчики BadgerDB выделяют следующие идеи, которые выделяют их среди традиционных LSM-tree проектов:

1. Разделение ключей и значений — в отличие от обычных LSM-деревьев, где ключи и значения хранятся вместе, BadgerDB оставляет только ключи в LSM-дереве, а значения записывает в отдельный журнал. Это помогает снизить нагрузку на систему.
    
2. Параллельные операции случайного чтения, которые поддерживаются современными SSD-устройствами, что заметно ускоряет доступ к данным (оптимизирована под SSD).
    
3. Методы обеспечения устойчивости к сбоям и управление сборкой мусора, что позволяет удобнее работать с журналом значений, не ухудшая производительность системы. Подробнее о технологии можно прочитать в [4].
    
4. Оптимизация производительности: BadgerDB использует уникальный подход к удалению журналов LSM-дерева, что улучшает скорость работы, не жертвуя консистентностью данных.
    

Эти решения позволяют ускорить как операции чтения, так и записи по сравнению с другими хранилищами на основе LSM-деревьев, как указано в статье [5]. Кроме того, BadgerDB поддерживает конкурентные ACID транзакции (детали здесь [6]). Подробнее можно ознакомиться с их репозиторием на GitHub [7].
BadgerDB – современная, актуальная, высокопроизводительная, open-source база данных, написанная на go, которая основана на иерархических структурах данных. Все вышеперечисленное делает ее «хорошим кандидатом» для LDAP-каталога.

LDAP

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

Для наглядности давайте рассмотрим как могла бы выглядеть структура LDAP-каталога для романа Р.Л. Стивенсона «Остров Сокровищ».

dc=treasureisland,dc=com
|
|-- ou=Treasure Hunters
|   |
|   |-- cn=jim.hawkins
|   |   |-- objectClass=treasureHunter
|   |   |-- cn=jim.hawkins
|   |   |-- sn=hawkins
|   |   |-- description=Мальчик, нашедший карту сокровищ.
|   |   |-- email=jim.hawkins@treasureisland.com
|   |
|   |-- cn=doctor.livesey
|   |   |-- objectClass=treasureHunter
|   |   |-- cn=doctor.livesey
|   |   |-- sn=livesey
|   |   |-- description=Врач
|   |   |-- email=doctor.livesey@treasureisland.com
|   |
|   |-- cn=squire.trelawney
|   |   |-- objectClass=treasureHunter
|   |   |-- cn=squire.trelawney
|   |   |-- sn=trelawney
|   |   |-- description=Спонсор экспидиции.
|   |   |-- email=squire.trelawney@treasureisland.com
|   |
|   |-- cn=captain.smollett
|   |   |-- objectClass=treasureHunter
|   |   |-- cn=captain.smollett
|   |   |-- sn=smollett
|   |   |-- description=Капитан корабля "Испаньола"
|   |   |-- email=captain.smollett@treasureisland.com
|
|-- ou=Pirates
|   |
|   |-- cn=john.silver
|   |   |-- objectClass=treasureHunter, pirate
|   |   |-- cn=john.silver
|   |   |-- sn=silver
|   |   |-- description=Лидер пиратов, маскируется под повара.
|   |   |-- email=john.silver@piratecrew.com
|   |   |-- isTraitor=true
|   |
|   |-- cn=israel.hands
|   |   |-- objectClass=treasureHunter, pirate
|   |   |-- cn=israel.hands
|   |   |-- sn=hands
|   |   |-- description=Пират, притворяющийся обычным моряком на "Испаньоле".
|   |   |-- email=israel.hands@piratecrew.com
|   |   |-- isTraitor=true
|   |
|   |-- cn=ben.gunn
|   |   |-- objectClass=treasureHunter, pirate
|   |   |-- cn=ben.gunn
|   |   |-- sn=gunn
|   |   |-- description=Бывший пират, оставшийся на острове, помогает искать сокровища.
|   |   |-- email=ben.gunn@islandresidents.com
|   |   |-- isTraitor=false
|   |
|   |-- cn=bill.bones
|   |   |-- objectClass=treasureHunter, pirate
|   |   |-- cn=bill.bones
|   |   |-- sn=bones
|   |   |-- description=Старый пират, который передал Джиму карту сокровищ перед своей смертью.
|   |   |-- email=bill.bones@pirategrave.com
|   |   |-- isTraitor=false

Структура записи в LDAP:

Запись состоит из уникального имени и атрибутов записи.

1. DN (Distinguished Name) — уникальное имя записи в каталоге. Оно представляет собой путь к объекту в иерархической структуре, который идентифицирует запись. Например:

DN состоит из набора RDN (Relative Distinguished Name):
- cn=john.silver
- ou=Pirates
- dc=treasureisland,dc=com
   
2. Атрибуты — данные, которые описывают объект. Например:
- cn (common name) — общее имя.
- email — адрес электронной почты.
- description — описание.

Сама запись выглядит следующим образом:
    

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

Схема LDAP:

Схема в LDAP — это набор правил, которые определяют как должны быть устроены записи в каталоге, какие атрибуты могут быть использованы для описания объектов и какие типы данных могут быть присвоены этим атрибутам. Существуют как общепринятые схемы [8], которые зафиксированы в спецификации, так и кастомные: каждая компания может расширить схему своими классами и атрибутами. Если вас интересует более подробная информация о схемах LDAP, рекомендую обратиться к следующему источнику. [9] 
Схему для этого дерева можно обозначить так:
Класс treasureHunter содержит следующие атрибуты: cn, sn, description, email.
Класс pirate наследуется от класса treasureHunter и имеет одно дополнительное поле isTraitor (предал он экспедицию или нет).

 Поиск LDAP

Запрос поиска LDAP содержит много параметров, однако, если выделить наиболее значимые, их можно сократить до трех:

1. BaseDN

2. Область поиска

3. Фильтр

Base DN

Это узел дерева, с которого начинается поиск в LDAP. Это может быть корень дерева или определенный подраздел. Например, если вы ищете информацию о пользователях, baseDN может быть ou=Users, dc=example,dc=com.

Область поиска

1. Поиск только по текущему объекту (baseObject):      В этом случае мы знаем, какая запись нам нужна, и указываем ее в BaseDN. Например, нам нужен конкретный пользователь. Тогда мы укажем в области поиска "Только этот объект", а в BaseDN - точный DN записи    cn=john.silver,ou=Pirates,dc=treasureisland,dc=com.

2.  Поиск только по непосредственным дочерним элементам (singleLevel):      Если Base DN - это ou=Pirates,dc=treasureisland,dc=com, то поиск будет ограничен только записями, находящимися непосредственно в подразделе ou=Pirates.

3.  Поиск по всему дереву под указанным Base DN (wholeSubtree):      В случае BaseDN - dc=treasureisland,dc=com поиск будет выполнен по всем записям в каталоге и их подкаталогам (если такие имеются).

Фильтр

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

Примеры:

Если необходимо получить всех пиратов, которые предали экспедицию, поисковый запрос составляется следующим образом:

Если необходимо найти учетную запись по известному dn:

Если необходимо найти запись по атрибуту, но точное его положение в дереве нам неизвестно:

LDAP-каталог на основе BadgerDB

После того, как мы проанализировали методы хранения и поиска записей в LDAP, можем перейти к еще более любопытному вопросу: "Как именно мы можем использовать BadgerDB для LDAP-каталога?"  В отличие от документации PostgreSQL на 3000 страниц, вся документация BadgerDB компактно помещается на одной. [10] 
Если внимательно её изучить, можно выделить несколько ключевых инструментов, которые нам понадобятся для построения LDAP-каталога на основе BadgerDB:

1. Создание записи с заданным ключом 

2. Получение записи по заданному ключу

3. Перебор итератором ключей, которым соответствует заданный префикс. Важно, что итератор читает хранимые ключи из сохраненных таблиц и позволяет нам итерироваться по лексикографически отсортированным ключам. [11]

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

В основе поискового движка лежат две идеи: побайтовая лексикографическая сортировка (byte-wise lexicographical sorting) и индексирование.

Лексикографическая сортировка ключей

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

Посмотрим подробнее на итератор BadgerDB [12]. Итератор будет начинать искать записи с указанного ключа, а следующим возьмет самый короткий ключ, который будет больше исходного.

Это свойство отлично подходит для того, чтобы искать записи в поддереве (wholeSubtree). В поисковом запросе LDAP всегда участвует BaseDN — это исходная точка, с которой мы начинаем поиск записей. Если в качестве BaseDN выбран ou=Users,dc=example,dc=com, мы хотим получать именно элементы этого поддерева и не хотим обрабатывать элементы из поддерева ou=Computers,dc=example,dc=com. 

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

Одним из вариантов решения такой задачи может быть использование обратного DN в качестве ключа записи (итератор умеет читать таблицу и в обратном порядке, поэтому можно выбрать прямой DN, но обратный порядок чтения).

Обратные DN:

В нашем случае порядок ключей был бы следующим:

Поэтому, выбрав BaseDN ou=Users,dc=example,dc=com , благодаря отсортированным таблицам мы никак не могли бы сканировать записи из подкаталога ou=Computers,dc=example,dc=com. Используя таким образом иерархические структуры данных, лежащие в основе BadgerDB, можно эффективно учитывать начальную точку поискового запроса и исключать из поиска записи, которые не соответствуют этой точке.

Индексирование

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

Значение записи оставляем пустым, так как необходимое значение ключа целевой записи мы получаем из самого ключа индексной записи.
При поиске записей по фильтру, содержащему индексированный атрибут, мы можем сначала с помощью итератора проверить индексные записи, которые начинаются с ключа "email=john.silver@piratecrew.com", а по второй части извлечь ключ целевой записи и далее — извлечь саму целевую запись.

Итак, соберем всё вместе.

При добавлении записи в каталог происходит следующее:
1) Запись проверяется по схеме, сопоставляются разрешенные атрибуты для указанных в записи классов, проверяются сами классы и синтаксис атрибутов. Сама схема хранится в памяти. Так мы понимаем, что добавляемые данные валидны.
2) Существует список индексируемых атрибутов, который составляется на основе статистики и здравого смысла. Чем лучше индекс может сузить поиск, основываясь на значении одного атрибута, тем лучше (выше селективность индексирования). Если запись содержит атрибут, который нужно индексировать, создаются дополнительные индексные записи.
3) Сама запись сериализуется и добавляется в каталог, ее ключ — обратный DN.

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

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

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