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 Dateisystem, das permanente Snapshots bietet – verwendet.

Geschichte

Entwickelt wurde Venti von Sean Quinlan und Sean Dorward in den Bell Laboratories. Es erschien erstmals 2002 in Plan 9. Die Entwicklung wurde von Russ Cox fortgesetzt, der den Großteil neu implementiert hat und eine Bibliothek für Venti-optimierte Datenstrukturen (Dateien, Verzeichnisse, Metadaten) entwickelt. Venti ist sowohl in Plan-9-Distributionen und -Forks als auch in einer Portierung für unixoide Systeme (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.

Ein Löschen von Datenblöcken ist nicht vorgesehen. 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 Hash-Baum, um große Dateien zu speichern. Venti selbst kümmert sich nicht um Inhalt oder Struktur der gespeicherten Daten, es speichert lediglich den Typen des Datenblocks.

Das Venti-Design bietet einige technische Vorteile gegenüber vergleichbaren Alternativen:

• 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 Fragmentierung des Dateisystems auftreten.
• Clients können die Korrektheit des Servers prüfen: die Score der zurückgelieferten Daten muss immer mit der angefragten Score übereinstimmen. Somit werden 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 separater Medien (z. B. CD-ROM/DVD, Bandlaufwerk, 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 (Datenprotokoll). Ein weiterer Satz von Dateien bilden den Index, der Scores auf konkrete Positionen innerhalb des data log abbildet. Die Datenstruktur des Index ist eine Hashtabelle 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 Schubfachprinzip 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 SHA-1-Hash das Risiko einer (zufälligen) Kollision infinitesimal ist, selbst in Größenordnung von Exabytes. 2005 gab es jedoch signifikante Fortschritte, um den Rechenaufwand zur Schaffung künstlicher SHA-1-Kollisionen zu senken (dennoch bleibt es enorm aufwendig). 2017 wurde von Google und CWI Amsterdam eine SHA-1-Kollision vorgestellt.

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