วันที่ดีของ trie-hard: ประหยัดคอมพิวต์ 1%

 (blog.cloudflare.com)
2 คะแนน โดย GN⁺ 2024-09-11 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Cloudflare เปิดตัว Rust crate แบบโอเพนซอร์ส trie-hard เพื่อลดการใช้ CPU ของพร็อกซีที่ใช้ Rust ชื่อ Pingora บนเครือข่ายที่ประมวลผลคำขอ HTTP เฉลี่ยมากกว่า 60 ล้านครั้งต่อวินาที
  • คอขวดอยู่ที่ฟังก์ชัน clear_internal_headers ของ pingora-origin ซึ่งลบเฮดเดอร์สำหรับการกำหนดเส้นทางภายใน การวัดผล และการปรับให้เหมาะสม ออกจากคำขอที่ไม่ได้แคชก่อนออกจาก Cloudflare และทำงานบนเส้นทางคำขอ 35 ล้านครั้งต่อวินาที
  • การใช้งานเดิมพยายามลบเฮดเดอร์ภายในมากกว่า 100 รายการในทุกคำขอ ใช้เวลาเฉลี่ย 3.65µs และกินเวลา CPU 1.71% ของ pingora-origin ทั้งหมด หรือเทียบเท่ากับ CPU core 680 คอร์จาก 40,000 compute-seconds/s
  • วิธีวนอ่านเฮดเดอร์ของคำขอจริงก่อนทำได้เร็วขึ้น 2.39 เท่า โดยเฉลี่ย 1.53µs แต่การลด CPU โดยรวมในเชิงทฤษฎีทำได้เพียง 0.993% จึงต้องการโครงสร้างค้นหาที่ดีกว่า
  • การใช้งาน trie แบบใหม่ลดเวลาเฉลี่ยลงเหลือ 0.93µs และจากการ sampling ที่รันในโปรดักชันตั้งแต่กรกฎาคม 2024 การใช้ CPU จริงของ clear_internal_headers ก็ลดลงเหลือ 0.34%

ต้นทุนที่ Cloudflare ต้องการลด

  • เครือข่ายทั่วโลกของ Cloudflare ประมวลผลคำขอ HTTP เฉลี่ย มากกว่า 60 ล้านครั้งต่อวินาที
  • การปรับให้เหมาะสมครั้งนี้เริ่มจาก Pingora ซึ่งเป็นแกนหลักของบริการพร็อกซีที่ใช้ Rust และบริการโปรดักชัน pingora-origin ที่ทำงานอยู่บนมัน
  • pingora-origin รับผิดชอบขั้นตอนสุดท้ายในการส่งคำขอที่ไม่ได้แคชของผู้ใช้ไปยังเซิร์ฟเวอร์ปลายทางจริงหรือ origin
  • บริการนี้ต้องลบข้อมูลที่ใช้สำหรับการกำหนดเส้นทางภายใน การวัดผล และการปรับให้เหมาะสม ออกจากเฮดเดอร์ ก่อนที่คำขอจะออกจากโครงสร้างพื้นฐานของ Cloudflare
  • ทั่วโลก คำขอที่ออกจาก pingora-origin ณ เวลาที่เขียนอยู่ที่ 35 ล้านครั้งต่อวินาที

ฟังก์ชันคอขวด: clear_internal_headers

  • ฟังก์ชันที่เป็นปัญหาอยู่บนเส้นทางที่ร้อนมากซึ่งทำงานกับทุกคำขอ
// 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);
    });
}
  • ฟังก์ชันเล็ก ๆ เพียงฟังก์ชันเดียวนี้ใช้เวลา CPU ของ pingora-origin ทั้งหมด มากกว่า 1.7%
  • เวลา CPU รวมของ pingora-origin คือ 40,000 compute-seconds ต่อวินาที ซึ่งมีขนาดเทียบเท่ากับ CPU core ที่ทำงานเต็ม 40,000 คอร์รันบริการนี้อย่างเดียว
  • ในจำนวนนั้น 1.7% หรือประมาณ 680 CPU core ถูกใช้ไปกับการประเมิน clear_internal_headers เพียงอย่างเดียว

