SQLite со встроенным онлайн-сжатием

Это экспериментальный мод Sqlite со встроенной поддержкой онлайн-сжатия. Проектирование и реализация обсуждаются, ограничения и критерии , предусмотренные и исходный код, а также DLL предварительно построенном будут включены .

Фон

И Sqlite, и MySql поддерживают сжатые (и зашифрованные) базы данных. Ну, более или менее. Поддержка Sqlite ограничена базами данных только для чтения, которые сжимаются в автономном режиме, в то время как поддержка MySql ограничивается сжатием строк (насколько я могу судить).

Работая над WikiDesk , браузерным проектом в Википедии, я знал, что база данных может легко вырасти до сотен гигабайт. Выбор базы данных здесь Sqlite из-за его компактности и мобильности. Английский дамп Википедии уже находится в диапазоне от 100 до 1000 гигабайт (в зависимости от типа дампа). WikiDesk поддерживает не только разные языки Википедии, но и различные проекты, такие как Викиновости, Викиучебники и Викисловарь, среди многих других во всех доступных. языки, все в одной базе данных. Теоретически можно импортировать весь возможный контент вики в одну базу данных.

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

Часть меня была счастлива, что не нашла прецедентного проекта. Я был более чем счастлив закатить рукава и заняться хакингом.

Очевидный подход — тот, который используется MySql, а именно для сжатия полей независимо. Это просто и условно говоря прямо. Однако это будет означать, что LIKE не может быть использован для сжатых строковых полей. Сортировка и сортировка и другие функции также будут отсутствовать. На самом деле, поля, о которых идет речь, вообще не могут быть текстовыми. Кроме того, нужно было явно сжать поля, запомнить, какие из них сжаты, и не забыть распаковать их перед использованием. Я думал, что очень ограничен и, вероятно, не стоил бы усилий. Другой подход заключается в том, чтобы сделать это на низком уровне, чтобы он был прозрачным для вызывающей стороны. Такое расширение к Sqlite существует, но это не принесет большого выигрыша на небольших полях. Я подозреваю, что сжатие NTFS даст лучшие результаты.

NTFS имеет встроенную поддержку сжатия. Это стоило того, чтобы его протестировать. В английском дампе SimpleWiki я мог сжать файл базы данных примерно до 57% от его первоначального размера (см. Тесты ниже.) Довольно неплохо. Однако я не мог контролировать это вообще. Я не мог установить размер чанка, уровень сжатия или что-либо еще, кроме как включить и отключить его. Кроме того, пользователь может отключить его и потерять все преимущества. Сжатие на уровне базы данных является более перспективным. Аналогичный результат может быть достигнут с помощью FuseCompress или compFUSEd (в Linux), хотя пользователь должен сначала установить такую ​​файловую систему.

Главная проблема файлов базы данных в том, что касается оперативного сжатия, заключается в том, что логическая структура базы данных обычно хранит указатели на смещения файлов, так что между физической и логической структурами существует однозначное сопоставление. Это разумно, поскольку база данных — это действительно большая и сложная структура данных на диске (в отличие от памяти). Узлы btree или rtree обычно являются индексами страниц, где все страницы имеют предопределенный фиксированный размер для всей базы данных. Нарушение этой структуры приведет к повреждению файла. Назначение страниц фиксированного размера — упростить распределение и управление пространством. Эта схема также используется как менеджерами памяти, так и менеджерами дисков.

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

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

Девиз «быть ленивым», кажется, хорошо работает для программистов, которые ориентированы на эффективность и ненавидят повторяющиеся и подверженные ошибкам работы. Каков был бы самый простой подход, который мог бы работать? Возвращаясь к NTFS, можно извлечь один или два урока по прозрачному сжатию. Секрет в том, что NTFS может просто выделить любой свободный инод на диске, записать на него сжатые данные и обновить таблицу индексов. Иноды — это связанные списки, поэтому вставлять / удалять и изменять цепочку очень просто. Файлы, с другой стороны, являются массивами байтов, абстрагированных от структуры диска. Перемещение битов в массиве намного сложнее и занимает больше времени, чем обновление узлов в связанном списке.

Что необходимо, так это преимущество файловой системы, применяемой на уровне файлов.

