# Sharding

`DocStore` schreibt eine Datei pro Datensatz. Ohne Sharding würden sich in einer großen Sammlung alle Dateien in einem Verzeichnis ansammeln, und Verzeichnisoperationen werden mit zunehmender Eintragszahl langsamer. Deshalb verteilt storh Datensatzdateien anhand von zwei Zeichen der Datensatz-ID auf Buckets:

```text
pages/data/2d/018bcfe5-6800-7000-8000-2d5dba6274da.jsonc
```

Der Bucket wird anhand der ersten beiden Zeichen der letzten Gruppe der UUID bestimmt (Zeichen 24 und 25), die zufällige Entropie enthalten. Zwei Hexadezimalzeichen ergeben 256 Buckets. Bei einer Sammlung mit 100.000 Datensätzen befinden sich daher durchschnittlich weniger als 400 Dateien pro Verzeichnis.

## Warum das Ende und nicht der Anfang

UUIDv7-IDs beginnen mit einem Zeitstempel in Millisekunden auf 48 Bit. Deshalb haben IDs, die kurz nacheinander erstellt werden, dieselben führenden Zeichen. Sharding nach Präfix würde alle Schreibspitzen in dasselbe stark beanspruchte Verzeichnis leiten und die Buckets erst mit der Zeit wechseln. Die letzten Bytes sind pro Datensatz zufällig, sodass sich Schreibvorgänge von Anfang an gleichmäßig verteilen.

Sharding bleibt bei Lesezugriffen und Abfragen unsichtbar: `get()` berechnet den Bucket anhand der ID, und `stream()` gibt Datensätze aus allen Buckets nach ID sortiert zurück. Dadurch verhält sich die Cursor-Paginierung so, als wäre die Sammlung eine einzige sortierte Liste.

## Bei großen Sammlungen

Die Anzahl der Buckets wächst nie: Zwei Hexadezimalzeichen ergeben unabhängig von der Sammlungsgröße 256 Verzeichnisse. Was wächst, ist die Anzahl der Dateien pro Bucket:

| Datensätze | Dateien pro Bucket |
| ------- | ---------------- |
| 10k     | ~40              |
| 100k    | ~390             |
| 1M      | ~3,900           |
| 10M     | ~39,000          |

Moderne Dateisysteme indizieren Verzeichniseinträge. Deshalb halten einige Tausend Dateien pro Bucket einzelne Abfragen schnell; 1M Datensätze sind für `get()` und indizierte Abfragen problemlos. Ein Store lässt sich unabhängig von der Größe der Sammlung in konstanter Zeit öffnen: Die Bereinigung verwaister temporärer Dateien läuft nur, wenn eine zurückgelassene Markierung eines inaktiven Schreibers zeigt, dass ein vorheriger Prozess während des Schreibens abgestürzt ist. Was mit zunehmender Größe linear wächst, sind Operationen über die gesamte Sammlung: nicht indizierte Scans, `reindex()` und `verify()` durchlaufen jede Datensatzdatei und sollten daher als Batch-Jobs behandelt werden. Ab etwa 10M Datensätzen pro Sammlung spielen die Anzahl pro Bucket und die Gesamtzahl der Inodes eine Rolle: Teile Sammlungen auf oder verwende für scanartige Daten das segmentierte Log, das die Dateianzahl von vornherein niedrig hält.

## Die anderen Engines

`SegmentedLog` und `Queue` benötigen keine Shards, da sie nicht eine Datei pro Datensatz erstellen. Das Log hängt Daten an Segmentdateien unter `segments/` an, begrenzt durch `max_segment_bytes` (standardmäßig 1 MiB), und die Warteschlange hängt Ereignisse an eine einzelne `queue.log` an. Die Dateianzahl bleibt von vornherein niedrig.