การวัดค่าพื้นฐานและการปรับปรุงครั้งแรก

  • ใช้ Rust crate criterion ในการวัดประสิทธิภาพ
  • Criterion รวมผลการรันแบบแยกหลายครั้งเพื่อวัดเวลาโค้ด Rust ในระดับ นาโนวินาที และยังให้ฟีดแบ็กเรื่องประสิทธิภาพที่ดีขึ้นหรือถดถอยตามเวลา
  • อินพุต benchmark คือชุดคำขอจำนวนมากที่สังเคราะห์ขึ้นให้เฮดเดอร์ภายในและเฮดเดอร์ที่ไม่ใช่ภายในกระจายอย่างสม่ำเสมอ
  • เวลาเฉลี่ยของ clear_internal_headers แบบเดิมวัดได้ 3.65µs

  • กลับทิศทางการค้นหา

    • โค้ดเดิมเรียก request_header.remove_header(h) กับทุกรายการในลิสต์เฮดเดอร์ภายใน ดังนั้นหากมีเฮดเดอร์ภายในมากกว่า 100 รายการ ก็จะประเมินมากกว่า 100 ครั้งต่อคำขอ
    • จำนวนเฮดเดอร์ของคำขอโดยเฉลี่ยอยู่ที่ 10~30 รายการ ซึ่งน้อยกว่า 100 มาก จึงลดจำนวนครั้งที่ต้องอ่านได้โดยวนผ่านเฮดเดอร์ของคำขอจริงแล้วค้นหาในเซตของเฮดเดอร์ภายใน
    • ใน http::HeaderMap ของ Rust ยังไม่มี retain จึงต้องรวบรวมเฮดเดอร์ภายในที่จะลบไว้ในขั้นตอนแยกต่างหากก่อน แล้วค่อยลบ
    • การเปลี่ยนแปลงนี้เพียงอย่างเดียวลดเวลาเฉลี่ยจาก 3.65µs เหลือ 1.53µs ทำให้เร็วขึ้น 2.39 เท่า
    • ในเชิงทฤษฎี การใช้ CPU โดยรวมจะลดจาก 1.71% เหลือ 0.717% โดยส่วนที่ประหยัดได้คือ 0.993%

การสำรวจโครงสร้างข้อมูลค้นหาที่ดีกว่า

  • หลังจากเปลี่ยนทิศทางการค้นหาแล้ว ก็สามารถเลือกได้ว่าจะเก็บลิสต์เฮดเดอร์ภายในแบบคงที่ไว้ในโครงสร้างข้อมูลแบบใด
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 แต่ hash ของคีย์สตริงต้องอ่านทุกไบต์ ดังนั้นแม้จะเป็นเวลาคงที่เมื่อเทียบกับขนาดตาราง แต่เมื่อเทียบกับ ความยาวคีย์ L ก็ยังเป็นเวลาเชิงเส้น
  • เป้าหมายคือหาโครงสร้างข้อมูลที่มีพฤติกรรมการอ่านดีกว่า O(L) เมื่อเทียบกับความยาวคีย์

  • ทางเลือกที่พิจารณา

    • เซตแบบเรียงลำดับอย่าง BTreeSet ใช้การค้นหาแบบอิงการเปรียบเทียบ และให้พฤติกรรม O(log(L)) เมื่อเทียบกับความยาวคีย์ แต่เมื่อเทียบกับขนาดของเซตก็ยังใช้เวลาแบบลอการิทึมด้วย
    • FST ซึ่งเป็นเซตแบบเรียงลำดับที่เร็ว ก็ยังช้ากว่า hashmap มาตรฐานประมาณ 50ns ใน benchmark
    • state machine เช่น parser หรือ regular expression รับอินพุตทีละหน่วยและตัดสินใจในแต่ละขั้นว่าจะประเมินต่อหรือไม่ จึงระบุสตริงที่ไม่ตรงกันได้อย่างรวดเร็ว
    • เฮดเดอร์ภายในมีเฉลี่ยเพียง 1~2 รายการ ต่อคำขอ จึงเหมาะกับสถานการณ์ที่ส่วนใหญ่เป็นกรณีไม่ตรงกัน
    • การใช้งาน clear_internal_headers ด้วย regular expression ใช้เวลานานกว่าโซลูชันที่ใช้ hashmap ประมาณ 2 เท่า แต่ก็ยังเป็นผลลัพธ์ที่เร็วเมื่อพิจารณาว่าไม่ใช่เครื่องมือที่ขึ้นชื่อเรื่องความเร็วดิบ

