Un'immersione profonda nell'indirizzamento dei dati nei sistemi di archiviazione: Da HashMap a HDFS, Kafka, Milvus e Iceberg

Se lavorate su sistemi di backend o di storage distribuito, probabilmente vi sarà capitato di assistere a questa situazione: la rete non è satura, le macchine non sono sovraccariche, eppure una semplice ricerca comporta migliaia di I/O su disco o di chiamate API per lo storage di oggetti, e la query impiega comunque pochi secondi.

Il collo di bottiglia raramente è la larghezza di banda o il calcolo. È l'indirizzamento, ovvero il lavoro che un sistema fa per capire dove si trovano i dati prima di poterli leggere. L 'indirizzamento dei dati è il processo di traduzione di un identificatore logico (una chiave, un percorso di file, un offset, un predicato di query) nella posizione fisica dei dati sullo storage. In scala, questo processo - e non il trasferimento effettivo dei dati - domina la latenza.

Le prestazioni dello storage possono essere ridotte a un semplice modello:

Costo totale di indirizzamento = accessi ai metadati + accessi ai dati.

Quasi tutte le ottimizzazioni dello storage, dalle tabelle hash ai livelli di metadati lakehouse, mirano a questa equazione. Le tecniche variano, ma l'obiettivo è sempre lo stesso: individuare i dati con il minor numero possibile di operazioni ad alta latenza.

Questo articolo ripercorre questa idea attraverso sistemi di scala crescente, dalle strutture di dati in-memory come HashMap, ai sistemi distribuiti come HDFS e Apache Kafka, fino ai moderni motori come Milvus (un database vettoriale) e Apache Iceberg che operano su storage a oggetti. Nonostante le differenze, tutti ottimizzano la stessa equazione.

Tre tecniche di indirizzamento fondamentali

Nei sistemi di archiviazione e nei motori distribuiti, la maggior parte delle ottimizzazioni dell'indirizzamento rientra in tre tecniche:

• Calcolo - Deriva la posizione dei dati direttamente da una formula, invece di scansionare o attraversare le strutture per trovarli.
• Caching - Mantenere in memoria i metadati o gli indici a cui si accede di frequente, per evitare letture ripetute ad alta latenza dal disco o dallo storage remoto.
• Pruning - Utilizzare le informazioni sull'intervallo o i confini delle partizioni per escludere file, shard o nodi che non possono contenere il risultato.

In questo articolo, per accesso si intende qualsiasi operazione con un costo reale a livello di sistema: una lettura del disco, una chiamata di rete o una richiesta di API per lo storage degli oggetti. Il calcolo della CPU a livello di nanosecondo non conta. Ciò che conta è ridurre il numero di operazioni di I/O o trasformare il costoso I/O casuale in letture sequenziali più economiche.

Come funziona l'indirizzamento: Il problema delle due somme

Per rendere concreto l'indirizzamento, si consideri un classico problema di algoritmo. Dato un array di numeri interi nums e un valore di destinazione target, restituire gli indici di due numeri la cui somma è target.

Ad esempio: nums = [2, 7, 11, 15], target = 9 → risultato [0, 1].

Questo problema illustra chiaramente la differenza tra la ricerca di dati e il calcolo della loro posizione.

Soluzione 1: Ricerca a forza bruta

L'approccio a forza bruta controlla ogni coppia. Per ogni elemento, scansiona il resto dell'array alla ricerca di una corrispondenza. Semplice, ma O(n²).

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) return new int[]{i, j};
        }
    }
    return null;
}

Non si sa dove possa trovarsi la risposta. Ogni ricerca parte da zero e attraversa l'array alla cieca. Il collo di bottiglia non è l'aritmetica, ma la scansione ripetuta.

Soluzione 2: indirizzamento diretto tramite calcolo

La soluzione ottimizzata sostituisce la scansione con una HashMap. Invece di cercare un valore corrispondente, calcola il valore necessario e lo cerca direttamente. La complessità del tempo scende a O(n).

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i]; // compute what we need
        if (map.containsKey(complement)) { // direct lookup, no scan
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return null;
}

Il cambiamento: invece di scansionare l'array per trovare una corrispondenza, si calcola il valore necessario e si va direttamente alla sua posizione. Una volta che la posizione può essere ricavata, l'attraversamento scompare.

Questa è la stessa idea alla base di ogni sistema di archiviazione ad alte prestazioni che esamineremo: sostituire le scansioni con il calcolo e i percorsi di ricerca indiretti con l'indirizzamento diretto.

HashMap: Come gli indirizzi calcolati sostituiscono le scansioni

Una HashMap memorizza coppie chiave-valore e individua i valori calcolando un indirizzo dalla chiave, non cercando tra le voci. Data una chiave, applica una funzione hash, calcola un indice di array e salta direttamente a quella posizione. Non è necessaria alcuna scansione.

Questa è la forma più semplice del principio che guida tutti i sistemi presentati in questo articolo: evitare le scansioni ricavando le posizioni attraverso il calcolo. La stessa idea, che è alla base di tutto, dalla ricerca distribuita di metadati agli indici vettoriali, è presente in ogni scala.

La struttura dati principale

Nel suo nucleo, una HashMap è costruita attorno a una singola struttura: un array. Una funzione hash mappa le chiavi in indici di array. Poiché lo spazio delle chiavi è molto più grande dell'array, le collisioni sono inevitabili: chiavi diverse possono avere lo stesso indice. Queste vengono gestite localmente all'interno di ogni slot utilizzando un elenco collegato o un albero rosso-nero.

Gli array offrono un accesso in tempo costante per indice. Questa proprietà - l'indirizzamento diretto e prevedibile - è alla base delle prestazioni delle HashMap ed è lo stesso principio che sta alla base dell'accesso efficiente ai dati nei sistemi di archiviazione su larga scala.

public class HashMap<K,V> {
<span class="hljs-comment">// Core structure: an array that supports O(1) random access</span>
<span class="hljs-keyword">transient</span> Node&lt;K,V&gt;[] table;

<span class="hljs-comment">// Node structure</span>
<span class="hljs-keyword">static</span> <span class="hljs-keyword">class</span> <span class="hljs-title class_">Node</span>&lt;K,V&gt; {
    <span class="hljs-keyword">final</span> <span class="hljs-type">int</span> hash;      <span class="hljs-comment">// hash value (cached to avoid recomputation)</span>
    <span class="hljs-keyword">final</span> K key;         <span class="hljs-comment">// key</span>
    V value;             <span class="hljs-comment">// value</span>
    Node&lt;K,V&gt; next;      <span class="hljs-comment">// next node (for handling collision)</span>
}

<span class="hljs-comment">// Hash function：key → integer</span>
<span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-type">int</span> <span class="hljs-title function_">hash</span><span class="hljs-params">(Object key)</span> {
    <span class="hljs-type">int</span> h;
    <span class="hljs-keyword">return</span> (key == <span class="hljs-literal">null</span>) ? <span class="hljs-number">0</span> : (h = key.hashCode()) ^ (h &gt;&gt;&gt; <span class="hljs-number">16</span>);
}

}

Come fa una HashMap a localizzare i dati?

Indirizzamento HashMap passo dopo passo: hash della chiave, calcolo dell’indice dell’array, salto diretto al bucket e risoluzione locale, per ottenere una ricerca O(1) senza attraversamento.

Prendiamo come esempio put("apple", 100). L'intera ricerca richiede quattro passaggi, senza scansione dell'intera tabella:

1. Hash della chiave: Passare la chiave attraverso una funzione di hash → hash("apple") = 93029210
2. Mappatura su un indice di array: 93029210 & (arrayLength - 1) → ad esempio, 93029210 & 15 = 10
3. Saltare al bucket: Accedere direttamente a table[10] - un singolo accesso alla memoria, non una traversata.
4. Risolvere localmente: Se non ci sono collisioni, leggere o scrivere immediatamente. Se c'è una collisione, controllare un piccolo elenco collegato o un albero rosso-nero all'interno del bucket.

Perché la ricerca di HashMap è O(1)?

L'accesso agli array è O(1) grazie a una semplice formula di indirizzamento:

element_address = base_address + index × element_size

Dato un indice, l'indirizzo di memoria viene calcolato con una moltiplicazione e un'addizione. Il costo è fisso, indipendentemente dalla dimensione dell'array: un calcolo, una lettura della memoria. Un elenco collegato, invece, deve essere attraversato nodo per nodo, seguendo i puntatori attraverso posizioni di memoria separate: O(n) nel caso peggiore.

Una HashMap esegue l'hash di una chiave in un indice di array, trasformando quella che sarebbe una traversata in un indirizzo calcolato. Invece di cercare i dati, calcola esattamente dove si trovano e vi salta.

Come cambia l'indirizzamento nei sistemi distribuiti?

HashMap risolve l'indirizzamento all'interno di una singola macchina, dove i dati vivono in memoria e i costi di accesso sono banali. Su scale maggiori, i vincoli cambiano drasticamente:

Fattore di scala	Impatto
Dimensione dei dati	Megabyte → terabyte o petabyte su cluster
Mezzo di memorizzazione	Memoria → disco → rete → memorizzazione degli oggetti
Latenza di accesso	Memoria: ~100 ns / Disco: 10-20 ms / Rete Same-DC: ~0,5 ms / Cross-region: ~150 ms

Il problema dell'indirizzamento non cambia: diventa solo più costoso. Ogni ricerca può comportare salti di rete e I/O su disco, quindi la riduzione del numero di accessi è molto più importante che in memoria.

Per vedere come i sistemi reali gestiscono questo problema, esaminiamo due esempi classici. HDFS applica l'indirizzamento basato sul calcolo a file di grandi dimensioni e basati su blocchi. Kafka lo applica ai flussi di messaggi di sola appendice. Entrambi seguono lo stesso principio: calcolare dove si trovano i dati invece di cercarli.

HDFS: indirizzare file di grandi dimensioni con metadati in memoria

HDFS è un sistema di archiviazione distribuito progettato per file molto grandi su cluster di macchine. Dato un percorso di file e un offset di byte, deve trovare il blocco di dati giusto e il DataNode che lo memorizza.

HDFS risolve questo problema con una scelta progettuale deliberata: mantenere tutti i metadati del filesystem in memoria.

L’organizzazione dei dati di HDFS mostra la vista logica di un file di 300 MB mappato sullo storage fisico come tre blocchi distribuiti tra i DataNode con replica .

Al centro si trova il NameNode. Carica in memoria l'intero albero del filesystem: struttura delle directory, mappature da file a blocco e mappature da blocco a DataNode. Poiché i metadati non vengono mai toccati dal disco durante la lettura, HDFS risolve tutti i problemi di indirizzamento solo attraverso ricerche in memoria.

Concettualmente, si tratta di HashMap su scala cluster: utilizzare strutture di dati in-memory per trasformare le ricerche lente in ricerche veloci e calcolate. La differenza è che HDFS applica lo stesso principio a insiemi di dati distribuiti su migliaia di macchine.

// Data structures stored in the NameNode's memory
// 1. Filesystem directory tree
class FSDirectory {
INodeDirectory rootDir;           // root directory “/”
INodeMap inodeMap;                // path → INode (HashMap!)
}
// 2. INode：file / directory node
abstract class INode {
long id;                          // unique identifier
String name;                      // name
INode parent;                     // parent node
long modificationTime;            // last modification time
}
class INodeFile extends INode {
BlockInfo[] blocks;               // list of blocks that make up the file
}
// 3. Block metadata mapping
class BlocksMap {
GSet blocks;    // Block → location info (HashMap!)
}
class BlockInfo {
long blockId;
DatanodeDescriptor[] storages;    // list of DataNodes storing this block
}

Come fa HDFS a localizzare i dati?

Consideriamo la lettura di dati all'offset di 200 MB di /user/data/bigfile.txt, con una dimensione di blocco predefinita di 128 MB:

1. Il client invia un singolo RPC al NameNode.
2. Il NameNode risolve il percorso del file e calcola che l'offset 200 MB rientra nel secondo blocco (intervallo 128-256 MB), interamente in memoria.
3. Il NameNode restituisce i DataNode che memorizzano il blocco (ad esempio, DN2 e DN3).
4. Il client legge direttamente dal DataNode più vicino (DN2)

