Venti (Speichertechnologie)

Venti ist ein Netzwerk-Speicher-System, das Datenblöcke permanent speichert. Der 160-bit SHA-1 Hashcode des Blocks (Score genannt) dient zur Adressierung der Daten. Damit wird sichergestellt, dass gleiche Datenblöcke nur einmal gespeichert werden, auch wenn sie mehrfach geschrieben werden, da gleiche Blöcke auch die gleiche Adresse erhalten. Jedoch können Blöcke nicht wieder entfernt werden. Damit eignet sich Venti für ewige Archive und Backups. Venti wird zumeist mit dem Archivprogrammen vac und vtstore, oder auch mit Fossil – einem Filesystem, das permanente Snapshots bietet – verwendet.

Geschichte

Entwickelt wurde Venti von Sean Quinlan und Sean Dorward in den Bell Labs. Es erschien in der Plan 9-Distribution in 2002. Die Entwicklung wurde von Russ Cox fortgesetzt, der den Großteil neu implementiert und eine Bibliothek für Venti-optimierte Datenstrukturen (Dateien, Verzeichnisse, Metadaten) entwickelt. Venti ist sowohl in der Plan9-Distribution als auch in einer Portierung für GNU/Linux und FreeBSD (als Teil von Plan 9 from User Space) verfügbar.

Details

Venti ist ein Userspace-Daemon. Clients verbinden sich mit über TCP und kommunizieren über ein einfaches RPC-Protokoll. Die wichtigsten RPC-Nachrichten sind wie folgt:

• read(score, type), liefert den Datenblock zu gegebener Score und Typ
• write(data, type), speichert einen Datenblock mit gegebenem Typ. Die Score setzt sich aus dem berechneten SHA-1-Hashcode und dem Typ zusammen.

Beachte, dass es keine Nachrichten zum Löschen oder Ändern eines Datenblocks gibt.

Die zu speichernden Datenblöcke dürfen nicht kleiner als 512 Bytes oder größer als 56 kB sein. Möchte ein Client größere Dateien speichern, so zerlegt er diese in bis zu 56 kB große Blöcke und speichert die resultierenden Scores in einer geeigneten Datenstruktur wiederum im Venti. Beispielsweise verwendet Fossil einen Hashtree um große Dateien zu speichern. Venti selbst kümmert sich nicht um Inhalt oder Struktur der gespeicherten Daten, es speichert lediglich den Typ des Datenblocks.

Das Venti-Design hat einige interessante Konsequenzen:

• Da alle Schreiboperationen permanent sind, das heißt lediglich neue Daten hinzukommen (was eine sehr einfache Implementierung, damit geringere Gefahr von Datenverlusten durch Bugs, ermöglicht), kann auch keine Filesystem-Fragmentierung auftreten.
• Clients können die Korrektheit des Servers prüfen: die Score der zurückgelieferten Daten muss immer mit der angefragten Score übereinstimmen. Da SHA-1 ein kryptographisch-sicherer Hash ist, werden somit nicht nur technische Defekte sondern auch Fälschungsversuche aufgedeckt.
• Daten können nicht überschrieben werden. Ist eine Score vorhanden, dann sind auch die zugehörigen Daten vorhanden.
• Wenig Bedarf an Nutzer-Authentifizierung: die Daten können nicht manipuliert oder zerstört werden, und man kann nur lesen, wenn die passende Score bekannt ist. Eine Bedrohung besteht allenfalls darin, dass ein Angreifer den Speicherplatz füllt.
• Komprimierung wird ohne komplizierte Disk-Strukturen möglich.
• Inkrementelle Datensicherung separate Medien (z. B. CDROM/DVD, Tape, Netzwerk) wird sehr einfach.
• Redundante, sich automatisch synchronisierende Venti-Implementierungen sind einfach und ohne Anpassung der Clients möglich.

Die Datenblöcke werden in Dateien fester Größe – Arenas genannt – gespeichert, typischerweise Festplatten oder -Partitionen, zum Beispiel in einem RAID-Verbund. Die einzelnen Arenas werden dabei meist so dimensioniert, dass sie sich leicht auf andere Medien (z. B. CD/DVD) oder Magnetband schreiben lassen. Alle Arenas zusammen genommen bilden das data log. Ein weiterer Satz von Dateien bilden den Index, der Scores auf konkrete Positionen innerhalb des data log abbildet. Die Datenstruktur des Index ist eine Hashtable mit einer festen Bucket-Größe. Venti verlässt sich auf die zufällige Verteilung der Hashcodes, damit die Buckets nicht überfüllt werden. Da jeder Index-Lookup einen Disk-Seek kostet, bietet es sich an, den Index auf mehrere kleine Disks mit kurzer Zugriffszeit zu verteilen. Die strikte Aufteilung in Datalog und Index hat einen weiteren Vorteil: der Index kann bei einem Datenverlust rekonstruiert werden.

Hash-Kollisionen

Ein grundlegendes Prinzip der Informationstheorie, das pigeonhole principle besagt, dass bei einer Funktion, die eine große Menge A auf eine kleine Menge B abbildet, diese Abbildung nicht eineindeutig bzw. umkehrbar ist. Es existieren also mehrere Elemente aus A, die auf das gleiche Element aus B abgebildet werden. Theoretisch existieren also sehr viele verschiedene Datenblöcke mit gleichem Hashcode – dies wird auch Kollision genannt.

Venti beschäftigt sich jedoch nicht mit dieser Frage. Es wird argumentiert, dass bei einem SHA1-Hash das Risiko einer (zufälligen) Kollision infinitesimal ist, selbst in Größenordnung von Exabytes.^[1] 2005 gab es jedoch signifikante Fortschritte, um den Rechenaufwand zur Schaffung künstlicher SHA1-Kollisionen zu senken (dennoch bleibt es enorm aufwendig).

Weblinks

• Venti: a new approach to archival storage, paper describing Venti (Also available as a PDF)
• New Venti manual page (overview), section 1 and 8 venti manual pages also exist
• Old Venti manual page, no longer in use on Plan 9.
• Old Venti utilities manual page, no longer in use on Plan 9.

Einzelnachweise

1. ↑ http://plan9.bell-labs.com/sys/doc/venti/venti.html