Cách Roblox giảm chi phí truy vấn Spark Join bằng bộ lọc Bloom được tối ưu hóa bằng học máy

Tóm tắt

Mỗi ngày trên Roblox, 70 triệu người dùng tương tác với hàng triệu trải nghiệm, tổng cộng 16 tỷ giờ mỗi quý. Sự tương tác này tạo ra một hồ dữ liệu quy mô petabyte, được làm giàu để phục vụ mục đích phân tích và học máy (ML). Việc kết hợp các bảng dữ liệu sự kiện và chiều trong hồ dữ liệu của chúng tôi đòi hỏi nhiều tài nguyên, vì vậy để tối ưu hóa quá trình này và giảm thiểu việc di chuyển dữ liệu, chúng tôi đã áp dụng các bộ lọc Bloom được huấn luyện [1] — các cấu trúc dữ liệu thông minh sử dụng học máy. Bằng cách dự đoán sự hiện diện, các bộ lọc này cắt giảm đáng kể dữ liệu kết hợp, nâng cao hiệu quả và giảm chi phí. Trong quá trình này, chúng tôi cũng đã cải thiện kiến trúc mô hình và chứng minh những lợi ích đáng kể mà chúng mang lại trong việc giảm bộ nhớ và thời gian xử lý CPU, cũng như tăng tính ổn định hoạt động.

Giới thiệu

Trong hồ dữ liệu của chúng tôi, các bảng sự kiện và khối dữ liệu được phân vùng theo thời gian để truy cập hiệu quả, trong khi các bảng chiều không có phân vùng như vậy, và việc kết hợp chúng với các bảng sự kiện trong quá trình cập nhật tiêu tốn nhiều tài nguyên. Không gian khóa của phép kết hợp được xác định bởi phân vùng thời gian của bảng sự kiện được kết hợp. Các thực thể chiều có trong phân vùng thời gian đó chỉ là một tập con nhỏ so với toàn bộ tập dữ liệu chiều. Do đó, phần lớn dữ liệu chiều được trộn trong các phép ghép này cuối cùng bị loại bỏ. Để tối ưu hóa quá trình này và giảm thiểu việc trộn dữ liệu không cần thiết, chúng tôi đã xem xét việc sử dụng Bộ lọc Bloom trên các khóa ghép duy nhất nhưng gặp phải các vấn đề về kích thước bộ lọc và dung lượng bộ nhớ.

Để giải quyết các vấn đề này, chúng tôi đã nghiên cứu Bộ lọc Bloom học được, một giải pháp dựa trên ML giúp giảm kích thước Bộ lọc Bloom trong khi vẫn duy trì tỷ lệ dương tính giả thấp. Sáng kiến này nâng cao hiệu quả của các hoạt động nối bằng cách giảm chi phí tính toán và cải thiện độ ổn định của hệ thống. Sơ đồ sau đây minh họa các quy trình nối thông thường và được tối ưu hóa trong môi trường tính toán phân tán của chúng tôi.

Nâng cao hiệu quả kết hợp với bộ lọc Bloom học được

Để tối ưu hóa việc kết hợp giữa bảng dữ liệu thực tế và bảng chiều, chúng tôi đã áp dụng triển khai Bộ lọc Bloom học được. Chúng tôi đã xây dựng một chỉ mục từ các khóa có trong bảng dữ liệu thực tế và sau đó triển khai chỉ mục này để lọc trước dữ liệu chiều trước khi thực hiện thao tác kết hợp. 

Sự phát triển từ bộ lọc Bloom truyền thống sang bộ lọc Bloom học được

Mặc dù bộ lọc Bloom truyền thống hiệu quả, nó vẫn tiêu tốn thêm 15-25% bộ nhớ cho mỗi nút làm việc cần tải để đạt được tỷ lệ dương tính giả mong muốn. Tuy nhiên, bằng cách sử dụng bộ lọc Bloom học máy, chúng tôi đã đạt được kích thước chỉ mục giảm đáng kể trong khi vẫn duy trì cùng tỷ lệ dương tính giả. Điều này là do việc chuyển đổi bộ lọc Bloom thành một vấn đề phân loại nhị phân. Nhãn dương tính cho biết sự hiện diện của giá trị trong chỉ mục, trong khi nhãn âm tính có nghĩa là chúng vắng mặt.

