Ghi Chú Phát Triển (23): Từ Điển Nguyên Tử

Ghi chú phát triển (23): Từ điển nguyên tử

Vấn đề đã được nêu lên từ lâu. Trong Ghi chú phát triển 18, chúng tôi đã đề cập một yêu cầu: một trình ghi dữ liệu người chơi cần có khả năng sửa đổi hàng loạt các thuộc tính. Tuy nhiên, có thể đồng thời tồn tại các luồng khác đang đọc dữ liệu người chơi này (thông qua bộ nhớ chia sẻ), dẫn đến nguy cơ dữ liệu đọc được bị thiếu sót.

Chúng tôi có thể chấp nhận việc đọc dữ liệu cũ ở một thời điểm nhất định, nhưng tuyệt đối không thể chấp nhận việc đọc dữ liệu không hoàn chỉnh. Nói cách khác, mọi thao tác sửa đổi dữ liệu người chơi phải được thực hiện theo nhóm, đảm bảo tính nguyên tử (atomicity) cho từng nhóm sửa đổi.

Ban đầu tôi dự định giải quyết vấn đề này bằng khóa đọc/ghi (read-write lock). Phương án đã được thiết kế nhưng chưa triển khai, chỉ mới hoàn thành chức năng cơ bản của khóa. Vài ngày gần đây vấn đề lại được đặt ra khi chúng tôi nhận ra chính sách “đầu tư” trước đây (giả vờ vấn đề không tồn tại) không còn phù hợp nữa (dù chưa phát hiện lỗi thực tế nào).

Chúng tôi đã thảo luận nhiều giải pháp, ban đầu đều xoay quanh việc sử dụng khóa với độ phân giải khác nhau. Thậm chí một phương án đã được triển khai hoàn chỉnh cùng chương trình kiểm tra hiệu năng. Tuy nhiên các giải pháp này đều tồn tại nhược điểm: chi phí khóa cao, nguy cơ deadlock do lập trình viên phải quản lý quá nhiều yếu tố, và độ phức tạp trong logic mã nguồn.

Hôm qua gần như đã quyết định dùng giải pháp “khóa bản đồ” (map lock), hy sinh khả năng song song giữa các người chơi trong cùng tiến trình bản đồ. Phương án này không tồi, nhưng khi nằm ngủ tối qua tôi vẫn trằn trọc không yên. Vì như vậy sẽ đánh mất mục tiêu ban đầu là xây dựng máy chủ game theo kiến trúc song song. Nếu phải làm như vậy, thà rằng quay về mô hình đơn giản “một bản đồ - một tiến trình” còn hơn.

Chắc chắn phải tồn tại một phương pháp có thể tránh dùng khóa và loại bỏ hoàn toàn gánh nặng quản lý xung đột đọc/ghi dữ liệu khỏi vai lập trình viên. Hôm nay tôi đã hoàn thành việc triển khai một cấu trúc dữ liệu tạm gọi là “từ điển nguyên tử”.

Module này được viết bằng C và sử dụng trong Lua. Từ phía Lua, nó hoạt động giống hệt một bảng Lua thông thường, chỉ khác ở các ràng buộc sau: khóa (key) chỉ có thể là chuỗi, giá trị (value) chỉ chấp nhận số và chuỗi, không hỗ trợ cấu trúc phân cấp. Các ràng buộc này chỉ nhằm đơn giản hóa việc triển khai, không phải do giới hạn thuật toán.

Chúng ta có thể đặt các dữ liệu liên quan vào một từ điển nguyên tử. Từ điển có thể được chia sẻ giữa các Lua State khác nhau trong cùng tiến trình (với một số cải tiến nhỏ, thậm chí có thể vượt qua ranh giới tiến trình thông qua bộ nhớ chia sẻ). Đối với Lua State sở hữu, việc đọc/ghi từ điển hoàn toàn trong suốt.

Tôi cung cấp một hàm barrier để ứng dụng gọi định kỳ. Trong hệ thống của chúng tôi, chỉ cần chèn lời gọi barrier vào hàm xử lý gói tin dữ liệu là đủ.

Các sửa đổi từ Lua State sở hữu chỉ được công bố với các Lua State khác sau khi gọi barrier. Điều này đảm bảo bạn sẽ không bao giờ thấy trạng thái trung gian của từ điển, mà chỉ thấy các “bức ảnh toàn cảnh” hoàn chỉnh.

Cơ chế triển khai như sau:

• Ước lượng giới hạn số luồng vật lý của hệ thống (trong trường hợp của chúng tôi, con số này luôn ≤ số nhân CPU)
• Mỗi từ điển nguyên tử được cấp phát trước N bản sao (N > số luồng tối đa)
• Từ điển duy trì một tham chiếu chỉ đến bản sao mới nhất
• Mọi thao tác đọc/ghi đều truy cập bản sao mới nhất và tăng bộ đếm tham chiếu. Việc tham chiếu này được thực hiện trực tiếp, đồng thời ghi nhận vào bộ điều khiển Barrier của Lua State hiện tại.

Khi muốn sửa đổi từ điển:

1. Kiểm tra xem kể từ barrier lần trước đã có sửa đổi nào chưa
2. Nếu là sửa đổi đầu tiên, tìm một bản sao trống trong vùng dự trữ, sao chép nội dung bản gốc sang, rồi thực hiện sửa đổi

Mỗi lần gọi barrier:

• Duyệt qua tất cả từ điển đã được đọc/ghi
• Nếu từ điển đã bị sửa đổi, cập nhật nó thành phiên bản mới nhất (đồng thời xử lý các chuỗi ký tự trong pool dự trữ)
• Nếu chưa sửa đổi, giảm bộ đếm tham chiếu tương ứng

Giải pháp này không xử lý xung đột ghi đồng thời. Nếu có nhiều hơn một luồng cùng sửa đổi, chỉ có một phiên bản được giữ lại. Đây là một thỏa thuận trong khung làm việc của chúng tôi - chúng tôi chỉ cho phép một luồng ghi duy nhất tại mọi thời điểm. Về mặt lý thuyết, có thể bổ sung cơ chế rollback nếu cần thiết.

Mỗi người chơi có khoảng 100 thuộc tính (phần lớn là số thực). Mỗi lần sửa đổi cần sao chép khoảng 0.5KB dữ liệu. Trong logic xử lý người chơi, trung bình mỗi giây xảy ra khoảng 10 thao tác ghi. Như vậy chi phí sao chép dữ liệu là 5KB/s/người chơi - mức chấp nhận được.

Để kiểm tra tính đúng đắn của module, tôi đã xây dựng chương trình đa luồng với 30 luồng. Mỗi luồng sở hữu một từ điển nguyên tử chứa 4 trường A B C D. Trong vòng lặp 10,000 lần, mỗi luồng cập nhật 4 trường này (3 trường đầu lấy giá trị ngẫu nhiên, trường thứ tư bằng 100 trừ tổng 3 trường trước). Đồng thời, mỗi luồng kiểm tra xem tổng 4 trường trong từ điển của 29 luồng còn lại có bằng 100 không.

Tôi rất hài lòng khi hoàn thành module này chỉ trong một ngày, với khoảng 800 dòng C và 200 dòng mã kiểm thử. Dù có vài lỗi nhỏ ban đầu khiến module không qua được bài kiểm thử tự viết, nhưng đã nhanh chóng được sửa chữa.

Phiên bản mã nguồn mở: