LINUX.ORG.RU

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


1

5

Сабж.

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

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

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

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

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

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

★★★★★

надо бы как то дампить/загружать дерево как есть

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

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

Могу предложить NoSQL.

В самом деле, «Как мне забить в стену гвоздь? Молоток не предлагать».

proud_anon ★★★★★ ()

Индекс иммутабельный после создания? Как насчёт мапнуть файл индекса в память?

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

Да, конечно. С-но после генерации файла для него генерируется индекс, и дальше его акутальность поддерживается сторонними средствами.

ЕМНИП std::map какой нить это аццкая вещь, и там даже непонятно чего мапать.

Видимо как варинта - индекс это обычный массив пар ключ:значение, отсортированный по ключам, и дальше mmap и дихотомия.

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

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

Оно универсально и страшно тупит на таких объемах.

В самом деле, «Как мне забить в стену гвоздь? Молоток не предлагать».

В этой аналогии СУБД не молоток, а паровой молот с ЧПУ перфоратором и андронным коллайдеров в придачу.

Я не исключаю, что со временем мы прикрутим СУБД к этой заадче, и тогда я буду задавать вопросы по СУБД. Пока что я хочу понять как это сделать БЕЗ СУБД.

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

Пока что я хочу понять как это сделать БЕЗ СУБД

Тут ничего особенного нет, ~

Получается два больших индекса, на диске их лучше представлять в виде отсортированных пар {ключ -> (файл, оффсет) } так, чтобы можно было применять бинарный поиск. Размер записи ~ 16 байт.

Дополнительно, чтобы не трогать весь индекс на диске при поиске, нужно построить индекс/дерево и кнему вида { ключ -> оффсет_в_индексе} до определённой глубины, чтобы он залез в память. Здесь размер записи может быть от 8 до 12 байт, забивать всю память им не стоит, нужно что-то оставлять под дисковый кеш.

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

Далее тоже просто - выборки (файл, оффсет) сортируются и превращаются в последовательную «прогоамму» для чтения с диска. Можно положиться на ОС отдавая одновременно N заданий на чтение, можно и самому химичить и пытаться близкие блоки с дырками вычитывать разом.

Возможны различные микро оптимизации если некоторые куски индексов читаются чаще других.

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

Ну и это всё применимо только до определённого объёма выборок выше которого будет дешевле читать все файлы последовательно без индексов. Оценить порог можно по условным IOPSам - обращение к дисковому индексу и одно чтение из файла данных 1 иопс, чтение 1 - 1.5 мб с диска тоже один иопс.

Примерно если кол-во уникальных ключей превышает 1млн для 1Tb данных, то становится дешевле тупо читать весь 1Tb последовательно.

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

Не, mmap это не std::map, это когда у тебя при обращении по определённому адресу в памяти ядро подсасывает тебе данные из файла на лету по мере того как ты к ним обращаешься: http://man7.org/linux/man-pages/man2/mmap.2.html

Оно так же умеет прозрачно кэшировать (page cache). Короче, имхо, хороший вариант когда тебе не хочется загружать файл в память целиком. Только могут быть с правами проблемы. Возможно, придётся поиграться с ulimit и sysctl. Короче, сначала запускай от рута пока не разберёшься.

true_admin ★★★★★ ()

Вот интересно, а журналирование/восстановление индекса после сбоев кто будет делать, теоретики хреновы?

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

Вместо этого сообщения мог бы просто написать кто это.

pedobear ()

Упрости задачу: взаимодействие (чтение) с большими объемами данных.

Наверное за полгода и более ?

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

обращение к дисковому индексу и одно чтение из файла данных 1 иопс, чтение 1 - 1.5 мб с диска тоже один иопс

А для SSD как нужно считать?

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

1 iops это чтение 4 килобайтного блока при длине очереди в 32

учи азы, студент

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

По аватарке судишь о кумирах? Ну ну

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

Зачем ты влез в хороших тех. тред со своим бесполезным флудом?

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

А для SSD как нужно считать?

Точно так же - узнаём скорость линейного чтения и кол-во IOPSов, из чего считаем стоимость иопса в байтах как BPS / IOPS. SSD очень разные встречаются, но порядок обычно около десятков кб.

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

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

Спасибо кэп. Разницу между std::map и mmap я знаю;-)

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

Спасибо. Насчет тэйловых индексов я не додумался;-)

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

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

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

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

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

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

mashina ★★★★★ ()

Параллельно, распределённо и в несколько строчек - http://spark.apache.org/docs/latest/quick-start.html

val textFile = sc.textFile("путь до твоей папки")
val index = textFile.map (строка => код преобразования строки в адекватные данные)
val filtered = index.filter (... правила фильтрации ...)

* могут быть проблемы, если запись занимает несколько строк. В этом случае Spark не подойдёт.

IPerm ()

А ключи не повторяются? Склей ключи в 128-битные представления, а значения - файл и оффсет. Запиши в файл и отобрази в память.

anonymous ()

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

а почему?

А то получается:

хочу чтоб мощный и ездил, что-бы с пушкой. Что-бы поворачивалась пушка. Что-бы на гусеницах. Что-бы бронированный. Что-бы ездил по степи/дороги и плавал(летать не нужно). Танк не предлагать!

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

Пока что я хочу понять как это сделать БЕЗ СУБД.

а никак.

