Berkeley DB — это встроенная система баз данных с открытым кодом, имеющая ряд преимуществ перед другими подобными программными продуктами. Она проста в обращении, поддерживает возможность одновременного доступа нескольких пользователей, реализует поддержку транзакций на промышленном уровне и восстановление баз данных после системных и дисковых сбоев.
Berkeley Database (Berkeley DB) - встроенная система баз данных, которую можно использовать в приложениях, нуждающихся в высокопроизводительном механизме хранения и извлечения пар ключ-значение, поддерживающем одновременный доступ. Программный продукт распространяется в виде библиотеки, которая может быть подключена к коду приложения. Функции библиотеки доступны через ряд API-интерфейсов, в том числе для языков Си, C++, Java, Perl, Python и Tcl.
Sleepycat распространяет Berkeley DB, как программный продукт с открытым кодом. Компания предусматривает лицензионные отчисления за определенные виды использования ПО, а также взимает плату за поддержку и услуги.
История
Berkeley DB зародилась, как новая реализация метода доступа hash, созданного взамен hsearch и различных вариантов dbm (а именно, dbm корпорации AT&T, ndbm от Berkeley и gdbm, разрабатывавшегося в рамках проекта GNU). Продукт был разработан и выпущен под названием Hash в 1990 году программистами Зельцер и Йигит [8].
В первой крупной редакции Berkeley DB, вышедшей в 1991 году, были внесены некоторые изменения в пользовательский интерфейс и добавлен новый метод доступа, B+tree. Примерно в то же время Зельтцер и Олсон разработали прототип транзакционной системы на основе Berkeley DB под названием LIBTP [9], код которой не публиковался.
В 1992 году Berkeley DB 1.85 была включена в состав операционной системы 4.4BSD UNIX. В начале 90-х Зельцер и Бостик сопровождали код в Беркли и Массачусетсе. В то время он получил широкое распространение среди пользователей.
К середине 1996 года появились пользователи, нуждающиеся в коммерческой поддержке продукта. Учтя их пожелания, Бостик и Зельтцер образовали компанию Sleepycat Software. Она совершенствует, распространяет и поддерживает Berkeley DB, а также сопутствующее программное обеспечение и документацию. В середине 1997 года Sleepycat выпустила Berkeley DB 2.1, содержащую ряд важных новшеств, в том числе возможность многопользовательского доступа к базам данных. Компания выпускает около трех коммерческих версий продукта в год. Последняя выпущенная ею версия Berkeley DB имеет номер 3.1.
Краткий обзор Berkeley DB
Си-интерфейсы, входящие в комплект поставки Berkeley DB, позволяют реализовать управление записями баз данных в dbm-стиле и предоставляют доступ к множеству расширений, в числе которых механизм элегантного решения задачи обработки идентичных записей, а также системы поддержки многопользовательского доступа и транзакций. Последнее расширение позволяет параллельно завершать по нескольку транзакций (с перманентной модификацией данных) или откатывать их (с восстановлением баз данных до состояния перед началом транзакции).
Интерфейсы для C++ и Java реализуют небольшой набор классов для работы с базами данных. Корневой класс в обоих языках носит название Db - он содержит методы, инкапсулирующие упомянутые выше интерфейсы dbm-стиля.
Имеются также интерфейсы для работы с Berkeley DB при помощи языков сценариев Perl, Python и Tcl.
Berkeley DB можно подключать к коду приложения динамически или статически.
Использование Berkeley DB
Библиотека Berkeley DB поддерживает возможность многопользовательского доступа к базам данных. Ее можно подключить к коду автономных приложений, к набору совместно работающих приложений или к серверам, обрабатывающим клиентские запросы и выполняющим в соответствии с ними операции над базами данных.
На наш взгляд, Berkeley DB проще в понимании и обращении, чем автономные СУБД. Она хранит и извлекает записи, состоящие из пар ключ-значение. Ключи используются для обнаружения элементов и могут представлять собой данные любого типа или любые структуры, поддерживаемые применяемым языком программирования.
Программист может указать Berkeley DB использовать написанные им самим функции выполнения операций над ключами. Например, метод доступа B+tree может использовать произвольную функцию сравнения, а Hash - произвольную хэш-функцию. Если пользовательские функции не определены, Berkeley DB использует собственные. В противном случае система вообще не просматривает и не интерпретирует ключи и значения. Значения могут быть произвольной длины.
Важно понимать, чем Berkeley DB не является. Berkeley DB - не сервер баз данных, обрабатывающий запросы, поступающие по сети. Это также не SQL-ядро, выполняющее запросы. Не является Berkeley DB и реляционной или объектно-ориентированной СУБД.
Все перечисленные системы можно построить поверх Berkeley DB, которая сама по себе является всего лишь встраиваемым механизмом баз данных. Разработчики постарались сделать его переносимым, компактным, быстрым и надежным.
Приложения, использующие Berkeley DB
Система Berkeley DB встроена в ряд продуктов, как с открытым кодом, так и коммерческих. В данном разделе перечислены некоторые из них.
Серверы каталогов, хранящие и извлекающие данные с применением протокола каталогов LDAP, а также реализующие службу именования и поиска по каталогам в локальных сетях. Основа этой службы - опрос и обновление базы данных, но с применением простого протокола, а не SQL или ODBC. Berkeley DB выполняет функции встроенного диспетчера данных в большинстве существующих серверов каталогов, включая LDAP-серверы компаний Netscape, MessagingDirect и других.
Berkeley DB встроена в большое число почтовых серверов. Intermail компании Software.com использует Berkeley DB в качестве хранилища сообщений и в качестве основного хранилища для своего сервера каталогов. Сервер sendmail (как коммерческий Sendmail Pro компании Sendmail, так и версия, распространяемая через sendmail.org) использует Berkeley DB для хранения псевдонимов и другой информации. Postfix (ранее носивший название VMailer) также использует Berkeley DB для хранения административной информации.
Кроме того, Berkeley DB встроен во множество других программных продуктов. Система применяется для управления списками контроля доступа; хранения пользовательских ключей в инфраструктурах, использующих шифрование с открытым ключом; записи таблиц соответствий машинных и сетевых адресов в адресных серверах; хранения конфигурации и информации об устройствах в программах видеомонтажа.
Berkeley DB также входит в состав многих программ с открытым кодом, распространяемых по Internet. В частности, система встроена в Web-сервер Apache и в графическую оболочку Gnome. Все коммерческие дистрибутивы Linux, а также многие разновидности BSD содержат Berkeley DB.
Методы доступа
В терминологии баз данных метод доступа — это совокупность размещаемой на диске структуры, используемой для хранения данных и операций над этой структурой. Например, многие системы баз данных поддерживают метод доступа B+tree. Он позволяет производить поиск по точному соответствию («найти ключи, равные некоторой константе»), поиск интервала («найти ключи, попадающие в интервал между двумя константами»), а также вставку и удаление записи.
Berkeley DB поддерживает четыре метода доступа: B+tree, Persistent Queues (Queue), Extended Linear Hashing (Hash) и Fixed- or Variable-length Records (Recno). В методах B+tree и Hash ключи могут иметь произвольную структуру. В методах доступа Queue и Recno каждой записи присваивается номер, который и служит ключом. Во всех методах доступа значение может иметь произвольную структуру. Если программист подставляет собственные функции сравнения или хэширования, Berkeley DB хранит и извлекает значения, не интерпретируя их.
В качестве основного хранилища все методы доступа используют файловую систему ОС.
Hash
Berkeley DB поддерживает метод доступа Hash, реализующий расширяемую линейную хэш-таблицу [4]. Особенность такого хэширования в том, что хэш-функция адаптируется по мере роста таблицы, и все хэш-корзины в устойчивом состоянии по мере возможности остаются заполненными не до конца.
Метод доступа Hash поддерживает возможность вставки и удаления записей, а также поиска, но лишь по точному соответствию. Допускается повторение всех записей, хранимых в таблице, но порядок их возврата не определен.
B+tree
Berkeley DB поддерживает метод доступа B+tree [1]. B+деревья хранят пары ключ-значение в листовых страницах, а пары «ключ, адрес дочерней страницы» - на внутренних узлах. Ключи в дереве хранятся в отсортированном порядке, заданном функцией сравнения, указанной при создании базы данных. Для упрощения задачи обхода дерева страницы на листовом уровне содержат указатели на соседей. B+tree поддерживает поиск по точному соответствию (равенству) или интервалу (допустимы лишь интервалы «больше или равно»). Как и хэш-таблицы, B+деревья поддерживают вставку, удаление и повторение всех записей в дереве.
По мере заполнения записями страниц они разбиваются - примерно половина ключей уходит на новую страницу, находящуюся на том же уровне дерева. Большинство реализаций В+дерева после деления оставляют оба узла заполненными наполовину. В общем случае это приводит к снижению производительности, когда вызывающий вставляет ключи по порядку. Но Berkeley DB запоминает порядок вставки и разбивает страницы не поровну, а таким образом, чтобы они заполнялись более, чем наполовину. Благодаря этому уменьшается размер дерева и общий объем базы данных, повышается производительность поиска.
По удалении пустые страницы воссоединяются посредством обратного разбиения. Данный метод доступа не принимает никаких дополнительных мер для балансировки страниц при удалении или вставке. Ключи при каждом обновлении не перемещаются от страницы к странице. Реализация такой возможности могла бы в отдельных случаях снизить время поиска, но дополнительная сложность кода привела бы к замедлению обновлений и частым взаимным блокированиям.
Queue
Berkeley DB реализует метод доступа, управляющий высокопроизводительными долговременными очередями. Он построен на базе метода доступа B+tree, но использует механизмы блокировки и протоколирования, необходимые для работы в условиях интенсивного многопользовательского доступа к голове и хвосту очереди. Процесс обновления головы или хвоста очереди блокирует другие потоки на протяжении не всей транзакции, а лишь на время своего выполнения. Благодаря этому качество поддержки параллельного выполнения транзакций значительно улучшается.
Recno
Berkeley DB содержит метод доступа к записям фиксированной или переменной длины под названием Recno. Он присваивает каждой из записей логический номер, по которому может осуществляться поиск и обновление. Recno может, например, загрузить в базу данных текстовый файл, рассматривая каждую строку в качестве записи. Используя эту возможность, в текстовых редакторах можно производить быстрый поиск по номеру строки [10].
Recno построен на базе метода доступа В+tree и предоставляет простой интерфейс для хранения значений, упорядоченных по номеру. Recno генерирует номера записей самостоятельно. С точки зрения программиста значения нумеруются последовательно, начиная с единицы. Разработчик может указать системе, должны ли записи автоматически перенумеровываться после добавления или удаления записей с меньшими номерами. Если да, то новые ключи можно будет вставлять между существующими.
Особенности
В данном разделе описываются важнейшие особенности Berkeley DB. Разработчик имеет возможность использовать в своем приложении только необходимые ему функции системы.
Например, когда приложение открывает базу данных, оно может назначить требуемый ему уровень поддержки многопользовательского доступа и восстановления. Простые автономные приложения, в частности перенесенные приложения, использовавшие dbm или какую-то из его разновидностей, обычно не требуют поддержки многопользовательского доступа и восстановления после сбоев. Однако, например СУБД корпоративного класса, хранящие данные по операциям службы сбыта и другую критически важную информацию, нуждаются в полноценной поддержке транзакций. В однопользовательском режиме система работает быстрее, чем в многопользовательском, ввиду отсутствия задержек, создаваемых блокировками. С отключенной системой восстановления Berkeley DB также работает быстрее, поскольку в этом случае при внесении изменений в базах данных их не нужно протоколировать.
Некоторые подсистемы уровня ядра, в частности механизмы блокировки и протоколирования могут использоваться и вне контекста методов доступа. Существует, нечасто используемая, возможность изолированного применения в приложении менеджера блокировки Berkeley DB, без каких-либо функций работы с базами данных. Кроме того, с помощью системы двухэтапной блокировки Berkeley DB вызывающий может реализовать блокирование не принадлежащих к базе данных ресурсов, подчиняя их таким образом транзакционной семантике.
Интерфейсы программирования
Berkeley DB предоставляет простой API-интерфейс для управления базами данных. В комплект поставки программного обеспечения не входят стандартные интерфейсы типа ODBC, OLEDB или SQL. Эти интерфейсы весьма удобны, однако они создавались с целью обеспечения интероперабельности систем баз данных, но не простоты или высокой производительности.
Идя навстречу пожеланиям пользователей, создатели Berkeley DB в версии 2.5 реализовали поддержку стандарта XA [5]. XA позволяет Berkeley DB принимать участие в распределенных транзакциях под управлением монитора обработки транзакций, подобного Tuxedo компании BEA Systems. Подобно XA, поверх ядра системы можно построить и другие стандартные интерфейсы. Стандарты не являются частью внутреннего механизма Berkeley DB, так как в их поддержке нуждаются не все приложения.
Работа с записями
Пользователю базы данных может понадобиться произвести поиск определенных ключей или просто просмотреть имеющиеся записи. Berkeley DB поддерживает как доступ по ключам, т. е. возможность найти все записи с заданным ключом, так и последовательный доступ - возможность извлечь сразу все записи базы данных. Порядок, в котором возвращаются записи, зависит от метода доступа. Базы данных в форматах В+tree и Recno возвращают записи в порядке сортировки, а Hash-базы - в случайном порядке.
В Berkeley DB предусмотрены также простые интерфейсы для вставки, обновления и удаления записей в базе данных.
Длинные ключи и значения
Berkeley DB может работать с ключами и значениями размером до 232 байт. Поскольку время, затрачиваемое на копирование записи, возрастает пропорционально ее размеру, в Berkeley DB предусмотрены интерфейсы для работы с фрагментами записей. Если приложению нужна лишь часть большой записи, оно может запросить извлечение лишь требуемого ему фрагмента. Это позволяет экономить и время, и память.
Berkeley DB позволяет программисту задать тип данных как для ключей, так и для значений. Разработчик может использовать любые типы данных, поддерживаемых применяемым языком программирования.
Крупные базы данных
Максимальный размер базы данных, поддерживаемый Berkeley DB, составляет 248 байт или 256 Тбайт. Поскольку Berkeley DB использует в качестве основного хранилища базы данных файловую систему ОС, она должна поддерживать работу с файлами больших размеров. У Sleepycat Software есть клиенты, пользующиеся Berkeley DB для управления базами данных, размер которых превышает 1 Тбайт.
Базы данных, размещаемые в основной памяти
Приложения, не требующие долговременного хранения информации, могут создавать базы данных, размещаемые лишь в основной памяти. Таким базам данных в принципе не свойственны ограничения по производительности, налагаемые подсистемой ввода/вывода.
Существуют приложения, нуждающиеся в дисковом пространстве для основного хранилища, но работающие на системах с очень большим объемом памяти. Berkeley DB может выполнять роль диспетчера очень больших участков памяти, совместно используемой для управления блокированием, хранения кэшированных страниц данных и записей протокола. Например, участок, используемый для кэширования страниц данных, может иметь размеры в несколько гигабайт - таким образом уменьшается вероятность того, что при операции чтения в устойчивом состоянии потребуется доступ к диску. Размер кэш-региона декларируется при старте программы.
Кроме того, многие операционные системы поддерживают файловые функции с отображением памяти - они работают намного быстрее, чем стандартные операции. Berkeley DB может отображать файлы своих баз данных в памяти, когда требуется их использование в режиме «только чтение». В этом случае приложение работает с записями, хранимыми непосредственно на страницах памяти, не расходуя ресурсы на кэширование. Поскольку приложение получает указатели непосредственно на страницы Berkeley DB, выполнять операции записи в таком режиме нельзя. В противном случае изменения могут миновать системы блокирования и протоколирования, и приложение может повредить структуру базы данных. Приложения, работающие в режиме «только чтение», могут использовать поддерживаемые Berkeley DB файловые операции с отображением в память на большинстве архитектур.
Определяемый размер страниц
Программист декларирует размер страниц, используемых применяемым методом доступа, при создании базы данных. Хотя в Berkeley DB предусмотрены разумные значения по умолчанию, разработчик может модифицировать их с целью оптимизации производительности системы. При небольшом размере страниц снижается число записей на страницу. Соответственно, при блокировании такой страницы блокируется меньше записей и улучшается качество многопользовательского доступа. Конечно, затраты ресурсов на страницу в обратной пропорции к их размеру, но зато разработчик, если того требует приложение, имеет возможность увеличить производительность.
Компактность
Berkeley DB - компактная система. Двоичные файлы полного комплекта, в том числе всех методов доступа, механизмов восстановления и транзакций, занимают на стандартных архитектурах около 200 Кбайт.
Курсоры
В терминологии СУБД курсор - это указатель на метод доступа, который циклически вызывается для последовательного возвращения записей. В Berkeley DB имеются курсорные интерфейсы для всех методов доступа. Применение курсоров позволяет, например, обойти В+дерево, просматривая записи в порядке обхода. Указатели на записи в курсорах являются долговременными, так что будучи захваченной один раз, запись может быть впоследствии обновлена на прежнем месте. Кроме того, курсоры позволяют работать с цепочками повторяющихся данных в различных методах доступа.
Соединения
В терминологии СУБД соединение это операция, объединяющая несколько таблиц (или в случае с Berkeley DB, несколько файлов баз данных) в одну. Приведем пример: компания хранит сведения о своих клиентах в одной таблице, а информацию о сбыте - в другой. Допустим, приложению понадобилось просмотреть данные о сбыте по именам клиентов; это потребует приведения в соответствие записей в двух таблицах, имеющих общее поле «имя покупателя». Такое объединение записей из двух таблиц называется соединением.
Berkeley DB содержит интерфейсы для соединения двух или более таблиц.
Транзакции
Транзакция обладает четырьмя свойствами [2].
- Атомарность. Транзакция должна быть выполнена полностью, или не выполнена вообще. Это свойство позволяет, например, единой атомарной операцией осуществить денежный перевод между двумя счетами, уменьшив баланс на одном и увеличив на другом.
- Согласованность. Изменения, вносимые транзакцией в базу данных, не должны повредить ее.
- Изолированность. Независимо от числа пользователей, одновременно работающих с базой данных, у каждого из них должна быть иллюзия, что никаких параллельных операций над базой данных не выполняется.
- Долговечность. Даже если утрачен диск, на котором хранилась база данных, должна быть возможность восстановить ее до состояния после выполнения последней согласованной транзакции.
Сочетание свойств атомарности, согласованности, изолированности и долговечности обычно обозначают сокращением ACID (atomicity, consistency, isolation, durability). Berkeley DB, как и большинство систем баз данных, обеспечивает ACID за счет набора базовых служб.
Программисты могут пользоваться поддержкой транзакций Berkeley DB при необходимости.
Протоколирование с упреждением
При запуске Berkeley DB программист может активизировать систему протоколирования. В процессе транзакции приложение вносит ряд изменений в базу данных. Каждое изменение фиксируется в отдельной записи протокола, предназначенного для хранения состояния записей базы данных до и после внесения изменений. Berkeley DB гарантирует, что запись протокола будет сохранена на устойчивую систему хранения до выполнения операции записи измененных страниц с данными. Такое поведение - запись протокола до записи страниц данных - называется протоколированием с упреждением.
В любой точке процесса выполнения транзакции приложение может подтвердить ее результаты (commit), сделав изменения перманентными, или откатить (roll back), отменив все изменения и восстановив базу данных до состояния перед началом транзакции. Если приложение откатывает транзакцию, протокол будет содержать состояние всех измененных страниц до начала транзакции, и Berkeley DB просто восстановит базу данных до этого состояния. Если приложение завершает транзакцию, Berkeley DB сохраняет записи протокола на диск. Копии страниц данных, находящиеся в памяти, уже содержат внесенные изменения и будут сброшены на диск установленным порядком в ходе нормальной обработки. Тем самым повышается производительность, поскольку протокол ведется последовательно, а запись в страницы данных происходит в случайной последовательности.
Сбои и восстановление
Для завершения и отката транзакций в Berkeley DB используется система протоколирования с упреждением. Она же предоставляет системе восстановления информацию, необходимую для защиты от потери или повреждения данных в случае сбоя. Berkeley DB может восстановить данные после сбоев приложения, системных сбоев и даже катастрофических сбоев вроде утраты жесткого диска.
Восстановление после сбоев требует хранения данных в нескольких различных местах. В ходе нормальной обработки Berkeley DB содержит в памяти копии активных записей протокола и недавно использовавшихся страниц данных. Записи протокола сбрасываются на диск протокола после завершения транзакции. Страницы данных копируются на диск данных по мере своего прохождения через буферный кэш. Периодически системный администратор создает в безопасном месте резервные копии диска данных. После создания резервной копии базы данных протокол можно урезать. Для достижения максимальной отказоустойчивости диск протокола и диск данных должны находиться на разных физических устройствах.
Различные системные сбои могут привести к повреждению содержимого памяти, диска протокола или диска данных. Berkeley DB способна восстанавливаться после утраты любого из этих хранилищ, не теряя ни одной из завершенных транзакций.
В случае потери содержимого компьютерной памяти в результате сбоя системы или приложения все завершенные транзакции сохраняются в протоколе. При перезапуске система восстановления сверяет базу данных с протоколом, внося все изменения в дисковые страницы, находящиеся в памяти в момент сбоя. Поскольку протокол содержит состояния записей до и после внесения изменений, система также использует его для восстановления всех страниц, измененных незавершенными транзакциями.
В случае утраты диска данных системный администратор может восстановить его содержимое по последней резервной копии. Система восстановления сверит базу данных по протоколу, внося все зафиксированные в нем изменения. По окончании этого процесса база данных будет содержать все изменения, внесенные всеми завершенными когда-либо транзакциями.
В случае утраты диска с протоколом система восстановления может использовать находящиеся в памяти копии записей протокола для отката всех незавершенных транзакций, сброса находящихся в памяти страниц на диск данных и корректного закрытия приложения. После этого системный администратор может сделать резервную копию диска с базой данных, установить новый диск для протокола и перезапустить систему.
Контрольные точки
В Berkeley DB имеется служба контрольных точек, взаимодействующая с системой восстановления. В ходе нормальной обработки и протокол, и база данных непрерывно меняются. В любой заданный момент дисковые версии того и другого могут оказаться не соответствующими друг другу. Протокол может содержать изменения, еще не внесенные в базу данных.
С применением контрольных точек все изменения, зафиксированные в протоколе, гарантированно будут внесены и в дисковые данные. Использование контрольных точек в ходе нормальной обработки отнимает некоторое количество ресурсов, но зато снижает временные затраты на восстановление после сбоев.
После сбоя приложения или ОС, системе восстановления необходимо просмотреть протокол не с самого начала, а лишь за две контрольных точки до последней записи. (Не за одну, потому что нет гарантии, что последняя контрольная точка была корректно выставлена - возможно, операция была прервана сбоем, в результате которого еще до ее окончания запустилась система восстановления). Без контрольных точек до перезапуска системы после сбоя может пройти неопределенно много времени. При наличии контрольных точек интервал до перезапуска может быть задан программистом. Процедура восстановления гарантированно будет завершаться за секунду-две.
Сбои программного обеспечения происходят гораздо чаще, чем дисковые сбои. Разработчики стараются обеспечить гарантию того, что ошибки в программах не разрушат данных, но на случай такого редкостного явления, как сбой диска, обычно предусматривают возможность восстановления резервной копии с ленты, в результате которого все же теряется один-два дня работы. Berkeley DB дает возможность обрезать протокол по контрольным точкам. В случае наличия двух последних контрольных точек система восстановления гарантирует, что после сбоя программного обеспечения не будет потеряно ни одной завершенной транзакции. При использовании контрольных точек система восстановления не требует размещения протокола и данных на раздельных дисках, хотя их разнесение все же позволяет поднять производительность за счет параллельной записи.
Двухфазная блокировка
В Berkeley DB имеется служба двухфазной блокировки. В целях снижения вероятности взаимного блокирования и обеспечения свойств ACID системы баз данных осуществляют блокировку в два этапа. В ходе выполнения транзакции блоки только ставятся, но не снимаются. В конце транзакции блоки только снимаются, но не ставятся. На практике большинство систем баз данных, включая Berkeley DB, ставят блоки по требованию в ходе транзакции, затем сбрасывают протокол на диск, затем снимают все блоки.
Berkeley DB может блокировать файлы баз данных (соответствующие таблицам) целиком, или же отдельные страницы внутри их. Блокировку на уровне записей Berkeley DB не осуществляет. Однако, уменьшив размер страницы, разработчик может добиться того, что на каждой из них будет храниться лишь небольшое число записей. Тем самым снижается уровень конфликтов.
При включенной функции блокирования операции чтения и записи базы данных устанавливают двухфазные блоки, не снимаемые до завершения транзакции. То, какие объекты и в каком порядке блокируются, зависит от рабочей нагрузки транзакции. Возможно взаимное блокирование двух и более транзакций, когда каждая из них ждет освобождения объекта, заблокированного параллельно выполняемой транзакцией.
Berkeley DB распознает взаимные блокирования и автоматически откатывает одну из транзакций. Этим снимаются установленные ею блоки, и остальные транзакции продолжают свое выполнение. Вызывающий получает извещение о том, что его транзакция не завершена, и может запустить ее снова. Разработчик может задать интервал запуска процедуры проверки наличия взаимного блокирования и политику выбора транзакции для отката.
Из приложений, к которым подключается Berkeley DB, интерфейсы двухфазной блокировки можно вызывать независимо от других, хотя до сих пор лишь немногим пользователям понадобилось задействовать эту возможность изолированно. Эти интерфейсы открывают доступ к быстрой, переносимой системе блокировки общего назначения. Berkeley DB также позволяет включать внешние по отношению к базе данных объекты в транзакции, контролируя доступ к этим объектам точно так же, как если бы они принадлежали к базе данных.
Механизм двухфазной блокировки построен на самых быстрых примитивах корректного блокирования, поддерживаемых архитектурой нижнего уровня. Это означает, что для каждой из Unix-платформ система блокировки реализована в последней версии Berkeley DB по-разному, не говоря уже о реализации для Windows NT. Как показывает наш опыт, самыми сложными этапами оптимизации производительности является поиск наиболее быстрых примитивов блокирования, корректно работающих на конкретной архитектуре, и интеграция нового интерфейса с уже существующими.
Идеальным был бы случай, если бы во всех операционных систем были реализованы блокирующие примитивы POSIX, и если бы существовала гарантия, что наиболее быстрой операцией является установка блока, на который не претендует другая операция. Блокировки должны работать как между потоками внутри одного процесса, так и между процессами.
Параллелизм
Хорошая производительность при параллельных операциях - одна из важнейших целей, которые ставили разработчики при создании Berkeley DB. Хотя сама по себе Berkeley DB не является многопоточной, она корректно работает в приложениях, использующих потоки. Мы считаем, что решение об использовании потоков и выборе механизма их реализации должны приниматься разработчиком, и поэтому предпочли реализовать механизм (возможность потокового или обычного выполнения), позволяющий приложению поступать сообразно своим потребностям.
Подсистемы блокировки, протоколирования и управления буферным пулом для обмена информацией используют совместный доступ к памяти или другие имеющиеся в от ОС функции совместного доступа. Блокировки, захваты буферных пулов и операции записи в протокол одинаково ведут себя, работая в потоках, в едином процессе и в разных процессах, выполняющихся на одной машине.
Благодаря этому многопользовательские БД-приложения могут запускать отдельный процесс для каждого нового пользователя, создать единый сервер, порождающий отдельный поток для каждого клиентского запроса или воспользоваться любой политикой, комбинирующей эти подходы.
Berkeley DB была тщательно спроектирована таким образом, чтобы минимизировать конфликты и обеспечить максимальный параллелизм. Диспетчер кэша позволяет всем потокам или процессам пользоваться операциями ввода-вывода, выполняемыми одним из них. Совместно используемые ресурсы иногда необходимо блокировать для предоставления эксклюзивного доступа одному управляющему потоку. Мы позаботились о том, чтобы важнейшие функции Berkeley DB были небольшими по объему и чтобы в ходе системных вызовов блоки критических ресурсов не удерживались слишком долго, чтобы создать препятствие для блокирующего потока или процесса. У Sleepycat Software есть клиенты, у которых с одной базой данных параллельно работают сотни пользователей.
Философия проектирования
Berkeley DB по сути представляет собой набор методов доступа и служб, таких как протоколирование, блокировка и использующий их транзакционный доступ. И в научном, и в коммерческом сообществе методы построения систем, подобных Berkeley DB, уже давно хорошо изучены.
Свои преимущества Berkeley DB получила благодаря тому пристальному вниманию, которое уделялось деталям проектирования на протяжении всего существования программного продукта. Мы позаботились о том, чтобы ключевые функции, такие как блокировка и ввод/вывод либо были доступными через удобные интерфейсы, либо работали прозрачно для вызывающего. Будучи программистами, мы понимаем ценность простоты и много работали над упрощением интерфейсов, через которые пользователь обращается к системе баз данных.
Berkeley DB старается не налагать ограничения на код использующего ее приложения. Система не налагает практических ограничений на размер ключей, значений или баз данных; они могут расти, заполняя все имеющееся пространство хранения.
При разработке подсистем блокировки и протоколирования одни критические участки мы делали как можно более компактными, от других отказывались; выполнялась также работа над сжатием размеров блокированных регионов и записей протокола. Все это делалось с целью снижения уровня конфликтов и улучшения пропускной способности.
В архитектуре и реализации Berkeley DB нет никаких новшеств. Проектируя систему, мы старались как можно лучше реализовать традиционные подходы. В результате получилась встроенная система баз данных, превосходящая сходные решения по качеству.
Разработчики большинства систем баз данных приносят простоту в жертву полноте реализации. Система либо проста в использовании, либо она поддерживает параллельный доступ и возможность восстановления после сбоев. Berkeley DB благодаря тщательному проектированию обладает и простотой, и полнотой реализации.
Система немного занимает в памяти, обеспечивает простоту выполнения несложных операций (вставка новой записи занимает всего лишь несколько строк кода), и корректно ведет себя в условиях интенсивного многопользовательского доступа, системных сбоев и даже катастрофических потерь вроде утраты жесткого диска.
Распространение Berkeley DB 3.x
Berkeley DB распространяется в исходных текстах. Пользователи имеют право без ограничений загружать и компилировать наше ПО, а также использовать его в своих приложениях.
Дистрибутив представляет собой заархивированный файл. Он содержит исходный текст библиотеки Berkeley DB, документацию, тестовые комплекты и утилиты сопровождения.
Исходный текст содержит директивы компиляции для всех поддерживаемых платформ. В Unix для идентификации разновидности ОС, сборки библиотеки и утилит Berkeley DB использует распространяемый на условиях лицензии GNU инструмент автоконфигурирования autoconf. Berkeley DB содержит директивы сборки и для других платформ, в том числе для ОС реального времени VxWorks, а также Windows 95/98/NT/2000.
Документация поставляется в формате HTML. Она состоит из двух частей - руководство в традиционном для Unix стиле для программистов и справочное руководство, составленное по принципу учебника.
В дистрибутив входит полноценный текстовый комплект, написанный на Tcl. На наш взгляд, тестовый комплект - главное преимущество Berkeley DB перед подобными ей системами.
Во-первых, он позволяет убедиться, что программа нормально работает после сборки.
Во-вторых, тестовый комплект дает нам возможность скрупулезно проверять каждую очередную версию системы. Узнавая о новых ошибках, мы воспроизводим их на тестовом комплекте. Мы постоянно работаем с тестовым комплектом в ходе разработки, всегда используя его до выпуска. В результате уже на этапе бета-версии система становится весьма стабильной.
Sleepycat предоставляет заказчикам скомпилированные библиотеки и полноценные двоичные дистрибутивы за деньги.
Поддерживаемые платформы
Berkeley DB работает на любой операционной системе с интерфейсом POSIX 1003.1 [3], который имеется практически во всех разновидностях Linux и Unix. Кроме того, программный продукт работает в среде ОС реального времени VxWorks компании Wind River Systems, а также на VMS, Windows 95, Windows 98, Windows NT и Windows 2000.
Лицензирование Berkeley DB 3.x
Berkeley DB распространяется как продукт с открытым кодом. Его можно бесплатно получить, загрузив его с нашего Web-сайта или иными способами. Пользователи имеют возможность без ограничений загружать и включать его в состав своих приложений.
Berkeley DB версий 1.х сопровождалась лицензией UC Berkeley, которая позволяла свободно распространять наше ПО в исходных текстах. После создания Sleepy Software нам потребовалось было разработать новую лицензию, согласующуюся с предыдущей. Ввиду серьезных отличий UC Berkeley от GPL мы не могли просто использовать последнюю. Создание новой лицензии, условия которой противоречили бы первой, означал бы отказ от прежних принципов.
По ряду причин Sleepycat намеревалась продолжать разработку Berkeley DB по принципу открытого кода. Мы согласны с Эриком Рэймондом [7] и другими в том, что ПО с открытым кодом, как правило, отличается от собственнических продуктов, распространяемых только в двоичном виде, более высоким качеством. Наши клиенты пользуются услугами сообщества разработчиков, хорошо знающих Berkeley DB, и способных помочь в проектировании, отладке приложения и оптимизации его производительности. Благодаря широкому распространению исходного текста ошибки обычно выявляются уже на ранних этапах, и исправления вносятся весьма оперативно. Таким образом обеспечивается высокая надежность Berkeley DB. Открытый, бесплатно распространяемый код дает и преимущества с точки зрения бизнеса. Мы имеем и прибыль, и рынок сбыта для своих продуктов и услуг. Кроме того, доступность исходных текстов сокращает нагрузку на нашу службу поддержки, поскольку во многих случаях клиенты могут самостоятельно находить и исправлять ошибки, не обращаясь к нам.
Новая лицензия, контролирующая Berkeley DB 2.x и 3.х, сохраняет принципы распространения кода предыдущих версий системы. Мы позаимствовали из GPL условия, делающие невозможным превращение открытого кода в собственнический.
Вкратце условия использования и распространения Berkeley DB таковы:
- приложение с Berkeley DB должно быть предназначено только для внутреннего применения, или
- должно быть свободно распространяемым в исходных текстах, или
- пользователь должен получить у нас лицензию.
Клиентам, не желающим распространять свои продукты в виде открытого кода, мы предлагаем по разумным ценам лицензии на использование, распространение и расширение Berkeley DB.
Мы стараемся прислушиваться к нуждам сообщества открытого кода. В частности, мы разработали специальные лицензионные соглашения с проектом Gnome, поощряющие использование и распространение в его составе Berkeley DB.
Berkeley DB соответствует определению открытого кода [6]. Лицензия была тщательно составлена таким образом, чтобы Berkeley DB с одной стороны оставалась продуктом с открытым кодом, а с другой обеспечивала прибыль на инвестицию, достаточную для финансирования дальнейшей разработки и поддержки продукта. Ныне действующее лицензионное соглашение уже в течение трех лет дает нам возможность поддерживать разработку Berkeley DB. Если бы не эта лицензия, такого программного продукта могло и не быть.
***
Berkeley DB реализует уникальный набор возможностей, адресованных разработчикам, приложениям которых необходимы простые и надежные службы управления базами данных. Благодаря своей совершенной архитектуре и реализации, а также благодаря тщательному проектированию продукт стал лучшим в своем классе.
Berkeley DB - программный продукт с открытым кодом. В дистрибутив входит все необходимое для сборки и развертывания или переноса его на новые операционные системы.
Sleepycat Software распространяет Berkeley DB на условиях лицензионного соглашения, базирующегося на Berkeley UC и GPL. Лицензия гарантирует, что Berkeley DB останется продуктом открытого кода и обеспечивает Sleepycat возможность зарабатывать средства на финансирование дальнейшего развития своего программного обеспечения.
Майкл Олсон, Кейт Бостик, Марго Зельтцер — сотрудники компании Sleepycat Software.
Литература
[1] Comer, D., «The Ubiquitous B-tree,» ACM Computing Surveys Volume 11, number 2, June 1979
[2] Gray, J., and Reuter, A., Transaction Processing: Concept and Techniques, Morgan-Kaufman Publishers, 1993
[3] Institute for Electrical and Electronics Engineers, IEEE/ANSI Std 1003.1, 1996 Edition
[4] Litwin, W., «Linear Hashing: A New Tool for File and Table Addressing,» Proceeding of the 6th International Conference on Very Large Databases (VLDB), Montreal, Quebec, Canada, October 1980
[5] The Open Group, Distributed TP: The XA+ Specification, Version 2, The Open Group, 1994
[6] Opensource.org, «Open Source Definition,» www.opensourse.org/osd.html, version 1.4, 1999
[7] Raymond, E.S., «The Cathedral and the Bazaar,» www.tuxedo.org/~esr/writings/cathedral-bazzar/cathedral-bazaar.htnl, January 1998
[8] Seltzer, M., and Yigit, O., «A New Hashing Package for UNIX,» Proceedings 1991 Winter USENIX Conference, Dallas, TX, January 1991
[9] Seltzer, M., and Olson, M., «LIBTP: Portable Modular Transactions for UNIX,» Proceeding 1992 Winter Usenix Conference San Francisco, CA, January 1992
[10] Stonebraker, M., Stettner, H., Kalash, J., Guttman, A., and Lynn, N., «Document Processing in a Relational Database System,» Memorandum No. UCB/ERL M82/32, University of California at Berkeley, CA, May 1982
Michael A. Olson, Keith Bostic, Margo Zeltzer. Berkley DB. Перевод статьи публикуется с разрешения Майкла Олсона. Первоначальный вариант статьи был опубликован в материалах конференции 1999 Summer Usenix Technical Conference. Перевод соответствует переработанному варианту статьи, датированному июнем 2000 года
Берклиевская СУБД из Гарварда
Встроенную СУБД Berkeley Database (Berkeley DB), относящуюся к категории свободно распространяемого программного обеспечения, разрабатывает и поддерживает Sleepycat Software. Компания была основана в 1996 году ее нынешним президентом Марго Зельцер и Кейтом Бостиком. В настоящее время оба они являются сотрудниками Гарвардского университета, однако в качестве первоосновы их продукта был избран Berkeley Database package, созданный в Университете Беркли, где они работали прежде. Таким образом, то, что называется Berkeley DB, является плодом сотрудничества двух знаменитых образовательных учреждений.
Не случайно, что, добившись определенных успехов, Sleepycat Software вернула Berkeley DB «на место», открыв в 1998 году свое представительство в Сан-Франциско. Штаб-квартиру в районе Залива возглавляет Майкл Олсон, автор одной и соавтор второй из публикуемых здесь статей. Sleepycat Software сотрудничает с более известной компанией MySQL, СУБД которой, начиная версии MySQL 3.23.21, комплектуется средствами для обработки транзакций, заимствованными из Berkeley DB .
Удивительно активная Марго Зельцер участвует в еще одном интересном проекте VINO, идея которого состоит в создании альтернативных операционных систем, называемых расширяемыми (Extensible Operating System). Сегодня работы в этом направлении лишь начинаются, они ведутся главным образом в университетах, их список и краткую характеристику каждой из разрабатываемых там операционных систем можно найти в Web по адресу www.cs.arizona.edu/people/bridges/os/extensible.html.
Разработчики проекта VINO и аналогичных ему исходят из того, что современные универсальные операционные системы обеспечивают очень «низкий коэффициент полезного действия» серверов, из-за них непропорционально много вычислительной мощности уходит «в тепло», на поддержание работоспособности самой ОС, а не пользу приложений. Роль «вычислительного КПД» становится критически важной при наблюдаемом экспоненциальном росте нагрузки на Internet. VINO и его аналоги обеспечивают более полное использование ресурсов системы за счет более эффективного управления ими.
На вопрос, почему компания названа «Спящая кошка» ответ найти очень просто. Загляните на сайт www.seltzer.com/margo.html.
Леонид Черняк
