Как хранить и искать в 10 миллиардах записей?

Question

[Андрей]

Есть 500 миллиардов записей, каждая запись это немного чисел и немного текста.
Это все поделено на N количество частей по примерно 10 миллиардов.

На данный момент 10 миллиардов хранятся в одном файле (около 5 Тб). К этому файлу есть несколько индексов, бинарные файлы (ключ -> офсет в файле с данными), отсортированные по ключу, поэтому поиск получатся довольно простой.

Главная проблема в том что часто приходят новые данные, N миллионов в день, и при добавлении в файл индекса этих записей файл индекса приходиться весь переписывать а это около 500 гб. И так каждый индекс а их несколько на каждую часть. Это получается долго.

Как обычно решают такие проблемы? Как хранить больше индексы? Может есть какая то дб способная вмещать себя столько с с несколькими индексами и сортировками.

Answer 1

[amarao]

Умный ответ в стиле «отстаньте» — hadoop.

Если же думать как решить — если проблем с производительностью нет и 5Тб одним файлом устраивает, то надо просто использовать деревья для хранения индекса и обновлять индексы только на порцию пришедших данных.

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

Это решение «на коленке», если что-то крутое — смотрите в сторону специализированных баз данных.

Answer 2

[darkdimius]

Для подобных задач иногда подходит такая идея: разделить базу на части(пакеты), и запросы к ним делать независимо, и потом объединять результаты
Например — отдельно хранить данные за последние дни с воскресения по пакету на один день, раз в 7 дней объединяя всю базу в один пакет.

Если нужен поиск по ключу — обращаться к пакетам в порядке возрастания «возраста» базы.
Если нужны отсортированные данные — то после поиска нужно данные «слить» с перекрыванием более старых записей новыми.

Более умная стратегия — объединять пакеты по степенному закону. Те пакеты бывают только на 2^i дней.

Answer 3

[pav]

Посмотрите в сторону LucidWorks Big Data. Сам я правда с ней не работал, но с LucidWorks Search работаю и пока проблем нет (~15гб, 10кк документов).

Answer 4

[relgames]

Я думаю, стоит попробовать Cassandra. Она умеет не только очень быстро искать по первичному ключу, но и по вторичному www.datastax.com/docs/1.0/ddl/indexes