Kyoto Cabinet

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:51, 1 марта 2019.
Kyoto Cabinet
NewLogoKyoto Cabinet.png
Создатели: FAL Labs
Разработчики: FAL Labs
Выпущена: 2009
Написана на: C++
Операционная система: Кросс-платформенное
Локализация: Английский язык, Японский язык
Тип ПО: Подсистема хранения, библиотека
Лицензия: GNU GPL
Веб-сайт fallabs.com/kyotocabinet

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

Описание

В базе данных предусмотрены следующие методы доступа: сохранение записи с ключом и значением, удаление записи по ключу, извлечение записи по ключу. Кроме того, обеспечивается доступ к каждому ключу. Эти методы доступа похожи на методы исходной библиотеки DBM (и ее последователей: NDBM и GDBM), определенной в стандарте UNIX. Киотский кабинет является альтернативой для DBM из-за его более высокой производительности.

Каждая операция хеш-базы данных имеет временную сложность «O (1)». Поэтому, теоретически, производительность постоянна независимо от масштаба базы данных. На практике производительность определяется скоростью основной памяти или запоминающего устройства. Если размер базы данных меньше емкости основной памяти, производительность будет отображаться на скорости памяти, которая выше, чем std :: map STL. Конечно, размер базы данных может быть больше, чем объем основной памяти, а верхний предел составляет 8 эксабайт. Даже в этом случае для каждой операции требуется только один или два поиска запоминающего устройства.

Каждая операция базы данных дерева B + имеет временную сложность «O (log N)». Таким образом, теоретически производительность является логарифмической по отношению к масштабу базы данных. Хотя производительность произвольного доступа к базе данных дерева B + ниже, чем к базе данных хэшей, база данных дерева B + поддерживает последовательный доступ в порядке ключей, что обеспечивает прямой поиск строк и поиск диапазона целых чисел. Производительность последовательного доступа намного выше, чем у произвольного доступа.

Поскольку API основан на объектно-ориентированном проектировании, база данных хэшей и база данных дерева B + имеют те же методы, которые унаследованы от верхнего абстрактного класса. Помимо них, семь видов баз данных предоставляются в одном базовом классе.

  • Хэш-база данных прототипа основана на стандартном контейнере std :: unordered_map.
  • База данных дерева прототипов основана на стандартном контейнере std :: map.
  • База данных stash основана на оригинальной реализации сохраняющей память наивной карты хешей.
  • Хэш-база данных кеша основана на оригинальной реализации хеш-карты с двойной связью и алгоритмом удаления LRU.
  • База данных дерева кеша основана на хэш-базе данных кеша и обеспечивает механизм дерева B +.
  • Хэш-база данных каталога основана на механизме каталогов файловой системы и хранит записи в виде соответствующих файлов в каталоге.
  • База данных дерева каталогов основана на хэш-базе данных каталогов и обеспечивает механизм дерева B +.

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

Киотский кабинет работает очень быстро. Например, время хранения одного миллиона записей составляет 0,9 секунды для базы данных хэшей и 1,1 секунды для базы данных дерева B +. Более того, размер базы данных очень маленький. Например, накладные расходы для записи составляют 16 байтов для базы данных хэшей и 4 байта для базы данных дерева B +. Кроме того, масштабируемость кабинета Киото великолепна.

Киотский кабинет написан на языке C++ и предоставляется как API C++, C, Java, Python, Ruby, Perl и Lua. Kyoto Cabinet доступен на платформах, API которых соответствует C ++ 03 с расширениями библиотеки TR1. Киотский кабинет является свободным программным обеспечением, лицензируемым в соответствии с GNU General Public License. Лицензионное исключение FOSS также предоставляется для размещения продуктов под другими бесплатными лицензиями и лицензиями с открытым исходным кодом. Специальное исключение связывания библиотеки FOSS также предоставляется для того, чтобы быть доступным в некоторых конкретных библиотеках FOSS. С другой стороны, коммерческая лицензия также предоставляется. Если вы используете Kyoto Cabinet в проприетарном программном обеспечении, вам потребуется коммерческая лицензия. [Источник 1]:

Характеристика

