Хотя в SQLite и нет возможности прочитать удаленные данные после завершения транзакции, сам формат файла позволяет отчасти сделать это. Подробности — под катом.

Данная статья возникла как результат прикручивания еще одной фичи для моего проекта sqlite-gui. Поначалу я думал ограничиться встраиванием undark, но он падал с ошибкой на тестовых базах, и потому я решил разобраться в вопросе получше.

Важно понимать, что восстановление возможно только когда значения прагм secure_delete и auto_vacuum равны 0. Обработка BLOB-полей, файлов журналов, индексов и таблиц без rowid осталась за рамками статьи.

Если требуется только восстановить поврежденную базу, то достаточно воспользоваться командами .recover и .dump в SQLite CLI. Имейте в виду, что сообщение о поврежденной базе может выводиться, если она зашифрована и указаны неверный метод шифрования, пароль или другие параметры.

Прежде чем перейти непосредственно к теме статьи, необходимо рассмотреть строение файлов SQLite. Файл базы поделен на части, называемыми страницами (page). Чтение и запись в файл ведется целыми страницами. Все страницы пронумерованы, начиная с 1, и имеют одинаковый размер, задаваемый в заголовке файла, который располагается в первых 100-байтах (и соответственно на первой странице). Некоторые значения заголовка приведены ниже, а полный список доступен здесь.
Данные в файле записываются в прямом порядке (big-endian), то есть два последовательных байта 0B 03 представляют число B03₁₆ = 11 * 16² + 16⁰ * 3₁₀ = 2819₁₀.
Пример заголовока файла в HEX-редакторе

Данные таблиц хранятся в виде сбалансированных деревьев (B⁺-tree), где вершины разделены на две группы — внутренние (interior) и листья (leaf/leaves). Строение страниц у групп различно из-за разного назначения: внутренние хранят иерархию, а листья — данные. Индексы и таблицы без rowid хранятся в сбалансированных деревьях (B-tree), у которые для обоих типов вершин используют структуру аналогичную внутренним страницам B⁺-tree. Если данные, напр. длинный текст или BLOB, не помещаются полностью на страницу, то они переносятся на страницы переполнения (overflow pages), организованные в лист, где первые 4 байта такой страницы указывают номер следующей в листе. Учет неиспользуемого (резервного) места ведется с помощью списка свободных страниц (free list), которые также делятся на корневые (trunk) и листья (leaf). Дополнительные данные для работы операций auto_vacuum и incremental_vacuum хранятся на страницах указателей (pointer map или ptrmap pages). Файлы, размер которых превышает 1Гб, имеют одну дополнительную страницу блокировок (lock-byte), располагающуюся всегда на 1073741824 байте и имеющую размер 512 байт. Для восстановления данных достаточно рассмотреть строение страниц у таблиц и списка свободных.

Свободные страницы (free list)

После массового удаления строк, размер базы данных остается прежним, поскольку гораздо дешевле с точки зрения ввода-вывода пометить страницы как пустые (иначе говоря поместить в список свободных), чтобы потом, когда потребуется место для сохранения новых данных, использовать их, а сдвигать на освободившееся место данные, чтобы уменьшить размер файла, как это делает команда VACUUM, удаляющая все свободные страницы из базы, и для больших таблиц занимающая значительное время. Эти страницы хранятся в виде связанного списка корневых (trunk) страниц, где каждая страница в первых 4-х байтах (INTEGER) хранит ссылку (номер) на следующую корневую (или ноль, если больше страниц нет), в следующих 4-х байтах число листьев и далее список номеров этих страниц (по 4 байта на номер).

Организация списка свободных страниц (freelist) в SQLite

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

B/B⁺-tree страницы

На каждой странице хранятся данные только одного и того же объекта; каждый объект имеет ровно одну стартовую страницу (корень дерева), которая уже содержит ссылки уже на другие.

Первая страница базы данных используется как корневая страница специальной таблицы sqlite_master (она же sqlite_schema), содержащей перечень всех объектов базы данных (их тип, имя, DDL-создания), а для таблиц и индексов еще и номер их корневой страницы. Эта страница по содержимому меньше обычной на 100 байт, поскольку содержит еще и заголовок файла, и ее заголовок располагается на 100 байте, а не нулевом. Для обработки первой страницы стоит иметь в виду, что все сдвиги (offsets) указываются от начала страницы, а не начала заголовка страницы.

