วันที่ดีของ trie-hard: ประหยัดการประมวลผล 1%

 (blog.cloudflare.com)
2 คะแนน โดย GN⁺ 2024-09-11 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

แรงจูงใจ

  • เครือข่ายทั่วโลกของ Cloudflare รองรับคำขอ HTTP มากกว่า 60 ล้านรายการต่อวินาที
  • ลดการใช้ CPU และเพิ่มความสามารถในการประมวลผลของ CDN ด้วย Rust crate โอเพนซอร์สตัวใหม่
  • Pingora เป็นแกนหลักของบริการพร็อกซีที่พัฒนาด้วย Rust ของ Cloudflare และถูกเปิดซอร์สแล้ว
  • บริการ Pingora-origin ทำหน้าที่ส่งต่อคำขอของผู้ใช้ไปยังปลายทางจริง
  • เมื่อคำขอออกจาก Cloudflare จำเป็นต้องลบข้อมูลภายในออก
  • งานนี้เกิดขึ้นบ่อยมากและกินการใช้ CPU ถึง 1.7%

การทำเบนช์มาร์ก

  • ใช้ Rust crate ชื่อ Criterion เพื่อวัดประสิทธิภาพของฟังก์ชันในระดับนาโนวินาที
  • เดิมฟังก์ชัน clear_internal_headers ใช้เวลาเฉลี่ย 3.65µs

ลดงานอ่านข้อมูล

  • ลดงานอ่านข้อมูลด้วยการกลับทิศทางการลบเฮดเดอร์
  • การเปลี่ยนแปลงนี้ทำให้เวลาทำงานของฟังก์ชันดีขึ้นจาก 3.65µs เหลือ 1.53µs
  • ลดการใช้ CPU จาก 1.71% เหลือ 0.717%

การค้นหาโครงสร้างข้อมูล

  • ลองใช้แฮชแมปเพื่อจัดเก็บและค้นหาเฮดเดอร์ภายใน
  • เวลาอ่านของแฮชแมปเพิ่มขึ้นแบบเชิงเส้นตามความยาวของคีย์
  • ได้ลองโครงสร้างข้อมูลอื่น ๆ เช่น เซตแบบเรียงลำดับหรือ state machine
  • การติดตั้งใช้งานที่ใช้ regular expression ช้ากว่าแฮชแมป 2 เท่า

การใช้ trie

  • trie คือโครงสร้างข้อมูลแบบต้นไม้ที่ใช้กับการค้นหาคำนำหน้าหรือระบบเติมคำอัตโนมัติ
  • trie สามารถระบุได้อย่างรวดเร็วว่าไม่มีสตริงนั้นอยู่
  • การติดตั้งใช้งาน trie ที่มีอยู่เดิมช้ากว่าแฮชแมป
  • Cloudflare จึงพัฒนา trie เวอร์ชันปรับแต่งของตัวเองชื่อ trie-hard

Trie Hard

  • trie-hard เก็บความสัมพันธ์ของโหนดไว้ในบิตของจำนวนเต็มและใช้หน่วยความจำแบบต่อเนื่องเพื่อเพิ่มความเร็ว
  • ลดเวลาทำงานของฟังก์ชัน clear_internal_headers ลงเหลือ 0.93µs
  • ลดการใช้ CPU จาก 1.71% เหลือ 0.43%
  • ในสภาพแวดล้อมโปรดักชันจริง ประสิทธิภาพของ trie-hard สอดคล้องกับผลเบนช์มาร์ก

บทสรุป

  • การระบุส่วนที่ช้าของโค้ดและปรับแต่งมันเป็นสิ่งสำคัญ
  • การปรับแต่งเล็ก ๆ หลายจุดสามารถรวมกันเป็นการเพิ่มประสิทธิภาพครั้งใหญ่ได้
  • Cloudflare Connected Cloud มอบความสามารถอย่างการปกป้องเครือข่าย การเร่งความเร็วแอปพลิเคชันอินเทอร์เน็ต และการป้องกันการโจมตี DDoS

สรุปโดย GN⁺

  • Cloudflare ลดการใช้ CPU และเพิ่มความสามารถในการประมวลผลของ CDN ผ่าน Rust crate โอเพนซอร์สตัวใหม่
  • ปรับแต่งงานลบเฮดเดอร์ภายในของบริการ Pingora-origin จนลดการใช้ CPU ได้ 1.28%
  • พัฒนา trie เวอร์ชันปรับแต่งของตนเองชื่อ trie-hard เพื่อยกระดับประสิทธิภาพอย่างมาก
  • บทความนี้เน้นความสำคัญของการปรับแต่งโค้ดและการเลือกโครงสร้างข้อมูล พร้อมแสดงให้เห็นว่าการปรับแต่งเล็ก ๆ สามารถนำไปสู่การเพิ่มประสิทธิภาพครั้งใหญ่ได้
  • โครงการที่มีฟังก์ชันคล้ายกัน ได้แก่ NGINX และ HAProxy

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-09-11
ความคิดเห็นจาก Hacker News

  • มีการคาดเดาหลายอย่างเกี่ยวกับวิธีที่ Cloudflare จัดเก็บและลบเฮดเดอร์ภายใน

    • ใช้พจนานุกรมหรือโครงสร้างข้อมูลแยกต่างหาก
    • ใช้เฮดเดอร์เดี่ยวที่รวมเมตาดาต้าภายในทั้งหมด
    • ใส่คำนำหน้าให้เฮดเดอร์ทั้งหมด โดยภายในขึ้นต้นด้วย 'I' และภายนอกขึ้นต้นด้วย 'E'
    • เฮดเดอร์ภายในทั้งหมดขึ้นต้นด้วย "CFInt"
    • ไม่คาดคิดว่าจะใช้วิธีที่เฮดเดอร์ในรายการเฉพาะถือเป็นเฮดเดอร์ภายใน
    • เว็บเต็มไปด้วยสัญญาณกำกวมและชื่อเฮดเดอร์ที่ชวนสับสนอยู่แล้ว
    • น่าแปลกที่บริษัทขนาดใหญ่อย่าง Cloudflare ใช้กลไกที่ผิดพลาดได้ง่ายแบบนี้

  • ตอนแรกคิดว่าการแมปอักขระ UTF-8 เป็นบิตมาสก์นั้นไม่มีประสิทธิภาพ

    • ใช้ 32 บิตเก็บ a-z และอักขระพิเศษอีกหกตัวได้
    • ใช้ 64 บิตเก็บตัวพิมพ์ใหญ่ A-Z และอักขระพิเศษอีกหกตัวได้
    • ให้พื้นที่เพียงพอสำหรับ HTTP header และทำให้อัลกอริทึมการจับคู่ทำงานได้รวดเร็ว
    • เทคนิคนี้คือ Bloom Filter
    • เป็นเทคนิคที่พัฒนาขึ้นในยุคทศวรรษ 1970 ซึ่งทรัพยากรมีจำกัด แต่ก็ยังถูกใช้งานได้อย่างมีประโยชน์มาจนถึงปัจจุบัน

  • มีข้อสงสัยว่าการปรับแต่งของ Cloudflare คุ้มค่าหรือไม่

    • ประหยัด CPU core ได้ราว 500 คอร์
    • ไม่รู้ต้นทุนของ Cloudflare แต่คาดว่าน่าจะประหยัดได้ระดับหลายหมื่นดอลลาร์
    • สงสัยว่าจะคาดหวัง ROI เชิงบวกจากงานวิศวกรรมนี้ได้จริงหรือไม่
    • อาจดีกว่าถ้าใช้ฟิลเตอร์ตั้งแต่ขั้นตอน deserialize เพื่อไม่ให้มีการสร้างเฮดเดอร์ตั้งแต่แรก

  • ไม่ค่อยรู้เรื่องการปรับแต่งโครงสร้างข้อมูลมากนัก แต่แปลกใจที่ตัด hash table ออกไปอย่างรวดเร็ว

    • คิดว่า hash table น่าจะเร็วกว่าสำหรับการค้นหาในตารางแบบคงที่

  • ใช้โครงสร้างข้อมูลแบบ fancy เพื่อกำหนดรายการที่จะลบ แล้วลบจาก header map ตามนั้น

    • ให้ลิงก์ไปยังโค้ดที่เกี่ยวข้องกับการเรียก remove_header

  • ในที่สุดก็มีบล็อกโพสต์ที่ใช้ trie

    • โจทย์เกี่ยวกับ trie ที่เคยทำมาก่อนหน้านี้ไม่ได้สูญเปล่า

  • สงสัยว่าได้ลองใช้ Bloom Filter ขนาดเล็กหรือไม่

    • การทำ convolution แบบเร็วกับคีย์ของเฮดเดอร์และทดสอบด้วย Bloom Filter อาจช่วยเลี่ยงการไล่เดิน trie ได้

  • สงสัยว่ากรณีจับคู่กับชุดรายการแบบคงที่ ได้ลองใช้ perfect hash table หรือไม่

    • อาจลดเหลือเพียงการคำนวณเชิงเลขไม่กี่ครั้งกับการเปรียบเทียบสตริงเพียงครั้งเดียว

  • การปรับแต่งนี้น่าสนใจ

    • สงสัยว่าเป็นไปได้ไหมที่จะติดแท็กเฮดเดอร์ว่าเป็นภายในตั้งแต่ตอนสร้างคำขอ
    • จะทำให้การกรองในตอนส่งออกง่ายขึ้น

  • สงสัยว่าทำไม regex crate ถึงทำงานได้ไม่ดีกว่า

    • เพราะควรคอมไพล์การค้นหาสตริงลิเทอรัลหลายตัวให้เป็น Aho-Corasick automaton