CloudFlare mỗi ngày nhận một lượng HTTP request rất lớn trên toàn cầu. Theo thống kê gần đây có khoảng 60 triệu request mỗi giây. Con số này không phải là quá mới, tuy nhiên trước đó vài tháng hành trình tối ưu để có lượng chịu tải như thế mới bắt đầu và kết quả là cho ra một thư viên mã nguồn mở: Trie-hard. Trie-hard đã giúp CloudFlare giảm được thời gian tính toán của CPU, và cuối cùng là giúp cho CloudFlare có thể xử lý được lượng requests càng ngày càng tăng dần.

Bối cảnh

Câu chuyện bắt đầu từ một vài tháng trước, lúc đó, CloudFlare đã phát hành Pingora thành một dự án mã nguồn mở trên GitHub. Có nhiều dịch vụ của CloudFlare được xây dựng trên nền tảng này. Một trong những dịch vụ đó chịu trách nhiệm thực hiện các xử lý trước khi gửi request của người dùng tới máy chủ đích. Trong nội bộ công ty, họ gọi máy chủ đích của request là “origin”, cho nên nó con tên gọi là là “pingora-origin”.

Một trong các nhiệm vụ của pingora-origin là đảm bảo rằng khi một request rời khỏi hạ tầng của CloudFlare, nó được làm sạch bằng cách loại bỏ các thông tin nội bộ khỏi request. Các thông tin này được thêm vào request trong quá trình định tuyến, đo lường, và tối ưu hóa lưu lượng cho khách hàng. Việc dọn dẹp này phải được thực hiện với mọi HTTP requests rời khỏi Cloudflare, và như đã đề cập, đó là số lượng request rất lớn. Tại thời điểm viết bài này, số request rời khỏi pingora-origin (trên toàn cầu) là 35 triệu request mỗi giây. Khi tiến hành tối ưu hệ thống này, họ nhắm đến những đoạn code mà luôn luôn được chạy khi xử lý mỗi request. Và họ tìm thấy một đoạn code tiềm năng như sau:

Hàm này tuy ngắn và dễ đọc nhưng lại tiêu tốn hơn 1,7% tổng thời gian CPU của pingora-origin. Để dễ hình dung hơn, tổng thời gian CPU mà pingora-origin tiêu thụ là 40.000 compute-seconds mỗi giây. Bạn có thể hiểu điều này như 40.000 core CPU được sử dụng hết công suất, hoàn toàn dành riêng cho việc chạy pingora-origin. Trong số 40.000 core đó, 1,7% (tức 680 core) chỉ được dùng riêng để chạy hàm clear_internal_headers. Hàm này đã trở thành một điểm lý tưởng để bắt đầu tối ưu hoá bởi vị nó đơn giản nhưng lượng CPU tiêu tốn là rất lớn.

Đo lường hiệu suất (Benchmarking)

Việc kiểm tra hiệu năng của hàm trên khá đơn giản vì nhờ vào criterion, một crate rất hay của Rust. Criterion cung cấp một API để đo thời gian thực thi (execution time) code Rust chính xác đến từng nano giây bằng cách tổng hợp nhiều lần thực thi riêng biệt. Nó cũng đưa ra các đánh giá về việc hiệu năng được cải thiện hay giảm xuống theo thời gian. Để kiểm tra hiệu năng của chương trình, người ta thu tập rất nhiều requests thực với số lượng ngẫu nghiên các header "nội bộ" và header "tiêu chuẩn". Qua việc đo lường tốc độ chạy của code, họ nhận thấy hàm clear_internal_headers ban đầu có thời gian chạy trung bình là 3,65µs. Từ giờ, họ sẽ cài đặt các phương án cải tiến và dùng lại cùng một bộ đữ liệu để so sánh và đánh giá hiệu năng giữa các phương pháp này.

Tối ưu 1: giảm số lần đọc

Một phương án nhanh chóng và đơn giản được vạch ra, đó là đảo ngược cách mà chúng ta tìm các header cần xoá. Nếu bạn nhìn vào đoạn code ban đầu, có thể thấy rằng chúng ta chạy lệnh request_header.remove_header(h) cho mỗi header trong danh sách cách header nội bộ cho trước, tức là hơn 100 lần. Để dễ hình dung hơn, các bạn hãy xem hình minh hoạ phía dưới:

Bởi vì một request trung bình có ít hơn 100 headers (thực tế là từ 10 đến 30), việc đảo ngược hướng tìm kiếm sẽ giảm số lần đọc trong khi vẫn đạt được cùng một kết quả. Chúng ta chỉ cần duyệt qua các header trong request, kiểm tra xem nó có nằm trong danh sách header nội bộ không, rồi mới xoá header đó ra khỏi request. Vẽ hình minh hoạ để các bạn dễ hình dung hơn:

Bằng các công cụ đo lường hiệu suất (benchmark tool), người ta tiến hành kiểm tra lại xem cách làm mới này có hiệu quả không? Thật không thể tin nổi, đây là một cải tiến đáng kể. Thời gian thực thi cải thiện từ 3.65µs xuống 1.53µs. Điều đó có nghĩa là tốc độ của hàm này đã cải thiện 2.39 lần. Chúng ta có thể tính toán tỷ lệ phần trăm CPU lý thuyết bằng cách nhân mức sử dụng ban đầu với tỷ lệ giữa thời gian chạy mới và cũ: 1.71% * 1.53 / 3.65 = 0.717%. Không may, nếu chúng ta trừ số đó từ mức 1.71% ban đầu, chỉ có nghĩa là tiết kiệm 1.71% - 0.717% = 0.993% tổng thời gian CPU. Chưa dừng lại ở đó, họ nghĩ vẫn có khả năng làm tốt hơn.

Tối ưu 2: Sử dụng cấu trúc dữ liệu hiệu quả hơn

Bây giờ khi chúng ta đã viết lại hàm để tìm kiếm trong một tập hợp tĩnh các header nội bộ thay vì duyệt qua các header của request thực tế. Chúng ta có thể thoải mái chọn cấu trúc dữ liệu để lưu trữ tên header chỉ bằng cách thay đổi kiểu của INTERNAL_HEADER_SET.

Đầu tiên, họ thử sử dụng std::HashMap, nhưng có thể có những cấu trúc dữ liệu khác phù hợp hơn với nhu cầu đó. Tất cả sinh viên ngành công nghệ thông tin đều đã từng được dạy rằng bảng băm (hash table) rất nhanh vì chúng có độ phức tạp là O(1) cho việc truy xuất dữ liệu. Điều này có nghĩa là bất kể bảng băm lớn như thế nào, việc đọc luôn tốn cùng một khoảng thời gian. Tuy nhiên, điều này chỉ đúng một phần. Để đọc được dữ liệu từ bảng băm, bạn phải tính toán giá trị băm (hash). Việc tính toán giá trị hash cho một string yêu cầu máy tính phải đọc tất cả các byte của chuỗi đó, vì vậy độ phức tạp lúc này là O(L) với L là độ dài của khoá

Vì vậy, mục tiêu của chúng ta là tìm một cấu trúc dữ liệu tốt hơn O(L).

Có một vài cấu trúc dữ liệu phổ biến có khả năng đọc đáp ứng tiêu chí của chúng ta. Cấu trúc dữ liệu ordered-set như BTreeSet sử dụng phép so sánh để tìm kiếm, và điều này khiến thời gian tìm kiếm chỉ còn là O(log(L)). Tuy nhiên, cấu trúc này cũng có độ phức tạp bộ nhớ (space complexity) theo logarit đối với kích thước tập hợp. Thực tế, ngay cả khi sử dụng các ordered-set rất nhanh như FST thì nó vẫn chậm hơn một chút (khoảng 50 ns) so với hashmap tiêu chuẩn.

Các state machines (máy trạng thái), chẳng hạn như bộ phân tích cú pháp (parsers) và regex là công cụ phổ biến để tìm kiếm chuỗi, mặc dù chúng không hẳn là cấu trúc dữ liệu. Các thuật toán này hoạt động bằng cách duyệt qua từng ký tự một và xác định ở mỗi bước xem có cần xử lý tiếp nữa hay không? Nhờ đó, state machine chạy rất nhanh trong việc xác định các trường hợp không hợp lệ (ví dụ: khi một chuỗi không hợp lệ hoặc không khớp). Điều này rất hiệu quả với bài toàn mà chúng ta đang xử lý, vì trung bình chỉ có một hoặc hai header trong mỗi request sẽ là header nội bộ.

Trên thực tế, khi đo hiệu suất của clear_internal_headers sử dụng regex, kết quả cho thấy nó chậm hơn khoảng 2 lần so với hashmap. Mặc dù regex rất linh hoạt trong việc tìm kiếm và xử lý chuỗi phức tạp, nhưng tốc độ chạy rất chậm. Tuy nhiên cách tiếp cận này gợi mở cho các kỹ sư một giải pháp kết hợp cả cấu trúc dữ liệu và state machine.

Trie thôi là chưa đủ

Cấu trúc dữ liệu Trie là một loại cấu trúc dữ liệu dạng cây thường được sử dụng cho việc tìm kiếm theo tiền tố hoặc các hệ thống autocomplete trên một tập các chuỗi cho trước. Cấu trúc của Trie rất phù hợp với mục đích này bởi vì mỗi nút (node) trong Trie đại diện cho một chuỗi con (substring) của các xâu trong tập hợp ban đầu. Các kết nối giữa các nút đại diện cho viêc các ký tự có thể xuất hiện sau một tiền tố (prefix).Dưới đây là ví dụ đơn giản về một Trie được xây dựng từ các từ: “and”, “ant”, “dad”, “do”, và “dot”:

