© Jane Rix, 123RF.com

USB-Sticks und SD-Karten verlieren schnell an Wert. Verteilt ein Skript Daten auf mehrere solcher Speicher, taugen Flashspeicher trotz begrenzter Kapazität als schnelle und zudem stoßsichere Backupmedien.

Es scheint, als ob auch USB-Sticks und SD-Karten dem Mooreschen Gesetz folgen, da sich die Kapazität angebotener Speicher jedes Jahr verdoppelt. Ein Stick mit 64 GByte kostet heute 40 US-Dollar, und ein vor Jahren führender 8-GByte-Stick hat fast allen Wert verloren und landet in der Schublade. Am anderen Ende des Produktspektrums steigen die Preise dagegen überproportional: Kostet ein 128-GByte-Stick etwa 80 Dollar, schlägt die doppelte Kapazität, 256 GByte, mit dem vierfachen Preis zu Buche.

Mehrere Einzelspeicher zu kombinieren würde akzeptable Kapazitäten zu einem niedrigen Preis bedeuten. Um mehrere Speicherbausteine zu einem Verbund zusammenzuschließen, böte sich eine Softwarelösung wie der Linux Volume Manager (LVM) an, der Hardware- elegant und zuverlässig zu Softwarepartitionen zusammenschweißt, die sich auf der Applikationsebene dann exakt wie ihre in Metall und Plastik gegossenen Hardwarelösungen anfühlen.

Abbildung 1: Verschieden große USB-Sticks und SD-Karten dienen kombiniert als Speichermedium.

Rucksackproblem

Allerdings will wohl kaum jemand die USB-Ports seines Rechners jedes Mal mit einer ganzen Handvoll USB-Sticks akupunktieren, nur um eine LVM-Partition zu mounten, die Zugriff auf ein Backup bietet. Besser wäre es, einzelne Dateien auf die Sticks zu verteilen. Die Literatur beschreibt das Verfahren als Rucksackproblem [2]. In dieser Optimierungsaufgabe der Kombinatorik gilt es, verschieden schwere Gegenstände in Rucksäcke zu verpacken, von denen keiner sein spezifisches Höchstgewicht überschreiten darf.

Dem Gewicht eines Gegenstands entspricht beim Backup die Größe einer Datei in Bytes. Der Rucksack ist der USB-Stick, der eine Reihe dieser Dateien speichert. Da sich das Problem der Klasse NP-vollständig (nicht-deterministisch polynominell vollständig, [3]) zuordnen lässt, ist es nachweisbar unökonomisch, die optimale Verteilung der Gegenstände zu finden. Bei den USB-Sticks spielen ein paar verschenkte Bytes jedoch keine Rolle, und ein simpler Algorithmus darf die “Behälter” einfach der Reihe nach befüllen, bis sie voll sind, und dann jeweils zum nächsten freien übergehen (Abbildung 2).

Abbildung 2: Der Rucksackalgorithmus füllt einen Behälter vollständig und schreitet dann zum nächsten.

Wie groß die einzelnen Behälter sind, hängt von der Größe der verwendeten USB-Sticks ab, die oft unterschiedliche Speicherkapazitäten aufweisen. Die Yaml-Datei ein Listing 1 gibt daher vor, wie die Sticks heißen und wie viele Bytes sie fassen können. Im Beispiel nummeriert die Datei die Sticks einfach durch. Mit einem Etikettendrucker lassen sich die Sticks im Verbund prima beschriften.

01 -
02   name: 1
03   size: 4g
04
05 -
06   name: 2
07   size: 8g
08
09 -
10   name: 3
11   size: 4g

Gilt es zum Beispiel, PDF-Dateien in einem Verzeichnis auf USB-Sticks zu verteilen, legt das Skript in Listing 2 zunächst ein neues Verzeichnis an und weist ihm gemäß der Yaml-Datei eine Byte-Kapazität zu. Dann füllt es den Behälter, indem es symbolische Links im Zielverzeichnis anlegt, die auf die Dateien im Originalverzeichnis zeigen, und zählt mit, wie viele Bytes symbolisch im Rucksack liegen, obwohl der Symlink natürlich kaum Speicher verbraucht.

Ist der Rucksack voll, legt das Skript gemäß der Konfiguration in Listing 1 einen neuen an und setzt das Verfahren fort, bis es keine Dateien mehr findet oder die definierten Behälter verbraucht sind. Die Symlinks verbleiben auch nach dem Skriptlauf in den Zielverzeichnissen und geben Auskunft darüber, welche Originaldateien schon gesichert sind.

