Эффективная (временная и пространственная) словарная база данных (уникальное слово для uniq id и обратно)

Question

Я ищу решение, которое способно:

• хранить уникальные слова произвольного размера вместе с их уникальным 64-битным целочисленным идентификатором без знака и 32- или 64-битным беззнаковым счетчиком ссылок int.
• быстрый доступ к данным с помощью следующих шаблонов:
  • для поиска слова, верните его идентификатор uint64
  • для поиска идентификатора, верните слово
• вставка новых записей, предпочтительно с автоматически увеличенным идентификатором и атомно-увеличенным счетчиком ссылок, предпочтительно в пакетных фиксациях (то есть не слово за словом, каждое в отдельной транзакции, а несколько слов в одной зафиксированной транзакции)
• атомарное удаление записей с нулевым счетчиком ссылок (это можно сделать даже при полном просмотре таблицы с ограниченной скоростью, путем перебора всех записей и удаления записей с 0 счетом в транзакции)
• хранение большого количества записей о традиционной вращающейся ржавчине (жестких дисках),номер записи где-то между 100 миллионами и 1000 миллиардами (1000 * 10 ^ 9)
• средний размер слова где-то между 25-80 байтами
• было бы хорошо иметь питона (дляпрототипирование) и интерфейс C, в основном встраиваемый, или эффективный «удаленный» (будет только на локальном хосте) API

Например, схема MySQL будет выглядеть примерно так:

CREATE TABLE words (
    id SERIAL,
    word MEDIUMTEXT,
    refcnt INT UNSIGNED,
    INDEX(word(12)),
    PRIMARY KEY (id)
)

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

Во время поиска наиболее эффективного решения я решил, чтодо сих пор: - потому что слова имеют много общего (большинство из них - простые словарные слова в разных языках и наборах символов), что-то такое: http://www.unixuser.org/~euske/doc/tcdb/index.html было бы хорошо - лучшее, что я мог найти, такдалеко находится TDB Кабинета министров Токио: packages.python.org/tokyocabinet-python/TDB.html, но я должен оценить его производительность и возможные настройки (где хранить какиеи какой тип индекса использовать для лучшей эффективности времени и пространства)

Есть идеи, алгоритмы, еще лучше, готовые к использованию продукты и настройки?

Спасибо,

Answer 1

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

Если вы можете разделить свою работу, вы можете загружать / обрабатывать данные с нескольких хостов параллельно.Учитывая скорость redis, вам может не потребоваться пакетировать вещи, но это возможно (команда MSET).

Еще один приятный аспект - вы можете взаимодействовать с Redis из командной строки, используя команду redis-cli.Таким образом, вы можете попробовать / отладить последовательность команд, прежде чем пытаться написать какой-либо код.Предполагая, что redis работает на локальном хосте с портом по умолчанию, введите:

% redis-cli
redis>

Я написал быстрый набор команд, которые поддерживают ваш вариант использования.

Этот фрагмент создает целочисленный ключ с именемnext.words.id и атомарно увеличивает его, возвращая новое значение.Я начал последовательность в 123455 для иллюстрации.(integer) 123456 - это значение, которое будет возвращено вашему клиенту:

redis> SET next.words.id 123455
OK
redis> INCR next.words.id
(integer) 123456

Затем мы сопоставим слово с его идентификатором "chaos" -> 123456, затем создадим обратное отображение из id:123456 -> "chaos" и, наконец, создадимключ счетчика ссылок установлен на 0.Префиксы id: и ref: и next.words.id - это просто соглашения, которые я выбрал - вы можете использовать любое название, которое вам нравится.

redis> SET chaos 123456
OK
redis> SET id:123456 chaos
OK
redis> SET ref:chaos 0
OK

Чтобы увеличить счетчик ссылок для слова "хаос":

redis> INCR ref:chaos
(integer) 1
redis> INCR ref:chaos
(integer) 2

Чтобы уменьшить счетчик ссылок, используйте DECR:

redis> DECR ref:chaos
(integer) 1
redis> DECR ref:chaos
(integer) 0

В этот момент ваш код может обнаружить, что счет для " chaos " перешел к 0 и выполните следующие команды в одной транзакции: удаление слова и его ключей id: и ref:.Я использовал команду WATCH, чтобы избежать состояния гонки: если какой-либо другой клиент изменит ключ ref:chaos до принятия нашей транзакции, он будет прерван.

redis> WATCH ref:chaos
OK
redis> GET chaos
(integer) 123456
redis> MULTI
redis> DEL chaos
QUEUED
redis> DEL id:123456
QUEUED
redis> DEL ref:chaos
QUEUED
redis> EXEC
1) (integer) 1
2) (integer) 1
3) (integer) 1

Надеюсь, это поможет.