Какой можно применить алгоритм для хранение индекса для 50 миллиардов записей в golang?

В результате работы программы получается около 50 миллиардов записей вида
<id string(60)> <source string(32)> <subid uint64>
и каждый день добавляются новые записи.

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

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

Может кто-то сможет подсказать название алгоритма или библиотеку на go или проект на go в котором реализованно что-то похожее. Требуется
1) Хранить индекс в нескольких файлах. Например у нас есть большой индекс и нужно добавить еще немного записей, перестройка индекса скорее всего трудный процесс, поэтому просто кладем рядом кусочек индекса и используем его тоже
2) Объединять индексы, те когда файлов уже много, можно пересобрать индекс
3) Удалять дубликаты/обновлять индекс . если приходит запись с уже существующим id + source то использовать последние данные.

У нас 50 миллиардов записей и они прибывают, по 200-300к каждый день.
  • Вопрос задан
  • 571 просмотр
Пригласить эксперта
Ответы на вопрос 6
mayton2019
@mayton2019
Bigdata Engineer
Немного бухгалтерии. Если взять по максимуму.

Размер одной записи должен быть порядка 60 + 32 +8 = 100 символов (байт для простоты)

При 50 млрд записей объем хранимых данных должен быть порядка

50 000 000 000 * 100 = 5 000 000 000 000 = 5 триллионов байт.

В дисковом хранении это будет примерно 4.5 терабайта. Задачка для in-memory неподъемная. Нужен диск + мемори.

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

Вобщем нужна дисковая БД которая встраивается в приложение. На требование менеджеров которые запретили использовать БД забейте. Они ничего не понимают. Делайте БД встраиваемую в приложение. В качестве таких (встраиваемых систем можно поробовать) LevelDb, BerkeleyDb, RocksDb. Они поддерживают индекс класса B+Tree и это даст возможность искать группы записей по одному ID. Для этого класса систем любую запись можно найти за 4-5 дисковых IOPS. Если какдый IOPS стоит 15 мс (это я так мерял свой собственный магнитный HDD) то любой поиск группы ключей для TTFB будет порядка 15 * 5 = 75 милисекунд. Ну если вы поставите SSD - то быстрее.

По поводу предложений хранить в файлах. До того как обсуждать это - надо уяснить требования по времени отклика. Сколько секунд вы согласны ждать - насколько можно и партицировать (или шардировать ваш файл).
В простейшем случае мы делим большой CSV файл на 512 partitions по хешу от ID и получаем соотв время фулл-скана всего файла поделенное на 512. Дальше - играйтесь с этим параметром партишенинга выводя его на доступный уровень отклика. Из недостатков - будет россыпь файлов. Надо почиать документацию на вашу файловую систему (ext4?) и тюнить ее так чтоб она не сдохла от такого числа inodes.

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

По поводу Parquet. Не взлетит. Скорее всего индекс по данному типу файла - это совсем не то что вкладывают туда релационные системы. Обычно Parquet/Orc/Delta вкладывают в индекс смысл - отбрасывания тех полосок данных (stripes) которые бесполезны при чтении всего файла. Такой индес - обычно просто либо range-признак либо карта Блума. И в случае с range - дает эффект на сортированных данных. Для прочих - будет бесполезно т.к. фулл-скан все равно обеспечен. А если фулл-скан то зачем тогда вообще индекс.

Вобщем для дизайна архитектуры нам нужны цифры. Средние длины по колонкам. И я-бы еще запросил кардинальность по полю ID.
Ответ написан
Apache Parquet вполне может подойти, т.к. это формат хранения, а не движок. Есть реализации на Го. Хранить можно на любом подходящем хранилище. Индексы колонок тоже поддерживаются.
Ответ написан
Комментировать
gzhegow
@gzhegow
aka "ОбнимиБизнесмена"
Такой спор с мозговыносящими технологиями, аж помутнело всё.

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

Простейший способ - взять пару букв того, пару букв этого и этого, слепить вместе. Получится группа. Группу (все записи разделенные переносом строки) положить в файл с именем "(парубукв_source)(парубукв_id)(парубукв_subid).txt". На сами группы запомнить по принципу "группа такая - знач файл такой". В вышеуказанном случае имя файла именно это и делает.

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

И да, нет смысла делать индекс на 60 букв, потому что айдишник уникален. Получится 50 миллиардов записей и из них 50 миллиардов групп. Это не имеет смысла. Смысл в том чтобы 50 миллиардов оказались в 10 тысячах групп, и при поиске пришлось просмотреть не 50 миллиардов, а пару групп. Учитывая что ты работаешь с айдишниками, то скорее всего ты будешь вязать одну запись, то есть группа вообще будет одна.

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

"Переиндексирование" - по одной или всё вместе. По одной - находим в группах, удаляем из групп. Все вместе - создаем соседнюю папку для index_2, делаем, удаляем старую папку, переименовываем новую на место старой. Так даже в elastic делается, там "переиндексирование" - это создание нового индекса и снос старого.

Чем более твои айдишники уникальны, тем сложнее это группировать, тем меньше смысла от индекса. Возвращаемся к самой задаче. 200 тысяч в день записей появляется. Это какая машина в день сама столько делает? Если машин несколько, то машина (её номер) - тоже группа, уменьшит уже на порядок, но скорее всего нет, т.к. в условии поиска номер машины не будет важен. Если одна машина всё это делает, можно критерий какой-то добавить, а хоть бы "день когда добавилось", или "тип записи" (это всё имеет смысл, если данные все настолько уникальные, что прям их никак не сгруппировать). Если критерий не добавить вообще никак - знач как описал ранее - лепи пару букв из тех полей, по которым будешь искать.

ps. есть вероятность, что "не используйте базу данных" имеется в виду "code first" - напишите на объектах, чтобы мы потом сами бд выбрали, а не сделайте "без бд".
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
vgray, Удаляются ли записи?

Так-то, поиск на полное совпадение по строке не самое сложное. Какое-нибудь B-Tree или Trie - отлично подойдут тут. Проблема только в том, что оно в память не влезает, поэтому придется повозиться с хранением этого всего кусками в файлах. B-Tree как раз для этого и сделано, но оно будет медленнее работать со строками. Аккуратно порезанный на куски Trie будет быстрее.
Ответ написан
Комментировать
dollar
@dollar
Делай добро и бросай его в воду.
Можно индексировать индекс. А именно, хранить, например, в 10 файлах: в первом все id % 10 == 1, во втором id % 10 == 2 и т.д. Если id - строки, то по первой букве, например. По сути это хеширование. Если потом перестраивать, то не всё и сразу, а тоже по 10% от всего индекса за раз. Это как пример.
Ответ написан
dimonchik2013
@dimonchik2013
non progredi est regredi
reindexer

он завязан на inmemory, но на Го, возможно, алгоритмы подойдут
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы