trie-hard का अच्छा दिन: compute में 1% की बचत

 (blog.cloudflare.com)
2 पॉइंट द्वारा GN⁺ 2024-09-11 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Cloudflare ने प्रति सेकंड औसतन 6 करोड़ से अधिक HTTP requests संभालने वाले नेटवर्क में Rust-आधारित proxy Pingora का CPU उपयोग घटाने के लिए open source Rust crate trie-hard जारी किया
  • bottleneck pingora-origin का clear_internal_headers function था, जो Cloudflare से बाहर जाने वाली non-cache requests में internal routing, measurement और optimization के headers हटाता है और प्रति सेकंड 3.5 करोड़ requests के path पर चलता है
  • मौजूदा implementation हर request पर 100 से अधिक internal headers को हटाने की कोशिश करता था, जिसमें औसतन 3.65µs लगते थे; यह pingora-origin के कुल CPU time का 1.71%, यानी 40,000 compute-seconds/s में से लगभग 680 CPU cores के बराबर खर्च करता था
  • पहले actual request headers पर iterate करने वाला तरीका औसतन 1.53µs के साथ 2.39x तेज हुआ, लेकिन कुल CPU बचत सैद्धांतिक रूप से 0.993% तक ही रही, इसलिए बेहतर search structure की जरूरत थी
  • नए trie implementation ने औसत execution time को 0.93µs तक घटाया, और जुलाई 2024 से production में चलाए गए sampling में भी clear_internal_headers का वास्तविक CPU उपयोग 0.34% तक नीचे आया

Cloudflare जिस लागत को घटाना चाहता था

  • Cloudflare का global network औसतन प्रति सेकंड 6 करोड़ से अधिक HTTP requests संभालता है
  • यह optimization Rust-आधारित proxy service के core Pingora और उस पर चलने वाली production service pingora-origin से शुरू हुआ
  • pingora-origin user की non-cache requests को वास्तविक destination server, यानी origin, तक भेजने के अंतिम चरण के लिए जिम्मेदार है
  • इस service को request के Cloudflare infrastructure से बाहर जाने से पहले internal routing, measurement और optimization में इस्तेमाल हुई जानकारी को headers से हटाना होता है
  • दुनिया भर में pingora-origin से बाहर जाने वाली requests, लिखे जाने के समय, प्रति सेकंड 3.5 करोड़ हैं

bottleneck function: clear_internal_headers

  • समस्या वाला function सभी requests में चलने वाले बेहद hot path में है
// 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);
    });
}
  • सिर्फ यह छोटा function pingora-origin के कुल CPU time का 1.7% से अधिक इस्तेमाल करता है
  • pingora-origin का कुल CPU time प्रति सेकंड 40,000 compute-seconds है, जो केवल इस service को चलाने वाले 40,000 fully saturated CPU cores के पैमाने जैसा है
  • उसमें से 1.7%, यानी लगभग 680 CPU cores, सिर्फ clear_internal_headers के evaluation में खर्च हो रहे थे

baseline measurement और पहला सुधार

  • performance measurement के लिए Rust crate criterion का इस्तेमाल किया गया
  • Criterion कई isolated runs को aggregate करके Rust code का time nanosecond level पर मापता है, और समय के साथ performance improvement या regression पर feedback भी देता है
  • benchmark input, internal headers और non-internal headers के बराबर distribution के लिए synthesize किए गए requests के बड़े set से बना था
  • मौजूदा clear_internal_headers का औसत execution time 3.65µs मापा गया

  • lookup direction को उलटना

    • मौजूदा code internal headers list के हर item के लिए request_header.remove_header(h) चलाता है, इसलिए अगर internal headers 100 से अधिक हों तो हर request पर 100 से अधिक evaluations होते हैं
    • औसत request में headers की संख्या 100 से काफी कम, लगभग 10–30 होती है, इसलिए actual request headers पर iterate करके internal header set में खोजने से reads की संख्या घटती है
    • Rust के http::HeaderMap में अभी retain नहीं है, इसलिए हटाए जाने वाले internal headers को अलग step में collect करके फिर delete करना पड़ता है
    • केवल इस बदलाव से average execution time 3.65µs से 1.53µs हो गया, यानी 2.39x तेज
    • सिद्धांत रूप में कुल CPU usage 1.71% से 0.717% पर आ जाता है, और बचत 0.993% है