เหตุผลที่ trie เหมาะสม

  • trie เป็นโครงสร้างข้อมูลแบบต้นไม้ที่มักใช้สำหรับการค้นหาคำนำหน้าหรือ autocomplete ในชุดสตริงที่ทราบอยู่แล้ว
  • แต่ละโหนดของ trie แทน สตริงย่อย ที่พบในชุดสตริงเริ่มต้น และการเชื่อมต่อระหว่างโหนดแทนอักขระที่สามารถตามหลังคำนำหน้าเฉพาะได้
  • เมื่อเริ่มจาก root node จะลดพื้นที่ค้นหาได้ตั้งแต่อักขระแรก ๆ ที่เป็นไปได้ จึงคัดสตริงที่ไม่รวมอยู่ในชุดออกได้อย่างรวดเร็ว
  • การอ่าน trie ให้พฤติกรรม O(log(L)) สำหรับกรณีไม่ตรงกัน แต่กรณีตรงกันยังคงเป็น O(L)
  • เฮดเดอร์คำขอมากกว่า 90% ไม่ใช่เฮดเดอร์ภายใน จึงเหมาะกับ use case นี้ที่มีกรณีไม่ตรงกันจำนวนมาก

  • ข้อจำกัดของการใช้งาน trie ที่มีอยู่

    • benchmark การใช้งาน trie หลายตัวใน crates.io แล้ว แต่ผลลัพธ์ต่ำกว่าที่คาด
    • trie ส่วนใหญ่ถูกออกแบบมาสำหรับ use case เช่น autocomplete ที่ตอบสนองต่อเหตุการณ์จากคีย์บอร์ด ไม่ได้ให้ความสำคัญกับการปรับให้เหมาะสมของ hot path ที่มีคำขอหลายสิบล้านครั้งต่อวินาที
    • การใช้งานเดิมที่พบว่าเร็วที่สุดคือ radix_trie แต่ยังช้ากว่า hashmap 1µs
    • สุดท้ายจึงเขียนการใช้งาน trie ใหม่ให้เหมาะกับ use case นี้

trie-hard และผลลัพธ์ในโปรดักชัน

  • Cloudflare เปิดตัว Rust crate โอเพนซอร์สตัวใหม่ trie-hard

  • trie-hard เก็บความสัมพันธ์ของโหนดไว้ในบิตของจำนวนเต็มแบบ unsigned และเก็บทั้งต้นไม้ไว้ใน บล็อกหน่วยความจำที่ต่อเนื่องกัน เพื่อให้ได้ความเร็ว

  • ใน benchmark trie-hard ลดเวลาเฉลี่ยของ clear_internal_headers ลงเหลือ 0.93µs

  • การใช้ CPU ที่คาดการณ์ไว้คือ 0.43% ซึ่งเมื่อเทียบกับ 1.71% เดิมแล้ว ส่งผลให้การใช้คอมพิวต์โดยรวมของ pingora-origin ลดลง 1.28%

  • ผลการ sampling จริง

    • trie-hard รันอยู่ในโปรดักชันตั้งแต่กรกฎาคม 2024
    • การวัดประสิทธิภาพเก็บข้อมูลด้วยการ sampling สถิติของ stack trace ตามเวลา
    • ประเมินการใช้ CPU ของฟังก์ชันจากสัดส่วนของ sample ที่มีฟังก์ชันนั้นรวมอยู่
    • ผลการ sampling ในโปรดักชันโดยรวมใกล้เคียงกับการคาดการณ์จาก benchmark ในเครื่อง
    การใช้งาน sample ของ stack trace ที่มี clear_internal_headers การใช้ CPU จริง การใช้ CPU ที่คาดการณ์
    Original 19 / 1111 1.71% n/a
    Hashmap 9 / 1103 0.82% 0.72%
    trie-hard 4 / 1171 0.34% 0.43%

