DBM (вычисления)

Эта статья нуждается в дополнительных ссылках для проверки . Пожалуйста, помогите улучшить эту статью , добавив ссылки на надежные источники . Неисходный материал может быть оспорен и удален.
Найдите источники: вычисления «DBM» — новости · газеты · книги · ученый · JSTOR ( январь 2022 г. ) ( узнайте, как и когда удалить это шаблонное сообщение )

В вычислительной технике DBM — это библиотека и файловый формат, обеспечивающий быстрый доступ к данным с помощью одного ключа. База данных «ключ-значение » из оригинальной Unix , dbm , является ранним примером системы NoSQL . ^[1]^[2]^[3]

История

Первоначальная библиотека dbm и формат файла представляли собой простой движок базы данных , первоначально написанный Кеном Томпсоном и выпущенный AT&T в 1979 году. Название представляет собой трехбуквенную аббревиатуру от DataBase Manager и может также относиться к семейству движков баз данных с API и функциями. производный от оригинального dbm .

Библиотека dbm хранит произвольные данные с помощью одного ключа ( первичного ключа ) в сегментах фиксированного размера и использует методы хеширования , чтобы обеспечить быстрый поиск данных по ключу.

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

Библиотека dbm и ее производные являются предреляционными базами данных — они управляют ассоциативными массивами , реализованными в виде хэш-таблиц на диске . На практике они могут предложить более практичное решение для высокоскоростного хранилища с доступом по ключу, поскольку не требуют накладных расходов на подключение и подготовку запросов. Это уравновешивается тем фактом, что они обычно могут быть открыты для записи только одним процессом за раз. Демон агента может обрабатывать запросы от нескольких процессов, но вводит дополнительные затраты IPC .

Реализации

Первоначальная библиотека AT&T dbm была заменена множеством последующих реализаций. Известные примеры включают: ^[3]

ndbm («новый dbm»), основанный на оригинальном dbm с некоторыми новыми функциями.
GDBM («GNU dbm»), переписанная GNU библиотека, реализующая функции ndbm и собственный интерфейс. Также предоставляет новые функции, такие как отказоустойчивость для обеспечения согласованности данных. ^[4]^[5]
sdbm («маленький dbm»), общедоступная версия dbm . Это часть стандартных дистрибутивов Perl и Ruby . ^[6]^[7]
qdbm ("Quick Database Manager"), высокопроизводительная СУБД , использующая многие из тех же методов, что и Tokyo/Kyoto Cabinet. Написано тем же автором до того, как они перешли к шкафам. ^[8]
tdb («Простая база данных»), простая база данных, используемая Samba , которая поддерживает несколько авторов. Имеет API на основе gdbm. ^[9]
Berkeley DB , 1991 г. Замена ndbm компанией Sleepycat Software (теперь Oracle ), созданной для того, чтобы обойти авторские права AT&T Unix на BSD . Он имеет множество расширений, таких как параллелизм, управление транзакциями, хеширование и хранение B-дерева.
LMDB : реализация дерева B+ с отображением памяти при копировании при записи на C с API в стиле Беркли.

Следующие базы данных вдохновлены dbm, но они напрямую не предоставляют интерфейс dbm, даже если было бы тривиально обернуть его:

cdb («постоянная база данных»), база данных Дэниела Дж. Бернштейна , файлы базы данных можно только создавать и читать, но нельзя изменять .
Tkrzw , лицензированный Apache 2.0, преемник Киотского кабинета и Токийского кабинета .
WiredTiger : база данных с традиционным хранилищем, ориентированным на строки и столбцы.

Доступность

По состоянию на 2001 год реализация DBM с помощью ndbm была стандартной для Solaris и IRIX, тогда как gdbm повсеместно используется в Linux . Реализации Berkeley DB были стандартными для некоторых бесплатных операционных систем. ^[2]^[10] После изменения лицензирования Berkeley DB на GNU AGPL в 2013 году такие проекты, как Debian , перешли на LMDB. ^[11]

Надежность

Тест фаззинга AFL 2018 года для многих баз данных семейства DBM выявил множество проблем в реализациях, когда речь идет о поврежденных или недействительных файлах базы данных. Только freecdb Дэниела Дж. Бернштейна не показал сбоев. Авторы gdbm, tdb и lmdb не замедлили отреагировать. Berkeley DB отстал из-за огромного количества других проблем; ^[10] исправления не будут иметь отношения к пользователям программного обеспечения с открытым исходным кодом из-за изменения лицензии, заблокировавшего их обратно на старой версии. ^[11]

Смотрите также

Встроенная база данных
База данных плоских файлов
ИСАМ
База данных "ключ-значение"
Мобильная база данных
NoSQL
Семафор (программирование)

использованная литература

