Spezialisierte Suchmaschinen - Big Data mit hoher Geschwindigkeit

Spezialisierte Suchmaschinen

Big Data mit hoher Geschwindigkeit

Rocco Gagliardi
von Rocco Gagliardi
am 24. Mai 2018
Lesezeit: 9 Minuten

Keypoints

  • Setzen Sie auf eine eigene Toolchain, um das Ziel effizient erreichen zu können
  • Komplexe Produkte sind selten die richtige Lösung
  • Werkzeuge des Betriebssystems sind von hohem Nutzen: Greifen Sie darauf zurück

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

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:

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

Parameter Wert
Anzahl analysierter Dateien 534
Anzahl analysierter Datensätze 1’895’800’000
Totale Grösse aller Dateien 222 GB

Resultate

Parameter Wert
Anzahl generierter Chunks 189’588
Total Grösse aller Chunks 222 GB
Anzahl generierter Indices 63’242
Total Grösse aller Indices 42 GB
Anzahl aller extrahierten Email-Adressen 757’036’765

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.

Chunking führt zu einheitlichen Zugriffszeiten

Zeitmessung

Parameter Wert
Vorbereitung ca. 1 Tag
Indexing ca. 1 Tag
Geschwindigkeit für Index auf Dateisystem ca. 9’000 Records/Sekunde
Geschwindigkeit für Index durch MariaDB ca. 350 Records/Sekunde
Geschwindigkeit für Index durch Elastic ca. 500 Records/Sekunde

Suchzeiten

Parameter Wert
Suche ohne Indexing ca. 960s (16m)
Suche mit Indexes, Best-Case 0.005s
Suche mit Indexes, Worst-Case 66s
Anzahl von indizierten Email-Adressen mit einer Zugriffszeit < 5s 559’356’992 (75%)
Anzahl von indizierten Email-Adressen mit einer Zugriffszeit zwischen 5s und 10s 110’331’635 (15%)
Anzahl von indizierten Email-Adressen mit einer Zugriffszeit > 10s 77’810’353 (10%)

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.

Anzahl von Email-Adressen mit schlechtestmöglicher Zugriffszeit

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:

Indices Anzahl Email-Adressen
mar__.idx 9’763’226
www__.idx 5’548’694
ale__.idx 4’605’329

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.

Übersicht der Index-Grössen

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

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 Routing, Firewalling und Log Management.

Links

Sie brauchen Unterstützung bei einem solchen Projekt?

Unsere Spezialisten kontaktieren Sie gern!

×
Schutz vor Phishing

Schutz vor Phishing

Rocco Gagliardi

Logging

Logging

Rocco Gagliardi

IT Security Policies

IT Security Policies

Rocco Gagliardi

Sie wollen mehr?

Weitere Artikel im Archiv

Sie brauchen Unterstützung bei einem solchen Projekt?

Unsere Spezialisten kontaktieren Sie gern!

Sie wollen mehr?

Weitere Artikel im Archiv