Контейнер произвольного доступа, который не помещается в памяти?

Question

У меня есть массив объектов (скажем, изображений), который слишком велик, чтобы поместиться в память (например, 40 ГБ). Но мой код должен иметь возможность произвольного доступа к этим объектам во время выполнения.

Каков наилучший способ сделать это?

С точки зрения моего кода, разумеется, не должно иметь значения, находятся ли некоторые данные на диске или временно хранятся в памяти; он должен иметь прозрачный доступ:

container.getObject(1242)->process();
container.getObject(479431)->process();

Но как мне реализовать этот контейнер? Должен ли он просто отправлять запросы в базу данных? Если так, какой из них будет лучшим вариантом? (Если база данных, то она должна быть бесплатной и не слишком хлопотной для администрирования, может быть, Berkeley DB или sqlite?)

Должен ли я сам это реализовать, запоминать объекты после того, как песок очищает память, когда она заполнена? Или для этого есть хорошие библиотеки (C ++)?

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

ОБНОВЛЕНИЕ: Оказывается, STXXL не работает для моей проблемы, потому что объекты, которые я храню в контейнере, имеют динамический размер, т.е. мой код может обновлять их (увеличивая или уменьшая размер некоторых объектов) во время выполнения. Но STXXL не может справиться с этим:

STXXL контейнеры предполагают, что данные Типы, которые они хранят, представляют собой простые старые данные типы (POD). http://algo2.iti.kit.edu/dementiev/stxxl/report/node8.html

Не могли бы вы прокомментировать другие решения? Как насчет использования базы данных? А какой?

Answer 1

Рассмотрите возможность использования STXXL :

Ядро STXXL является реализацией стандартной библиотеки шаблонов C ++ STL для внешней памяти (вне ядра) вычисления, то есть реализует STXXL контейнеры и алгоритмы, которые могут обрабатывать огромные объемы данных, которые только помещается на дисках. Пока совместимость к STL поддерживает простоту использования и совместимость с существующими приложения, еще один приоритет дизайна высокая производительность.

Answer 2

Я бы реализовал базовый кеш. При таком размере рабочего набора вы получите наилучшие результаты с набором ассоциативного кэша с x-байтовыми строками кэша (x ==, что лучше всего соответствует вашему шаблону доступа). Просто внедрите в программное обеспечение то, что каждый современный процессор уже имеет в аппаратном обеспечении. Это должно дать вам лучшие результаты. Вы могли бы оптимизировать его дальше, если бы вы могли оптимизировать шаблон доступа, чтобы он был как-то линейным.

Answer 3

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

Answer 4

Я видел очень умный код, который перегружает operator[]() для выполнения доступа к диску на лету и прозрачной загрузки необходимых данных с диска / базы данных.

Answer 5

Одним из решений является использование структуры, аналогичной B-дереву, индексам и «страницам» массивов или векторов. Концепция заключается в том, что индекс используется для определения того, какую страницу загружать в память для доступа к вашей переменной.

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