Việc giới thiệu mô hình ML giúp thực hiện kiểm tra ban đầu cho các giá trị, sau đó là bộ lọc Bloom dự phòng để loại bỏ các kết quả âm tính giả. Kích thước được giảm bớt xuất phát từ biểu diễn nén của mô hình và số lượng khóa giảm xuống mà bộ lọc Bloom dự phòng yêu cầu. Điều này phân biệt nó với phương pháp bộ lọc Bloom truyền thống. 

Trong khuôn khổ công trình này, chúng tôi đã thiết lập hai thước đo để đánh giá phương pháp Bộ lọc Bloom học được của chúng tôi: kích thước đối tượng tuần tự hóa cuối cùng của chỉ mục và mức tiêu thụ CPU trong quá trình thực thi các truy vấn nối. 

Vượt qua những thách thức trong triển khai

Thách thức ban đầu của chúng tôi là xử lý tập dữ liệu đào tạo có độ lệch cao với ít khóa bảng chiều trong bảng sự kiện. Trong quá trình này, chúng tôi nhận thấy sự trùng lặp khoảng một trên ba khóa giữa các bảng. Để giải quyết vấn đề này, chúng tôi đã áp dụng phương pháp Sandwich Learned Bloom Filter [2]. Phương pháp này tích hợp một bộ lọc Bloom truyền thống ban đầu để cân bằng lại phân phối tập dữ liệu bằng cách loại bỏ phần lớn các khóa thiếu trong bảng sự kiện, từ đó loại bỏ các mẫu âm tính khỏi tập dữ liệu. Sau đó, chỉ các khóa có trong bộ lọc Bloom ban đầu, cùng với các kết quả dương tính giả, mới được chuyển tiếp đến mô hình ML, thường được gọi là "oracle đã học". Cách tiếp cận này đã tạo ra một tập dữ liệu huấn luyện cân bằng tốt cho oracle đã học, giúp khắc phục hiệu quả vấn đề thiên vị.

Thách thức thứ hai tập trung vào kiến trúc mô hình và các tính năng đào tạo. Không giống như vấn đề cổ điển về URL lừa đảo [1], các khóa liên kết của chúng tôi (trong hầu hết các trường hợp là các mã định danh duy nhất cho người dùng/trải nghiệm) vốn không mang tính thông tin. Điều này đã dẫn chúng tôi đến việc khám phá các thuộc tính chiều như những tính năng mô hình tiềm năng có thể giúp dự đoán liệu một thực thể chiều có hiện diện trong bảng dữ liệu thực tế hay không. Ví dụ: hãy tưởng tượng một bảng dữ liệu thực tế chứa thông tin phiên người dùng cho các trải nghiệm bằng một ngôn ngữ cụ thể. Vị trí địa lý hoặc thuộc tính ưu tiên ngôn ngữ của chiều người dùng sẽ là những chỉ số tốt cho biết một người dùng cụ thể có hiện diện trong bảng dữ liệu thực tế hay không.

Thách thức thứ ba — độ trễ suy luận — đòi hỏi các mô hình vừa giảm thiểu các kết quả âm tính giả vừa cung cấp phản hồi nhanh chóng. Mô hình cây tăng cường độ dốc là lựa chọn tối ưu cho các chỉ số chính này, và chúng tôi đã cắt tỉa tập hợp các đặc tính của nó để cân bằng giữa độ chính xác và tốc độ.

Câu hỏi kết hợp cập nhật của chúng tôi sử dụng Bộ lọc Bloom đã học được như sau:

Kết quả

Dưới đây là kết quả của các thí nghiệm của chúng tôi với bộ lọc Bloom học được trong hồ dữ liệu của chúng tôi. Chúng tôi đã tích hợp chúng vào năm khối lượng công việc sản xuất, mỗi khối lượng công việc có các đặc điểm dữ liệu khác nhau. Phần tốn nhiều tài nguyên tính toán nhất trong các khối lượng công việc này là việc kết hợp giữa bảng dữ liệu thực tế và bảng chiều. Không gian khóa của các bảng dữ liệu thực tế chiếm khoảng 30% bảng chiều. Đầu tiên, chúng tôi sẽ thảo luận về cách bộ lọc Bloom học vượt trội hơn so với bộ lọc Bloom truyền thống về kích thước đối tượng tuần tự hóa cuối cùng. Tiếp theo, chúng tôi sẽ trình bày những cải thiện về hiệu suất mà chúng tôi quan sát được khi tích hợp bộ lọc Bloom học vào các đường ống xử lý khối lượng công việc của chúng tôi.

