Ghi Chú Tối Ưu Hóa Hệ Thống (Kỳ 21): Cấu Trúc Hàng Đợi Không Khóa

Trong ba tuần qua, nhóm chúng tôi đã hoàn tất giai đoạn phát triển Milestone 1 theo đúng kế hoạch. Hầu như tất cả các tính năng mới đã được đóng băng, toàn bộ thành viên tập trung sửa lỗi và hoàn thiện các chi tiết còn lại. Tuy nhiên hiệu năng hệ thống vẫn còn tồn tại vấn đề nghiêm trọng - kết quả benchmark không đạt yêu cầu mong muốn.

Ban đầu tôi kỳ vọng có thể dễ dàng xử lý các trận chiến 40 đấu 40 người. Tuy nhiên với cấu hình máy tính để bàn hiện tại, mục tiêu này vẫn chưa thể đạt được. Mặc dù có thể đạt được hiệu năng mong muốn khi sử dụng máy chủ cấu hình cao, nhưng điều này sẽ làm gia tăng đáng kể chi phí vận hành. Do đó nhóm quyết định tiến hành tối ưu hóa hệ thống từ gốc.

Dù “tối ưu hóa sớm” không phải là điều kiện tiên quyết, nhưng các vấn đề hiệu năng phát hiện sớm thường phản ánh những lỗi thiết kế nền tảng. Việc phát hiện và sửa lỗi thiết kế ở giai đoạn đầu sẽ hiệu quả hơn nhiều so với việc tối ưu hóa ở cấp độ thấp sau này.

Hệ thống chúng tôi sử dụng mô hình xử lý song song với hàng ngàn tiến trình (không phải tiến trình hệ điều hành, mà là tiến trình Erlang). Mô hình này tận dụng tối đa sức mạnh đa nhân, nhưng lại gây áp lực lớn cho giao tiếp nội bộ. Qua phân tích cho thấy 90% lưu lượng giao tiếp nội bộ trong đấu trường nhiều người là các gói đồng bộ trạng thái. Mặc dù tiến trình Erlang trên cùng máy có thể giao tiếp thông qua cơ chế truyền tham số hàm đơn giản, nhưng thao tác đóng gói dữ liệu (marshalling) và sao chép bộ nhớ vẫn tạo gánh nặng nhất định.

Hiện chưa thể xác định chính xác chi phí biên tế của giao tiếp nội bộ ảnh hưởng thế nào đến hiệu năng tổng thể. Do đó tôi quyết định tập trung tối ưu hóa thiết kế và triển khai ở phần này để xác định điểm nghẽn thực sự.

Về đồng bộ trạng thái, khi một Agent thực hiện hành động, nó phải thông báo hành vi đó đến tất cả người chơi trong phạm vi nhất định. Khi có hơn 50 người chơi cùng một khu vực, lượng dữ liệu cần phát tán tăng đột biến. Giải pháp hiện tại dựa trên giả định: giao tiếp nội bộ máy chủ có chi phí cực thấp. Phát sóng (broadcast) hiệu quả hơn gửi riêng lẻ vì có thể giảm thiểu sao chép dữ liệu nội bộ. Do đó, trên cùng một bản đồ, bất kỳ thay đổi trạng thái nào của Agent sẽ được phát sóng đến tất cả người chơi khác trên bản đồ đó, sau đó từng Agent tự thực hiện lọc dữ liệu theo logic riêng trước khi gửi về client.

Tuy nhiên, chúng tôi đang xem xét một giải pháp phát sóng hiệu quả hơn để tránh sao chép dữ liệu dư thừa.

Tôi dự định thiết kế một cấu trúc dữ liệu đặc biệt với các đặc điểm sau:

• Nhiều tác nhân ghi dữ liệu đồng thời vào hàng đợi
• Nhiều tác nhân đọc dữ liệu đồng thời từ hàng đợi
• Giả sử bộ nhớ vô hạn, hàng đợi không cần xóa dữ liệu chưa bao giờ được đọc
• Con trỏ ghi được chia sẻ, mỗi tác nhân ghi sẽ dịch chuyển con trỏ này
• Mỗi tác nhân đọc duy trì con trỏ đọc riêng, có thể đọc đồng thời không ảnh hưởng nhau

Cấu trúc này có thể triển khai đơn giản với tính an toàn đồng thời không cần khóa (lock-free). Đây là cách tôi thực hiện:

Sử dụng hai vùng nhớ liên tục:

1. INDEX_QUEUE - Lưu trữ chỉ số truy cập
2. DATA_QUEUE - Lưu trữ dữ liệu thực tế

Quy trình ghi dữ liệu vào hàng đợi:

1
2
3
4
5

 1. OFFSET = SYNC_FETCH_AND_ADD(DATA_QUEUE.TAIL , SIZE)
 2. WRITE_DATA(DATA_QUEUE , OFFSET, DATA , SIZE)
 3. INDEX = SYNC_FETCH_AND_ADD(INDEX_QUEUE.WTAIL, 1)
 4. INDEX_QUEUE[INDEX] = OFFSET
 5. WHILE NOT SYNC_COMPARE_AND_SWAP(INDEX_QUEUE.RTAIL , INDEX, INDEX+1)

Giải thích chi tiết:

• Bước 1: Tăng con trỏ đuôi hàng đợi dữ liệu để dành chỗ trống
• Bước 2: Ghi dữ liệu vào vùng nhớ đã định sẵn
• Bước 3: Tăng con trỏ WTAIL của hàng đợi chỉ số để phân bổ vị trí
• Bước 4: Ghi OFFSET vào vị trí chỉ định
• Bước 5: Cập nhật con trỏ RTAIL, cần đảm bảo RTAIL tăng theo thứ tự chỉ số

Đối với quy trình đọc dữ liệu, mỗi thread độc lập duy trì con trỏ đầu hàng đợi riêng, không cần thao tác nguyên tử. Mỗi lần đọc từ vị trí đầu hàng đợi đến RTAIL.

Do bộ nhớ thực tế hữu hạn, chúng tôi triển khai hàng đợi vòng (circular queue), khi đầy sẽ quay vòng. Điều này làm tăng độ phức tạp của mã nguồn so với mã giả minh họa, nhưng vẫn đảm bảo tính chất không khóa.

Trong ứng dụng thực tế:

• Người dùng hàng đợi không cần biết tất cả người đọc
• Mỗi người đăng ký (subscriber) sẽ khởi tạo con trỏ đọc tại vị trí đuôi hàng đợi
• Xử lý toàn bộ dữ liệu trong hàng đợi mỗi 0.1 giây
• Hàng đợi có thể lưu trữ ít nhất 1 giây dữ liệu (khoảng 30,000 gói), đủ cho tình huống hàng ngàn người chơi cùng bản đồ

Nhờ vậy, khi Agent cần phát tán dữ liệu, chỉ cần đẩy vào hàng đợi phát sóng bản đồ. Khi xử lý theo chu kỳ, Agent chỉ cần trỏ trực tiếp vào vùng nhớ dữ liệu trong hàng đợi mà không cần sao chép, giúp tiết kiệm tài nguyên.

Tôi chỉ mất nửa ngày để hoàn thành cấu trúc này với hơn 200 dòng mã C và bao bọc Lua. Tuy nhiên lập trình đa luồng luôn tiềm ẩn nhiều lỗi phức tạp - phải mất thêm một ngày nữa mới khắc phục xong các vấn đề đồng thời.

Kết quả ban đầu:

• Giảm 90% lưu lượng giao tiếp nội bộ
• Nâng cao hiệu năng tổng thể từ