MDB: отображаемая в памяти база данных и механизм манипуляции данными для OpenLDAP

Выступление Howard Chu (Symas Corp., OpenLDAP Project) на 3-й Международной конференции по LDAP (LDAPCon 2011) в октябре 2011 года. Оригинал статьи (PDF) на сайте проекта OpenLDAP, там же можно найти слайды к этому выступлению (на английском языке).

Тезисы

В этом документе представлена MDB (Memory-Mapped Database, отображаемая в памяти база данных), библиотека оптимизированной на чтение базы данных и механизм манипуляции данными slapd, разработанный для OpenLDAP. В этом документе мы обсудим традиционные первичные механизмы манипуляции данными OpenLDAP, а также некоторые другие альтернативы, которые мы испытывали перед тем, как приступить к реализации MDB. Также будут представлены первые результаты тестирования реализации MDB. Разработка ещё ведётся, но, по существу, уже завершена, и MDB будет интегрирована в общедоступные выпуски OpenLDAP в ближайшем будущем.

1. Введение

Хотя OpenLDAP уже предоставляет надёжный высокопроизводительный механизм, работающий с транзакционной базой данных (использующий Oracle BerkeleyDB "BDB"^[1]), для достижения хороших результатов этот механизм требует тщательной настройки, и аспекты настройки могут быть достаточно сложны. Данные, прежде чем их можно будет использовать, проходят через три отдельных уровня кэширования, каждый из которых оказывает существенное влияние. Балансировка этих трёх уровней относительно друг друга может превратиться в сложный цирковой номер. Кроме того, существует два уровня блокировок, требуемых для безопасного манипулирования этими кэшами, и эти блокировки серьёзно ограничивают масштабируемость базы данных в мультипроцессорных системах.

Вместо того, чтобы продолжать попытки адаптации стороннего программного обеспечения баз данных в OpenLDAP, специально для использования в OpenLDAP была написана библиотека MDB. Эта библиотека является полностью транзакционной и реализует B+ деревья^[2] с управлением конкурентным доступом с помощью многоверсионности (Multi-Version Concurrency Control)^[3]. База данных целиком отображается в виртуальную память и извлечение всех данных выполняется посредством прямого доступа к отображению в памяти, а не через промежуточные буферы и копии.

2. Предпосылки

Перед тем, как описывать все те положительные моменты, которые повлекла за собой разработка MDB, предлагаем обзор существующих механизмов манипуляции данными, основанных на BDB (back-bdb и back-hdb).

У LDAP и BDB богатая совместная история; Netscape заказала разработку BDB версии 2.0 специально для использования в своём LDAP-сервере^[4]. Впервые OpenLDAP Project использовал API BDB в выпуске OpenLDAP 2.1 в июне 2002. Поскольку BDB поддерживает свой собственный внутренний кэш, была надежда, что механизм back-bdb может быть развёрнут без какого-либо кэширования на уровне механизма, но результаты уже самых первых тестов показали, что извлечение записей непосредственно из базы данных при каждом запросе оказалось слишком медленным. Несмотря на радикальные улучшения выборки записей и скорости декодирования^[5], было принято решение ввести кэш записей для механизма манипуляции данными. Отсюда берут своё начало проблемы управления кэшем.

Суть этих проблем:

