Saya tahu dari universitas tentang filter Bloom , struktur data probabilistik yang dinamai Burton Bloom. Tetapi saya tidak memiliki kesempatan untuk menggunakannya. Bulan lalu, kesempatan seperti itu muncul - dan struktur ini benar-benar membuat saya terpesona. Namun, saya segera menemukan beberapa kekurangan dalam dirinya. Artikel ini adalah kisah tentang hubungan asmara singkat saya dengan filter Bloom.

Dalam proses meneliti IP spoofing, perlu untuk memeriksa alamat IP dalam paket yang masuk, membandingkannya dengan lokasi geografis dari pusat data kami. Misalnya, paket dari Italia tidak boleh pergi ke pusat data Brasil. Masalah ini mungkin tampak sederhana, tetapi dalam lanskap Internet yang terus berubah itu jauh dari sederhana. Cukuplah untuk mengatakan bahwa pada akhirnya saya mengumpulkan banyak file teks besar dengan kira-kira konten berikut:

Ini berarti bahwa permintaan dari alamat IP yang diselesaikan 192.0.2.1 telah direkam dalam data center Cloudflare nomor 107. Data ini berasal dari banyak sumber, termasuk sampel aktif dan pasif kami, log dari beberapa domain yang kami miliki (misalnya,cloudflare.com), sumber terbuka (misalnya, tabel BGP), dll. Baris yang sama biasanya diulang dalam beberapa file.

Pada akhirnya, saya mendapat dataset raksasa seperti ini. Pada titik tertentu, di semua sumber yang terkumpul, saya menghitung 1 miliar baris. Biasanya saya menulis skrip bash untuk preprocessing data input, tetapi pada skala ini pendekatan ini tidak berhasil. Sebagai contoh, menghapus duplikat dari file kecil ini dari 600 MiB dan 40 juta baris membutuhkan ... keabadian:

Cukuplah untuk mengatakan bahwa garis deduplicating dengan perintah biasa dari jenis sortdalam berbagai konfigurasi (lihat --parallel, --buffer-sizedan --unique) bukan yang terbaik untuk set data yang besar.

Filter mekar

Ilustrasi David Epstein dalam domain publik.

Kemudian saya sadar: jangan mengurutkan garis! Anda perlu menghapus duplikat, sehingga beberapa jenis struktur data 'set' akan bekerja lebih cepat. Selain itu, saya kira-kira tahu ukuran file input (jumlah baris unik), dan hilangnya beberapa data tidak kritis, yaitu, struktur data probabilistik cukup cocok.

Ini sempurna untuk filter Bloom!

Saat Anda membacaWikipedia di filter Bloom, ini adalah bagaimana saya melihat struktur data ini.

Bagaimana Anda menerapkanpluralitas? Diberikan fungsi hash yang ideal dan memori tak terbatas, kita dapat dengan mudah membuat bitmap tak terbatas dan menetapkan angka bit untuk setiap elemenhash(item). Ini memberikan struktur data yang ideal untuk "banyak". Baik? Sepele. Sayangnya, fungsi hash bertabrakan, dan memori tak terbatas tidak ada, jadi dalam kenyataan kita harus berkompromi. Tetapi kita dapat menghitung probabilitas tabrakan dan mengelola nilai ini. Misalnya, kami memiliki fungsi hash yang baik dan memori 128 GB. Kita dapat menghitung bahwa probabilitas tumbukan untuk setiap elemen baru adalah 1 hingga 1099511627776. Ketika Anda menambahkan lebih banyak elemen, probabilitas meningkat saat bitmap diisi.

Selain itu, kita dapat menerapkan lebih dari satu fungsi hash dan mendapatkan bitmap yang lebih padat. Di sinilah filter Bloom berfungsi dengan baik, yang merupakan kumpulan data matematika dengan empat variabel:

n - jumlah elemen yang dimasukkan (nomor kardinal)
m - memori yang digunakan oleh bitmap
k - jumlah fungsi hash yang dihitung untuk setiap input
p - probabilitas kebetulan positif palsu

Mengingat nomor kardinal ndan probabilitas positif palsu yang diinginkan p, filter Bloom mengembalikan memori yang diperlukan mdan jumlah fungsi hash yang diperlukan k.

Lihatlah visualisasi Thomas Hurst yang luar biasa ini tentang bagaimana parameter saling memengaruhi.

mmuniq-mekar