Costo totale: una RPC, qualche ricerca in memoria, una lettura di dati. I metadati non vengono mai letti su disco durante questo processo e ogni ricerca è a tempo costante. HDFS evita le costose scansioni dei metadati anche quando i dati scalano su cluster di grandi dimensioni.

Apache Kafka: Come l'indicizzazione sparsa evita l'I/O casuale

Apache Kafka è stato progettato per flussi di messaggi ad alta velocità. Dato un offset di un messaggio, deve individuare l'esatta posizione del byte sul disco, senza trasformare le letture in I/O casuale.

Kafka combina l'archiviazione sequenziale con un indice rado in memoria. Invece di cercare tra i dati, calcola una posizione approssimativa ed esegue una piccola scansione limitata.

L’organizzazione dei dati di Kafka mostra una vista logica con argomenti e partizioni mappati sullo storage fisico come directory di partizione contenenti file di segmento .log, .index e .timeindex .

I messaggi sono organizzati come Argomento → Partizione → Segmento. Ogni partizione è un registro di sola appendice suddiviso in segmenti, ciascuno dei quali è costituito da:

• un file .log che memorizza i messaggi in modo sequenziale su disco
• Un file .index che funge da indice sparso nel registro.

Il file .index è mappato in memoria (mmap), quindi le ricerche dell'indice vengono effettuate direttamente dalla memoria senza I/O su disco.

Il design dell’indice sparse di Kafka mostra una voce dell’indice per 4KB di dati, con un confronto di memoria: indice denso a 800MB contro indice sparse a soli 2MB residenti in memoria

// A Partition manages all its Segments
class LocalLog {
    // Core structure: TreeMap, ordered by baseOffset
    ConcurrentNavigableMap<Long, LogSegment> segments;
<span class="hljs-comment">// Locate the target Segment</span>
LogSegment <span class="hljs-title function_">floorEntry</span><span class="hljs-params">(<span class="hljs-type">long</span> offset)</span> {
    <span class="hljs-keyword">return</span> segments.floorEntry(offset);  <span class="hljs-comment">// O(log N)</span>
}

}
// A single Segment
class LogSegment {
FileRecords log;           // .log file (message data)
LazyIndex offsetIndex;  // .index file (sparse index)
long baseOffset;           // starting Offset
}
// Sparse index entry (8 bytes per entry)
class OffsetPosition {
int relativeOffset;        // offset relative to baseOffset (4 bytes)
int position;              // physical position in the .log file (4 bytes)
}

Come fa Kafka a localizzare i dati?

Supponiamo che un consumatore legga il messaggio all'offset 500.000. Kafka risolve questo problema in tre passi:

1. Individuazione del segmento (ricerca su TreeMap)

• Offset di base del segmento: [0, 367834, 735668, 1103502]
• floorEntry(500000) → baseOffset = 367834
• File di destinazione: 00000000000000367834.log
• Complessità temporale: O(log S), dove S è il numero di segmenti (in genere < 100).

2. Cercare la posizione nell'indice sparse (.index)

• Offset relativo: 500000 − 367834 = 132166
• Ricerca binaria in .index: trovare la voce più grande ≤ 132166 → [132100 → position 20500000]
• Complessità temporale: O(log N), dove N è il numero di voci dell'indice.

3. Lettura sequenziale dal log (.log)

• Iniziare la lettura dalla posizione 20.500.000
• Continuare fino a raggiungere l'offset 500.000
• Viene scansionato al massimo un intervallo di indice (~4 KB)

Totale: una ricerca del segmento in memoria, una ricerca dell'indice, una breve lettura sequenziale. Nessun accesso casuale al disco.

HDFS vs. Apache Kafka