• Несколько кэшей, каждый из которых должен быть тщательно настроен. Поверх кэша BDB располагаются кэши записей, DN и индексирования атрибутов механизма манипуляции данными. Каждый из них расходует память, зачастую избыточно, поскольку одни и те же данные могут присутствовать в трёх местах: в кэше файловой системы, кэше BDB и кэшах механизма манипуляции данными. Настройка их взаимодействия становится утомительным процессом, поскольку у каждого уровня кэша свои собственные, отличные от других размеры и характеристики быстродействия, и трудно добиться баланса, оптимального для всех вариантов использования.
• Кэши с очень сложными зависимостями блокировок. Для достижения высокого быстродействия большинство кэшей механизма манипуляции данными защищаются с помощью простых семафоров (мьютексов). Однако, при взаимодействии с API BDB эти мьютексы должны быть отброшены и заменены на (гораздо более медленные) блокировки базы данных. В противном случае может произойти взаимная блокировка (deadlock), которую не способен определить детектор взаимных блокировок BDB. Во время штатной работы механизма манипуляции данными подобные взаимные блокировки случаются очень часто.
• Кэши с патологическим поведением, если их размеры меньше, чем размер базы данных целиком. Если размер кэша был достаточно мал, так что значительное количество запросов удовлетворялись не за счёт этого кэша, наблюдалась экстремальная фрагментация кучи^[6], поскольку кэш избавлялся от существующих записей, чтобы освободить место для новых. Фрагментация приводила к тому, что размер процесса slapd быстро увеличивался, сводя на нет то, ради чего уменьшался размер кэша. Наихудшая ситуация была с распределителем памяти из состава библиотек GNU^[7], её можно было улучшить с помощью альтернативных распределителей Hoard^[8] или Google tcmalloc^[9]. С другой стороны, в slapd были внесены дополнительные изменения, чтобы уменьшить количество вызовов malloc() и free() и отсрочить наступление этой ситуации с фрагментацией^[10].
• Кэши с очень низкой эффективностью. При поступлении нескольких запросов, результаты которых превышали размер кэша записей, эффективность этого кэша падала до нуля, поскольку записи постоянно освобождались, прежде чем у них появлялся шанс быть повторно использованными^[11]. Для борьбы с этой проблемой было потрачено много усилий в изучении более продвинутых алгоритмов замены кэша^[12][13].

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

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

3. Решения

Проблемы с back-bdb и back-hdb можно обобщить в две основные категории: управление кэшем и управление блокировками. Подход к решению этих проблем в back-mdb прост — не делать кэширование и не делать блокировок. Другие вопросы административных издержек обрабатываются как побочный эффект основных решений.

3.1 Устранение кэширования

Одна из фундаментальных концепций подхода MDB известна как "одноуровневое хранилище" ("Single-Level Store")^[14]. Основная идея — интерпретировать всю память компьютера как единое адресное пространство. Страницы хранилища могут находиться в основной системе хранения (RAM) или во вторичной системе хранения (на диске), но фактическое расположение не имеет значения для приложения. Если страница, на которую происходит ссылка, в текущий момент находится в основной системе хранения, приложение может использовать её немедленно, в противном случае возникает ошибка страницы и операционная система переносит необходимую страницу в первичную систему хранения. Эта концепция была впервые представлена в 1964 году в операционной системе Multics^[15], но была по сути заморожена в начале 1990-х, поскольку объёмы данных превысили ёмкость 32-разрядного адресного пространства (последнее упоминание о ней мы видели в операционной системе Apollo DOMAIN^[16], хотя ею занимались и многие другие Multics-подобные системы). Сегодня, благодаря применению 64-разрядных процессоров, этой концепции вновь можно найти хорошее применение (если принять лимит виртуального адресного пространства за 63 бита, то верхняя граница размера базы данных будет 8 экзабайт; доступные в настоящее время процессоры реализуют адресное пространство только в 48 бит, ограничивая нас, таким образом, 47-ю битами или 128-ю терабайтами).

Другое требование операционной системы, обеспечение которого необходимо для жизнеспособности данного подхода — это унифицированный буферный кэш (Unified Buffer Cache). Хотя большинство основанных на стандартах POSIX операционных систем уже многие годы поддерживает системный вызов mmap(), первоначальные их реализации поддерживали память, управляемую подсистемой VM, отдельно от памяти, управляемой кэшем файловой системы. Это было не только расточительно (та же ситуация — хранимые данные кэшируются в двух местах одновременно), но также приводило к проблемам согласованности — данные, модифицированные в отображённой памяти, не были видны посредством вызовов read() файловой системы, а данные, модифицированные через вызовы write() файловой системы, не были видны в отображённой памяти. Большинство современных операционных систем в настоящее время имеют унифицированную систему подкачки страниц для файловой системы и VM, так что в большинстве конфигураций проблем возникать не должно ^[17][18][19].

