LINUX.ORG.RU

Индексация больших объемов данных


1

5

Сабж.

Есть некоторое кол-во бинарных файлов, каждый файл содержит некоторое кол-во записей. Каждая запись имеет заголовок длиной 32 байта + тело записи, длины записей разные, в заголовке в частности указана длина записи. Характерная длина записи 1Кб.

Общий объем данных сотни Гб, м.б. и неск Тб. Размер файла - ну какие то Гб (десятки Гб).

Каждую запись можно характеризовать четырьмя числами (float или int32_t). Одна из задач - за разумное время вынуть из файлов набор записей по некоторому критерию (скажем по набору 4рок чисел) и сложить кучкой в другой файл, при этом вынимать надо оптимальным образом (т.е. последовательно достать все нужные записи из одного файла, потом из другого и тд).

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

Вопрос - что лучше взять для этого? Индекс лежит на диске (в отдельном файле), в памяти его лучше держать в виде ассциативного массива. Если держать индекс на диске в виде обычного массива, то время загрузки будет довльно значительным, надо бы как то дампить/загружать дерево как есть?

Всякие реляционные СУБД не предлагать!

★★★★★

Последнее исправление: AIv (всего исправлений: 1)
Ответ на: комментарий от vertexua

У этой СУБД нету операции shutdown, ее можно просто завершать через SIGTERM или SIGKILL. При старте она всегда создает чистое дерево в памяти и в него воспроизводит последний оборваный журнал.

vertexua ★★★★★
()
Ответ на: комментарий от emulek

Можна просто использовать идеи частично. Но иммутабельность индекса решается наличием нескольких индексов с обновлениями

vertexua ★★★★★
()
Ответ на: комментарий от lovesan

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

anonymous
()
Ответ на: комментарий от emulek

вообще-то ФС должна этим заниматься. Ну и бекапы на случай аварии.

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

anonymous
()
Ответ на: комментарий от vertexua

давай начнём с онлайна. это значит, что тебе летит пара миллионов запросов в секунду, а индекс должен меняться под ногами.

anonymous
()
Ответ на: комментарий от anonymous

Вот он берет и пишется в память. Пишется пакетами в журнал. Потом сбрасывается на диск. Потом в фоне сливается вместе. Онлайн.

Ну и да, шардинг и все дела, пара миллионов же

vertexua ★★★★★
()
Ответ на: комментарий от vertexua

я и говорю — никаких проблем. лет 7-8 взад в яндексах трудно было коллег убедить что это так...

anonymous
()
Ответ на: комментарий от vertexua

Тише, тише горячие эстонские парни:-)

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

AIv ★★★★★
() автор топика
Ответ на: комментарий от AIv

поставь задачу корректно :)

иначе тебе или к кнуту за btree, или в bdb

до тех пор мы так и будем резвиться со своими никому не нужными большими задачами :)

anonymous
()
Ответ на: комментарий от vertexua

с моей колокольни, осталась одна недосказанность: иммутабельность индекса. раз уж ты задвинул тс-у за это — раскрой тему, быдь добр. а я послушаю.

anonymous
()
Ответ на: комментарий от anonymous

Иммутабельность одной таблицы. Она после создания не меняется. Потом пары сливают в одну, саму пару удаляют.

vertexua ★★★★★
()
Ответ на: комментарий от vertexua

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

anonymous
()
Ответ на: комментарий от anonymous

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

vertexua ★★★★★
()
Ответ на: комментарий от vertexua

объясни это тс-у. заодно напомни о подводных камнях чтобы не споткнулся.

anonymous
()
Ответ на: комментарий от anonymous

Для каждого файла свой индекс отсортированный по ключам + дихотомия.

С-но я могу и записи в файле по ключам отсортировать при построении индекса, тогда вообще все по шерсти получается.

У меня все данные иммутабельны (если я правильно понимаю этот термин) + приходится обрабатывать редкие но большие запросы. С-но поэтому я и не хочу СУБД, они наск я понимаю под другие задачи в первую очередь заточены.

AIv ★★★★★
() автор топика
Последнее исправление: AIv (всего исправлений: 1)
Ответ на: комментарий от anonymous

кому непонятно — пускай берут учебник в руки

кстати, безотносительно слияния, с ним более или менее понятно, а есть такой «учебник» по проектированию и запиливанию СУБД (что-то более low-level чем Гарсия-Молина)?

