В чем можно хранить около триллиона значений key=>value?

Question

[v_k]

Собственно, вопрос. Длина ключа - 8 симовлов [a-z-A-Z0-9], длина значения 64 символа [a-f0-9].
В чем можно создать такую базу, чтобы быстро поместить в нее все значения и потом быстро извлекать данные по нужному ключу?

Comments

[v_k]

В оперативной памяти такое не сохранишь - денег никаких не хватит.

[v_k]

Dr. Bacon, хранение пароля и его хеша

[v_k]

Yokaze, слишком медленно вставляются данные, т.е. заполняется таблица

[v_k]

Dr. Bacon, решил с того, что у меня такое ТЗ, а как реализовать его - вот главный вопрос.

[v_k]

Yokaze, сервер амазоновский 32vcpu, тип носителя - SSD.

[v_k]

Dr. Bacon, ту то базу я реализовал на Postgres, пришло время новой базы и хотелось бы ее сделать побыстрее.

[v_k]

Dr. Bacon, угу, скорее всего, так и буду делать, только все равно остается открытым вопрос - на какой БД это реализовать пока не зашло все слищком далеко.

[Сергей Соколов]

Триллион записей 1e12 vs 8-значный ключ a-zA-Z0-9 = 26+26+10 = 62
62^8 / 1e12 ~= 218.34
Уникальных вариантов ключа всего лишь в 218 раз больше, чем ожидается записей.
Рассматривали варианты коллизий? Что на один ключ («пароль») может претендовать несколько разных значений.

Точно ли нет однозначного способа вычислительно получать длинное значение из короткого «пароля» ?

[v_k]

Сергей Соколов, да, при коллизии данные будут обновлены

Answer 1

[mayton2019]

Давайте прикинем объем который понадобится. Что такое триллион?
Это 12 нулей. Или 1 000 000 000 000 элементов. Какая у нас data-row?
8 + 64 символов типа ASCII (байт подходит чтоб покрыть все символы).
Итого 72 байта на строку. Там можно еще поужимать биты в байтах но только
сложность повышает а большой пользы для дела не дает. Пускай будет ASCII == 1 байт.

Вобщем такой расчет

72000000000000 байтов на весь сегмент данных когда таблица загружена.
Или 65 терабайт. А сколько магнитных блинов надо прикупить? Возьмем популярный магнитный
Western Digital Purple 10TB 7200rpm 256MB WD102PURZ 3.5" SATA III при цене 290$
Порядка 7 штук надо. Вобщем готовте котлету денег 290$ * 7 = 2030$

По поводу DBMS. Да key-value здесь подходит. Можно начинать с LevelDb или RocksDb но у них
расход дисковой памяти на 1 строчку может быть больше чем я посчитал. Я ведь считал эконом-эконом
вариант в виде бинарного типизированного файла где все записи строго по 72 байта. Сколько именно
захватит РоксДб или ЛевлДб - чорт его знает. Вряд-ли документация об этом что-то говорит.
Но берите 1% датасета. Загружайте
и аппроксимируйте сколько выйдет после полной прогрузкуи. Это - надежный способ оценки.

Comments

[v_k]

мне главное - это чтобы побыстрее заполнить эту базу, не за месяцы, а где-то дней за 10. При скорости генерации данных - 1м в секунду. Проблема в том, что мне не понятно как сконструировать хранилище, чтобы была такая высокая скорость вставки. Что пробовали: файловая система (хранение в подпапках вида /a/b/c.../a1.txt, скорость вставки получилась медленная, Postgres - тоже медленная скорость).

Может надо сделать распределенное хранилище?

[mayton2019]

Postgres - тоже медленная скорость

Как ты оптимизировал Postgres. Там тоже должен быть режим batch-insert. Ты его применял?

[mayton2019]

