Aperçu
Ce document spécifie le format de fichier I2P blockfile et les tables dans le hostsdb.blockfile utilisé par le Blockfile Naming Service NAMING .
Le blockfile fournit une recherche rapide de Destination dans un format compact. Bien que la surcharge des pages du blockfile soit substantielle, les destinations sont stockées en binaire plutôt qu’en Base 64 comme dans le format hosts.txt. De plus, le blockfile offre la possibilité de stocker des métadonnées arbitraires (telles que la date d’ajout, la source et les commentaires) pour chaque entrée. Les métadonnées peuvent être utilisées à l’avenir pour fournir des fonctionnalités avancées de carnet d’adresses. Les exigences de stockage du blockfile représentent une augmentation modeste par rapport au format hosts.txt, et le blockfile fournit approximativement une réduction de 10x des temps de recherche.
Un blockfile est simplement un stockage sur disque de plusieurs cartes triées (paires clé-valeur), implémentées sous forme de skiplists. Le format blockfile est adopté de la Metanotion Blockfile Database METANOTION . Nous définirons d’abord le format de fichier, puis l’utilisation de ce format par le BlockfileNamingService.
Format de fichier de blocs
La spécification blockfile originale a été modifiée pour ajouter des nombres magiques à chaque page. Le fichier est structuré en pages de 1024 octets. Les pages sont numérotées à partir de 1. Le “superblock” se trouve toujours à la page 1, c’est-à-dire commençant à l’octet 0 dans le fichier. La skiplist metaindex se trouve toujours à la page 2, c’est-à-dire commençant à l’octet 1024 dans le fichier.
Toutes les valeurs entières sur 2 octets sont non signées. Toutes les valeurs entières sur 4 octets (numéros de page) sont signées et les valeurs négatives sont illégales. Toutes les valeurs entières sont stockées dans l’ordre des octets réseau (big endian).
La base de données est conçue pour être ouverte et accédée par un seul thread. Le BlockfileNamingService fournit la synchronisation.
Format de superbloc
| 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 |
Tous les niveaux ont une portée. Toutes les portées n’ont pas de niveaux.
| 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 |
Les structures clé/valeur sont triées par clé dans chaque segment et à travers tous les segments. Les structures clé/valeur sont triées par clé dans chaque segment. Les segments autres que le premier segment ne peuvent pas être vides.
| 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 |
Les longueurs de clé et de valeur ne doivent pas être réparties sur plusieurs pages, c’est-à-dire que les 4 octets doivent être sur la même page. S’il n’y a pas assez de place, les 1 à 3 derniers octets d’une page ne sont pas utilisés et les longueurs seront à l’offset 8 dans la page de continuation. Les données de clé et de valeur peuvent être réparties sur plusieurs pages. Les longueurs maximales de clé et de valeur sont de 65535 octets.
| 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 |
Tables du Service de Nommage Blockfile
Les tables créées et utilisées par le BlockfileNamingService sont les suivantes. Le nombre maximum d’entrées par span est de 16.
Liste de saut des propriétés
%%__INFO__%% est la skiplist principale de la base de données avec des entrées clé/valeur String/Properties ne contenant qu’une seule entrée :
info - un Properties (Map UTF-8 String/String), sérialisé comme un Mapping :
- version - “4”
- created - Temps Java long (ms)
- upgraded - Temps Java long (ms) (à partir de la version 2 de la base de données)
- lists - Liste séparée par des virgules des bases de données d’hôtes, à rechercher dans l’ordre pour les recherches. Presque toujours “privatehosts.txt,userhosts.txt,hosts.txt”.
- listversion_* - La version de chaque base de données dans les listes, par exemple : listversion_hosts.txt=4. Utilisé pour identifier les mises à niveau partielles ou interrompues de listes individuelles. (à partir de la version 4 de la base de données)
Liste de saut de recherche inversée
%%__REVERSE__%% est la skiplist de recherche inversée avec des entrées clé/valeur Integer/Properties (à partir de la version 2 de la base de données) :
- Les clés de skiplist sont des entiers de 4 octets, les 4 premiers octets du hash de la Destination .
- Les valeurs de skiplist sont chacune des Properties (une Map String/String UTF-8) sérialisées comme un Mapping
- Il peut y avoir plusieurs entrées dans les propriétés, chacune étant un mappage inverse, car il peut y avoir plus d’un nom d’hôte pour une destination donnée, ou il pourrait y avoir des collisions avec les mêmes 4 premiers octets du hash.
- Chaque clé de propriété est un nom d’hôte.
- Chaque valeur de propriété est une chaîne vide.
Listes d’exclusion hosts.txt, userhosts.txt et privatehosts.txt
Pour chaque base de données d’hôtes, il y a une skiplist contenant les hôtes de cette base de données. Notez que le format version 4 prend en charge plusieurs Destinations par nom d’hôte. Ce format a été introduit dans la version 0.9.26 d’I2P. Les bases de données version 3 sont automatiquement migrées vers la version 4.
Les clés/valeurs dans ces skiplists sont les suivantes :
key - une chaîne UTF-8 (le nom d’hôte)
value - - Version 4 de la base de données : Un DestEntry, qui est un nombre d’un octet de paires Properties/Destination à suivre. Ce nombre de paires de : Un Properties (une Map UTF-8 String/String) sérialisé comme un Mapping suivi d’une Destination binaire (sérialisée comme d’habitude). - Version 3 de la base de données : un DestEntry, qui est un Properties (une Map UTF-8 String/String) sérialisé comme un Mapping suivi d’une Destination binaire (sérialisée comme d’habitude).
Les propriétés DestEntry contiennent généralement :
- “a” - L’heure d’ajout (temps Java long en ms)
- “m” - L’heure de dernière modification (temps Java long en ms)
- “notes” - Commentaires fournis par l’utilisateur
- “s” - La source originale de l’entrée (généralement un nom de fichier ou une URL d’abonnement)
- “v” - Si la signature de l’entrée a été vérifiée, “true” ou “false”
Les clés de nom d’hôte sont stockées en minuscules et se terminent toujours par “.i2p”.