Заголовок B/B⁺-tree страницы имеет следующую структуру
Таким образом, длина заголовка 8 байт для листьев и 12 для внутренних страниц. Сразу после заголовка идет массив по два байта, на каждую хранимую ячейку на странице, где хранится положение этой ячейки на странице. Хотя это и может быть вычислено по заголовку и последовательному перебором ячеек. Обратите внимание, что ячейки записываются с конца, поднимаясь вверх в незанятую область.
Общий вид B/B⁺-tree страницы

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

Тип данных varint

Прежде чем продолжить описание B/B⁺-tree страниц, стоит рассмотреть как SQLite кодирует целочисленные значения, что позволяет, в зависимости от величины значения, хранить его в виде последовательности от 1 до 9 байт, а не обычных фиксированных 4-х байт, и таким образом экономить место.
Как легко видеть числа от 0 до 127 (2⁷ — 1) требуют для хранения 1 байт, от 128 до 16383 (2¹⁴ — 1) — два байта и так далее. Обратной стороной медали является то, что любое отрицательное число требует 9 байт. Минимальное целое число представляется как C0 80 80 80 80 80 80 80 80, а максимальное отрицательное, т.е. -1, как FF FF FF FF FF FF FF FF FF. Алгоритм получения значения по его позиции предполагает побайтное чтение пока не будет обнаружен ведущий ноль (значение байта менее 128) или не прочитано 9 байт.

Внутренние (interior) страницы

Данные страницы хранят иерархию, где каждая ячейка — это пара, состоящая из номера страницы (4 байта) и ключа (varint, для таблицы ключ — это идентификатор строки rowid). При этом ячейки отсортированы по ключу. Принцип поиска по дереву следующий: допустим требуется найти на какой странице хранится строка с rowid равным N. Если первая страница листовая, т.е. таблица помещается на один лист целиком, то поиск выполняется сразу на ней, перебором ячеек и сравнения их rowid с N. Если первая страница внутренняя, то выполняется проход по ячейкам страницы и ищется первая такая, что ее ключ (rowid) больше N. Если такая ячейка найдена, то выполняется переход на страницу, по номеру хранящемуся в первых 4-х байтах ячейки. Если же не найдено, то выполняется поиск на странице, указанной в последних байтах заголовка. И так до тех пор, пока не будет совершен переход на листовую страницу.

Если определение первичного ключа таблицы отлично от INTEGER PRIMARY KEY, когда например ключ составной или тестовый, то таблица использует автосгенерированный rowid, и потому для получения строки по ключу, сначала ищется её rowid в индексном дереве, а потом уже в дереве таблицы.

Листовые (leaf) страницы

Каждая ячейка (строка таблицы) состоит из набора: размер всех данных ячейки в байтах, идентификатор строки rowid, размер блока, где заданы типы хранимых значений по столбцам, включая в размер и это поле, сам блок состоящий из N-значений, задающих типы, а потом все N-значений без каких либо разделителей. Если всё значения не влезли, то в конце добавляется 4-х байтное поле, содержащее номер страницы, где хранится остальное (Overflow page). При этом размеры указываются такими, как если бы размер страницы был неограничен. Размер ячейки и заголовка строки, rowid, а так же типы, отвечающие строкам и BLOB, записываются как varint. Сами данные записываются как есть в big-endian порядке.

Состав ячейки на листе B⁺-tree


Кодирование типа значения, подбираемого по записываемой величине
Если в таблице есть первичный ключ, то его значение будет использоваться как rowid, а тип этого значения в заголовке строки будет указан как NULL, и, соответственно, в данных это поле будет пропущено.

Пример ячейки на листе B⁺-tree

При удалении строки занимаемое место помечается как пустое, путем изменения первых 4 байт ячейки: в первые два записывается расстояние от начала страницы до следующего пустого блока и 00 00, если этот блок последний, а в следующие два — полный размер пустого блока. При этом, если удаляемая строка одним из концов примыкала к свободному блоку, то образуется один блок и

