Ein tiefes Eintauchen in die Datenadressierung in Speichersystemen: Von HashMap zu HDFS, Kafka, Milvus und Iceberg

Wenn Sie an Backend-Systemen oder verteilten Speichern arbeiten, haben Sie das sicher schon einmal erlebt: Das Netzwerk ist nicht gesättigt, die Rechner sind nicht überlastet, und doch löst eine einfache Abfrage Tausende von Festplatten-E/As oder Objektspeicher-API-Aufrufe aus - und die Abfrage dauert immer noch Sekunden.

Der Engpass ist selten die Bandbreite oder die Rechenleistung. Es ist die Adressierung - die Arbeit, die ein System leistet, um herauszufinden, wo sich die Daten befinden, bevor es sie lesen kann. Bei der Datenadressierung wird ein logischer Bezeichner (ein Schlüssel, ein Dateipfad, ein Offset, ein Abfrageprädikat) in den physischen Speicherort der Daten übersetzt. In großem Maßstab dominiert dieser Prozess - und nicht die eigentliche Datenübertragung - die Latenzzeit.

Die Speicherleistung lässt sich auf ein einfaches Modell reduzieren:

Gesamtadressierungskosten = Metadatenzugriffe + Datenzugriffe

Nahezu jede Speicheroptimierung - von Hash-Tabellen bis hin zu Lakehouse-Metadatenschichten - zielt auf diese Gleichung ab. Die Techniken variieren, aber das Ziel ist immer dasselbe: Daten mit so wenig Operationen mit hoher Latenz wie möglich zu finden.

In diesem Artikel wird diese Idee in Systemen mit zunehmendem Umfang verfolgt - von In-Memory-Datenstrukturen wie HashMap über verteilte Systeme wie HDFS und Apache Kafka bis hin zu modernen Engines wie Milvus (eine Vektordatenbank) und Apache Iceberg, die mit Objektspeicher arbeiten. Trotz ihrer Unterschiede optimieren sie alle die gleiche Gleichung.

Drei grundlegende Adressierungstechniken

Bei allen Speichersystemen und verteilten Engines lassen sich die meisten Adressierungsoptimierungen in drei Techniken unterteilen:

• Berechnung - Der Speicherort der Daten wird direkt aus einer Formel abgeleitet, anstatt Strukturen zu durchsuchen oder zu durchlaufen, um ihn zu finden.
• Caching - Speicherung von Metadaten oder Indizes, auf die häufig zugegriffen wird, im Speicher, um wiederholte Lesevorgänge mit hoher Latenz von der Festplatte oder einem entfernten Speicher zu vermeiden.
• Pruning - Verwendung von Bereichsinformationen oder Partitionsgrenzen, um Dateien, Shards oder Knoten auszuschließen, die das Ergebnis nicht enthalten können.

In diesem Artikel wird unter einem Zugriff jede Operation mit realen Kosten auf Systemebene verstanden: ein Festplattenlesevorgang, ein Netzwerkaufruf oder eine Objektspeicher-API-Anforderung. CPU-Berechnungen auf Nanosekundenebene zählen nicht. Worauf es ankommt, ist die Verringerung der Anzahl von E/A-Operationen - oder die Umwandlung von teuren zufälligen E/A in billigere sequenzielle Lesevorgänge.

Wie die Adressierung funktioniert: Das Zwei-Summen-Problem

Um die Adressierung zu verdeutlichen, betrachten wir ein klassisches Algorithmusproblem. Bei einem Array mit ganzen Zahlen nums und einem Zielwert target sollen die Indizes von zwei Zahlen zurückgegeben werden, deren Summe target ergibt.

Zum Beispiel: nums = [2, 7, 11, 15], target = 9 → Ergebnis [0, 1].

Dieses Problem veranschaulicht deutlich den Unterschied zwischen der Suche nach Daten und der Berechnung, wo sie sich befinden.

Lösung 1: Brute-Force-Suche

Bei der Brute-Force-Suche wird jedes Paar überprüft. Für jedes Element wird der Rest des Arrays nach einer Übereinstimmung durchsucht. Einfach, aber 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;
}

Es gibt keine Vorstellung davon, wo die Antwort liegen könnte. Jeder Suchvorgang beginnt bei Null und durchläuft das Array blindlings. Der Engpass ist nicht die Arithmetik, sondern das wiederholte Scannen.

Lösung 2: Direkte Adressierung durch Berechnung