Dipandu oleh intuisi, saya menambahkan alat probabilistik mmuniq-bloom ke gudang senjata saya, yang mengambil input STDIN dan hanya mengembalikan garis unik di STDOUT. Seharusnya lebih cepat daripada kombinasi sort+ uniq!

Itu dia:

mmuniq-bloom.c

Untuk kesederhanaan dan kecepatan, saya awalnya menetapkan beberapa parameter. Pertama, kecuali dinyatakan sebaliknya, mmuniq-bloom menggunakan delapan fungsi hash k = 8. Ini tampaknya mendekati angka optimal untuk ukuran data kami, dan fungsi hash dapat dengan cepat menghasilkan delapan hash yang layak. Kemudian kami menyelaraskan memori mdalam bitmap ke kekuatan dua untuk menghindari operasi yang mahal %modulo, yang dalam assembler turun menjadi lambat div. Jika array sama dengan kekuatan dua, kita bisa menggunakan bitwise AND (untuk bersenang-senang, baca bagaimana kompiler mengoptimalkan beberapa operasi divisi dengan mengalikan dengan konstanta ajaib ).

Sekarang kita dapat menjalankannya pada file data yang sama yang kita gunakan sebelumnya:

Oh, itu jauh lebih baik! 12 detik, bukan dua menit. Program ini menggunakan struktur data yang dioptimalkan, jumlah memori yang relatif terbatas, penguraian garis yang dioptimalkan, dan buffering keluaran yang baik ... dan dengan semua ini, 12 detik tampak seperti selamanya dibandingkan dengan alat wc -l:

Apa yang terjadi? Saya mengerti bahwa menghitung string wclebih mudah daripada menghitung string unik, tetapi apakah perbedaan 26 kali benar-benar dibenarkan? Apa yang diterima CPU mmuniq-bloom?

Harus untuk hash komputasi. Utilitas wctidak menghabiskan prosesor, melakukan semua matematika aneh ini untuk masing-masing dari 40 juta baris. Saya menggunakan fungsi hash yang agak non-sepele siphash24, pasti membakar prosesor, kan? Mari kita verifikasi dengan menjalankan hanya fungsi hash, tetapi tidaktidak melakukan operasi dengan filter Bloom:

Ini aneh. Perhitungan fungsi hash hanya membutuhkan waktu sekitar dua detik, meskipun seluruh program dalam menjalankan sebelumnya membutuhkan waktu 12 detik. Apakah satu filter Bloom berfungsi selama 10 detik? Bagaimana ini mungkin? Ini adalah struktur data yang sederhana ...

Senjata Rahasia - Profiler

Saatnya menerapkan alat yang tepat untuk tugas ini - mari kita jalankan profiler dan lihat apa yang sedang dikerjakan prosesor. Pertama, mari kita jalankan straceuntuk memverifikasi bahwa tidak ada panggilan sistem yang tidak terduga:

Semuanya terlihat baik. Sepuluh panggilan ke mmapmasing-masing 4 ms (3971 μs) sangat menarik, tetapi itu tidak masalah. Kami pra-mengisi memori dengan MAP_POPULATE, untuk mencegah kesalahan karena kurangnya halaman.

Apa langkah selanjutnya? Tentu saja perf!

Lalu mari kita lihat hasilnya:

Jadi, kita benar-benar membakar 87,2% dari siklus dalam kode utama. Mari kita lihat di mana tepatnya. Tim perf annotate process_line --sourcesegera menunjukkan sesuatu yang tidak terduga.

Kita melihat bahwa 26,90% dari prosesor terbakarmov, Tapi bukan itu saja! Compiler dengan benar memasukkan fungsi dan memperluas loop. Ternyata sebagian besar siklus mengarah ke ini movatau ke garis uint64_t v = *p!

Jelas perf salah, bagaimana string yang sederhana dapat mengambil begitu banyak sumber daya? Tetapi mengulangi pengujian dengan profiler lain menunjukkan masalah yang sama. Sebagai contoh, saya suka menggunakan google-perftools dengan kcachegrind karena diagram berwarna-warni:

Hasil visualisasi adalah sebagai berikut:

Biarkan saya meringkas apa yang telah kami temukan sejauh ini.

Utilitas standar wcmemproses file 600 MiB untuk waktu prosesor 0,45 detik. Alat kami yang dioptimalkan mmuniq-bloomberjalan 12 detik. Prosesor dibakar pada satu instruksi mov, memori dereferencing ...

