Какой можно применить алгоритм для хранение индекса для 50 миллиардов записей в golang?
В результате работы программы получается около 50 миллиардов записей вида <id string(60)> <source string(32)> <subid uint64>
и каждый день добавляются новые записи.
нужно по id получить все записи. те типичная задача для кассанды или сциллы, но проблема в том, что нам запретили использовать внешние бд, я не знаю почему, но такое требование.
Я с индексами особо не сталкивался, пока не знаю с чего приступить, гугление пока особых результатов не принесло.
Может кто-то сможет подсказать название алгоритма или библиотеку на go или проект на go в котором реализованно что-то похожее. Требуется
1) Хранить индекс в нескольких файлах. Например у нас есть большой индекс и нужно добавить еще немного записей, перестройка индекса скорее всего трудный процесс, поэтому просто кладем рядом кусочек индекса и используем его тоже
2) Объединять индексы, те когда файлов уже много, можно пересобрать индекс
3) Удалять дубликаты/обновлять индекс . если приходит запись с уже существующим id + source то использовать последние данные.
У нас 50 миллиардов записей и они прибывают, по 200-300к каждый день.
Во-первых, из чего у вас состоят айдишки и стоит ли их хранить в стрингах? Это просто довольно расточительно по памяти.
Во-вторых, не использовать внешние базы данных это дичь. Вы соберете все грабли, на которые создатели баз данных наступали на протяжении многих лет разработки.
В-третьих, если реально другого выбора нет, используйте btree, оно хорошо ложится на файловую систему и само балансируется при добавлении записей. Только вам полюбому его нужно шардировать по какому-то признаку, потому что 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.
Dimonchik, Хороший вопрос. Я спецом поискал характеристики рандомного времени доступа. К сожалению маркетинг завалаен не теми цифрами. Большинстов рекламных листов NVME / M2 показывают пропускную способность канала. А это не то. Нас интересует именно время ожидания доступа с случайному блоку. Обычно оно хуже чем пропускная способность. Вот кое что нашел. По состоянию на 2018 год.
IOPS (Read) = 540k IOPS
IOPS (Write) = 50k IOPS
Перевернем величину в секунды.
String.format("%4.7f", 1.0 / 540000.0)
0.0000019 s = 2 mks
Оперативная память - это доступ порядка НАНО-секунд. А твердотельник - порядка микро-секунд. Грубо говоря на 4 порядка. Быстрее чем магнитный диск. Но при этом запись и чтение магнитного диска практически не отличаются. А твердотельник пишет в 10 раз медленее чем читает.
iops зависят от пропускной - чем больше велечина даных, тем меньше iops - это везде, в том числе на бенчмарк простейших
у ТС же данные невелики, так что iops будет
подход Aerospike тому подтверждение, уже 10 лет как, если не 15-20: индекс в памяти, данные на ssd (ну в данном случае nvme)
впрочем, теребайт памяти тоже не так уж дорого, если цель того стоит (хз что, на крипту похоже вроде)
другое дело что врял ли без несольких серверов/кластера получится
Dimonchik, ммм не согласен насчет IOPS и пропускной способности. Это сильно большое упрощение.
А по поводу LSM-tree (дерева которе разделено на 2 сегмента) - это как раз по адресу к RocksDB. Берем RocksDb - значит эта фича уже включена в комплекте.
И меня смущает наличие ненужных для автора фичей таких как distributed, shared-nothing e.t.c. Ему это пока не надо. С настройками только заморачиваться.
До того как обсуждать это - надо уяснить требования по времени отклика. Сколько секунд вы согласны ждать - насколько можно и партицировать (или шардировать ваш файл).
У нас до максимум 500 запросов в день будет, можем ждать хоть 10 минут, те основная цель вопроса - это найти решение, куда можно спихнуть эти индексы за дешево (имеется в виду, дешево с точки зрения программирования и дальнейшей поддержки) и работать дальше :)
Средние длины по колонкам. И я-бы еще запросил кардинальность по полю ID.
Средние длины
id - 20 байт
source - всегда 32 байта (это md5 от имени источника), можем в 16 переделать.
subid - 8 байт
кардинальность id, на глаз где-то в диапазоне 10-20 записей (источников) на каждый id
scala> 50_000_000_000L * (20 + 32 + 8) / 1024 / 1024 / 1024
val res7: Long = 2793
Чуть менше трех терабайт.
У нас до максимум 500 запросов в день будет, можем ждать хоть 10 минут, те основная цель вопроса - это найти решение, куда можно спихнуть эти индексы за дешево (имеется в виду, дешево с точки зрения программирования и дальнейшей поддержки) и работать дальше :)
Это хорошо. Тут кстати есть хитрость. Если вы ждете 10 минут - то оптимальная стратегия - не искать сразу а накапливать 3-5 поисковых ID и искать сразу пачку. Логика такая. Лучше подождать 15 минут и найти 3 штуки сразу чем ждать 30 минут = 10 + 10 + 10 и находить по одной штуке. Full-table-scan - дорогая операция. Вот амазон сервисы даже отдельно считают фулл-сканы по другому тарифу.
Я не специалист в Go и не могу написать никакого прототипа. Но идею я уже озвучил. Дробите на части по хешу от ID и будет быстрый поиск. Можно даже CSV поскольку вам безразлично.
Apache Parquet вполне может подойти, т.к. это формат хранения, а не движок. Есть реализации на Го. Хранить можно на любом подходящем хранилище. Индексы колонок тоже поддерживаются.
Так-то, поиск на полное совпадение по строке не самое сложное. Какое-нибудь B-Tree или Trie - отлично подойдут тут. Проблема только в том, что оно в память не влезает, поэтому придется повозиться с хранением этого всего кусками в файлах. B-Tree как раз для этого и сделано, но оно будет медленнее работать со строками. Аккуратно порезанный на куски Trie будет быстрее.
Можно индексировать индекс. А именно, хранить, например, в 10 файлах: в первом все id % 10 == 1, во втором id % 10 == 2 и т.д. Если id - строки, то по первой букве, например. По сути это хеширование. Если потом перестраивать, то не всё и сразу, а тоже по 10% от всего индекса за раз. Это как пример.
понятно, что можно изобретать самому :) но просто там 50 миллиардов записей, не хочется во все это вникать. Как минимум индекс нужно сортировать (данные приходят в разнобой) и т.д. Если бы не это требования, то взялибы кликхаус (его скрость работы тут устраивает) и все.
vgray, есть популярные алгоритмы, заточенные на довольно простые случаи, зачастую на общие случаи. Возьмём к примеру, алгоритм сортировки. За какое там время лучший из них справится? За N*log(N), не так ли? Но что если у вас миллиард чисел, каждое из которых от 0 до 255? Тогда уже можно уложиться за O(N) внезапно! А всё потому, что появились дополнительные условия.
У вас довольно специфичные условия, причем их много - количество записей, формат индекса, различные ограничения данных, требования могут быть как к скорости добавления, так и к скорости поиска, а также к объему используемой оперативки, не всегда нужно всё и сразу. И с учётом пересечения всех этих условий вам подойдёт какой-то особый алгоритм, но да, придётся самому "изобретать". А потом ещё и тестировать придётся, чтобы подтюнить его или выбрать из двух разных несовместимых хороших идей.