• Если свободный блок был слева, то все байты строки остаются неизменными, а изменяются вторые 2 байта блока, увеличивая длину на длину удаленной строки
• Если свободный блок был справа, то в первые два байта строки будут записаны первые два байта из блока (позиция следующего свободного блока), а во вторые два — сумма длин удаленной строки и блока
• Если примыкающий блок имел длину менее трех байт, то первые 2 байта образованного блока будут содержать позицию следующего свободного.

Пример трех удаленных строк, две из которых были соседними.
Образовалось два свободных блока. Начало большего, состоящего из оранжевого и маджента?, содержит позицию меньшего, выделенного желтым цветом. По указателю на желтый блок, можно утвержать, что сначала была удалена желтая строка, потом маджента, а после — оранжевая.

Если на странице удаляются все строки, то она переносится в список свободных (корневую или листовую). Перенос страниц происходит также при удалении самой таблицы. При обновлении данных, когда места для новых значений не достаточно, старое место на странице помечается как свободное, и добавляется строка с новыми значениями и старым номером строки (rowid).

Восстановление удаленных строк

Поскольку свободная страница, когда начинает использоваться, напр. для хранения индекса или переполнения, предварительно очищается, то поиск удаленных данных можно ограничить листьями таблиц (незанятое место и свободные блоки) и свободными страницами (корневыми и листовыми). Если прагма secure_delete равна fast, то данные в освобождающихся блоках на листьях таблиц затираются нулями, но перенос листа таблицы в список свободных остается неизменным и потому данные на свободных страницах могут быть восстановлены.

После удаления таблицы командой DROP страницы этой таблицы переносятся в список свободных как есть. Аналогично происходит при выполнении DELETE, если в результате удаляются все строки страницы (за исключением первой страницы таблицы, которая даже будучи пустой, не будет добавлена в список свободных). В случае, если страница попадает в листовые списка свободных, то это самый простой случай и она может быть прочитана как обычный лист таблицы. В случае, если она стала корневой, то необходимо оценить объем занятого места. Если он незначителен, то возможно сохранился список позиций ячеек (или его часть) на странице и потому часть данных также можно прочитать.

Самый наивный и простой способ восстановить данные из блока — это последовательно читать байты, и пытаться декодировать данные, считая, что текущий байт — это начало ячейки. Если это удалось сделать без ошибок (все типы в заголовке строки не равны 10 и 11 и, если есть текстовое поле, то все его данные действительно текст, заданной в заголовке длины), значит скорее всего такая строка была. Строки с поврежденным заголовком (строки) при этом найдены не будут.

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

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

Сначала надо вывести заголовок строки в «обобщенном» виде, т.е. как строку вида itt, где i соотвествует любому целочисленному типу, t — текстовому полю, f — значению с плавающей точкой, n для NULL и ? для BLOB. Для блока с листовой страницы таблицы, данная строка может быть восстановлена из DDL таблицы, для блока с свободной страницы или страниц таблицы, у которой в DDL типы не указаны, по неповрежденной строке (или строкам). Поскольку у каждой строки на странице обобщенный заголовок один и тот же, то можно попробовать найти такую обобщенную строку, что для нее на странице найдется максимальное количество блоков, которые при перекодировании дадут эту строку, и предположить её заголовком.

После того, как «обобщенный» заголовок определен можно попробовать найти его положение в данных, последовательно двигаясь с начала блока до тех пор пока декодирование не даст этот заголовок. Если это не удалось или декодирование строки дает некорректный результат, то отбросить первый тип и попробовать снова. Понятно, что чем меньше «обобщенный» заголовок содержит типов, тем больше вероятность обнаружить не сам заголовок, а случайные данные. Более того, типы такого заголовка могут не полностью совпадать с типами в конкретной строке, т.к. SQLite подбирает тип по значению, и потому для числа 111.0 тип будет не 0x07 (float), а 0x01 (int8). Аналогичное несовпадение типов будет и для NULL-значений.

Если заголовок был найден без первого типа, то требуется восстановить этот тип, чтобы понять сколько первых байт он занимает в данных строки. В зависимости от того к какому обобщенному типу принадлежал отсутсвующий

