Самый быстрый способ извлечь / сохранить миллионы маленьких двоичных объектов

Question

Я ищу быстрое (как с огромной производительностью, а не быстрое исправление) решение для сохранения и извлечения десятков миллионов маленьких (около 1 тыс.) Двоичных объектов. Каждый объект должен иметь уникальный идентификатор для поиска (предпочтительно, GUID или SHA). Дополнительные требования заключаются в том, что он должен использоваться из .NET и не требует дополнительной установки программного обеспечения.

В настоящее время я использую базу данных SQLite с одной таблицей для этого задания, но я хочу избавиться от накладных расходов при обработке простых инструкций SQL, таких как SELECT data FROM store WHERE id = id.

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

P.S. Кстати, объекты никогда не нужно удалять, а скорость вставки очень и очень низкая. Фактически, каждый раз, когда объект изменяется, сохраняется новая версия, а предыдущая версия остается. На самом деле это требование для поддержки путешествий во времени.

Просто добавив некоторую дополнительную информацию в эту ветку:

В BLOB или не в BLOB: хранилище больших объектов в базе данных или файловой системе http://arxiv.org/abs/cs.DB/0701168

Answer 1

Вы можете уменьшить проблемы с производительностью NTFS, разбив идентификатор GUID объекта на части и используя их в качестве имен каталогов. Таким образом, каждый каталог содержит только ограниченное количество подкаталогов или файлов.

например. если идентификатор равен aaaa-bb-cc-ddddeeee, путь к элементу будет c:\store\aaaa\bbcc\dddd\eeee.dat, ограничивая каждый каталог не более чем 64k подпунктов.

Answer 2

Вы должны вызывать функцию prepare только один раз для каждого оператора, с параметром, обозначенным, например, ? (поэтому SELECT data FROM store WHERE id=? - это заявление, которое вы подготовите); тогда то, что вы делаете «миллионы раз», это просто привязывает параметр к подготовленному оператору и вызывает sqlite_step - это быстрые операции. Стоит сравнить, если blob open может быть даже не быстрее. Итак, я рекомендую придерживаться SQLite и углубиться в его низкоуровневый интерфейс (из управляемого C ++, если необходимо) для максимальной производительности - это действительно удивительный маленький движок, и он часто меня приятно удивляет своей производительностью!

Answer 3

Я не знаю, поддерживают ли индексы SQLite или нет, но если это так, то вы можете ускорить процесс, создав индекс над полем ID.

Если это не так, тогда ваш лучший вариант - деревья B +. Спасибо

Answer 4

Я склонен согласиться с Алексом: если вы пишете свое собственное решение, вы заново изобретаете вещи, которые, вероятно, уже есть в SQLite, но если вам нужно ...

Вы, вероятно, можете заставить BTree работать здесь. Это рабочая лошадка любой базы данных, и ваше проблемное пространство не так уж и плохо. Десятки миллионов объектов по 1К - это всего лишь десятки миллиардов байтов, поэтому файл управляется ОС, и существует множество примеров BTree, которые можно попробовать.

По сравнению с использованием структуры каталогов файловой системы для создания аналога BTree с использованием реального BTree будет гораздо быстрее.

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

Answer 5

Вы можете проверить, подходят ли HDF5 структуры для ваших задач

• .Net интерфейс

Answer 6

Мне нравится решение Earwicker. То, как я с этим справился, очень похоже.

Что я сделал, это было:

Скажем, ваш гид 3F2504E0-4F89-11D3-9A0C-0305E82C3301.

Хэш проводника до трехбуквенного хэша. ааа-ZZZ.

Допустим, ради аргумента, что ваш гид хэшируется до "xap".

Ваша информация будет найдена в файле c: \ store \ x \ xa \ xap \ 3F2504E04F8911D39A0C0305E82C3301.dat

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

Answer 7

Как насчет двоичного файла с блоками фиксированного размера около 2 КБ, первые 4 байта которого равны длине объекта ...

местоположение объекта i находится в i * 2048 байтах, затем считывается 2048 байтов для объекта, получая длину фактического объекта из первых 4 байтов (без знака).

Answer 8

Рассматривали ли вы попробовать объектную базу данных, например db4o ? Он может сохранять любые объекты CLR и быстро получать к ним доступ с помощью языка запросов (поддерживает LINQ!). У меня не было миллионов объектов, но доступ к нескольким тысячам был довольно быстрым, и между ними не было существенных отличий, чем схожий SQL-запрос с индексированным полем id.

Answer 9

Сохранение отдельного индекса (другого файла) в [Guid -> номер файла + смещение в файле]. Используйте двоичный поиск для поиска и переходите к файлу n + 1 всякий раз, когда файл n достигает определенного размера. Каждая строка в файле индекса занимает всего 24 байта (фиксированный размер: guid + номер файла + смещение, разделение файлов по 4 ГБ), и сортировка выполняется быстро (вставка сортируется с низкой скоростью.)

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

Редактировать 2: Если вам это тоже нужно безопасно (всегда хорошая идея), посмотрите здесь описание того, как концепция транзакций файловой системы может помочь вам в пуленепробиваемых вещах. 1007 *

Answer 10

Я думаю, что запрос к базе данных - ваш лучший выбор.

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

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