Fragen? Antworten! Siehe auch: Alternativlos
Bei Logdaten ist das für den Fuß, denn der Index würde einem sagen: Dieses Wort kommt in allen Logs des Webservers vor. Ja super. Da bin ich dann so weit wie vorher und muss die alle der Reihe nach durchsuchen.
Oder man könnte "Dokument" umdeuten, und zum Beispiel sagen: Alle 15 Minuten Weblog sind ein Dokument.
Aber man will ja auch andere Arten von Anfragen stellen können bei Logdaten. Man will ja sowas fragen können wie: Welche IPs haben in den letzten Stunden mehr als doppelt so häufig wie der Median zugegriffen?
Oder, bei Maillogs: Welche IP, die wir sonst selten sehen, versucht das Absetzen von mehr als 2 Mails in einer Minute.
Für diese Anfragen von Logs reicht ein Volltextindex nicht.
Und eigentlich wil man diese Art von Anfragen auch nicht ad hoc auf den Corpus anwenden, sondern man will sie auf einen vorbeifließenden Stream ansetzen, und dann einen Trigger auslösen können.
Nun kann man da auf mehrere Arten rangehen. Ich überlege gerade, ob man das nicht weniger schlimm machen kann, wenn man die Daten später durchsuchen will. Also man läuft immer noch komplett durch (ich vermute, dass das für einige ad-hoc-Anfragen gar nicht anders gehen wird), aber man reduziert den Aufwand, den man treiben muss. Ich dachte mir das so, dass man aus den rohen Logdaten die Felder extrahiert, d.h. die Logdaten in einen pro Logzeilentyp konstanten Format-String (wie bei printf/strftime) und die Datenfelder zerlegt. Und dann speichert man den Stream binär ab, die Format-Strings jeweils nur als Referenz auf ein Dictionary, und die Inhalte der Felder aus den Daten herausgeparsed. Dann muss man statt 127.0.0.1 nur vier Bytes abspeichern. Pro Logzeile legt man dann eine Referenz auf den Format-String ab (ich nenne das mal Template), dann das Offset zur nächsten Zeile, und dann binär kodiert die ganzen Werte. Die Idee wäre, dass man dann beim Suchen weiß, an welchem Template man interessiert ist, und die anderen schnell überspringen kann.
Konzeptionell versuche ich also ein Komprimierungsverfahren zu basteln, das ein Matching ohne vollständige Rekonstruktion der Quelldaten erlaubt. Oder zumindest ein fail fast beim Matching.
Was ich an der Stelle unbedingt vermeiden möchte sind irgendwelche Sammlungen von regulären Ausdrücken. Das Parsing muss automatisiert funktionieren.
Der erste Schritt dabei wäre, dass man erstmal typische Felder erkennt. Ich habe da mal eine Heuristik gehackt, die erkennt schonmal IP-Adressen, Timestamps in einigen üblichen Formaten, Hostnamen, Dateinamen, Pfadnamen, URLs, Email-Adressen. Das Problem ist halt, dass man Hostnamen und Dateinamen nicht wirklich erkennen und auseinanderhalten kann. Möglicherweise braucht es diese Aufteilung ja auch gar nicht und ich könnte auch einfach sagen: Das ist ein String-Feld.
Nehmen wir mal diese Logzeile hier:
Jul 17 12:34:56 ptrace sshd[2342]: Accepted publickey for usereins from 1.2.3.4 port 59932 ssh2: ED25519 00:11:22:33:44:55:66:77:88:99:aa:bb:cc:dd:ee:ffDaraus macht mein Tool sowas wie
%t %h %P[%i]: Accepted publickey for usereins from %4 port %i ssh2: ED25519 00:11:22:33:44:55:66:77:88:99:aa:bb:cc:dd:ee:ffDen Hex-String könnte mein Tool auch erkennen, tut es aber im Moment noch nicht. Aber das größere Problem ist, wenn ich zwei solcher Zeilen habe, eine mit usereins und eine mit userzwei, wie führe ich die Templates zusammen und mache aus usereins/userzwei ein %s?
Klassische Verfahren für sowas sind Edit-Distance/Levenshtein oder sowas, aber das muss doch auch irgendwie geschickter gehen. Und ich bräuchte das auf Wörtern, nicht auf Zeichen. Bonusproblem: Mit Feldern klarkommen, die Leerzeichen beinhalten dürfen.
Daran knabbere ich gerade herum.
Spannenderweise findet man für dieses Problem auf Anhieb wenig Kram, weil alles mit Template im Namen in die andere Richtung geht, aus Rohdaten und einem Template den String zu rekonstruieren. Was ich ja trivial genug finde, dass mir nicht klar ist, wieso sich so viele Leute damit beschäftigen. Aber gut.
Vielleicht fehlt mir auch einfach der richtige Suchbegriff?
Update: A-Ha! Der erste sachdienliche Hinweis geht ein. Ein verwandtes Problem ist das Longest common subsequence problem.
Update: Von Microsoft Research gibt es ein Paper, das genau die Fragestellung zu behandeln scheint. Die arbeiten da mit endlichen Automaten.
Update: Und hier ist noch ein Paper von einem Haufen MIT-Leuten. Das scheint mir aber inhaltlich nicht weiterzuhelfen.
Update: Ein verwandtes Problem aus der Bioinformatik ist das Sequenzalignment.