1. (только для листовой страницы таблицы) Если n, т.к. в DDL таблицы первая колонка имеет в определении INTEGER PRIMARY KEY, и потому значение хранится в rowid, то и число занимаемых байт 0, т.е. значения в данных строки хранятся начиная со второго.
2. Если f, то тип первого значения должен быть 0x7, т.е. первые 8 байт — это первое значение. Однако, если хранимое значение целое, то оно использовало целочисленный тип, размер которого от 1 до 8 байт, и потому здесь может возникнуть ошибка восстановления.
3. Если t, то длину значения можно вычислить, выделив текстовый блок (см. ниже). Если длина получилась больше 67, то в таком случае она должна была быть записана несколькими байтами, и все эти байты, кроме первого, должны обнаружиться в заголовке.
4. Если i, то это самый сложный случай, поскольку значение может занимать 1, 2, 3, 4, 6 или 8 байт. Если в заголовке есть текстовый тип, то можно локализовать его значение и по вычисленной длине найти позицию в заголовке, а потом восстановить значения справа налево (оставшееся число байт — это и будет неопределенное первое значение). Иначе, можно попробовать найти конец текущей удаленной строки, воспользовавшись тем, как изменяются заголовки строк при удалении, и также восстановить значения справа налево.

Отмечу, что на свободных страницах, используемых ранее для индекса, содержится информация в виде список проиндексированных значений + rowid. Поскольку rowid при удалении зачастую повреждается, то для восстановления строк индекс не слишком подходит, но вот для получения дополнительных текстовых данных вполне.

Описание последовательности действий при восстановлении данных

1. Прочитать sqlite_master, чтобы определить список таблиц и для каждой таблицы корневую страницу и обобщенный тип.
2. Для каждой таблицы выполнить обход иерархии по внутренним страницам и получить листовые.
3. На каждом листе выполнить поиск как в незанятом пространстве, так и в свободных блоках между хранимыми ячейками.
4. Построить список свободных страниц.
5. Проверить являются свободные листовые страницы бывшими листовыми страницами таблицы. Обработать их, если данные страницы не противоречивы. Дополнительно можно выполнить поиск в свободном месте страниц.
6. Выполнить поиск на корневых свободных страницах, если удастся предположить обобщенный заголовок.

Множество нюансов, которые следует учитывать, делают восстановление данных не слишком простой задачей, требующей скрупулезности. Потому в итоге, я решил ограничиться отдельной утилитой проверяющей концепцию, sqlite-unhide с возможной доработкой в дальнейшем, если найдутся желающие проспонсировать разработку. Исходники пока раскрывать не стал. Для отладки использовались набор эталонных баз от Nemetz (папка 0С) и SQLiteExplorer.

Дополнительные материалы

1. Официальный сайт SQLite
   Database File Format
2. Sangjun Jeon, Jewan Bang, Keunduck Byun, Sangjin Lee, 2011
   A recovery method of deleted record for SQLite database
3. Christian Meng, Harald Baier, 2019
   bring2lite: A Structural Concept and Tool for Forensic Data Analysis and Recovery of Deleted SQLite Records
   Утилита bring2lite
4. Paul Sanderson, 2018 (по отзывам — одна из лучших книг по теме; я её достать не смог)
   SQLite Forensics
5. Dirk Pawlaszczyk, Christian Hummert, 2020
   Making the Invisible Visible – Techniques for Recovering Deleted SQLite Data Records
   Утилита FQLite
6. Ramisch Felix, Rieger Martin, 2015
   Recovery of SQLite Data using expired Indexes
7. Paul Daniels, 2016
   Утилита Undark
   Моя модификация с фиксом
8. D. Richard Hipp, 2015
   SQLite The Databaseology Lectures
9. Sebastian Nemetz, Sven Schmitt, Felix Freiling, 2018
   A standardized corpus for SQLite database forensics
   Набор эталонных баз для тестирования
10. Утилиты для просмотра базы данных постранично в HEX-формате
    SQLiteExplorer (сыровата, но HEX-режим хорош)
    SysTools SQLite Viewer и клоны (базовый HEX-режим и просмотр удаленных строк).
    showdb (консольная, одна из стандартных SQLite утилит)