Vorsprung durch Vorarbeit (Linux-Magazin, Juli 2018)

Was waren das noch für Zeiten, als man einfach eine Codezeile oder einen ungewöhnlichen Variablennamen in Googles "Codesearch"-Seite (Abbildung 1) eingeben konnte, und die Datenkrake ruckzuck ausspie, in welchen Open-Source-Repositories letztere auftauchten? Leider hat Google den Service vor etlichen Jahren wohl mangels Profit eingestellt (offizielle Begründung: "Focus on higher impact products"), aber noch ist nicht alles verloren, denn das Github-Projekt "Codesearch" [2] mit seinem in Go gebauten Indexer erlaubt es zumindest, lokal vorliegende Repositories zu durchstöbern, zu indizieren und anschließend blitzschnell nach Codestücken zu durchsuchen. An anderer Stelle erklärt Autor Russ Cox, damals Praktikant bei Google, wie die Suche funktionert ([3]).

Wie wäre es, nach einem ähnlichen Verfahren einen Index der Dateien unterhalb eines Einstiegsverzeichnisses anzulegen, um daraufhin blitzschnell ausgeführte Abfragen wie "was sind die zehn größten Platzverschwender", "welche Dateien wurden kürzlich modifiziert" oder "welche Dateinamen passen auf folgendes Muster" zuzulassen?

Unix-Dateisysteme speichern diese Metadaten in den Inodes, die aber in ausgeflachten Strukturen auf der Platte liegen, die Datenbank-ähnliche Abfragen nur im Schneckentempo zulassen. Der Befehl stat auf eine Datei enthüllt, dass das Dateisystem die Dateigröße speichert, sowie diverse Zeitstempel wie den Zeitpunkt der letzten Modifizierung (Abbildung 2). Neuere Dateisystem wie ZFS oder btrfs gehen zwar in der Organisation der darin enthaltenen Dateien in Richtung Datenbank, aber eben nicht weit genug, damit es aus dem Userland möglich wäre, Queries mit Schmackes darauf abzusetzen.

Abbildung 1: So sah anno 2007 die Seite von "Google Code Search" aus (Quelle: archive.org)

Schmackes statt Kaffeepause

Wer zum Beispiel alle Dateien über 100M auf der Platte aufstöbern möchte, kann dies mit einem find-Aufruf wie

    $ find / -type f -size +100M

tun, kann aber auf einer traditionellen Festplatte gleich in die Kaffeepause gehen und sich selbst auf einer schnellen SSD auf lange Suchzeiten gefasst machen, einfach aus dem Grund, weil die Daten sehr abfrageunfreundlich auf den Sektoren der Platte verstreut vorliegen.

Abbildung 2: Mit stat ermittelte Inode-Metadaten einer Datei zum Aufbau eines Indexes zur sp├Ąteren Abfrage.

Um dies abzukürzen, soll ein Indexer in regelmäßigen Abständen, zum Beispiel während ruhiger Phasen in den frühen Morgenstunden die Metadaten einholen und in einer SQLite-Datenbank ablegen, damit ein Abfragetool daruf blitzschnell herumorgeln kann. Die Utiltiy updatedb auf Linux tut ähnliches, damit der User mit locate blitzschnell nach Dateinamen suchen kann.

Und weil der Programmiersnapshot niemals vor neuen Herausforderungen zurückschreckt (und er während eines Hawaiiurlaubes mit viel Zeit und guter Laune entstanden ist), erfolgt die Implementierung in der Programmiersprache Go, ganz genau wie das Codesearch-Projekt. Als Index kommt eine SQLite-Datenbank zum Einsatz, die zwar nur eine Datei belegt, aber optimierte Queries auf selbst mittelgroße Datenmengen zulässt.

Dazu legt Listing 1 eine SQLite-Datenbank namens files.db an, die zu jeder gefundenen Datei im Verzeichnisbaum einen Tabelleneintrag mit den Feldern path (Vollständiger Dateipfad), size (Dateigröße) und modified (Zeitstempel der letzten Modifizierung) einfügt.

Listing 1: create.go

    01 package main
    02 
    03 import (
    04   "database/sql"
    05   _ "github.com/mattn/go-sqlite3"
    06   "os"
    07 )
    08 
    09 func main() {
    10 
    11   file := ".findex.db"
    12   os.Remove(file)
    13 
    14   db, err := sql.Open("sqlite3", file)
    15   if err != nil {
    16     panic(err)
    17   }
    18 
    19   _, err = db.Exec("CREATE TABLE files " + 
    20       "(path text, modified int, size int)")
    21   if err != nil {
    22     panic(err)
    23   }
    24 }

Um den notwendigen SQLite-Treiber zu installieren, holt das Bordmittel go get den Source-Code von Github ab, löst etwaige Abhängigkeiten auf und kompiliert und installiert das Ergebnis lokal:

    $ go get github.com/mattn/go-sqlite3

Anschließend dürfen Skripts wie Listing 1 den Treiber in ihrer import-Sektion unter dem vollen Namen laden, der Unterstrich in Zeile 5 dient dazu, den ultrastrengen Go-Compiler vor der Explosion zu bewahren, weil ein Paket importiert wurde, das offenbar nirgendwo im Code referenziert wird. Go duldet keine überflüssigen Abhängigkeiten, im vorliegenden Fall ist der Treiber jedoch notwendig.

Der Anfang jedes Go-Programms steht in einem package main in einer Funktion main, so auch in Listing 1 ab Zeile 8. Dort öffnet die Methode Open() über Gos Standard-Datenbank-Interface database/sql (und unter der Haube mit dem SQLite-Treiber) eine Verbindung zur Dateidatenbank files.db, legt letztere also erstmals an. Falls sie schon existiert oder ein anderer Fehler auftritt, enthält der Rückgabewert err einen Wert ungleich nil und Zeile 11 schlägt mit panic() Alarm und bricht den Programmfluss ruckartig ab.

Old-School Fehlerprüfung

Der nachfolgend in Zeile 14 abgesetzte SQL-Befehl create legt eine neue Datenbanktabelle an, und auch hier prüft Zeile 16, ob ein Fehler zurück kam und bricht notfalls mit einer Meldung ab. Go glaubt noch an die alte Schule der individuellen Prüfung von Rückgabewerten, statt dass es dem Programmierer erlaubt, Exceptions zu werfen, hochblubbern zu lassen und irgendwo weiter oben zu verarbeiten. Noch ein Wort zu den verschiedenen Zuweisungen in Zeile 9 und Zeile 14, die erst mit ":=" und dann mit "=" erfolgt. Das erste ist Gos Zuweisung mit Deklaration, ist eine Variable bislang noch nicht deklariert, erledigt die Kurzform mit ":=" dies.

Wehe, wehe

Aber wehe, wenn in der Deklarations-Liste der Variablen nur bereits deklarierte Variablen stehen, dann weigert sich Go stur, den Code überhaupt zu kompilieren. In diesem Fall muss die Zuweisung wie in Zeile 14 mit "=" erfolgen. Ebenfalls ein Go-Unikum sind Funktionen mit mehreren Rückgabewerten. Oft ist in der Liste der Werte eine Error-Variable enthalten, und ist sie auf nil gesetzt, ging alles gut. Interessiert ein zurückkommender Wert nicht, wie zum Beispiel der erste Rückgabewert von db.Exec() in Zeile 16, schreibt der Go-Apostel einen Unterstrich an die Stelle einer überflüssigen Variablen. Von einer Funktion, die zwei Rückgabewerte liefert nur einen abzuholen hätte einen Compile-Fehler zur Folge.

Abbildung 3: Nach dem Lauf des Indexers liegen mehr als eine Million Dateieintr├Ąge in der SQLite-Datenbank.