Библиотека MDB разработана для доступа ко всей базе данных через единое, доступное только для чтения отображение в памяти. То, что отображение находится в режиме только для чтения, предотвращает порчу базы данных в результате случайных записей со стороны ошибочного программного кода. Обновления базы данных выполняются с помощью стандартных вызовов write(). Обновление через отображение в любом случае было бы трудной задачей, поскольку невозможно увеличить размер файла через ссылки отображения; через отображение могут быть проведены обновления только существующих страниц. Для упрощения процесса все обновления производятся с помощью вызова write(), и не важно, увеличивается при этом размер файла или нет. Такой подход к обновлению требует, чтобы представления файловой системы и VM поддерживались согласованными, то есть требуется, чтобы операционная система использовала унифицированный буферный кэш.

Подход с отображением в памяти приводит к полному использованию кэша файловой системы операционной системы и устраняет любое кэширование на уровне базы данных. Также и механизм манипуляции данными back-mdb сам по себе не выполняет кэширования; он использует информацию из базы данных напрямую. Использование отображённых в памяти данных исключает два уровня кэширования, относящиеся к back-hdb, а также исключает избыточные операции memcpy() между этими кэшами. Оно также устраняет все вопросы настройки и оптимизации кэша, таким образом облегчая администраторам задачу развёртывания.

Конечно, при исключении кэша можно ожидать значительное падение производительности. Гораздо быстрее в ответ на поисковый запрос скопировать содержимое закэшированной, полностью декодированной записи, чем считывать запись с диска и декодировать при каждом запросе. Первые результаты тестирования back-mdb показали, что это соответствует действительности, однако дальнейшая оптимизация механизма позволила по большей части устранить данное падение производительности.

3.2 Устранение блокировок

Другая фундаментальная концепция MDB — использование управления конкурентным доступом с помощью многоверсионности (Multi-Version Concurrency Control, MVCC). Основная идея — то, что обновления данных никогда не перезаписывают существующие данные; вместо этого обновления производят запись в новые страницы, таким образом создаётся новая версия базы данных. Те, кто выполняет чтение базы данных, когда бы они не производили доступ, всегда видят снимок базы данных в том состоянии, в котором она находилась перед началом транзакции на чтение, таким образом, они полностью изолированы от тех, кто производит запись. Из-за такой изоляции доступы на чтение не требуют блокировок, представление базы данных для них всегда самосогласовано.

BDB поддерживала MVCC начиная с версии 4.5.20, но, из-за наличия слоя кэширования механизмов back-bdb/hdb, не было никаких преимуществ от его использования. Получить какую-либо выгоду от использования MVCC можно было лишь при одновременном устранении кэширования на уровне механизма манипуляции данными, но без слоя кэширования производительность back-bdb/hdb была бы слишком мала, поскольку поиск данных в BDB всё ещё был слишком медленным.

Основной недостаток основанных на MVCC систем — то, что из-за постоянной записи новых данных в новые дисковые страницы файлы базы данных имеют тенденцию неограниченно разрастаться. Чтобы как-то ограничить использование дискового пространства, требуется их периодическое уплотнение или сборка мусора, и для баз данных с высокими показателями обновляемости подобные уплотнения требуется проводить очень часто. Кроме того, основанные на сборке мусора системы обычно требуют вдвое больше дискового пространства, чем то, которое фактически занимают данные. Также, для поддержания скорости записи N операций в секунду, система ввода/вывода должна в действительности поддерживать скорость, значительно превышающую 2N операций в секунду, поскольку задачи уплотнения должны выполняться быстрее, чем нормальные задачи записи, чтобы они могли успевать за обновлениями и рано или поздно завершить работу, а объём уже записанных данных всегда превышает объём первоначальных данных. Если нельзя гарантировать подобное избыточное выделение ресурсов ввода/вывода, то типичное решение этой проблемы — запрет обновлений во время выполнения уплотнения.

Поскольку перерывы в выполнении записи во время сборки мусора неприемлемы, MDB использует другой подход. В заданном окружении базы данных MDB поддерживается две структуры B+ деревьев: одна содержит данные приложения, а вторая — список свободных страниц с идентификаторами страниц, которые больше не используются. Отслеживание статуса "используется" обычно выполняется с помощью счетчиков ссылок и других подобных механизмов, требующих блокирования. Очевидно, что использование блокировок будет противоречить целям использования MVCC, поэтому вместо этого было разработано безблокировочное решение. В этом решении страницы, не используемые более ни одним из активных снимков базы данных, повторно используются при проведении обновлений, таким образом размер базы данных остаётся относительно постоянным. Это ключевое преимущество MDB перед другими известными базами данных MVCC, такими как CouchDB^[20].