बेहतर search data structure की खोज

  • lookup direction बदलने के बाद static internal headers list को किस data structure में store किया जाए, यह चुनना संभव हो गया
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);
   });
}
  • पहला प्रयास std::HashMap था, लेकिन string key hashing में सभी bytes पढ़ने पड़ते हैं, इसलिए table size के लिहाज से constant time होने के बावजूद key length L के लिहाज से linear time बनता है
  • लक्ष्य ऐसा data structure ढूंढना था जिसकी read behavior key length के लिए O(L) से बेहतर हो

  • जांचे गए विकल्प

    • BTreeSet जैसे sorted sets comparison-based search का इस्तेमाल करके key length के लिए O(log(L)) behavior देते हैं, लेकिन set size के लिए भी logarithmic time लेते हैं
    • तेज sorted set FST भी benchmark में standard hashmap से लगभग 50ns धीमा था
    • parser या regex जैसी state machines input को एक-एक unit लेकर हर step पर तय करती हैं कि evaluation जारी रखना है या नहीं, इसलिए non-matching strings को जल्दी identify कर सकती हैं
    • internal headers प्रति request औसतन सिर्फ 1–2 होते हैं, इसलिए यह negative cases वाले माहौल के लिए अच्छा fit है
    • regex इस्तेमाल करने वाला clear_internal_headers implementation hashmap-based solution से लगभग 2 गुना अधिक समय लेता था, लेकिन raw speed के लिए प्रसिद्ध tool न होने को देखते हुए यह तेज नतीजा था

trie सही क्यों है

  • trie known strings के set में prefix search या autocomplete के लिए अक्सर इस्तेमाल होने वाला tree data structure है
  • trie का हर node शुरुआती string set में मिलने वाली substring को दर्शाता है, और nodes के बीच connections उन characters को दर्शाते हैं जो किसी खास prefix के बाद आ सकते हैं
  • root node से शुरू करके संभावित पहले character से ही search space को घटाया जा सकता है, इसलिए शामिल न होने वाली strings को तेजी से exclude किया जा सकता है
  • trie reads mismatch cases के लिए O(log(L)) behavior देते हैं, लेकिन match cases अब भी O(L) रहते हैं
  • request headers के 90% से अधिक internal headers नहीं होते, इसलिए बहुत सारे mismatch cases वाले इस use case के लिए यह उपयुक्त है

  • मौजूदा trie implementations की सीमाएं

    • crates.io पर कई trie implementations benchmark किए गए, लेकिन results उम्मीद से कम रहे
    • ज्यादातर trie implementations keyboard events पर respond करने वाले autocomplete जैसे use cases के लिए tuned हैं, जहां प्रति सेकंड करोड़ों requests के hot path optimization की प्राथमिकता नहीं होती
    • सबसे तेज मिले मौजूदा implementation radix_trie था, लेकिन वह भी hashmap से 1µs धीमा था
    • आखिरकार इस use case के हिसाब से नया trie implementation लिखा गया

trie-hard और production results

  • Cloudflare ने नया open source Rust crate trie-hard जारी किया

  • trie-hard unsigned integers के bits में node relationships store करता है और speed पाने के लिए पूरे tree को contiguous memory block में रखता है

  • benchmark में trie-hard ने clear_internal_headers का average execution time 0.93µs तक घटाया

  • अनुमानित CPU usage 0.43% है, जो मौजूदा 1.71% की तुलना में पूरे pingora-origin compute usage को 1.28% घटाता है

  • वास्तविक sampling results

    • trie-hard जुलाई 2024 से production में चल रहा है
    • performance measurement समय के साथ stack trace statistics sampling से collect किया गया
    • किसी specific function वाले samples के ratio से उस function के CPU usage का अनुमान लगाया गया
    • production sampling results, local benchmark predictions के कुल मिलाकर करीब हैं
    implementation clear_internal_headers शामिल stack trace samples वास्तविक CPU usage अनुमानित CPU usage
    Original 19 / 1111 1.71% n/a
    Hashmap 9 / 1103 0.82% 0.72%
    trie-hard 4 / 1171 0.34% 0.43%