Что пробовали: файловая система (хранение в подпапках вида /a/b/c.../a1.txt, скорость вставки получилась медленная

Это хорошая идея и ее надо обдумать. Но если вы планируете по 1 файлу на каждый ключ то ваша система лопнет по количеству inodes. А тюнинг ФС до такого уровня количества ключей я еще ни разу не встречал.
И вообще я думаю это плохая практика. ФС будет хранить больше мета-информации на каждый файл чем длина вашего ключа. Именно поэтому эта идея нежизнеспособна. Вы потеряете все терабайты в мету. Можно группировать ключи в файлы-группы но это все - уводит вас в сторону от собственно базы данных. Тогда постановку нужно пересмотреть полностью.

[v_k]

mayton2019, batch-insert делаю, да. Проблема, видимо, в том, что никакая отдельно стоЯщая БД не позволит делать 1м вставок в секунду с одним индексом по ключу, поэтому я хочу понять, может мне как-то распределенно построить базу? Например, грубо говоря, взять 1-ый символ, всего 58 вариантов и сделать 58 серверов, на которые будет идти вставка, а поиск по базе будет заключаться в одновременном запросе на все эти сервера.

[mayton2019]

v_k, вы можете отказаться от ACID и строгой консистентности и поднять например 8 постгресов и таким образом вставлять в разные БД ключи по формуле MOD(8) от ключа. Такое часто бывает в облатси биг-дата где я работаю. Но у нас в биг-дате данные обычно write-only. Исторические.

Вот. А при поисковых операциях вы будете просто очень быстро искать ключ в нужной БД из 8 возможных.

[v_k]

Dr. Bacon, у меня немного другая задача: есть пароль, задача по нему найти хеш, а не наоборот.

[v_k]

Dr. Bacon, по паролю я не узнаю где он, пароль со своей "солью"

[rPman]

универсальные базы данных это МЕДЛЕННАЯ ЗАПИСЬ, причем медленная от слова кошмар
они оптимальны там где многопользовательский доступ и есть транзакции, они очень дорогие!

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

[v_k]

v_k, всмысле хеш с солью

[v_k]

rPman, спасибо, посмотрю!

[v_k]

Dr. Bacon, а ну да, точно, а то я уже запутался

[mayton2019]

v_k, мне кажется что мы "не с той стороны" начали.
Вот смотри. Ты делаешь акцент на загрузке триллиона records за 10 дней.
А зачем тебе их все вообще грузить? В каком виде они лежат сейчас?
Если это - CSV файлы - то их можно так и положить на какую-нибудь
hdfs-like файловую систему и работать как с большими данными.
AWS athena может работать с ними сразу через SQL никуда даже не
преобразовывая. Spark умеет CSV в датафреймы преобразовывать.
А для скорости надо просто сделать партишенинг хешу от ключа.

А для быстрого ответа построить поврх этой системы Redis. Таким образом
горячие ключи быстро поднимутся в кеш а холодные.... а нафик они нужны.

Вобщем есть миллиард способов как решать эту задачу.

Answer 2

[rPman]

ключ 49 бит - log(66^8) - пусть для простоты 8байт, значение 32 байта (у тебя там hex строка)
только на значения тебе нужно 30 терабайта на каждый триллион - 32*10^12 и даже в идеальном случае еще 16тб на индекс ключа (чем больше оптимизируешь хранение тем больше операций на чтение и запись каждой)

Недавно была статья на хабре про тесты производительности работы mssql с похожими ключами миллионы записей

Я бы предложил схему с самописным индексом (мне кажется тут колхозить идеальнее всего).
* делишь ключ на 2 части (если бы ключ был не такой равномерный, то нужно было бы брать хеш от него), например по 4 байта
* младшие 4 байта (они наиболее равномерно будут распределены) - это номер блока в общем хранилище (на 1 триллион примерно 9кб, рекомендую. 16кб или 32кб, ssd на таких кластерах идеально работают), с массивом элементов: каждый из которых это вторые 4 байта ключа (старшие байты) + 32 байта искомое значение
для 16кб блока итоговое хранилище будет 70 тб - 2^32*16кб, можно прямо в дисковое устройство писать без файловой системы, по дискам пусть какой-нибудь рейд 0 раскидывает
* последняя запись в 16кб блоке - ссылка на дополнительное хранилище переполнений неравномерного распределения, его можно организовать как хочешь, на отдельном носителе

Итого на каждый запрос ты делаешь ровно одно чтение 16кб блока с диска, в полученном массиве ищешь нужный ключ и получаешь значение (если нет значит переполнения из-за неравномерного заполнения индекса, топать в дополнительное хранилище), кстати можно читать по секторно в процессе поиска, тогда если диск сумеет это оптимизировать будет 2х профит. Запись то точно так же - 1 чтение 16кб и запись 1 сектора диска, дозапись в массив. Кстати, если контролировать порядоковый номер ключевого значения (а что то мне говорит там будет простой перебор всех паролей) то будет последовательная запись блоков на диск, для hdd это идеальная ситуация. Иначе всю оперативную память используешь как самодельный lazy write буфер, при переполнении записываешь его на диск, отсортировав согласно дисковым устройствам и отсортировав порядок номеров секторов (тогда либо понимать как работает рейд либо самому раскидывать по дискам), операционные системы и контроллер диска это умеют но у них кеш маленький.

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

Добавь еще один уровень, будет 2 чтения по 8-16кб (когда ты не на 2 части делишь ключевое значение а на 3, первая часть ссылается на список ссылок на вторую часть, которые уже ссылаются на блоки с третьей частью), можно уменьшить этот оверхед но мне кажется скорость в твоей задаче важнее, ведь она упадет в два раза.
Универсальные базы данных делают многоуровневые древовидные индексы (это настраивается) и ради удобства и универсальности ты теряешь в скорости.

Comments

[Kirgus]

А что такое log(8^66)?

[rPman]

чтобы понять сколько бит нужно для хранения X значений, нужно взять логарифм по оснванию 2 (в калькуляторах есть просто log, нужно брать log(x)/log(2)

8 - количество символов в пароле
66 - количество значений одного символа (28+28+10)
66 в степени 8 - все количество возможных комбинаций значений

[rPman]

я извиняюсь посчитал то я верно а написал с ошибкой, конечно 66 в степени 8, подправил

Answer 3

[Dimonchik]

Aerospike

Comments

[v_k]

а если Cassandra?

[mayton2019]

v_k, кассандра скорее всего не подходит. Она в основном расчитана на In-Memory Cluster. Дорого и безсмысленно. Будете платить за uptime.

Хотя ее младший брат AWS-Dynamo может стоит рассмотреть. Будет дешевле с точки зрения хранения информации. Кажется там платить надо за фактически вычитанные строки. А за само хранение и за uptime
я не помню. Может и что-то начисляется но мало.

[Dimonchik]

v_k, на сайте есть же бенчмарки

Answer 4

[u007]

Так, а что, решения от Яндекса никто не предложил? ClickHouse - это как раз про то, когда данные текут рекой. Но там конечно не key-value.

Comments

[v_k]

В официальной документации кликхауса вроде бы написано, что он не подходит для хранения значений key => value

[Dimonchik]

ну я предложил
клик не гарантирует консистентности
и данные ТС не для колоночной базы

поэтому см выше

а клик по-своему хорош

Answer 5

[alfss]

Предлагаю взглянуть на tarantool
Еще может apache ignite

Answer 6

[Евгений Гл]

Что пробовали: файловая система (хранение в подпапках вида /a/b/c.../a1.txt, скорость вставки получилась медленная

Тут много времени уходит на создание папок.

Есть такой вариант:

1) Генерируете в памяти по N штук (в завис от размера ram).
dataBundle (словарь/массив/hashSet или т.п.):
   key = pass[0..M] //первые M символов (играем с этим значением)
   value = [[pass, hash], [pass2, hash2], [pass3, hash3]]

2) Скидываем в файл большим массивом (т.е. построчно будет каждый раз открывать)
foreach(var bundle in dataBundle)
{
     // ! не текстовой файл - бинарный
     AppendBytesToFile(d.key, d.value);
    // можем запоминать открытые файлы, чтобы не открывать их потом опять.
}

Результат:

0000.txt
0001.txt
...
asdf.txt:
   asdf0001 hash1
   asdf0002 hash2
   ...
   asdfZZZZ hash