Идеальная база данных для хранения большого числа уникальных строк?

Question

[Михаил Юрьевич]

Продолжая развивать наш проект https://spyserp.com/ru/ появилась интересная задача

Входные данные:
- 150 млн уникальных строк длинной от 1 до 2048 символов(в данном примере ссылки, но могут быть любые бинарные строки)
- ежедневный прирост по 1 млн, ожидаемый прирост в диапозоне 5-10 млрд
- сейчас хранится в PostgreSQL, в формате id(primary key), link bytea(btree index), занимает 22 гб и индекс 32 гб

Задача:
- подобрать более оптимальное хранилище, уменьшить физический размер индекса, улучшить производительность

Из требований к новой базе:
- желательно максимальное заточенное и оптимизированное хранилище под такой тип данных(уникальная строка + ее id)
- быстрый поиск как по ключу(ссылке) так и получение ссылки по ее id
- возможность горизонтального масштабирования
- дисковое хранилище(понятно что для наилучшей производительности лучше все положить в память, но на данный момент этот вариант не рассматривается)

Из того что пробовалось:
- все key/value хранилища(leveldb, rocksdb и т.д.) - нет поиска по value(в данном случае key - ссылка, value это id)
- был активный период гугления, но к сожалению подходящего решения так и не было найдено

Обсудим? Очень хочется услышать мнение тех кто сталкивался с подобной задачей и как ее решали

Comments

[Eugene Khrustalev]

Зачем вводить суррогатный ключ id, если ссылки уникальные?

[Михаил Юрьевич]

Eugene Khrustalev: для хранения id ссылки в других местах

Answer 1

[lega]

1) Используйте хеш от ссылки в качестве ид, тогда индекс по ссылке не нужен будет
2) Вместо btree возьмите hash индекс, вам же там сортировка не нужна
3) Данные переменной длинны не эффективно хранить в таблицах, т.к. оно там дробится и частично резервируется, итого занимает больше и работает медленнее.

Comments

[Михаил Юрьевич]

1) хеш от ссылки не даст уникальный id, есть требование чтобы id был bigint(8 байт)
2) попробуем, спасибо
3) хорошо, но где тогда эффективно?

[nirvimel]

Forbidden: Если вы боитесь коллизий при использовании стандартных (оптимизированных для быстродействия) хеш-функций, то возьмите какую-нибудь криптографическую (SHA, MD5, и.т.д.), они дают больше, чем bigint.

[nirvimel]

lega:

3) Данные переменной длинны не эффективно хранить в таблицах, т.к. оно там дробится и частично резервируется, итого занимает больше и работает медленнее.

Документация PostgreSQL говорит об обратном:

Tip: There is no performance difference among these three types, apart from increased storage space when using the blank-padded type, and a few extra CPU cycles to check the length when storing into a length-constrained column. While character(n) has performance advantages in some other database systems, there is no such advantage in PostgreSQL; in fact character(n) is usually the slowest of the three because of its additional storage costs. In most situations text or character varying should be used instead.

[lega]

nirvimel: Наоборот подтверждает - "While character(n) has performance advantages", и ещё говорит что все 3 типа тормозные в постгресе.

1) Если берете фиксированную колонку - то лишний расход памяти и производительности (because of its additional storage costs)
2) Если берете плавающую - то данные дробятся, заголовки в одном месте + часть данных (в некоторых БД), остальная часть хранится в другом месте, итого тормоза из-за того что бегать в разные места (io).

Нужен чанковый подход как в MongoDB без 1 и 2-й проблемы, но не такую прожорливую как MongoDB.

[lega]

Forbidden: Можно поэксперементировать: levelDB, ключ - link, а id - это физический адрес строки в файле, итого есть поиск по link и id, id - числовой.

[Михаил Юрьевич]

nirvimel: тут не стоит вопрос боязни коллизий, они должны быть исключены, а на 8 байт для id коллизий будет много, и без разницы какая hash функция используется

lega: а каким образом можно получить адрес строки в файле? в стандартных обертках для php/perl/nodejs я не видел такого функционала, и не будет ли адрес строки в файле меняться для старых данных при добавлении новых?

[nirvimel]

Forbidden: Для 16 миллиардов строк (2^34) вероятность одной коллизии в 64-битном пространстве значений примерно равна 1 / 2^(64 - 34) = 1 / 1073741824. Это намного меньше, чем вероятность того, что третья мировая война начнется сегодня ночью.

[lega]

Forbidden: И это ключевые вопросы на данном пути, если вы по нему пойдете.
Большие компании не редко пилят (допиливают) что-то свое чтобы получить максимум.

Кстати коллизии же можно обруливать, есть несколько способов, например если X и Y дают один хеш 15,
то первый записанный X забирает 15, при записи Y видим, что 15 занято другим текстом, и берем следующий свободный 16 или 17, это запись.
Поиск по ид будет как есть, а поиск по тексту так же как и запись: делаем хеш (ид) от текста, если текст по ид не совпал проверяем следующее значение, если совпало - значит оно, если нет - берем следующее, если следующей записи нет - значит такого текста в базе нет совсем.
Как написал nirvimel при int64 будет немного таких случаев.