Bei der optimierten Lösung wird das Scannen durch eine HashMap ersetzt. Anstatt nach einem passenden Wert zu suchen, wird der benötigte Wert berechnet und direkt nachgeschlagen. Die Zeitkomplexität sinkt auf 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;
}

Die Umstellung: Anstatt das Array zu durchsuchen, um eine Übereinstimmung zu finden, berechnen Sie den benötigten Wert und gehen direkt zu seiner Position. Sobald der Ort abgeleitet werden kann, entfällt das Traversieren.

Dies ist die gleiche Idee, die hinter jedem Hochleistungsspeichersystem steht, das wir untersuchen werden: Ersetzen Sie Scans durch Berechnungen und indirekte Suchpfade durch direkte Adressierung.

HashMap: Wie berechnete Adressen Scans ersetzen

Eine HashMap speichert Schlüssel-Wert-Paare und findet Werte, indem sie eine Adresse aus dem Schlüssel berechnet - und nicht, indem sie Einträge durchsucht. Bei einem Schlüssel wendet sie eine Hash-Funktion an, berechnet einen Array-Index und springt direkt zu dieser Stelle. Kein Scannen erforderlich.

Dies ist die einfachste Form des Prinzips, das allen Systemen in diesem Artikel zugrunde liegt: Vermeidung von Scans durch Ableitung von Speicherorten durch Berechnung. Dieselbe Idee - die allem zugrunde liegt, von verteilten Metadatensuchen bis hin zu Vektorindizes - taucht in jedem Maßstab auf.

Die Kerndatenstruktur

Im Kern besteht eine HashMap aus einer einzigen Struktur: einem Array. Eine Hash-Funktion bildet Schlüssel auf Array-Indizes ab. Da der Schlüsselraum viel größer ist als das Array, sind Kollisionen unvermeidlich - verschiedene Schlüssel können auf denselben Index verschlüsselt werden. Diese werden lokal in jedem Slot mit einer verknüpften Liste oder einem Rot-Schwarz-Baum behandelt.

Arrays bieten einen zeitlich konstanten Zugriff über den Index. Diese Eigenschaft - direkte, vorhersehbare Adressierung - ist die Grundlage für die Leistung der HashMap und das gleiche Prinzip, das dem effizienten Datenzugriff in großen Speichersystemen zugrunde liegt.

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>);
}

}

Wie lokalisiert eine HashMap Daten?

Schrittweise HashMap-Adressierung: Hash des Schlüssels, Berechnung des Array-Indexes, direkter Sprung zum Bucket und lokale Auflösung - dadurch wird O(1) Lookup ohne Traversal erreicht

Nehmen Sie put("apple", 100) als Beispiel. Die gesamte Suche erfolgt in vier Schritten - kein Full-Table-Scan:

1. Hash des Schlüssels: Übergeben Sie den Schlüssel durch eine Hash-Funktion →. hash("apple") = 93029210
2. Abbildung auf einen Array-Index: 93029210 & (arrayLength - 1) → z.B., 93029210 & 15 = 10
3. Sprung zum Bucket: Direkter Zugriff auf table[10] - ein einzelner Speicherzugriff, kein Traversal
4. Lokal auflösen: Wenn keine Kollision, sofort lesen oder schreiben. Wenn es eine Kollision gibt, eine kleine verknüpfte Liste oder einen rot-schwarzen Baum innerhalb des Buckets überprüfen.

Warum ist HashMap Lookup O(1)?

Der Array-Zugriff ist aufgrund einer einfachen Adressierungsformel O(1):

element_address = base_address + index × element_size

Bei einem Index wird die Speicheradresse mit einer Multiplikation und einer Addition berechnet. Die Kosten sind unabhängig von der Größe des Arrays gleich - eine Berechnung, ein Speicherzugriff. Eine verknüpfte Liste hingegen muss Knoten für Knoten durchlaufen werden, wobei Zeigern durch einzelne Speicherstellen gefolgt wird: O(n) im schlimmsten Fall.

Bei einer HashMap wird ein Schlüssel in einen Array-Index gehasht, was eine Durchquerung in eine berechnete Adresse verwandeln würde. Anstatt nach Daten zu suchen, wird genau berechnet, wo sich die Daten befinden und dorthin gesprungen.

Wie ändert sich die Adressierung in verteilten Systemen?

HashMap löst die Adressierung innerhalb einer einzelnen Maschine, wo die Daten im Speicher liegen und die Zugriffskosten trivial sind. Bei größeren Systemen ändern sich die Bedingungen drastisch:

Skalierungsfaktor	Auswirkung
Größe der Daten	Megabytes → Terabytes oder Petabytes in Clustern
Speichermedium	Speicher → Festplatte → Netzwerk → Objektspeicher
Zugriffslatenz	Speicher: ~100 ns / Festplatte: 10-20 ms / Same-DC-Netzwerk: ~0,5 ms / Regionsübergreifend: ~150 ms

Das Adressierungsproblem ändert sich nicht - es wird nur teurer. Jede Suche kann Netzwerksprünge und Festplatten-E/A beinhalten, so dass die Verringerung der Anzahl von Zugriffen viel wichtiger ist als im Speicher.

Um zu sehen, wie reale Systeme damit umgehen, schauen wir uns zwei klassische Beispiele an. HDFS wendet die rechnungsbasierte Adressierung auf große, blockbasierte Dateien an. Kafka wendet sie auf reine Append-Nachrichtenströme an. Beide folgen dem gleichen Prinzip: Berechnen, wo sich die Daten befinden, anstatt sie zu suchen.

HDFS: Adressierung großer Dateien mit In-Memory-Metadaten

HDFS ist ein verteiltes Speichersystem, das für sehr große Dateien auf mehreren Rechnern ausgelegt ist. Anhand eines Dateipfads und eines Byte-Offsets muss es den richtigen Datenblock und den DataNode finden, der ihn speichert.

HDFS löst dieses Problem mit einer bewussten Designentscheidung: alle Dateisystem-Metadaten werden im Speicher gehalten.

Die HDFS-Datenorganisation zeigt die logische Ansicht einer 300 MB großen Datei, die auf dem physischen Speicher als drei Blöcke verteilt auf DataNodes mit Replikation abgebildet ist

Im Zentrum steht der NameNode. Er lädt den gesamten Dateisystembaum - Verzeichnisstruktur, Datei-zu-Block-Zuordnungen und Block-zu-DataNode-Zuordnungen - in den Speicher. Da die Metadaten beim Lesen niemals die Festplatte berühren, löst HDFS alle Adressierungsfragen ausschließlich durch Nachschlagen im Speicher.

Vom Konzept her ist dies eine HashMap im Cluster-Maßstab: Verwendung von In-Memory-Datenstrukturen, um langsame Suchvorgänge in schnelle, berechnete Lookups zu verwandeln. Der Unterschied besteht darin, dass HDFS das gleiche Prinzip auf Datensätze anwendet, die über Tausende von Rechnern verteilt sind.

// 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
}

Wie lokalisiert HDFS Daten?

Stellen Sie sich vor, Sie lesen Daten im 200-MB-Offset von /user/data/bigfile.txt, mit einer Standard-Blockgröße von 128 MB:

1. Der Client sendet einen einzigen RPC an den NameNode
2. Der NameNode löst den Dateipfad auf und berechnet, dass der Offset 200 MB in den zweiten Block (Bereich 128-256 MB) fällt - vollständig im Speicher
3. Der NameNode gibt die DataNodes zurück, die diesen Block speichern (z. B. DN2 und DN3)
4. Der Client liest direkt vom nächstgelegenen DataNode (DN2)

Gesamtkosten: ein RPC, ein paar Suchvorgänge im Speicher, ein Datenlesevorgang. Die Metadaten werden während dieses Prozesses nie auf die Festplatte übertragen, und jeder Suchvorgang ist zeitlich konstant. HDFS vermeidet teure Metadatenscans, selbst wenn die Daten über große Cluster skaliert werden.

Apache Kafka: Wie Sparse Indexing zufällige E/A vermeidet

Apache Kafka ist für Nachrichtenströme mit hohem Durchsatz konzipiert. Bei einem Nachrichtenoffset muss die exakte Byteposition auf der Festplatte gefunden werden, ohne dass Lesevorgänge zu zufälligen E/A werden.

Kafka kombiniert sequenzielle Speicherung mit einem spärlichen, speicherinternen Index. Anstatt die Daten zu durchsuchen, wird eine ungefähre Position berechnet und ein kleiner, begrenzter Scan durchgeführt.

Die Kafka-Datenorganisation zeigt eine logische Ansicht mit Themen und Partitionen, die dem physischen Speicher als Partitionsverzeichnisse mit .log-, .index- und .timeindex-Segmentdateien zugeordnet sind

Nachrichten sind organisiert als Topic → Partition → Segment. Jede Partition ist ein reines Anhangsprotokoll, das in Segmente unterteilt ist, die jeweils aus folgenden Elementen bestehen:

• einer .log Datei, die Nachrichten sequentiell auf der Festplatte speichert
• einer .index Datei, die als spärlicher Index für das Protokoll dient

Die Datei .index ist memory-mapped (mmap), so dass Indexabfragen direkt aus dem Speicher ohne Festplatten-E/A durchgeführt werden.

Kafka-Sparse-Index-Design mit einem Indexeintrag pro 4 KB Daten, mit Speichervergleich: Dense-Index mit 800 MB gegenüber Sparse-Index mit nur 2 MB im Speicher

// 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)
}

Wie lokalisiert Kafka Daten?

Nehmen wir an, ein Verbraucher liest die Nachricht am Offset 500.000. Kafka löst dies in drei Schritten auf:

1. Lokalisieren des Segments (TreeMap-Lookup)

• Segment-Basis-Offsets: [0, 367834, 735668, 1103502]
• floorEntry(500000) → baseOffset = 367834
• Zieldatei: 00000000000000367834.log
• Zeitkomplexität: O(log S), wobei S die Anzahl der Segmente ist (normalerweise < 100)

2. Nachschlagen der Position im Sparse-Index (.index)

• Relativer Versatz: 500000 − 367834 = 132166
• Binäre Suche in .index: Suche nach dem größten Eintrag ≤ 132166 → [132100 → position 20500000]
• Zeitliche Komplexität: O(log N), wobei N die Anzahl der Indexeinträge ist

3. Sequentielles Lesen aus dem Protokoll (.log)

• Beginn des Lesens ab Position 20.500.000
• Fortsetzen, bis der Offset 500.000 erreicht ist
• Höchstens ein Indexintervall (~4 KB) wird gescannt

Insgesamt: ein In-Memory-Segment-Lookup, ein Index-Lookup, ein kurzes sequenzielles Lesen. Kein zufälliger Plattenzugriff.

HDFS vs. Apache Kafka

Dimension	HDFS	Kafka
Ziel der Entwicklung	Effizientes Speichern und Lesen von großen Dateien	Sequentielles Lesen/Schreiben von Nachrichtenströmen mit hohem Durchsatz
Adressierungsmodell	Pfad → Block → DataNode über speicherinterne HashMaps	Offset → Segment → Position über Sparse-Index + sequentielle Suche
Speicherung von Metadaten	Zentralisiert im NameNode-Speicher	Lokale Dateien, Speicherabbildung über mmap
Zugriffskosten pro Lookup	1 RPC + N Blocklesungen	1 Indexabfrage + 1 Datenlesung
Optimierung der Schlüssel	Alle Metadaten im Speicher - keine Festplatte im Suchpfad	Lückenhafte Indizierung + sequentielles Layout vermeidet zufällige E/A

Warum Objektspeicher das Adressierungsproblem verändern

Von HashMap bis HDFS und Kafka haben wir die Adressierung im Speicher und in klassischer verteilter Speicherung gesehen. Mit der Entwicklung der Arbeitslasten steigen auch die Anforderungen:

• Umfangreichere Abfragen. Moderne Systeme beherrschen Mehrfeldfilter, Ähnlichkeitssuche und komplexe Prädikate - nicht nur einfache Schlüssel und Offsets.
• Objektspeicher als Standard. Daten werden zunehmend in S3-kompatiblen Speichern gespeichert. Dateien sind über Buckets verteilt, und jeder Zugriff ist ein API-Aufruf mit einer festen Latenzzeit in der Größenordnung von zehn Millisekunden - selbst für einige Kilobytes.

An diesem Punkt ist die Latenz - nicht die Bandbreite - der Engpass. Eine einzelne S3-GET-Anfrage kostet ~50 ms, unabhängig davon, wie viele Daten sie zurückgibt. Wenn eine Abfrage Tausende solcher Anfragen auslöst, steigt die Gesamtlatenz in die Höhe. Die Minimierung des API-Fan-outs wird zur zentralen Design-Bedingung.

