Overview

This document specifies the I2P blockfile file format and the tables in the hostsdb.blockfile used by the Blockfile Naming Service [NAMING].

The blockfile provides fast Destination lookup in a compact format. While the blockfile page overhead is substantial, the destinations are stored in binary rather than in Base 64 as in the hosts.txt format. In addition, the blockfile provides the capability of arbitrary metadata storage (such as added date, source, and comments) for each entry. The metadata may be used in the future to provide advanced addressbook features. The blockfile storage requirement is a modest increase over the hosts.txt format, and the blockfile provides approximately 10x reduction in lookup times.

A blockfile is simply on-disk storage of multiple sorted maps (key-value pairs), implemented as skiplists. The blockfile format is adopted from the Metanotion Blockfile Database [METANOTION]. First we will define the file format, then the use of that format by the BlockfileNamingService.

Blockfile Format

The original blockfile spec was modified to add magic numbers to each page. The file is structured in 1024-byte pages. Pages are numbered starting from 1. The "superblock" is always at page 1, i.e. starting at byte 0 in the file. The metaindex skiplist is always at page 2, i.e. starting at byte 1024 in the file.

All 2-byte integer values are unsigned. All 4-byte integer values (page numbers) are signed and negative values are illegal. All integer values are stored in network byte order (big endian).

The database is designed to be opened and accessed by a single thread. The BlockfileNamingService provides synchronization.

Superblock format:

Byte       Contents
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

Skip list block page format:

Byte       Contents
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

Skip level block page format is as follows. All levels have a span. Not all spans have levels.

Byte       Contents
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 bytes unused

Skip span block page format is as follows. Key/value structures are sorted by key within each span and across all spans. Key/value structures are sorted by key within each span. Spans other than the first span may not be empty.

Byte       Contents
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

Span Continuation block page format:

Byte       Contents
0-3    Magic number      0x434f4e54 "CONT"
4-7    Next continuation page or 0
8-1023 key/value structures

Key/value structure format is as follows. Key and value lengths must not be split across pages, i.e. all 4 bytes must be on the same page. If there is not enough room the last 1-3 bytes of a page are unused and the lengths will be at offset 8 in the continuation page. Key and value data may be split across pages. Max key and value lengths are 65535 bytes.

Byte       Contents
0-1    key length in bytes
2-3    value length in bytes
4-     key data
      value data

Free list block page format:

Byte       Contents
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

Free page block format:

Byte       Contents
0-7    Magic number      0x7e2146524545217e "~!FREE!~"
8-1023 unused

The metaindex (located at page 2) is a mapping of US-ASCII strings to 4-byte integers. The key is the name of the skiplist and the value is the page index of the skiplist.

Blockfile Naming Service Tables

The tables created and used by the BlockfileNamingService are as follows. The maximum number of entries per span is 16.

References