Hari Baik untuk trie-hard: Menghemat 1% Komputasi

 (blog.cloudflare.com)
2 poin oleh GN⁺ 2024-09-11 | 1 komentar | Bagikan ke WhatsApp
  • Cloudflare merilis crate Rust open source trie-hard untuk mengurangi penggunaan CPU pada Pingora, proxy berbasis Rust, di jaringan yang rata-rata menangani lebih dari 60 juta permintaan HTTP per detik
  • Titik bottleneck ada di fungsi clear_internal_headers milik pingora-origin, yang menghapus header untuk routing internal, pengukuran, dan optimasi dari permintaan non-cache yang keluar dari Cloudflare, dan dijalankan pada jalur 35 juta permintaan per detik
  • Implementasi lama mencoba menghapus lebih dari 100 header internal pada setiap permintaan dan rata-rata memerlukan 3.65µs, menghabiskan 1,71% dari total waktu CPU pingora-origin, setara sekitar 680 core CPU dari 40.000 compute-seconds/detik
  • Pendekatan yang lebih dulu menelusuri header permintaan nyata rata-rata berjalan dalam 1.53µs, 2,39x lebih cepat, tetapi penghematan CPU total secara teoretis hanya 0,993%, sehingga dibutuhkan struktur pencarian yang lebih baik
  • Implementasi trie baru menurunkan waktu eksekusi rata-rata menjadi 0.93µs, dan sampling yang dijalankan di produksi sejak Juli 2024 juga menunjukkan penggunaan CPU nyata clear_internal_headers turun hingga 0,34%

Biaya yang ingin dikurangi Cloudflare

  • Jaringan global Cloudflare rata-rata menangani lebih dari 60 juta permintaan HTTP per detik
  • Optimasi kali ini dimulai dari Pingora, inti layanan proxy berbasis Rust, dan layanan produksi pingora-origin yang berjalan di atasnya
  • pingora-origin bertanggung jawab atas tahap terakhir yang mengirim permintaan non-cache pengguna ke server tujuan sebenarnya, yaitu origin
  • Sebelum permintaan meninggalkan infrastruktur Cloudflare, layanan ini harus menghapus informasi pada header yang dipakai untuk routing internal, pengukuran, dan optimasi
  • Secara global, jumlah permintaan yang meninggalkan pingora-origin adalah 35 juta per detik pada saat tulisan ini dibuat

Fungsi bottleneck: clear_internal_headers

  • Fungsi ini berada di jalur yang sangat panas dan dijalankan pada semua permintaan
// PERF: heavy function: 1.7% CPU time
pub fn clear_internal_headers(request_header: &mut RequestHeader) {
    INTERNAL_HEADERS.iter().for_each(|h| {
        request_header.remove_header(h);
    });
}
  • Fungsi kecil ini sendiri memakai lebih dari 1,7% dari total waktu CPU pingora-origin
  • Total waktu CPU pingora-origin adalah 40.000 compute-seconds per detik, setara dengan 40 ribu core CPU tersaturasi yang hanya menjalankan layanan ini
  • Dari angka itu, 1,7% atau sekitar 680 core CPU dipakai hanya untuk mengevaluasi clear_internal_headers

Pengukuran dasar dan perbaikan pertama

  • Untuk mengukur performa, digunakan crate Rust criterion
  • Criterion menggabungkan banyak eksekusi terisolasi untuk mengukur waktu kode Rust hingga satuan nanodetik, sekaligus memberikan umpan balik tentang peningkatan atau penurunan performa dari waktu ke waktu
  • Input benchmark adalah kumpulan besar permintaan sintetis yang dibuat agar header internal dan non-internal terdistribusi merata
  • Waktu eksekusi rata-rata clear_internal_headers lama terukur 3.65µs

  • Membalik arah pencarian

    • Kode lama menjalankan request_header.remove_header(h) untuk setiap item di daftar header internal, jadi bila ada lebih dari 100 header internal, maka setiap permintaan dievaluasi lebih dari 100 kali
    • Jumlah header pada permintaan rata-rata jauh lebih sedikit daripada 100, yakni sekitar 10~30, sehingga lebih efisien menelusuri header permintaan nyata lalu mencarinya di himpunan header internal untuk mengurangi jumlah pembacaan
    • http::HeaderMap di Rust belum memiliki retain, jadi header internal yang akan dihapus harus dikumpulkan dulu pada tahap terpisah lalu dihapus
    • Perubahan ini saja menurunkan waktu eksekusi rata-rata dari 3.65µs menjadi 1.53µs, atau 2,39x lebih cepat
    • Secara teoretis, penggunaan CPU total turun dari 1,71% menjadi 0,717%, dengan penghematan 0,993%

