Стратегии записи расширяемых упорядоченных файлов на диск
Я аспирант ядерной физики, в настоящее время работаю над программой анализа данных. Данные состоят из миллиардов многомерных точек.
В любом случае я использую кривые заполнения пространства, чтобы отобразить несколько измерений в одно измерение, и я использую дерево B+ для индексации страниц данных. Каждая страница будет иметь некоторое постоянное максимальное количество точек в ней.
Когда я читаю необработанные данные (несколько сотен гигабайт) из исходных файлов, препроцессирую и индексирую их, мне нужно вставить отдельные точки в страницы. Очевидно, будет слишком много страниц, чтобы просто сохранить их в памяти и затем сбросить их на диск. Итак, мой вопрос заключается в следующем: какова хорошая стратегия записи страниц на диск, чтобы обеспечить минимальный объем перетасовок данных, когда страница достигает максимального размера и ее необходимо разделить.
Основываясь на комментариях, позвольте мне немного уменьшить это.
У меня есть файл, который будет содержать упорядоченные записи. Эти записи вставляются в файл, и их слишком много, чтобы просто сделать это в памяти и затем записать в файл. Какую стратегию следует использовать, чтобы минимизировать количество перестановок, необходимых при вставке записи.
Если это вообще имеет какой-то смысл, я был бы признателен за любые решения, которые вы могли бы иметь.
Редактировать:
Данные являются точками в многомерных пространствах. По сути списки целых чисел. Каждое из этих целых чисел составляет 2 байта, но каждое целое также имеет дополнительные 2 байта метаданных, связанных с ним. Таким образом, 4 байта на координату и где угодно между 3 и 20 координатами. Таким образом, данные состоят из миллиардов блоков, каждый из которых находится в диапазоне от 12 до 100 байтов. (очевидно, что точки с 4 измерениями будут расположены в другом файле, чем точки с 5 измерениями после их извлечения).
Я использую методы, подобные тем, которые обсуждались в этой статье: http://www.ddj.com/184410998
Редактировать 2: Я с сожалением задаю этот вопрос здесь, поэтому считаю, что он официально отменен; но вот моя причина не использовать готовые продукты. Мои данные - это точки в диапазоне от 3 до 22 измерений. Если вы рассматриваете каждую точку как просто список, вы можете думать о том, как я хочу запросить точки, как о всех числах, которые появились в тех же списках, что и эти числа. Ниже приведены некоторые примеры с низкой размерностью (и гораздо меньшим количеством точек данных, чем обычно). Пример: данные 237, 661, 511, 1021, 1047, 661, 237, 511, 237, 1021, 511, 661, 1047, 1021.
Queries:
511
1021
237, 661
1021, 1047
511, 237, 1047
Responses:
237, 661, 1021, 237, 1021, 661, 1047, 1021
237, 661, 511, 511, 237, 511, 661, 1047
511, 1021, 1047
511, 661
_
Так что это небольшая трудная проблема для большинства программ баз данных, хотя я знаю некоторые из существующих, которые могут справиться с этим хорошо.
Но проблема становится более сложной. Не все координаты одинаковы. Много раз мы просто работали с гамма-сферой отдельно, и поэтому каждая координата представляет энергию гамма-луча. Но в других случаях мы вставляем детекторы нейтронов в гамма-сферу или систему детекторов, называемую микроболом, или иногда нуклиды, образующиеся в гамма-сфере, направляются в масс-анализатор фрагментов, и все эти и более детекторные системы могут использоваться по отдельности или в любой комбинации с гамма-сферой. К сожалению, мы почти всегда хотим иметь возможность выбирать эти дополнительные данные способом, аналогичным описанному выше. Так что теперь координаты могут иметь разные значения, если в дополнение к гамма-сфере у вас есть только микробол, вы создаете n-мерное событие так же, как есть положительные решения уравнения x + y = n. Кроме того, с каждой координатой связаны метаданные. так что каждое из показанных мною чисел будет иметь по крайней мере 2 дополнительных числа, связанных с ними, первое - номер детектора для детектора, который уловил событие, второе - значение эффективности, чтобы описать, сколько раз этот конкретный гамма-луч рассчитывает (так как процент гамма-лучей, попадающих в детектор, которые фактически обнаружены, зависит от детектора и энергии).
Я искренне сомневаюсь, что любое готовое решение для базы данных может делать все эти вещи и работать хорошо одновременно без огромного количества настроек. Я считаю, что время, потраченное на это, лучше потратить на написание собственного, гораздо менее общего решения. Из-за потери общности мне не нужно реализовывать функцию удаления для какого-либо кода базы данных, мне не нужно создавать вторичные индексы для привязки к разным типам координат (только один набор, эффективно подсчитывая каждую точку только один раз), и т.п.
3 ответа
Я сам придумал ответ. Поскольку события вставляются в страницы, когда страница должна быть разделена, в конце файла создается новая страница. Половина событий исходной страницы перемещается на эту страницу. Это оставляет страницы не отсортированными, что несколько нарушает механизмы быстрого поиска.
Тем не менее, поскольку я пишу в БД только в один большой стартовый период (вероятно, длящийся несколько дней), я могу оправдать тратить немного дополнительного времени после написания, чтобы просмотреть страницы и отсортировать их после того, как они все были построены. Эта часть довольно проста на самом деле из-за природы деревьев B+, используемых для индексации страниц. Я просто начинаю с самого левого конечного узла дерева B+, читаю первую страницу и помещаю ее сначала в окончательный файл, затем читаю вторую страницу и помещаю ее второй, и так далее, и так далее.
Таким образом, в конце вставки все страницы будут отсортированы в их файлах, что позволяет эффективно и быстро работать при считывании данных с диска методами, которые я использую для сопоставления многомерных запросов с одномерными индексами.
Я считаю, что вы должны сначала посмотреть, что коммерческие и бесплатные базы данных могут предложить. Они предназначены для быстрого поиска по диапазону (при правильных индексах) и для эффективного управления памятью и чтения / записи страниц на диск.
В противном случае взгляните на один из вариантов деревьев двоичного разбиения пространства ( BSP).
Таким образом, первый аспект заключается в том, чтобы сделать это в многопоточном приложении, чтобы быстрее пройти через него. Разбейте свои куски данных на работающие разделы. Что заставляет меня думать...
Сначала я собирался предложить вам использовать Lucene... но, подумав об этом, это действительно похоже на то, что вы должны обработать с помощью Hadoop. Это было сделано для такого рода работы (при условии, что у вас есть инфраструктура для этого).
Я наверняка не буду делать это в базе данных.
Когда вы говорите об индексации данных и заполнении документов точками данных... и у вас нет инфраструктуры, ноу-хау или времени для реализации hadoop, вам следует вернуться к моей первоначальной мысли и использовать Lucene. Таким образом, вы можете индексировать свои данные и сохранять точки данных непосредственно в индексе (я бы подумал, по числовому диапазону) со структурой "документ" (объект), как вам кажется, лучше всего.