4. Основные моменты реализации

Поскольку с самого начала работы весь исходный код был в свободном доступе, а также по причине ограниченного размера этого документа, здесь будут описаны лишь несколько наиболее заметных деталей реализации. Всех заинтересовавшихся приглашаем почитать исходный код в git-репозитории OpenLDAP и присылать вопросы в список рассылки openldap-technical.

API библиотеки MDB был смоделирован по образцу API BDB для упрощения миграции основанного на BDB кода. Первый срез кода back-mdb был просто скопирован из дерева исходных кодов back-bdb, а затем из него были удалены все ссылки на слои кэширования. После того, как были приведены в соответствие несколько небольших различий API, механизм манипуляции данными был полностью работоспособен (но всё ещё нуждался в оптимизации). По состоянию на сегодня back-mdb составляет 340KB исходного кода, по сравнению с 476KB кода back-bdb/hdb он примерно на 30% меньше.

Сам код MDB берёт своё начало из кода В-дерева "только для добавления" демона ldapd из репозитория исходных кодов OpenBSD, написанного Martin Hedenfalk^[21]. Первый срез кода MDB был просто скопирован из исходного кода ldapd, а затем весь код менеджера страничного кэша B-дерева был удалён и заменён на код доступа mmap. Оригинальный исходный код B-дерева давал на выходе объектный файл размером 39KB, версия MDB — 32KB. Первоначальное тестирование с кодом "только для добавления" показало полную непрактичность такого подхода. С маленькой тестовой базой данных и лишь несколькими сотнями операций добавления/удаления, эта база данных заняла 1027 страниц, из которых только 10 действительно содержали текущую информацию; более 99% пространства было растрачено впустую.

Наряду с управлением mmap и повторным использованием страниц было внесено множество других существенных изменений, пока библиотека MDB не стала тем, что она представляет собой сейчас, в основном были добавлены функции из BDB, которые требовались для back-mdb. По состоянию на сегодня библиотека MDB включает в себя 35KB объектного кода. Сравнение исходного кода не слишком информативно, поскольку в исходном коде MDB большое количество комментариев Doxygen. Первоначальная версия mdb.c была размером 59KB (по сравнению с 76KB исходного кода btree.c), но теперь, со всей встроенной документацией, mdb.c стал размером 162KB. Также для сравнения, BDB сейчас представляет собой более 1.5MB объектного кода.

4.1 Сводка изменений MDB

Код В-дерева "только для добавления" использовал метастраницу в конце файла базы данных для указания на текущий корневой узел B-дерева. Новые страницы всегда записывались последовательно в конце этого файла, за ними по завершении транзакции следовала новая метастраница. Для получения текущего снимка базы данных любому приложению, открывающему базу данных, нужно было искать в обратном направлении от конца файла, чтобы найти самую свежую метастраницу (дополнительные разъяснения деталей операции "только добавление" можно получить на веб-сайте Мартина^[22]).

В MDB две метастраницы занимают страницы 0 и 1 файла базы данных. Они по очереди используются в транзакциях. Каждая метастраница указывает на корневые узлы двух B-деревьев: одно для списка свободных страниц, второе — для данных приложения. Новые данные сначала повторно используют доступные страницы из списка свободных страниц, а затем, при отсутствии доступных свободных страниц, последовательно записываются в конец файла. При фиксации транзакции происходит перезапись более старой метастраницы. По сути, это стандартная двойная буферизация — любые приложения, открывающие базу данных, используют более новую метастраницу, а при фиксации транзакции перезаписывается более старая из них. Для защиты тех, кто производит чтение, от тех, кто производит запись, не требуется блокировок; тем, кто производит чтение, гарантируется, что они всегда будут иметь дело с действующим в настоящий момент корневым узлом.