Gambar dari Jose Nicdao , CC BY / 2.0

Oh! Bagaimana saya bisa lupa. Akses acak ke memorisangatlambat! Sangat, sangat, sangat lambat!

Menurutangka yang harus diketahui oleh setiap programmer, satu akses ke RAM membutuhkan waktu sekitar 100 ns. Mari kita hitung: 40 juta baris, masing-masing 8 hash. Karena filter Bloom kami memiliki ukuran 128 MiB, padaperangkat keras lama kamitidak muat ke cache L3! Hash didistribusikan secara merata di berbagai memori - masing-masing menghasilkan cache miss. Menyatukan semuanya, dan ternyata ...

Ternyata 32 detik terbakar hanya pada akses memori. Program sebenarnya cocok hanya dalam 12 detik, karena filter Bloom masih mendapat manfaat dari caching. Ini mudah dilihat perf stat -d:

Ya, kita seharusnya memiliki minimal 320 juta cache cache (LLC-load-misses), tetapi hanya 280 juta yang terjadi: ini masih tidak menjelaskan mengapa program bekerja hanya dalam 12 detik. Tapi itu tidak masalah. Adalah penting bahwa jumlah cache yang hilang adalah masalah nyata, dan kita dapat menyelesaikannya hanya dengan mengurangi jumlah akses memori. Mari kita coba mengkonfigurasi filter Bloom untuk menggunakan hanya satu fungsi hash:

Ay! Sangat menyakitkan! Untuk mendapatkan probabilitas tabrakan 1 per 10.000 baris, filter Bloom memerlukan 64 gigabytes memori. Ini mengerikan!

Selain itu, sepertinya kecepatannya tidak meningkat secara signifikan. Butuh sistem operasi 22 detik untuk menyiapkan memori bagi kami, tetapi kami masih menghabiskan 11 detik di ruang pengguna. Saya percaya bahwa sekarang semua keuntungan dari akses yang lebih jarang ke memori dikompensasi oleh probabilitas yang lebih rendah untuk masuk ke cache karena ukuran memori meningkat tajam. Sebelumnya, 128 MiB sudah cukup untuk filter Bloom!

Menolak Filter Bloom

Ini semakin konyol. Untuk mengurangi kemungkinan kesalahan positif, Anda harus menggunakan banyak hash di filter Bloom (misalnya, delapan) dengan banyak akses memori, atau meninggalkan satu fungsi hash, tetapi gunakan memori dalam jumlah besar.

Kami sebenarnya tidak memiliki batas memori, kami ingin meminimalkan jumlah panggilan ke sana. Kami membutuhkan struktur data yang memerlukan biaya maksimum satu cache miss per elemen dan menggunakan RAM kurang dari 64 gigabyte ...

Tentu saja, Anda dapat menerapkan struktur data yang kompleks, seperti filter kukuk , tetapi tentu ada opsi yang lebih mudah. Bagaimana dengan tabel hash probing linier yang bagus?

Ilustrasi Podans Vadims

Temui mmuniq-hash

Ini adalah versi baru dari mmuniq-bloom menggunakan tabel hash:

mmuniq-hash.c

Alih-alih bit untuk filter Bloom, kami sekarang menyimpan hash 64-bit dari fungsi 'siphash24' . Ini memberikan perlindungan yang jauh lebih baik terhadap tabrakan hash: jauh lebih baik dari satu per 10.000 baris.

Mari berhitung. Menambahkan item baru ke tabel hash, katakanlah dengan 40 juta entri, memberikan peluang tabrakan hash 40 000 000/2^64. Ini sekitar 1 dalam 461 miliar - probabilitas yang cukup rendah. Tapi kami tidak menambahkan satu elemen ke set yang sudah diisi sebelumnya! Sebagai gantinya, kami menambahkan 40 juta baris ke set yang awalnya kosong. Menurut paradoks ulang tahun , ini sangat meningkatkan kemungkinan tabrakan. Perkiraan yang masuk akal akan menjadi perkiraan '~n^2/2m, dalam kasus kami adalah~(40M^2)/(2*(2^64)). Ternyata satu peluang dari 23.000. Dengan kata lain, dengan fungsi hash yang baik, kami mengharapkan tabrakan di salah satu dari 23.000 kumpulan acak dari 40 juta elemen. Ini adalah probabilitas non-nol, tetapi masih lebih baik daripada di filter Bloom, dan sepenuhnya dapat ditoleransi untuk kasus penggunaan kami.

