Speichermedien wie USB-Sticks oder SD-Karten mit wenig Speicherplatz verlieren schnell an Wert. Verteilt ein Skript die Dateien aber auf mehrere kleinere Einheiten, taugen sie als letzte Ruhestätte für Backups.
Speichermedien wie USB-Sticks und SD-Karten unterliegen dem Mooreschen Gesetz, nach dem sich ihre Speicherkapazität jedes Jahr etwa verdoppelt. Ein Stick mit 64GB kostet heutzutage nur noch $40, und ein noch vor Jahren führender 8GB-Stick hat fast allen Wert verloren und fristet oft ein bedauernswertes Schubladendasein. Kombiniert man allerdings mehrere Einzelbausteine, erreicht ihre gebündelte Kapazität schnell akzeptable Größen. Außerdem steigen die Preise überproportional, sobald man das Ende der Fahnenstange erreicht. Kostet ein 128GB-Stick noch etwa $80, schlägt die doppelte Speicherkapazität (256GB) noch mit dem vierfachen Preis zu Buche.
Um mehrere kleine Speicherbausteine zu einem größeren Verbund zusammen zu schließen, böte sich eine Softwarelösung wie der Linux Volume Manager (LVM) an, der nackte Hardware-Partitionen elegant und zuverlässig zu Software-Partitionen zusammenschweißt, die sich auf 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. |
Allerdings möchte wohl kaum jemand jedes Mal fünf USB-Sticks gleichzeitig einstöpseln, um eine LVM-Partition zu mounten, die Zugriff auf ein Backup bietet. Vielmehr bietet es sich an, einzelne Dateien auf Applikationsebene auf verschiedene Sticks zu verteilen. Das Verfahren lässt sich in der Algoritmen-Literatur als Rucksackproblem ("Knapsack Problem") nachlesen. In dieser Optimierungsaufgabe der Kombinatorik gilt es, verschieden schwere Gegenstände in Rucksäcke zu verpacken, von denen keiner sein vorgegebenens Höchstgewicht überschreiten darf.
Dem Gewicht eines Gegenstandes entspricht beim Backup die Größe einer Datei in Bytes. Der Rucksack ist der USB-Stick, der eine Reihe dieser Dateien speichert. Da es sich um ein Problem der Klasse "NP-Vollständig" handelt, 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 kann die "Behälter" einfach der Reihe nach befüllen, bis sie voll sind, und dann jeweils zum nächsten freien übergehen.
 |
| Abbildung 2: Der Rucksackalgorithmus füllt einen Behälter bis zum Rand und schreitet dann zum nächsten. |
Wie groß die einzelnen Behälter sind, liegt an der Größe der verwendeten USB-Sticks, die oft unterschiedliche Specherkapazitäten aufweisen. Die YAML-Datei ein Listing 1 gibt deshalb vor, wie die Sticks heißen und wieviele Bytes sie fassen können. Im Beispiel numeriert die Datei die Sticks einfach durch, und mit einem Etikettendrucker lassen sich die Sticks im Verbund so ohne großen Aufwand 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 befüllt es den Behälter, indem es symbolische Links im Zielverzeichnis anlegt, die auf die entsprechenden Dateien im Originalverzeichnis zeigen und zählt mit, wie viele Bytes nun symbolisch im Rucksack liegen, obwohl der Symlink natürlich kaum Speicherplatz verbraucht. Ist der Rucksack voll, legt es gemäß der Konfiguration in Listing 1 einen neuen an und setzt das Verfahren fort, bis es keine Dateien mehr findet oder keine Behälter mehr definiert sind. Die Symlinks verbleiben auch nach dem Skriptlauf in den Zielverzeichnissen und geben Auskunft darüber, welche Originaldateien schon gesichert wurden.
Bei einem erneuten Backup-Lauf stellt das Skript fest, welcher Rucksack schon mit welchen Dateien befüllt wurden und sucht nur für noch nicht gesicherte Dateien im Originalverzeichnis aufnahmefähige Behälter. Das hat den Vorteil, dass der User bereits befüllte USB-Speichersticks nicht bei jedem Backuplauf neu einstecken und auffrischen muss, da die Daten darauf sich nicht mehr ändern. Der Einfachheit halber geht der Algorithmus davon aus, dass sich Dateien nicht ändern, sondern nur neue Dateien ins Originalverzeichnis hinzukommen, wie das etwas bei einer eBook-Bibliothek mit PDF-Dateien oder einer Musiksammlung der Fall ist.
Die Verzeichnisse mit den Symlinks kopiert dann ein rsync-Kommando mit
der Option --copy-links auf die zugewiesenen Sticks. Abbildung 2 zeigt,
wie alle Symlinks aus dem Rucksack mit dem Namen "3" auf Dateien verweisen,
die insgesamt 4GB auf die Waage bringen. Der rsync-Befehl kopiert die
Dateiinhalte und ein anschließend abgesetzes df-Kommando auf den unter
/dev/sdb1 eingestöpselten und unter /media/8CB1-7B24 gemounteten Stick
zeigt dass letzterer nun bis zur Unterkante Oberlippe befüllt ist.
 |
| Abbildung 3: Der Bucket Nummer 3 füllt einen 4GB-USB-Stick bis zum Rand. |
Das Skript in Listing 2 nutzt 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. Wieviele Dateien ein Zielverzeichnis aber tatsächlich aufnehmen kann, ist nicht ganz so trivial wie die jeweiligen Dateigrößen von der aufgedruckten Speicherkapazität des Sticks abzuziehen. Zwei stille Fresser zwacken zusätzliche Bytes ab.
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 }
Dass Zeile 16 ein Gigabyte mit 1_000_000_000 angibt, liegt daran, dass Festplatten- und USB-Stick-Hersteller seit Beginn der Neuzeit falsche Zahlen publizieren. Kein einziger 4GB-Stick auf dem Markt hat 4*1024**3 also 4.294.967.312 Bytes, sondern nur 4.000.000.000. Da der Rechner die Kapazität eines USB-Sticks in echten Gigabytes anzeigt, stehen dann dort plötzlich nur 3.8GB obwohl der User sein hartverdientes Geld in 4GB investiert hat. Lange Gesichter und heißgelaufene Hotlines der Stickhersteller sind seit jeher die Folge, aber niemand hat anscheindend die Chuzpe, diesen Irrsinn zu ändern.
 |
| Abbildung 4: Eine Datei mit einem einzigen Byte belegt einen 4K-Block auf dem USB-Speicherstick. |
Weitere stille Fresser, wenngleich auch mit geringerem Hunger sind
die Blockgrößen des Dateisystems auf dem Stick. Jedes Dateisystem, egal
ob Linux- oder Windows-basiert, speichert Dateien in festen Blockgrößen,
meist etwa 4KBytes große Bereiche. Auch eine Datei, die nur ein Byte
enthält, frißt auf so einem Filesystem geschlagene 4096 Bytes. Bei den
heutzutage angebotenen Stickkapazitäten im Gigabytebereich 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
Byteverbrauch einer kopierten Datei auf dem Stick zu ermitteln.
Listing 2 befüllt also bei jedem Lauf zunächst die virtuelle Rucksackkette
in Algorithm::Bucketizer mit den bereits im Zielverzeichnis "~/sticks"
vorhandenen virtuellen Einträgen. Anschließend wirft es den Füllalgorithmus
an für die in ~/books liegenden PDF-Dateien an, die es zu sichern gilt.
Ohne weitere Optionen nutzt das CPAN-Modul den Modus "simple", der
einfach versucht, den letzten aktiven Rucksack zu befüllen, und falls dieser
schon voll ist, zum nächsten weitergeht. Bei diesem einfachen Verfahren
geht es niemals zu vorherigen Behältern zurück, in deren verbleibenden
Speicherplatz eine Datei vielleicht auch noch passen würde. Dies hat 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.
Zeile 19 liest die YAML-Datei nach Abbildung Listing 1 ein. Jeder Eintrag
weist dort den Schlüsseln name und size Werte zu. Entdeckt Zeile
38 in Listing 2 eine numerische Dateigröße, der der Buchstabe "g" anhängt,
multipliziert es den Eintrag mit dem in Zeile 16 Wert für ein Gigabyte.
Die Methode add_bucket() der Klasse Algorithm::Bucketizer legt
daraufhin in Zeile 41 einen neuen 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.
Alle später in den Zielverzeichnissen gefundenen Links entfernt der
delete-Befehl in Zeile 55 dann wieder aus dem Hash. Zuvor hat
die Methode prefill_bucket() des rucksackfüllenenden CPAN-Moduls
die Datei dem Behälter zugewiesen, dessen Nummer dem Zielordner entspricht,
in dem sie gefunden wurde. Ein Behälter der Rucksackkette liefert diese
Nummer mittels der 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 alter USB-Sticks aus verschiedensten Schubladen
und Grabbelkisten zusammengesucht, trägt er ihre Größen in die YAML-Datei
ein und weist jedem Stick eine numerischen Namen zu, mit der er
den Stick mittels eines Etikettendruckers beschriftet. Die Pfade der
Backup-Verzeichnisse in den Zeilen 13 und 14 sind an die lokalen
Gegebenheiten anzupassen. Nach dem Skriptlauf frischt der User nur
diejenigen USB-Sticks mittels rsync aus den Rucksackverzeichnissen auf,
deren Inhalt sich gemäß der Ausgabe des Skripts verändert hat und
bewahrt sie an einem sicheren Ort auf. Tritt der Kathastrophenfall ein,
leisten die ehemals wertlosen Sticks gute Dienste.
Listings zu diesem Artikel: ftp://www.linux-magazin.de/pub/listings/magazin/2013/03/Perl
"Rucksackproblem", http://de.wikipedia.org/wiki/Rucksackproblem
"NP-Vollständigkeit", http://de.wikipedia.org/wiki/NP-Vollst%C3%A4ndigkeit
 |
Michael Schilliarbeitet als Software-Engineer bei Yahoo in Sunnyvale, Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen der Skriptsprache Perl. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen. |