ข้อสรุปในมุมมองการดำเนินงาน

  • ก่อนจะเขียนโครงสร้างข้อมูลใหม่ ต้องรู้ก่อนว่าโค้ดช้าตรงไหนและช้าแค่ไหน
  • การใช้ flame graph, profiling และเครื่องมือ benchmarking ช่วยให้พบการประหยัดที่มีความหมายได้แม้ในฟังก์ชันระดับไมโครวินาที
  • การปรับให้เหมาะสมกับงานที่สั้นมากอยู่แล้วอาจดูเหมือนเรื่องเล็กน้อย แต่ในระดับหลายสิบล้านคำขอต่อวินาที การปรับปรุงเล็ก ๆ จะสะสมจนลดการใช้คอมพิวต์โดยรวมได้

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

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

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

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

    • ในฐานะอดีตพนักงาน สิ่งที่ทั้งน่าสนใจและน่ากลัวคือ ใน ผลิตภัณฑ์ serverless อย่าง Workers เคยสามารถตั้งค่าเฮดเดอร์ภายในบางตัวได้ และอาจเกิดเรื่องแย่ ๆ ได้สารพัด เช่นบั๊กที่เห็นได้ชัดเกี่ยวกับ cf-cache-status
    • เคยทำงานในองค์กรความปลอดภัย IT ของบริษัทยักษ์ใหญ่หลายแห่ง แม้แต่ที่ที่ใส่ใจกับเฮดเดอร์มาก ๆ ก็ใช้เฮดเดอร์ในลักษณะคล้าย Cloudflare
      รวมถึงการลบเฮดเดอร์ภายในทั้งสองทิศทางที่ edge proxy และทำแบบนั้นกับขาเข้าด้วย
    • ผมเห็นว่าทางแก้อื่น ๆ ที่เสนอมาก็มีปัญหาคล้ายกันหลายอย่างด้วยซ้ำ แม้แต่ปัญหาบางข้อที่ยกมาก็น่าจะใช้กับทางแก้อื่น ๆ เหล่านั้นได้เช่นกัน
      วิธีแบบรายการมีข้อเสีย แต่ก็มีข้อดีมากมาย เวลาแตะถึงข้อบกพร่องที่เป็นไปได้ของแนวทางนี้ มักดูเหมือนละเลยประวัติและความยากลำบากที่เกิดขึ้นในสเกลของ Cloudflare รายการแบบ enum เป็นวิธีที่ง่ายและยืดหยุ่นที่สุด และไม่ต้องมีการตกลงล่วงหน้าเกี่ยวกับโครงสร้างคีย์ของเฮดเดอร์ เมื่อคิดถึงจำนวนทีมของ Cloudflare และความเป็นไปได้ในการซื้อกิจการด้านเทคโนโลยี จุดนี้น่าจะสำคัญมาก
    • ผมก็คิดอย่างนั้นเหมือนกัน แต่ระบบโตขึ้นเรื่อย ๆ ตามเวลา และเริ่มใช้ HTTP header เพื่อสารพัดวัตถุประสงค์ การปรับแต่งนี้ทำให้สถานการณ์ดีขึ้น แต่ทางแก้จริงที่กำลังดำเนินอยู่คือการใช้ กลไกแยกต่างหากสำหรับ IPC และเลิกใช้ HTTP header ไปโดยสิ้นเชิง
    • อีกไอเดียหนึ่งคือ บังคับให้เพิ่มเฮดเดอร์ภายในที่จะไม่ส่งออกไปภายนอกไว้เฉพาะช่วงต้นของรายการเฮดเดอร์ หรือเติม hash table ของทุก request ไว้ล่วงหน้าด้วยเฮดเดอร์ภายในที่จะถูกลบ
      ถ้าเติมไว้ล่วงหน้า ก็เท่ากับผสานไอเดียเหล่านี้เข้าด้วยกัน และทำให้จำนวนเฮดเดอร์ภายในต่อ request คงที่ เมื่อถึงจุดนั้นก็ใช้ linked hash table ที่รักษาลำดับการสร้างไว้ แล้วลบแค่ N รายการแรกออกจากรายการสุดท้ายที่จะส่งกลับไปยังไคลเอนต์ก็พอ

  • ผมลองคิดชั่วครู่ถึงผลของการแมปอักขระ UTF-8 ด้วย บิตมาสก์ ตอนแรกดูไม่ค่อยฉลาดนัก แต่แล้วก็นึกได้ว่า 32 บิตสามารถเก็บ a-z กับอักขระพิเศษได้ 6 ตัว และ 64 บิตก็เก็บตัวพิมพ์ใหญ่ A-Z กับอักขระพิเศษเพิ่มอีก 6 ตัวได้
    สำหรับ HTTP header นี่เป็นพื้นที่ที่มากพอ และแค่ mask กับเปรียบเทียบจำนวนเต็มไม่กี่ตัว ก็กลายเป็นอัลกอริทึมจับคู่ที่เร็วมาก การดูว่าอักขระใดตรงกับบิตไหนก็เป็นเพียงการ lookup ตาราง 256 word ครั้งเดียว
    สิ่งที่ผู้เขียนตกหล่นไปคือ เทคนิคนี้ในเชิงเทคนิคแล้วคือ Bloom filter เหตุผลที่ของพวกนี้น่าสนใจก็คือ มันเป็นการปรับแต่งจากยุคที่ทรัพยากรคอมพิวต์จำกัดกว่าตอนนี้มาก ในกรณีนี้มาจากปี 1970 แต่เรายังใช้การปรับแต่งเก่าแบบเดียวกันนี้อยู่ตามมุมต่าง ๆ ของโลกจริง
    https://en.wikipedia.org/wiki/Bloom_filter

    • ระหว่าง trie-hard กับ Bloom filter มีความต่างกันมาก Bloom filter เป็นแบบความน่าจะเป็นและใช้ hashing เหมาะเมื่อยอมรับ false positive ที่พบได้น้อยเพื่อแลกกับการต้องไม่มี false negative แต่สิ่งที่ต้องการที่นี่ไม่ใช่แบบนั้น ที่นี่ต้องการความถูกต้อง และตัว hashing เองก็คือขั้นตอนที่ต้องเอาชนะให้ได้
      กลับกัน สิ่งนี้ใกล้เคียงกับเวอร์ชันปรับปรุงหรือดัดแปลงของ อัลกอริทึม Liang ที่ใช้เก็บพจนานุกรมการใส่ยัติภังค์ใน TeX มากกว่า วิทยานิพนธ์พูดถึงอัลกอริทึมของ Bloom ในชื่อ “superimposed coding” ซึ่งทำให้นึกถึงยุคที่หน่วยความจำเป็นทรัพยากรล้ำค่าที่สุดอย่างแรง คุณน่าจะชอบ ^_^
      https://tug.org/docs/liang/liang-thesis.pdf
    • Bloom filter จะมีประโยชน์เมื่อชุดข้อมูลมีขนาดใหญ่ และต้นทุนการคำนวณ hash หลายตัวต่อรายการถูกกว่าต้นทุนการค้นหาในชุดข้อมูลเดิม ที่นี่บอกว่าแม้แต่ hash เดียวก็แพง ดังนั้น Bloom filter จึงน่าจะช้ากว่า hash map เดิมมาก

  • ข้อมูลที่เสนอมาเพื่อพิสูจน์ประโยชน์นั้นจริง ๆ แล้วมี กำลังของการทดสอบ ไม่พอที่จะแสดงให้เห็นเรื่องนั้น ตัวอย่างยังไม่เพียงพอ
    ถ้าวิเคราะห์แบบง่ายมากใน R ก็เป็น prop.test(c(9, 4), c(1103,1171)) และในการทดสอบความเท่ากันของสัดส่วนสองค่าพร้อม continuity correction จะได้ค่า p-value 0.222
    p-value 0.22 ไม่ได้ต่ำกว่าค่า 0.05 วิเศษ และช่วงความเชื่อมั่น 95% ชี้ว่า trie อาจจะแย่กว่าเล็กน้อยจริง ๆ ก็ได้
    ดูจากการวิเคราะห์ก่อนหน้าแล้ว trie น่าจะดีกว่า และก็มีหลักฐานอ่อน ๆ อยู่ แต่ควรเก็บตัวอย่างให้มากกว่านี้มาก ๆ เพื่อให้มั่นใจว่าดีกว่าแค่ไหน

  • สำหรับเป้าหมายที่จะวิเคราะห์ประสิทธิภาพ การอธิบายจำนวนการเปรียบเทียบด้วย Big-O notation ดูไม่ค่อยเข้าที่ การเปรียบเทียบใช้ราว 1 cycle และด้วย instruction-level parallelism กับ SIMD ก็ทำได้หลายครั้งในหนึ่ง cycle
    คอขวดจริงและต้นตอของความช้าคือหน่วยความจำ การเข้าถึงหน่วยความจำอาจใช้หลายพัน cycle และถ้าต้องมี TLB walk หรือ OS interrupt ก็อาจขึ้นไปถึงหลายหมื่นหรือหลายแสน cycle ได้ ถ้าอยากใช้ Big-O ก็ควรใช้เพื่อประมาณ จำนวน cache miss
    ถ้าเป็นผมคงใช้ฟังก์ชัน perfect hash แบบปรับแต่งเองกับทริก popcount ของ Phil Bagwell น่าจะเร็วกว่าทางแก้อื่น ๆ ที่ต้อง lookup หน่วยความจำหลายครั้ง
    CPU เร็ว ส่วนหน่วยความจำช้า

  • ผมไม่ได้เชี่ยวชาญเรื่องการปรับแต่งโครงสร้างข้อมูลมากนัก แต่โดยเฉพาะเมื่อคำนึงว่าตารางที่เป็นเป้าหมายในการค้นหาเป็นแบบคงที่ ก็แปลกใจที่พวกเขาตัด ตารางแฮช ออกเร็วเกินไป ยากจะเชื่อว่าตารางแฮชที่ปรับแต่งเป็นพิเศษจะไม่เร็วกว่า implementation แบบ trie ของพวกเขา

    • ฟังก์ชันแฮชไม่สามารถตรวจแค่ไบต์แรกแล้วปฏิเสธสตริงได้ มันเป็นไปไม่ได้
      สำหรับการใช้งานนี้ นั่นคือข้อได้เปรียบที่แฮชตามไม่ทัน เทคนิคที่เหลือคือการลด constant factor ของ trie ให้มากพอจนข้อได้เปรียบตั้งต้นนี้สะท้อนออกมาในประสิทธิภาพจริง
    • มี FxHashMap ที่เร็วกว่า std::collections::HashMap: https://github.com/rust-lang/rustc-hash
      ถ้ารายการคงที่มีประมาณ 100 รายการ o1hash ก็น่าจะใช้ได้: https://github.com/rurban/smhasher/blob/master/o1hash.h
    • ในบทความบอกว่า โอเวอร์เฮด ของ hashing ทำให้มันช้ากว่า trie

  • บทความนี้สร้างชุด to_remove ด้วยโครงสร้างข้อมูลเจ๋ง ๆ แล้ววนผ่านมันเพื่อลบออกจาก header map หลัก
    การเรียก remove_header ดูเหมือนจะเป็นโค้ดนี้: https://docs.rs/pingora-http/0.3.0/src/pingora_http/lib.rs.html#576
    ฟังก์ชันนี้เรียก .remove() บนโครงสร้างข้อมูลอีกสองตัว และทั้งคู่สุดท้ายก็ไหลลงไปที่โค้ดขนาดใหญ่นี้: https://docs.rs/http/latest/src/http/header/map.rs.html#1550

  • ในที่สุดก็มีบล็อกโพสต์ที่พูดถึง trie แล้ว ปัญหา trie ใน LeetCode ไม่สูญเปล่าสินะ ;)

    • เคยใช้ในโค้ดจริงมาก่อน สำหรับงานบางแบบมันค่อนข้างเข้าใจง่าย ครั้งล่าสุดที่ใช้ trie คือทำ lookup ที่อยู่ และถึงขั้นใช้ generator ด้วย เรียกว่าชีวิตจริงโดน LeetCode สองดอกพร้อมกัน
      ถึงอย่างนั้นก็ไม่ใช่เครื่องมือที่หยิบมาใช้บ่อยแน่นอน
    • ในตัวตรวจสะกดหรือตัวตรวจไวยากรณ์ที่เร็ว ๆ จะพบ trie ได้
    • เมื่อไม่นานมานี้มีโอกาสได้ใช้ hybrid trie แบบดัดแปลงในงานจริง และสนุกกับการ implement มาก ยังมีช่องให้ optimize ได้อีกเยอะ
      เป็น parser user agent สำหรับ Go: https://github.com/medama-io/go-useragent
      ปกติปัญหาแบบนี้พึ่งพาการ parse regex จำนวนมาก เลยดีที่ได้ลองแนวทางที่ใหม่กว่านั้น
    • ใน build tool หรือสคริปต์วิเคราะห์โค้ดที่มีความซับซ้อนระดับกลาง บางทีก็ได้ใช้ trie/radix tree เมื่อต้องเก็บข้อมูลของ file path จำนวนมาก การแยก prefix ร่วมออกมาช่วยประหยัดหน่วยความจำได้มากและยังค่อนข้างเข้าใจง่าย
    • ในโปรแกรมสร้างและเล่น Scrabble trie สำคัญมาก ผมเคยทำมาหลายตัว และโครงสร้างที่เร็วที่สุดคือ compressed trie ที่มี representation ของคำแบบหมุนได้

  • ถ้าชุดรายการที่ต้อง match เป็นแบบคงที่ ก็สงสัยว่าพวกเขาลอง perfect hash table แล้วหรือยัง หลังจากคำนวณเลขคณิตไม่กี่ครั้งก็น่าจะลดเหลือการเปรียบเทียบสตริงครั้งเดียว น่าสนใจว่าจะเทียบกับ trie เป็นอย่างไร

    • ผมก็คิดแบบนั้นทันทีเหมือนกัน เพียงแต่ perfect hash เองก็ยังเป็น O(n) ตามความยาวคีย์ เพราะฟังก์ชันแฮช และนั่นแหละคือส่วนที่พวกเขาพยายามหลีกเลี่ยง
      ในทางทฤษฎี ถ้าใช้ regex มันจะ match ด้วย state machine ดังนั้นกรณีแย่สุดควรได้ประสิทธิภาพ O(k) คล้าย trie แต่เท่าที่ผมเข้าใจ ไลบรารี regex มักใช้ backtracking มากกว่าสร้าง state machine จริง ๆ ประสิทธิภาพจึงไม่ใช่ O(k) อีกต่อไป
      ก็น่าแปลกใจที่พวกเขาหาไลบรารี regex ที่ทำงานบน state machine และมีประสิทธิภาพดีอยู่แล้วไม่เจอ มันน่าจะมีประสิทธิภาพใกล้เคียง trie แต่ในทางปฏิบัติ ปัจจัยอย่างรูปแบบการเข้าถึงหน่วยความจำหรือประสิทธิภาพของคำสั่งเลขคณิตบางอย่างมีผลลึกกว่า จึงเดายากอยู่ดี

  • ได้ลองใช้ Bloom filter ขนาดเล็กมากหรือเปล่า? ถ้าประมวลผล header key อย่างรวดเร็วคล้าย convolution แล้วเทียบกับ Bloom filter ก็น่าจะหลีกเลี่ยงการเดิน trie ได้เกือบทั้งหมดในกรณีส่วนใหญ่ ด้วยต้นทุนเพียงไม่กี่ cycle
    ดูเหมือนจะมีตัวเลือกอย่าง SIMD, คำสั่ง CRC ในตัว, ขนาด Bloom filter 256 บิตด้วย

    • ไม่รู้ว่าทีมนั้นได้ทำหรือไม่ แต่ Bloom filter ไม่ใช่ยาครอบจักรวาล: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/
    • เมื่อพิจารณาว่าใน implementation trie ของพวกเขา filter ของแต่ละ node ก็คล้ายกับ Bloom filter อยู่แล้ว แนวทางนี้จึงค่อนข้างใกล้กัน เห็นด้วยว่าการตรวจช่วงที่กว้างขึ้นของสตริงในครั้งเดียวอาจเร่งความเร็วได้อย่างมาก
      แนวทางที่ง่ายกว่านั้นก็อาจคุ้มค่า การวิเคราะห์ความถี่ hit/miss ของ node ใน trie อาจพบตำแหน่งอักขระบางตำแหน่งที่มีอัตราล้มเหลวสูงกว่าอักขระตัวแรก ถ้าตรวจตำแหน่งพิเศษเหล่านั้นก่อนก็อาจเร็วขึ้นได้ แน่นอนว่าต้องอาศัยสมมติฐานว่า header data มีรูปแบบค่อนข้างสม่ำเสมอโดยธรรมชาติ
    • นั่นน่าจะต้องคำนวณแฮช ซึ่งดูเหมือนถูกตัดออกไปแล้วเพราะต้นทุนช้าเกินไป

  • ความเห็นของผมคือแบบนี้ อย่างแรก นี่เป็นงานที่คุ้มทำไหม? ดูเหมือนจะประหยัดได้ประมาณ 500 CPU cores แต่ไม่รู้ว่านี่หมายถึงคอร์จริง ๆ หรือรวมคอร์แบบ hyper-threaded ด้วย
    ผมไม่รู้ต้นทุนของ Cloudflare แต่ก็น่าจะเทียบได้กับเซิร์ฟเวอร์จำนวนหลักหน่วย และเงินที่ประหยัดได้ก็คงอยู่ระดับหลายหมื่นดอลลาร์ต่อปี ไม่ใช่จำนวนที่มองข้ามได้ แต่ก็ไม่แน่ใจว่าจะคาดหวัง ROI เป็นบวกเมื่อเทียบกับการลงทุนด้านวิศวกรรมได้หรือไม่
    อย่างที่สอง ถ้าจะลงรายละเอียดถึงขนาดนี้ ผมก็สงสัยว่าได้พิจารณาแนวทางใส่ฟิลเตอร์ในขั้นตอน deserialization เพื่อไม่ให้ header ถูกสร้างขึ้นมาตั้งแต่แรกหรือเปล่า

    • อาจจะแค่หลายหมื่นดอลลาร์ก็จริง แต่การประหยัดนั้นจะอยู่ถาวร
      ประหยัดไฟต่อเนื่อง และลดการปล่อยคาร์บอนด้วย
      ผมชอบเห็นบริษัทพยายามทำอะไรสักอย่างให้ เร็วขึ้น 1% มากกว่าทำเรื่องโง่ ๆ อย่างเอา AI ไปวิเคราะห์ header เพื่อพยายามขายรองเท้าแตะ
    • เป็นกรณีมุมเล็กมาก ๆ แต่ก็เป็นเนื้อหาที่เปิดเผยต่อสาธารณะได้ง่ายด้วย มันกลายเป็น คอนเทนต์การตลาด ที่ทำให้ geek หลายร้อยคนมาถกกันว่าสิ่งที่ Cloudflare ทำสมเหตุสมผลไหม และใส่ใจประสิทธิภาพมากแค่ไหน
      มูลค่าของมันอาจเป็นล้านดอลลาร์ก็ได้
    • ผมไม่ค่อยเข้าใจประเด็นเรื่อง ROI เท่าไร ถ้าประหยัดได้ปีละ 40,000 ดอลลาร์เป็นเวลา 5 ปี ก็เท่ากับ 200,000 ดอลลาร์แล้ว ตามมาตรฐานฮังการีหรือโปแลนด์ นั่นคือเงินเดือนหลายปีของหลายคนเลย ไม่รู้ว่า Cloudflare มีสำนักงานที่นั่นหรือเปล่า
    • ถ้าเป็นแค่วิศวกรใช้เวลาไม่กี่วัน เงินที่ประหยัดได้ก็ดูคุ้มค่าพอแล้วไม่ใช่เหรอ?