Hari Baik bagi Trie-Hard: Menghemat 1% Komputasi

Motivasi

• Jaringan global Cloudflare menangani lebih dari 60 juta permintaan HTTP per detik
• Mengurangi penggunaan CPU dan meningkatkan kapasitas pemrosesan CDN dengan menggunakan crate Rust open source baru
• Pingora adalah inti dari layanan proksi berbasis Rust milik Cloudflare, dan telah dirilis sebagai open source
• Layanan Pingora-origin berperan meneruskan permintaan pengguna ke tujuan sebenarnya
• Saat permintaan meninggalkan Cloudflare, diperlukan proses untuk menghapus informasi internal
• Proses ini terjadi sangat sering dan menyumbang 1,7% dari penggunaan CPU

Benchmarking

• Menggunakan crate Rust Criterion untuk mengukur performa fungsi dalam satuan nanodetik
• Fungsi clear_internal_headers awalnya memerlukan rata-rata 3.65µs

Mengurangi operasi baca

• Mengurangi operasi baca dengan membalik arah penghapusan header
• Perubahan ini meningkatkan waktu eksekusi fungsi dari 3.65µs menjadi 1.53µs
• Menurunkan penggunaan CPU dari 1,71% menjadi 0,717%

Pencarian struktur data

• Mencoba metode menyimpan dan mencari header internal menggunakan hash map
• Waktu baca hash map bersifat linear, sebanding dengan panjang key
• Mencoba struktur data lain seperti sorted set atau state machine
• Implementasi yang menggunakan regular expression dua kali lebih lambat daripada hash map

Menggunakan trie

• Trie adalah struktur data pohon yang digunakan untuk pencarian prefiks atau sistem autocomplete
• Trie dapat dengan cepat mengidentifikasi kasus ketika sebuah string tidak termasuk
• Implementasi trie yang sudah ada lebih lambat daripada hash map
• Cloudflare mengembangkan implementasi trie hasil optimasi mereka sendiri, yaitu trie-hard

Trie Hard

• trie-hard menyimpan relasi antar node dalam bit-bit integer dan menggunakan memori secara kontigu untuk meningkatkan kecepatan
• Menurunkan waktu eksekusi fungsi clear_internal_headers menjadi 0.93µs
• Menurunkan penggunaan CPU dari 1,71% menjadi 0,43%
• Di lingkungan produksi nyata, performa trie-hard sesuai dengan hasil benchmark

Kesimpulan

• Penting untuk mengidentifikasi dan mengoptimalkan bagian kode yang lambat
• Optimasi kecil yang terakumulasi dapat menghasilkan peningkatan performa yang besar
• Cloudflare's connectivity cloud menyediakan fungsi seperti perlindungan jaringan, akselerasi aplikasi internet, dan pertahanan terhadap serangan DDoS

Ringkasan GN⁺

• Cloudflare mengurangi penggunaan CPU dan meningkatkan kapasitas pemrosesan CDN melalui crate open source baru berbasis Rust
• Dengan mengoptimalkan proses penghapusan header internal pada layanan Pingora-origin, penggunaan CPU berkurang 1,28%
• Dengan mengembangkan implementasi trie hasil optimasi mereka sendiri bernama trie-hard, performa meningkat secara signifikan
• Artikel ini menekankan pentingnya optimasi kode dan pemilihan struktur data, serta menunjukkan bahwa optimasi kecil dapat menghasilkan peningkatan performa yang besar
• Proyek dengan fungsi serupa antara lain NGINX dan HAProxy

[GN⁺]

Opini Hacker News

• Ada berbagai spekulasi tentang cara Cloudflare menyimpan dan menghapus header internal

  • menggunakan kamus atau struktur data terpisah
  • satu header tunggal yang mencakup semua metadata internal
  • semua header diberi prefiks, internal diawali dengan 'I' dan eksternal dengan 'E'
  • semua header internal diawali dengan "CFInt"
  • tidak menyangka bahwa pendekatannya adalah daftar header tertentu dianggap sebagai header internal
  • web sudah penuh dengan sinyal ambigu dan penamaan header yang membingungkan
  • terasa aneh bahwa perusahaan sebesar Cloudflare menggunakan mekanisme yang mudah menimbulkan kesalahan seperti ini

• Awalnya mengira pemetaan karakter UTF-8 ke bitmask tidak efisien

  • 32 bit bisa memuat a-z dan enam karakter khusus
  • 64 bit bisa memuat huruf besar A-Z dan enam karakter khusus
  • memberi ruang yang cukup untuk header HTTP dan memungkinkan algoritme pencocokan yang cepat
  • teknik ini adalah Bloom Filter
  • ini adalah teknik yang dikembangkan pada era 1970-an saat sumber daya terbatas, tetapi masih tetap berguna sampai sekarang

• Ada pertanyaan apakah optimisasi Cloudflare ini benar-benar sepadan

  • menghemat sekitar 500 core CPU
  • tidak tahu biaya Cloudflare, tetapi diperkirakan penghematannya sekitar puluhan ribu dolar
  • meragukan apakah ROI untuk upaya engineering-nya bisa positif
  • mungkin lebih baik menerapkan filter pada tahap deserialisasi agar header tidak dibuat sejak awal

• Tidak terlalu paham optimisasi struktur data, tetapi terkejut karena hash table langsung dikesampingkan

  • mengira hash table akan lebih cepat saat mencari pada tabel statis

• Menggunakan struktur data fancy untuk menyusun item yang akan dihapus lalu menghapusnya dari header map berdasarkan itu

  • memberikan tautan kode terkait pemanggilan remove_header

• Akhirnya muncul juga postingan blog yang menggunakan trie

  • soal-soal terkait trie ternyata tidak sia-sia

• Penasaran apakah mereka mencoba Bloom Filter kecil

  • konvolusi cepat pada kunci header dan pengujian Bloom Filter bisa menghindari kebutuhan menelusuri trie

• Penasaran apakah mereka mencoba perfect hash table untuk kasus pencocokan himpunan item statis

  • bisa dipersempit menjadi beberapa operasi aritmetika dan satu perbandingan string

• Optimalisasinya menarik

  • penasaran apakah header bisa ditandai sebagai internal saat request dibuat
  • filtering saat output akan menjadi lebih sederhana

• Penasaran mengapa crate regex tidak bekerja lebih baik

  • seharusnya pencarian banyak string literal bisa dikompilasi menjadi automaton Aho-Corasick