^ Кью 2007 , с. 80: «СУБД были с нами с первых дней вычислительной техники, когда была осознана потребность в быстром поиске по ключу. Первоначальная DBM — это библиотека и файловый формат на основе UNIX для быстрого и масштабируемого доступа к данным с ключом. за ними (по порядку) следуют NDBM ("новая DBM"), GDBM ("GNU DBM") и Berkeley DB. Последняя на сегодняшний день является наиболее продвинутой и единственной DBM, находящейся в активной разработке на сегодняшний день. Тем не менее, все DBM, начиная с NDBM, обеспечивают ту же базовую функциональность, что и большинство программ, включая Apache.SDBM с минимальной реализацией также связан с APR и доступен для приложений вместе с другими DBM.
Хотя NDBM уже устарел — как и город, названный греками Новым городом («Неаполис») примерно в 600 г. до н. э. и до сих пор называемый Неаполем, — он остается базовым DBM. NDBM использовался ранними модулями Apache, такими как версии Apache 1.x mod_auth_dbmи mod_rewrite. И GDBM, и Berkeley DB предоставляют эмуляции NDBM, а дистрибутивы Linux поставляются с той или иной из этих эмуляций вместо «настоящей» NDBM, которая исключена из соображений лицензирования. К сожалению, различные форматы файлов полностью несовместимы, и существуют тонкие различия в поведении, связанном с блокировкой базы данных. Эти проблемы привели к тому, что постоянный поток пользователей Linux стал сообщать о проблемах с DBM в Apache 1.x».
^ а б Хейзел 2001 , с. 500: «Наиболее распространенный [одноключевой] формат называется DBM. В большинстве современных версий Unix стандартно установлена библиотека DBM, хотя это не относится к некоторым более старым системам. Две наиболее распространенные библиотеки DBM — это ndbm (стандартная для Solaris и IRIX) и Berkeley DB версии 2 или 3 (стандарт для нескольких бесплатных операционных систем). Exim поддерживает оба из них, а также более старую версию 1 Berkeley DB, gdbm и tdb .
^ a b
Ladd & O'Donnell 2001 , стр. 823–824: «Большинство систем UNIX имеют какую-либо базу данных DBM. DBM — это набор библиотечных подпрограмм, которые управляют файлами данных, состоящими из пар ключ-значение. Подпрограммы DBM управляют тем, как пользователи вводят и извлекают информацию из базы данных.Хотя это не самый мощный механизм для хранения информации, использование DBM является более быстрым методом извлечения информации, чем использование плоского файла.Поскольку большинство сайтов UNIX используют одну из библиотек DBM, инструменты вам нужно хранить информацию в базе данных DBM, легко доступны.Существует
почти столько же разновидностей библиотек DBM, сколько существует систем UNIX.Хотя большинство этих библиотек совместимы друг с другом, все они в основном работают одинаково...
Ниже приводится список некоторых из наиболее популярных доступных библиотек DBM:
- DBM — DBM хранит базу данных в двух файлах. Первый имеет расширение .Pagи содержит растровое изображение. Второй, имеющий расширение .Dir, содержит данные.
- NDBM — NDBM очень похож на DBM, но с несколькими дополнительными функциями; это было написано, чтобы обеспечить лучшие методы хранения и поиска. Кроме того, NDBM позволяет вам открывать множество баз данных, в отличие от DBM, в котором вам разрешено открывать только одну базу данных в вашем скрипте. Как и DBM, NDBM хранит информацию в двух файлах с расширениями .Pagи .Dir.
- SDBM — SDBM поставляется с архивом Perl, портированным на многие платформы. Поэтому вы можете использовать базы данных DBM до тех пор, пока для вашего компьютера существует версия Perl. SDBM был написан так, чтобы соответствовать функциям, предоставляемым NDBM, поэтому переносимость кода не должна быть проблемой. Perl доступен практически на всех популярных платформах.
- GDBM — GDBM — это версия GNU семейства подпрограмм базы данных DBM. GDBM также позволяет кэшировать данные, сокращая время, необходимое для записи в базу данных. База данных не имеет ограничений по размеру; его размер полностью зависит от ресурсов вашей системы. Файлы базы данных GDBM имеют расширение .Db. В отличие от DBM и NDBM, которые используют два файла, GDBM использует только один файл.
- Berkeley db — Berkeley db значительно расширяет исходные подпрограммы DBM. База данных Berkeley использует хэш-таблицы так же, как и другие базы данных DBM, но библиотека также может создавать базы данных на основе отсортированного сбалансированного двоичного дерева ( BTREE) и хранить информацию с номером строки записи ( RECNO). Используемый метод полностью зависит от того, как вы хотите хранить и извлекать информацию из базы данных. Berkeley db создает только один файл без расширения».
Викискладе есть медиафайлы по теме аварийной устойчивости . Руководство по ГДБМ . Проверено 3 октября 2021 г.
^ «Защита от сбоев исходного хранилища ключей и значений NoSQL» . Проверено 3 октября 2021 г.
^ йигит, озан. "sdbm.bun" . cse.yorku.ca . Проверено 8 мая 2019 г. .
Викискладе есть медиафайлы по теме SDBM класса . Документация для Ruby 2.4.0 . Обратите внимание, что Ruby поставляется с исходным кодом для SDBM, в то время как стандартные библиотеки DBM и GDBM зависят от внешних библиотек и заголовков.
^ «QDBM: быстрый менеджер баз данных» . www.fallabs.com . 2006.
^ "tdb: Главная страница" . tdb.samba.org .
↑ a b Дебру, Лайонел (16 июня 2018 г.). «oss-security — развлечение с базами данных типа DBM…» openwall.com .
^ a b Сури, Ондржей (19 июня 2014 г.). «Новая цель проекта: избавиться от Berkeley DB (post jessie)» . debian-devel (список рассылки). Дебиан .