operations के नजरिए से निष्कर्ष

  • नया data structure लिखने से पहले यह जानना जरूरी है कि code कहां और कितना slow है
  • flame graph, profiling और benchmarking tools का उपयोग करके microsecond-level functions में भी meaningful savings मिल सकती हैं
  • पहले से बहुत छोटे operations को optimize करना मामूली लग सकता है, लेकिन प्रति सेकंड करोड़ों requests के पैमाने पर छोटे improvements जमा होकर कुल compute usage घटाते हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-09-11
Hacker News की राय

  • अगर मुझसे अंदाज़ा लगाने को कहा जाता कि Cloudflare internal headers को कैसे स्टोर और हटाता है, तो शायद मैं अलग dictionary या data structure, सभी internal metadata रखने वाला एक single header, internal/external को prefix से अलग करने का तरीका, या CFInt जैसा कोई prefix सोचता
    किसी खास list में मौजूद header names को internal headers मानने का तरीका शायद मेरे दिमाग में नहीं आता. सवाल उठते हैं कि अगर कोई और वही नाम इस्तेमाल करे तो क्या होगा, cleanup छूट जाए तो क्या होगा, साथ-साथ चल रहे programs की lists अलग-अलग हों तो क्या होगा, Connection header Cloudflare के internal header की ओर इशारा करे तो क्या होगा, और set-difference algorithm धीमा हो तो क्या होगा
    web पहले ही परेशान करने की हद तक अस्पष्ट in-band signals और header naming से भरा है, ऐसे में Cloudflare जैसी scale वाली कंपनी का internally इतना झंझट भरा और error-prone mechanism इस्तेमाल करना अजीब लगता है

    • एक पूर्व कर्मचारी के तौर पर दिलचस्प और डरावनी बात यह है कि Workers जैसे serverless products में कुछ internal headers सेट किए जा सकते थे, और cf-cache-status से जुड़े साफ़ दिखने वाले bugs जैसी तरह-तरह की खराब चीज़ें हो सकती थीं
    • मैंने कई बड़ी कंपनियों के IT security organizations में काम किया है, और जो जगहें headers पर काफ़ी ध्यान देती थीं, वे भी Cloudflare जैसे ही तरीके से headers इस्तेमाल करती थीं
      इसमें edge proxy पर internal headers को दोनों दिशाओं में हटाना भी शामिल था, inbound में भी ऐसा ही किया जाता था
    • मुझे लगता है कि सुझाए गए दूसरे solutions में भी मिलती-जुलती कई समस्याएँ हैं. बल्कि सूचीबद्ध की गई कुछ समस्याएँ उन दूसरे solutions पर भी लागू होंगी
      list वाले तरीके की कमियाँ हैं, लेकिन फायदे भी बहुत हैं. ऐसे approach की संभावित कमियों को बताते समय लोग अक्सर Cloudflare के scale पर बनी history और कठिनाइयों को नजरअंदाज करते दिखते हैं. enumerated list सबसे simple और flexible तरीका है, और header key structure पर पहले से agreement की भी ज़रूरत नहीं होती. Cloudflare की teams की संख्या, technology acquisitions की संभावना आदि सोचें तो यह बात अहम रही होगी
    • मैं भी यही सोचता हूँ, लेकिन system समय के साथ बढ़ता गया और HTTP headers को हर तरह के काम के लिए इस्तेमाल किया जाने लगा. यह optimization स्थिति को बेहतर बनाता है, लेकिन असली solution जिस पर काम चल रहा है वह IPC के लिए अलग mechanism इस्तेमाल करना और HTTP headers के इस्तेमाल को पूरी तरह खत्म करना है
    • एक और idea यह है कि जो internal headers बाहर नहीं भेजे जाने हैं उन्हें header list की शुरुआत में ही add कराया जाए, या हर request की hash table को हटाए जाने वाले internal headers से पहले से pre-fill कर दिया जाए
      pre-fill करने से असल में ये ideas combine हो जाते हैं और हर request में internal headers की संख्या fixed हो जाती है. उस point पर creation order preserve करने वाली linked hash table इस्तेमाल की जा सकती है, और client को वापस भेजी जाने वाली final list में से आगे के N headers ही हटाने होंगे

  • UTF-8 characters को bitmask में map करने के effect पर मैंने थोड़ा सोचा, और शुरू में यह बहुत समझदारी भरा नहीं लगा. लेकिन फिर समझ आया कि 32-bit में a-z और 6 special characters समा जाते हैं, और 64-bit में uppercase A-Z और 6 और special characters भी समा सकते हैं
    HTTP headers के लिए यह पर्याप्त space है, और कुछ integers को mask करके compare करना बहुत तेज़ matching algorithm बन जाता है. कौन सा character किस bit से match करता है, इसके लिए भी सिर्फ 256-word table lookup चाहिए
    लेखक ने जो बात छोड़ दी है वह यह है कि यह technique technically Bloom filter है. ऐसी चीज़ें इसलिए रोचक हैं क्योंकि जब computing resources आज की तुलना में बहुत सीमित थे—इस मामले में 1970 में निकली optimization—तब भी real world के किसी कोने में वही पुरानी optimization इस्तेमाल हो रही है
    https://en.wikipedia.org/wiki/Bloom_filter

    • trie-hard और Bloom filter में बड़ा अंतर है. Bloom filter probabilistic होता है और hashing इस्तेमाल करता है. यह तब अच्छा है जब दुर्लभ false positives स्वीकार्य हों लेकिन false negatives नहीं होने चाहिए, पर यहाँ जरूरत वह नहीं है. यहाँ accuracy चाहिए, और hashing खुद ही वह step है जिसे हराना है
      बल्कि यह TeX में hyphenation dictionary store करने के लिए इस्तेमाल किए गए Liang algorithm के improved version या variant के ज्यादा करीब है. paper Bloom के algorithm को “superimposed coding” कहकर discuss करता है, और उस दौर की जोरदार याद दिलाता है जब memory सबसे कीमती resource थी. शायद आपको पसंद आए ^_^
      https://tug.org/docs/liang/liang-thesis.pdf
    • Bloom filter तब useful होता है जब dataset बड़ा हो, और हर item के लिए कई hashes calculate करने की cost original dataset में search करने की cost से कम हो. यहाँ तो कहा जा रहा है कि एक hash भी महंगा है, इसलिए Bloom filter original hash map से कहीं धीमा होगा

  • फायदा साबित करने के लिए पेश किया गया data असल में उसे दिखाने के लिए पर्याप्त statistical power नहीं रखता. sample पर्याप्त नहीं है
    R में बहुत simple analysis करें तो यह prop.test(c(9, 4), c(1103,1171)) है, और continuity correction के साथ दो proportions की equality test में p-value 0.222 आती है
    p-value 0.22 जादुई 0.05 से कम नहीं है, और 95% confidence interval संकेत देता है कि trie असल में थोड़ा worse भी हो सकता है
    prior analysis देखें तो trie बेहतर लगता है और कुछ weak evidence भी है, लेकिन sample काफी ज्यादा लेकर यह पक्का कर लेना बेहतर होगा कि वह कितना बेहतर है

  • performance analyze करने के goal में comparisons की संख्या को Big-O notation से समझाना अटपटा है. comparison करीब 1 cycle का होता है, और instruction-level parallelism और SIMD से एक cycle में कई comparisons भी हो सकते हैं
    असली bottleneck और slowness का source memory है. memory access में हजारों cycles लगते हैं, और अगर TLB walk या OS interrupt की जरूरत पड़े तो यह tens of thousands या hundreds of thousands cycles तक जा सकता है. अगर Big-O इस्तेमाल करना है तो उसे cache misses की संख्या estimate करने में इस्तेमाल करना चाहिए
    मैं होता तो custom perfect hash function और Phil Bagwell की popcount trick इस्तेमाल करता. यह memory को कई बार lookup करने वाले दूसरे solutions से तेज़ होगा
    CPU तेज़ है, memory धीमी है

  • मैं डेटा स्ट्रक्चर ऑप्टिमाइज़ेशन में बहुत माहिर नहीं हूँ, लेकिन खासकर यह देखते हुए कि जिस टेबल में खोज करनी है वह static है, hash table को इतनी जल्दी खारिज कर देना हैरान करने वाला लगा। यह मानना मुश्किल है कि खास तौर पर optimized hash table इनके trie implementation से तेज़ नहीं होगा

    • hash function सिर्फ़ पहले byte को देखकर string को reject नहीं कर सकता। यह बस संभव नहीं है
      इस use case में यही वह फायदा है जिसकी बराबरी hash नहीं कर सकता। बाकी तकनीकें trie के constant factors को इतना घटाने का काम हैं कि यह शुरुआती फायदा वास्तविक performance में वसूल हो सके
    • std::collections::HashMap से तेज़ FxHashMap मौजूद है: https://github.com/rust-lang/rustc-hash
      static entries लगभग 100 हों तो o1hash भी काम कर सकता है: https://github.com/rurban/smhasher/blob/master/o1hash.h
    • लेख में कहा गया था कि hashing का overhead उसे trie की तुलना में धीमा बनाता है

  • यह लेख एक शानदार data structure से to_remove set बनाता है, फिर उस पर iterate करके basic header map से हटाता है
    remove_header call इस code जैसा दिखता है: https://docs.rs/pingora-http/0.3.0/src/pingora_http/lib.rs.html#576
    यह function दो दूसरे data structures पर .remove() call करता है, और दोनों आखिर में इस विशाल code तक उतरते हैं: https://docs.rs/http/latest/src/http/header/map.rs.html#1550

  • आखिरकार trie पर एक blog post आ ही गया। trie वाले LeetCode problems बेकार नहीं गए ;)

    • असली code में इस्तेमाल किया है। कुछ use cases में यह काफ़ी intuitive होता है। आखिरी बार trie मैंने address lookup के लिए इस्तेमाल किया था, और generator तक बनाया था। असल दुनिया में एक साथ दो LeetCode hits मिल गए
      फिर भी यह निश्चित रूप से ऐसा tool नहीं है जिसे मैं अक्सर निकालता हूँ
    • तेज़ spell checker या grammar checker में trie मिल सकता है
    • हाल ही में मुझे बदले हुए hybrid trie को असल में इस्तेमाल करने का मौका मिला, और implement करना मज़ेदार था। optimize करने की गुंजाइश भी बहुत थी
      यह Go के लिए user agent parser है: https://github.com/medama-io/go-useragent
      आम तौर पर ऐसी समस्या बहुत सारी regex parsing पर निर्भर करती है, इसलिए थोड़ा नया approach आज़माना अच्छा लगा
    • मध्यम complexity वाले build tools या code analysis scripts में कभी-कभी trie/radix tree इस्तेमाल हो जाता है। बहुत सारे file paths की जानकारी store करनी हो तो common prefixes अलग करने से memory काफ़ी बचती है और फिर भी यह काफी intuitive रहता है
    • Scrabble word generator और play programs में trie बहुत अहम होता है। मैंने कुछ बनाए हैं, और सबसे तेज़ structure शब्दों के rotated representation वाला compressed trie था

  • अगर match किए जाने वाले items का set static है, तो जिज्ञासा है कि क्या इन्होंने perfect hash table आज़माया था। कुछ arithmetic operations के बाद बस एक string comparison रह जाना चाहिए, तो trie से इसकी तुलना देखना रोचक होगा

    • मेरा भी तुरंत यही ख्याल आया। हालांकि perfect hash भी hash function की वजह से अभी भी key length O(n) है, और यही वह हिस्सा है जिससे ये बचना चाहते हैं
      theoretically regex इस्तेमाल करने पर matching state machine से होती है, इसलिए trie जैसी worst-case O(k) performance मिलनी चाहिए। लेकिन मेरी समझ में regex libraries असली state machine बनाने के बजाय backtracking इस्तेमाल करती हैं, इसलिए performance अब O(k) नहीं रहती
      यह हैरान करने वाला है कि उन्हें पहले से मौजूद कोई अच्छी performance वाली state-machine-based regex library नहीं मिली। performance trie जैसी होनी चाहिए, पर असल में memory access pattern या खास arithmetic operations की performance जैसे factors गहराई से असर डालते हैं, इसलिए अनुमान लगाना मुश्किल है

  • क्या इन्होंने बहुत छोटा Bloom filter आज़माया होगा? header keys को जल्दी से convolution जैसा process करके Bloom filter से मिलाया जाए तो कुछ cycles की cost में ज़्यादातर मामलों में trie traversal पूरी तरह avoid किया जा सकता है
    SIMD, built-in CRC instructions, 256-bit Bloom filter size जैसे options भी दिखते हैं

    • पता नहीं उस team ने किया या नहीं, लेकिन Bloom filter कोई रामबाण नहीं है: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/
    • इनके trie implementation में हर node का filter पहले से ही Bloom filter जैसा है, इसे देखते हुए solution काफ़ी करीब है। मैं सहमत हूँ कि string के बड़े हिस्से को एक बार में check करना dramatic speedup दे सकता है
      और भी simple approach valuable हो सकता है। trie nodes की hit/fail frequency analysis करें तो शायद first character से ज्यादा failure rate वाला कोई specific character position मिल जाए। ऐसी special position को पहले check करने से speed बढ़ सकती है। बेशक, इसके लिए assumption चाहिए कि header data मूल रूप से काफी regular है
    • उसमें hash calculation चाहिए होगी, और लगता है उसी cost को बहुत slow मानकर पहले ही खारिज किया जा चुका है

  • मेरी राय यह है। पहला, क्या यह करने लायक काम है? लगता है कि लगभग 500 CPU कोर बचाए गए हैं, लेकिन पता नहीं ये असली कोर हैं या hyperthreaded कोर भी शामिल हैं।
    Cloudflare की लागत मुझे नहीं पता, लेकिन यह सर्वरों की इकाई-अंकों वाली संख्या के बराबर होगा और बचत भी शायद सालाना दसियों हजार डॉलर के स्तर की होगी। यह नज़रअंदाज़ करने लायक नहीं है, लेकिन engineering निवेश के मुकाबले positive ROI की उम्मीद की जा सकती है या नहीं, पता नहीं।
    दूसरा, अगर इतनी बारीकी में जाना है, तो मैं जानना चाहूँगा कि क्या उन्होंने deserialization चरण में filter लगाकर headers को शुरुआत में ही बनने से रोकने का विकल्प देखा था।

    • हो सकता है यह सिर्फ दसियों हजार डॉलर हो, लेकिन यह बचत स्थायी है।
      बिजली की बचत भी जारी रहती है, और carbon emissions भी घटते हैं।
      headers को AI से analyze करके sandals बेचने जैसी बेवकूफी करने के बजाय, किसी चीज़ को 1% तेज़ बनाने की कोशिश करती कंपनी देखना अच्छा लगता है।
    • यह बहुत छोटा edge case है, लेकिन ऐसा कंटेंट भी है जिसे आसानी से public किया जा सकता है। यह marketing content बन जाता है, जिससे सैकड़ों geeks इस पर चर्चा करते हैं कि Cloudflare जो कर रहा है वह सही है या नहीं, और वह performance की कितनी परवाह करता है।
      इसकी कीमत दस लाख डॉलर हो सकती है।
    • ROI वाली बात का मतलब मुझे ठीक से समझ नहीं आया। अगर सालाना 40 हज़ार डॉलर 5 साल तक बचते हैं, तो 2 लाख डॉलर हुए। Hungary या Poland के हिसाब से यह कई हैकरों की सालाना salary है। पता नहीं Cloudflare के वहाँ offices हैं या नहीं।
    • अगर किसी engineer ने बस कुछ दिन लगाए हों, तो क्या बचत काफ़ी valuable नहीं लगती?