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

 (blog.cloudflare.com)
2 पॉइंट द्वारा GN⁺ 2024-09-11 | 1 टिप्पणियां | WhatsApp पर शेयर करें

प्रेरणा

  • Cloudflare का global network प्रति सेकंड 6 करोड़ से अधिक HTTP requests को संभालता है
  • एक नए open source Rust crate का उपयोग करके CPU उपयोग को कम किया गया और CDN की processing क्षमता को बेहतर बनाया गया
  • Pingora, Cloudflare की Rust-आधारित proxy service का core है, और इसे open source के रूप में जारी किया गया है
  • Pingora-origin service उपयोगकर्ता के requests को वास्तविक destination तक पहुंचाने का काम करती है
  • request के Cloudflare से बाहर जाने पर internal जानकारी हटाने का काम आवश्यक होता है
  • यह काम बहुत बार होता है और CPU उपयोग का 1.7% हिस्सा लेता है

बेंचमार्किंग

  • Criterion Rust crate का उपयोग करके function performance को nanosecond स्तर पर मापा गया
  • मूल clear_internal_headers function को औसतन 3.65µs लगते थे

पढ़ने के काम को कम करना

  • headers हटाने की दिशा को उलटकर read operations को कम किया गया
  • इस बदलाव से function का execution time 3.65µs से घटकर 1.53µs हो गया
  • CPU उपयोग 1.71% से घटकर 0.717% हो गया

data structure खोज

  • internal headers को store और search करने के लिए hash map का उपयोग करने की कोशिश की गई
  • hash map का read time key की लंबाई के अनुपात में linear होता है
  • sorted set या state machine जैसे अन्य data structures भी आज़माए गए
  • regular expression का उपयोग करने वाला implementation hash map से दोगुना धीमा था

trie का उपयोग

  • trie एक tree data structure है जिसका उपयोग prefix search या autocomplete systems में किया जाता है
  • trie ऐसे मामलों को तेज़ी से पहचान सकता है जहाँ string मौजूद नहीं होती
  • मौजूदा trie implementations hash map से धीमे थे
  • Cloudflare ने अपनी optimized trie implementation trie-hard विकसित की

Trie Hard

  • trie-hard, node relationships को integer के bits में store करता है और speed बढ़ाने के लिए memory का contiguous उपयोग करता है
  • clear_internal_headers function का execution time 0.93µs तक घटा दिया गया
  • CPU उपयोग 1.71% से घटकर 0.43% हो गया
  • वास्तविक production environment में trie-hard का प्रदर्शन benchmark के अनुरूप रहा

निष्कर्ष

  • code के धीमे हिस्सों की पहचान करके उन्हें optimize करना महत्वपूर्ण है
  • छोटी optimizations मिलकर बड़ा performance improvement ला सकती हैं
  • Cloudflare का connectivity cloud network protection, internet application acceleration, DDoS attack defense जैसी क्षमताएँ प्रदान करता है

GN⁺ का सार

  • Cloudflare ने Rust-आधारित नए open source crate के जरिए CPU उपयोग कम किया और CDN की processing क्षमता बेहतर बनाई
  • Pingora-origin service में internal header removal को optimize करके CPU उपयोग 1.28% घटाया गया
  • trie-hard नाम की अपनी optimized trie implementation विकसित कर performance में बड़ा सुधार किया गया
  • यह लेख code optimization और data structure selection के महत्व पर ज़ोर देता है, और दिखाता है कि छोटी optimizations भी बड़ा performance improvement ला सकती हैं
  • समान कार्यक्षमता वाले प्रोजेक्ट्स में NGINX, HAProxy आदि शामिल हैं

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

1 टिप्पणियां

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

  • Cloudflare के internal header को store और remove करने के तरीके को लेकर कई तरह के अनुमान लगाए गए

    • अलग dictionary या data structure का उपयोग
    • एक single header जिसमें सभी internal metadata शामिल हो
    • सभी header में prefix जोड़ना, जहाँ internal 'I' से और external 'E' से शुरू हों
    • सभी internal header की शुरुआत "CFInt" से हो
    • यह उम्मीद नहीं थी कि किसी खास सूची के header को internal header माना जाएगा
    • web पहले से ही अस्पष्ट signals और header naming से भरा हुआ है
    • यह अजीब है कि Cloudflare जैसी बड़े पैमाने की कंपनी ऐसा mechanism इस्तेमाल करे जिसमें ऐसी गलती आसानी से हो सकती है

  • UTF-8 characters को bitmask पर map करने के बारे में शुरुआत में यह अक्षम लगा

    • 32-bit में a-z और छह special characters शामिल किए जा सकते हैं
    • 64-bit में uppercase A-Z और छह special characters शामिल किए जा सकते हैं
    • यह HTTP header के लिए पर्याप्त space देता है और fast matching algorithm को संभव बनाता है
    • यह तकनीक Bloom Filter है
    • यह 1970s में resource-constrained दौर में विकसित हुई तकनीक है, लेकिन आज भी उपयोगी है

  • इस पर सवाल कि Cloudflare का optimization वास्तव में कितना मूल्यवान है

    • लगभग 500 CPU cores बचाए गए
    • Cloudflare की लागत का पता नहीं, लेकिन कुछ दसियों हज़ार डॉलर की बचत का अनुमान है
    • यह स्पष्ट नहीं कि engineering पर सकारात्मक ROI की उम्मीद की जा सकती है या नहीं
    • शायद filter को deserialization stage पर लागू करना बेहतर होता ताकि header बनें ही नहीं

  • data structure optimization के बारे में बहुत जानकारी नहीं, लेकिन hash table को इतनी जल्दी नज़रअंदाज़ करना हैरान करता है

    • static table में lookup करते समय hash table के तेज़ होने की उम्मीद थी

  • fancy data structure का उपयोग करके हटाए जाने वाले items को व्यवस्थित किया गया और उसके आधार पर header map से हटाया गया

    • remove_header call से जुड़ा code link दिया गया

  • trie का उपयोग करने वाली blog post आखिरकार आ गई

    • trie से जुड़े सवाल बेकार नहीं गए

  • यह जानने की जिज्ञासा कि क्या किसी ने छोटा Bloom Filter आज़माया था

    • header key के लिए fast convolution और Bloom Filter test, trie walk से बचा सकता है

  • static item set को match करने के मामले में यह जिज्ञासा कि क्या perfect hash table आज़माया गया था

    • इसे कुछ arithmetic operations और एक single string comparison तक सीमित किया जा सकता है

  • optimization दिलचस्प है

    • यह जिज्ञासा कि request बनाते समय header को internal के रूप में tag करना संभव था या नहीं
    • output के समय filtering आसान हो जाती

  • यह जिज्ञासा कि regex crate ने बेहतर काम क्यों नहीं किया

    • कई literal string searches को Aho-Corasick automaton में compile किया जाना चाहिए