Постановка задачи

В одном из прошлых проектов мне была поставлена задача написания системы для хранения миллиардов записей. Доступ к данным должен осуществляться по ключу: одному ключу в общем случае соответствует множество (на практике, вплоть до десятков миллионов) записей, которые могут добавляться, но не модифицироваться или удаляться.

К такому количеству записей существующие SQL/NoSQL системы хранения оказались плохо приспособлены, поэтому клиент предложил с нуля разработать специализированное решение.

Выбранный подход

После серии опытов был выбран следующий подход. Данные в базе распределены по секциям, каждая из которых представляет собой файл или директорию на диске. Секции соответствует значение CRC16-хеша, т.е. возможно всего 65,636 секций. Практика показывает, что современные файловые системы (тестировалась ext4) достаточно эффективно справляются с таким количеством элементов внутри одной директории. Итак, добавляемые записи хешируются по ключу и распределяются по соответствующим секциям.

Каждая секция состоит из кэша (файл, в котором накапливаются неупорядоченные записи вплоть до заданного размера) и индекса (набора сжатых файлов, хранящих упорядоченные по ключу записи). Т.е. предполагается следующий сценарий работы:

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

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

Подробный алгоритм добавления записей в секцию

1. Если размер добавляемых записей в сумме с размером кэш-файла меньше заданного максимального объёма, то записи просто добавляется в кэш-файл, и на этом обработка секции завершена.
2. Иначе содержимое кэш-файла, а также индексные файлы читаются (исключая файлы с размером больше заданного лимита) и добавляется к обрабатываемой секции.
3. Секция сортируется по значению ключа.
4. Создаётся временная директория, в которую будут записаны новые индексные файлы.
5. Отсортированный массив записей делится на равные части (без разрыва записей) заданного размера (но с разными именами, в противном случае файл растёт до нужного размера, игнорируя лимит) и записываются в gzip-компрессированные индексные файлы. Каждый такой файл имеет имя _url_encoded<ключ>_XXXX, где ключ — это ключ первой записи содержимого файла, а XXXX — 4 16-ричных разряда (нужны для различения файлов с одним значением ключа при сохранении лексикографического порядка именования). XXXX равен 0000, если в директории секции нет файла с таким именем, иначе 0001, и т.д.
6. Для всех файлов, с именами которых возникли коллизии (и пришлось увеличивать XXXX) создаём твёрдые ссылки во временной директории.
7. Удаляем старую директорию секции и переименовываем временную на её место.

Как пользоваться

Mastore (от massive storage) написан на Golang и собирается в исполняемый файл, запускаемый в режиме чтения, записи или самотестирования. Будучи запущенным в режиме записи Mastore читает из stdin текстовые строки, состоящие из ключа и значения, разделённых символом табуляции (для бинарных данных можно использовать дополнительное кодирование, например, Base85):

mastore write [-config=<config>]

Для чтения записей по заданному ключу используется следующая команда:

mastore read [-config=<config>] -key=<key>

А для получения списка всех ключей:

mastore read [-config=<config>] -keys

Mastore конфигурируется с помощью JSON-файла. Вот пример конфигурации по-умолчанию:

{     "StorePath": "$HOME/$STORE",     "MaxAccumSizeMiB": 1024,     "MaxCacheSizeKiB": 1024,     "MaxIndexBlockSizeKiB": 8192,     "MinSingularSizeKiB": 8192,     "CompressionLevel": -1,     "MaxGoroutines": 1 }

ссылка на оригинал статьи https://habrahabr.ru/post/317874/