Kode dengan tabel hash bekerja lebih cepat, ia memiliki pola akses memori yang lebih baik dan probabilitas positif palsu yang lebih rendah daripada di filter Bloom.

Jangan khawatir dengan garis "konflik hash", itu hanya menunjukkan seberapa penuh tabel hash. Kami menggunakan penginderaan linier, jadi ketika kami masuk ke set lengkap, kami hanya mengambil yang kosong berikutnya. Dalam kasus kami, kami harus melewati rata-rata 0,7 set untuk menemukan tempat kosong di tabel. Ini normal. Karena kita beralih pada set dalam urutan linier, memori harus penuh secara kualitatif.

Dari contoh sebelumnya, kita tahu bahwa fungsi hash kita membutuhkan waktu sekitar dua detik. Kami menyimpulkan bahwa 40 juta akses memori membutuhkan waktu sekitar empat detik.

Pelajaran yang dipetik

Prosesor modern sangat baik dalam mengakses berurutan ke memori ketika dimungkinkan untuk memprediksi pola pengambilan sampel (lihat pengambilan cache sebelumnya ). Akses acak ke memori, di sisi lain, sangat mahal.

Struktur data lanjutan sangat menarik, tetapi hati-hati. Komputer modern membutuhkan penggunaan algoritma yang dioptimalkan cache. Saat bekerja dengan kumpulan data besar yang tidak sesuai dengan L3, optimalisasi atas jumlah hit lebih disukai, daripada optimasi atas jumlah memori yang digunakan.

Wajar untuk mengatakan bahwa filter Bloom berperforma hebat ketika ditempatkan di cache L3. Tetapi jika tidak, maka mereka mengerikan. Ini bukan berita: Filter Bloom dioptimalkan untuk jumlah memori, bukan jumlah panggilan ke sana. Sebagai contoh, lihatartikel ilmiah tentang filter kukuk .

Hal lain adalah diskusi tanpa akhir tentang fungsi hash. Jujur, dalam banyak kasus ini tidak masalah. Biaya menghitung bahkan fungsi hash yang kompleks tampaknya siphash24kecil dibandingkan dengan biaya akses acak ke memori. Dalam kasus kami, menyederhanakan fungsi hash hanya akan membawa sedikit manfaat. Waktu CPU hanya terbuang sia-sia - menunggu memori!

Seorang kolega sering mengatakan: “Dapat diasumsikan bahwa prosesor modern sangat cepat. Mereka bekerja dengan kecepatan tak terbatas, sampai mereka bersandar pada dinding memori . "

Akhirnya, jangan ulangi kesalahan saya. Anda selalu perlu melakukan profiling terlebih dahuluperf stat -ddan lihat penghitung IPC (instruksi per siklus). Jika kurang dari satu, ini biasanya berarti bahwa program macet menunggu memori. Nilai optimal di atas dua. Ini berarti bahwa beban kerjanya terutama pada CPU. Sayangnya, dalam tugas saya, IPC masih rendah ...

Mmuniq unggul

Dengan bantuan kolega, saya menulis versi perbaikan alat mmuniq berdasarkan tabel hash. Ini kodenya:

mmuniq.c

Itu secara dinamis dapat mengubah ukuran tabel hash, mendukung input dengan nomor kardinal sewenang-wenang. Kemudian memproses data dalam paket, secara efektif menggunakan petunjuk prefetchdi CPU, yang mempercepat program sebesar 35-40%. Hati-hati, penggunaan berlebihan prefetchdalam kode jarang memberikan efek. Untuk menggunakan fungsi ini, saya secara khusus memesan ulang algoritma. Dengan semua peningkatan, waktu eksekusi dikurangi menjadi 2,1 detik:

tamat

Penciptaan alat dasar yang mencoba mengungguli kombinasi 'sort / uniq' telah mengungkapkan beberapa fitur tersembunyi dari komputasi modern. Setelah sedikit berkeringat, kami mempercepat program dari lebih dari dua menit menjadi dua detik. Selama pengembangan, kami belajar tentang penundaan akses acak ke memori, serta kekuatan struktur data yang ramah-cache. Struktur data yang aneh menarik perhatian, tetapi dalam praktiknya seringkali lebih efisien untuk mengurangi jumlah akses acak ke memori.

Ketika filter mekar tidak cocok