Tokyo Cabinet

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:10, 21 января 2019.
Tokyo Cabinet
Tokyo Cabinet Logo.png
Разработчики: FAL Labs
Выпущена: 2006
Постоянный выпуск: 1.4.48 / 5 August 2010 года; 9 years ago (2010-08-05)
Написана на: C
Операционная система: Кросс-платформенное
Локализация: Английский язык, Японский язык
Тип ПО: Подсистема хранения, библиотека
Лицензия: GNU GPL
Веб-сайт fallabs.com/tokyocabinet

Tokyo Cabinet является библиотекой C для управления базами данных "ключ-значение". Был анонсирован авторами как "современная реализация DBM (DataBase Manager) ".

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

Описание

Особенности Tokyo Cabinet[Источник 1]:
Современная реализация Менеджера Баз Данных (DBMS (Database Management System))

  • база данных "ключ-значение"
  • простая библиотека
  • наследник QDBM (Quick DataBase Manager - другая библиотека от FAL Labs)

Высокий уровень производительности

  • вставка: 0.4 сек / 1 миллион записей (2 500 000 запросов/сек)
  • поиск: 0.33 сек / 1 миллион записей (3 000 000 запросов/сек)

Высокий уровень согласованности

  • многопоточное сохранение
  • блокировка чтения/записи при запросах

Высокий уровень масштабируемости

  • сложность структур данных (хеш-таблиц и B+ деревьев) = O(1) и O(log n)
  • нет лимита на возможный размер файла БД

Возможность транзакций

  • выполняются требования ACID
    • Atomicity — Атомарность
    • Consistency — Согласованность
    • Isolation — Изолированность
    • Durability — Устойчивость

Вариативность структур данных

  • хранение в памяти в структуре лист/хеш/дерево
  • файловое хранение в структуре хеш/B+ дерево/массив/таблица

Биндинг скриптов на различных языках

Различные реализации БД

При помощи Tokyo Cabinet можно реализовать несколько видов БД.

TCHDB: Hash Database[Источник 2]

Возможность реализации БД на хеш-таблице.

Особенности:

Рисунок 1 – Описание TCHDB


Статическое хеширование

  • Сложность O(1)

Использование метода цепочек для устранения коллизии

  • Используется бинарное дерево поиска
  • Балансируется с помощью второго хеша

Пул свободных блоков

  • Обеспечивается лучшая аллокация
  • Используется динамическое дефрагментирование

Сочетание mmap и pwrite/pread

  • Сохраняет вызовы Syscall

Компрессия

  • Уменьшает размер
  • Используется сжатие gzip/bzip2
  • Есть возможность использовать пользовательские утилиты для сжатия данных

Структура такой базы данных показана на рисунке 1.


TCBDB: B+ Tree Database[Источник 3]

Возможность реализации БД на B+ дереве.

Особенности:

Рисунок 2 – Описание TCBDB


B+ дерево

  • Сложность O(log n)

Кеширование страниц

  • Удаление LRU: Least recently used (Вытеснение давно неиспользуемых)
  • Интеллектуальный поиск, основанный на предположениях

Базируется на Хеш БД

  • Записывает страницы в хеш БД
  • Улучшение эффективности использования по памяти и по времени

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

  • Возможность использовать пользовательские функции сравнения для балансировки дерева
  • Проверка совпадений по префиксу/диапазону

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

  • Реализованы функции jump/next/prev

Структура такой базы данных показана на рисунке 2.

TCFDB: Fixed-length Database[Источник 4]

Возможность реализации БД на массиве фиксированной длины.

Особенности:

Рисунок 3 – Описание TCFDB


Массив фиксированной длины

  • Сложность O(1)
  • Натуральное число ключей
  • Адресация записей несколькими ключами

Наибольшая эффективность

  • Основной объем загружается с помощью mmap
  • Нет хранения ключей для каждой записи
  • Чрезвычайно быстрый и согласованный

Структура такой базы данных показана на рисунке 3.


TCTDB: Table Database[Источник 5]

Возможность реализации табличной БД.

Особенности:

Рисунок 4 – Описание TCTDB


Колонко-ориентированная БД

  • Первичный ключ и проименованные столбцы
  • Базируется на хеш БД

Гибкая структура

  • Нет схем данных, нет типов данных
  • Различные структуры для каждой записи

Механизм запросов

  • Различные операторы соответствуют значением столбцов
  • Лексический порядок значений столбцов

Индексы столбцов

  • Реализованы с помощью B+ деревьев
  • Записаны как строка/число
  • Инвертированный индекс токена/q-gram
  • Оптимизатор запросов

Структура такой базы данных показана на рисунке 4.

Структуры данных, хранящиеся в памяти программы[Источник 6]

TCXSTR: extensible string

