Một ngày tuyệt vời của trie-hard: tiết kiệm 1% chi phí tính toán
(blog.cloudflare.com)- Cloudflare đã công bố mã nguồn mở Rust crate trie-hard nhằm giảm mức sử dụng CPU của proxy viết bằng Rust Pingora trên mạng xử lý trung bình hơn 60 triệu HTTP request mỗi giây
- Điểm nghẽn nằm ở hàm
clear_internal_headerscủapingora-origin, hàm này loại bỏ các header dùng cho định tuyến nội bộ, đo lường và tối ưu hóa khỏi các request không được cache khi rời Cloudflare, và chạy trên đường đi của 35 triệu request mỗi giây - Cách triển khai cũ cố gắng xóa hơn 100 header nội bộ trong mỗi request, mất trung bình 3.65µs, và tiêu tốn 1,71% tổng thời gian CPU của
pingora-origin, tương đương 680 lõi CPU trong tổng 40.000 compute-seconds/s - Cách duyệt qua header thực tế của request trước đạt trung bình 1.53µs, nhanh hơn 2,39 lần, nhưng mức giảm CPU toàn cục theo lý thuyết chỉ đạt 0,993%, nên cần một cấu trúc tra cứu tốt hơn
- Triển khai trie mới đã hạ thời gian thực thi trung bình xuống 0.93µs, và trong dữ liệu lấy mẫu chạy production từ tháng 7/2024, mức sử dụng CPU thực tế của
clear_internal_headersgiảm còn 0,34%
Chi phí mà Cloudflare muốn cắt giảm
- Mạng toàn cầu của Cloudflare xử lý trung bình hơn 60 triệu HTTP request mỗi giây
- Đợt tối ưu hóa này bắt đầu từ Pingora, thành phần cốt lõi của dịch vụ proxy viết bằng Rust, và dịch vụ production
pingora-originchạy phía trên nó pingora-originđảm nhiệm bước cuối cùng là gửi các request không được cache của người dùng tới origin, tức máy chủ đích thực tế- Dịch vụ này phải xóa khỏi header các thông tin dùng cho định tuyến nội bộ, đo lường và tối ưu hóa trước khi request rời khỏi hạ tầng Cloudflare
- Trên toàn cầu, số request rời
pingora-originvào thời điểm bài viết được viết là 35 triệu mỗi giây
Hàm gây nghẽn: clear_internal_headers
- Hàm gây vấn đề này nằm trên một đường thực thi rất nóng, được gọi với mọi request
// 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);
});
}
- Chỉ riêng hàm nhỏ này đã dùng hơn 1,7% tổng thời gian CPU của
pingora-origin - Tổng thời gian CPU của
pingora-originlà 40.000 compute-seconds mỗi giây, tương đương quy mô 40.000 lõi CPU bão hòa chỉ để chạy dịch vụ này - Trong đó, 1,7%, tức khoảng 680 lõi CPU, chỉ được dùng để đánh giá
clear_internal_headers
Đo chuẩn và cải tiến đầu tiên
- Cloudflare dùng Rust crate criterion để đo hiệu năng
- Criterion tổng hợp nhiều lần chạy cô lập để đo thời gian code Rust ở độ phân giải nano giây, đồng thời cung cấp phản hồi về cải thiện hay suy giảm hiệu năng theo thời gian
- Đầu vào benchmark là một tập request tổng hợp lớn với phân bố đồng đều giữa header nội bộ và không nội bộ
- Thời gian thực thi trung bình của
clear_internal_headersbản cũ được đo là 3.65µs -
Đảo hướng tra cứu
- Mã cũ gọi
request_header.remove_header(h)cho từng mục trong danh sách header nội bộ, nên nếu có hơn 100 header nội bộ thì mỗi request sẽ bị đánh giá hơn 100 lần - Số header trong một request trung bình thực tế thấp hơn nhiều, chỉ khoảng 10–30, nên duyệt các header thực có trong request rồi tra trong tập header nội bộ sẽ giảm số lần đọc
- Rust
http::HeaderMaphiện vẫn chưa córetain, nên cần gom riêng các header nội bộ cần xóa ở một bước trước rồi mới xóa - Chỉ với thay đổi này, thời gian thực thi trung bình giảm từ 3.65µs xuống 1.53µs, nhanh hơn 2,39 lần
- Về mặt lý thuyết, mức dùng CPU toàn cục giảm từ 1,71% xuống 0,717%, tức tiết kiệm 0,993%
- Mã cũ gọi
Tìm kiếm cấu trúc dữ liệu tra cứu tốt hơn
- Sau khi đảo hướng tra cứu, Cloudflare có thể lựa chọn cấu trúc dữ liệu để lưu danh sách header nội bộ tĩnh
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);
});
}
- Thử nghiệm đầu tiên là
std::HashMap, nhưng băm khóa chuỗi phải đọc mọi byte, nên dù là thời gian hằng theo kích thước bảng, nó vẫn là thời gian tuyến tính theo độ dài khóa L - Mục tiêu là tìm một cấu trúc dữ liệu có hành vi đọc tốt hơn O(L) theo độ dài khóa
-
Các phương án đã xem xét
- Tập có thứ tự như
BTreeSetdùng tìm kiếm dựa trên so sánh, cho độ phức tạp O(log(L)) theo độ dài khóa, nhưng cũng phải chịu thời gian log theo kích thước tập - FST, một tập có thứ tự rất nhanh, trong benchmark vẫn chậm hơn hash map chuẩn khoảng 50ns
- Máy trạng thái như parser hay regex nhận đầu vào từng đơn vị và quyết định ở mỗi bước có tiếp tục đánh giá hay không, nên có thể nhanh chóng nhận diện chuỗi không khớp
- Điều này rất hợp với bối cảnh mà mỗi request trung bình chỉ có 1–2 header nội bộ, nên đa số là trường hợp phủ định
- Một bản triển khai
clear_internal_headersdùng regex mất thời gian khoảng gấp đôi so với lời giải dựa trên hash map, nhưng vẫn là kết quả nhanh nếu xét rằng regex không phải công cụ nổi tiếng về tốc độ thô
- Tập có thứ tự như
Vì sao trie là lựa chọn phù hợp
- trie là một cấu trúc dữ liệu dạng cây thường được dùng cho tìm kiếm tiền tố hoặc tự động hoàn thành trên một tập chuỗi đã biết
- Mỗi nút trong trie biểu diễn một chuỗi con xuất hiện trong tập chuỗi ban đầu, còn các liên kết giữa nút biểu diễn ký tự có thể đi sau một tiền tố nhất định
- Bắt đầu từ nút gốc, trie có thể thu hẹp không gian tìm kiếm ngay từ ký tự đầu tiên có thể có, nhờ đó nhanh chóng loại bỏ các chuỗi không thuộc tập
- Việc đọc trie cho trường hợp không khớp có hành vi O(log(L)), còn trường hợp khớp vẫn là O(L)
- Vì hơn 90% request header không phải header nội bộ, đây là một trường hợp sử dụng phù hợp với trie do có nhiều tình huống không khớp
-
Hạn chế của các triển khai trie hiện có
- Cloudflare đã benchmark nhiều triển khai trie trên crates.io, nhưng kết quả không đạt kỳ vọng
- Phần lớn trie hiện có được thiết kế cho các tình huống như tự động hoàn thành phản hồi theo thao tác bàn phím, chứ không ưu tiên tối ưu đường nóng xử lý hàng chục triệu request mỗi giây
- Triển khai có sẵn nhanh nhất được tìm thấy là radix_trie, nhưng vẫn chậm hơn hash map khoảng 1µs
- Cuối cùng, Cloudflare đã tự viết một triển khai trie mới phù hợp với trường hợp sử dụng này
trie-hard và kết quả production
-
Cloudflare đã công bố Rust crate mã nguồn mở mới trie-hard
-
trie-hardtăng tốc bằng cách lưu quan hệ giữa các nút trong các bit của số nguyên không dấu, đồng thời giữ toàn bộ cây trong một khối bộ nhớ liên tục -
Trong benchmark,
trie-hardđã hạ thời gian thực thi trung bình củaclear_internal_headersxuống 0.93µs -
Mức sử dụng CPU dự kiến là 0,43%, tương ứng giảm 1,28% mức sử dụng tài nguyên tính toán toàn cục của
pingora-originso với mức 1,71% ban đầu -
Kết quả lấy mẫu thực tế
trie-hardđã chạy production từ tháng 7/2024- Đo hiệu năng được thu thập bằng lấy mẫu thống kê stack trace theo thời gian
- Tỷ lệ mẫu chứa một hàm cụ thể được dùng để ước lượng mức sử dụng CPU của hàm đó
- Kết quả lấy mẫu trong production nhìn chung khá gần với dự đoán từ benchmark cục bộ
Triển khai Mẫu stack trace chứa clear_internal_headersMức sử dụng CPU thực tế Mức sử dụng CPU dự đoán Original 19 / 1111 1.71% n/a Hashmap 9 / 1103 0.82% 0.72% trie-hard 4 / 1171 0.34% 0.43%
Kết luận từ góc độ vận hành
- Trước khi viết một cấu trúc dữ liệu mới, điều quan trọng hơn là phải biết chính xác đoạn mã nào đang chậm và chậm đến mức nào
- Với flame graph, profiling và các công cụ benchmark, ngay cả những hàm ở cấp độ micro giây cũng có thể mang lại mức tiết kiệm đáng kể
- Việc tối ưu một phép toán vốn đã rất ngắn có thể trông như chuyện nhỏ, nhưng ở quy mô hàng chục triệu request mỗi giây, những cải thiện nhỏ sẽ cộng dồn thành mức giảm đáng kể trong tổng mức sử dụng tài nguyên tính toán
1 bình luận
Ý kiến trên Hacker News
Nếu phải đoán đại cách Cloudflare lưu trữ và loại bỏ các header nội bộ, có lẽ tôi sẽ nghĩ đến một dictionary hay cấu trúc dữ liệu riêng, một header duy nhất chứa toàn bộ metadata nội bộ, cách phân biệt nội bộ/bên ngoài bằng tiền tố, hoặc một tiền tố như
CFIntTôi có lẽ sẽ không nghĩ đến cách coi các tên header trong một danh sách cụ thể là header nội bộ. Điều đó làm nảy sinh các câu hỏi như: nếu người khác dùng cùng tên thì sao, nếu việc dọn dẹp bị bỏ sót thì sao, nếu các chương trình chạy đồng thời có danh sách khác nhau thì sao, nếu header
Connectiontrỏ đến một header nội bộ của Cloudflare thì sao, hoặc nếu thuật toán lấy hiệu tập hợp quá chậm thì saoWeb vốn đã đầy rẫy những tín hiệu in-band và cách đặt tên header mơ hồ đến mức khó chịu, nên việc một công ty quy mô như Cloudflare lại nội bộ dùng một cơ chế rườm rà và dễ lỗi như vậy nghe khá kỳ lạ
cf-cache-statusBao gồm cả việc loại bỏ header nội bộ ở proxy biên theo cả hai chiều, và cả ở luồng inbound cũng làm như vậy
Cách dùng danh sách có nhược điểm, nhưng cũng có nhiều ưu điểm. Khi chỉ ra các khuyết điểm tiềm ẩn của kiểu tiếp cận này, người ta thường bỏ qua lịch sử và những khó khăn phát sinh ở quy mô Cloudflare. Danh sách liệt kê là cách đơn giản và linh hoạt nhất, đồng thời không cần có thỏa thuận trước về cấu trúc khóa header. Xét đến số lượng đội ngũ ở Cloudflare, khả năng thâu tóm công nghệ, v.v., có lẽ điểm này rất quan trọng
Nếu điền sẵn, thì về cơ bản là kết hợp các ý tưởng này lại đồng thời cố định số lượng header nội bộ trên mỗi request. Khi đó có thể dùng bảng băm liên kết để giữ nguyên thứ tự tạo, rồi chỉ cần loại bỏ N mục đầu trong danh sách cuối cùng được trả về cho client
Tôi có nghĩ thoáng qua về hiệu quả của việc ánh xạ ký tự UTF-8 thành bitmask, và lúc đầu thấy nó có vẻ không mấy khôn ngoan. Nhưng rồi tôi nhận ra 32 bit đủ chứa
a-zvà 6 ký tự đặc biệt, còn 64 bit có thể chứa thêm chữ hoaA-Zvà 6 ký tự đặc biệt nữaVới HTTP header thì vậy là quá đủ, và chỉ cần mask rồi so sánh vài số nguyên là thành một thuật toán khớp cực nhanh. Việc ánh xạ ký tự nào vào bit nào cũng chỉ cần một lần tra bảng 256 từ
Điều tác giả bỏ sót là về mặt kỹ thuật, kỹ thuật này chính là một Bloom filter. Điều khiến những thứ này thú vị là dù đây là một kiểu tối ưu hóa từ thời tài nguyên tính toán còn hạn chế hơn bây giờ rất nhiều, trong trường hợp này là từ năm 1970, người ta vẫn đang dùng đúng những tối ưu hóa cổ điển đó ở đâu đó trong thế giới thực
https://en.wikipedia.org/wiki/Bloom_filter
trie-hardvà Bloom filter. Bloom filter là xác suất và dùng hashing. Nó phù hợp khi chấp nhận dương tính giả hiếm gặp để đổi lấy việc không có âm tính giả, nhưng ở đây đó không phải điều cần thiết. Ở đây cần độ chính xác, và hashing bản thân nó lại là bước cần phải vượt quaĐúng hơn thì đây gần với một phiên bản cải tiến hay biến thể của thuật toán Liang, từng được dùng để lưu từ điển ngắt dòng trong TeX. Bài báo gọi thuật toán của Bloom là “superimposed coding”, gợi rất mạnh đến thời mà bộ nhớ là tài nguyên quý giá nhất. Có lẽ bạn sẽ thích nó ^_^
https://tug.org/docs/liang/liang-thesis.pdf
Dữ liệu được đưa ra để chứng minh lợi ích thực ra thiếu đủ lực thống kê để cho thấy điều đó. Mẫu chưa đủ lớn
Nếu phân tích rất đơn giản bằng R thì là
prop.test(c(9, 4), c(1103,1171)), và với kiểm định hai tỷ lệ bằng nhau có hiệu chỉnh tính liên tục, p-value ra 0.222p-value 0.22 không thấp hơn mức 0.05 thần kỳ, và khoảng tin cậy 95% cho thấy trie trên thực tế thậm chí có thể tệ hơn đôi chút
Phân tích trước đó gợi ý trie có lẽ tốt hơn và cũng có bằng chứng yếu theo hướng đó, nhưng tốt hơn hết là lấy mẫu nhiều hơn nữa để chắc chắn nó tốt hơn đến mức nào
Với mục tiêu phân tích hiệu năng, việc mô tả số lần so sánh bằng ký hiệu Big-O nghe không hợp lắm. Một phép so sánh chỉ cỡ 1 chu kỳ, và với song song mức lệnh cùng SIMD thì thậm chí có thể làm nhiều phép trong một chu kỳ
Nút thắt thật sự và nguồn gốc của sự chậm chạp là bộ nhớ. Việc truy cập bộ nhớ có thể tốn hàng nghìn chu kỳ, và nếu cần TLB walk hay ngắt của hệ điều hành thì có thể lên đến hàng chục nghìn hoặc hàng trăm nghìn chu kỳ. Nếu muốn dùng Big-O thì nên dùng để ước lượng số lần cache miss
Nếu là tôi, tôi sẽ dùng một hàm băm hoàn hảo tùy chỉnh và mẹo
popcountcủa Phil Bagwell. Nó sẽ nhanh hơn các lời giải khác phải tra cứu bộ nhớ nhiều lầnCPU thì nhanh, còn bộ nhớ thì chậm
Tôi không quá rành về tối ưu hóa cấu trúc dữ liệu, nhưng vẫn khá ngạc nhiên khi họ loại bảng băm quá sớm, nhất là khi xét tới việc bảng cần tra cứu là tĩnh. Thật khó tin rằng một bảng băm được tối ưu riêng lại không thể nhanh hơn cách triển khai trie của họ
Với trường hợp này, đó là lợi thế mà băm không theo kịp được. Phần còn lại của kỹ thuật là giảm đủ hệ số hằng của trie để lợi thế ban đầu này được chuyển hóa thành hiệu năng thực tế
std::collections::HashMap: https://github.com/rust-lang/rustc-hashNếu chỉ có khoảng 100 mục tĩnh thì o1hash cũng có vẻ phù hợp: https://github.com/rurban/smhasher/blob/master/o1hash.h
Bài này tạo tập
to_removebằng một cấu trúc dữ liệu khá ngầu, rồi duyệt tập đó để xóa khỏi bản đồ header cơ sởLời gọi
remove_headercó vẻ là đoạn mã này: https://docs.rs/pingora-http/0.3.0/src/pingora_http/lib.rs.html#576Hàm này gọi
.remove()trên hai cấu trúc dữ liệu khác, và cả hai cuối cùng đều đi xuống đoạn mã khổng lồ này: https://docs.rs/http/latest/src/http/header/map.rs.html#1550Cuối cùng cũng có một bài blog xuất hiện về trie. Mấy bài trie trên LeetCode không hề vô ích ;)
Dù vậy, đây rõ ràng không phải công cụ tôi hay lôi ra dùng
Đây là một trình phân tích user-agent cho Go: https://github.com/medama-io/go-useragent
Bình thường những bài toán như vậy phụ thuộc rất nhiều vào việc phân tích bằng regex, nên thật tuyệt khi có thể thử một cách tiếp cận mới hơn
Nếu tập mục cần khớp là tĩnh, tôi tự hỏi họ có thử bảng băm hoàn hảo không. Nó có thể rút xuống còn vài phép toán số học rồi một lần so sánh chuỗi; sẽ khá thú vị nếu so với trie thì thế nào
Về lý thuyết, nếu dùng regex thì việc khớp sẽ thông qua máy trạng thái, nên đáng ra phải có hiệu năng trường hợp xấu nhất O(k) tương tự trie. Nhưng theo tôi hiểu thì các thư viện regex lại dùng backtracking thay vì thực sự xây dựng máy trạng thái, nên hiệu năng không còn là O(k) nữa
Điều đáng ngạc nhiên là họ không tìm được một thư viện regex dựa trên máy trạng thái vừa có sẵn vừa hiệu năng tốt. Đáng ra nó phải gần với trie, nhưng trên thực tế còn bị chi phối sâu hơn bởi những yếu tố như mẫu truy cập bộ nhớ hay hiệu năng của một số phép toán số học cụ thể, nên cũng khó đoán
Liệu họ có thử một Bloom filter rất nhỏ không? Nếu xử lý nhanh khóa header kiểu tích chập rồi đối chiếu với Bloom filter, có vẻ như với vài chu kỳ chi phí là có thể tránh hẳn việc duyệt trie trong đa số trường hợp
Có vẻ cũng có các lựa chọn như SIMD, lệnh CRC tích hợp, hay kích thước Bloom filter 256 bit
Một cách tiếp cận đơn giản hơn cũng có thể đáng giá. Nếu phân tích tần suất trúng/trượt của các nút trie, có thể tìm ra một số vị trí ký tự có tỷ lệ trượt cao hơn cả ký tự đầu tiên. Kiểm tra trước những vị trí đặc biệt đó có thể sẽ nhanh hơn. Tất nhiên điều này đòi hỏi giả định rằng dữ liệu header vốn có tính quy luật khá cao
Tôi nghĩ thế này. Thứ nhất, việc này có đáng làm không? Có vẻ như họ đã tiết kiệm được khoảng 500 lõi CPU, nhưng tôi không rõ đó là lõi vật lý hay có tính cả lõi hyperthread
Tôi không biết chi phí của Cloudflare, nhưng có lẽ chỉ tương đương vài máy chủ một chữ số, và số tiền tiết kiệm có lẽ chỉ ở mức vài chục nghìn USD mỗi năm. Không phải là có thể bỏ qua, nhưng tôi không chắc có thể kỳ vọng ROI dương so với mức đầu tư kỹ thuật hay không
Thứ hai, nếu đã đi sâu đến mức này thì tôi tự hỏi liệu họ có cân nhắc phương án đặt bộ lọc ở giai đoạn deserialization để ngay từ đầu các header không bị tạo ra hay chưa
Việc tiết kiệm điện cũng tiếp diễn, và lượng phát thải carbon cũng giảm
Thay vì làm mấy việc ngớ ngẩn kiểu phân tích header bằng AI để bán dép sandal, tôi thích thấy một công ty cố gắng làm cho thứ gì đó nhanh hơn 1%
Giá trị của điều đó có thể là cả triệu đô