shty ★★★★★
()
Ответ на: комментарий от AIv

+ дихотомия

ты бредишь

У меня все данные иммутабельны (если я правильно понимаю этот термин)

этим широко пользуются поисковики, например. правильнее будет сказать, что у тебя есть неограниченное время на построение индекса.

редкие но большие запросы

подробнее. этот момент может оказаться существенным.

поэтому я и не хочу СУБД

если тупо ключ-значение — этот вопрос довольно хорошо исследован и лучше использовать готовое решение. если свои нюансы — есть простор для «творчества» :)

anonymous
()
Ответ на: комментарий от anonymous

имеется в виду поиск вообще (что-то около data mining) или именно реляционная модель?

не, конкретно здесь не data mining, и не реляционная модель (хотя, скорее всего, тут пофиг), интересуют книги по построению backend для хранения данных, то есть структуры для хранения данных, подходы и т.д.

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

собственно:
1) необходимо построить по ним индекс, на основе чего-то типа z-order curve, чтобы делать по ним пространственную выборку
2) данные версионированы по времени
3) может существовать несколько типов данных, которые привязаны к пространственным координатам, надо уметь их доставать совместно
4) есть куча метаданных, которые необходимо тоже засунуть в отдельный индекс(ы)

собственно что-то похожее уже как-то есть - это SciDb, но оно написано «норкоманами» и не совсем мне подходит

да, для решения этой задачи можно натянуть каракатицу на существующие решения (типа все данные в hbase по ключу, а индекс построить рядом и положить тоже куда-нибудь), но настоящие джедаи ездят на великах + мне интересно разобраться в теме + у меня есть 1-3 года на построение базового решения

да, есть hard-way - изучать сорцы, благо все есть в доступе, собственно план и был изначально такой, но если есть книга (кстати, не обязательно книга, может быть любой материал), которая бы базовые основы объясняла, мне бы это сэкономило кучу времени

shty ★★★★★
()
Последнее исправление: shty (всего исправлений: 1)
Ответ на: комментарий от shty

есть ещё дейт. недавно он придумал транс-реляционные бд (книга называется go faster, вроде).

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

то что находится за пределами реляционной модели называется big data. гугл довольно подробно описывает устройство своей big table. интел спонсирует исследования в этой области: http://istc-bigdata.org/

судя по тому, что ты упоминаешь многомерные данные (т.е. не имеющие полного порядка), тебе надо копать свою предметную область. придумали кучу индексов: для картинок — свои, для генетики — свои и т.д.

anonymous
()
Ответ на: комментарий от shty

Наск я понимаю, тут самое сложное определится с типовыми видами запросов. Вся остальная оптимизация строится уже исходя из этого, причем алгоритмов довольно немного - нужно их правильно скомпоновать:-)

AIv ★★★★★
() автор топика
Ответ на: комментарий от AIv

От того что ты путаешь названия алгоритмов алгоритмы не перестанут работать, а вот понимать тебя, когда ты попытаешься объяснить суть работы - вполне могут перестать.

maloi ★★★★★
()
Ответ на: комментарий от AIv

методом половинного деления, но КО считает, что ты пользовался бинарным поиском, а не методом половинного деления.

maloi ★★★★★
()
Ответ на: комментарий от maloi

Википедия вот грит что бисекция и есть метод половинного деления. И я открою вам дяденька страшшшшную тайну - бинарный поиск это тоже он.

А вот дихотомия это и правда немношко другое.

AIv ★★★★★
() автор топика
Ответ на: комментарий от AIv

Википедия вот грит что бисекция и есть метод половинного деления.

ну извините, дяденька, я образование не по википедии получал, хотя с этим я и не спорил.

И я открою вам дяденька страшшшшную тайну - бинарный поиск это тоже он.

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

maloi ★★★★★
()
Ответ на: комментарий от maloi

Вики грит: «Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.

Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.»

С-но есть еще поиск минимума ф-ии (который тоже кое-где зовут дихотомией), и он действительно чутка другой.

Так в чем же разница промеж методом деления пополам и бинарным поиском, поведуй мне о светоч разума?

AIv ★★★★★
() автор топика
Последнее исправление: AIv (всего исправлений: 2)
Ответ на: комментарий от maloi

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

Я прошу тебя рассказать мне, чем же они отличаются... и внезапно выясняется что ты бессилен O_O!