Dimensione	HDFS	Kafka
Obiettivo di progettazione	Memorizzazione e lettura efficiente di file di grandi dimensioni	Lettura/scrittura sequenziale ad alta velocità di flussi di messaggi
Modello di indirizzamento	Percorso → blocco → DataNode tramite HashMaps in memoria	Offset → segmento → posizione tramite indice sparse + scansione sequenziale
Memorizzazione dei metadati	Centralizzata nella memoria del NameNode	File locali, mappati in memoria tramite mmap
Costo di accesso per ricerca	1 RPC + N letture di blocchi	1 ricerca di indici + 1 lettura di dati
Ottimizzazione chiave	Tutti i metadati in memoria - nessun disco nel percorso di ricerca	L'indicizzazione sparsa e il layout sequenziale evitano l'I/O casuale.

Perché lo storage a oggetti cambia il problema dell'indirizzamento

Da HashMap a HDFS e Kafka, abbiamo visto l'indirizzamento in memoria e nello storage distribuito classico. Con l'evoluzione dei carichi di lavoro, i requisiti continuano a crescere:

• Query più ricche. I sistemi moderni gestiscono filtri multi-campo, ricerca per similarità e predicati complessi, non solo semplici chiavi e offset.
• Archiviazione a oggetti come impostazione predefinita. I dati vivono sempre più spesso in archivi compatibili con S3. I file sono distribuiti tra i vari bucket e ogni accesso è una chiamata API con una latenza fissa dell'ordine di decine di millisecondi, anche per pochi kilobyte.

A questo punto, il collo di bottiglia è la latenza, non la larghezza di banda. Una singola richiesta S3 GET costa ~50 ms, indipendentemente dalla quantità di dati restituiti. Se una query genera migliaia di richieste di questo tipo, la latenza totale aumenta. La minimizzazione del fan-out dell'API diventa il vincolo centrale della progettazione.

Esamineremo due sistemi moderni - Milvus, un database vettoriale, e Apache Iceberg, un formato di tabella lakehouse - per vedere come affrontano queste sfide. Nonostante le differenze, entrambi applicano le stesse idee di base: minimizzare gli accessi ad alta latenza, ridurre precocemente il fan-out e privilegiare il calcolo rispetto all'attraversamento.

Milvus V1: Quando l'archiviazione a livello di campo crea troppi file

Milvus è un database vettoriale molto diffuso, progettato per la ricerca di similarità su incorporazioni vettoriali. Il suo progetto iniziale di archiviazione riflette un primo approccio comune alla costruzione di un archivio di oggetti: archiviare ogni campo separatamente.

Nella V1, ogni campo di una collezione è memorizzato in file binlog separati tra i vari segmenti.

Il layout di archiviazione di Milvus V1 mostra una collezione divisa in segmenti, con ogni segmento che memorizza campi come id, vettori e dati scalari in file binlog separati, oltre a file stats_log separati per le statistiche dei file .

Come Milvus V1 individua i dati?

Consideriamo una semplice interrogazione: SELECT id, vector FROM collection WHERE id = 123.

1. Ricerca dei metadati - Interrogazione di etcd/MySQL per l'elenco dei segmenti → [Segment 12345, 12346, 12347, …]
2. Leggere il campo id tra i segmenti - Per ogni segmento, leggere i file binlog id
3. Individuare la riga di destinazione - Eseguire la scansione dei dati id caricati per trovare id = 123
4. Leggere il campo vettoriale - Leggere i file binlog vettoriali corrispondenti per il segmento corrispondente

Totale accessi ai file: N × (F₁ + F₂ + ...) dove N = numero di segmenti, F = file binlog per campo.

I conti si fanno presto difficili. Per una raccolta con 100 campi, 1.000 segmenti e 5 file binlog per campo:

1.000 × 100 × 5 = 500.000 file.

Anche se una query tocca solo tre campi, si tratta di 15.000 chiamate all'API di archiviazione degli oggetti. Con 50 ms per richiesta S3, la latenza serializzata raggiunge i 750 secondi, oltre 12 minuti per una singola query.

Milvus V2: Come il Parquet a livello di segmento riduce le chiamate API di 10 volte

Per risolvere i limiti di scalabilità della V1, Milvus V2 apporta un cambiamento fondamentale: organizzare i dati per segmento anziché per campo. Invece di molti piccoli file binlog, la V2 consolida i dati in file Parquet basati su segmenti.

Il numero di file scende da N × fields × binlogs a circa N (un gruppo di file per segmento).