Оригинальная DBM была разработана Кеннетом Томпсоном как часть оригинальной AT & T UNIX. После этого многие последователи разработали такие DBM-подобные продукты, как NDBM, SDBM, GDBM, TDB и BerkeleyDB. В 2003 году я разработал QDBM для замены GDBM по соображениям производительности.

В 2009 году Киотский кабинет был разработан как еще один преемник QDBM. По сравнению с аналогичным продуктом (Токийский кабинет) были реализованы следующие преимущества. Однако производительность Токийского кабинета выше, чем у Киотского кабинета, по крайней мере, в однопотоковых операциях.

  • Повышает эффективность использования пространства : меньший размер файла базы данных.
  • Улучшает параллелизм : более высокая производительность в многопоточной среде.
  • Улучшает переносимость : абстракция нижнего уровня для поддержки не-POSIX систем.
  • Повышает удобство использования : упрощенный API, объектно-ориентированный дизайн.
  • Повышает надежность : файл базы данных не поврежден даже в катастрофической ситуации.

Эффективная реализация базы данных Hash
Киотский кабинет использует алгоритм хеширования для извлечения записей. Если массив блоков имеет достаточное количество элементов, временная сложность поиска равна «O (1)». То есть время, необходимое для извлечения записи, является постоянным, независимо от масштаба базы данных. То же самое относится и к хранению и удалению. Столкновение значений хеша управляется отдельной цепочкой. Структура данных цепочек представляет собой двоичное дерево поиска. Даже если массив блоков имеет необычно дефицитные элементы, временная сложность поиска равна «O (log n)».

Киотский кабинет достигает улучшения производительности при извлечении, загружая весь массив блоков в ОЗУ. Если массив блоков находится в ОЗУ, можно получить доступ к области целевой записи с помощью примерно одного набора файловых операций, таких как lseek, read и write. Массив корзины, сохраненный в файле, не читается в ОЗУ с помощью вызова read, но напрямую отображается в ОЗУ с помощью вызова mmap. Следовательно, время подготовки к подключению к базе данных очень мало, и два или более процессов могут совместно использовать одну и ту же карту памяти.

Хеш-функцией, используемой для хеш-таблицы, является MurMurHash 2.0. Если число элементов массива сегментов составляет около половины записей, хранящихся в базе данных, хотя это зависит от характеристики входных данных, вероятность столкновения значений хеш-функции составляет около 55,3% (35,5%, если то же самое, 20,4%, если дважды, 11,0%, если четыре раза, 5,7%, если восемь раз). В этом случае можно извлечь запись с помощью двух или менее наборов файловых операций. Если он превращен в индекс производительности, для обработки базы данных, содержащей миллион записей, требуется массив блоков с полмиллиона элементов. Размер каждого элемента составляет 6 байт. То есть, если доступно 3 МБ ОЗУ, можно обработать базу данных, содержащую миллион записей.

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

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

Полезная реализация базы данных B + Tree
Хотя база данных дерева B + медленнее, чем база данных хэшей, она имеет упорядоченный доступ к каждой записи. Заказ может быть назначен пользователями. Записи в базе данных дерева B + сортируются и упорядочиваются по логическим страницам. Для каждой страницы поддерживается разреженный индекс, организованный в виде дерева B, являющегося многогранным сбалансированным деревом. Таким образом, сложность времени поиска и тд равна «O (log n)». Курсор предоставляется для доступа к каждой записи по порядку. Курсор может перейти на позицию, указанную клавишей, и может перейти вперед или назад от текущей позиции. Поскольку каждая страница организована в виде двойного связанного списка, временная сложность пошагового курсора равна «O (1)».

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

Несмотря на то, что для обновления базы данных дерева B + требуются операции на многих страницах, Kyoto Cabinet ускоряет этот процесс за счет кэширования страниц и сокращения операций с файлами. Кэш страниц реализован с помощью двухслойного списка LRU, который понимает, что часто используемые страницы кэшируются в «горячем» списке, а недавно открытые страницы кэшируются в «горячем» списке LRU. Если кэш страниц работает эффективно и весь разреженный индекс кэшируется в памяти, можно извлечь запись одним или несколькими наборами файловых операций.

