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

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

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

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

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

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

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

Что за злорадный чувак на аватаре?

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

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

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

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

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

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

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

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

Не в этом треде обсудим

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

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

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

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

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

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

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

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

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

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

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

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

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

Андрей Дещица

Странные кумиры у тебя.

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

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

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

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

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

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

Тебя в гугле забанили, болезный?

http://goo.gl/bXwRhv

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

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

никто не замечает твоих?

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

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

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

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

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

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

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

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

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

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

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

шта? почему это не подойдет?

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

solr /thread

http://lucene.apache.org/solr/

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

а почему?

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

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

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

а никак.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Одна из задач

....

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

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

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

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

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

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

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

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

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

Стандартная архитектура 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 для дерева памяти с файлами совсем просто, они иммутабельные и все легко может уйти в другой тред.