Menjelajahi struktur data pencarian yang lebih baik

  • Setelah arah pencarian dibalik, menjadi mungkin untuk memilih struktur data penyimpanan bagi daftar statis header internal
pub fn clear_internal_headers(request_header: &mut RequestHeader) {
   let to_remove = request_header
       .headers
       .keys()
       .filter_map(|name| INTERNAL_HEADER_SET.get(name))
       .collect::<Vec<_>>();

   to_remove.into_iter().for_each(|k| {
       request_header.remove_header(k);
   });
}
  • Percobaan pertama adalah std::HashMap, tetapi hashing kunci string harus membaca semua byte, sehingga walaupun waktunya konstan terhadap ukuran tabel, ia tetap linear terhadap panjang kunci L
  • Tujuannya adalah mencari struktur data dengan perilaku pembacaan yang lebih baik daripada O(L) terhadap panjang kunci

  • Alternatif yang ditinjau

    • Himpunan terurut seperti BTreeSet memakai pencarian berbasis perbandingan dan memberi perilaku O(log(L)) terhadap panjang kunci, tetapi juga membutuhkan waktu logaritmik terhadap ukuran himpunan
    • Himpunan terurut cepat FST juga dalam benchmark ternyata sekitar 50ns lebih lambat daripada hashmap standar
    • Mesin status seperti parser atau regex menerima input satu unit demi satu unit dan pada setiap langkah memutuskan apakah evaluasi perlu dilanjutkan, sehingga bisa cepat mengidentifikasi string yang tidak cocok
    • Header internal rata-rata hanya 1~2 per permintaan, sehingga kasus negatif mendominasi dan cocok dengan pendekatan ini
    • Implementasi clear_internal_headers berbasis regex memakan waktu sekitar 2x lebih lama daripada solusi berbasis hashmap, tetapi hasil itu tetap cepat mengingat regex bukan alat yang dikenal karena kecepatan mentah

Mengapa trie cocok

  • trie adalah struktur data pohon yang sering dipakai untuk pencarian prefiks atau autocomplete pada himpunan string yang sudah diketahui
  • Setiap node pada trie merepresentasikan substring yang ditemukan dalam himpunan string awal, dan koneksi antar-node menunjukkan karakter yang bisa muncul setelah prefiks tertentu
  • Dengan memulai dari node root, ruang pencarian bisa dipersempit sejak karakter pertama yang memungkinkan, sehingga string yang tidak termasuk dapat cepat dieliminasi
  • Pembacaan trie memberi perilaku O(log(L)) untuk kasus tidak cocok, tetapi untuk kasus cocok masih O(L)
  • Karena lebih dari 90% header permintaan bukan header internal, use case ini cocok untuk trie yang unggul pada banyak kasus tidak cocok

  • Keterbatasan implementasi trie yang sudah ada

    • Berbagai implementasi trie di crates.io diuji dengan benchmark, tetapi hasilnya tidak memuaskan
    • Kebanyakan trie dirancang untuk use case seperti autocomplete yang merespons event keyboard, sehingga optimasi jalur panas dengan puluhan juta permintaan per detik bukan prioritas utama
    • Implementasi yang sudah ada dan paling cepat ditemukan adalah radix_trie, tetapi tetap 1µs lebih lambat daripada hashmap
    • Akhirnya dibuat implementasi trie baru yang disesuaikan untuk use case ini