Библиография

Хейзел, Филип (2001). Exim: агент по пересылке почты . О'Райли.
Лэдд, Эрик; О'Доннелл, Джим (2001). Использование XHTML, XML и Java 2: Platinum Edition . Que. ISBN 9780789724731.
Кью, Ник (2007). Книга модулей Apache: разработка приложений с помощью Apache . Прентис Холл Профессионал. ISBN 9780132704502.

Библиотека SDBM @ Apache
Мэтью, Нил; Стоунз, Ричард (2008). «Базы данных». Начало программирования для Linux . Уайли.
Олсон, Майкл А .; Бостик, Кит; Зельцер, Марго (1999). «Беркли БД» (PDF) . Материалы ежегодной технической конференции FREENIX Track:1999 USENIX .

[2007-kew-apache-1] Кью 2007 , с. 80: «СУБД были с нами с первых дней вычислительной техники, когда была осознана потребность в быстром поиске по ключу. Первоначальная DBM — это библиотека и файловый формат на основе UNIX для быстрого и масштабируемого доступа к данным с ключом. за ними (по порядку) следуют NDBM ("новая DBM"), GDBM ("GNU DBM") и Berkeley DB. Последняя на сегодняшний день является наиболее продвинутой и единственной DBM, находящейся в активной разработке на сегодняшний день. Тем не менее, все DBM, начиная с NDBM, обеспечивают ту же базовую функциональность, что и большинство программ, включая Apache.SDBM с минимальной реализацией также связан с APR и доступен для приложений вместе с другими DBM.
Хотя NDBM уже устарел — как и город, названный греками Новым городом («Неаполис») примерно в 600 г. до н. э. и до сих пор называемый Неаполем, — он остается базовым DBM. NDBM использовался ранними модулями Apache, такими как версии Apache 1.x mod_auth_dbmи mod_rewrite. И GDBM, и Berkeley DB предоставляют эмуляции NDBM, а дистрибутивы Linux поставляются с той или иной из этих эмуляций вместо «настоящей» NDBM, которая исключена из соображений лицензирования. К сожалению, различные форматы файлов полностью несовместимы, и существуют тонкие различия в поведении, связанном с блокировкой базы данных. Эти проблемы привели к тому, что постоянный поток пользователей Linux стал сообщать о проблемах с DBM в Apache 1.x».

[2001-hazel-exim-2] а б Хейзел 2001 , с. 500: «Наиболее распространенный [одноключевой] формат называется DBM. В большинстве современных версий Unix стандартно установлена библиотека DBM, хотя это не относится к некоторым более старым системам. Две наиболее распространенные библиотеки DBM — это ndbm (стандартная для Solaris и IRIX) и Berkeley DB версии 2 или 3 (стандарт для нескольких бесплатных операционных систем). Exim поддерживает оба из них, а также более старую версию 1 Berkeley DB, gdbm и tdb .