Il layout di archiviazione di Milvus V2 mostra un segmento memorizzato come file Parquet con gruppi di righe contenenti gruppi di colonne per id, vettore e timestamp, oltre a un piè di pagina con lo schema e le statistiche delle colonne.

Ma la V2 non memorizza tutti i campi in un unico file. Raggruppa i campi per dimensione:

• I campi scalari piccoli (come id, timestamp) sono memorizzati insieme.
• Icampi grandi (come i vettori densi) sono divisi in file dedicati.

Tutti i file appartengono allo stesso segmento e le righe sono allineate per indice tra i file.

Struttura del file Parquet che mostra i gruppi di righe con i pezzi di colonna e le pagine di dati compressi, oltre a un piè di pagina contenente i metadati del file, i metadati dei gruppi di righe e le statistiche delle colonne, come i valori minimi e massimi .

Come Milvus V2 individua i dati?

Per la stessa query - SELECT id, vector FROM collection WHERE id = 123:

1. Ricerca dei metadati - Recupera l'elenco dei segmenti → [12345, 12346, …]
2. Leggere i piè di pagina di Parquet - Estrarre le statistiche dei gruppi di righe. Controllare il min/max della colonna id per gruppo di righe. id = 123 rientra nel gruppo di righe 0 (min=1, max=1000).
3. Leggere solo ciò che è necessario - La potatura delle colonne di Parquet legge solo la colonna id dal file a campo ridotto e solo la colonna vettore dal file a campo grande. Si accede solo ai gruppi di righe corrispondenti.

La suddivisione dei campi grandi offre due vantaggi fondamentali:

• Letture più efficienti. Le incorporazioni vettoriali dominano le dimensioni della memoria. Insieme ai campi piccoli, limitano il numero di righe che possono essere inserite in un gruppo di righe, aumentando gli accessi al file. Isolandoli, i gruppi di righe di campi piccoli possono contenere molte più righe, mentre i campi grandi utilizzano layout ottimizzati per le loro dimensioni.
• Evoluzione flessibile dello schema. Aggiungere una colonna significa creare un nuovo file. Rimuoverne una significa saltarla in lettura. Non è necessario riscrivere i dati storici.

Il risultato: il numero di file si riduce di oltre 10 volte, le chiamate API di oltre 10 volte e la latenza delle query passa da minuti a secondi.

Milvus V1 vs V2

Aspetto	V1	V2
Organizzazione dei file	Diviso per campo	Integrato per segmento
File per collezione	N × campi × binlog	~N × gruppi di colonne
Formato di archiviazione	Binlog personalizzato	Parquet (supporta anche Lance e Vortex)
Potenziamento delle colonne	Naturale (file a livello di campo)	Potenziamento delle colonne Parquet
Statistiche	File stats_log separati	Incorporato nel footer di Parquet
Chiamate API S3 per query	10,000+	~1,000
Latenza della query	Minuti	Secondi

Apache Iceberg: Potenziamento dei file guidato dai metadati

Apache Iceberg gestisce tabelle analitiche su enormi insiemi di dati in sistemi lakehouse. Quando una tabella si estende su migliaia di file di dati, la sfida consiste nel restringere una query ai soli file rilevanti, senza scansionare tutto.

La risposta di Iceberg: decidere quali file leggere prima che avvenga l'I/O dei dati, utilizzando metadati stratificati. È lo stesso principio che sta alla base del filtraggio dei metadati nei database vettoriali: utilizzare statistiche precalcolate per saltare i dati irrilevanti.

L’organizzazione dei dati di Iceberg mostra una directory di metadati con metadata.json, elenchi di manifest e file di manifest accanto a una directory di dati con file Parquet suddivisi per data .

Iceberg utilizza una struttura di metadati a strati. Ogni livello filtra i dati irrilevanti prima che venga consultato il successivo, in modo simile a come i database distribuiti separano i metadati dai dati per un accesso efficiente.

Architettura a quattro livelli di Iceberg: metadata.json punta a elenchi di manifest, che fanno riferimento a file di manifest contenenti statistiche a livello di file, che puntano ai file di dati Parquet veri e propri.

