Постановка задачи
В одном из прошлых проектов мне была поставлена задача написания системы для хранения миллиардов записей. Доступ к данным должен осуществляться по ключу: одному ключу в общем случае соответствует множество (на практике, вплоть до десятков миллионов) записей, которые могут добавляться, но не модифицироваться или удаляться.
К такому количеству записей опробованные SQL/NoSQL системы хранения оказались плохо приспособлены, поэтому клиент предложил с нуля разработать специализированное решение.
Выбранный подход
После серии опытов был выбран следующий подход. Данные в базе распределены по секциям, каждая из которых представляет собой файл или директорию на диске. Секции соответствует значение CRC16-хеша, т.е. возможно всего 65,536 секций. Практика показывает, что современные файловые системы (тестировалась ext4) достаточно эффективно справляются с таким количеством элементов внутри одной директории. Итак, добавляемые записи хешируются по ключу и распределяются по соответствующим секциям.
Каждая секция состоит из кэша (файл, в котором накапливаются неупорядоченные записи вплоть до заданного размера) и индекса (набора сжатых файлов, хранящих упорядоченные по ключу записи). Т.е. предполагается следующий сценарий работы:
- Записи накапливаются в памяти до некоторого предела, а далее распределяются по секциям.
- Внутри секции записи попадут в кэш, если он не превысит заданный размер.
- Иначе содержимое индекса будет полностью вычитано (за некоторыми оговорками, о них ниже), к нему будет добавлено содержимое кэша, а далее все эти данные будут отсортированы и разбиты на файлы индекса (кэш при этом обнуляется).
Каждый индексный файл имеет то же имя, что и ключ первой хранимой записи (на практике оно url-encoded для совместимости с файловыми системами). Таким образом, при поиске записей по ключу индекс позволяет не вычитывать всю секцию, а только кэш и малую часть индексных файлов, в которых могут находиться искомые записи.
Подробный алгоритм добавления записей в секцию
- Если размер добавляемых записей в сумме с размером кэш-файла меньше заданного максимального объёма, то записи просто добавляется в кэш-файл, и на этом обработка секции завершена.
- Иначе содержимое кэш-файла, а также индексные файлы читаются (исключая файлы с размером больше заданного лимита) и добавляется к обрабатываемой секции.
- Секция сортируется по значению ключа.
- Создаётся временная директория, в которую будут записаны новые индексные файлы.
- Отсортированный массив записей делится на равные части (без разрыва записей) заданного размера (но с разными именами, в противном случае файл растёт до нужного размера, игнорируя лимит) и записываются в gzip-компрессированные индексные файлы. Каждый такой файл имеет имя _url_encoded<ключ>_XXXX, где ключ — это ключ первой записи содержимого файла, а XXXX — 4 16-ричных разряда (нужны для различения файлов с одним значением ключа при сохранении лексикографического порядка именования). XXXX равен 0000, если в директории секции нет файла с таким именем, иначе 0001, и т.д.
- Для всех файлов, с именами которых возникли коллизии (и пришлось увеличивать XXXX) создаём твёрдые ссылки во временной директории.
- Удаляем старую директорию секции и переименовываем временную на её место.
Как пользоваться
Mastore (от massive storage) написан на Golang и собирается в исполняемый файл, запускаемый в режиме чтения, записи или самотестирования. Будучи запущенным в режиме записи Mastore читает из stdin текстовые строки, состоящие из ключа и значения, разделённых символом табуляции (для бинарных данных можно использовать дополнительное кодирование, например, Base85):
mastore write [-config=<config>]Для чтения записей по заданному ключу используется следующая команда:
mastore read [-config=<config>] -key=<key>А для получения списка всех ключей:
mastore read [-config=<config>] -keysMastore конфигурируется с помощью JSON-файла. Вот пример конфигурации по-умолчанию:
{
"StorePath": "$HOME/$STORE",
"MaxAccumSizeMiB": 1024,
"MaxCacheSizeKiB": 1024,
"MaxIndexBlockSizeKiB": 8192,
"MinSingularSizeKiB": 8192,
"CompressionLevel": -1,
"MaxGoroutines": 1
}Комментарии (63)
terrier
18.12.2016 21:33+11Миллиард записей, пусть по килобайту — это у нас терабайт.
Гм-гм, велосипедостроение, конечно, почетная и уважаемая отрасль промышленности, но сложно представить себе современную базу данных, которая бы захлебнулась на миллионах/миллиардах записей при хоть сколько либо вменяемых настройках и железе.
Плюс к тому, существующие решения и пишут на диск грамотнее и хранят лучше. То, что вы три дня писали терабайт на SSD как бы намекает на неоптимальность вашего решения. Чисто ради интереса: а сколько времени ушло на разработку?
ababo
18.12.2016 21:40В моём случае записи были небольшими, порядка 100-150 байт. Было записано 350GiB с компрессией порядка 20% процентов.
ababo
18.12.2016 21:50+1Попробуйте записать миллиард записей в базу с индексом. И сразу отпадут все вопросы.
zzzcpan
18.12.2016 22:10+3А чего не смотрели другие решения, LevelDB явно очень хорошо приспособлено для вашей задачи.
ababo
18.12.2016 22:27Не смотрел в его сторону, кажется интересным вариантом. Но, насколько я понял, LevelDB не поддерживает множественные значения на один ключ.
zzzcpan
18.12.2016 22:39+1Это формальность, данные хранятся в сортированных таблицах и их можно искать и по ним итерировать. Потому достаточно добавить timastamp или счеткик к концу ключа и получатся множественные значения.
rotor
19.12.2016 02:15+1Итераторы в LevelDB делают его очень гибким.
В вашем случае, возможно, стоит еще обратить внимание на RocksDB
Это доработанный LevelDB. Он оптимизирован для SSD и подходит для больших размеров БД. Не нужны лишние конвертирования — можно хранить бинарные данные. Ну и скорость нaaaамного выше. Три дня, что-то уж совсем перебор.
Короче, LevelDB/RocksDB — то что вам нужно.
VaalKIA
18.12.2016 22:26+5Индекс можно строить уже после записи, мне кажется, у вас проблемы надуманы.
terrier
18.12.2016 22:39+2А зачем вы активно писали в таблицу с индексом? Я так понимаю, ваш кейс — сначала запишем миллиард записей, потом начинаем оттуда читать. Вывод — дропаем индекс, ставим COPY/BULK INSERT/что--то другое, отключаем autocommit/fsync и д.р., идем на обед или ставим на ночь. Приходим — все закачалось, возвращаем все назад, ставим индекс обратно, радуемся.
Если же вам нужно одновременно И читать, И активно писать, то это надо было делать с разных реплик, конечно же.ababo
18.12.2016 22:49-3Это будет эффективнее, но построение индекса на диске для миллиардов записей (это значит, их все отсортировать, причём на диске, так как памяти не хватит) кажется не слишком практичной задачей. Кроме того, придётся писать их без компрессии, что потребует в 6-10 раз большего объёма.
Akon32
18.12.2016 22:29+6Не вполне понятно, для чего эта статья.
О том, как раскидать миллиард записей по файлам? Так это
почти тривиальноне такая уж сложная задача.
Предоставить сообществу код? Но тогда хотелось бы видеть лицензию и комментарии в коде (единственный — комментарий репозитория "Key/value(s) database capable for effective storage of billions of records" — мало о чём говорит). Вообще, текущая ревизия — неплохой пример того, что т. н. "самодокументируемый код" плохо понятен. Описание "алгоритмов" тоже не слишком подробно.
И самое главное — где результаты замеров скорости записи и поиска? Сколько ключей, сколько записей на один ключ, какой их объём?
Интересно было бы увидеть скорость с использованием других ФС и других алгоритмов сжатия. gzip всё-таки не самый быстрый (и не самый сильный) компрессор.
Тема интересна, но освещена недостаточно подробно.
ababo
18.12.2016 23:02+1Скорость выборки по ключу с малым числом записей на базе объёмом в 350GIB (записи размером 100-150 байт) — единицы сотых секунды (например, для ключа с сотней выбранных записей — 0.015s).
Tatikoma
19.12.2016 15:04+4У меня в продуктиве: PostgreSQL 9.5, 658 млн уникальных записей. Первичный ключ — Bigint, индекс на первичный ключ — 20 ГБ.
SELECT * FROM table WHERE pkey IN (100 случайных ключей)
Время выполнения — 0.012s.Akon32
19.12.2016 16:09У автора одному ключу соответствует довольно большой список записей.
Возможно, "обычная" СУБД в этом случае из-за фрагментации списков записей с одним ключом будет тормозить при добавлении, да и при поиске (зависит от последовательности добавления; вероятно, перед поиском БД можно дефрагментировать).
leventov
18.12.2016 23:34+8К такому количеству записей существующие SQL/NoSQL системы хранения оказались плохо приспособлены
Неубедительно. Приведите сравнение по скорости с каким-нибудь MySQL/PostgreSQL, храня значение в листовой колонке, и документной базой типа Couchbase.
Luchnik22
18.12.2016 23:41+1А как насчёт параллельной записи? Что если запустить несколько копий приложения, которые будут добавлять значения одновременно, не сломается ли эта конструкция?
Чаще всего такие кейсы «миллиард записей» требуют многопоточных или распределённых по не скольким машинам приложений.ababo
18.12.2016 23:42Система поддерживает параллельность на уровне секций — можно задать число потоков, на которые будет распределяться задача добавления данных по секциям. На практике это здорово ускоряет процесс записи.
Luchnik22
18.12.2016 23:56В принципе выглядит вкусно, нужен бенчмарк Mastore vs Redis vs PostgreSQL, чтобы точно знать)
grossws
19.12.2016 04:07+4Я б предложил сравнивать с:
- чем-нибудь из классических rdbms (MySQL/MariaDB, Postregsql);
- чем-нибудь из kv движков (LevelDB, Kyoto Cabinet, lmdb);
- чем-нибудь имеющим lsmt внизу, например Apache Cassandra.
miksoft
19.12.2016 10:27+1К такому количеству записей опробованные SQL/NoSQL системы хранения оказались плохо приспособлены
Данные в базе распределены по секциям
Проводилось ли сравнение (в т.ч. по производительности) с распространенными СУБД именно с использованием секционирования?
Использовались ли при этом средства bulk insert сравниваемой СУБД?
heleo
19.12.2016 14:28Под секционированием имеете ввиду — вертикальные партиции?
miksoft
19.12.2016 15:39Нет, вот эти, например.
Правда, там ограничение на 8К партиций. Если этого не хватает, то можно сделать несколько таблиц, если логика задачи позволяет. Правда, тогда разделение данных по таблицам придется самостоятельно реализовывать.
Ну или другую СУБД выбрать, с другим ограничением.
В пределе можно вообще эмулировать секционирование, создав 64К таблиц. Но насколько это хороший вариант — не знаю, надо тестировать.
yusman
19.12.2016 11:41+9Удивляют такие люди — «Настоящий кодер не будет читать Войну и Мир — настоящий кодер напишет ее с нуля».
Ну есть же достаточно большое количество СУБД которых вам с головой хватит, тем более при таких то объемах
Regis
19.12.2016 16:23Вполне возможно, что ClickHouse от Яндекса подойдет к вашей задаче — по упомянутым в статье требованиям она подходит. А скорость у нее весьма и весьма хорошая. См. бенчмарки (там сравнения на разных объемах с разными БД, от 10 млн. до 1 млрд. записей).
ababo
19.12.2016 18:33Мой самописный инструмент прекрасно справляется с поставленной задачей, но за ссылку спасибо. Почитаю.
Regis
19.12.2016 18:42Если простое вычитывание данных — это всё, что вам нужно, тогда да, вряд ли какая-то БД сможет сделать более эффективное линейное чтение. Разве что может добавить в каком-то виде защиту целостности данных.
Ares_ekb
19.12.2016 20:58+1Это немного оффтопик, но может кто-нибудь посоветовать простую РСУБД с поддержкой SQL, которая поддерживала бы такие объемы? Пытаюсь сделать задачку на kaggle, там csv-файл на ~100Gb, 2 млрд. записей. У меня сутки ушли на то чтобы его загрузить в MS SQL. Теперь я хочу скопировать эти данные в новую таблицу с нужным кластерным индексом, немного преобразованными полями. 12 часов этот запрос мучил мой жёсткий диск, создал журнал транзакций на 500Gb. В итоге место закончилось. Я конечно тупанул, нужно было это делать в пакетном режиме, но, в любом случае, на домашнем компе MS SQL такие объемы не тянет.
Глянул Apache Hadoop, но там безумное количество каких-то пакетов, месяц уйдет, чтобы разобраться. А что ещё можно попробовать?grossws
19.12.2016 21:39+3А вы уверены, что вам нужна rdbms? Hadoop вообще ни пол раза не про sql.
Если исходные данные в виде какой-нибудь csv, то можно попробовать любой поточный обработчик. Например, Apache Spark, он может обмолотить довольно быстро. Ну и лучше, конечно, сначала обкатать на небольшом куске алгоритмику, а потом уже развлекаться со всей базой. Больше итераций может быть куда более продуктивным подходом.
Ares_ekb
20.12.2016 06:24Вообще, основной анализатор у меня написан на R. Но он работает только с данными загруженными в память.
Мне нужно сджойнить 3 csv-файла и посчитать частоты. Можно было бы всё это делать небольшими кусками по миллиону записей. Но проблема в том, что данные идут вперемежку, сначала 100Gb-файл нужно отсортировать. Для сортировки и джойнинга я как-раз и хотел использовать РСУБД. Ну, и частоты тоже можно сразу в РСУБД посчитать. Но оказалось, что это очень медленно.
Спасибо, попробую Apache Spark, тем более у него есть биндинги для R и библиотека для машинного обучения. Хотя есть сомнения, что он сможет сджойнить несколько CSV, отсортировать их и при этом уложится в 16Gb оперативной памяти.
А колоночные РСУБД кто-нибудь пробовал?
am-amotion-city
20.12.2016 09:31+1На Кафку еще посмотрите, он как раз для этого, то есть, по идее, должен хоть под 1G оперативки справиться. Правда, если вам из этих csv-шек нужно все, то Кафка тут лишний.
На всякий случай, как подружить Спарк с Кафкой.
Ares_ekb
26.12.2016 16:36+1У меня ушла неделя на то, чтобы разобраться со всеми ошибками, фичами и вникнуть в SparkR — не всё сходу заработало и API несколько отличается от data.tables. Но оно того стоило. 100Gb-ый csv-файл превратился в нужный мне 4,5Gb-ый всего за 3,5 часа! При том, что у MS SQL ушло часов 12 только на загрузку CSV, а на обработке он просто забил ещё за 15 часов весь жесткий диск мусором и умер.
Если вместо CSV использовать более адекватные форматы, то со Spark можно добиться ещё большей производительности. Ещё в Spark очень прикольный Web UI, в котором видна схема выполняемого запроса, виден прогресс каждого шага — сколько данных уже обработано и т.п. Напоминает SSIS-скрипт, только ты его не накликиваешь мышкой, а пишешь нормальный код на R или другом языке, а схема выполнения рисуется сама.
Словом, очень не хотелось изучать очередную технологию. Но Spark — очень клевая штука.
Stas911
28.12.2016 07:31Вы на RDD или на DataFrames сделали?
Ares_ekb
28.12.2016 08:56На DataFrames. По RDD для R документации почти нет. Пока я просто преобразовал данные. Попробовал посчитать линейную регрессию по одному фактору на 100 млн. записей. У Spark ушло где-то полчаса. А в R памяти хватало только для обработки порядка 10 млн. записей. Похоже придётся ещё изучать Spark MLlib.
miksoft
19.12.2016 22:33Некоторые СУБД умеют подключать csv-файл как внешнюю таблицу. Возможно, MS SQL тоже.
Ares_ekb
20.12.2016 06:27Может, но я думаю, что это будет ещё медленней. Мне удалось загрузить CSV за сутки, но даже с этой таблицей ничего толком не сделаешь, все запросы выполняются часами и съедают всё место на жестком диске.
lega
20.12.2016 01:11Тоже делал подобный велосипед, но поверх MongoDB, данные резались на чанки в доль индексов, упаковывались и максимально сжимались bzip2/xz без заголовков, далее чанки растекались по шардингу.
Чтение этих данных — питон потоково получал, распаковывал и передавал сырье в с++ либу которая уже все обсчитывала. По скорости, 20 млн (или 200 млн, уже не помню) записей обрабатывались за 2 сек на одном ядре, это включая вычитывание из базы и пересчет — формирование простого отчета, на одно ядро виртуалки из DO. Не один SQL-db построчно такую скорость не выдаст на ядро.
За счет чанкования и сжатия скорость выросла в сотни раз, занимаемое место уменьшилось в десяки и индексы уменьшились в сотни раз.
Возможно ClickHouse нам бы подошел, но его ещё не было (в паблике).
truezemez
20.12.2016 10:10+1Попробуем sqlite.
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
bak
1) Я правильно понимаю что при большом количестве случайных записей в большие секции (превысившие размер кеша и уже содержащие индекс) у вас на каждую запись будет происходить вычитывание соотвествующего индексного файла, распаковка, добавление записи, запаковка и запись обратно?
2) Вы ведь проводили бенчмарки? Можно увидеть результаты сравнения производительности с другими решениями, хотя бы с тем-же mysql?
ababo
1. Во избежание фрагментации считывается весь индекс секции целиком (кроме больших файлов, каждый из которых содержат записи для только одного ключа). Но этот эффект сильно смягчается наличием кэшей, а также тем, что записи не сразу пишутся на диск, а группируются по секциям в памяти, и лишь при накоплении заданного объёма сбрасываются на диск.
2. К сожалению нет, но существующие SQL-решения (в частности, PostgreSQL) при наличии индекса по ключу неприемлемо замедлялись при миллионах записей (скорость падала в сотни раз). Данное же решение позволило записать несколько миллиардов записей на два сервера (оборудованных SSD) в течение 6-ти дней (половина отведённого времени ушло на парсинг источников данных). За этот срок скорость записи упала на 30%.
bak
1) Ну с кешами уже не всё так плохо. Про фрагментацию — не очень понял. Почему бы не сделать следующий вариант: изначально все записи кладутся в отсортированном виде в один файл. Как только он достигает определенного размера — разбить этот файл пополам. И так всё время разбивать пополам файлы — тогда не будет нужды зачитывать все файлы для вставки / удаления.
2) Какой именно тип индекса пробовали? Какого размера ключи и значения?
ababo
1. У меня тот же вариант. Есть максимальный размер индексного файла. Если он превышен, то файл разбивается на два, и т.д. Исключение составляют так называемые сингулярные файлы (файлы с записями одного ключа) — они не дробятся, поскольку всё равно для поиска по этому ключу придётся вычитывать их все. Это серьёзная оптимизация, поскольку индекс перестраивается целиком, а эти файлы остаются нетронутыми.
2. Нету никаких алгоритмов, просто массив строк отсортировали и поделили на части с заданным размером, сжали и записали в файлы.
kmu1990
А я не понял, как вы будете случайные записи складывать в отсортированном виде в один файл? Вы имеете ввиду использовать какую-нибудь индексную структуру, вроде B+ деревьев?
ababo
Случайные записи попадают в кэш соотв. секций, т.е. просто добавляются в неотсортированном виде. Когда кэш-файл переполняется секция перестраивается целиком (кроме больших файлов с записями одного ключа).
kmu1990
Этот вопрос был не вам, как у вас сделано я понял. Меня интересует конкретный момент добавления записей в файл в отсортированном порядке.
kmu1990
Если записи накапливаются в памяти, то при креше все что в памяти сидит потеряется? Или есть какой-то журнал? Какие вообще гарантии в плане персистентности?
ababo
Если упадёт, то данные потеряются. Никакого журналирования не предусмотрено.