Compiliert wird der Code mittels

    $ go build create.go

und einen Sekundenbruchteil später steht ein Executable create zur Verfügung, das alle Abhängigkeiten und Libraries bereits enthält, also ohne weiteres auf einen weiteren Rechner mit dem gleichen Betriebssystem kopiert werden kann, ohne dass ein Rattenschwanz von Abhängigkeiten folgen müsste. Das entstehende Binary ist mit etwa 4.5MB allerdings auch nicht gerade ein Leichtgewicht.

Listing 2: index.go

    01 package main
    02 
    03 import (
    04   "database/sql"
    05   _ "github.com/mattn/go-sqlite3"
    06   "os"
    07   "path/filepath"
    08 )
    09 
    10 type Walker struct {
    11   Db *sql.DB
    12 }
    13 
    14 func main() {
    15   if len(os.Args) != 2 {
    16     panic("usage: " + os.Args[0] +
    17           " start_dir")
    18   }
    19   root := os.Args[1]
    20 
    21   db, err :=
    22       sql.Open("sqlite3", ".findex.db")
    23 
    24   w := &Walker{
    25     Db: db,
    26   }
    27 
    28   err = filepath.Walk(root, w.Visit)
    29   checkErr(err)
    30 
    31   db.Close()
    32 }
    33 
    34 func (w *Walker) Visit(path string,
    35           f os.FileInfo, err error) error {
    36   stmt, err := w.Db.Prepare(
    37       "INSERT INTO files VALUES(?,?,?)")
    38   checkErr(err)
    39 
    40   _, err = stmt.Exec(
    41       path, f.ModTime().Unix(), f.Size())
    42   checkErr(err)
    43 
    44   return nil
    45 }
    46 
    47 func checkErr(err error) {
    48   if err != nil {
    49     panic(err)
    50   }
    51 }

Closure als Brücke

Listing 2 zeigt den Indexer, der sich mittels der Walk()-Methode des Standardpakets path/filepath durch eine Dateihierarchie wühlt, beginnend mit dem Startverzeichnis, das der User auf der Kommandozeile angegeben hat. Dem Progarmm übergebene Argumente liegen im Array os.Args, und zwar wie in C mit dem Programmnamen als erstem Element und allen Aufrufparametern in den folgenden. Den Dateibaum zu durchstöbern wäre nicht weiter schwierig, doch Go kommuniziert in Zeile 28 mit diesem Wanderer über eine Callback-Funktion Visit(). Das Problem ist hier, dass kein Datenbank-Handle innerhalb des Scopes dieses Callbacks ab Zeile 34 existiert, auf das diese zugreifen und die notwendigen Änderungen an der Datenbank vornehmen könnte. Die Lösung des Dilemmas liegt in einer Closure zur Funktion Visit(). Dazu definiert Visit() in Zeile 34 zwischen dem Schlüsselwort func und dem Funktionsnamen einen sogenannten Receiver und weist Go somit an, die Datenstruktur Walker (Zeile 10), die ein Datenbankhandle enthählt, mit der Funktion Visit() zu verbandeln. Auf diese Weise kann Visit() über die Variable w auf das Db-Handle zugreifen und damit neue Records in die Datenbank einfügen.

Die eigentliche Arbeit beim Kommunizieren mit der Datenbank übernimmt dabei die Methode Prepare(), die einen SQL-Befehl vorbereitet und ein Statement-Handle zurückgibt, worauf Zeile 40 auf letzteres die Methode Exec abfeuert und dem SQL-Kommando die Parameter für den Pfad der Datei, den Zeitstempel ihrer letzten Modifizierung und ihre Größe in Bytes übergibt.

Damit das Programm nicht nach jedem Funktionsaufruf prüfen muss, ob die Fehlervariable err ja den Wert nil hat und demnach alles in trockenen Tüchern ist, definiert Zeile 47 eine Funktion checkErr, die dies erledigt, und das Programm mit panic abbricht, falls etwas unvorhergesehenes passiert ist.