Оригинальный код поддерживал только одно B-дерево в заданном файле базы данных. Мы же хотели, чтобы MDB поддерживал несколько деревьев в одном файле базы данных. Код индексирования back-mdb использует индивидуальную базу данных для каждого индекса атрибута, и было бы глупо требовать от системного администратора настраивать несколько областей mmap для одного экземпляра back-mdb. Кроме того, код индексирования использует функцию отсортированных дубликатов BDB, позволяющую хранить в B-дереве несколько элементов данных с одним и тем же ключом, и эту функцию необходимо было также добавить в MDB. Обе этих функции были добавлены с помощью механизма подчинённых баз данных, позволяющего элементам данных в B-дереве быть интерпретированными как корневой узел другого B-дерева.

4.2 Блокировка

Для простоты библиотека MDB позволяет в определённый момент времени производить запись только одному процессу. Создание транзакции записи устанавливает блокировку на мьютекс записывающего процесса; обычно этот мьютекс находится в области разделяемой памяти, таким образом, он может быть разделен между несколькими процессами. Эта разделяемая память отделена от области, занимаемой основной базой данных. Область блокировок также содержит таблицу с отдельными слотами для каждого активного процесса чтения этой базы данных. В слотах помещаются идентификаторы процесса чтения и потока, а также идентификатор снимка транзакции, используемого данным процессом чтения. (Идентификаторы процесса и потока учитываются, чтобы выявить устаревшие записи в таблице, например, потоки, закончившие работу, но не высвободившие свои слоты процессов чтения.) Эта таблица строится в выровненной по кэшу процессора памяти, таким образом, предотвращается ложное разделение (False Sharing^[23]) строк кэша.

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

Таблица процессов чтения используется, когда процесс записи хочет выделить страницу и ему известно, что список свободных страниц не пуст. Запись в базу данных выполняется с использованием семантики "копирования при записи": всякий раз, когда должна произойти запись страницы, делается копия и эта копия модифицируется вместо оригинала. После копирования идентификатор исходной страницы добавляется в расположенный в памяти список свободных страниц. При фиксации транзакции этот расположенный в памяти список свободных страниц сохраняется как одна запись в базе данных списков свободных страниц вместе с идентификатором транзакции для этой фиксации. Когда процесс записи хочет извлечь страницу из базы данных списков свободных страниц, он сравнивает идентификатор транзакции самой старой записи в базе данных списков свободных страниц с идентификаторами транзакций всех активных процессов чтения. Если запись в базе данных списков свободных страниц старше, чем все процессы чтения, то все страницы в такой записи могут быть безопасно использованы повторно, поскольку ничего в базе данных на них уже не указывает.

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

4.3 Функции механизма манипуляции данными

Представление базы данных в back-mdb функционально идентично тому, что используется в back-hdb, то есть эта база данных полностью иерархична. Записи хранятся в бинарном формате, основанном на формате, используемом для back-hdb, но с более продвинутой оптимизацией кодирования. Наиболее значимая оптимизация заключается в использовании отображения AttributeDescriptions в двухбайтовые целые числа, таким образом, их канонические имена не хранятся больше в каждой записи. Это позволяет сэкономить немного места в закодированной записи, и, что более важно, делает декодирование атрибута операцией типа O(1) вместо O(logN). Кроме того, хотя библиотеке MDB не требуется выделение какой-либо памяти для возвращения данных, записи по-прежнему требуют выделения памяти под структуры Entry и Attribute. Но поскольку записям не нужно постоянно находиться в кэше, все выделения могут быть произведены из временной локальной для потока памяти. В результате подобной оптимизации декодировщик записей по всем показателям в 6.5 раз быстрее того, что используется в back-hdb.

Конфигурация back-mdb значительно проще — там нет директив настройки кэша. Для механизма манипуляции данными требуется только указать путь к директории, где будут храниться файлы базы данных и максимальный разрешённый размер базы данных. Установки конфигурации влияют только на ёмкость базы данных, а не на её производительность — оптимизировать попросту нечего.

5. Результаты

Для профилирования c целью оптимизации MDB использовались нескольких инструментов, в том числе FunctionCheck^[24], valgrind callgrind^[25] и oprofile^[26]. oprofile меньше всего загружает систему во время работы и обеспечивает наилучшее представление многопоточного поведения, но так как он основан на случайных выборках, он имеет тенденцию пропускать некоторые данные, представляющие интерес. FunctionCheck работает медленнее, в четыре раза медленнее предыдущего инструмента, но так как он использует инструментальный код, он всегда предоставляет полный профиль работы всех функций. Самый медленный инструмент — callgrind, работает в тридцать раз медленнее первого инструмента и предоставляет только данные, относящиеся к однопоточным операциям, но поскольку он выполняет профилирование на уровне инструкций, он даёт наиболее детальное представление о поведении программы. Так как поведение программы может сильно отличаться при выполнении однопоточных и многопроцессорных операций, было важно собрать статистику производительности от разных подходов к тестированию.

В таблице 1 сравнивается общая производительность back-mdb и back-hdb при выполнении первоначальной загрузки тестовой базы данных с помощью slapadd в "быстром" ("quick") режиме.

Таблица 1: Время добавления 5 миллионов записей с помощью slapadd -q

У back-hdb время, затраченное на обработку пользовательских вызовов (user time), значительно превышает реальное время работы (real time) из-за использования многопоточного индексирования. В настоящий момент back-mdb не поддерживает многопоточные операции для slapadd. В этих тестах back-hdb использовал BDB 4.7.25, но результаты с BDB 5.2.28 были, по существу, такими же.

Следующий тест после загрузки баз данных состоял в запуске slapd и замера времени, которое он затрачивает на сканирование всей базы данных целиком при выполнении одного поиска с помощью ldapsearch. Также сравнивались размеры процессов slapd и их соответствие с размерами баз данных на диске. Эти результаты приведены в таблице 2.

Таблица 2: Сравнение ldapsearch

back-hdb был сконфигурирован с размером кэша записей в 5 миллионов записей, таким образом вся база данных полностью была закэширована после первого выполнения ldapsearch. Также отметим, что файлы базы данных были полностью размещены в кэше файловой системы, поскольку непосредственно перед этим была завершена работа slapadd. Кроме того, размер кэша BDB был установлен в 32GB, таким образом база данных целиком также размещалась в этом кэше; во время этого теста не происходило никаких операций ввода/вывода на диск. Эта таблица демонстрирует накладные расходы на извлечение данных из кэша BDB и декодирование их в кэш записей back-hdb. Но даже при втором запуске, когда этих расходов больше нет, back-mdb всё равно быстрее. Дополнительное время, затрачиваемое при первом запуске c back-mdb, отражает время, требуемое операционной системе для отображения страниц базы данных в адресное пространство процесса slapd. Размер процесса slapd с mdb меньше размера базы данных по двум причинам: во-первых, база данных содержит индексы атрибутов, а поскольку в этом поиске не задействуются какие-либо индексы, страницы индексов не отображаются в адресное пространство процесса. Во-вторых, в базе данных содержится несколько свободных страниц, оставшихся от предшествующих транзакций slapadd.

Ещё до начала разработки было подсчитано, что подход MDB будет использовать от 1/3 до 1/2 объёма оперативной памяти по сравнению с аналогичной базой данных back-hdb; этот расчёт подтвердился: back-mdb использует только 37% оперативной памяти от размера back-hdb при нашем тесте с полным кэшированием базы данных.

Затем выполнялся базовый тест параллельной работы путём одновременного запуска 2, 4, 8, и 16 однообразных операций ldapsearch и замера времени на получение результатов. Средние значения результирующего времени приведены в таблице 3.

Таблица 3: Время выполнения параллельных поисков