trie-hard dan hasil di produksi

  • Cloudflare merilis crate Rust open source baru trie-hard

  • trie-hard memperoleh kecepatan dengan menyimpan relasi node pada bit integer tak bertanda, dan menjaga seluruh trie dalam blok memori yang berurutan

  • Dalam benchmark, trie-hard menurunkan waktu eksekusi rata-rata clear_internal_headers menjadi 0.93µs

  • Penggunaan CPU yang diperkirakan adalah 0,43%, dan dibandingkan 1,71% sebelumnya, ini menurunkan penggunaan komputasi total pingora-origin sebesar 1,28%

  • Hasil sampling nyata

    • trie-hard sudah berjalan di produksi sejak Juli 2024
    • Pengukuran performa dikumpulkan melalui sampling statistik stack trace dari waktu ke waktu
    • Rasio sampel yang memuat fungsi tertentu dipakai untuk memperkirakan penggunaan CPU fungsi tersebut
    • Hasil sampling di produksi secara umum cukup dekat dengan prediksi benchmark lokal
    Implementasi Sampel stack trace yang memuat clear_internal_headers Penggunaan CPU nyata Prediksi penggunaan CPU
    Original 19 / 1111 1.71% n/a
    Hashmap 9 / 1103 0.82% 0.72%
    trie-hard 4 / 1171 0.34% 0.43%

Kesimpulan dari sudut pandang operasional

  • Sebelum menulis struktur data baru, yang lebih penting adalah mengetahui di mana dan seberapa lambat kode berjalan
  • Dengan memanfaatkan flame graph, profiling, dan alat benchmarking, penghematan yang berarti bisa ditemukan bahkan pada fungsi berdurasi mikrodetik
  • Mengoptimalkan operasi yang sudah sangat singkat mungkin terlihat sepele, tetapi pada skala puluhan juta permintaan per detik, perbaikan kecil akan terakumulasi dan mengurangi total penggunaan komputasi

Bacaan terkait

