Wir haben eine beachtliche Anzahl an Dateien zwecks Analyse bekommen; sie bestanden aus verschiedenen Formaten und hatten unterschiedliche Inhalte. Der Auftrag war relativ simpel: Suchen und finden aller Email-Adressen, wobei der dazugehörige Datensatz extrahiert werden können musste.

Als erstes haben wir versucht die Daten in MariaDB und Elasticsearch zu importieren. Doch beide Lösungen erwiesen sich als zu langsam. MariaDB hatte zwar die bessere und flexiblere Suchperformance für erste Anfragen. Es konnte damit jedoch keine Skalierung erreicht werden. Elastic hat gut skaliert, setzt jedoch zusätzlichen Code und zusätzliche Hardware voraus. Bei der ersten Umsetzung sollte es sich um einen Proof-of-Concept handeln, weshalb keine zusätzlichen Aufwände in Bezug auf Hardware auf sich genommen werden wollte.

Herausforderungen

• Dateigrösse: Wir haben eine Vielzahl an Dateien verschiedener Grösse erhalten. Diese reichten von 50 MB bis zu 89 GB. ⇒ Um die Zugriffszeit linear zu halten, haben wir die Dateien in Chunks von 10k Zeilen gesplittet.
• Dateierweiterungen: Einige Dateien hatten keine klaren Zeilenenden ⇒ Wir haben dies mittels sed korrigiert.
• JSON-Dateien: Einige Exports bestanden aus einer grossen Zeile; andere kamen mit mehreren Zeilen pro Record daher. ⇒ In beiden Fällen haben wir die JSON-Dateien so umgewandelt, dass ein Record aus einer Zeile bestand. Hierzu haben wir das Tool jq verwendet.
• Extrahieren der Email-Adresse: Das Extrahieren von Email-Adressen klingt auf den ersten Blick trivial, ist es aber nicht: Der standardisierte reguläre Ausdruck ist sehr komplex und zeitintensiv ⇒ Wir haben mehrere Tests durchgeführt, um den idealen Kompromiss zwischen Komplexität und Genauigkeit ermitteln zu können. Für weitere Details zu diesem Aspekt siehe How to Find or Validate an Email Address

Lösung

Wir haben ein ausgedientes Shuttle/I5/8GB verwendet, die Harddisk durch eine SSD (Samsung 850Pro, 1TB) ausgetauscht und darauf Debian installiert.

Nach der Vorbereitung der Hardware und einiger ersten Tests haben wir einen Dateisystem-Index ausgearbeitet:

• ein Set an Dateien, die nach den ersten drei Buchstaben der Email-Adresse definiert werden
• beinhalten einen Querverweis auf die Ursprungsdatei/Zeile

Wir haben dann einige Python- und Shell-Skripte erstellt, um mit den Daten dementsprechend umgehen zu können.

Wir haben dann ein Pre-Parsing der Dateien mittels spezieller Tools und sed-Skripten vorgenommen, um eine einheitliche und stabile Dateistruktur erhalten zu können. Dann haben wir den folgenden Ablauf angewendet:

1. Suche nach file (f)
2. Extrahiere email (e)
3. Füge an "e, hash(f)" >> left(e,3)__.idx

Innerhalb zweier Tage konnten alle Dateien gescannt und indiziert werden. Danach war es innert weniger Sekunden möglich, eine Email-Adresse zu finden und einem Datensatz zuzuweisen.

Besonderes Augenmerk wurde auf die Wahl des Hash-Algorithmus gelegt. Dadurch sollte es nämlich möglich sein, mehrere GB an redundanten Informationen einsparen zu können. Mindestens so wichtig war die Balance der Regulären Ausdrücke zur Suche der Email-Adresse: Nicht zu simpel und nicht zu komplex.

Messungen

Analyse von Datensätzen

Resultate

Die Grafik illustriert auf der X-Achse die Anzahl der Chunks und auf der Y-Achse die Anzahl der Dateien, aus denen die Chunks generiert wurden. Dies zeigt, wie die Originaldateien durch Chunking dazu gebracht werden konnten, eine einheitliche Zugriffszeit gewährleisten zu können.

Zeitmessung

Suchzeiten

Die folgende Grafik zeigt auf der X-Achse die Indices in 50k Gruppen (cg), in der linken Y-Achse die Anzahl der Email-Adresse in cg und auf der rechten Y-Achse die schlechteste zu erwartende Zugriffszeit (Worst-Case in Seconds) für gc.

Ungefähr 90% der Email-Adressen können innerhalb von 10s gefunden werden. Für die restlichen 10% ist aber eine überproportionale Zugriffszeit vorgesehen. Basierend auf unseren statistischen Untersuchungen kann ein Reindexing der Top 10 mittels 4 Zeichen eine Zugriffszeit von maximal 10s gewährleisten.

Top Indices

Indizieren bei den 3 linken Zeichen führt zu einem Index mit unterschiedlichen Grössen, abhängig von der Anzahl der betroffenen Email-Adressen. Die Top 3 Indices kommen mit Millionen von Email-Adressen daher:

Es hat sich gezeigt, dass ein Grossteil der extrahierten Email-Adressen mit mar beginnt, direkt gefolgt durch www. Dies deutet darauf hin, dass ein Grossteil der Email-Adressen aus Service-Mails bestehen.

Die folgende Grafik stellt die Index-Grössen als Treemap dar.

Fazit

Durch das Heranziehen spezifischer Tools war es möglich, die Zugriffszeit um ein Vielfaches zu reduzieren. Abhängig von den Anforderungen kann das Anstreben einer Ad Hoc Lösung bessere Resultate versprechen, als der Einsatz von zusätzlicher Hardware und komplexer Tools.

Über den Autor

Rocco Gagliardi ist seit den 1980er Jahren im Bereich der Informationstechnologie tätig. In den 1990er Jahren hat er sich ganz der Informationssicherheit verschrieben. Die Schwerpunkte seiner Arbeit liegen im Bereich Security Frameworks, Routing, Firewalling und Log Management.

Links

• https://stedolan.github.io/jq/
• https://www.regular-expressions.info/email.html