Можно ли отсюда сделать вывод, что бинарный поиск и метод деления пополам действительно одно и то же, а ты следовательно был неправ? Или на этот вопрос ты тоже бессилен ответить?

Ни капли глумления, мне правда очень интересно. ПРосветите же меня наконец, о Гуру!

AIv ★★★★★
() автор топика
Ответ на: комментарий от IPerm

спасибо, капитан. кто мешает считать самому в рдд подходящей формы?

anonymous
()
Ответ на: комментарий от AIv

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

maloi ★★★★★
()
Ответ на: комментарий от maloi

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

Но Вы дяденька мне не ответили. Я напомню - Вы утверждали что бинарный поиск и метод деления пополам вещи разные. В процитированном тексте написано что это одно и то же. На мой вопрос чем же они по Вашему отличаются, Вы издаете какое то невразумительное ла-ла... нехорошо. Как же так, неужели же Вы брехливое трепло O_O? Я прямо таки в шоке...

Я таки поясню - ошибаются все, это неизбежно. Но нормальный человек свои ошибки признает, а брехливое трепло сначала пушит хвост а потом уходит от ответа. Таки кто Вы есть в итоге?

AIv ★★★★★
() автор топика
Ответ на: комментарий от maloi

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

моя претензия (по поводу бреда) касалась не формы, а таки содержания. кто большие индексы в сортированные массивы складывает?

anonymous
()
Ответ на: комментарий от anonymous

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

кто большие индексы в сортированные массивы складывает?

Я не очень понял что есть «большой индекс», но в общем это отдельная софтинка. Не очень важно как она запускается, в итоге индекс акутален.

Есть такая феня - инертность мышления. Все почему то смотрят на эту задачу как на заадчу из области СУБД, хотя это та самая биг дата. У нее 1.5 пользователя, редкие запросы и т.д. Более того, до меня сення дошло что зная специфику задачи и повысив связность между модулями я всегда могу сваять специфический индекс с временем доступа О(1).

AIv ★★★★★
() автор топика
Ответ на: комментарий от AIv

если ты не в состоянии понять русский язык - так и напиши.

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

Мешает, т.к. в бинарном поиске предполагается что значения вектора упорядочены, а в бисекции - непрерывность функции (как ты вообще себе представляешь непрерывную функцию на конечном множестве?), а монотонность необязательна, и никакими формальными изменениями ты одно в другое не переведешь.

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

В процитированном тексте написано что это одно и то же.

Даже в процитированном тобой тексте написано, что одно - частный случай другого, если ты не в состоянии отличить когда одно множество является подмножеством другого, а когда они равны - я бессилен. Впрочем эту фразу (про частный случай) наверняка написал какой-нибудь неуч.

maloi ★★★★★
()
Ответ на: комментарий от maloi

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

Дяденька, вот тут Индексация больших объемов данных (комментарий)

Вы утвержали

даже твоя любимая википедия считает, что это разные вещи

Причем речь шла о различиях между БИНАРНЫМ ПОИСКОМ и МЕТОДОМ ПОЛОВИННОГО ДЕЛЕНИЯ.

Посколльку вот тут Индексация больших объемов данных (комментарий) Вы писали

методом половинного деления, но КО считает, что ты пользовался бинарным поиском, а не методом половинного деления.

Я начинаю подозревать у Вас дислексию. В последний раз повторяю вопрос - В ЧЕМ РАЗНИЦА МЕЖДУ МЕТОДОМ ПОЛОВИННОГО ДЕЛЕНИЯ И БИНАРНЫМ ПОИСКОМ?

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

AIv ★★★★★
() автор топика
Ответ на: комментарий от AIv

Если мне нужно найти все корни, то придется наложить на ф-ю дополнительное требование монтонности.

ЩИТО?

Дальше я вполне могу дополнить ф-ю на дискретном множестве до непрерывной любым способом (ман интерполяция)

можешь конечно

и получится в точности метод половинного деления.

не получится

Причем речь шла о различиях между БИНАРНЫМ ПОИСКОМ и МЕТОДОМ ПОЛОВИННОГО ДЕЛЕНИЯ.

я тебе в прошлом сообщении уже на этот вопрос ответил, если ты не способен понимать русский язык, то я могу попровать написать на английском, но сомневаюсь, что от этого что-то изменится.

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

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

maloi ★★★★★
()
Ответ на: комментарий от maloi

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

AIv ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.