Wir werden uns zwei moderne Systeme ansehen - Milvus, eine Vektordatenbank, und Apache Iceberg, ein Lakehouse-Tabellenformat - um zu sehen, wie sie mit diesen Herausforderungen umgehen. Trotz ihrer Unterschiede gelten für beide Systeme dieselben Kerngedanken: Minimierung von Zugriffen mit hoher Latenz, frühzeitige Reduzierung des Fan-Out und Bevorzugung von Berechnungen gegenüber Traversierungen.

Milvus V1: Wenn Field-Level-Storage zu viele Dateien erzeugt

Milvus ist eine weit verbreitete Vektordatenbank, die für die Ähnlichkeitssuche über Vektoreinbettungen entwickelt wurde. Das frühe Speicherdesign spiegelt einen üblichen ersten Ansatz für den Aufbau eines Objektspeichers wider: jedes Feld wird separat gespeichert.

In V1 wird jedes Feld in einer Sammlung in separaten binlog-Dateien segmentübergreifend gespeichert.

Das Speicherlayout von Milvus V1 zeigt eine in Segmente aufgeteilte Sammlung, wobei jedes Segment Felder wie id-, Vektor- und Skalardaten in separaten binlog-Dateien speichert, sowie separate stats_log-Dateien für Dateistatistiken

Wie findet Milvus V1 die Daten?

Betrachten Sie eine einfache Abfrage: SELECT id, vector FROM collection WHERE id = 123.

1. Metadaten-Lookup - Abfrage von etcd/MySQL für die Segmentliste → Lesen des id-Feldes über die Segmente [Segment 12345, 12346, 12347, …]
2. Lesen des id-Feldes in allen Segmenten - Für jedes Segment die id-Binlog-Dateien lesen
3. Suche nach der Zielzeile - Scannen der geladenen id-Daten, um zu finden id = 123
4. Lesen des Vektorfeldes - Lesen der entsprechenden Vektor-Binlogdateien für das passende Segment

Dateizugriffe insgesamt: N × (F₁ + F₂ + ...) wobei N = Anzahl der Segmente, F = binlog-Dateien pro Feld.

Die Rechnung wird schnell hässlich. Für eine Sammlung mit 100 Feldern, 1.000 Segmenten und 5 binlog-Dateien pro Feld:

1.000 × 100 × 5 = 500.000 Dateien

Selbst wenn eine Abfrage nur drei Felder berührt, sind das 15.000 Aufrufe der Objektspeicher-API. Bei 50 ms pro S3-Anfrage erreicht die serialisierte Latenz 750 Sekunden - über 12 Minuten für eine einzige Abfrage.

Milvus V2: Wie Segment-Level Parquet die API-Aufrufe um das 10-fache reduziert

Um die Grenzen der Skalierbarkeit in V1 zu beheben, nimmt Milvus V2 eine grundlegende Änderung vor: Die Daten werden nach Segmenten statt nach Feldern organisiert. Anstatt vieler kleiner binlog-Dateien werden in V2 die Daten in segmentbasierten Parquet-Dateien konsolidiert.

Die Anzahl der Dateien sinkt von N × fields × binlogs auf etwa N (eine Dateigruppe pro Segment).

Das Milvus-V2-Speicherlayout zeigt ein als Parquet-Dateien gespeichertes Segment mit Zeilengruppen, die Spaltenblöcke für ID, Vektor und Zeitstempel enthalten, sowie eine Fußzeile mit Schema- und Spaltenstatistiken

V2 speichert jedoch nicht alle Felder in einer einzigen Datei. Es gruppiert die Felder nach Größe:

• Kleine skalare Felder (wie id, timestamp) werden zusammen gespeichert.
• Große Felder (wie dichte Vektoren) werden in eigene Dateien aufgeteilt

Alle Dateien gehören zu demselben Segment, und die Zeilen werden nach dem Index über die Dateien hinweg ausgerichtet.

Parquet-Dateistruktur mit Zeilengruppen mit Spaltenblöcken und komprimierten Datenseiten sowie einer Fußzeile mit Dateimetadaten, Zeilengruppen-Metadaten und Spaltenstatistiken wie Min/Max-Werten

Wie findet Milvus V2 die Daten?

Für dieselbe Abfrage - SELECT id, vector FROM collection WHERE id = 123:

1. Metadaten-Lookup - Abrufen der Segmentliste → Lesen von Parquet-Fußzeilen [12345, 12346, …]
2. Parquet-Fußzeilen lesen - Zeilengruppenstatistiken extrahieren. Prüfen Sie das Minimum/Maximum der id-Spalte pro Zeilengruppe. id = 123 fällt in die Zeilengruppe 0 (min=1, max=1000).
3. Nur lesen, was gebraucht wird - Die Spaltenbeschneidung von Parquet liest nur die id-Spalte aus der Small-Field-Datei und nur die Vektorspalte aus der Large-Field-Datei. Es wird nur auf passende Zeilengruppen zugegriffen.

