Vấn Đề Về Ánh Xạ ID Hash Ngắn

Hôm nay mình vừa giải quyết xong một vấn đề khá thú vị. Ban đầu định đăng lên Twitter nhưng nhận ra không thể diễn đạt rõ ràng trong một hai câu. Vì vậy quyết định viết bài blog này để ghi lại chi tiết.

Trong tựa game đang phát triển, chúng tôi dùng một con số ID để xác định bản chất của từng đối tượng trong game. Ví dụ, “Tấm sắt” là 1, “Than đá” là 2, “Máy khai thác” là 3… Nhờ đó, mã C có thể dễ dàng tra cứu thuộc tính của từng đối tượng dựa trên ID. Các thuộc tính này được cấu hình bằng Lua và giữ nguyên trong suốt quá trình chạy game. Chẳng hạn, mỗi đơn vị “Than đá” khi đốt cháy sẽ tạo ra nhiệt lượng 100KJ; một thùng “Tấm sắt” chứa 100 cái.

Để chia sẻ dữ liệu cấu hình giữa C và Lua một cách hiệu quả, mình còn thiết kế riêng một mô-đun cache đặc biệt.

Vấn đề phát sinh khi cần lưu trữ lâu dài các ID này. Vì số lượng loại vật phẩm trong game không quá lớn, để tối ưu hiệu suất thời gian và không gian, mình quyết định dùng ID 16 bit. Con số 64K giới hạn loại vật phẩm dường như là dư thừa. Tuy nhiên, việc phân bổ ID lại gặp nhiều bất cập.

Giải pháp đơn giản nhất là dùng ID tự tăng dần mỗi khi khởi động chương trình. Nhưng cách này khiến ID rất bất ổn định. Khi cần lưu trữ save file, sự thay đổi này khiến các bản lưu trở nên không thể sử dụng được. Vì vậy mình chuyển sang dùng thuật toán hash dựa trên tên vật phẩm và một số tham số nội tại (như số phiên bản) để tạo ra ID.

Tuy nhiên, với độ dài chỉ 16 bit, xung đột hash là điều không thể tránh khỏi. Cuối cùng mình kết hợp thêm cơ chế tự tăng để đảm bảo mỗi vật phẩm có ID duy nhất. Phương pháp này hoạt động ổn định trong thời gian dài. Hầu hết các bản cập nhật nhỏ đều không làm hỏng save file cũ, dù thỉnh thoảng có bản cập nhật lớn gây lỗi tương thích cũng vẫn chấp nhận được. Vì nguồn nhân lực hạn chế, việc phát triển hệ thống nâng cấp save file song song với cập nhật game chưa được ưu tiên.

Gần đây chu kỳ phát triển rút ngắn và thời lượng chơi game tăng lên đáng kể. Ngay cả trong giai đoạn test, việc phải chơi lại từ đầu sau mỗi lần save file bị lỗi cũng bắt đầu ảnh hưởng nghiêm trọng đến tiến độ. Vì vậy hôm nay mình cùng đồng nghiệp đã xem xét lại vấn đề này. Nguyên nhân chính khiến save file lỗi là do các bản cập nhật mới (thêm/sửa/xóa vật phẩm) làm thay đổi thứ tự ID của các loại vật phẩm, khiến thông tin ID trong save file cũ trở nên lỗi thời.

Chúng mình đã thảo luận ba giải pháp phổ biến:

1. Chuyển sang chỉ định ID thủ công - Phương pháp truyền thống này được áp dụng trong nhiều game trước đây. Tuy nhiên cần có nhân viên thiết kế game chuyên trách quản lý bảng ánh xạ, đảm bảo không thay đổi các bản ghi cũ.
2. Tăng độ dài ID - Chuyển sang ID 32/64/128 bit và chỉ dùng hash để sinh ID. Điều này gần như loại bỏ xung đột hash nhưng gây lãng phí tài nguyên.
3. Xây dựng cơ chế nâng cấp save file - Khi tải save file cũ, tiến hành tiền xử lý để cập nhật các ID lỗi thời.

Phương án một bị loại ngay vì dự án không có nhân viên thiết kế chuyên trách. Người duy nhất đảm nhận vai trò này còn phải kiêm nhiệm nhiều công việc khác như thiết kế giao diện, kiểm thử và quản lý dự án. Hơn nữa, quy mô bảng ánh xạ quá lớn khiến việc duy trì thủ công trở nên bất khả thi.

Phương án hai gặp khó khăn về hiệu suất. Dù tăng lên 128 bit có thể tránh hoàn toàn xung đột hash nhưng gây lãng phí bộ nhớ đáng kể. Ngay cả với ID 32 bit, việc duy trì cơ sở dữ liệu tập trung ghi nhận toàn bộ ID đã dùng cũng rất phức tạp, đặc biệt trong giai đoạn phát triển nhanh chóng hiện tại.

Phương án ba về bản chất chỉ là giải pháp tạm thời. Việc xây dựng hệ thống nâng cấp save file đòi hỏi nhiều metadata hiện tại chưa có. Dù đây là hướng phát triển lâu dài, nhưng với tiến độ hiện tại, việc bổ sung toàn bộ dữ liệu cần thiết sẽ tốn rất nhiều thời gian. Ngay cả các game lớn như Factorio hay Stellaris với hàng chục năm phát triển cũng chưa thể đạt đến mức tương thích hoàn toàn với mọi phiên bản save file cũ.

Giải pháp cuối cùng lại vô cùng đơn giản:

Chúng mình quyết định lưu kèm một bảng ánh xạ ID trong save file, ghi lại đầy đủ thông tin chi tiết tạo nên mỗi ID - bao gồm tên gọi, thành phần, số phiên bản… dùng để tính hash ban đầu.

Dù không thể tránh xung đột hash trong không gian 16 bit, nhưng chúng mình có thể trì hoãn việc sinh ID đến thời điểm tải save file. Cụ thể, khi khởi tạo các vật phẩm trong game, hệ thống sẽ không gán ID ngay lập tức. Thay vào đó, khi tải save file, hệ thống sẽ động thực hiện ánh xạ ID dựa trên bảng ghi này. Nếu save file chứa vật phẩm “Tấm sắt” được đánh dấu là 42, thì tại thời điểm tải file, hệ thống mới gán ID 42 cho đối tượng “Tấm sắt” trong bộ nhớ.

Các vật phẩm tồn tại trong hệ thống nhưng không xuất hiện trong save file sẽ được sinh ID theo thuật toán hash thông thường.