Каждая страница базы данных дерева B + может храниться в сжатом виде. По умолчанию используется метод сжатия «Deflate» с помощью ZLIB. Поскольку записи на странице имеют сходные шаблоны, ожидается высокая эффективность сжатия благодаря алгоритму LZW. В случае обработки текстовых данных размер базы данных уменьшается примерно до 50% или менее. Если масштаб базы данных большой, а дисковый ввод-вывод является узким местом, использование сжатия значительно повышает скорость обработки. Кроме того, вы можете указать такие внешние алгоритмы сжатия, как LZO и LZMA.

Практическая функциональность

Киотский кабинет имеет механизмы транзакций. Можно выполнить серию операций между началом и концом транзакции в виде единовременного кода или отменить транзакцию и выполнить откат до состояния перед транзакцией. Поддерживаются два уровня изоляции: «serializable» и «read uncommitted». Долговечность обеспечивается записью в журнал с опережением записи и теневым разбиением на страницы

Автоматические транзакции и механизмы автоматического восстановления также поддерживаются. Если при открытии базы данных указана опция автоматической транзакции, каждая операция обновления защищается транзакцией, которая неявно фиксируется. Следовательно, долговечность может быть гарантирована без явных операций транзакции. Механизм автоматического восстановления работает после сбоя базы данных вне транзакции. Если при открытии базы данных обнаруживается несогласованность базы данных, все регионы сканируются как с помощью «fsck», и база данных неявно восстанавливается из сохранившихся записей.

Киотский кабинет предоставляет два режима подключения к базе данных: «читатель» и «писатель». Читатель может выполнять поиск, но не сохранять и не удалять. Автор может выполнять все методы доступа. Контроль исключения между процессами осуществляется при подключении к базе данных путем блокировки файлов. Пока писатель подключен к базе данных, ни читатели, ни писатели не могут быть подключены. Пока считыватель подключен к базе данных, другие читатели могут подключаться, а писатели - нет. Согласно этому механизму согласованность данных гарантируется при одновременных подключениях в многозадачной среде.

Функции API являются реентерабельными и доступны в многопоточной среде. Различные объекты базы данных могут работать параллельно полностью. Для одновременных операций с одним и тем же объектом базы данных rwlock (блокировка чтения-записи) используется для контроля исключений. То есть, пока поток записи управляет объектом, другие потоки чтения и записи блокируются. Однако, пока поток чтения управляет объектом, потоки чтения не блокируются. Степень детализации блокировки зависит от структуры данных. Хэш-база данных использует блокировку записи. База данных дерева B + использует блокировку страницы.

Чтобы улучшить производительность и параллелизм, Kyoto Cabinet использует такие элементарные операции, встроенные в популярные процессоры, как atomic-increment и CAS (сравнение и замена). Примитивы блокировки, предоставляемые собственной средой, такой как пакет потоков POSIX, чередуются собственными примитивами, использующими CAS.

Простые, но гибкие интерфейсы

Kyoto Cabinet предоставляет простые API на основе объектно-ориентированного дизайна. Каждая операция для базы данных инкапсулируется и публикуется как понятные методы как open , close, set, remove, get и так далее. Классы хеш-базы данных и базы данных B + tree являются производными от общего абстрактного класса, который определяет интерфейс. Портировать приложение из одной базы данных в другую очень просто. Кроме того, API полиморфной базы данных предназначен для назначения базы данных во время выполнения.

Киотский кабинет поддерживает модель «посетитель». Вы можете определить произвольные операции с базой данных с помощью функций обратного вызова. Класс посетителя инкапсулирует функции обратного вызова и их данные о состоянии. У класса базы данных есть метод accept, который принимает экземпляр класса посетителя и вызывает его функции с записанными данными. Возвращаемое значение функции обратного вызова отражается как новое состояние записи.

Кроме того, предоставляется множество полезных утилит, таких как «поиск по префиксу», «поиск по регулярному выражению», «ведение журнала», «горячее резервное копирование», «псевдо-снимок» и «объединение». Каркас для MapReduce также предоставляется. Хотя он не распределен, он полезен для совокупного расчета с меньшей загрузкой ЦП и меньшим использованием памяти. Простая текстовая база данных представляет собой интерфейс для обработки простого текстового файла как файла базы данных. Полезно использовать текстовый файл в качестве входных или выходных данных для инфраструктуры MapReduce. Полезно построить инвертированные индексы.