[2001-ladd-odonell-xhtml-3] Ladd & O'Donnell 2001 , стр. 823–824: «Большинство систем UNIX имеют какую-либо базу данных DBM. DBM — это набор библиотечных подпрограмм, которые управляют файлами данных, состоящими из пар ключ-значение. Подпрограммы DBM управляют тем, как пользователи вводят и извлекают информацию из базы данных.Хотя это не самый мощный механизм для хранения информации, использование DBM является более быстрым методом извлечения информации, чем использование плоского файла.Поскольку большинство сайтов UNIX используют одну из библиотек DBM, инструменты вам нужно хранить информацию в базе данных DBM, легко доступны.Существует
почти столько же разновидностей библиотек DBM, сколько существует систем UNIX.Хотя большинство этих библиотек совместимы друг с другом, все они в основном работают одинаково...
Ниже приводится список некоторых из наиболее популярных доступных библиотек DBM:
DBM — DBM хранит базу данных в двух файлах. Первый имеет расширение .Pagи содержит растровое изображение. Второй, имеющий расширение .Dir, содержит данные.
NDBM — NDBM очень похож на DBM, но с несколькими дополнительными функциями; это было написано, чтобы обеспечить лучшие методы хранения и поиска. Кроме того, NDBM позволяет вам открывать множество баз данных, в отличие от DBM, в котором вам разрешено открывать только одну базу данных в вашем скрипте. Как и DBM, NDBM хранит информацию в двух файлах с расширениями .Pagи .Dir.
SDBM — SDBM поставляется с архивом Perl, портированным на многие платформы. Поэтому вы можете использовать базы данных DBM до тех пор, пока для вашего компьютера существует версия Perl. SDBM был написан так, чтобы соответствовать функциям, предоставляемым NDBM, поэтому переносимость кода не должна быть проблемой. Perl доступен практически на всех популярных платформах.
GDBM — GDBM — это версия GNU семейства подпрограмм базы данных DBM. GDBM также позволяет кэшировать данные, сокращая время, необходимое для записи в базу данных. База данных не имеет ограничений по размеру; его размер полностью зависит от ресурсов вашей системы. Файлы базы данных GDBM имеют расширение .Db. В отличие от DBM и NDBM, которые используют два файла, GDBM использует только один файл.
Berkeley db — Berkeley db значительно расширяет исходные подпрограммы DBM. База данных Berkeley использует хэш-таблицы так же, как и другие базы данных DBM, но библиотека также может создавать базы данных на основе отсортированного сбалансированного двоичного дерева ( BTREE) и хранить информацию с номером строки записи ( RECNO). Используемый метод полностью зависит от того, как вы хотите хранить и извлекать информацию из базы данных. Berkeley db создает только один файл без расширения».

[4] DBM — DBM хранит базу данных в двух файлах. Первый имеет расширение .Pagи содержит растровое изображение. Второй, имеющий расширение .Dir, содержит данные.

[5] NDBM — NDBM очень похож на DBM, но с несколькими дополнительными функциями; это было написано, чтобы обеспечить лучшие методы хранения и поиска. Кроме того, NDBM позволяет вам открывать множество баз данных, в отличие от DBM, в котором вам разрешено открывать только одну базу данных в вашем скрипте. Как и DBM, NDBM хранит информацию в двух файлах с расширениями .Pagи .Dir.

[6] SDBM — SDBM поставляется с архивом Perl, портированным на многие платформы. Поэтому вы можете использовать базы данных DBM до тех пор, пока для вашего компьютера существует версия Perl. SDBM был написан так, чтобы соответствовать функциям, предоставляемым NDBM, поэтому переносимость кода не должна быть проблемой. Perl доступен практически на всех популярных платформах.

[7] GDBM — GDBM — это версия GNU семейства подпрограмм базы данных DBM. GDBM также позволяет кэшировать данные, сокращая время, необходимое для записи в базу данных. База данных не имеет ограничений по размеру; его размер полностью зависит от ресурсов вашей системы. Файлы базы данных GDBM имеют расширение .Db. В отличие от DBM и NDBM, которые используют два файла, GDBM использует только один файл.

[8] Berkeley db — Berkeley db значительно расширяет исходные подпрограммы DBM. База данных Berkeley использует хэш-таблицы так же, как и другие базы данных DBM, но библиотека также может создавать базы данных на основе отсортированного сбалансированного двоичного дерева ( BTREE) и хранить информацию с номером строки записи ( RECNO). Используемый метод полностью зависит от того, как вы хотите хранить и извлекать информацию из базы данных. Berkeley db создает только один файл без расширения».

[4] Викискладе есть медиафайлы по теме аварийной устойчивости . Руководство по ГДБМ . Проверено 3 октября 2021 г.

[5] «Защита от сбоев исходного хранилища ключей и значений NoSQL» . Проверено 3 октября 2021 г.

[6] йигит, озан. "sdbm.bun" . cse.yorku.ca . Проверено 8 мая 2019 г. .

[7] Викискладе есть медиафайлы по теме SDBM класса . Документация для Ruby 2.4.0 . Обратите внимание, что Ruby поставляется с исходным кодом для SDBM, в то время как стандартные библиотеки DBM и GDBM зависят от внешних библиотек и заголовков.

[8] «QDBM: быстрый менеджер баз данных» . www.fallabs.com . 2006.

[9] "tdb: Главная страница" . tdb.samba.org .

[fuzz-10] Дебру, Лайонел (16 июня 2018 г.). «oss-security — развлечение с базами данных типа DBM…» openwall.com .

[deb-11] Сури, Ондржей (19 июня 2014 г.). «Новая цель проекта: избавиться от Berkeley DB (post jessie)» . debian-devel (список рассылки). Дебиан .

[1]