Trie-hard’ın iyi günü: hesaplamada %1 tasarruf

Motivasyon

• Cloudflare’ın küresel ağı saniyede 60 milyondan fazla HTTP isteğini işler
• Yeni bir açık kaynak Rust crate’i kullanarak CPU kullanımını azalttı ve CDN’in işleme kapasitesini artırdı
• Pingora, Cloudflare’ın Rust tabanlı proxy hizmetinin çekirdeğidir ve açık kaynak olarak yayımlandı
• Pingora-origin hizmeti, kullanıcı isteklerini gerçek hedefe iletme görevini üstlenir
• İstek Cloudflare’dan ayrılırken iç bilgilerin kaldırılması gerekir
• Bu işlem çok sık gerçekleşir ve CPU kullanımının %1,7’sini oluşturur

Kıyaslama

• Criterion Rust crate’i kullanılarak fonksiyon performansı nanosaniye düzeyinde ölçüldü
• Orijinal clear_internal_headers fonksiyonu ortalama 3.65µs sürüyordu

Okuma işlemlerini azaltma

• Okuma işlemlerini azaltmak için header kaldırma yönü tersine çevrildi
• Bu değişiklikle fonksiyonun çalışma süresi 3.65µs’den 1.53µs’ye iyileşti
• CPU kullanımı %1,71’den %0,717’ye düştü

Veri yapısı araması

• Dahili header’ları depolamak ve aramak için hash map kullanımı denendi
• Hash map’in okuma süresi, anahtar uzunluğuyla orantılı olarak doğrusaldır
• Sıralı küme veya durum makinesi gibi başka veri yapıları da denendi
• Düzenli ifade kullanan uygulama, hash map’ten iki kat daha yavaştı

Trie kullanımı

• Trie, önek arama veya otomatik tamamlama sistemlerinde kullanılan bir ağaç veri yapısıdır
• Trie, bir dizenin bulunmadığı durumları hızlıca belirleyebilir
• Mevcut trie uygulamaları hash map’ten daha yavaştı
• Cloudflare, trie-hard adlı kendi optimize trie uygulamasını geliştirdi

Trie Hard

• trie-hard, düğüm ilişkilerini tamsayı bitlerinde saklayıp belleği kesintisiz kullanarak hızı artırır
• clear_internal_headers fonksiyonunun çalışma süresini 0.93µs’ye düşürdü
• CPU kullanımını %1,71’den %0,43’e indirdi
• Gerçek üretim ortamında trie-hard performansı benchmark sonuçlarıyla örtüştü

Sonuç

• Koddaki yavaş bölümleri belirleyip optimize etmek önemlidir
• Küçük optimizasyonlar birikerek büyük performans artışları sağlayabilir
• Cloudflare’ın bağlantı bulutu, ağ koruması, internet uygulamalarını hızlandırma ve DDoS saldırılarına karşı savunma gibi işlevler sunar

GN⁺ özeti

• Cloudflare, Rust tabanlı yeni bir açık kaynak crate ile CPU kullanımını azaltıp CDN’in işleme kapasitesini artırdı
• Pingora-origin hizmetindeki dahili header kaldırma işlemini optimize ederek CPU kullanımını %1,28 azalttı
• trie-hard adlı kendi optimize trie uygulamasını geliştirerek performansı ciddi biçimde iyileştirdi
• Bu yazı, kod optimizasyonu ve veri yapısı seçiminin önemini vurgularken küçük optimizasyonların büyük performans kazanımları getirebileceğini gösteriyor
• Benzer işlevlere sahip projeler arasında NGINX ve HAProxy bulunuyor

[GN⁺]

Hacker News görüşleri

• Cloudflare'ın iç başlıkları saklama ve kaldırma yöntemi hakkında çeşitli tahminler yapılmış

  • ayrı bir sözlük ya da veri yapısı kullanılması
  • tüm iç meta veriyi içeren tek bir başlık
  • tüm başlıklara önek eklenmesi; iç olanların I, dış olanların E ile başlaması
  • tüm iç başlıkların CFInt ile başlaması
  • belirli bir listedeki başlıkların iç başlık sayılması yaklaşımı beklenmiyormuş
  • web zaten belirsiz sinyaller ve başlık adlarıyla dolu
  • Cloudflare gibi büyük ölçekli bir şirketin hataya açık böyle bir mekanizma kullanması tuhaf bulunmuş

• UTF-8 karakterlerini bit maskesine eşleme fikri ilk başta verimsiz görünmüş

  • 32 bit ile a-z ve altı özel karakter kapsanabiliyor
  • 64 bit ile büyük harf A-Z ve altı özel karakter kapsanabiliyor
  • HTTP başlıkları için yeterli alan sağlıyor ve hızlı eşleştirme algoritmalarını mümkün kılıyor
  • bu teknik bir Bloom Filter
  • 1970'lerde kaynakların kısıtlı olduğu bir dönemde geliştirilmiş olsa da hâlâ faydalı biçimde kullanılıyor

• Cloudflare'ın optimizasyonunun gerçekten değerli olup olmadığı sorgulanmış

  • yaklaşık 500 CPU çekirdeği tasarruf edilmiş
  • Cloudflare'ın maliyeti bilinmese de bunun on binlerce dolarlık bir tasarruf olduğu tahmin ediliyor
  • mühendislik açısından olumlu bir ROI beklenip beklenemeyeceği sorgulanmış
  • filtrenin ters serileştirme aşamasında uygulanarak başlıkların hiç oluşturulmamasının daha iyi olabileceği söylenmiş

• Veri yapısı optimizasyonları konusunda çok bilgili olunmasa da hash tablosunun bu kadar hızlı elenmesi şaşırtıcı bulunmuş

  • statik bir tabloda arama yaparken hash tablosunun daha hızlı olacağı düşünülmüş

• Kaldırılacak öğeleri düzenlemek için süslü bir veri yapısı kullanılıp buna göre başlık haritasından silme yapılıyor

  • remove_header çağrısının geçtiği kod bağlantısı paylaşılmış

• Nihayet trie kullanan bir blog yazısı çıkmış

  • trie ile ilgili sorunlarla uğraşmak boşa gitmemiş

• Küçük bir Bloom Filter denenip denenmediği merak edilmiş

  • başlık anahtarları üzerinde hızlı bir convolution ve Bloom Filter testi, trie üzerinde yürümeyi önleyebilir

• Statik bir öğe kümesini eşleştirirken perfect hash table denenip denenmediği merak edilmiş

  • birkaç aritmetik işlem ve tek bir string karşılaştırmasına indirgenebilir

• Optimizasyon ilgi çekici bulunmuş

  • isteğin oluşturulması sırasında başlıkların iç olarak etiketlenmesinin mümkün olup olmadığı merak edilmiş
  • böylece çıktı aşamasında filtreleme daha basit olurdu

• regex crate'inin neden daha iyi çalışmadığı merak edilmiş

  • birden fazla literal string aramasını Aho-Corasick otomatına derlemesi gerekirdi