Ich wusste von der Universität über den Bloom-Filter Bescheid , eine probabilistische Datenstruktur, die nach Burton Bloom benannt ist. Aber ich hatte keine Gelegenheit, es zu nutzen. Im vergangenen Monat bot sich eine solche Gelegenheit - und diese Struktur faszinierte mich buchstäblich. Ich fand jedoch bald einige Mängel in ihr. Dieser Artikel ist eine Geschichte über meine kurze Liebesbeziehung mit dem Bloom-Filter.

Bei der Untersuchung des IP-Spoofing mussten die IP-Adressen in den eingehenden Paketen überprüft und mit dem geografischen Standort unserer Rechenzentren verglichen werden. Beispielsweise sollten Pakete aus Italien nicht in das brasilianische Rechenzentrum gehen. Dieses Problem mag einfach erscheinen, aber in der sich ständig ändernden Landschaft des Internets ist es alles andere als einfach. Es genügt zu sagen, dass ich am Ende viele große Textdateien mit ungefähr dem folgenden Inhalt gesammelt habe:

Dies bedeutet, dass eine Anfrage von der aufgelösten IP-Adresse 192.0.2.1 im Cloudflare-Rechenzentrum Nummer 107 aufgezeichnet wurde. Diese Daten stammen aus vielen Quellen, einschließlich unserer aktiven und passiven Beispiele, den Protokollen einiger Domänen, die wir besitzen (z. B.cloudflare.com), Open Source (z. B. BGP-Tabellen) usw. Dieselbe Zeile wird normalerweise in mehreren Dateien wiederholt.

Am Ende hatte ich einen riesigen Datensatz dieser Art. Irgendwann zählte ich in allen gesammelten Quellen 1 Milliarde Zeilen. Normalerweise schreibe ich Bash-Skripte für die Vorverarbeitung der Eingabedaten, aber in diesem Maßstab hat dieser Ansatz nicht funktioniert. Zum Beispiel nimmt Duplikate aus dieser kleinen Datei von 600 MiB und 40 Millionen Zeilen zu entfernen ... Ewigkeit:

Es reicht aus , dass die Deduplizierung Linien mit gewöhnlichen Befehlen des Typs zu sagen , sortin verschiedenen Konfigurationen (siehe --parallel, --buffer-sizeund --unique) war nicht die beste für einen so großen Datensatz.

Bloom Filter

Illustration von David Epstein im öffentlichen Bereich

Dann wurde mir klar: Sortieren Sie die Zeilen nicht! Sie müssen Duplikate entfernen, damit eine Art 'festgelegte' Datenstruktur viel schneller funktioniert. Außerdem kenne ich ungefähr die Größe der Eingabedatei (die Anzahl der eindeutigen Zeilen), und der Verlust einiger Daten ist nicht kritisch, dh die probabilistische Datenstruktur ist durchaus geeignet.

Dies ist perfekt für Bloom-Filter!

Während SieWikipedia über Bloom-Filterlesen, sehe ich diese Datenstruktur so.

Wie würden Siedie Pluralitätumsetzen? Bei einer idealen Hash-Funktion und einem unendlichen Speicher können wir einfach eine unendliche Bitmap erstellen und für jedes Element eine Bitnummer festlegenhash(item). Dies liefert die ideale Datenstruktur für die "Menge". Recht? Trivial. Leider kollidieren Hash-Funktionen und es gibt kein unendliches Gedächtnis. In unserer Realität müssen wir also Kompromisse eingehen. Wir können aber die Wahrscheinlichkeit von Kollisionen berechnen und diesen Wert verwalten. Zum Beispiel haben wir eine gute Hash-Funktion und 128 GB Speicher. Wir können berechnen, dass die Kollisionswahrscheinlichkeit für jedes neue Element 1 in 1099511627776 beträgt. Wenn Sie weitere Elemente hinzufügen, erhöht sich die Wahrscheinlichkeit, wenn die Bitmap gefüllt wird.