Wer hat an der Uhr gedreht?

Nachdem der Indexer seine Arbeit beendet hatte, lagen auf meinem Rechner, wie Abbildung 2 zeigt, mehr als eine Million Einträge in der Datebanktabelle files. Grund für die recht hohe Anzahl von Dateien waren wohl zahlreiche geklonte Git-Repositories, sowie mehr als 20 Jahre Programmier-Artikel der Snapshot-Reihe. Mit diesen Daten in der SQLite-Datenbank files.db kann nun ein Client schnell Queries abfeuern und zum Beispiel feststellen, welche Dateien unter meinem Home-Verzeichnis sich kürzlich verändert haben.

Listing 3: latest.go

    01 package main
    02 
    03 import (
    04   "database/sql"
    05   "fmt"
    06   _ "github.com/mattn/go-sqlite3"
    07 )
    08 
    09 func main() {
    10   db, err :=
    11     sql.Open("sqlite3", ".findex.db")
    12   checkErr(err)
    13 
    14   rows, err := db.Query("SELECT path, " +
    15     "modified FROM files " +
    16     "ORDER BY modified DESC LIMIT 10")
    17   checkErr(err)
    18 
    19   var path string
    20   var mtime string
    21 
    22   for rows.Next() {
    23     err = rows.Scan(&path, &mtime)
    24     checkErr(err)
    25     fmt.Printf("%s %s\n", path, mtime)
    26   }
    27 }
    28 
    29 func checkErr(err error) {
    30   if err != nil {
    31     panic(err)
    32   }
    33 }

Hierzu verbindet sich Listing 3 mit der SQLite-Datenbank und setzt einen Select-Befehl ab, der alle Zeilen der Tabelle selektiert, absteigend nach dem Zeitstempel in der Spalte modified sortiert und die ersten zehn Treffer ausgibt.

Die Methode rows.Next() arbeitet sich dabei Schrittweise durch die Treffer, rows.Scan() holt die ersten zwei Spaltenwerte ein und weist sie den als Pointer übergebenen Variablen path und mtime zu, beide wurden vorher als String deklariert. Go unterstützt Pointer, doch nimmt es dem User das Memory-Management ab und stürzt nicht wie C ins Bodenlose wenn eine Adresse wegen eines Bugs mal nicht stimmt, sondern bricht mit einer hilfreichen Fehlermeldung ab.

Listing 4: max-size.go

    01 package main
    02 
    03 import (
    04   "database/sql"
    05   "fmt"
    06   "flag"
    07   "os"
    08   "strconv"
    09   _ "github.com/mattn/go-sqlite3"
    10 )
    11 
    12 func main() {
    13   db, err :=
    14     sql.Open("sqlite3", ".findex.db")
    15   checkErr(err)
    16 
    17   max_files := flag.Int("max-files", 30,
    18     "max number of files")
    19 
    20   flag.Parse()
    21   if len(flag.Args()) != 0 {
    22     panic("usage: " + os.Args[0])
    23   }
    24 
    25   rows, err := db.Query("SELECT path," +
    26     "size FROM files WHERE path NOT like '%.git%'" +
    27     "ORDER BY size DESC LIMIT " +
    28     strconv.Itoa(*max_files))
    29   checkErr(err)
    30 
    31   var path string
    32   var size string
    33 
    34   for rows.Next() {
    35     err = rows.Scan(&path, &size)
    36     checkErr(err)
    37     fmt.Printf("%s %s\n", path, size)
    38   }
    39 }
    40 
    41 func checkErr(err error) {
    42   if err != nil {
    43     panic(err)
    44   }
    45 }

Mehr Luxus, mehr Zeilen

