Trie-hard için güzel bir gün: işlem gücünde %1 tasarruf
(blog.cloudflare.com)- Cloudflare, saniyede ortalama 60 milyondan fazla HTTP isteği işleyen ağında Rust tabanlı proxy Pingora’nın CPU kullanımını azaltmak için açık kaynak Rust crate’i trie-hard’ı yayımladı
- Darboğaz,
pingora-originiçindekiclear_internal_headersfonksiyonuydu; Cloudflare’dan ayrılan önbelleğe alınmamış isteklerde dahili yönlendirme, ölçüm ve optimizasyon için kullanılan başlıkları kaldırıyor ve saniyede 35 milyon istek yolunda çalışıyordu - Mevcut uygulama, her istekte 100’den fazla dahili başlığı kaldırmayı deniyor, ortalama 3.65µs sürüyor ve
pingora-origin’in toplam CPU süresinin %1,71’ini, yani 40 bin compute-second/s içinde 680 CPU çekirdeğine denk bir miktarı tüketiyordu - Önce gerçek istek başlıklarını dolaşan yöntem ortalama 1.53µs ile 2,39 kat hızlandı; ancak toplam CPU tasarrufu teorik olarak %0,993’te kaldığından daha iyi bir arama yapısına ihtiyaç vardı
- Yeni trie uygulaması ortalama çalışma süresini 0.93µs’ye düşürdü; Temmuz 2024’ten beri üretimde çalışan örneklemede de
clear_internal_headers’ın gerçek CPU kullanımı %0,34’e kadar indi
Cloudflare’ın azaltmaya çalıştığı maliyet
- Cloudflare’ın küresel ağı saniyede ortalama 60 milyondan fazla HTTP isteği işler
- Bu optimizasyon, Rust tabanlı proxy hizmetinin çekirdeği olan Pingora ve onun üzerinde çalışan üretim hizmeti
pingora-originile başladı pingora-origin, kullanıcının önbelleğe alınmamış isteklerini gerçek hedef sunucu olan origin’e gönderen son aşamadan sorumludur- Bu hizmet, istek Cloudflare altyapısından ayrılmadan önce dahili yönlendirme, ölçüm ve optimizasyon için kullanılan bilgileri başlıklardan kaldırmak zorundadır
- Dünya genelinde
pingora-origin’den ayrılan istek sayısı, yazının kaleme alındığı sırada saniyede 35 milyondur
Darboğaz fonksiyon: clear_internal_headers
- Söz konusu fonksiyon, tüm isteklerde çalışan son derece sıcak bir yoldadır
// 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);
});
}
- Bu küçük fonksiyon tek başına
pingora-origin’in toplam CPU süresinin %1,7’den fazlasını kullanır pingora-origin’in toplam CPU süresi saniyede 40.000 compute-second’dır; bu, doygun 40 bin CPU çekirdeğinin yalnızca bu hizmeti çalıştırmasına denk bir ölçektir- Bunun %1,7’si, yani yaklaşık 680 CPU çekirdeği, yalnızca
clear_internal_headersdeğerlendirmesi için harcanıyor demektir
Temel ölçüm ve ilk iyileştirme
- Performans ölçümü için Rust crate’i criterion kullanıldı
- Criterion, birden fazla yalıtılmış çalıştırmayı birleştirerek Rust kodunun süresini nanosaniye düzeyinde ölçer ve zaman içindeki performans iyileşmesi/gerilemesi hakkında geri bildirim de sağlar
- Benchmark girdisi, dahili başlıklar ile dahili olmayan başlıkların eşit dağılacağı şekilde sentezlenmiş büyük bir istek kümesidir
- Mevcut
clear_internal_headers’ın ortalama çalışma süresi 3.65µs olarak ölçüldü -
Arama yönünü tersine çevirmek
- Mevcut kod, dahili başlık listesindeki her öğe için
request_header.remove_header(h)çalıştırdığından, dahili başlık sayısı 100’den fazlaysa her istekte 100’den fazla değerlendirme yapar - Ortalama bir istekteki başlık sayısı 100’den çok daha az, 10–30 seviyesinde olduğundan, gerçek istek başlıklarını dolaşıp dahili başlık kümesinde aramak okuma sayısını azaltır
- Rust’ın
http::HeaderMapyapısında henüzretainolmadığı için, kaldırılacak dahili başlıkları ayrı bir adımda topladıktan sonra silmek gerekir - Yalnızca bu değişiklikle ortalama çalışma süresi 3.65µs’den 1.53µs’ye düşerek 2,39 kat hızlandı
- Teorik olarak toplam CPU kullanımı %1,71’den %0,717’ye iner; tasarruf %0,993 olur
- Mevcut kod, dahili başlık listesindeki her öğe için
Daha iyi bir arama veri yapısı arayışı
- Arama yönü değiştirildikten sonra, statik dahili başlık listesinin hangi veri yapısında saklanacağı seçilebilir hale geldi
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);
});
}
- İlk deneme
std::HashMapoldu; ancak string anahtarlarının hash’i tüm baytları okumak zorunda olduğundan, tablo boyutuna göre sabit zamanlı olsa bile anahtar uzunluğu L açısından doğrusal zamanlı hale gelir - Amaç, anahtar uzunluğuna göre O(L)’den daha iyi okuma davranışı gösteren bir veri yapısı bulmaktı
-
İncelenen alternatifler
BTreeSetgibi sıralı kümeler karşılaştırmaya dayalı arama kullanarak anahtar uzunluğu açısından O(log(L)) davranış sağlar; ancak küme boyutu açısından da logaritmik zaman alır- Hızlı bir sıralı küme olan FST de benchmark’ta standart hash map’ten yaklaşık 50ns daha yavaştı
- Parser veya regex gibi durum makineleri girdiyi birim birim alır ve her adımda değerlendirmeye devam edilip edilmeyeceğine karar verdiğinden, eşleşmeyen string’leri hızlıca tanımlayabilir
- İstek başına ortalama yalnızca 1–2 dahili başlık olduğundan, olumsuz örneklerin çoğunlukta olduğu bu duruma iyi uyar
- Regex kullanan
clear_internal_headersuygulaması, hash map tabanlı çözüme göre yaklaşık 2 kat daha uzun sürdü; ancak ham hızıyla bilinen bir araç olmadığı düşünülürse hızlı bir sonuçtu
trie neden uygun?
- trie, bilinen string kümelerinde önek arama veya otomatik tamamlama için sık kullanılan bir ağaç veri yapısı)dır
- trie’nin her düğümü, başlangıçtaki string kümesinde bulunan bir alt string’i temsil eder; düğümler arasındaki bağlantılar ise belirli bir önekten sonra gelebilecek karakterleri temsil eder
- Kök düğümden başlayıp olası ilk harflerden arama alanını daraltabildiği için, dahil olmayan string’leri hızla eleyebilir
- trie okuması, eşleşmeyen durumlar için O(log(L)) davranış sağlar; ancak eşleşen durumlar hâlâ O(L)’dir
- İstek başlıklarının %90’dan fazlası dahili başlık olmadığından, eşleşmeyen durumların çok olduğu bu kullanım senaryosuna uygundur
-
Mevcut trie uygulamalarının sınırları
- crates.io üzerindeki çeşitli trie uygulamaları benchmark edildi, ancak sonuçlar beklentileri karşılamadı
- Çoğu trie, klavye olaylarına yanıt veren otomatik tamamlama gibi kullanım senaryolarına yönelik olduğundan, saniyede on milyonlarca isteğin geçtiği sıcak yolu optimize etmek öncelikleri değildir
- Bulunan en hızlı mevcut uygulama radix_trie oldu; ancak yine de hash map’ten 1µs daha yavaştı
- Sonunda bu kullanım senaryosuna özel yeni bir trie uygulaması yazıldı
trie-hard ve üretim sonuçları
-
Cloudflare yeni açık kaynak Rust crate’i trie-hard’ı yayımladı
-
trie-hard, düğüm ilişkilerini işaretsiz tamsayıların bitlerinde saklar ve hızı artırmak için tüm ağacı bitişik bir bellek bloğunda tutar -
Benchmark’ta
trie-hard,clear_internal_headers’ın ortalama çalışma süresini 0.93µs’ye düşürdü -
Beklenen CPU kullanımı %0,43’tür; bu da mevcut %1,71’e kıyasla toplam
pingora-originişlem kullanımını %1,28 azaltan bir sonuçtur -
Gerçek örnekleme sonuçları
trie-hard, Temmuz 2024’ten beri üretimde çalışıyor- Performans ölçümü, zaman içinde yığın izi istatistiklerinin örneklenmesiyle toplandı
- Belirli bir fonksiyonun yer aldığı örnek oranıyla, o fonksiyonun CPU kullanımı tahmin edilir
- Üretim örnekleme sonuçları, yerel benchmark tahminlerine genel olarak yakındır
Uygulama clear_internal_headersiçeren yığın izi örneğiGerçek CPU kullanımı Tahmini CPU kullanımı Original 19 / 1111 %1,71 n/a Hashmap 9 / 1103 %0,82 %0,72 trie-hard 4 / 1171 %0,34 %0,43
Operasyonel açıdan sonuç
- Yeni bir veri yapısı yazmadan önce, kodun nerede ve ne kadar yavaş olduğunu bilmek gerekir
- flame graph, profil çıkarma ve benchmark araçları kullanıldığında mikrosaniye düzeyindeki fonksiyonlarda bile anlamlı tasarruflar bulunabilir
- Zaten çok kısa olan işlemleri optimize etmek önemsiz görünebilir; ancak saniyede on milyonlarca istek ölçeğinde küçük iyileştirmeler birikerek toplam işlem kullanımını azaltır
1 yorum
Hacker News yorumları
Cloudflare’ın iç başlıkları nasıl saklayıp kaldırdığını kabaca tahmin etmem istenseydi, ayrı bir sözlük ya da veri yapısı, tüm iç metaveriyi tutan tek bir başlık, iç/dış ayrımını önekle yapma ya da
CFIntgibi bir önek aklıma gelirdi.Belirli bir listedeki başlık adlarını iç başlık sayma yöntemini düşünemezdim. Başka biri aynı adı kullanırsa ne olur, temizleme atlanırsa ne olur, aynı anda çalışan programların listeleri birbirinden farklıysa ne olur,
Connectionbaşlığı Cloudflare iç başlığını işaret ederse ne olur, küme farkı algoritması yavaşsa ne olur gibi sorular doğuyor.Web zaten rahatsız edici derecede muğlak in-band sinyaller ve başlık adlandırmalarıyla doluyken, Cloudflare ölçeğinde bir şirketin içeride bu kadar zahmetli ve hataya açık bir mekanizma kullanması tuhaf geliyor.
cf-cache-statusile ilgili göze çarpan hata gibi her tür kötü şey yaşanabiliyordu.Buna edge proxy’de iç başlıkların iki yönde de kaldırılması dahildi; inbound tarafta da böyle yapılıyordu.
Liste yönteminin dezavantajları var ama avantajları da çok. Bu yaklaşımın olası kusurlarına işaret ederken Cloudflare ölçeğinde oluşan geçmiş ve zorluklar çoğu zaman göz ardı ediliyor gibi görünüyor. Enum liste en basit ve esnek yöntem; başlık anahtarı yapısı üzerinde önceden mutabakat da gerektirmiyor. Cloudflare’daki ekip sayısını, teknoloji satın alma olasılıklarını vb. düşününce bu nokta önemli olmuş olmalı.
Önceden doldurunca bu fikirleri fiilen birleştirmiş ve her istekteki iç başlık sayısını sabitlemiş olursun. O noktada oluşturma sırasını koruyan bir bağlantılı hash tablosu kullanıp, istemciye geri gönderilecek nihai listeden yalnızca ilk N öğeyi kaldırmak yeterli olur.
UTF-8 karakterlerini bit maskesiyle eşlemenin etkisini kısa bir süre düşündüm; başta pek akıllıca görünmedi. Sonra 32 bit ile
a-zve 6 özel karakterin, 64 bit ile de büyük harfA-Zve 6 özel karakterin daha sığabileceğini fark ettim.HTTP başlıkları için yeterli alan var; birkaç tamsayıyı maskeleyip karşılaştırmak çok hızlı bir eşleştirme algoritması yapar. Hangi karakterin hangi bite karşılık geldiği de 256 kelimelik bir tabloda tek bir aramayla bulunabilir.
Yazarın kaçırdığı nokta, bu tekniğin teknik olarak bir Bloom filtresi olması. Bunların ilginç olmasının nedeni, hesaplama kaynaklarının bugünkünden çok daha kısıtlı olduğu dönemden, bu örnekte 1970’ten kalma bir optimizasyon olmasına rağmen, gerçek dünyanın köşelerinde hâlâ aynı eski optimizasyonların kullanılması.
https://en.wikipedia.org/wiki/Bloom_filter
trie-hardile Bloom filtresi arasında büyük fark var. Bloom filtresi olasılıksaldır ve hashing kullanır. Nadir false positive’lere izin verip false negative olmaması gerektiğinde iyidir; ama burada gereken bu değil. Burada doğruluk gerekiyor ve hashing’in kendisi aşılması gereken bir aşama.Bu daha çok TeX’te tireleme sözlüğünü saklamak için kullanılan Liang algoritmasının geliştirilmiş ya da değiştirilmiş bir sürümüne yakın. Makale Bloom’un algoritmasını “superimposed coding” olarak ele alıyor; belleğin en değerli kaynak olduğu dönemleri güçlü biçimde hatırlatıyor. Hoşuna gidebilir ^_^
https://tug.org/docs/liang/liang-thesis.pdf
Kazancı kanıtlamak için sunulan verilerin bunu gerçekten göstermeye istatistiksel gücü yetmiyor. Örneklem yeterli değil.
R’de çok basit bir analiz
prop.test(c(9, 4), c(1103,1171)); süreklilik düzeltmesi uygulanmış iki oranın eşitliği testinde p-değeri 0,222 çıkıyor.0,22’lik p-değeri sihirli 0,05’in altında değil ve %95 güven aralığı trie’ın aslında biraz daha kötü olabileceğini ima ediyor.
Ön analiz trie’ın daha iyi olabileceğini gösteriyor ve zayıf kanıt da var; ancak ne kadar daha iyi olduğundan emin olmak için çok daha fazla örnek almak daha iyi olur.
Performansı analiz etme hedefi açısından karşılaştırma sayısını Big O gösterimiyle açıklamak garip. Karşılaştırma yaklaşık 1 çevrimlik bir iş ve instruction-level parallelism ile SIMD sayesinde bir çevrimde birkaç tane bile yapılabilir.
Asıl darboğaz ve yavaşlığın kaynağı bellek. Belleğe erişmek binlerce çevrim sürebilir; TLB walk ya da OS interrupt gerekirse on binlerce, hatta yüz binlerce çevrime kadar çıkabilir. Big O kullanmak istiyorsan bunu cache miss sayısını tahmin etmek için kullanmalısın.
Ben olsam özel bir perfect hash fonksiyonu ve Phil Bagwell’in
popcountnumarasını kullanırdım. Belleğe birden çok kez bakan diğer çözümlerden daha hızlı olur.CPU hızlı, bellek yavaş.
Veri yapısı optimizasyonunda çok uzman değilim ama özellikle arama yapılacak tablonun statik olduğu düşünülürse hash table’ı bu kadar erken elemeleri şaşırtıcıydı. Özel olarak optimize edilmiş bir hash table’ın onların trie uygulamasından daha hızlı olmayacağına inanmak zor
Bu kullanımda hash’in yetişemediği avantaj da bu. Geri kalan teknikler, trie’ın sabit katsayılarını yeterince düşürüp bu başlangıç avantajının gerçek performansta karşılık bulmasını sağlamakla ilgili
std::collections::HashMap’ten daha hızlı FxHashMap var: https://github.com/rust-lang/rustc-hashStatik öğe sayısı yaklaşık 100 ise o1hash de çalışabilir gibi: https://github.com/rurban/smhasher/blob/master/o1hash.h
Bu yazı, şık bir veri yapısıyla
to_removekümesini oluşturuyor, sonra bunun üzerinden geçip temel header map’ten siliyorremove_headerçağrısı şu kod gibi görünüyor: https://docs.rs/pingora-http/0.3.0/src/pingora_http/lib.rs.html#576Bu fonksiyon iki başka veri yapısında
.remove()çağırıyor ve ikisi de sonunda şu devasa koda iniyor: https://docs.rs/http/latest/src/http/header/map.rs.html#1550Sonunda trie geçen bir blog yazısı çıktı. Trie LeetCode problemleri boşa gitmemiş ;)
Yine de sıkça elime aldığım bir araç olduğu kesinlikle söylenemez
Go için bir user agent parser: https://github.com/medama-io/go-useragent
Normalde bu tür problemler çok sayıda regex parsing’e dayanır; bu yüzden daha yeni bir yaklaşım deneyebilmek güzeldi
Eşleştirilecek öğe kümesi statikse perfect hash table denemişler mi merak ediyorum. Birkaç aritmetik işlemden sonra tek bir string karşılaştırmasına inerdi; trie ile nasıl kıyaslanacağı ilginç olurdu
Teoride regex kullanırsanız eşleştirme bir durum makinesiyle yapıldığı için trie’a benzer şekilde en kötü durumda O(k) performans vermesi gerekir. Ama anladığım kadarıyla regex kütüphaneleri gerçek durum makinesi üretmek yerine backtracking kullanıyor, bu yüzden performans artık O(k) olmuyor
Zaten var olan, performanslı, durum makinesi tabanlı bir regex kütüphanesi bulamamış olmaları şaşırtıcı. Trie’a benzer performansta olması gerekirdi; gerçekteyse bellek erişim örüntüleri veya belirli aritmetik işlemlerin performansı gibi etkenler daha derinden etkilediği için tahmin etmek zor
Çok küçük bir Bloom filter denediler mi acaba? Header anahtarını hızlıca konvolüsyon benzeri şekilde işleyip Bloom filter ile karşılaştırırsanız, birkaç cycle maliyetle çoğu durumda trie dolaşımını tamamen atlayabilecekmişsiniz gibi geliyor
SIMD, yerleşik CRC komutları, 256 bit Bloom filter boyutu gibi seçenekler de var gibi görünüyor
Daha basit bir yaklaşım da değerli olabilir. Trie düğümlerinin isabet/başarısızlık sıklığı analiz edilirse, ilk karakterden daha yüksek başarısızlık oranına sahip belirli karakter konumları bulunabilir. Bu özel konumları önce kontrol etmek daha hızlı olabilir. Elbette bunun için header verisinin doğası gereği oldukça düzenli olduğu varsayımı gerekir
Benim düşüncem şu. Birincisi, bu yapılmaya değer bir iş mi? Yaklaşık 500 CPU çekirdeği tasarruf edilmiş gibi görünüyor; bunun gerçek çekirdekler mi yoksa hyper-thread çekirdekleri de dahil mi olduğunu bilmiyorum
Cloudflare’in maliyetlerini bilmiyorum ama bu, tek haneli sayıda sunucuya denk geliyor ve tasarruf da muhtemelen yılda on binlerce dolar düzeyindedir. Göz ardı edilecek bir miktar değil, ama mühendislik yatırımı karşılığında pozitif ROI beklenip beklenemeyeceğinden emin değilim
İkincisi, bu kadar ayrıntıya ineceklerse, header’ların en başta oluşturulmaması için deserialization aşamasına bir filtre koyma seçeneğini değerlendirip değerlendirmediklerini merak ediyorum
Güç tasarrufu da sürer, karbon emisyonu da azalır
Header’ları yapay zekayla analiz edip sandalet satmaya çalışmak gibi aptalca şeylerdense, bir şeyi %1 daha hızlı yapmaya çalışan bir şirket görmek hoşuma gidiyor
Bunun değeri bir milyon dolar olabilir