Обзор
Данный документ описывает формат файлов I2P blockfile и таблицы в hostsdb.blockfile, используемые службой имен Blockfile NAMING .
Блочный файл обеспечивает быстрый поиск Destination в компактном формате. Хотя накладные расходы на страницы блочного файла существенны, destinations хранятся в бинарном формате, а не в Base 64, как в формате hosts.txt. Кроме того, блочный файл предоставляет возможность хранения произвольных метаданных (таких как дата добавления, источник и комментарии) для каждой записи. Метаданные могут использоваться в будущем для предоставления расширенных возможностей адресной книги. Требования к хранилищу блочного файла незначительно превышают формат hosts.txt, при этом блочный файл обеспечивает примерно 10-кратное сокращение времени поиска.
Blockfile — это просто дисковое хранилище нескольких отсортированных карт (пар ключ-значение), реализованное как списки с пропусками. Формат blockfile заимствован из базы данных Metanotion Blockfile Database METANOTION . Сначала мы определим формат файла, затем рассмотрим использование этого формата службой BlockfileNamingService.
Формат файла блоков
Оригинальная спецификация blockfile была изменена для добавления магических чисел на каждую страницу. Файл структурирован в виде страниц размером 1024 байта. Страницы нумеруются начиная с 1. “Суперблок” всегда находится на странице 1, т.е. начиная с байта 0 в файле. Метаиндекс skiplist всегда находится на странице 2, т.е. начиная с байта 1024 в файле.
Все 2-байтовые целочисленные значения являются беззнаковыми. Все 4-байтовые целочисленные значения (номера страниц) являются знаковыми, и отрицательные значения недопустимы. Все целочисленные значения хранятся в сетевом порядке байтов (big endian).
База данных спроектирована для открытия и доступа одним потоком. BlockfileNamingService обеспечивает синхронизацию.
Формат суперблока
| Byte | Contents | Description |
|---|---|---|
| 0-5 | Magic number | 0x3141de493250 ("1A" 0xde "I2P") |
| 6 | Major version | 0x01 |
| 7 | Minor version | 0x02 |
| 8-15 | File length | Total length in bytes |
| 16-19 | First free list page | |
| 20-21 | Mounted flag | 0x01 = yes |
| 22-23 | Span size | Max number of key/value pairs per span (16 for hostsdb). Used for new skip lists. |
| 24-27 | Page size | As of version 1.2. Prior to 1.2, 1024 is assumed. |
| 28-1023 | unused |
| Byte | Contents | Description |
|---|---|---|
| 0-7 | Magic number | 0x536b69704c697374 "SkipList" |
| 8-11 | First span page | |
| 12-15 | First level page | |
| 16-19 | Size | Total number of keys - may only be valid at startup |
| 20-23 | Spans | Total number of spans - may only be valid at startup |
| 24-27 | Levels | Total number of levels - may only be valid at startup |
| 28-29 | Span size | As of version 1.2. Max number of key/value pairs per span. Prior to that, specified for all skiplists in the superblock. Used for new spans in this skip list. |
| 30-1023 | unused |
Все уровни имеют диапазон. Не все диапазоны имеют уровни.
| Byte | Contents | Description |
|---|---|---|
| 0-7 | Magic number | 0x42534c6576656c73 "BSLevels" |
| 8-9 | Max height | |
| 10-11 | Current height | |
| 12-15 | Span page | |
| 16- | Next level pages | 'current height' entries, 4 bytes each, lowest first |
| remaining | unused |
Структуры ключ/значение сортируются по ключу внутри каждого диапазона и во всех диапазонах. Структуры ключ/значение сортируются по ключу внутри каждого диапазона. Диапазоны, кроме первого диапазона, не могут быть пустыми.
| Byte | Contents | Description |
|---|---|---|
| 0-3 | Magic number | 0x5370616e "Span" |
| 4-7 | First continuation page | or 0 |
| 8-11 | Previous span page | or 0 |
| 12-15 | Next span page | or 0 |
| 16-17 | Max keys | 16 for hostsdb |
| 18-19 | Size | Current number of keys |
| 20-1023 | key/value structures |
| Byte | Contents | Description |
|---|---|---|
| 0-3 | Magic number | 0x434f4e54 "CONT" |
| 4-7 | Next continuation page | or 0 |
| 8-1023 | key/value structures |
Длины ключей и значений не должны разделяться между страницами, т.е. все 4 байта должны находиться на одной странице. Если места недостаточно, последние 1-3 байта страницы остаются неиспользованными, а длины будут располагаться со смещением 8 в продолжающей странице. Данные ключей и значений могут разделяться между страницами. Максимальные длины ключей и значений составляют 65535 байт.
| Byte | Contents |
|---|---|
| 0-1 | key length in bytes |
| 2-3 | value length in bytes |
| 4- | key data |
| value data |
| Byte | Contents | Description |
|---|---|---|
| 0-7 | Magic number | 0x2366724c69737423 "#frList#" |
| 8-11 | Next free list block | or 0 if none |
| 12-15 | Number of valid free pages | in this block (0 - 252) |
| 16-1023 | Free pages | 4 bytes each, only the first (valid number) are valid |
| Byte | Contents | Description |
|---|---|---|
| 0-7 | Magic number | 0x7e2146524545217e "~!FREE!~" |
| 8-1023 | unused |
Таблицы службы имен Blockfile
Таблицы, создаваемые и используемые BlockfileNamingService, следующие. Максимальное количество записей на промежуток составляет 16.
Список пропуска свойств
%%__INFO__%% — это главный skiplist базы данных с записями ключ/значение String/Properties, содержащий только одну запись:
info - Properties (UTF-8 String/String Map), сериализованный как Mapping :
- version - “4”
- created - Java long время (мс)
- upgraded - Java long время (мс) (начиная с версии базы данных 2)
- lists - Список баз данных хостов, разделенный запятыми, которые должны быть просмотрены по порядку при поиске. Почти всегда “privatehosts.txt,userhosts.txt,hosts.txt”.
- listversion_* - Версия каждой базы данных в списках, например: listversion_hosts.txt=4. Используется для определения частичного или прерванного обновления отдельных списков. (начиная с версии базы данных 4)
Список пропусков обратного поиска
%%__REVERSE__%% — это skiplist обратного поиска с записями ключ/значение типа Integer/Properties (начиная с версии базы данных 2):
- Ключи skiplist являются 4-байтовыми целыми числами, первые 4 байта хэша Destination .
- Значения skiplist представляют собой Properties (карта UTF-8 строк), сериализованная как Mapping
- В свойствах может быть несколько записей, каждая из которых является обратным отображением, поскольку для данного destination может быть более одного имени хоста, или могут возникнуть коллизии с одинаковыми первыми 4 байтами хэша.
- Каждый ключ свойства является именем хоста.
- Каждое значение свойства является пустой строкой.
Списки пропуска hosts.txt, userhosts.txt и privatehosts.txt
Для каждой базы данных хостов существует skiplist, содержащий хосты для этой базы данных. Обратите внимание, что формат версии 4 поддерживает несколько Destination для каждого имени хоста. Этот формат был введен в релизе I2P 0.9.26. Базы данных версии 3 автоматически мигрируют в версию 4.
Ключи/значения в этих списках с пропусками следующие:
key - строка UTF-8 (имя хоста)
value - - База данных версии 4: DestEntry, который представляет собой однобайтовое число пар Свойства/Назначение, которые следуют далее. Это количество пар: Свойства (UTF-8 карта Строка/Строка), сериализованные как Mapping , за которыми следует бинарное Destination (сериализованное обычным образом). - База данных версии 3: DestEntry, который представляет собой Свойства (UTF-8 карта Строка/Строка), сериализованные как Mapping , за которыми следует бинарное Destination (сериализованное обычным образом).
Свойства DestEntry обычно содержат:
- “a” - Время добавления (Java long время в мс)
- “m” - Время последнего изменения (Java long время в мс)
- “notes” - Комментарии пользователя
- “s” - Исходный источник записи (обычно имя файла или URL подписки)
- “v” - Если подпись записи была проверена, “true” или “false”
Ключи имен хостов хранятся в нижнем регистре и всегда заканчиваются на “.i2p”.