Darüber hinaus können wir mehr als eine Hash-Funktion anwenden und eine dichtere Bitmap erhalten. Hier funktioniert der Bloom-Filter gut. Hierbei handelt es sich um einen Satz mathematischer Daten mit vier Variablen:

n - Anzahl der eingefügten Elemente (Kardinalzahl)
m - Von der Bitmap verwendeter Speicher
k - Die Anzahl der für jede Eingabe berechneten Hash-Funktionen
p - Wahrscheinlichkeit eines falsch positiven Zufalls

Angesichts der Kardinalzahl nund der gewünschten Wahrscheinlichkeit von Fehlalarmen pgibt der Bloom-Filter den erforderlichen Speicher mund die erforderliche Anzahl von Hash-Funktionen zurück k.

Schauen Sie sich diese hervorragende Thomas Hurst- Visualisierung an, wie sich Parameter gegenseitig beeinflussen.

mmuniq-Blüte

Von der Intuition geleitet, habe ich meinem Arsenal das probabilistische Werkzeug mmuniq-bloom hinzugefügt, das die Eingabe STDIN verwendet und nur eindeutige Zeilen in STDOUT zurückgibt. Es sollte viel schneller sein als eine Kombination von sort+ uniq!

Da ist er:

mmuniq-bloom.c

Der Einfachheit und Geschwindigkeit halber habe ich zunächst einige Parameter eingestellt. Erstens verwendet mmuniq-bloom, sofern nicht anders angegeben, acht Hash-Funktionen k = 8. Dies scheint nahe an der optimalen Anzahl für unsere Datengröße zu liegen, und die Hash-Funktion kann schnell acht anständige Hashes erzeugen. Dann richten wir den Speicher min der Bitmap auf eine Zweierpotenz aus, um eine teure Operation zu vermeiden %modulo, die im Assembler zu langsam wird div. Wenn das Array gleich der Zweierpotenz ist, können wir nur bitweises UND verwenden (lesen Sie zum Spaß, wie die Compiler einige Divisionsoperationen durch Multiplikation mit einer magischen Konstante optimieren ).

Jetzt können wir es mit derselben Datendatei ausführen, die wir zuvor verwendet haben:

Oh, das ist viel besser! 12 Sekunden statt zwei Minuten. Das Programm verwendet eine optimierte Datenstruktur, eine relativ begrenzte Speichermenge, eine optimierte Zeilenanalyse und eine gute Ausgabepufferung ... und bei alledem scheinen 12 Sekunden im Vergleich zum Tool eine Ewigkeit zu sein wc -l:

Was passiert? Ich verstehe, dass das Einzählen von Zeichenfolgen wceinfacher ist als das Berechnen eindeutiger Zeichenfolgen, aber ist der 26-fache Unterschied wirklich gerechtfertigt? Was nimmt die CPU auf mmuniq-bloom?

Muss für die Berechnung von Hashes sein. Das Dienstprogramm wcgibt den Prozessor nicht aus und führt all diese seltsamen Berechnungen für jede der 40 Millionen Zeilen durch. Ich benutze eine eher nicht triviale Hash-Funktion siphash24, die den Prozessor sicher verbrennt, oder? Lassen Sie uns überprüfen, indem Sie nur die Hash-Funktion ausführen, aber nichtKeine Operationen mit dem Bloom-Filter ausführen:

Das ist seltsam. Die Berechnung der Hash-Funktion dauert nur etwa zwei Sekunden, obwohl das gesamte Programm im vorherigen Lauf 12 Sekunden lang ausgeführt wurde. Funktioniert ein Bloom-Filter 10 Sekunden lang? Wie ist das möglich? Dies ist eine so einfache Datenstruktur ...

Geheimwaffe - Profiler

Es ist Zeit, das richtige Tool für diese Aufgabe anzuwenden. Lassen Sie uns den Profiler ausführen und sehen, woran der Prozessor arbeitet. Lassen Sie uns stracezunächst überprüfen, ob keine unerwarteten Systemaufrufe vorliegen:

Alles sieht gut aus. Zehn Anrufe zu je mmap4 ms (3971 μs) sind faszinierend, aber das ist in Ordnung. Wir füllen den Speicher vor MAP_POPULATE, um später Fehler aufgrund fehlender Seite zu vermeiden.

Was ist der nächste Schritt? Natürlich ist es das perf!

Dann sehen wir uns das Ergebnis an:

Wir brennen also wirklich 87,2% der Zyklen im Hauptcode. Mal sehen wo genau. Das Team perf annotate process_line --sourcezeigt sofort etwas Unerwartetes.

Wir sehen, dass 26,90% des Prozessors ausgebrannt sindmov, Aber das ist nicht alles! Der Compiler fügt die Funktion korrekt ein und erweitert die Schleife. Es stellt sich heraus, dass die meisten Zyklen zu dieser movoder zur Linie gehen uint64_t v = *p!

Offensichtlich ist Perf falsch. Wie kann eine so einfache Zeichenfolge so viele Ressourcen beanspruchen? Das Wiederholen des Tests mit einem anderen Profiler zeigt jedoch das gleiche Problem. Zum Beispiel verwende ich wegen der farbenfrohen Diagramme gerne Google-Perftools mit kcachegrind:

Das Visualisierungsergebnis lautet wie folgt:

Lassen Sie mich zusammenfassen, was wir bisher entdeckt haben.

Das Standarddienstprogramm wcverarbeitet eine 600-MiB-Datei für eine Prozessorzeit von 0,45 s. Unser optimiertes Tool mmuniq-bloomläuft 12 Sekunden. Der Prozessor wird auf einen Befehl gebrannt mov, wodurch der Speicher dereferenziert wird ...

Bild von Jose Nicdao , CC BY / 2.0

Oh! Wie könnte ich vergessen. Der zufällige Zugriff auf den Speicher istsehrlangsam! Sehr, sehr, sehr langsam!

Nach denZahlen, die jeder Programmierer kennen sollte,dauert ein einzelner Zugriff auf den RAM etwa 100 ns. Zählen wir: 40 Millionen Zeilen mit jeweils 8 Hashes. Da unser Bloom-Filter eine Größe von 128 MiB hat,passt eraufunserer alten Hardwarenicht in den L3-Cache! Hashes sind gleichmäßig über einen weiten Speicherbereich verteilt - jeder von ihnen erzeugt einen Cache-Miss. Alles zusammen und es stellt sich heraus ...

Es stellt sich heraus, dass 32 Sekunden nur bei Speicherzugriffen ausbrennen. Das eigentliche Programm passt in nur 12 Sekunden, da der Bloom-Filter immer noch vom Caching profitiert. Dies ist leicht zu erkennen bei perf stat -d:

Ja, wir hätten mindestens 320 Millionen Cache-Fehler (LLC-Ladefehler) haben müssen, aber nur 280 Millionen sind passiert: Dies erklärt immer noch nicht, warum das Programm in nur 12 Sekunden funktioniert hat. Aber das ist egal. Es ist wichtig, dass die Anzahl der Cache-Fehler ein echtes Problem darstellt, und wir können es nur lösen, indem wir die Anzahl der Speicherzugriffe reduzieren. Versuchen wir, den Bloom-Filter so zu konfigurieren, dass nur eine Hash-Funktion verwendet wird:

Ay! Es tut wirklich weh! Um eine Kollisionswahrscheinlichkeit von 1 pro 10.000 Zeilen zu erhalten, benötigte der Bloom-Filter 64 Gigabyte Speicher. Es ist schrecklich!