01 #!/usr/local/bin/perl -w
02 use strict;
03 use local::lib;
04 use YAML qw( LoadFile );
05 use Algorithm::Bucketizer 0.13;
06 use File::Basename;
07 use Sysadm::Install qw( :all );
08 use Log::Log4perl qw(:easy);
09
10 Log::Log4perl->easy_init($DEBUG);
11
12 my( $home )  = glob "~";
13 my $src_dir  = "$home/books";
14 my $dst_dir  = "$home/sticks";
15 my $cfg_file = "usbback.yml";
16 my $gig      = 1_000_000_000;
17 my $buckets = Algorithm::Bucketizer->new();
18
19 my $conf = LoadFile $cfg_file;
20
21 my %files = ();
22
23 for my $path ( <$src_dir/*> ) {
24   my $file = basename $path;
25   $files{ $file } =
26     blocksize_round( -s $path );
27 }
28
29   # buckets configured in YAML
30 for my $entry ( @$conf ) {
31   my $bucket_dir  = $entry->{ name };
32   my $bucket_path = "$dst_dir/$bucket_dir";
33
34   if( !-d $bucket_path ) {
35     mkd $bucket_path;
36   }
37   if( $entry->{ size } =~ /(\d+)g/ ) {
38       $entry->{ size } = $1 * $gig;
39   }
40
41   my $bucket = $buckets->add_bucket(
42       maxsize => $entry->{ size },
43       dir     => $bucket_path,
44   );
45
46     # prefill buckets with links found
47   for my $path ( <$bucket_path/*> ) {
48     my $file = basename $path;
49     my $ref  = readlink $path;
50     my $size = blocksize_round( -s $ref );
51
52     $buckets->prefill_bucket(
53         $bucket->idx(), $file, $size );
54
55     delete $files{ $file };
56   }
57 }
58
59   # remaining files
60 for my $file ( sort keys %files ) {
61   my $size = $files{ $file };
62
63   my $bucket = $buckets->add_item(
64       $file, $size ) or
65         die "Item $file won't fit, " .
66         "buckets are full";
67
68   INFO "Adding $file ($size bytes) to ",
69     "bucket $bucket->{ dir }";
70
71   symlink "$src_dir/$file",
72           "$bucket->{ dir }/$file";
73 }
74
75 ###########################################
76 sub blocksize_round {
77 ###########################################
78   my( $size ) = @_;
79
80   my $bs = 4096;
81
82   if( ($size % $bs) ) {
83       return (int( $size/$bs ) + 1 ) * $bs;
84   }
85
86   return $size;
87 }

Konstanz spart Arbeit

Bei einem erneuten Backuplauf stellt das Skript fest, welcher Rucksack schon mit welchen Dateien gefüllt ist, und sucht für noch nicht gesicherte Dateien im Originalverzeichnis aufnahmefähige Behälter. Das hat den Vorteil, dass der User bereits gefüllte USB-Speichersticks nicht bei jedem Backuplauf neu einstecken und auffrischen muss. Die Daten darauf haben sich ja nicht geändert. Der Einfachheit halber geht der Algorithmus davon aus, dass nur neue Dateien ins Originalverzeichnis kommen, wie das etwa bei einer E-Book-Bibliothek mit PDF-Dateien oder einer Musiksammlung der Fall ist.

Symlinks aufblasen

Die Verzeichnisse mit den Symlinks kopiert dann ein »rsync –copy-links« -Kommando auf die zugewiesenen Sticks. Abbildung 3 demonstriert, wie alle Symlinks aus dem Rucksack mit dem Namen »3« auf Dateien verweisen, die insgesamt 4 GByte auf die Waage bringen. Rsync kopiert die Datei-Inhalte, und ein danach abgesetztes »df« -Kommando auf den unter »/dev/sdb1« eingestöpselten und unter »/media/8CB1-7B24« gemounteten Stick beweist, dass dieser nun bis zur Unterkante Oberlippe gefüllt ist.

Das Skript in Listing 2 benutzt zur Rucksackverwaltung das CPAN-Modul Algorithm::Bucketizer, das mit variablen Behältergrößen umgehen und sie vorab befüllen kann, bevor der Algorithmus aufnahmefähige Behälter für neue Einträge sucht. Die Berechnung, wie viele Dateien ein Zielverzeichnis tatsächlich aufnehmen kann, scheint einfach: Subtrahiere die einzelnen Dateigrößen von dem auf dem Stick aufgedruckten Wert. So simpel liegt die Sache nicht, denn auch zwei Mitesser laben sich an der Kapazität.

Dass Zeile 16 den Wert 1 GByte mit »1 000 000 000« angibt, liegt daran, dass Festplatten- und USB-Stick-Hersteller seit jeher falsche Zahlen publizieren. Kein einziger 4-GByte-Stick auf dem Markt hat 4 mal 10243, also 4 294 967 312 Bytes, sondern nur 4 000 000 000. Ein PC zeigt aber die echten 3,8 GByte an – und der User bleibt verwirrt zurück. Kein Anbieter hat offenbar den Mut, diesen Irrsinn mal zu beenden.

Der zweite stille Fresser, doch mit kleinerem Hunger, ist die Blockgröße auf dem Stick. Jedes Filesystem, egal ob aus der Linux- oder Windows-Ecke, speichert Dateien in gleich großen Blöcken, meist 4 KBytes. Auch eine 1 Byte große Datei beißt vom einem Filesystem geschlagene 4096 Bytes ab (Abbildung 4).

Bei den heute angebotenen Sticks spielen diese Verluste allerdings nur eine Rolle, falls man Hundertausende kleiner Dateien auf dem Stick speichert. Dennoch berücksichtigt das Skript diese Rundung mit der ab Zeile 76 definierten Funktion »blocksize_round()« , die das Füllprogramm in den Zeilen 26 und 50 aufruft, um den wahren Byte-Bedarf einer kopierten Datei auf dem Stick zu ermitteln.

Abbildung 3: Der Bucket »3« füllt einen 4-GByte-USB-Stick bis zum Rand.

Abbildung 4: Eine Datei mit 1 Byte belegt einen 4-KByte-Block auf dem Stick.

Rucksäcke füllen

Listing 2 befüllt also bei jedem Lauf zunächst die virtuelle Rucksackkette in Algorithm::Bucketizer mit den im Zielverzeichnis »~/sticks« bereits vorhandenen virtuellen Einträgen. Dann wirft es den Füllalgorithmus für die zu sichernden PDF-Dateien in »~/books« an.

Ohne weitere Optionen nutzt das CPAN-Modul den Modus »simple« , der den letzten aktiven Rucksack zu füllen versucht und, falls der voll ist, zum nächsten wechselt. Das einfache Verfahren geht niemals zu vorherigen Behältern zurück, selbst wenn deren Speicher noch Platz für die nächste Datei besitzt. Es bietet den Vorteil, dass der Inhalt bereits befüllter USB-Sticks sich niemals ändert und der User nur jeweils die neuesten Behälter tatsächlich mit »rsync« synchronisieren muss.

Konfiguration in Yaml

Zeile 19 liest die Yaml-Datei nach Listing 1 ein. Jeder Eintrag dort weist den Schlüsseln »name« und »size« Werte zu. Entdeckt Zeile 38 des Listings 2 eine Dateigröße mit angehängtem »g« , multipliziert es sie mit dem 1-GByte-Wert aus Zeile 16. Die Methode »add_bucket()« von Algorithm::Bucketizer legt daraufhin in Zeile 41 einen Behälter an.

Die zu sichernden PDF-Dateien legt die For-Schleife ab Zeile 23 im Hash »%files« zusammen mit ihrer gerundeten Bytegröße ab. Der »delete« -Befehl in Zeile 55 entfernt aus dem Hash später in den Zieldirectories gefundene Links.

Zuvor hat die Methode »prefill_bucket()« des Rucksack füllenden CPAN-Moduls die Datei jenem Behälter zugewiesen, dessen Nummer dem Zielordner entspricht, in dem sie gefunden wurde. Ein Behälter der Rucksackkette liefert diese Nummer mittels »idx()« wie in Zeile 53. Nach dem Befüllen der Kette mit bereits gesicherten Dateien legt die Methode »add_item()« in Zeile 63 noch nicht bearbeitete Dateien im nächsten freien Rucksack ab.

Hat der User eine Reihe USB-Sticks aus seinen Schubladen und Grabbelkisten zusammengesucht, trägt er ihre Größen in die Yaml-Datei ein. Er weist jedem Stick einen numerischen Namen zu, mit dem er den Stick per Etikettendrucker beschriftet. Die Pfade der Backupverzeichnisse in den Zeilen 13 und 14 passt er noch an die eigenen Gegebenheiten an.

Nach dem Skriptlauf frischt der Anwender mit Rsync nur jene USB-Sticks aus den Rucksack-Verzeichnissen auf, deren Inhalt sich laut Skriptmeldung verändert hat, und bewahrt sie an einem sicheren Ort auf. Tritt jetzt die Katastrophe ein, sind die vermeintlich wertlosen Sticks Gold wert.