Система хранения для миллиардов записей с доступом по ключу
Постановка задачи
В одном из прошлых проектов мне была поставлена задача написания системы для хранения миллиардов записей. Доступ к данным должен осуществляться по ключу: одному ключу в общем случае соответствует множество (на практике, вплоть до десятков миллионов) записей, которые могут добавляться, но не модифицироваться или удаляться.
К такому количеству записей существующие SQL/NoSQL системы хранения оказались плохо приспособлены, поэтому клиент предложил с нуля разработать специализированное решение.
Выбранный подход
После серии опытов был выбран следующий подход. Данные в базе распределены по секциям, каждая из которых представляет собой файл или директорию на диске. Секции соответствует значение CRC16-хеша, т.е. возможно всего 65,636 секций. Практика показывает, что современные файловые системы (тестировалась ext4) достаточно эффективно справляются с таким количеством элементов внутри одной директории. Итак, добавляемые записи хешируются по ключу и распределяются по соответствующим секциям.
Каждая секция состоит из кэша (файл, в котором накапливаются неупорядоченные записи вплоть до заданного размера) и индекса (набора сжатых файлов, хранящих упорядоченные по ключу записи). Т.е. предполагается следующий сценарий работы:
- Записи накапливаются в памяти до некоторого предела, а далее распределяются по секциям.
- Внутри секции записи попадут в кэш, если он не превысит заданный размер.
- Иначе содержимое индекса будет полностью вычитано (за некоторыми оговорками, о них ниже), к нему будет добавлено содержимое кэша, а далее все эти данные будут отсортированы и разбиты на файлы индекса (кэш при этом обнуляется).
Каждый индексный файл имеет то же имя, что и ключ первой хранимой записи (на практике оно url-encoded для совместимости с файловыми системами). Таким образом, при поиске записей по ключу индекс позволяет не вычитывать всю секцию, а только кэш и малую часть индексных файлов, в которых могут находиться искомые записи.
Подробный алгоритм добавления записей в секцию
- Если размер добавляемых записей в сумме с размером кэш-файла меньше заданного максимального объёма, то записи просто добавляется в кэш-файл, и на этом обработка секции завершена.
- Иначе содержимое кэш-файла, а также индексные файлы читаются (исключая файлы с размером больше заданного лимита) и добавляется к обрабатываемой секции.
- Секция сортируется по значению ключа.
- Создаётся временная директория, в которую будут записаны новые индексные файлы.
- Отсортированный массив записей делится на равные части (без разрыва записей) заданного размера (но с разными именами, в противном случае файл растёт до нужного размера, игнорируя лимит) и записываются в gzip-компрессированные индексные файлы. Каждый такой файл имеет имя _url_encoded<ключ>_XXXX, где ключ — это ключ первой записи содержимого файла, а XXXX — 4 16-ричных разряда (нужны для различения файлов с одним значением ключа при сохранении лексикографического порядка именования). XXXX равен 0000, если в директории секции нет файла с таким именем, иначе 0001, и т.д.
- Для всех файлов, с именами которых возникли коллизии (и пришлось увеличивать XXXX) создаём твёрдые ссылки во временной директории.
- Удаляем старую директорию секции и переименовываем временную на её место.
Как пользоваться
Mastore (от massive storage) написан на Golang и собирается в исполняемый файл, запускаемый в режиме чтения, записи или самотестирования. Будучи запущенным в режиме записи Mastore читает из stdin текстовые строки, состоящие из ключа и значения, разделённых символом табуляции (для бинарных данных можно использовать дополнительное кодирование, например, Base85):
mastore write [-config=] Для чтения записей по заданному ключу используется следующая команда:
mastore read [-config=] -key= А для получения списка всех ключей:
mastore read [-config=] -keys Mastore конфигурируется с помощью JSON-файла. Вот пример конфигурации по-умолчанию:
{
"StorePath": "$HOME/$STORE",
"MaxAccumSizeMiB": 1024,
"MaxCacheSizeKiB": 1024,
"MaxIndexBlockSizeKiB": 8192,
"MinSingularSizeKiB": 8192,
"CompressionLevel": -1,
"MaxGoroutines": 1
}Комментарии (32)
bak
18 декабря 2016 в 20:33
+4↑
↓
1) Я правильно понимаю что при большом количестве случайных записей в большие секции (превысившие размер кеша и уже содержащие индекс) у вас на каждую запись будет происходить вычитывание соотвествующего индексного файла, распаковка, добавление записи, запаковка и запись обратно?
2) Вы ведь проводили бенчмарки? Можно увидеть результаты сравнения производительности с другими решениями, хотя бы с тем-же mysql?
ababo
18 декабря 2016 в 20:48
0↑
↓
1. Во избежание фрагментации считывается весь индекс секции целиком (кроме больших файлов, каждый из которых содержат записи для только одного ключа). Но этот эффект сильно смягчается наличием кэшей, а также тем, что записи не сразу пишутся на диск, а группируются по секциям в памяти, и лишь при накоплении заданного объёма сбрасываются на диск.2. К сожалению нет, но существующие SQL-решения (в частности, PostgreSQL) при наличии индекса по ключу неприемлемо замедлялись при миллионах записей (скорость падала в сотни раз). Данное же решение позволило записать несколько миллиардов записей на два сервера (оборудованных SSD) в течение 6-ти дней (половина отведённого времени ушло на парсинг источников данных). За этот срок скорость записи упала на 30%.
-
bak
18 декабря 2016 в 21:36
0↑
↓
1) Ну с кешами уже не всё так плохо. Про фрагментацию — не очень понял. Почему бы не сделать следующий вариант: изначально все записи кладутся в отсортированном виде в один файл. Как только он достигает определенного размера — разбить этот файл пополам. И так всё время разбивать пополам файлы — тогда не будет нужды зачитывать все файлы для вставки / удаления.
2) Какой именно тип индекса пробовали? Какого размера ключи и значения?-
ababo
18 декабря 2016 в 21:44
0↑
↓
1. У меня тот же вариант. Есть максимальный размер индексного файла. Если он превышен, то файл разбивается на два, и т.д. Исключение составляют так называемые сингулярные файлы (файлы с записями одного ключа) — они не дробятся, поскольку всё равно для поиска по этому ключу придётся вычитывать их все. Это серьёзная оптимизация, поскольку индекс перестраивается целиком, а эти файлы остаются нетронутыми.2. Нету никаких алгоритмов, просто массив строк отсортировали и поделили на части с заданным размером, сжали и записали в файлы.
18 декабря 2016 в 21:52
0↑
↓
А я не понял, как вы будете случайные записи складывать в отсортированном виде в один файл? Вы имеете ввиду использовать какую-нибудь индексную структуру, вроде B+ деревьев?-
ababo
18 декабря 2016 в 21:56
0↑
↓
Случайные записи попадают в кэш соотв. секций, т.е. просто добавляются в неотсортированном виде. Когда кэш-файл переполняется секция перестраивается целиком (кроме больших файлов с записями одного ключа).18 декабря 2016 в 21:57
0↑
↓
Этот вопрос был не вам, как у вас сделано я понял. Меня интересует конкретный момент добавления записей в файл в отсортированном порядке.
18 декабря 2016 в 21:49
0↑
↓
Если записи накапливаются в памяти, то при креше все что в памяти сидит потеряется? Или есть какой-то журнал? Какие вообще гарантии в плане персистентности?-
ababo
18 декабря 2016 в 22:02
0↑
↓
Если упадёт, то данные потеряются. Никакого журналирования не предусмотрено.
terrier
18 декабря 2016 в 21:33
+3↑
↓
Миллиард записей, пусть по килобайту — это у нас терабайт.
Гм-гм, велосипедостроение, конечно, почетная и уважаемая отрасль промышленности, но сложно представить себе современную базу данных, которая бы захлебнулась на миллионах/миллиардах записей при хоть сколько либо вменяемых настройках и железе.
Плюс к тому, существующие решения и пишут на диск грамотнее и хранят лучше. То, что вы три дня писали терабайт на SSD как бы намекает на неоптимальность вашего решения. Чисто ради интереса:, а сколько времени ушло на разработку?-
ababo
18 декабря 2016 в 21:40
0↑
↓
В моём случае записи были небольшими, порядка 100–150 байт. Было записано 350GiB с компрессией порядка 20% процентов. -
ababo
18 декабря 2016 в 21:50 (комментарий был изменён)
0↑
↓
Попробуйте записать миллиард записей в базу с индексом. И сразу отпадут все вопросы.18 декабря 2016 в 22:10
+2↑
↓
А чего не смотрели другие решения, LevelDB явно очень хорошо приспособлено для вашей задачи.-
ababo
18 декабря 2016 в 22:27 (комментарий был изменён)
0↑
↓
Не смотрел в его сторону, кажется интересным вариантом. Но, насколько я понял, LevelDB не поддерживает множественные значения на один ключ.18 декабря 2016 в 22:39
+1↑
↓
Это формальность, данные хранятся в сортированных таблицах и их можно искать и по ним итерировать. Потому достаточно добавить timastamp или счеткик к концу ключа и получатся множественные значения.
rotor
19 декабря 2016 в 02:15
0↑
↓
Итераторы в LevelDB делают его очень гибким.
В вашем случае, возможно, стоит еще обратить внимание на RocksDB
Это доработанный LevelDB. Он оптимизирован для SSD и подходит для больших размеров БД. Не нужны лишние конвертирования — можно хранить бинарные данные. Ну и скорость нaaaамного выше. Три дня, что-то уж совсем перебор.
Короче, LevelDB/RocksDB — то что вам нужно.
18 декабря 2016 в 22:26
+2↑
↓
Индекс можно строить уже после записи, мне кажется, у вас проблемы надуманы.-
terrier
18 декабря 2016 в 22:39 (комментарий был изменён)
0↑
↓
А зачем вы активно писали в таблицу с индексом? Я так понимаю, ваш кейс — сначала запишем миллиард записей, потом начинаем оттуда читать. Вывод — дропаем индекс, ставим COPY/BULK INSERT/что--то другое, отключаем autocommit/fsync и д.р., идем на обед или ставим на ночь. Приходим — все закачалось, возвращаем все назад, ставим индекс обратно, радуемся.
Если же вам нужно одновременно И читать, И активно писать, то это надо было делать с разных реплик, конечно же.-
ababo
18 декабря 2016 в 22:49 (комментарий был изменён)
0↑
↓
Это будет эффективнее, но построение индекса на диске для миллиардов записей (это значит, их все отсортировать, причём на диске, так как памяти не хватит) кажется не слишком практичной задачей. Кроме того, придётся писать их без компрессии, что потребует в 6–10 раз большего объёма.
ibKpoxa
18 декабря 2016 в 22:52
+2↑
↓
Писал и неоднократно, базы по 2–3 тб на mysql с записями по 50 байт с 4–5 индексами, полет нормальный.-
ababo
19 декабря 2016 в 00:29
0↑
↓
Значит, ваши 4–5 индексов съели 90% процентов объёма базы. Сколько записей выходило?
18 декабря 2016 в 22:29 (комментарий был изменён)
+3↑
↓
Не вполне понятно, для чего эта статья.
О том, как раскидать миллиард записей по файлам? Так это почти тривиально не такая уж сложная задача.
Предоставить сообществу код? Но тогда хотелось бы видеть лицензию и комментарии в коде (единственный — комментарий репозитория «Key/value (s) database capable for effective storage of billions of records» — мало о чём говорит). Вообще, текущая ревизия — неплохой пример того, что т. н. «самодокументируемый код» плохо понятен. Описание «алгоритмов» тоже не слишком подробно.
И самое главное — где результаты замеров скорости записи и поиска? Сколько ключей, сколько записей на один ключ, какой их объём?
Интересно было бы увидеть скорость с использованием других ФС и других алгоритмов сжатия. gzip всё-таки не самый быстрый (и не самый сильный) компрессор.Тема интересна, но освещена недостаточно подробно.
-
ababo
18 декабря 2016 в 22:40
+1↑
↓
Добавил MIT-лицензию. -
ababo
18 декабря 2016 в 23:02 (комментарий был изменён)
0↑
↓
Скорость выборки по ключу с малым числом записей на базе объёмом в 350GIB (записи размером 100–150 байт) — единицы сотых секунды (например, для ключа с сотней выбранных записей — 0.015s).-
bak
18 декабря 2016 в 23:46
0↑
↓
0.015 секунд — это время извлечения всех 100 записей с заданным ключем?-
ababo
18 декабря 2016 в 23:58
0↑
↓
да
leventov
18 декабря 2016 в 23:34
+2↑
↓
К такому количеству записей существующие SQL/NoSQL системы хранения оказались плохо приспособлены
Неубедительно. Приведите сравнение по скорости с каким-нибудь MySQL/PostgreSQL, храня значение в листовой колонке, и документной базой типа Couchbase.
Luchnik22
18 декабря 2016 в 23:41
+1↑
↓
А как насчёт параллельной записи? Что если запустить несколько копий приложения, которые будут добавлять значения одновременно, не сломается ли эта конструкция?Чаще всего такие кейсы «миллиард записей» требуют многопоточных или распределённых по не скольким машинам приложений.
-
ababo
18 декабря 2016 в 23:42 (комментарий был изменён)
0↑
↓
Система поддерживает параллельность на уровне секций — можно задать число потоков, на которые будет распределяться задача добавления данных по секциям. На практике это здорово ускоряет процесс записи.-
Luchnik22
18 декабря 2016 в 23:56
–1↑
↓
В принципе выглядит вкусно, нужен бенчмарк Mastore vs Redis vs PostgreSQL, чтобы точно знать)-
leventov
19 декабря 2016 в 00:00 (комментарий был изменён)
+3↑
↓
Redis-то тут при чем? Он в памяти, решение автора на диске
grossws
19 декабря 2016 в 04:07
0↑
↓
Я б предложил сравнивать с:
- чем-нибудь из классических rdbms (MySQL/MariaDB, Postregsql);
- чем-нибудь из kv движков (LevelDB, Kyoto Cabinet, lmdb);
- чем-нибудь имеющим lsmt внизу, например Apache Cassandra.