Первое выполнение этого теста с back-hdb дало какие-то невероятно плохие результаты. Последующее тестирование показало, что тот тест был случайно выполнен с использованием предоставляемой Debian сборкой BDB 4.7, а не с обычно используемой нами собственной сборкой. Принципиальное отличие между ними в том, что мы всегда собираем BDB с параметром конфигурации --with-mutex=POSIX/pthread, тогда как по умолчанию BDB использует гибрид спинлоков (циклических блокировок) и потоковых мьютексов. Спинлоки довольно эффективны в случае одного процессорного сокета, но они очень плохо масштабируются при увеличении количества процессоров. Масштабирование back-mdb, по существу, прямо пропорционально количеству процессоров из-за отсутствия блокировок, замедляющих его работу. Производительность незначительно падает при 16-ти одновременных поисках, поскольку в этот момент все процессоры нашей тестовой машины становятся заняты, таким образом, клиенты и slapd конкурируют за процессорное время с другими процессами системы. В качестве ещё одного показательного момента: время, требуемое для копирования базы данных MDB в /dev/null с помощью 'dd' составило 10.20 секунд. Даже с учётом всех декодирований и фильтрации, которые необходимо было выполнить slapd, сканирование всей базы данных целиком было лишь на 6% медленнее, чем операция прямого копирования.

Предыдущие тесты демонстрируют производительность в случае самых неоптимизированных поисковых запросов. Для получения более приближенных к жизни результатов мы переключились на использование SLAMD^[27]. (У SLAMD есть известные проблемы с производительностью, но мы привыкли к ним, к тому же использование одного и того же инструмента позволяет сравнивать полученные результаты с результатами наших предыдущих работ.) В таблице 4 сравниваются результаты случайным образом сгенерированных запросов к базе данных в 5 миллионов записей для back-hdb и back-mdb.

Таблица 4: Результаты оценки скорости поиска с помощью SLAMD

Полученные для back-hdb результаты в самом деле необычайно хороши — скорость поиска на 15% быстрее, чем у второго по скорости программного обеспечения служб каталогов, которое мы ранее тестировали на этой машине (OpenDS 2.3). Но они не идут ни в какое сравнение с back-mdb. Если взглянуть на фактическую статистику на рисунке 1, Вы увидите, что производительность только возрастает по мере того, как отображение в адресном пространстве процесса наполняется страницами.

Рисунок 1: Результаты оценки скорости поиска back-mdb

После просмотра этих результатов мы подумывали переименовать MDB в "LightningDB" — производительность операций чтения в ней невероятно высока и совершенно беспрецедентна.

Что касается операций записи, то тут back-mdb значительно медленнее back-hdb. Таблица 5 демонстрирует производительность при тестировании чистой операции modify, то есть модификации одного атрибута в случайно выбранных записях из базы данных в 5 миллионов записей.

Таблица 5: Результаты оценки скорости операции модификации с помощью SLAMD

Обратите внимание, что back-mdb фактически выполняет модификации быстро, но, поскольку в MDB соблюдается принцип единичности записи, механизм не выполняет множество операций записи одновременно. Наше финальное тестирование, — сравнение скоростей одновременно выполняющихся операций модификации и поиска, — приведено в таблице 6.

Таблица 6: Результаты оценки скорости комбинированных операций поиска и модификации с помощью SLAMD

До сих пор большая часть усилий была сосредоточена на достижении высокой скорости чтения; возможно, дальнейшие работы позволят повысить производительность операций записи в MDB, но на данный момент это не воспринимается нами как серьезная проблема.

6. Выводы

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

6.1 Портируемость

Хотя изначально разработка велась на Linux, MDB и back-mdb были портированы в MacOSX и Windows. Вряд ли следует ожидать каких-то особых проблем при портировании на другие платформы.

6.2 Другие направления

Также был сделан порт SQLite для использования MDB. Потребовалось расширить библиотеку MDB для поддержки вложенных транзакций, но в остальном изменений практически не потребовалось. Основная функциональность уже работает и код можно получить по адресу http://gitorious.org/mdb/sqlightning. Вероятно, найдётся ещё множество применений для компактной библиотеки баз данных с относительно низкой скоростью записи и практически без накладных расходов на чтение.

6.3 Дальнейшая работа

В нашем списке доработок осталось ещё несколько пунктов:

• До сих пор не исследована оптимизация операций записи.
• Было бы здорово разработать API массовых загрузок для дальнейшего увеличения скорости в slapadd.
• Было бы здорово сделать так, чтобы размер отображения базы данных и другие параметры могли увеличиваться динамически, вместо того чтобы задаваться статически в конфигурации.
• Хорошо бы иметь функции инкрементного и/или полного резервного копирования.
• Всё ещё рассматривается вопрос о back-mdb, который хранил бы записи в базе данных в том же формате, в котором они представлены в памяти, чтобы декодирования не требовалось вовсе.

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