Trie là một cấu trúc mạnh cho việc tìm kiếm nhanh bằng tiền tố, vì chúng cho phép chúng ta kiểm tra từng ký tự một, giảm thiểu thời gian so sánh chuỗi, đặc biệt hiệu quả khi làm việc với nhiều từ có chung tiền tố.

Nút gốc (root node) đại diện cho tiền tố "chuỗi rỗng", vì vậy hai cạnh có chữ cái xuất phát từ nút gốc là các chữ cái có thể xuất hiện làm chữ cái đầu tiên, ở đây là “a” và “d”. Các nút tiếp theo có tiền tố ngày càng dài hơn cho đến khi tạo thành các từ hợp lệ. Bố cục này giúp chúng ta dễ dàng thấy Trie hữu ích trong việc nhanh chóng xác định các chuỗi không tồn tại. Chẳng hạn, ngay tại nút gốc, chúng ta có thể loại trừ bất kỳ chuỗi nào không bắt đầu bằng “a” hoặc “d”.

Việc thu hẹp không gian tìm kiếm ở mỗi bước, làm cho Trie độ phức tạp O(log(L)), đúng những gì mà chúng ta đang mong đợi, nhưng chỉ đối với các trường hợp không tìm thấy (misses). Trong trường hợp tìm thấy (hits), độ phức tạp vẫn là O(L), nhưng điều này không sao, vì trong hơn 90% thời gian chúng ta sẽ gặp trường hợp không tìm thấy.

Trie giúp loại trừ các chuỗi không hợp lệ một cách hiệu quả, giảm số lượng ký tự cần kiểm tra khi không có xâu nào được tìm thấy, cải thiện hiệu suất trong các tình huống khi tỷ lệ "miss" cao.

Việc đo hiệu suất một vài cách cài đặt Trie từ crates.io khá thất vọng. Cần nhớ rằng, hầu hết các Trie được sử dụng để phản hồi các sự kiện từ bàn phím (chẳng hạn như tính năng autocomplete), nên tối ưu hóa chúng để chạy với hàng chục triệu request mỗi giây không phải là ưu tiên. Cách cài đặt nhanh nhất mà họ tìm thấy là radix_Trie, nhưng nó vẫn chậm hơn so với hashmap đến một microsecond. Điều cuối cùng cần làm là tự viết một Trie riêng, được tối ưu hóa cho cho yêu cầu cụ thể của bài toán này.

Cấu trúc dữ liệu mới: Trie Hard

Họ đã thành công! Team CloudFlare đã công bố mã nguồn của Trie-hard lên Github. Trie-hard đạt được tốc độ kinh khủng nhờ vào hai đặc điểm chính sau:

Trong các bài kiểm tra hiệu suất, họ thấy rằng Trie-hard đã giảm thời gian chạy trung bình của hàm clear_internal_headers xuống dưới 1 microsecond (0.93µs). Họ cũng đã sử dụng lại công thức trước đó để tính toán mức sử dụng CPU dự kiến cho Trie-hard: 1.71% x (3.65 / 0.93) = 0.43%

Điều này có nghĩa là họ đã đạt và vượt mục tiêu đề ra, giảm mức sử dụng CPU của pingora-origin đi: 1.71% - 0.43% = 1.28%

Trước đó, tất cả tính toán trên chỉ là lý thuyết và các bài kiểm tra hiệu suất cũng chỉ được thực hiện trên máy tính cá nhân. Do đó dữ liệu cũng chưa phản ánh được hiệu quả thực tế. Họ quyết định đưa Trie-hard triển khai vào môi trường production từ tháng 7 năm 2024, trong quá trình chạy, họ đã thu thập số liệu về hiệu suất từ môi trường production của pingora-origin thông qua phương pháp lấy mẫu ngẫu nhiên. Bằng kỹ thuật này, tỷ lệ phần trăm sử dụng CPU của một hàm được ước tính dựa trên tần suất hàm xuất hiện trong các mẫu. Khi so sánh hiệu suất của các phiên bản khác nhau của clear_internal_headers, người ta thấy rằng kết quả lấy mẫu rất phù hợp với những gì đã được dự đoán trong các bài kiểm tra ban đầu.

Kết luận

Tối ưu hóa các hàm và viết các cấu trúc dữ liệu mới là một công việc rất ngầu phải không? Nhưng điểm quan trọng mà đội ngũ Sydexa nhấn mạnh trong bài viết là:

Nguồn bài viết: https://blog.cloudflare.com/pingora-saving-compute-1-percent-at-a-time/