[Михаил Юрьевич]

nirvimel lega: спасибо, интересные цифры выходят, и подход, посмотрю в эту сторону

[numfin]

в сторону https://cloud.google.com/products/big-data/ никто не смотрел?

Answer 2

[LORiO]

clickhouse от яндекса. И с url база хорошо работает, так как изначально для метрики разрабатывалась.

Comments

[Михаил Юрьевич]

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

[lega]

Forbidden: Скорее пальцем в небо.

[LORiO]

Forbidden: мы используем её для хранения сообщений из соц сетей и последующего анализа.
Как раз с PostgreSQL перешли.

Answer 3

[Eugene Khrustalev]

CouchDB

Comments

[Yustas Alexu]

Вы шутите? CouchDB как раз таки славится обжорством по отношению к занимаемому месту на диске.

[Yustas Alexu]

ожидаемый прирост в диапозоне 5-10 млрд

stackoverflow.com/questions/3498856/couchdb-view-f...

[d'Ivan]

Yustas Alexu: за 7 лет могло много чего поменяться

Answer 4

[xfg]

Можете посмотреть еще https://ru.wikipedia.org/wiki/HBase

Answer 5

[#]

посмотрите это https://habrahabr.ru/company/yandex/blog/303282/

Answer 6

[Philipp]

Храните в MongoDB в виде документа:
{_id: 'http://your/url'}

Comments

[gaxetasok]

Неэффективно

[Philipp]

gaxetasok: можете пояснить, почему?

[Михаил Юрьевич]

монго довольно компактно хранит, но загнулась после 100 млн

[Philipp]

Forbidden: как это выглядело?
У меня есть коллекции подобных масштабов, но данные хранятся нормально.
Просто интересно узнать, что произошло? И какое у вас было хранилище и как версия движка?

[Михаил Юрьевич]

Philipp: последня stable 3.4, wiredtiger, вставка деградировала с 20 секунд до 1000+ сек на 1 млн записей после 100млн

[lega]

Forbidden: Монга в первую очередь упирается в io.
Если индекс один, то на 100млн, нужно ~5Гб оперативы, то есть возможно у вас кончилась память и все начало писаться в своп, а оно будет сильно тормозить, так же и с другими БД.

Интересно сколько был оверхед?, например на 10Гб данных может использоваться 12-50Гб диска.

[Philipp]

Forbidden: а какое у вас железо? Используете ли шардинг?

У меня примерно 64 Gb RAM, Data Size ~ 1.2 TB. Диск SSD. Обычная реплика.
Самые тяжелые аггрегации считает в пределах 200мс.

Нагрузка выглядит так:
Т.е. очень смешанная

Правда записи пачкой в миллион я не вставляю, считаю это не самой разумной практикой. Т.к. это NoSQL, то в ней все, что нельзя записать сразу, кладется в очередь. Это помогает эффективно обрабатывать вслески нагрузки. Но это имеет и обратную сторону - при переполнении очереди в памяти, база начинает свопить и без того уже загруженный сервер начинает уходить в отказ.
Если MySQL выдает что-нибудь вроде "Server gone", то Mongo держится до последнего. Обычно в реплике это заканчивается выборами, т.к. если праймари не отвечает в течение 15 секунд, то арбитер запускает голосование.

[Андрей Токмаков]

Forbidden: На сколько помнится гугл сидит на монго и не загибается же, а у Вас на 100млн сдох, как так!?

[Михаил Юрьевич]

Андрей Токмаков: гугл на монго? не шутите так :)

[Андрей Токмаков]

Forbidden: Пардоньте, перепутал с MariaDB не проснувшись :)

Answer 7

[Сергей]

Если у вас ссылки, то вы можете очень хорошо их сжимать
используя поиск по префиксу. Т.е. ищите максимальную строку, которую можно адресовать и заменяете всю строку (префикс) на ИД. Т.о. вы можете съэкономить значительные ресурсы.

Comments

[Михаил Юрьевич]

а есть ли готовые библиотеки, с возможностью натренировать "словарь" и в дальнейшем его использовать?

[lega]

Размен диска на пямять и проц.
Диск экономится, но расход на оперативу и проц растут.
Нужно будет 2 индекса, поиск по строке с сортировкой - для подбора подстроки.

[Сергей]

Ну тут палка о двух концах. Больше в память помещается -- быстрее поиск. В большинстве БД узкое место это диск.

[Сергей]

Forbidden: в данном случае LZW какой-нить. Но проще по префиксам работать, т.к. по сути это и есть LZW-алгоритм. Т.е. вы сами делаете словарь и его же на диск сохраняете.

Answer 8

[dummyman]

Я раньше очень часто пользовался базой Пастухова.
Теперь мне хватает ключевиков, собранных собственным трудом.
Но принцип хранения не поменялся - текстовый файл рулит!
Позже прикрутил индексы на первые 6 байт в каждой строке и на первые 2 байта в каждом слове (кодировка cp1251).
Короче, удобно хранить, копировать, использовать на разных компьютерах запуская прямо с флешки, максимальная скорость работы!