Хотя базовый API предоставляется для C ++, также предоставляются привязки для других языков, таких как C, Java, Python, Ruby, Perl и Lua. Интерфейсы командной строки также предоставляются в соответствии с каждым API. Они полезны для создания прототипов, тестирования и отладки.[Источник 2]

Руководство по эксплуатации

Требования

  • Linux 2.6 и более поздние версии (i386 / x86-64 / PowerPC / Alpha / SPARC)
  • FreeBSD 7.1 и более поздние версии (i386 / x86-64)
  • Solaris 10 и более поздние версии (i386 / x86-64 / SPARC)
  • Mac OS X 10.5 и более поздние версии (x86-64)
  • Windows XP и более поздние версии (i386 / x86-64)

gcc (GNU Compiler Collection) 4.2 или более поздней makeверсии и (GNU Make) требуются для установки Kyoto Cabinet с пакетом исходного кода. Они установлены по умолчанию в Linux, FreeBSD и так далее. Поскольку Киотский кабинет зависит от следующих библиотек, установите их заранее.

  • ZLIB : для сжатия данных без потерь. 1.2.3 или более поздняя версия обязательна.

Установка

Когда архивный файл Kyoto Cabinet извлечен, измените текущий рабочий каталог на созданный каталог и выполните установку. [Источник 3]

Запустите скрипт конфигурации.

 $ ./configure

Сборка программ.

 $ make

Выполните самодиагностику. Это займет некоторое время.

 $ make check

Установите программы. Эта операция должна выполняться rootпользователем.

 # make install

После завершения серии работ будут установлены следующие файлы:

/usr/local/include/kccommon.h
/usr/local/include/kcutil.h
/usr/local/include/kcthread.h
/usr/local/include/kcfile.h
/usr/local/include/kccompress.h
/usr/local/include/kccompare.h
/usr/local/include/kcmap.h
/usr/local/include/kcregex.h
/usr/local/include/kcdb.h
/usr/local/include/kcplantdb.h
/usr/local/include/kcprotodb.h
/usr/local/include/kcstashdb.h
/usr/local/include/kccachedb.h
/usr/local/include/kchashdb.h
/usr/local/include/kcdirdb.h
/usr/local/include/kctextdb.h
/usr/local/include/kcpolydb.h
/usr/local/include/kcdbext.h
/usr/local/include/kclangc.h
/usr/local/lib/libkyotocabinet.a
/usr/local/lib/libkyotocabinet.so.x.y.z
/usr/local/lib/libkyotocabinet.so.x
/usr/local/lib/libkyotocabinet.so
/usr/local/lib/pkgconfig/kyotocabinet.pc
/usr/local/bin/kcutiltest
/usr/local/bin/kcutilmgr
/usr/local/bin/kcprototest
/usr/local/bin/kcstashtest
/usr/local/bin/kccachetest
/usr/local/bin/kcgrasstest
/usr/local/bin/kchashtest
/usr/local/bin/kchashmgr
/usr/local/bin/kctreetest
/usr/local/bin/kctreemgr
/usr/local/bin/kcdirtest
/usr/local/bin/kcdirmgr
/usr/local/bin/kcforesttest
/usr/local/bin/kcforestmgr
/usr/local/bin/kcpolytest
/usr/local/bin/kcpolymgr
/usr/local/bin/kclanctest
/usr/local/man/man1/...
/usr/local/share/doc/kyotocabinet/...

Использование библиотекой

Kyoto Cabinet предоставляет API [Источник 4]языка C ++ и доступен для программ, соответствующих стандарту C ++ 03. Поскольку заголовочные файлы Киотского Кабинета предоставляются в виде 'kcutil.h', 'kchashdb.h' и тд., приложения должны включать один или несколько из них, соответственно, для использования API. Поскольку библиотека предоставляется как 'libkyotocabinet.a'и 'libkyotocabinet.so', и они зависят от 'libz.so', 'libstdc++.so', 'librt.so', 'libpthread.so', 'libm.so'и 'libc.so', соответствующие опции компоновщика требуются командой build. Типичная команда сборки следующая.

 $ g ++ -I / usr / local / include example.cc -o example \ 
-L / usr / local / lib -lkyotocabinet -lz -lstdc ++ -lrt -lpthread -lm -lc