Die Aufteilung großer Felder bietet zwei wesentliche Vorteile:

• Effizientere Lesevorgänge. Vektoreinbettungen dominieren die Speichergröße. Zusammen mit kleinen Feldern begrenzen sie die Anzahl der Zeilen, die in eine Zeilengruppe passen, was die Dateizugriffe erhöht. Durch ihre Isolierung können Zeilengruppen mit kleinen Feldern viel mehr Zeilen aufnehmen, während große Felder Layouts verwenden, die für ihre Größe optimiert sind.
• Flexible Schema-Entwicklung. Das Hinzufügen einer Spalte bedeutet das Erstellen einer neuen Datei. Das Entfernen einer Spalte bedeutet, dass sie zur Lesezeit übersprungen wird. Es müssen keine historischen Daten neu geschrieben werden.

Das Ergebnis: Die Anzahl der Dateien sinkt um mehr als das Zehnfache, die API-Aufrufe um mehr als das Zehnfache und die Abfragelatenz sinkt von Minuten auf Sekunden.

Milvus V1 vs. V2

Aspekt	V1	V2
Dateiorganisation	Aufgeteilt nach Feldern	Integriert nach Segmenten
Dateien pro Sammlung	N × Felder × binlogs	~N × Spaltengruppen
Speicherformat	Benutzerdefiniertes Binlog	Parquet (unterstützt auch Lance und Vortex)
Säulenbeschneidung	Natürlich (Dateien auf Feldebene)	Parquet-Spaltenbeschneidung
Statistik	Separate stats_log-Dateien	Eingebettet in Parquet-Fußzeile
S3-API-Aufrufe pro Abfrage	10,000+	~1,000
Abfrage-Latenzzeit	Minuten	Sekunden

Apache Iceberg: Metadaten-gesteuertes File Pruning

Apache Iceberg verwaltet analytische Tabellen über umfangreiche Datensätze in Lakehouse-Systemen. Wenn sich eine Tabelle über Tausende von Dateien erstreckt, besteht die Herausforderung darin, eine Abfrage auf die relevanten Dateien einzugrenzen - ohne alle Dateien zu scannen.

Die Antwort von Iceberg: Die Entscheidung, welche Dateien gelesen werden sollen , bevor eine Datenein- oder -ausgabe erfolgt, wird mit Hilfe von mehrschichtigen Metadaten getroffen. Dies ist das gleiche Prinzip wie bei der Filterung von Metadaten in Vektordatenbanken - vorberechnete Statistiken werden verwendet, um irrelevante Daten zu überspringen.

Die Iceberg-Datenorganisation zeigt ein Metadatenverzeichnis mit metadata.json, Manifestlisten und Manifestdateien neben einem Datenverzeichnis mit datumsseparierten Parquet-Dateien

Iceberg verwendet eine mehrschichtige Metadatenstruktur. Jede Schicht filtert irrelevante Daten heraus, bevor die nächste konsultiert wird - ähnlich wie bei verteilten Datenbanken, die Metadaten von den Daten trennen, um einen effizienten Zugriff zu ermöglichen.

Icebergs vierschichtige Architektur: metadata.json verweist auf Manifestlisten, die auf Manifestdateien verweisen, welche Statistiken auf Dateiebene enthalten, die wiederum auf die eigentlichen Parquet-Datendateien verweisen

Wie findet Iceberg die Daten?

Überlegen Sie: SELECT * FROM orders WHERE date=’2024-01-15’ AND amount>1000.

1. Lesen von metadata.json (1 I/O) - Laden des aktuellen Snapshots und seiner Manifestlisten
2. Lesen der Manifestliste (1 E/A) - Anwenden von Filtern auf Partitionsebene, um ganze Partitionen zu überspringen (z. B. werden alle 2023-Daten eliminiert)
3. Lesen der Manifestdateien (2 E/A) - Verwendung von Statistiken auf Dateiebene (Mindest-/Maximaldatum, Mindest-/Maximalmenge) zur Eliminierung von Dateien, die der Abfrage nicht entsprechen können
4. Lesen von Datendateien (3 E/A) - Nur drei Dateien bleiben übrig und werden tatsächlich gelesen.