1 komentar

 
GN⁺ 2024-09-11
Opini Hacker News

  • Kalau diminta menebak secara kasar bagaimana Cloudflare menyimpan dan menghapus header internal, saya mungkin akan membayangkan kamus atau struktur data terpisah, satu header tunggal yang memuat semua metadata internal, cara membedakan internal/eksternal dengan prefiks, atau prefiks seperti CFInt
    Saya mungkin tidak akan terpikir pendekatan yang menganggap nama header dalam daftar tertentu sebagai header internal. Muncul pertanyaan seperti apa yang terjadi jika orang lain memakai nama yang sama, apa yang terjadi jika ada yang terlewat saat pembersihan, apa yang terjadi jika program-program yang berjalan bersamaan punya daftar yang berbeda, apa yang terjadi jika header Connection menunjuk ke header internal Cloudflare, atau apa yang terjadi jika algoritma selisih himpunannya lambat
    Web sudah penuh dengan sinyal in-band dan penamaan header yang ambigu sampai menyebalkan, jadi terasa aneh bahwa perusahaan sebesar Cloudflare secara internal memakai mekanisme yang merepotkan dan mudah menimbulkan kesalahan seperti ini

    • Sebagai mantan karyawan, fakta yang menarik sekaligus menakutkan adalah bahwa di produk serverless seperti Workers, sebagian header internal bisa disetel, dan berbagai hal buruk bisa terjadi, seperti bug mencolok terkait cf-cache-status
    • Saya pernah bekerja di organisasi keamanan TI beberapa perusahaan besar, dan bahkan tempat-tempat yang cukup memperhatikan header pun menggunakan header dengan cara yang mirip Cloudflare
      Itu termasuk menghapus header internal dua arah di proxy edge, juga pada inbound
    • Menurut saya, banyak solusi alternatif yang diajukan punya masalah serupa. Bahkan sebagian masalah yang disebutkan sepertinya juga berlaku untuk solusi-solusi lain itu
      Pendekatan daftar punya kekurangan, tetapi juga banyak kelebihan. Saat menunjukkan potensi kelemahan pendekatan seperti ini, orang sering tampak mengabaikan sejarah dan kesulitan yang muncul pada skala Cloudflare. Daftar enumerasi adalah cara paling sederhana dan fleksibel, dan tidak memerlukan kesepakatan sebelumnya soal struktur kunci header. Mengingat jumlah tim di Cloudflare, kemungkinan akuisisi teknologi, dan sebagainya, poin ini kemungkinan penting
    • Saya juga berpikir begitu, tetapi sistemnya terus membesar seiring waktu dan header HTTP akhirnya dipakai untuk segala macam hal. Optimisasi ini membuat situasi lebih baik, tetapi solusi sebenarnya yang sedang dikerjakan adalah memakai mekanisme terpisah untuk IPC dan sepenuhnya menghapus penggunaan header HTTP
    • Ide lain adalah mewajibkan header internal yang tidak akan dikirim keluar hanya ditambahkan di bagian awal daftar header, atau mengisi lebih dulu tabel hash setiap request dengan header internal yang nantinya akan dihapus
      Jika diisi lebih dulu, pada dasarnya ini menggabungkan ide-ide tersebut sambil membuat jumlah header internal per request menjadi tetap. Pada titik itu, gunakan tabel hash tertaut yang mempertahankan urutan pembuatan, lalu cukup hapus N entri pertama dari daftar akhir yang akan dikirim kembali ke klien

  • Saya sempat memikirkan efek memetakan karakter UTF-8 ke bitmask, dan awalnya itu tidak terlihat terlalu pintar. Namun kemudian saya sadar bahwa 32 bit bisa memuat a-z dan 6 karakter khusus, sementara 64 bit bisa memuat huruf kapital A-Z dan 6 karakter khusus lagi
    Itu ruang yang cukup untuk header HTTP, dan karena cukup melakukan masking dan perbandingan pada beberapa integer, ini menjadi algoritma pencocokan yang sangat cepat. Karakter mana berkorespondensi dengan bit mana pun cukup dengan satu lookup tabel 256-word
    Hal yang terlewat oleh penulis adalah bahwa teknik ini secara teknis adalah Bloom filter. Hal seperti ini menarik karena, meski merupakan optimisasi dari masa ketika sumber daya komputasi jauh lebih terbatas daripada sekarang—dalam kasus ini dari tahun 1970—kita masih memakai optimisasi lama yang sama di sudut-sudut dunia nyata
    https://en.wikipedia.org/wiki/Bloom_filter

    • Ada perbedaan besar antara trie-hard dan Bloom filter. Bloom filter bersifat probabilistik dan menggunakan hashing. Ia bagus ketika kita bisa menerima false positive yang jarang terjadi asalkan tidak ada false negative, tetapi bukan itu yang dibutuhkan di sini. Di sini yang dibutuhkan adalah ketepatan, dan hashing itu sendiri adalah tahap yang harus dikalahkan
      Justru ini lebih mirip versi perbaikan atau variasi dari algoritma Liang yang dipakai di TeX untuk menyimpan kamus pemenggalan kata. Makalahnya membahas algoritma Bloom sebagai “superimposed coding”, dan sangat mengingatkan pada masa ketika memori adalah sumber daya paling berharga. Sepertinya Anda akan menyukainya ^_^
      https://tug.org/docs/liang/liang-thesis.pdf
    • Bloom filter berguna ketika dataset besar, dan biaya menghitung beberapa hash per item harus lebih murah daripada biaya mencari di dataset asli. Di sini bahkan satu hash disebut mahal, jadi Bloom filter akan jauh lebih lambat daripada hash map aslinya

  • Data yang disajikan untuk membuktikan manfaatnya sebenarnya tidak punya power uji yang cukup untuk menunjukkan hal itu. Sampelnya tidak memadai
    Analisis yang sangat sederhana di R adalah prop.test(c(9, 4), c(1103,1171)), dan pada uji kesamaan dua proporsi dengan koreksi kontinuitas, nilai p-nya 0,222
    Nilai p 0,22 tidak lebih rendah dari angka ajaib 0,05, dan interval kepercayaan 95% menunjukkan bahwa trie mungkin saja sebenarnya sedikit lebih buruk
    Dari analisis awal, trie tampaknya lebih baik dan ada bukti lemah, tetapi akan lebih baik mengambil sampel jauh lebih banyak agar yakin seberapa besar peningkatannya

  • Untuk tujuan menganalisis performa, menjelaskan jumlah perbandingan dengan notasi Big-O terasa janggal. Perbandingan kira-kira hanya 1 siklus, dan dengan instruction-level parallelism serta SIMD, beberapa perbandingan bahkan bisa dilakukan dalam satu siklus
    Bottleneck sebenarnya dan sumber kelambatan adalah memori. Mengakses memori memakan ribuan siklus, dan jika perlu TLB walk atau interrupt OS, bisa mencapai puluhan ribu atau ratusan ribu siklus. Kalau ingin memakai Big-O, seharusnya dipakai untuk memperkirakan jumlah cache miss
    Kalau saya, saya mungkin akan memakai fungsi perfect hash khusus dan trik popcount dari Phil Bagwell. Itu akan lebih cepat daripada solusi lain yang melakukan banyak lookup memori
    CPU cepat, memori lambat

  • Saya tidak terlalu paham optimasi struktur data, tetapi khususnya mengingat tabel yang menjadi target pencarian bersifat statis, cukup mengejutkan bahwa tabel hash disingkirkan terlalu cepat. Sulit dipercaya bahwa tabel hash yang dioptimalkan secara khusus tidak akan lebih cepat daripada implementasi trie mereka

    • Fungsi hash tidak bisa menolak string hanya dengan memeriksa satu byte pertama. Itu memang mustahil
      Untuk penggunaan ini, itulah keunggulan yang tidak bisa dikejar oleh hash. Teknik-teknik lainnya adalah soal memangkas faktor konstanta pada trie secukupnya agar keunggulan awal ini terbayar dalam performa nyata
    • Ada FxHashMap yang lebih cepat daripada std::collections::HashMap: https://github.com/rust-lang/rustc-hash
      Jika item statisnya sekitar 100, o1hash sepertinya juga bisa bekerja: https://github.com/rurban/smhasher/blob/master/o1hash.h
    • Artikel itu mengatakan overhead hashing membuatnya lebih lambat dibanding trie

  • Artikel ini membuat himpunan to_remove dengan struktur data yang keren, lalu mengiterasinya untuk menghapus dari header map dasar
    Pemanggilan remove_header tampaknya adalah kode ini: https://docs.rs/pingora-http/0.3.0/src/pingora_http/lib.rs.html#576
    Fungsi ini memanggil .remove() pada dua struktur data lain, dan keduanya pada akhirnya turun ke kode raksasa ini: https://docs.rs/http/latest/src/http/header/map.rs.html#1550

  • Akhirnya ada posting blog yang membahas trie. Soal-soal trie di LeetCode ternyata tidak sia-sia ;)

    • Pernah memakainya di kode nyata. Untuk beberapa penggunaan, cukup intuitif. Terakhir kali saya memakai trie adalah untuk lookup alamat, bahkan sampai memakai generator. Jadi di dunia nyata kena dua jurus LeetCode sekaligus
      Meski begitu, jelas bukan alat yang sering saya ambil
    • Pada pemeriksa ejaan atau pemeriksa tata bahasa yang cepat, trie bisa ditemukan
    • Baru-baru ini saya sempat memakai trie hibrida yang dimodifikasi di dunia nyata, dan implementasinya menyenangkan. Ruang untuk optimasi juga banyak
      Ini parser user agent untuk Go: https://github.com/medama-io/go-useragent
      Biasanya masalah seperti ini bergantung pada banyak parsing regex, jadi menyenangkan bisa mencoba pendekatan yang lebih baru
    • Pada build tool atau skrip analisis kode dengan kompleksitas menengah, kadang akhirnya memakai trie/radix tree. Ketika perlu menyimpan informasi tentang sangat banyak path file, memisahkan prefiks bersama bisa menghemat memori secara signifikan sekaligus tetap cukup intuitif
    • Dalam generator dan program permainan untuk membuat langkah Scrabble, trie sangat penting. Saya pernah membuat beberapa, dan struktur tercepat adalah trie terkompresi dengan representasi rotasi kata

  • Jika himpunan item yang akan dicocokkan bersifat statis, saya penasaran apakah mereka mencoba perfect hash table. Itu akan mereduksinya menjadi beberapa operasi aritmetika lalu satu perbandingan string, dan menarik untuk melihat perbandingannya dengan trie

    • Saya juga langsung memikirkan hal itu. Namun perfect hash pun karena fungsi hashnya tetap memiliki panjang kunci O(n), dan itulah bagian yang ingin mereka hindari
      Secara teori, kalau memakai regex, pencocokan dilakukan dengan state machine sehingga seharusnya memberi performa kasus terburuk O(k) yang mirip dengan trie. Namun setahu saya library regex memakai backtracking alih-alih benar-benar membangun state machine, sehingga performanya tidak lagi O(k)
      Agak mengejutkan bahwa mereka tidak menemukan library regex berbasis state machine yang sudah ada dan berkinerja bagus. Seharusnya performanya mirip trie, tetapi dalam praktiknya faktor seperti pola akses memori atau performa operasi aritmetika tertentu berpengaruh lebih dalam, jadi memang sulit ditebak

  • Apakah mereka mencoba Bloom filter yang sangat kecil? Jika kunci header diproses cepat seperti konvolusi dan dicocokkan dengan Bloom filter, sepertinya dalam kebanyakan kasus traversal trie bisa sepenuhnya dihindari hanya dengan biaya beberapa siklus
    Opsi seperti SIMD, instruksi CRC bawaan, dan ukuran Bloom filter 256-bit juga tampak mungkin

    • Entah tim itu melakukannya atau tidak, tetapi Bloom filter bukan obat mujarab: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/
    • Mengingat dalam implementasi trie mereka filter di tiap node sudah mirip Bloom filter, solusinya cukup dekat. Saya setuju bahwa memeriksa bagian string yang lebih lebar sekaligus bisa memberi akselerasi dramatis
      Pendekatan yang lebih sederhana juga bisa bernilai. Jika menganalisis frekuensi hit/gagal pada node trie, mungkin bisa ditemukan posisi karakter tertentu yang tingkat gagalnya lebih tinggi daripada karakter pertama. Memeriksa posisi khusus seperti itu terlebih dahulu bisa membuatnya lebih cepat. Tentu saja ini membutuhkan asumsi bahwa data header pada dasarnya cukup teratur
    • Itu tampaknya membutuhkan perhitungan hash, dan biaya itu sepertinya sudah disingkirkan karena terlalu lambat

  • Menurut saya begini. Pertama, apakah ini hal yang layak dilakukan? Kelihatannya mereka menghemat sekitar 500 core CPU, tetapi saya tidak tahu apakah itu core fisik atau termasuk core hyperthread
    Saya tidak tahu biaya Cloudflare, tetapi itu setara dengan jumlah server satu digit, dan penghematannya mungkin hanya puluhan ribu dolar per tahun. Bukan jumlah yang bisa diabaikan, tetapi saya tidak tahu apakah bisa mengharapkan ROI positif dibandingkan investasi engineering-nya
    Kedua, kalau memang akan masuk sedetail ini, saya penasaran apakah mereka mempertimbangkan memasang filter pada tahap deserialisasi agar header tidak dibuat sejak awal

    • Mungkin memang hanya puluhan ribu dolar, tetapi penghematan itu bersifat permanen
      Penghematan listrik juga terus berlangsung, dan emisi karbon juga berkurang
      Saya senang melihat perusahaan yang mencoba membuat sesuatu 1% lebih cepat, ketimbang melakukan hal bodoh seperti menganalisis header dengan AI demi menjual sandal
    • Ini kasus pinggiran yang sangat kecil, tetapi juga sesuatu yang mudah dipublikasikan. Ini menjadi konten marketing yang membuat ratusan geek berdiskusi tentang apakah yang dilakukan Cloudflare masuk akal dan seberapa besar mereka peduli pada performa
      Nilainya bisa saja satu juta dolar
    • Saya kurang paham inti soal ROI. Kalau menghemat 40 ribu dolar per tahun selama 5 tahun, itu 200 ribu dolar. Untuk standar Hungaria atau Polandia, itu gaji beberapa engineer selama beberapa tahun. Saya tidak tahu apakah Cloudflare punya kantor di sana
    • Kalau seorang engineer hanya menghabiskan beberapa hari, bukankah penghematannya terlihat cukup sepadan?