Darüber hinaus scheint die Geschwindigkeit nicht wesentlich zugenommen zu haben. Das Betriebssystem brauchte 22 Sekunden, um den Speicher für uns vorzubereiten, aber wir verbrachten immer noch 11 Sekunden im Benutzerbereich. Ich glaube, dass jetzt alle Vorteile eines selteneren Zugriffs auf den Speicher durch eine geringere Wahrscheinlichkeit kompensiert werden, aufgrund einer stark erhöhten Speichergröße in den Cache zu gelangen. Früher reichten 128 MiB für den Bloom-Filter!

Bloom-Filter ablehnen

Das wird nur lächerlich. Um die Wahrscheinlichkeit von Fehlalarmen zu verringern, müssen Sie entweder viele Hashes im Bloom-Filter (z. B. acht) mit einer großen Anzahl von Speicherzugriffen verwenden oder eine Hash-Funktion belassen, aber sehr viel Speicher verwenden.

Wir haben eigentlich kein Speicherlimit, wir wollen die Anzahl der Aufrufe minimieren. Wir brauchen eine Datenstruktur, die maximal einen Cache-Miss pro Element kostet und weniger als 64 Gigabyte RAM benötigt ...

Natürlich können Sie komplexe Datenstrukturen wie einen Kuckucksfilter implementieren , aber es gibt sicherlich eine einfachere Option. Was ist mit der guten alten linearen Probing-Hash-Tabelle?

Illustration von Vadims Podans

Treffen Sie mmuniq-Hash

Hier ist die neue Version von mmuniq-bloom unter Verwendung einer Hash-Tabelle:

mmuniq-hash.c

Anstelle der Bits für den Bloom-Filter speichern wir jetzt 64-Bit-Hashes aus der Funktion 'siphash24' . Dies bietet einen viel besseren Schutz gegen Hash-Kollisionen: viel besser als eine pro 10.000 Zeilen.

Lass uns zählen. Das Hinzufügen eines neuen Elements zu einer Hash-Tabelle, beispielsweise mit 40 Millionen Einträgen, erhöht die Wahrscheinlichkeit von Hash-Kollisionen 40 000 000/2^64. Dies ist ungefähr 1 von 461 Milliarden - eine ziemlich geringe Wahrscheinlichkeit. Wir fügen dem vorgefüllten Set jedoch kein Element hinzu! Stattdessen fügen wir dem anfänglich leeren Satz 40 Millionen Zeilen hinzu. Nach dem Geburtstagsparadoxon erhöht dies die Wahrscheinlichkeit von Kollisionen erheblich. Eine vernünftige Annäherung wäre '~n^2/2min unserem Fall eine Schätzung~(40M^2)/(2*(2^64)). Es ergibt sich eine Chance von 23.000. Mit anderen Worten, mit einer guten Hash-Funktion erwarten wir eine Kollision in einer der 23.000 zufälligen Mengen von 40 Millionen Elementen. Dies ist eine Wahrscheinlichkeit ungleich Null, aber immer noch besser als im Bloom-Filter und für unseren Anwendungsfall vollständig tolerierbar.

Code mit einer Hash-Tabelle funktioniert schneller, hat bessere Speicherzugriffsmuster und eine geringere Wahrscheinlichkeit von Fehlalarmen als im Bloom-Filter.

Lassen Sie sich nicht von der Zeile "Hash-Konflikte" beunruhigen, sie zeigt nur, wie voll die Hash-Tabelle ist. Wir verwenden die lineare Abtastung. Wenn wir also in den vollständigen Satz kommen, nehmen wir einfach den nächsten leeren. In unserem Fall müssen wir durchschnittlich 0,7 Sätze überspringen, um eine leere Stelle in der Tabelle zu finden. Es ist in Ordnung. Da wir die Mengen in einer linearen Reihenfolge durchlaufen, muss der Speicher qualitativ voll sein.

Aus dem vorherigen Beispiel wissen wir, dass unsere Hash-Funktion ungefähr zwei Sekunden dauert. Wir schließen daraus, dass 40 Millionen Speicherzugriffe etwa vier Sekunden dauern.

Gewonnene Erkenntnisse

