Запись больших сводок данных на диск - PullRequest
2 голосов
/ 13 июня 2011

У меня есть большой набор данных, из которого я получаю иерархический набор сводок на разных уровнях грубости. Я хочу кэшировать эти сводки в файле на диске, причем каждая сводка может быть извлечена из файла через его смещение. Первоначальная сводка получается путем взятия небольших фрагментов (около 256 байт) из исходного набора данных и извлечения максимального значения из каждого фрагмента. Последующие сводки затем выводятся путем взятия максимума каждой пары значений в предыдущей сводке. Будем надеяться, что следующая (элементарная) иллюстрация прояснит:

251 18 5 91  11 17 54 16  9 31 201 148  173 214 66 43   ;;Initial data-set (chunked)

    251           54          201            214        ;;Summary 0

           251                        214               ;;Summary 1

                         251                            ;;Summary 2

То, что я пытаюсь реализовать, - это средство извлечения (а затем и кэширования) этих сводок, которое масштабируется до больших наборов данных, например порядка 4 ГБ. Скорость не является особой проблемой, но пространство таково: потому что для наборов данных такого размера даже сводки могут быть слишком большими для обработки в памяти. Я экспериментировал с несколькими подходами:

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

  2. Рассчитать каждый слой в чанках - вычислить чанк первого слоя, затем второго слоя, затем третьего и т. Д., Наконец, записав чанки в файл с соответствующими смещениями и перезапустив процесс. Проблема в том, что, поскольку каждый кусок будет в два раза меньше фрагмента, из которого он рассчитывается, мы получим размер фрагмента 0 до того, как будут рассчитаны все слои.

  3. Используйте один файл для каждой сводки.

  4. Используйте какой-то подход, основанный на деревьях (приведенная выше иллюстрация - если включить ее голову - напоминает кучу). Возможно, каждый узел в дереве может представлять, скажем, кусок 1024 байта в каждом слое. Родительский узел будет иметь двух дочерних элементов, представляющих последовательные чанки в предыдущем слое, и его содержимое будет рассчитываться из этих дочерних элементов Как только это будет сделано, дочерние узлы могут быть просто записаны на диск. Я подозреваю, что этот процесс может быть выполнен полностью в памяти (хотя я не знаю, в чем его сложность).

Мысли / наблюдения приветствуются.

Christopher

1 Ответ

1 голос
/ 25 июня 2011

ОК, поэтому после небольшого исследования я в конечном итоге выбрал B-Tree с несколькими верхними уровнями, кэшированными в основной памяти.Работает сейчас.

Крис

...