Ghi Chú Phát Triển (6): Lưu Trữ Dữ Liệu Cấu Trúc Chia Sẻ
Trước khi bắt đầu chủ đề này, đã hơn một tuần trôi qua kể từ bài ghi chú phát triển trước. Tôi dự định sẽ tiếp tục viết các ghi chú phát triển mãi mãi, bởi vì quá trình phát triển chắc chắn sẽ không trải đầy hoa hồng. Những quyết định kỹ thuật, sự từ bỏ và thay đổi ý tưởng có thể xảy ra liên tục. Việc ghi lại công khai hành trình này không chỉ giúp lưu giữ luồng suy nghĩ mà còn là cách tự nhắc nhở bản thân. Không nên sa đà vào chi tiết kỹ thuật đến mức đánh mất tiến độ phát triển sản phẩm. Và một ngày nào đó, khi dự án hoàn thành, tôi có thể tự hào nói với mọi người: “Hãy nhìn xem, sản phẩm của chúng ta đã được xây dựng từng bước như thế này đây. Mỗi mốc son đều chứa đựng biết bao tâm huyết của các kỹ sư phát triển.”
Trong nhóm chúng tôi, những tranh luận về phương án kỹ thuật luôn rất gay gắt. Việc thuyết phục mọi người tin vào ý tưởng của mình là điều vô cùng khó khăn. Ví dụ gần đây là cuộc tranh luận về luồng dữ liệu phía server trong tương lai.
Tôi mong muốn tách biệt dữ liệu và logic, với các điểm truy cập dữ liệu vật lý độc lập. Mỗi kết nối bên ngoài sẽ được phục vụ bởi một thực thể agent riêng biệt. Điều này khiến chi phí giao tiếp giữa các tiến trình trở nên tần suất cao. Đối với một trò chơi chiến đấu thời gian thực, chúng tôi lại cần tốc độ tương tác giữa các thực thể đủ nhanh. Do đó, phương án tưởng chừng đẹp đẽ này có thể gặp phải vấn đề hiệu năng không đạt yêu cầu - một trong những điểm tranh cãi nóng bỏng nhất.
Cá nhân tôi khá tự tin có thể giải quyết bài toán chia sẻ dữ liệu giữa các tiến trình với hiệu năng cao. Thực ra bài viết trước đã đề cập đến vấn đề này, nhưng lần này tôi sẽ đi sâu hơn.
Vấn đề cốt lõi nằm ở chỗ: Mỗi PC (người chơi) và cả NPC (nếu có) sẽ tồn tại ở các thực thể khác nhau (tôi dùng từ “thực thể” thay vì “tiến trình” để tránh hiểu nhầm với tiến trình hệ điều hành). Khi chúng tương tác, mã logic sẽ đọc/ghi dữ liệu của các đối tượng khác. Cuối cùng, một thực thể sẽ chịu trách nhiệm lưu giữ và duy trì toàn bộ dữ liệu của một đối tượng, đồng thời cung cấp giao diện RPC để thao tác dữ liệu. Vì thế giới ảo sẽ được xây dựng trên nhiều máy vật lý, nên RPC là phương thức duy nhất khả thi. Bạn có thể hình dung mỗi thực thể như một cơ sở dữ liệu, lưu trữ toàn bộ dữ liệu của mình và mở giao diện RPC để đọc/ghi dữ liệu từ bên ngoài.
Tuy nhiên, với những dữ liệu “nóng” cần trao đổi thường xuyên, dù tối ưu giao thức và triển khai đến đâu cũng khó đạt được hiệu năng mong muốn. Ít nhất là không thể sánh bằng việc xử lý tất cả dữ liệu trong cùng một tiến trình.
Vì vậy, ngoài giao diện RPC, tôi muốn cung cấp thêm một API trực tiếp hơn sử dụng cơ chế trạng thái chia sẻ. Nếu xác định hai thực thể cần trao đổi dữ liệu thường xuyên, chúng ta có thể di chuyển quy trình xử lý của hai thực thể này về cùng một máy vật lý. Khi đó, tiến trình xử lý đồng thời hai đối tượng có thể dùng cơ chế bộ nhớ chia sẻ để đọc/ghi dữ liệu của cả hai, đạt hiệu năng lý thuyết cao nhất.
Điều này dẫn đến bài toán: Làm thế nào để nhiều tiến trình cùng truy cập một khối dữ liệu cấu trúc? Trong đó, việc duy trì cấu trúc dữ liệu là thách thức lớn nhất.
Giải pháp như sau: Chúng ta coi dữ liệu cần chia sẻ và tương tác chính là dữ liệu cần được lưu trữ lâu dài. Nhìn tổng thể, nó giống như một cơ sở dữ liệu bộ nhớ nhỏ, có thể được tuần tự hóa thành luồng nhị phân theo giao thức tương tự Google Protocol Buffers. Nó khác với cấu trúc dữ liệu trong bộ nhớ ở chỗ có thêm một số ràng buộc giúp đơn giản hóa vấn đề mà vẫn đáp ứng được đa dạng nhu cầu.
Các kiểu dữ liệu giới hạn trong 6 loại:
- nil
- number
- boolean
- string
- map
- array
6 kiểu này đủ để mô tả mọi nhu cầu, điều này đã được chứng minh qua thực tiễn sử dụng Lua. Tuy nhiên ở đây, chúng tôi chia table của Lua thành map và array như một sự tham khảo từ Protocol Buffers. Map ở đây có sơ đồ dữ liệu (data scheme) rõ ràng, không phải từ điển tùy ý. Các key phải là các nguyên tử được định nghĩa trước, thực chất là các ID nguyên, còn value có thể thuộc bất kỳ kiểu nào khác. Array là tập hợp đơn giản các phần tử cùng kiểu, không cho phép array lồng array - điều đã được chứng minh khả thi qua ứng dụng Protocol Buffers.
Về bản chất, dữ liệu của mọi thực thể đều có thể biểu diễn dưới dạng map - tập hợp các cặp key-value. Array chỉ là sự lặp lại của các key giống nhau (tương tự từ khóa repeated trong Protocol Buffers).
Điểm đặc biệt là ngoài string, tất cả các value đều có độ dài cố định, thuận lợi cho việc lưu trữ đồng nhất trong C. Mỗi mục dữ liệu gồm id - type - value - brother. Map được lưu trữ dưới dạng cây nhị phân để đảm bảo độ dài cố định của nút, trong đó cây con trái là con đầu tiên, cây con phải là nút anh em.
Chúng tôi sử dụng một khối bộ nhớ cố định để lưu trữ toàn bộ dữ liệu này dưới dạng các bản ghi độ dài bằng nhau. Trong bản ghi map, cả cây con trái và phải đều chứa chỉ số toàn cục của bản ghi. String được lưu trữ riêng biệt, tất cả các string đều nằm trong một vùng bộ nhớ khác (có thể là cùng một khối nhưng ở phần đối diện). Trong bảng ghi, vị trí của string sẽ được lưu tham chiếu đến pool string.
Giải pháp này mang lại lợi ích gì? Nhờ có sơ đồ dữ liệu (có thể mô tả trực tiếp bằng định dạng Protocol Buffers), quy mô dữ liệu ở mỗi cấp có thể dự đoán được. Mọi dữ liệu đều được lưu dưới dạng bản ghi độ dài bằng nhau. Các thao tác sửa đổi toàn bộ khối dữ liệu có thể coi là sửa đổi cục bộ hoặc bổ sung tổng thể. Hai thao tác này đều có thể triển khai không khóa (lock-free).
Nói cách khác, mỗi lần sửa đổi một nút cụ thể trong cây đều không ảnh hưởng đến dữ liệu của các nút khác.
Cấu trúc dữ liệu tổ chức như vậy có tác dụng gì? Trước tiên, bài toán lưu trữ lâu dài trở nên đơn giản, nhưng đây chỉ là lợi ích phụ. Dù dữ liệu có thể ghi lại đầy đủ các cấu trúc phức tạp, nhưng việc tr