So sánh kích thước bộ lọc Bloom học được

Như được trình bày dưới đây, khi xem xét một tỷ lệ dương tính giả nhất định, hai biến thể của bộ lọc Bloom học được cải thiện kích thước tổng thể của đối tượng từ 17-42% so với bộ lọc Bloom truyền thống.

Ngoài ra, bằng cách sử dụng một tập hợp con nhỏ hơn các đặc trưng trong mô hình dựa trên cây tăng cường gradient của chúng tôi, chúng tôi chỉ mất một phần trăm nhỏ về khả năng tối ưu hóa trong khi làm cho quá trình suy luận nhanh hơn.

Kết quả nghiên cứu về việc sử dụng bộ lọc Bloom 

Trong phần này, chúng tôi so sánh hiệu suất của các phép nối dựa trên Bloom Filter với các phép nối thông thường trên một số chỉ số. 

Bảng dưới đây so sánh hiệu suất của các khối lượng công việc có và không sử dụng bộ lọc Bloom học được. Một bộ lọc Bloom học được với tổng xác suất dương tính giả là 1% thể hiện so sánh dưới đây trong khi duy trì cùng cấu hình cụm cho cả hai loại kết hợp. 

Đầu tiên, chúng tôi nhận thấy rằng việc triển khai Bloom Filter vượt trội hơn so với phương pháp kết hợp thông thường tới 60% về số giờ CPU. Chúng tôi nhận thấy sự gia tăng trong việc sử dụng CPU ở bước quét đối với phương pháp Learned Bloom Filter do phải tốn thêm thời gian tính toán để đánh giá Bloom Filter. Tuy nhiên, việc lọc trước được thực hiện trong bước này đã giảm kích thước dữ liệu được xáo trộn, giúp giảm lượng CPU được sử dụng bởi các bước tiếp theo, từ đó giảm tổng số giờ CPU.

Thứ hai, Learned Bloom Filter có tổng kích thước dữ liệu ít hơn khoảng 80% và tổng số byte xáo trộn được ghi ít hơn khoảng 80% so với phép nối thông thường. Điều này dẫn đến hiệu suất nối ổn định hơn như được thảo luận dưới đây. 

Chúng tôi cũng ghi nhận sự giảm thiểu sử dụng tài nguyên trong các tác vụ sản xuất khác đang được thử nghiệm. Trong khoảng thời gian hai tuần trên tất cả năm tác vụ, phương pháp Learned Bloom Filter mang lại tiết kiệm chi phí trung bình hàng ngày là 25%, bao gồm cả quá trình đào tạo mô hình và tạo chỉ mục.

Do lượng dữ liệu được xáo trộn giảm khi thực hiện phép nối, chúng tôi đã có thể giảm đáng kể chi phí vận hành của đường ống phân tích đồng thời làm cho nó ổn định hơn. Biểu đồ sau đây cho thấy độ biến động (sử dụng hệ số biến động) về thời gian chạy (thời gian đồng hồ) cho một tác vụ nối thông thường và một tác vụ dựa trên bộ lọc Bloom học được trong khoảng thời gian hai tuần đối với năm tác vụ mà chúng tôi đã thử nghiệm. Các lần chạy sử dụng Learned Bloom Filter ổn định hơn — thời gian chạy nhất quán hơn — điều này mở ra khả năng chuyển chúng sang các tài nguyên tính toán tạm thời, không đáng tin cậy nhưng rẻ hơn. 

Tài liệu tham khảo

[1] T. Kraska, A. Beutel, E. H. Chi, J. Dean, và N. Polyzotis. The Case for Learned Index Structures. https://arxiv.org/abs/1712.01208, 2017.

[2] M. Mitzenmacher. Tối ưu hóa bộ lọc Bloom học được bằng phương pháp kẹp. 

https://arxiv.org/abs/1803.01474, 2018.

¹Tính đến ngày 30 tháng 6 năm 2023

²Tính đến ngày 30 tháng 6 năm 2023