Ссылки

1. Oracle, BerkeleyDB, 2011, http://www.oracle.com/technetwork/database/berkeleydb/overview/index.html

2. Википедия, "B+ деревья", http://en.wikipedia.org/wiki/B+_tree

3. Википедия, "MVCC", http://en.wikipedia.org/wiki/Multiversion_concurrency_control

4. Margo Seltzer, Keith Bostic, "Berkeley DB, архитектура приложений с открытым исходным кодом", 2011, http://www.aosabook.org/en/bdb.html

5. Jong-Hyuk Choi and Howard Chu, "Вскрытие задержек поиска", 2001, http://www.openldap.org/lists/openldap-devel/200111/msg00042.html

6. Howard Chu, "Более эффективные стратегии в malloc?", 2006, http://www.openldap.org/lists/openldap-devel/200607/msg00005.html

7. Howard Chu, "Тестирование malloc", 2006, http://highlandsun.com/hyc/malloc/

8. Emery Berger, "Распределитель памяти Hoard", 2006-2010, http://www.hoard.org

9. Sanjay Ghemawat, Paul Menage, "TCMalloc: malloc с потоковым кэшированием", 2005, http://goog-perftools.sourceforge.net/doc/tcmalloc.html

10. Howard Chu, Minimize malloc fragmentation, 2006, http://www.openldap.org/lists/openldap-devel/200608/msg00033.html

11. Википедия, "Алгоритмы замещения страниц", http://en.wikipedia.org/wiki/Page_replacement_algorithm#Least_recently_used

12. Howard Chu, "Код замещения кэша CLOCK-Pro", 2007, http://www.openldap.org/lists/openldap-bugs/200701/msg00039.html

13. Howard Chu, "Защита от пробуксовок кэша", 2007, http://www.openldap.org/lists/openldap-commit/200711/msg00068.html

14. Википедия, "Одноуровневое хранилище", http://en.wikipedia.org/wiki/Single-level_store

15. Multicians, "Общие сведения и FAQ по Multics", http://www.multicians.org/general.html

16. Apollo Computer Inc., "Принципы построения домена/ОС", 1989, http://bitsavers.org/pdf/apollo/014962-A00_Domain_OS_Design_Principles_Jan89.pdf

17. R.A. Gingell, J.P. Moran и W.A. Shannon, "Архитектура виртуальной памяти в SunOS", Летняя конференция USENIX, 1987, http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.132.8931

18. Marshall Kirk McKusick, Keith Bostic, Michael J. Karels, John S. Quarterman, "Управление памятью, построение и реализация операционной системы 4.4BSD", 1996, http://www.freebsd.org/doc/en/books/design-44bsd/overview-memory-management.html

19. Linus Torvalds, "Статус буферного кэша в ядре 2.3.7+", 1999, http://lkml.indiana.edu/hypermail/linux/kernel/9906.3/0670.html

20. Apache Software Foundation, "Apache CouchDB: технический обзор", 2008-2011, http://couchdb.apache.org/docs/overview.html

21. Martin Hedenfalk, "Репозиторий исходных кодов ldapd OpenBSD", 2010-2011, http://www.openbsd.org/cgi-bin/cvsweb/src/usr.sbin/ldapd/

22. Martin Hedenfalk, "Как работают B-деревья 'только для добавления'", 2011, http://www.bzero.se/ldapd/btree.html

23. Suntorn Sae-eung, "Анализ эффектов ложного разделения строк в системах с многоядерными процессорами", 2010, http://scholarworks.sjsu.edu/etd_projects/2

24. Howard Chu, "FunctionCheck", 2005, http://highlandsun.com/hyc/#fncchk

25. Разработчики Valgrind, "Callgrind: профайлер кэша и прогнозирования ветвлений с генерацией графов вызовов", 2011, http://valgrind.org/docs/manual/cl-manual.html

26. "OProfile — системный профайлер для Linux", 2011, http://oprofile.sourceforge.net/news/

27. UnboundID Corp., "Распределённый инструмент генерации нагрузки SLAMD", 2010, http://dl.thezonemanager.com/slamd/