Come fa Iceberg a localizzare i dati?

Si consideri: SELECT * FROM orders WHERE date=’2024-01-15’ AND amount>1000.

1. Leggere metadata.json (1 I/O) - Caricare lo snapshot corrente e i suoi elenchi manifesti
2. Leggere l'elenco dei manifesti (1 I/O) - Applicare filtri a livello di partizione per saltare intere partizioni (ad esempio, tutti i dati 2023 vengono eliminati)
3. Leggere i file manifest (2 I/O) - Usare le statistiche a livello di file (data minima/massima, quantità minima/massima) per eliminare i file che non corrispondono alla query.
4. Lettura dei file di dati (3 I/O) - Rimangono solo tre file che vengono effettivamente letti.

Invece di scansionare tutti i 1.000 file di dati, Iceberg completa la ricerca in 7 operazioni di I/O, evitando oltre il 94% delle letture non necessarie.

Come i diversi sistemi affrontano i dati

Sistema	Organizzazione dei dati	Meccanismo di indirizzamento principale	Costo di accesso
HashMap	Chiave → slot dell'array	Funzione hash → indice diretto	Accesso alla memoria O(1)
HDFS	Percorso → blocco → DataNode	HashMaps in-memory + calcolo del blocco	1 RPC + N letture di blocchi
Kafka	Argomento → Partizione → Segmento	TreeMap + indice sparso + scansione sequenziale	1 ricerca dell'indice + 1 lettura dei dati
Milvus V2	Raccolta → Segmento → Colonne Parquet	Ricerca dei metadati + potatura delle colonne	N letture (N = segmenti)
Iceberg	Tabella → Istantanea → Manifesto → File di dati	Metadati stratificati + potatura statistica	3 letture di metadati + M letture di dati

Tre principi alla base di un indirizzamento efficiente dei dati

1. Il calcolo batte sempre la ricerca

In tutti i sistemi esaminati, l'ottimizzazione più efficace segue la stessa regola: calcolare dove si trovano i dati invece di cercarli.

• HashMap calcola l'indice di un array da hash(key) invece di effettuare una scansione.
• HDFS calcola il blocco di destinazione a partire dall'offset di un file, invece di esplorare i metadati del filesystem.
• Kafka calcola il segmento rilevante e la posizione dell'indice invece di eseguire la scansione del log.
• Iceberg usa i predicati e le statistiche a livello di file per calcolare quali file valgono la pena di essere letti.

Il calcolo è aritmetico con un costo fisso. La ricerca è un'operazione di attraversamento - confronti, ricerca di puntatori o I/O - il cui costo cresce con la dimensione dei dati. Quando un sistema può ricavare direttamente una posizione, la scansione diventa superflua.

2. Ridurre al minimo gli accessi ad alta latenza

Questo ci riporta alla formula principale: Costo totale dell'indirizzamento = accessi ai metadati + accessi ai dati. Ogni ottimizzazione mira a ridurre queste operazioni ad alta latenza.

Schema	Esempio
Riduzione del numero di file per limitare il fan-out dell'API	Consolidamento del segmento Milvus V2
Utilizzare le statistiche per escludere i dati in anticipo	Potenziamento dei manifesti Iceberg
Cache dei metadati in memoria	NameNode HDFS, indici mmap Kafka
Scambiare piccole scansioni sequenziali per un minor numero di letture casuali	Indice sparso di Kafka

3. Le statistiche consentono di prendere decisioni tempestive

La registrazione di semplici informazioni in fase di scrittura (valori minimi/massimi, confini delle partizioni, conteggio delle righe) consente ai sistemi di decidere in fase di lettura quali file valgono la pena di essere letti e quali possono essere completamente saltati.

Si tratta di un piccolo investimento con un grande ritorno. Le statistiche trasformano l'accesso ai file da una lettura cieca a una scelta deliberata. Che si tratti del pruning a livello di manifest di Iceberg o delle statistiche del footer di Parquet di Milvus V2, il principio è lo stesso: pochi byte di metadati in fase di scrittura possono eliminare migliaia di operazioni di I/O in fase di lettura.

Conclusione