Welche Dateien verbrauchen den meisten Speicherplatz? Listing 4 findet das schnell heraus, indem es mit dem Select-Query ab Zeile 25 alle Einträge nach der Spalte size absteigend sortiert ("ORDER BY size DESC") und die Ausgabe mittels LIMIT auf eine Maximalzahl von Treffern beschränkt. Diese Zahl legt der User mit dem Parameter -max-files auf der Kommandozeile fest, und Go bietet mit dem Paket flag eine komfortable Schnittstelle zum Parsen der Parameter eines Kommandos. Zunächst verlangt es die Deklaration der Variablen, die den Parameter entgegennimmt (max_files in Zeile 17), und der Aufruf der Methode flag.Int() legt dabei fest, dass als Wert nur ein Integer in Frage kommt. Anschließend analysiert flag.Parse() (Zeile 20) die vorliegenden Kommandozeilenparameter, und weist, falls der User -max-files gesetzt hat, diesen Wert einer Variablen zu, auf die der Pointer max_files zeigt. Die Funktion Itoa() aus dem Paket strconv wandelt den Integer hinter dem dereferenzierten Pointer *max_files wieder in einen String um, und Zeile 28 fügt ihn per LIMIT-Klausel in den SQL-Befehl ein. Dieses Ringelpietz mit verschiedenen Typumwandlungen hat aber wenigstens den Vorteil, dass so im Query tatsächlich ein Integer ankommt und nicht etwa eine Zeichenfolge zur SQL-Injektion.

Dass ein Datenbank-Client in einer Skriptsprache wie Python doch leichter von der Hand geht, zeigt Listing 5. Es kramt alle Datenbankeinträge hervor, deren Dateipfade einem vorgegebenen Muster entsprechen. Es nimmt auf der Kommandozeile einen regulären Ausdruck entgegen, pflanzt ihn in einen SQL-Query ein und gibt die Treffer aus.

Listing 5: like.py

    01 #!/usr/bin/env python3
    02 import sys
    03 import sqlite3
    04 
    05 try:
    06   _, pattern = sys.argv
    07 except:
    08   raise SystemExit(
    09      "usage: " + sys.argv[0] + " pattern")
    10 
    11 conn = sqlite3.connect('files.db')
    12 c = conn.cursor()
    13 like = "%" + pattern + "%"
    14 for row in c.execute('SELECT path,size FROM files WHERE path LIKE ?', [like]):
    15   print(row)

Gos Typsicherheit und die Tatsache, dass es nicht innerhalb eines Bytecode-Interpreters läuft sondern als compiliertes Binary mit etwas eleganterem Memory-Management als ein C oder C++-Programm hat seinen Preis: Es erfordert etwas detailliertere Instruktionen und zieht den Programmcode in die Länge. Go-Programme laufen schneller als Python-Skripts, aber wie so oft liegt der Flaschenhals auch hier nicht beim Abarbeiten der Instruktionen, sondern beim Kommunizieren mit externen Systemen: Im vorliegenden Fall verbraten die Aufrufe der SQLite-Datenbank den Hauptteil der Rechenzeit und ob das Hauptprogramm nun 10% oder gar 100% schneller läuft, ist komplett irrelevant. Dennoch ist Gos kompaktes Binary-Format mit eingebetteten Libraries und ohne "Dependency Hell" ein dicker Vorteil und zweifellos ein Grund für seine Popularität gerade in der Systemprogrammierung.

Infos

[1]

Listings zu diesem Artikel: http://www.linux-magazin.de/static/listings/magazin/2018/07/snapshot/

[2]

Google Code Search, https://github.com/google/codesearch

[3]

"Regular Expression Matching with a Trigram Index or How Google Code Search Worked", Russ Cox, 2012, https://swtch.com/~rsc/regexp/regexp4.html

Michael Schilli

arbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen.

POD ERRORS

Hey! The above document had some coding errors, which are explained below:

Around line 5:

Unknown directive: =desc