Anstatt alle 1.000 Datendateien zu scannen, schließt Iceberg die Suche in 7 E/A-Operationen ab und vermeidet so über 94 % der unnötigen Lesevorgänge.

Wie verschiedene Systeme Daten adressieren

System	Organisation der Daten	Kern-Adressierungsmechanismus	Zugriffskosten
HashMap	Schlüssel → Array-Slot	Hash-Funktion → direkter Index	O(1) Speicherzugriff
HDFS	Pfad → Block → DataNode	In-Memory HashMaps + Blockberechnung	1 RPC + N Blocklesungen
Kafka	Thema → Partition → Segment	TreeMap + spärlicher Index + sequentieller Scan	1 Indexnachschlag + 1 Datenlesung
Milvus V2	Sammlung → Segment → Parquet-Spalten	Nachschlagen von Metadaten + Spaltenbeschneidung	N Lesevorgänge (N = Segmente)
Eisberg	Tabelle → Schnappschuss → Manifest → Datendateien	Schichtweise Metadaten + statistisches Pruning	3 Metadatenlesungen + M Datenlesungen

Drei Prinzipien der effizienten Datenadressierung

1. Berechnung ist immer besser als Suche

Bei allen von uns untersuchten Systemen folgt die effektivste Optimierung derselben Regel: Berechnen Sie, wo sich die Daten befinden, anstatt sie zu suchen.

• HashMap berechnet einen Array-Index von hash(key), anstatt zu scannen.
• HDFS berechnet den Zielblock aus einem Dateiversatz, anstatt die Metadaten des Dateisystems zu durchsuchen
• Kafka berechnet das relevante Segment und die Indexposition, anstatt das Protokoll zu scannen
• Iceberg verwendet Prädikate und Statistiken auf Dateiebene, um zu berechnen, welche Dateien lesenswert sind.

Berechnung ist Arithmetik mit festen Kosten. Die Suche ist eine Durchquerung - Vergleiche, Zeigerjagd oder E/A - und die Kosten wachsen mit der Datengröße. Wenn ein System einen Ort direkt ableiten kann, wird das Scannen überflüssig.

2. Minimierung von Zugriffen mit hoher Latenz

Damit sind wir wieder bei der Kernformel angelangt: Gesamtadressierungskosten = Metadatenzugriffe + Datenzugriffe. Jede Optimierung zielt letztlich darauf ab, diese Operationen mit hoher Latenzzeit zu reduzieren.

Muster	Beispiel
Verringern der Dateianzahl zur Begrenzung des API-Fan-Outs	Milvus V2 Segment-Konsolidierung
Verwendung von Statistiken, um Daten frühzeitig auszuschließen	Eisberg-Manifest-Bereinigung
Cache-Metadaten im Speicher	HDFS NameNode, Kafka mmap-Indizes
Kleine sequenzielle Scans gegen weniger zufällige Lesevorgänge tauschen	Kafka Sparse-Index

3. Statistiken ermöglichen frühe Entscheidungen

Durch die Aufzeichnung einfacher Informationen zum Zeitpunkt des Schreibens - Minimal-/Maximalwerte, Partitionsgrenzen, Zeilenzahl - können Systeme zum Zeitpunkt des Lesens entscheiden, welche Dateien lesenswert sind und welche vollständig übersprungen werden können.

Dies ist eine kleine Investition mit großem Nutzen. Statistiken machen den Dateizugriff von einem blinden Lesen zu einer bewussten Entscheidung. Ob Icebergs Pruning auf Manifest-Ebene oder die Parquet-Footer-Statistiken von Milvus V2, das Prinzip ist dasselbe: Ein paar Bytes Metadaten beim Schreiben können Tausende von E/A-Operationen beim Lesen vermeiden.

Schlussfolgerung

Von Two Sum zu HashMap und von HDFS und Kafka zu Milvus und Apache Iceberg, ein Muster wiederholt sich immer wieder: Die Leistung hängt davon ab, wie effizient ein System Daten lokalisiert.

Mit dem Wachstum der Daten und der Verlagerung der Speicherung vom Arbeitsspeicher über die Festplatte zum Objektspeicher ändern sich die Mechanismen, nicht aber die Kerngedanken. Die besten Systeme berechnen Speicherorte, anstatt sie zu durchsuchen, halten Metadaten in der Nähe und verwenden Statistiken, um Daten zu vermeiden, die nicht wichtig sind. Alle von uns untersuchten Leistungssteigerungen beruhen auf der Reduzierung von Zugriffen mit hoher Latenz und der frühestmöglichen Eingrenzung des Suchraums.

