Comments 66
1) Я правильно понимаю что при большом количестве случайных записей в большие секции (превысившие размер кеша и уже содержащие индекс) у вас на каждую запись будет происходить вычитывание соотвествующего индексного файла, распаковка, добавление записи, запаковка и запись обратно?
2) Вы ведь проводили бенчмарки? Можно увидеть результаты сравнения производительности с другими решениями, хотя бы с тем-же mysql?
2) Вы ведь проводили бенчмарки? Можно увидеть результаты сравнения производительности с другими решениями, хотя бы с тем-же mysql?
1. Во избежание фрагментации считывается весь индекс секции целиком (кроме больших файлов, каждый из которых содержат записи для только одного ключа). Но этот эффект сильно смягчается наличием кэшей, а также тем, что записи не сразу пишутся на диск, а группируются по секциям в памяти, и лишь при накоплении заданного объёма сбрасываются на диск.
2. К сожалению нет, но существующие SQL-решения (в частности, PostgreSQL) при наличии индекса по ключу неприемлемо замедлялись при миллионах записей (скорость падала в сотни раз). Данное же решение позволило записать несколько миллиардов записей на два сервера (оборудованных SSD) в течение 6-ти дней (половина отведённого времени ушло на парсинг источников данных). За этот срок скорость записи упала на 30%.
2. К сожалению нет, но существующие SQL-решения (в частности, PostgreSQL) при наличии индекса по ключу неприемлемо замедлялись при миллионах записей (скорость падала в сотни раз). Данное же решение позволило записать несколько миллиардов записей на два сервера (оборудованных SSD) в течение 6-ти дней (половина отведённого времени ушло на парсинг источников данных). За этот срок скорость записи упала на 30%.
1) Ну с кешами уже не всё так плохо. Про фрагментацию — не очень понял. Почему бы не сделать следующий вариант: изначально все записи кладутся в отсортированном виде в один файл. Как только он достигает определенного размера — разбить этот файл пополам. И так всё время разбивать пополам файлы — тогда не будет нужды зачитывать все файлы для вставки / удаления.
2) Какой именно тип индекса пробовали? Какого размера ключи и значения?
2) Какой именно тип индекса пробовали? Какого размера ключи и значения?
1. У меня тот же вариант. Есть максимальный размер индексного файла. Если он превышен, то файл разбивается на два, и т.д. Исключение составляют так называемые сингулярные файлы (файлы с записями одного ключа) — они не дробятся, поскольку всё равно для поиска по этому ключу придётся вычитывать их все. Это серьёзная оптимизация, поскольку индекс перестраивается целиком, а эти файлы остаются нетронутыми.
2. Нету никаких алгоритмов, просто массив строк отсортировали и поделили на части с заданным размером, сжали и записали в файлы.
2. Нету никаких алгоритмов, просто массив строк отсортировали и поделили на части с заданным размером, сжали и записали в файлы.
А я не понял, как вы будете случайные записи складывать в отсортированном виде в один файл? Вы имеете ввиду использовать какую-нибудь индексную структуру, вроде B+ деревьев?
Если записи накапливаются в памяти, то при креше все что в памяти сидит потеряется? Или есть какой-то журнал? Какие вообще гарантии в плане персистентности?
Миллиард записей, пусть по килобайту — это у нас терабайт.
Гм-гм, велосипедостроение, конечно, почетная и уважаемая отрасль промышленности, но сложно представить себе современную базу данных, которая бы захлебнулась на миллионах/миллиардах записей при хоть сколько либо вменяемых настройках и железе.
Плюс к тому, существующие решения и пишут на диск грамотнее и хранят лучше. То, что вы три дня писали терабайт на SSD как бы намекает на неоптимальность вашего решения. Чисто ради интереса: а сколько времени ушло на разработку?
Гм-гм, велосипедостроение, конечно, почетная и уважаемая отрасль промышленности, но сложно представить себе современную базу данных, которая бы захлебнулась на миллионах/миллиардах записей при хоть сколько либо вменяемых настройках и железе.
Плюс к тому, существующие решения и пишут на диск грамотнее и хранят лучше. То, что вы три дня писали терабайт на SSD как бы намекает на неоптимальность вашего решения. Чисто ради интереса: а сколько времени ушло на разработку?
В моём случае записи были небольшими, порядка 100-150 байт. Было записано 350GiB с компрессией порядка 20% процентов.
Попробуйте записать миллиард записей в базу с индексом. И сразу отпадут все вопросы.
А чего не смотрели другие решения, LevelDB явно очень хорошо приспособлено для вашей задачи.
Не смотрел в его сторону, кажется интересным вариантом. Но, насколько я понял, LevelDB не поддерживает множественные значения на один ключ.
Это формальность, данные хранятся в сортированных таблицах и их можно искать и по ним итерировать. Потому достаточно добавить timastamp или счеткик к концу ключа и получатся множественные значения.
Итераторы в LevelDB делают его очень гибким.
В вашем случае, возможно, стоит еще обратить внимание на RocksDB
Это доработанный LevelDB. Он оптимизирован для SSD и подходит для больших размеров БД. Не нужны лишние конвертирования — можно хранить бинарные данные. Ну и скорость нaaaамного выше. Три дня, что-то уж совсем перебор.
Короче, LevelDB/RocksDB — то что вам нужно.
Индекс можно строить уже после записи, мне кажется, у вас проблемы надуманы.
А зачем вы активно писали в таблицу с индексом? Я так понимаю, ваш кейс — сначала запишем миллиард записей, потом начинаем оттуда читать. Вывод — дропаем индекс, ставим COPY/BULK INSERT/что--то другое, отключаем autocommit/fsync и д.р., идем на обед или ставим на ночь. Приходим — все закачалось, возвращаем все назад, ставим индекс обратно, радуемся.
Если же вам нужно одновременно И читать, И активно писать, то это надо было делать с разных реплик, конечно же.
Если же вам нужно одновременно И читать, И активно писать, то это надо было делать с разных реплик, конечно же.
Не вполне понятно, для чего эта статья.
О том, как раскидать миллиард записей по файлам? Так это почти тривиально не такая уж сложная задача.
Предоставить сообществу код? Но тогда хотелось бы видеть лицензию и комментарии в коде (единственный — комментарий репозитория "Key/value(s) database capable for effective storage of billions of records" — мало о чём говорит). Вообще, текущая ревизия — неплохой пример того, что т. н. "самодокументируемый код" плохо понятен. Описание "алгоритмов" тоже не слишком подробно.
И самое главное — где результаты замеров скорости записи и поиска? Сколько ключей, сколько записей на один ключ, какой их объём?
Интересно было бы увидеть скорость с использованием других ФС и других алгоритмов сжатия. gzip всё-таки не самый быстрый (и не самый сильный) компрессор.
Тема интересна, но освещена недостаточно подробно.
Добавил MIT-лицензию.
Скорость выборки по ключу с малым числом записей на базе объёмом в 350GIB (записи размером 100-150 байт) — единицы сотых секунды (например, для ключа с сотней выбранных записей — 0.015s).
0.015 секунд — это время извлечения всех 100 записей с заданным ключем?
А уникальных ключей сколько?
У меня в продуктиве: PostgreSQL 9.5, 658 млн уникальных записей. Первичный ключ — Bigint, индекс на первичный ключ — 20 ГБ.
SELECT * FROM table WHERE pkey IN (100 случайных ключей)
Время выполнения — 0.012s.
SELECT * FROM table WHERE pkey IN (100 случайных ключей)
Время выполнения — 0.012s.
У автора одному ключу соответствует довольно большой список записей.
Возможно, "обычная" СУБД в этом случае из-за фрагментации списков записей с одним ключом будет тормозить при добавлении, да и при поиске (зависит от последовательности добавления; вероятно, перед поиском БД можно дефрагментировать).
К такому количеству записей существующие SQL/NoSQL системы хранения оказались плохо приспособлены
Неубедительно. Приведите сравнение по скорости с каким-нибудь MySQL/PostgreSQL, храня значение в листовой колонке, и документной базой типа Couchbase.
А как насчёт параллельной записи? Что если запустить несколько копий приложения, которые будут добавлять значения одновременно, не сломается ли эта конструкция?
Чаще всего такие кейсы «миллиард записей» требуют многопоточных или распределённых по не скольким машинам приложений.
Чаще всего такие кейсы «миллиард записей» требуют многопоточных или распределённых по не скольким машинам приложений.
Система поддерживает параллельность на уровне секций — можно задать число потоков, на которые будет распределяться задача добавления данных по секциям. На практике это здорово ускоряет процесс записи.
В принципе выглядит вкусно, нужен бенчмарк Mastore vs Redis vs PostgreSQL, чтобы точно знать)
К такому количеству записей опробованные SQL/NoSQL системы хранения оказались плохо приспособлены
Данные в базе распределены по секциямПроводилось ли сравнение (в т.ч. по производительности) с распространенными СУБД именно с использованием секционирования?
Использовались ли при этом средства bulk insert сравниваемой СУБД?
Под секционированием имеете ввиду — вертикальные партиции?
Нет, вот эти, например.
Правда, там ограничение на 8К партиций. Если этого не хватает, то можно сделать несколько таблиц, если логика задачи позволяет. Правда, тогда разделение данных по таблицам придется самостоятельно реализовывать.
Ну или другую СУБД выбрать, с другим ограничением.
В пределе можно вообще эмулировать секционирование, создав 64К таблиц. Но насколько это хороший вариант — не знаю, надо тестировать.
Правда, там ограничение на 8К партиций. Если этого не хватает, то можно сделать несколько таблиц, если логика задачи позволяет. Правда, тогда разделение данных по таблицам придется самостоятельно реализовывать.
Ну или другую СУБД выбрать, с другим ограничением.
В пределе можно вообще эмулировать секционирование, создав 64К таблиц. Но насколько это хороший вариант — не знаю, надо тестировать.
Удивляют такие люди — «Настоящий кодер не будет читать Войну и Мир — настоящий кодер напишет ее с нуля».
Ну есть же достаточно большое количество СУБД которых вам с головой хватит, тем более при таких то объемах
Ну есть же достаточно большое количество СУБД которых вам с головой хватит, тем более при таких то объемах
Вполне возможно, что ClickHouse от Яндекса подойдет к вашей задаче — по упомянутым в статье требованиям она подходит. А скорость у нее весьма и весьма хорошая. См. бенчмарки (там сравнения на разных объемах с разными БД, от 10 млн. до 1 млрд. записей).
Это немного оффтопик, но может кто-нибудь посоветовать простую РСУБД с поддержкой SQL, которая поддерживала бы такие объемы? Пытаюсь сделать задачку на kaggle, там csv-файл на ~100Gb, 2 млрд. записей. У меня сутки ушли на то чтобы его загрузить в MS SQL. Теперь я хочу скопировать эти данные в новую таблицу с нужным кластерным индексом, немного преобразованными полями. 12 часов этот запрос мучил мой жёсткий диск, создал журнал транзакций на 500Gb. В итоге место закончилось. Я конечно тупанул, нужно было это делать в пакетном режиме, но, в любом случае, на домашнем компе MS SQL такие объемы не тянет.
Глянул Apache Hadoop, но там безумное количество каких-то пакетов, месяц уйдет, чтобы разобраться. А что ещё можно попробовать?
Глянул Apache Hadoop, но там безумное количество каких-то пакетов, месяц уйдет, чтобы разобраться. А что ещё можно попробовать?
А вы уверены, что вам нужна rdbms? Hadoop вообще ни пол раза не про sql.
Если исходные данные в виде какой-нибудь csv, то можно попробовать любой поточный обработчик. Например, Apache Spark, он может обмолотить довольно быстро. Ну и лучше, конечно, сначала обкатать на небольшом куске алгоритмику, а потом уже развлекаться со всей базой. Больше итераций может быть куда более продуктивным подходом.
Вообще, основной анализатор у меня написан на R. Но он работает только с данными загруженными в память.
Мне нужно сджойнить 3 csv-файла и посчитать частоты. Можно было бы всё это делать небольшими кусками по миллиону записей. Но проблема в том, что данные идут вперемежку, сначала 100Gb-файл нужно отсортировать. Для сортировки и джойнинга я как-раз и хотел использовать РСУБД. Ну, и частоты тоже можно сразу в РСУБД посчитать. Но оказалось, что это очень медленно.
Спасибо, попробую Apache Spark, тем более у него есть биндинги для R и библиотека для машинного обучения. Хотя есть сомнения, что он сможет сджойнить несколько CSV, отсортировать их и при этом уложится в 16Gb оперативной памяти.
А колоночные РСУБД кто-нибудь пробовал?
Мне нужно сджойнить 3 csv-файла и посчитать частоты. Можно было бы всё это делать небольшими кусками по миллиону записей. Но проблема в том, что данные идут вперемежку, сначала 100Gb-файл нужно отсортировать. Для сортировки и джойнинга я как-раз и хотел использовать РСУБД. Ну, и частоты тоже можно сразу в РСУБД посчитать. Но оказалось, что это очень медленно.
Спасибо, попробую Apache Spark, тем более у него есть биндинги для R и библиотека для машинного обучения. Хотя есть сомнения, что он сможет сджойнить несколько CSV, отсортировать их и при этом уложится в 16Gb оперативной памяти.
А колоночные РСУБД кто-нибудь пробовал?
У меня ушла неделя на то, чтобы разобраться со всеми ошибками, фичами и вникнуть в SparkR — не всё сходу заработало и API несколько отличается от data.tables. Но оно того стоило. 100Gb-ый csv-файл превратился в нужный мне 4,5Gb-ый всего за 3,5 часа! При том, что у MS SQL ушло часов 12 только на загрузку CSV, а на обработке он просто забил ещё за 15 часов весь жесткий диск мусором и умер.
Если вместо CSV использовать более адекватные форматы, то со Spark можно добиться ещё большей производительности. Ещё в Spark очень прикольный Web UI, в котором видна схема выполняемого запроса, виден прогресс каждого шага — сколько данных уже обработано и т.п. Напоминает SSIS-скрипт, только ты его не накликиваешь мышкой, а пишешь нормальный код на R или другом языке, а схема выполнения рисуется сама.
Словом, очень не хотелось изучать очередную технологию. Но Spark — очень клевая штука.
Если вместо CSV использовать более адекватные форматы, то со Spark можно добиться ещё большей производительности. Ещё в Spark очень прикольный Web UI, в котором видна схема выполняемого запроса, виден прогресс каждого шага — сколько данных уже обработано и т.п. Напоминает SSIS-скрипт, только ты его не накликиваешь мышкой, а пишешь нормальный код на R или другом языке, а схема выполнения рисуется сама.
Словом, очень не хотелось изучать очередную технологию. Но Spark — очень клевая штука.
Вы на RDD или на DataFrames сделали?
На DataFrames. По RDD для R документации почти нет. Пока я просто преобразовал данные. Попробовал посчитать линейную регрессию по одному фактору на 100 млн. записей. У Spark ушло где-то полчаса. А в R памяти хватало только для обработки порядка 10 млн. записей. Похоже придётся ещё изучать Spark MLlib.
Некоторые СУБД умеют подключать csv-файл как внешнюю таблицу. Возможно, MS SQL тоже.
Попробуйте sqlite. См. бенчмарк в комментарии.
Тоже делал подобный велосипед, но поверх MongoDB, данные резались на чанки в доль индексов, упаковывались и максимально сжимались bzip2/xz без заголовков, далее чанки растекались по шардингу.
Чтение этих данных — питон потоково получал, распаковывал и передавал сырье в с++ либу которая уже все обсчитывала. По скорости, 20 млн (или 200 млн, уже не помню) записей обрабатывались за 2 сек на одном ядре, это включая вычитывание из базы и пересчет — формирование простого отчета, на одно ядро виртуалки из DO. Не один SQL-db построчно такую скорость не выдаст на ядро.
За счет чанкования и сжатия скорость выросла в сотни раз, занимаемое место уменьшилось в десяки и индексы уменьшились в сотни раз.
Возможно ClickHouse нам бы подошел, но его ещё не было (в паблике).
Чтение этих данных — питон потоково получал, распаковывал и передавал сырье в с++ либу которая уже все обсчитывала. По скорости, 20 млн (или 200 млн, уже не помню) записей обрабатывались за 2 сек на одном ядре, это включая вычитывание из базы и пересчет — формирование простого отчета, на одно ядро виртуалки из DO. Не один SQL-db построчно такую скорость не выдаст на ядро.
За счет чанкования и сжатия скорость выросла в сотни раз, занимаемое место уменьшилось в десяки и индексы уменьшились в сотни раз.
Возможно ClickHouse нам бы подошел, но его ещё не было (в паблике).
Попробуем sqlite.
1000 ключей по 10 000 значений = 10 000 000 записей, размер значения ~100 байт:
Размер csv — 1.1 Gb
Размер базы с индексом — 1.4 Gb
1000 ключей по 10 000 значений = 10 000 000 записей, размер значения ~100 байт:
CSV GENERATION:
real 2m4.618s
user 1m51.416s
sys 0m12.280s
CSV IMPORT:
real 0m33.533s
user 0m21.216s
sys 0m2.640s
INDEX CREATION:
real 0m6.253s
user 0m4.420s
sys 0m1.036s
#!/bin/bash
keys=1000
values=10000
size=100
data=$(tr -dc 'a-z' < /dev/urandom | head -c $size)
csv_file=test.csv
db_file=test.db
rm $csv_file $db_file
echo CSV GENERATION:
echo key,value > $csv_file
time for k in $(seq $keys); do
for v in $(seq $values); do
echo $k.key,$k.$v.$data
done
done >> $csv_file
echo
echo CSV IMPORT:
time echo -e ".mode csv\n.import $csv_file kv" | sqlite3 $db_file
echo
echo INDEX CREATION:
time sqlite3 $db_file 'create index ikey on kv (key)'
Размер csv — 1.1 Gb
Размер базы с индексом — 1.4 Gb
А почему максимум 65636 секций, а не 65536?
Кто из вас, минусующих автора диванных аналитиков, написал свое хоть немного что-то близкое по сложности?
Человек решил свою задачу так как ему нравится. Поделился с вами своим внутренним миром и получил «а зачем», «а есть же». Чуть ли не «ты дурак, делал то что уже есть»
Семён (@ababo) жму руку. От какой суммы рассматриваешь предложения о работе?
Человек решил свою задачу так как ему нравится. Поделился с вами своим внутренним миром и получил «а зачем», «а есть же». Чуть ли не «ты дурак, делал то что уже есть»
Семён (@ababo) жму руку. От какой суммы рассматриваешь предложения о работе?
Спасибо за слова поддержки — действительно, как-то уж слишком много негатива вылилось. А по поводу вашего вопроса… если вам реально интересно, то пишите в личку.
Кто из вас, минусующих автора диванных аналитиков, написал свое хоть немного что-то близкое по сложности?
Задача не так сложна, как вам кажется. Автор в ~800 строк кода на go уложился — уже показатель невысокой сложности. Примерно уровень курсового проекта. Такое писали все.
Sign up to leave a comment.
Система хранения для миллиардов записей с доступом по ключу