Moderne Prozessoren können sehr gut sequentiell auf den Speicher zugreifen, wenn Sie Beispielmuster vorhersagen können (siehe Cache-Prefetching ). Der zufällige Zugriff auf den Speicher ist dagegen sehr teuer.

Erweiterte Datenstrukturen sind sehr interessant, aber seien Sie vorsichtig. Moderne Computer erfordern die Verwendung von Cache-optimierten Algorithmen. Bei der Arbeit mit großen Datenmengen, die nicht in L3 passen, wird die Optimierung über die Anzahl der Treffer gegenüber der Optimierung über die verwendete Speichermenge bevorzugt.

Man kann mit Recht sagen, dass Bloom-Filter im L3-Cache eine hervorragende Leistung erbringen. Aber wenn nicht, dann sind sie schrecklich. Dies ist keine Neuigkeit: Bloom-Filter sind für die Speichermenge optimiert, nicht für die Anzahl der Aufrufe. Zum Beispiel siehewissenschaftlicher Artikel über Kuckucksfilter .

Eine andere Sache sind endlose Diskussionen über Hash-Funktionen. Ehrlich gesagt spielt dies in den meisten Fällen keine Rolle. Die Kosten für das Zählen selbst komplexer Hash-Funktionen scheinen im siphash24Vergleich zu den Kosten für den wahlfreien Zugriff auf den Speicher gering zu sein. In unserem Fall bringt die Vereinfachung der Hash-Funktion nur einen geringen Vorteil. CPU-Zeit wird nur woanders verschwendet - auf Speicher warten!

Ein Kollege sagt oft: „Man kann davon ausgehen, dass moderne Prozessoren unendlich schnell sind. Sie arbeiten mit unendlicher Geschwindigkeit, bis sie an der Wand der Erinnerung ruhen . "

Schließlich wiederholen Sie nicht meinen Fehler. Sie müssen immer zuerst eine Profilerstellung durchführenperf stat -dund schauen Sie sich den IPC-Zähler an (Anweisungen pro Zyklus). Wenn es weniger als eins ist, bedeutet dies normalerweise, dass das Programm nicht mehr auf Speicher wartet. Die optimalen Werte liegen über zwei. Dies bedeutet, dass die Arbeitslast hauptsächlich auf der CPU liegt. Leider ist der IPC bei meinen Aufgaben immer noch niedrig ...

Überlegene mmuniq

Mit Hilfe von Kollegen habe ich eine verbesserte Version des mmuniq-Tools basierend auf einer Hash-Tabelle geschrieben. Hier ist der Code:

mmuniq.c

Es kann die Größe der Hash-Tabelle dynamisch ändern und unterstützt die Eingabe mit einer beliebigen Kardinalzahl. Anschließend werden die Daten in Paketen verarbeitet, wobei der Hinweis prefetchin der CPU effektiv verwendet wird , wodurch das Programm um 35-40% beschleunigt wird. Seien Sie vorsichtig, eine reichliche Verwendung prefetchdes Codes führt selten zu einer Wirkung. Um diese Funktion nutzen zu können, habe ich die Algorithmen speziell neu angeordnet. Mit allen Verbesserungen wurde die Ausführungszeit auf 2,1 Sekunden reduziert:

das Ende

Die Entwicklung eines grundlegenden Tools, das versucht, die Kombination 'sort / uniq' zu übertreffen, hat einige verborgene Merkmale des modernen Computing aufgedeckt. Nachdem wir ein wenig geschwitzt hatten, beschleunigten wir das Programm von mehr als zwei Minuten auf zwei Sekunden. Während der Entwicklung haben wir die Verzögerung beim Direktzugriff auf den Speicher sowie die Leistungsfähigkeit cachefreundlicher Datenstrukturen kennengelernt. Bizarre Datenstrukturen ziehen die Aufmerksamkeit auf sich, aber in der Praxis ist es oft effizienter, die Anzahl der zufälligen Zugriffe auf den Speicher zu reduzieren.

Wenn der Bloom-Filter nicht passt