Überblick
Dieses Dokument spezifiziert das I2P blockfile Dateiformat und die Tabellen in der hostsdb.blockfile, die vom Blockfile Naming Service NAMING verwendet werden.
Die Blockdatei bietet eine schnelle Destination-Suche in einem kompakten Format. Obwohl der Overhead der Blockdatei-Seiten erheblich ist, werden die Destinations in binärer Form gespeichert und nicht in Base 64 wie im hosts.txt-Format. Zusätzlich bietet die Blockdatei die Möglichkeit, beliebige Metadaten (wie Hinzufügungsdatum, Quelle und Kommentare) für jeden Eintrag zu speichern. Die Metadaten können in Zukunft verwendet werden, um erweiterte Adressbuch-Funktionen bereitzustellen. Der Speicherbedarf der Blockdatei ist nur geringfügig höher als beim hosts.txt-Format, und die Blockdatei bietet etwa eine 10-fache Reduzierung der Suchzeiten.
Eine Blockfile ist einfach eine festplattenbasierte Speicherung mehrerer sortierter Maps (Schlüssel-Wert-Paare), implementiert als Skiplists. Das Blockfile-Format wurde von der Metanotion Blockfile Database METANOTION übernommen. Zuerst werden wir das Dateiformat definieren, dann die Verwendung dieses Formats durch den BlockfileNamingService.
Blockfile-Format
Die ursprüngliche Blockfile-Spezifikation wurde modifiziert, um jeder Seite magische Zahlen hinzuzufügen. Die Datei ist in 1024-Byte-Seiten strukturiert. Die Seiten werden beginnend mit 1 nummeriert. Der “Superblock” befindet sich immer auf Seite 1, d.h. beginnend bei Byte 0 in der Datei. Die Metaindex-Skiplist befindet sich immer auf Seite 2, d.h. beginnend bei Byte 1024 in der Datei.
Alle 2-Byte-Ganzzahlenwerte sind vorzeichenlos. Alle 4-Byte-Ganzzahlenwerte (Seitennummern) sind vorzeichenbehaftet und negative Werte sind unzulässig. Alle Ganzzahlenwerte werden in Netzwerk-Byte-Reihenfolge (Big Endian) gespeichert.
Die Datenbank ist so konzipiert, dass sie von einem einzigen Thread geöffnet und darauf zugegriffen werden kann. Der BlockfileNamingService stellt die Synchronisation bereit.
Superblock-Format
| 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 |
Alle Ebenen haben eine Spanne. Nicht alle Spannen haben Ebenen.
| 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 |
Schlüssel/Wert-Strukturen sind nach Schlüssel innerhalb jedes Bereichs und über alle Bereiche hinweg sortiert. Schlüssel/Wert-Strukturen sind nach Schlüssel innerhalb jedes Bereichs sortiert. Bereiche außer dem ersten Bereich dürfen nicht leer sein.
| 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 |
Schlüssel- und Wertlängen dürfen nicht über Seiten aufgeteilt werden, d.h. alle 4 Bytes müssen sich auf derselben Seite befinden. Wenn nicht genügend Platz vorhanden ist, bleiben die letzten 1-3 Bytes einer Seite ungenutzt und die Längen befinden sich bei Offset 8 auf der Fortsetzungsseite. Schlüssel- und Wertdaten können über Seiten aufgeteilt werden. Die maximalen Schlüssel- und Wertlängen betragen 65535 Bytes.
| 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 Naming Service Tabellen
Die vom BlockfileNamingService erstellten und verwendeten Tabellen sind wie folgt. Die maximale Anzahl der Einträge pro Span beträgt 16.
Properties Skiplist
%%__INFO__%% ist die Haupt-Datenbank-Skiplist mit String/Properties-Schlüssel/Wert-Einträgen, die nur einen Eintrag enthält:
info - ein Properties (UTF-8 String/String Map), serialisiert als ein Mapping :
- version - “4”
- created - Java long time (ms)
- upgraded - Java long time (ms) (ab Datenbankversion 2)
- lists - Komma-getrennte Liste von Host-Datenbanken, die in der angegebenen Reihenfolge für Lookups durchsucht werden. Fast immer “privatehosts.txt,userhosts.txt,hosts.txt”.
- listversion_* - Die Version jeder Datenbank in lists, zum Beispiel: listversion_hosts.txt=4. Wird verwendet, um teilweise oder abgebrochene Upgrades einzelner Listen zu identifizieren. (ab Datenbankversion 4)
Reverse Lookup Skiplist
%%__REVERSE__%% ist die Reverse-Lookup-Skiplist mit Integer/Properties-Schlüssel/Wert-Einträgen (ab Datenbankversion 2):
- Die skiplist-Schlüssel sind 4-Byte-Integer, die ersten 4 Bytes des Hashes der Destination .
- Die skiplist-Werte sind jeweils eine Properties (eine UTF-8 String/String Map), serialisiert als Mapping
- Es kann mehrere Einträge in den Properties geben, jeder ist ein umgekehrtes Mapping, da es mehr als einen Hostnamen für eine gegebene Destination geben kann, oder es könnte Kollisionen mit denselben ersten 4 Bytes des Hashes geben.
- Jeder Property-Schlüssel ist ein Hostname.
- Jeder Property-Wert ist der leere String.
hosts.txt, userhosts.txt und privatehosts.txt Sperrlisten
Für jede Host-Datenbank gibt es eine Skiplist, die die Hosts für diese Datenbank enthält. Beachten Sie, dass das Version-4-Format mehrere Destinations pro Hostname unterstützt. Dieses Format wurde in I2P-Version 0.9.26 eingeführt. Version-3-Datenbanken werden automatisch zu Version 4 migriert.
Die Schlüssel/Werte in diesen Skiplisten sind wie folgt:
key - ein UTF-8 String (der Hostname)
value - - Datenbankversion 4: Ein DestEntry, welcher eine Ein-Byte-Zahl von Properties/Destination-Paaren ist, die folgen. Diese Anzahl von Paaren aus: Properties (eine UTF-8 String/String Map) serialisiert als Mapping , gefolgt von einer binären Destination (wie üblich serialisiert). - Datenbankversion 3: ein DestEntry, welcher Properties (eine UTF-8 String/String Map) serialisiert als Mapping ist, gefolgt von einer binären Destination (wie üblich serialisiert).
Die DestEntry-Eigenschaften enthalten normalerweise:
- “a” - Die Zeit der Hinzufügung (Java long Zeit in ms)
- “m” - Die Zeit der letzten Änderung (Java long Zeit in ms)
- “notes” - Benutzerdefinierte Kommentare
- “s” - Die ursprüngliche Quelle des Eintrags (normalerweise ein Dateiname oder eine Abonnement-URL)
- “v” - Ob die Signatur des Eintrags verifiziert wurde, “true” oder “false”
Hostname-Schlüssel werden in Kleinbuchstaben gespeichert und enden immer mit “.i2p”.