Da Two Sum a HashMap, da HDFS e Kafka a Milvus e Apache Iceberg, uno schema continua a ripetersi: le prestazioni dipendono dall'efficienza con cui un sistema individua i dati.

Con la crescita dei dati e il passaggio dalla memoria al disco e all'archiviazione a oggetti, le meccaniche cambiano, ma non le idee di base. I sistemi migliori calcolano le posizioni invece di cercare, mantengono i metadati vicini e usano le statistiche per evitare di toccare dati non importanti. Tutti i vantaggi in termini di prestazioni che abbiamo esaminato derivano dalla riduzione degli accessi ad alta latenza e dal restringimento dello spazio di ricerca il più presto possibile.

Sia che stiate progettando una pipeline di ricerca vettoriale, sia che stiate costruendo sistemi su dati non strutturati, sia che stiate ottimizzando un motore di query lakehouse, vale la stessa equazione. Capire come il vostro sistema affronta i dati è il primo passo per renderlo più veloce.

---

Se lavorate con Milvus e volete ottimizzare le prestazioni di archiviazione o di interrogazione, saremo lieti di aiutarvi:

• Unitevi alla community Milvus su Slack per porre domande, condividere la vostra architettura e imparare da altri ingegneri che lavorano su problemi simili.
• Prenotate una sessione gratuita di 20 minuti di Milvus Office Hours per analizzare il vostro caso d'uso, che si tratti di layout di storage, messa a punto di query o scalata verso la produzione.
• Se preferite evitare la configurazione dell'infrastruttura, Zilliz Cloud (gestito da Milvus) offre un livello gratuito per iniziare.

---

Alcune domande che sorgono quando gli ingegneri iniziano a pensare all'indirizzamento dei dati e alla progettazione dello storage:

D: Perché Milvus è passato dallo storage a livello di campo a quello a livello di segmento?

In Milvus V1, ogni campo era memorizzato in file binlog separati tra i segmenti. Per una raccolta con 100 campi e 1.000 segmenti, si creavano centinaia di migliaia di piccoli file, ognuno dei quali richiedeva una propria chiamata API S3. V2 consolida i dati in file Parquet basati su segmenti, riducendo il numero di file di oltre 10 volte e riducendo la latenza delle query da minuti a secondi. L'intuizione principale: sullo storage a oggetti, il numero di chiamate API è più importante del volume totale dei dati.

D: Come fa Milvus a gestire in modo efficiente sia la ricerca vettoriale che il filtraggio scalare?

Milvus V2 memorizza i campi scalari e i campi vettoriali in gruppi di file separati all'interno dello stesso segmento. Le query scalari utilizzano il potenziamento delle colonne di Parquet e le statistiche dei gruppi di righe per saltare i dati irrilevanti. La ricerca vettoriale utilizza indici vettoriali dedicati. Entrambe condividono la stessa struttura di segmento, quindi le query ibride - che combinano filtri scalari e similarità vettoriale - possono operare sugli stessi dati senza duplicazioni.

D: Il principio della "prevalenza del calcolo sulla ricerca" si applica ai database vettoriali?

Sì. Gli indici vettoriali come HNSW e IVF si basano sulla stessa idea. Invece di confrontare un vettore interrogato con ogni vettore memorizzato (ricerca bruta), utilizzano strutture a grafo o centri di cluster per calcolare quartieri approssimativi e saltare direttamente alle regioni rilevanti dello spazio vettoriale. Il compromesso - una piccola perdita di precisione per un numero di ordini di grandezza inferiore di calcoli di distanza - è lo stesso modello di "calcolo su ricerca" applicato ai dati di incorporazione ad alta dimensione.

D: Qual è il più grande errore di performance che i team commettono con lo storage a oggetti?

Creare troppi file di piccole dimensioni. Ogni richiesta S3 GET ha una latenza fissa (~50 ms), indipendentemente dalla quantità di dati restituiti. Un sistema che legge 10.000 piccoli file serializza 500 secondi di latenza, anche se il volume totale dei dati è modesto. La soluzione è il consolidamento: unire file piccoli in file più grandi, usare formati colonnari come Parquet per letture selettive e mantenere metadati che consentano di saltare completamente i file.