Что если бы мы могли сказать файловой системе, что эти области свободного пространства файла действительно не используются? NTFS поддерживает разреженные файлы в дополнение к сжатым файлам. Это может быть использовано в наших интересах. Все, что нам нужно сделать, это пометить свободное место на каждой странице как неиспользуемое, и файловая система сделает их доступными для других файлов на диске, уменьшая используемое сетевое дисковое пространство базы данных.

Sqlite поддерживает страницы длиной 512-65535 байт. Поскольку мы не можем разбить одну страницу, минимальный размер сжатия должен быть не менее 64 Кбайт. Кроме того, кажется , что единица сжатия NTFS также составляет 64 Кбайт. Это означает, что разреженный диапазон должен быть по меньшей мере таким же, как и единица сжатия, которая должна быть удалена с диска и помечена как свободная. Это накладывает явное ограничение на количество сбережений, которые мы можем достичь, используя этот дизайн; Сжатие не сэкономит дисковое пространство, если не уменьшит размер в 64 Кбайт. В качестве единицы сжатия используется кратное 64 Кбайт, внутренне называемое чанком . Действительно, размер фрагмента в 64 Кбайт был бы абсолютно бесполезным, поскольку не было никакой экономии вообще.

Когда данные записываются, они сначала записываются в буфер памяти. Этот буфер используется для отслеживания изменений в чанке, его смещения в файле и использования для сжатия данных. Когда блок требует очистки, данные сначала сжимаются, а сжатые данные записываются в смещение фрагмента. Остальная часть фрагмента помечена как разреженная область. NTFS освобождает любые естественно скомпонованные блоки сжатия, которые являются полностью разреженными. Частично записанные блоки физически размещаются на диске, а 0-значные байты записываются на диск.

При считывании данных считывается, распаковывается полный фрагмент запрошенного байтового смещения, и из буферизованных данных запрошенные байты копируются обратно в вызывающую сторону. Разреженные байты прозрачно считываются как 0-значные байты. Это делается NTFS и освобождает нас от отслеживания редких регионов.

Первоначально очень быстрые библиотеки сжатия использовались, чтобы не жертвовать слишком большой производительностью. FastLz, Lz4 и MiniLzo были протестированы, но результаты были не очень многообещающими, с точки зрения сжатия. В качестве таковой текущая сборка использует Zlib .

Мод сжатия написан как VFS Shim . Преимущество этого состоит в том, что вы избегаете любых модификаций базы кода Sqlite.

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

int sqlite3_compress(
    int trace,
    int compressionLevel
    );

trace может иметь значение от 0 до 7. Когда трассировка 0 отключена, большие значения позволяют отслеживать операции все более низкого уровня. Журналы трассировки записываются в stderr. -1 по умолчанию.

Уровень сжатия может принимать значение от 1 до 9, где 1 дает максимальную производительность за счет степени сжатия, а 9 — лучшее сжатие за счет производительности. -1 по умолчанию, как правило, уровень 6.

Чтобы включить сжатие, эта функция просто вызывается перед вызовом sqlite3_open. Уровень сжатия может изменяться между запусками, однако, если фрагмент не будет изменен, данные не будут повторно сжаты с новым уровнем.

Сжимается только основная база данных. Журнал или любые другие временные файлы не сжимаются.

Загрузите код и готовую DLL . Это sqlite3.dll представляет собой объединение версии 3.7.7.1, созданное с настройками / флагами по умолчанию из объединения, созданного из исходных файлов исходной конфигурацией и созданием файлов. Код сжатия добавляется, и он построен с использованием VS2010 Sp1 и статически нравится библиотекам времени выполнения, поэтому не имеет никаких зависимостей.

Чтобы создать код, сначала загрузите последнюю версию Sqlite. Объединение 3.7.7.1 идеально. Последнее Zlib также должно быть загружено и построено.

Добавьте заголовки Zlib к пути включения, скопируйте файл vfs_compress.c рядом с источниками sqlite и выполните сборку. Затем создайте объединение sqlite3.c (или исходные источники) и свяжите двоичные файлы sqlite3, vfs_compress и Zlib для создания исполняемого файла.

From http://blog.ashodnakashian.com/2011/09/sqlite-with-built-in-online-compression/