Ngày đẹp trời của trie-hard: tiết kiệm 1% tài nguyên tính toán

Động lực

• Mạng lưới toàn cầu của Cloudflare xử lý hơn 60 triệu yêu cầu HTTP mỗi giây
• Sử dụng một crate Rust mã nguồn mở mới để giảm mức sử dụng CPU và cải thiện năng lực xử lý của CDN
• Pingora là cốt lõi của dịch vụ proxy dựa trên Rust của Cloudflare, và công ty đã mã nguồn mở nó
• Dịch vụ Pingora-origin có vai trò chuyển tiếp yêu cầu của người dùng đến đích thực tế
• Khi yêu cầu rời khỏi Cloudflare, cần thực hiện việc loại bỏ thông tin nội bộ
• Công việc này diễn ra rất thường xuyên và chiếm 1,7% mức sử dụng CPU

Benchmarking

• Sử dụng crate Rust Criterion để đo hiệu năng của hàm ở đơn vị nano giây
• Hàm clear_internal_headers ban đầu mất trung bình 3.65µs

Giảm thao tác đọc

• Giảm thao tác đọc bằng cách đảo ngược hướng loại bỏ header
• Thay đổi này cải thiện thời gian thực thi của hàm từ 3.65µs xuống 1.53µs
• Giảm mức sử dụng CPU từ 1.71% xuống 0.717%

Tìm kiếm cấu trúc dữ liệu

• Thử dùng hashmap để lưu trữ và tra cứu các header nội bộ
• Thời gian đọc của hashmap tăng tuyến tính theo độ dài khóa
• Thử các cấu trúc dữ liệu khác như tập hợp được sắp xếp hoặc máy trạng thái
• Cách triển khai dùng biểu thức chính quy chậm gấp đôi so với hashmap

Sử dụng trie

• Trie là cấu trúc dữ liệu dạng cây dùng cho tìm kiếm theo tiền tố hoặc hệ thống tự động hoàn thành
• Trie có thể nhanh chóng nhận diện trường hợp chuỗi không tồn tại
• Các triển khai trie hiện có chậm hơn hashmap
• Cloudflare đã phát triển trie-hard, một triển khai trie tối ưu hóa riêng của mình

Trie Hard

• trie-hard lưu quan hệ giữa các nút vào các bit của số nguyên và sử dụng bộ nhớ liên tục để tăng tốc
• Giảm thời gian thực thi của hàm clear_internal_headers xuống 0.93µs
• Giảm mức sử dụng CPU từ 1.71% xuống 0.43%
• Hiệu năng của trie-hard trong môi trường production thực tế khớp với benchmark

Kết luận

• Việc xác định và tối ưu các phần chậm trong mã là rất quan trọng
• Nhiều tối ưu nhỏ có thể cộng lại thành cải thiện hiệu năng lớn
• Connected Cloud của Cloudflare cung cấp các chức năng như bảo vệ mạng, tăng tốc ứng dụng Internet và phòng vệ trước tấn công DDoS

Tóm tắt của GN⁺

• Cloudflare giảm mức sử dụng CPU và cải thiện năng lực xử lý của CDN thông qua một crate mã nguồn mở mới dựa trên Rust
• Tối ưu hóa tác vụ loại bỏ header nội bộ trong dịch vụ Pingora-origin giúp giảm 1.28% mức sử dụng CPU
• Công ty đã phát triển trie-hard, một triển khai trie tối ưu hóa riêng, để cải thiện hiệu năng đáng kể
• Bài viết nhấn mạnh tầm quan trọng của tối ưu mã và lựa chọn cấu trúc dữ liệu, đồng thời cho thấy các tối ưu nhỏ có thể mang lại cải thiện hiệu năng lớn
• Các dự án có chức năng tương tự gồm NGINX, HAProxy, v.v.

[GN⁺]

Ý kiến trên Hacker News

• Đã đưa ra nhiều suy đoán về cách Cloudflare lưu trữ và loại bỏ các header nội bộ

  • Dùng một từ điển hoặc cấu trúc dữ liệu riêng
  • Một header duy nhất chứa toàn bộ metadata nội bộ
  • Gắn tiền tố cho mọi header để header nội bộ bắt đầu bằng I, còn bên ngoài bắt đầu bằng E
  • Mọi header nội bộ đều bắt đầu bằng "CFInt"
  • Không ngờ lại là cách coi một danh sách header cụ thể là header nội bộ
  • Web vốn đã đầy những tín hiệu mơ hồ và tên header khó hiểu
  • Thật lạ khi một công ty quy mô lớn như Cloudflare lại dùng một cơ chế dễ phát sinh lỗi như vậy

• Ban đầu cho rằng việc ánh xạ ký tự UTF-8 sang bitmask là không hiệu quả

  • 32 bit có thể chứa a-z và sáu ký tự đặc biệt
  • 64 bit có thể chứa chữ hoa A-Z và sáu ký tự đặc biệt
  • Cung cấp đủ không gian cho HTTP header và cho phép thuật toán đối sánh nhanh
  • Kỹ thuật này là Bloom Filter
  • Đây là kỹ thuật được phát triển trong thời kỳ tài nguyên hạn chế vào thập niên 1970 nhưng đến nay vẫn được dùng hiệu quả

• Có nghi ngờ liệu tối ưu hóa của Cloudflare có đáng giá hay không

  • Đã tiết kiệm khoảng 500 lõi CPU
  • Không biết chi phí của Cloudflare, nhưng dự đoán tiết kiệm được cỡ vài chục nghìn USD
  • Nghi ngờ liệu có thể kỳ vọng ROI tích cực cho phần kỹ thuật hay không
  • Có thể tốt hơn nếu áp dụng bộ lọc ở giai đoạn deserialize để header không bị tạo ra ngay từ đầu

• Không rành về tối ưu hóa cấu trúc dữ liệu, nhưng ngạc nhiên khi hash table bị loại bỏ quá nhanh

  • Khi tra cứu bảng tĩnh, tưởng rằng hash table sẽ nhanh hơn

• Dùng một cấu trúc dữ liệu cầu kỳ để xác định các mục cần loại bỏ rồi xóa chúng khỏi header map dựa trên đó

  • Cung cấp liên kết đến đoạn mã có lời gọi remove_header

• Cuối cùng cũng có một bài blog dùng trie

  • Những bài toán liên quan đến trie hóa ra không vô ích

• Tò mò không biết họ có thử một Bloom Filter nhỏ hay chưa

  • Một phép convolution nhanh trên khóa header và kiểm tra Bloom Filter có thể tránh phải duyệt trie

• Tò mò không biết họ có thử perfect hash table khi đối sánh một tập mục tĩnh hay chưa

  • Có thể rút xuống còn vài phép toán số học và một lần so sánh chuỗi duy nhất

• Phần tối ưu hóa này khá thú vị

  • Tò mò liệu có thể gắn thẻ header là nội bộ ngay khi tạo request hay không
  • Như vậy việc lọc ở đầu ra sẽ đơn giản hơn

• Tò mò vì sao crate regex lại không hoạt động tốt hơn

  • Đáng ra nó phải biên dịch việc tìm nhiều chuỗi literal thành automaton Aho-Corasick