Можно сделать свою СУБД. Иди читай Кнута про всякие красно-чёрные деревья. Это если в память влезает. Если не влезает, то лучше сильноветвящиеся деревья. Деревья — это если тебе нужны выборки _подряд_, к примеру ОТ и ДО. Если тебе просто key→value без сортировки и без последовательной выборки надо, то можно что-то замутить с хешами.

индекс это обычный массив

тогда у тебя время одной вставки будет O(N), а с деревом O(log(N)). Для списка время поиска O(N). Короче: только для дерева время поиска И вставки логарифмическое.

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

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

ну тут ты почти придумал сильноветвящееся дерево. Там получается как у тебя, только проще: «грубый индекс» автоматически занимает оперативную память, это верхние уровни дерева (корень на самом верху), они всегда «горячие», потому всегда в дисковом кеше. Просто нужно что-бы один узел индекса занимал 4К(или 2К или 1К) памяти, т.е. один блок типичной ФС (и типичной RAM).

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

Ну и это всё применимо только до определённого объёма выборок выше которого будет дешевле читать все файлы последовательно без индексов.

индекс всегда как минимум безвреден. Просто не нужно его сильно детализировать.

Примерно если кол-во уникальных ключей превышает 1млн для 1Tb данных, то становится дешевле тупо читать весь 1Tb последовательно.

таки вдвое дешевле хранить индекс из одного бита, тогда последовательно надо читать только ½Тб.

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

журналирование/восстановление индекса после сбоев кто будет делать

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

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

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

значит. А как ты вставку организуешь? Будешь гигабайты на диске двигать? Почему не прилепить новый узел где-то «сбоку», ведь память всё равно виртуальная.

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

А как все делают вставки пользуясь иммутабельными sstable? :)

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

А как все делают вставки пользуясь иммутабельными sstable? :)

Никак. Вот первый попавшийся пруф:

http://www.mezhov.com/2013/09/sstable-lsm-tree.html

Основное достоинство SSTable – в его простоте, однако у этого формата есть один недостаток. Как только SSTable оказывается на диске, он становится неэффективен в использовании. Поскольку SSTable хранит отсортированные сегменты данных, то любая операция вставки или удаления потребует больших накладных расходов из-за необходимости перезаписи всего файла. Таким образом, SSTable идеально подходит для хранения статических индексов, так как для чтения из индекса нужно всего лишь один раз позиционировать головку жесткого диска, после чего будет осуществлено последовательное чтение. Случайное чтение осуществляется также быстро.

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

emulek ()

sqlite делает то что тебе нужно, я считаю.

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

Преобразования (map, filter, ...) делаются построково, но распределённо и в случайном порядке. Если запись занимает две строки, то при обработке одной ты не сможешь сказать «дай мне следующую». Порядка нет (как кортежи в БД). Это просто не та парадигма.

IPerm ()

Если держать индекс на диске в виде обычного массива, то время загрузки будет довльно значительным, надо бы как то дампить/загружать дерево как есть?

что за бред несет этот поциент?

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

Если запись занимает две строки, то

Можно сделать свой ридер.

bj ()

Одна из задач

....

вынуть из файлов набор записей по некоторому критерию

что за поток сознания? запросы только по ключу? индекс не помещается в память? btree. когда устанешь свою велосипедить, возьми bdb

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

Лицоладонь. Я ж тебе сразу сказал что он иммутабельный. Но при этом sstable является базовым строительным блоком для множества СУБД. Как так? Угадаешь?

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

Лицоладонь. Я ж тебе сразу сказал что он иммутабельный. Но при этом sstable является базовым строительным блоком для множества СУБД. Как так? Угадаешь?

я не гадалка, твои мысли разгадывать. Так бы сразу и говорил «базовый строительный блок».

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

Разговор у нас начался с того, что мы обсуждали как делать вставку. Иммутабельные индексы на sstable, журналом, сбросом sstable с памяти и с периодическим merge - боян.

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

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

emulek ()

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

Собственно, единственный вариант это взять RDBMS. Если данных станет совсем дохрена, или уже - использовать partitioning.

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

Стандартная архитектура LevelDB, BigTable, Cassandra, HBase

1. Приходит запись a->b. Пишешь ее в двоичное дерево в памяти. Пишешь ее в журнал на диске. 2. Делаешь так для последующих записей. 3. Когда дерево разрослось сбрасываешь его на диск в виде SSTable. Только после готовности SSTable очищаешь дерево и удаляешь журнал. Заводишь новый журнал. Таким образом у нас есть набор SSTable, которые упорядочены по новизне. 4. В фоне работает поток, который читает пары SSTable и линейным прохождением по ним делает merge. После слияния удаляет пару SSTable источников. Merge для одинаковых данных может или удалять или сохранять все версии данных.

При удалении данные не удаляются, а просто в дерево записывается факт удаления, tombstone. При слиянии двух SSTable более новый tombstone затирает более старые данные. При слиянии с самой последней SSTable tombstone с данными исчезает.

Выполнение запроса по id происходит следующим образом.

1. Сначала происходит проверка значения в памяти. 2. Потом проверяются по очереди все SSTable бинарным поиском до достижения уровня одного блока. Там быстрее будет линейный поиск и возможна префикс-компрессия ключей. 3. При нахождении tombstone данные считаются удалеными, дальше проверять не нужно.

При выполнении сканирования сканируются итераторы по памяти и всем SSTable последовательно. При обеспечении O(1) snapshot для дерева памяти с файлами совсем просто, они иммутабельные и все легко может уйти в другой тред.

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