Visão Geral
Este documento especifica o formato de arquivo blockfile do I2P e as tabelas no hostsdb.blockfile usado pelo Serviço de Nomenclatura Blockfile NAMING .
O blockfile fornece busca rápida de Destination em um formato compacto. Embora a sobrecarga de página do blockfile seja substancial, os destinations são armazenados em binário em vez de Base 64 como no formato hosts.txt. Além disso, o blockfile oferece a capacidade de armazenamento arbitrário de metadados (como data de adição, origem e comentários) para cada entrada. Os metadados podem ser usados no futuro para fornecer recursos avançados de catálogo de endereços. O requisito de armazenamento do blockfile é um aumento modesto em relação ao formato hosts.txt, e o blockfile proporciona aproximadamente uma redução de 10x nos tempos de busca.
Um blockfile é simplesmente armazenamento em disco de múltiplos mapas ordenados (pares chave-valor), implementados como skiplists. O formato blockfile é adotado do Metanotion Blockfile Database METANOTION . Primeiro definiremos o formato do arquivo, depois o uso desse formato pelo BlockfileNamingService.
Formato de Blockfile
A especificação original do blockfile foi modificada para adicionar números mágicos a cada página. O arquivo é estruturado em páginas de 1024 bytes. As páginas são numeradas começando do 1. O “superbloco” está sempre na página 1, ou seja, começando no byte 0 no arquivo. A skiplist do metaíndice está sempre na página 2, ou seja, começando no byte 1024 no arquivo.
Todos os valores inteiros de 2 bytes são sem sinal. Todos os valores inteiros de 4 bytes (números de página) são com sinal e valores negativos são ilegais. Todos os valores inteiros são armazenados em ordem de bytes de rede (big endian).
A base de dados foi projetada para ser aberta e acessada por uma única thread. O BlockfileNamingService fornece sincronização.
Formato do superbloco
| 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 |
Todos os níveis têm um intervalo. Nem todos os intervalos têm níveis.
| 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 |
As estruturas chave/valor são ordenadas por chave dentro de cada segmento e em todos os segmentos. As estruturas chave/valor são ordenadas por chave dentro de cada segmento. Segmentos que não sejam o primeiro segmento não podem estar vazios.
| 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 |
Os comprimentos de chave e valor não devem ser divididos entre páginas, ou seja, todos os 4 bytes devem estar na mesma página. Se não houver espaço suficiente, os últimos 1-3 bytes de uma página ficam inutilizados e os comprimentos estarão no deslocamento 8 na página de continuação. Os dados de chave e valor podem ser divididos entre páginas. Os comprimentos máximos de chave e valor são 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 |
Tabelas do Serviço de Nomenclatura Blockfile
As tabelas criadas e utilizadas pelo BlockfileNamingService são as seguintes. O número máximo de entradas por span é 16.
Lista de Pulos de Propriedades
%%__INFO__%% é a skiplist principal do banco de dados com entradas chave/valor String/Properties contendo apenas uma entrada:
info - um Properties (Mapa UTF-8 String/String), serializado como um Mapping :
- version - “4”
- created - Java long time (ms)
- upgraded - Java long time (ms) (a partir da versão 2 da base de dados)
- lists - Lista separada por vírgulas de bases de dados de hosts, a serem pesquisadas por ordem para consultas. Quase sempre “privatehosts.txt,userhosts.txt,hosts.txt”.
- listversion_* - A versão de cada base de dados em lists, por exemplo: listversion_hosts.txt=4. Usado para identificar atualizações parciais ou abortadas de listas individuais. (a partir da versão 4 da base de dados)
Lista de Saltos de Busca Reversa
%%__REVERSE__%% é a skiplist de pesquisa reversa com entradas chave/valor Integer/Properties (a partir da versão 2 da base de dados):
- As chaves da skiplist são Inteiros de 4 bytes, os primeiros 4 bytes do hash do Destination .
- Os valores da skiplist são cada um uma Properties (um Mapa String/String UTF-8) serializada como um Mapping
- Pode haver múltiplas entradas nas properties, cada uma é um mapeamento reverso, pois pode haver mais de um hostname para um dado destination, ou poderia haver colisões com os mesmos primeiros 4 bytes do hash.
- Cada chave de property é um hostname.
- Cada valor de property é a string vazia.
Listas de exclusão hosts.txt, userhosts.txt e privatehosts.txt
Para cada base de dados de hosts, existe uma skiplist contendo os hosts para essa base de dados. Note que o formato da versão 4 suporta múltiplos Destinations por nome de host. Este formato foi introduzido na versão 0.9.26 do I2P. Bases de dados da versão 3 são automaticamente migradas para a versão 4.
As chaves/valores nessas skiplists são os seguintes:
key - uma String UTF-8 (o nome do host)
value - - Versão 4 da base de dados: Uma DestEntry, que é um número de um byte de pares Properties/Destination a seguir. Esse número de pares de: Uma Properties (um Mapa String/String UTF-8) serializada como um Mapping seguido por um Destination binário (serializado como de costume). - Versão 3 da base de dados: uma DestEntry, que é uma Properties (um Mapa String/String UTF-8) serializada como um Mapping seguido por um Destination binário (serializado como de costume).
As Propriedades DestEntry normalmente contêm:
- “a” - O tempo adicionado (tempo Java long em ms)
- “m” - O tempo da última modificação (tempo Java long em ms)
- “notes” - Comentários fornecidos pelo usuário
- “s” - A fonte original da entrada (tipicamente um nome de arquivo ou URL de subscrição)
- “v” - Se a assinatura da entrada foi verificada, “true” ou “false”
As chaves de hostname são armazenadas em minúsculas e sempre terminam em “.i2p”.