Для Windows

Microsoft Visual Studio (Visual C ++) требуется для сборки Киото Кабинета на Windows. Конфигурация здания описана в файле 'VCmakefile', который следует редактировать в соответствии с вашей средой.

Выполните следующую команду в окне командной строки.

 > nmake -f VCmakefile

Проведите самодиагностику.

 > nmake -f VCmakefile check

Если все процессы сборки завершаются успешно,то генерируется статическая библиотека kyotocabinet.lib и некоторые исполняемые файлы. На данный момент, ни DLL, ни инструмент для установки не предоставляется. Пожалуйста, установите заголовочные файлы, библиотечный файл и исполняемые файлы самостоятельно.

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

 > cl /I. example.cc kyotocabinet.lib

По умолчанию библиотека построена со ссылками на 'LIBCMT.LIB'с помощью '/MT'. Если вы хотите использовать 'MSVCRT.LIB', что требуется для MFC, пересоберите библиотеку с опцией '/MD' и установите ту же опцию при сборке приложений. Если ваша среда имеет 64-битную версию, добавьте /D_SYS_WIN64_опцию в опции компилятора, чтобы повысить производительность.

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

Особенности различных классов базы данных

Поскольку Kyoto Cabinet предоставляет различные классы баз данных, они имеют общий базовый класс, который определяет общий интерфейс всех классов баз данных. То есть вы можете использовать следующие классы таким же образом как на таблице.

Класс Файл Описание
ProtoHashDB kcprotodb.h Прототип хэш-базы.база данных в памяти реализована с помощью std :: unorderd_map.
ProtoTreeDB kcprotodb.h База данных дерева прототипов. База данных в памяти реализована с помощью std :: map.
StashDB kcstashdb.h Тайник базы данных. База данных в памяти экономит память.
CacheDB kccachedb.h База данных в памяти, показывающая удаление LRU.
GrassDB kccachedb.h База данных дерева кеша. База данных дерева B + в памяти: кэш с порядком.
HashDB kchashdb.h База данных хэша. Файловая база данных хеш-таблицы: типичная DBM.
TreeDB kchashdb.h База данных файлового дерева. Файловая база данных дерева B +: DBM с заказом.
DirDB kcdirdb.h Каталог хэш-базы данных. Соответствующие файлы в каталоге файловой системы.
ForestDB kcdirdb.h База данных дерева каталогов. Каталог базы данных дерева B +: огромная DBM с заказом.
TextDB kctextdb.h Простая текстовая база данных. Эмуляция для обработки простого текстового файла в качестве базы данных.
PolyDB kcpolydb.h Полиморфная база данных. Динамическое связывание вышеуказанных баз данных.

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

class persistence algorithm complexity sequence lock unit
ProtoHashDB volatile hash table O(1) undefined whole (rwlock)
ProtoTreeDB volatile red black tree O(log N) lexical order whole (rwlock)
StashDB volatile hash table O(1) undefined record (rwlock)
CacheDB volatile hash table O(1) undefined record (mutex)
GrassDB volatile B+ tree O(log N) custom order page (rwlock)
HashDB persistent hash table O(1) undefined record (rwlock)
TreeDB persistent B+ tree O(log N) custom order page (rwlock)
DirDB persistent undefined undefined undefined record (rwlock)
ForestDB persistent B+ tree O(log N) custom order page (rwlock)
TextDB persistent plain text undefined stored order record (rwlock)

Источники

  1. Fundamental Specifications of Kyoto Cabinet Version 1 // FAL Labs. [2009-2012]. Дата обновления: 04.03.2011. URL: https://fallabs.com/kyotocabinet/spex.html (дата обращения: 09.01.2019).
  2. Features // FAL Labs. [2009-2012]. Дата обновления: 12.05.2012. URL: https://fallabs.com/kyotocabinet/spex.html#features (дата обращения: 01.03.2019).
  3. Specificatoins of Command Line Utilities of Kyoto Cabinet. URL: https://fallabs.com/kyotocabinet/command.html (дата обращения: 09.01.2019).
  4. Kyoto Cabinet: a straightforward implementation of DBM. URL: https://fallabs.com/kyotocabinet/api/ (дата обращения: 09.01.2019).