Храните огромные std :: map, в основном на диске

Question

У меня есть программа на C ++, которая может генерировать ОГРОМНОЕ количество данных - миллиарды двоичных записей различного размера, скорее всего, менее 256 байт, но несколько простираются до нескольких К. Большинство записей редко будут программа просматривается после их создания, но некоторые из них будут регулярно доступны и изменены. Невозможно сказать, какие именно, когда они созданы.

Учитывая объем данных, я никак не могу сохранить все это в памяти. Но поскольку данные нужно только проиндексировать и получить к ним доступ по их номеру (64-разрядное целое число), я не хочу получить издержки на полноценную программу базы данных. В идеале я хотел бы рассматривать его как std::map с его данными, хранящимися на диске до тех пор, пока не будет запрошено.

Есть ли уже написанная библиотека, которая будет делать то, что я ищу, или мне нужно написать ее самостоятельно?

РЕДАКТИРОВАТЬ: После некоторых размышлений я понял, что ответ Роба Уокера содержал правильную точку зрения: мне было бы трудно получить хоть что-то похожее на целостность данных в классе домашнего пивоварения, который я получил от реальная база данных.

Хотя BerkeleyDB (как предлагает RHM) выглядит так, как будто он будет делать именно то, что мы ищем, двойное лицензирование - это головная боль, с которой мы не хотим иметь дело. Когда мы закончим с кодом и сможем доказать, что он извлечет значительную пользу из BerkeleyDB (что, вероятно, будет), мы пересмотрим проблему.

Я посмотрел на предложение Ферруччо о stxxl, но не смог сказать, как он будет обрабатывать прерывание и перезапуск программы (возможно, с изменениями). С таким большим количеством данных я бы не хотел просто отбрасывать то, что он уже выполнил, и начинать каждый раз заново, если можно было бы сохранить некоторые данные.

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

Answer 1

Взгляните на STXXL .

stxxl::map<> похоже, что он делает именно то, что вам нужно.

Answer 2

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

Миллиарды записей - это большой набор данных на любом отрезке. С какой скоростью генерируются записи? Как долго они сохраняются? Меняется ли схема доступа с течением времени?

Всегда ли обновления содержат тот же объем данных, что и оригинал?

Я бы предложил окончательно доказать, что решение БД не будет работать до того, как вы начнете работать самостоятельно, особенно если целостность данных имеет первостепенное значение (и обычно это ...). Надежное поддержание этого объема данных на диске определенно может быть проблемой. Нужна ли вам какая-либо семантика транзакций при изменении данных? Является ли клиент многопоточным?

Answer 3

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

Answer 4

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

http://www.sqlite.org/

Я процитирую их страницу:

SQLite - это программная библиотека, в которой реализован автономный серверный транзакционный механизм баз данных SQL с нулевой конфигурацией. SQLite - это наиболее широко используемый в мире механизм баз данных SQL. Исходный код SQLite находится в открытом доступе.

И

Текущая разработка и сопровождение SQLite частично финансируется членами консорциума SQLite, в том числе: Adobe, Symbian, Bloomberg, Mozilla

Если вам нужен легкий дб, это может быть просто

Answer 5

Я использовал Gigabase http://www.garret.ru/gigabase.html, в нескольких проектах, у него отличный интерфейс C ++, я работал с миллионами записей без проблем, он поддерживает откат Он имеет MIT-подобную лицензию, также автор очень быстро отвечает на вопросы и исправляет ошибки.

Answer 6

вам, вероятно, придется кататься самостоятельно. я, вероятно, вставил бы это в пару таблиц mysql и лениво загрузил карту фиксированного размера (lru). если вы действительно не хотите избегать БД, поместите записи <256 или любой другой длины в файлы произвольного доступа с фиксированной записью и сохраните записи большего размера в виде отдельных файлов. </p>

Answer 7

Я согласен с другими, что BerkeleyDB, sqlite или gigabase должны быть хорошими решениями.

Но написание собственного решения тоже не должно быть слишком сложным.

У меня есть простое решение, но есть три предпосылки:

1. Вы можете по крайней мере сохранить std::vector<int64> с numkey элементами в памяти.
2. Ваши ключи могут быть непрерывными.
3. После записи файла каждый размер записи данных имеет фиксированный maxsize, т.е. его размер не может быть увеличен.

Если эти предварительные условия выполнены, простым решением является сохранение позиции файла (int64) каждого ключа (int64) в векторе в памяти. Для поиска просто извлеките позицию файла из вектора, seek в ту позицию, где вы найдете размер записи в качестве первой записи, и прочитайте size байт.

Answer 8

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

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

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