Nén Luồng Dữ Liệu TCP Hiệu Quả

Trong hai ngày qua, mình đã nghiên cứu kỹ thuật thuật toán nén LZW - một phương pháp nén dữ liệu dựa trên từ điển. Điều đáng mừng là bằng sáng chế của thuật toán này đã hết hiệu lực, cho phép sử dụng tự do mà không gặp vấn đề pháp lý. Đặc điểm nổi bật của phương pháp này là khả năng nén cực tốt khi gặp các chuỗi dữ liệu lặp lại thường xuyên. Trong các ứng dụng game trực tuyến, hiện tượng này rất phổ biến nhưng thường xảy ra ở cấp độ luồng dữ liệu giữa các gói tin, chứ không phải trong phạm vi từng gói đơn lẻ.

Khác với các ứng dụng thông thường, game online luôn yêu cầu tốc độ truyền dữ liệu nhanh nhất có thể để giảm độ trễ mạng. Do đó, chúng ta thường truyền dữ liệu ngay khi có sẵn thay vì gom nhiều gói lại để nén chung. Điều này khiến việc áp dụng nén dữ liệu theo từng gói riêng lẻ trở nên không hiệu quả.

Giải pháp tối ưu nhất mình tìm ra là giữ nguyên ngữ cảnh của bộ nén giữa các lần xử lý. Cụ thể, từ điển nén sẽ không được đặt lại sau mỗi gói dữ liệu, giúp các thông tin lặp lại được mã hóa ngày càng ngắn gọn hơn. Trong quá trình thử nghiệm, mình đã phát triển một phiên bản LZW đặc biệt với từ điển khởi tạo bao gồm toàn bộ 256 ký tự byte có thể xảy ra. Để tiện lợi hơn trong việc phân tách gói dữ liệu, mình còn thêm vào từ điển một ký hiệu “kết thúc gói” đặc biệt. Nhờ đó, không cần phải lưu trữ độ dài gói trong header mà chỉ cần kết thúc gói bằng ký hiệu này.

Một cải tiến thú vị khác là việc điều chỉnh độ dài mã hóa. Thay vì cứng nhắc dùng 8-bit, mình đã thử nghiệm với đơn vị 4-bit, cho phép bắt đầu mã hóa từ 5-bit. Kết quả thử nghiệm cho thấy hiệu quả nén được cải thiện đáng kể. Để kiểm chứng, mình đã thực hiện thí nghiệm nén chuỗi “Hello World” (11 byte gốc + ký hiệu kết thúc gói) lặp lại 25 lần. Kết quả cho thấy:

04 99 62 58 35 4f 80 72 f0 11 2e 02 02 d1 74 59 d9 d6 3d 5f 08 01 23 65 99 1a e7 81 96 08 6d 89 c5 e9 5a 43 f6 8b a3 66 2c bd cb 49 a6 a2 19 44 42 18 d0 c8 02 c9 5f 71 87 84 00 4d a2 ee 28 02 d2 5c 90 07 d6 25 54 04 d9 67 15 02 5c 2a 0b 5f 6c 14 61 26 0f e3 2d 04 65 2f 67 16 68 1e e9 28 6a 11 6b 08 6c 6c 6c

Ở lần nén đầu tiên, kích thước dữ liệu tăng nhẹ lên 13 byte, nhưng sau 25 lần lặp, chuỗi này chỉ còn được biểu diễn bằng 1 byte duy nhất. Bộ nén này yêu cầu mỗi kết nối phải dành riêng một vùng nhớ cố định (khoảng 64KB cho cấu hình 32KB từ điển). Với 1000 kết nối đồng thời, tổng bộ nhớ cần thiết là 64MB - một con số không nhỏ. Tuy nhiên, khi xem xét trên mạng 1Gbps, chi phí này hoàn toàn hợp lý vì thời gian sao chép dữ liệu từ user space sang kernel space vốn đã nhanh hơn nhiều so với chi phí xử lý nén dữ liệu.

Ngoài LZW, mình cũng xem xét phương pháp Huffman động. Mặc dù thuật toán này có hiệu suất nén tốt nhờ lý thuyết entropy, nhưng việc cập nhật cây Huffman liên tục lại đòi hỏi chi phí tính toán rất cao. So với LZW, rõ ràng thuật toán này kém phù hợp hơn cho các ứng dụng thời gian thực.

Việc tích hợp tính năng nén dữ liệu vào engine game là một thử nghiệm rất thú vị. Trong một lần kiểm tra thực tế với traffic game Đại thoại Tây Du, sau 2504 giây ghi nhận: 32,903 gói dữ liệu được nhận với tổng kích thước 943,888 byte, sau khi nén chỉ còn 700,508 byte (đạt hiệu suất 74.2%). Hiện tại mình đang lên kế hoạch tối ưu hóa thêm thuật toán để cải thiện hiệu suất.

P/s: Mình nhận thấy vẫn còn nhiều không gian cải tiến trong cách triển khai hiện tại, dự kiến sẽ dành thời gian cuối tuần tới để hoàn thiện.