Unabhängig davon, ob Sie eine Vektorsuchpipeline entwickeln, Systeme für unstrukturierte Daten aufbauen oder eine Lakehouse-Abfrage-Engine optimieren, gilt die gleiche Gleichung. Zu verstehen, wie Ihr System Daten anspricht, ist der erste Schritt, um es schneller zu machen.

---

Wenn Sie mit Milvus arbeiten und Ihre Speicher- oder Abfrageleistung optimieren möchten, helfen wir Ihnen gerne:

• Treten Sie der Milvus-Slack-Community bei, um Fragen zu stellen, Ihre Architektur zu teilen und von anderen Ingenieuren zu lernen, die an ähnlichen Problemen arbeiten.
• Buchen Sie eine kostenlose 20-minütige Milvus-Sprechstunde, um Ihren Anwendungsfall zu besprechen - egal, ob es sich um Speicherlayout, Abfrageoptimierung oder Skalierung auf Produktion handelt.
• Wenn Sie die Einrichtung der Infrastruktur lieber überspringen möchten, bietet Zilliz Cloud (managed Milvus) ein kostenloses Tier für den Einstieg.

---

Ein paar Fragen, die auftauchen, wenn Ingenieure über Datenadressierung und Speicherdesign nachdenken:

F: Warum hat Milvus von der Feld- zur Segmentebene gewechselt?

In Milvus V1 wurde jedes Feld segmentübergreifend in separaten binlog-Dateien gespeichert. Bei einer Sammlung mit 100 Feldern und 1.000 Segmenten entstanden so Hunderttausende kleiner Dateien, die jeweils einen eigenen S3-API-Aufruf erforderten. V2 konsolidiert Daten in segmentbasierten Parquet-Dateien, wodurch die Anzahl der Dateien um mehr als das Zehnfache reduziert und die Abfragelatenz von Minuten auf Sekunden gesenkt werden konnte. Die wichtigste Erkenntnis: Bei Objektspeichern ist die Anzahl der API-Aufrufe wichtiger als das Gesamtdatenvolumen.

F: Wie kann Milvus sowohl die Vektorsuche als auch die skalare Filterung effizient handhaben?

Milvus V2 speichert skalare Felder und Vektorfelder in separaten Dateigruppen innerhalb desselben Segments. Skalare Abfragen verwenden Parquet-Spaltenbeschneidung und Zeilengruppenstatistiken, um irrelevante Daten zu überspringen. Die Vektorsuche verwendet spezielle Vektorindizes. Beide nutzen dieselbe Segmentstruktur, so dass hybride Abfragen - die skalare Filter mit vektorieller Ähnlichkeit kombinieren - auf denselben Daten ohne Duplizierung arbeiten können.

F: Gilt für Vektordatenbanken der Grundsatz "Rechnen vor Suchen"?

Ja. Vektorindizes wie HNSW und IVF basieren auf der gleichen Idee. Anstatt einen Abfragevektor mit jedem gespeicherten Vektor zu vergleichen (Brute-Force-Suche), verwenden sie Graphenstrukturen oder Clusterschwerpunkte, um ungefähre Nachbarschaften zu berechnen und direkt zu relevanten Regionen des Vektorraums zu springen. Der Kompromiss - ein kleiner Genauigkeitsverlust für eine um Größenordnungen geringere Anzahl von Abstandsberechnungen - ist das gleiche Muster "Berechnung vor Suche", das bei hochdimensionalen Einbettungsdaten angewandt wird.

F: Was ist der größte Leistungsfehler, den Teams bei der Objektspeicherung machen?

Die Erstellung zu vieler kleiner Dateien. Jede S3-GET-Anfrage hat eine feste Latenzzeit (~50 ms), unabhängig davon, wie viele Daten sie zurückgibt. Ein System, das 10.000 kleine Dateien liest, hat eine Latenz von 500 Sekunden - selbst wenn das Gesamtdatenvolumen bescheiden ist. Die Lösung liegt in der Konsolidierung: kleine Dateien in größere zusammenführen, kolumnare Formate wie Parquet für selektive Lesevorgänge verwenden und Metadaten pflegen, die das Überspringen von Dateien ermöglichen.