Растяжимая строка

  • Доступны функции конкатенации, форматированной аллокации

TCLIST: array list

Список, реализованный с помощью массива

  • Случайный доступ по индексу
  • Доступны функции push/pop, unshift/shift, insert/remove

TCMAP: map of hash table

Хеш-таблица

  • Доступны функции insert/remove/search
  • Порядок итерации по порядку вставки

TCTREE: map of ordered tree

Упорядоченное дерево

  • Доступны функции insert/remove/search
  • Порядок итерации определяется с помощью функции сравнения

Другие возможности и механизмы библиотеки

Абстрактная БД

  • простой интерфейс
    • хеш и дерево, хранящиеся в памяти
    • файловые хеш, B+ дерево, массив и таблица
  • выбор конкретного способа хранения во время работы

Удаленная БД

  • сетевой интерфейс абстрактной БД
  • реализован в Tokyo Tyrant

Разнообразные доп. утилиты

  • обработка строк, операции ФС
  • пул памяти, шифрование/расшифрование

Пример кода на основе библиотеки

int main(int argc, char **argv) {
	TCHDB *hdb;
	int ecode;
	char *key, *value;
	/* create the object */
	hdb = tchdbnew();
	/* open the database */
	if (!tchdbopen(hdb, "casket.hdb", HDBOWRITER | HDBOCREAT)) {
		ecode = tchdbecode(hdb);
		fprintf(stderr, "open error: %s\n", tchdberrmsg(ecode));
	}
	/* store records */
	if (!tchdbput2(hdb, "foo", "hop") ||
		!tchdbput2(hdb, "bar", "step") ||
		!tchdbput2(hdb, "baz", "jump")) {
		ecode = tchdbecode(hdb);
		fprintf(stderr, "put error: %s\n", tchdberrmsg(ecode));
	}
	/* retrieve records */
	value = tchdbget2(hdb, "foo");
	if (value) {
		printf("%s\n", value);
		free(value);
	}
	else {
		ecode = tchdbecode(hdb);
		fprintf(stderr, "get error: %s\n", tchdberrmsg(ecode));
	}
	/* traverse records */
	tchdbiterinit(hdb);
	while ((key = tchdbiternext2(hdb)) != NULL) {
		value = tchdbget2(hdb, key);
		if (value) {
			printf("%s:%s\n", key, value);
			free(value);
		}
		free(key);
	}
	/* close the database */
	if (!tchdbclose(hdb)) {
		ecode = tchdbecode(hdb);
		fprintf(stderr, "close error: %s\n", tchdberrmsg(ecode));
	}
	/* delete the object */
	tchdbdel(hdb);
	return 0;
}

Установка

Качаем архив с официального сайта http://fallabs.com/tokyocabinet/tokyocabinet-1.4.48.tar.gz и дополнительные пакеты, необходимые для работы библиотеки.

$ wget http://fallabs.com/tokyocabinet/tokyocabinet-1.4.48.tar.gz
$ tar -xvzf tokyocabinet-1.4.48.tar.gz
$ apt-get install libbz2-dev
$ apt-get install zlib1g-dev

Собираем Tokyo Cabinet.

$ ./configure
$ make
$ make install
$ make clean

Библиотека скомпилирована и готова к работе!

Источники

  1. FAL Labs Official Page: Презентация продуктов FAL Labs. // FAL Labs. [2006-2011]. Дата обновления: 05.08.2010. URL: http://fallabs.com/tokyocabinet/tokyoproducts.pdf (дата обращения: 03.10.2018).
  2. FAL Labs Official Page: The Hash Database API. // FAL Labs. [2006-2011]. Дата обновления: 05.08.2010. URL: https://fallabs.com/tokyocabinet/spex-en.html#tchdbapi (дата обращения: 03.10.2018).
  3. FAL Labs Official Page: The B+ Tree Database AP. // FAL Labs. [2006-2011]. Дата обновления: 05.08.2010. URL: https://fallabs.com/tokyocabinet/spex-en.html#tcbdbapi (дата обращения: 03.10.2018).
  4. FAL Labs Official Page: The Fixed-length Database API. // FAL Labs. [2006-2011]. Дата обновления: 05.08.2010. URL: https://fallabs.com/tokyocabinet/spex-en.html#tcfdbapi (дата обращения: 03.10.2018).
  5. FAL Labs Official Page: The Table Database API. // FAL Labs. [2006-2011]. Дата обновления: 05.08.2010. URL: https://fallabs.com/tokyocabinet/spex-en.html#tctdbapi (дата обращения: 03.10.2018).
  6. FAL Labs Official Page: The Abstract Database API. // FAL Labs. [2006-2011]. Дата обновления: 05.08.2010. URL: https://fallabs.com/tokyocabinet/spex-en.html#tcadbapi (дата обращения: 03.10.2018).