Cải Tiến Hệ Thống ID 64-Bit Tích Hợp Trong Luaecs

Anonymous trong Full-Stack và Mã Nguồn Mở

2022-08-01 Khoảng 1000 từ 5 phút

Nội dung

Trong quá trình thiết kế luaecs vào năm ngoái, một vấn đề còn tồn đọng là cơ chế tham chiếu entity cụ thể. Ban đầu tôi cho rằng hệ thống tag linh hoạt có thể giải quyết phần lớn nhu cầu, hoặc người dùng có thể tự xây dựng component ID 64-bit kèm thuật toán tìm kiếm nhị phân. Tuy nhiên đến đầu năm nay, qua quan sát cả người dùng nội bộ và bên ngoài, tôi nhận ra nhu cầu tham chiếu trực tiếp đến entity là không thể tránh khỏi. Điều này dẫn đến việc phát triển giải pháp tham chiếu phi xâm nhập mới.

Gần đây, các cuộc thảo luận xung quanh vấn đề này đã khiến tôi xem xét lại việc tích hợp cơ chế tham chiếu entity gốc. Trước đây, các component liên kết với cùng một entity sử dụng ID 32-bit (gọi là entity id), nhưng thiết kế này gây ra hai vấn đề chính:

Hiện tượng vòng lặp ID: Với hệ thống vận hành lâu dài, việc ID 32-bit vượt quá giới hạn và quay lại từ đầu là điều tất yếu. Điều này dẫn đến nguy cơ tái sử dụng ID của entity đã bị xóa.
Cơ chế rearrange phức tạp: Để giải quyết vấn đề trên, tôi đã thiết kế cơ chế “sắp xếp lại” khi ID vượt quá ngưỡng 31-bit. Trong quá trình update hệ thống, toàn bộ ID sẽ được tái phân bổ về giá trị nhỏ hơn. Tuy nhiên, cơ chế này gây ra overhead đáng kể.

Vấn đề thực sự phát sinh khi ID được phơi bày cho tầng ứng dụng. Một giải pháp đơn giản là chuyển sang ID 64-bit để loại bỏ hoàn toàn hiện tượng vòng lặp. Tuy nhiên, việc này sẽ làm tăng 4 byte trên mỗi component (tổng cộng 32-bit payload), đồng thời làm giảm hiệu suất tìm kiếm. Đây không phải là lựa chọn tối ưu.

Giải pháp tối ưu: Component ID 64-bit độc lập

Chúng tôi quay lại ý tưởng ban đầu nhưng cải tiến sâu sắc: mỗi entity sẽ được sinh ra một component ID 64-bit độc lập, đảm bảo tính ổn định vĩnh viễn. Khi cần giải tham chiếu, thuật toán tìm kiếm nhị phân với độ phức tạp O(logN) sẽ được sử dụng. Trong thực tế, các thao tác phổ biến nhất trên ECS vẫn là lọc và duyệt tập hợp entity, chứ không phải thao tác trên entity đơn lẻ.

Ban đầu, luaecs đã cung cấp API tìm kiếm nhị phân trên component tập hợp có thứ tự. Tuy nhiên, việc tích hợp trực tiếp vào hệ thống mang lại hai lợi thế vượt trội:

Tiết kiệm bộ nhớ: ID nội bộ dùng để liên kết component có thể rút gọn còn 24-bit (3 byte), thay vì 4 byte như trước.
Hiệu suất cao hơn: Khi entity bị xóa, hệ thống sẽ nén ID về phía giá trị nhỏ hơn trong mỗi chu kỳ update.

Giải pháp này giới hạn tổng số entity đồng thời trong hệ thống ở mức 16 triệu (2^24), nhưng hoàn toàn phù hợp với nhu cầu thực tế hiện tại. Đồng thời, việc giảm 1 byte trên mỗi component mang lại lợi ích đáng kể về hiệu suất bộ nhớ.

Tối ưu hóa tính năng Group

Tính năng group được bổ sung trong năm nay cũng có thể được cải tiến sâu sắc. Khi tạo entity, người dùng có thể gán một group ID 32-bit. Sau đó, hệ thống cho phép đánh tag lên toàn bộ entity trong group để thực hiện lọc nhanh. Đây là tính năng quan trọng trong engine của chúng tôi, đặc biệt hiệu quả cho các tác vụ tiền xử lý đối tượng.

Ban đầu, mỗi group đều yêu cầu một mảng ID 64-bit riêng biệt. Nay với cơ chế ID 64-bit mới, hai hệ thống này có thể được hợp nhất. Đặc điểm nổi bật của group:

Tính đơn điệu: Entity chỉ được thêm vào group khi tạo mới, và chỉ bị loại bỏ khi xóa. Do đó, ID trong group luôn tăng dần.
Chỉ duyệt tuần tự: Không có nhu cầu truy cập ngẫu nhiên, chỉ cần thao tác duyệt toàn bộ.

Dựa trên đặc điểm này, chúng tôi áp dụng kỹ thuật mã hóa hiệu số biến đổi (delta encoding + varint). Cụ thể:

Tính hiệu số giữa các ID liên tiếp
Mã hóa hiệu số bằng varint 128-bit (mỗi byte chứa 7 bit dữ liệu, 1 bit đánh dấu tiếp tục)

Ví dụ với chuỗi ID 1, 2, 5, 200:

Hiệu số: 1, 1, 3, 195
Trừ 1 để tối ưu: 0, 0, 2, 194
Mã hóa varint: 0x00, 0x00, 0x02, 0xC2 0x01 (chỉ cần 5 byte thay vì 32 byte ban đầu)

Việc xóa entity khỏi group không thực hiện ngay lập tức, mà được xử lý trong quá trình duyệt group tiếp theo. Điều này giúp giảm overhead và tận dụng cơ hội tối ưu hóa dữ liệu.

Hướng phát triển

Toàn bộ các cải tiến trên hiện đang được phát triển trên nhánh v2. Trong tương lai, chúng tôi sẽ tiếp tục nghiên cứu các kỹ thuật nén dữ liệu tiên tiến hơn, đồng thời mở rộng khả năng truy vấn phức tạp dựa trên hệ thống ID ổn định này.

Việc tái thiết kế từ ID 32-bit sang 64-bit không chỉ giải quyết vấn đề kỹ thuật, mà còn mở ra hướng phát triển mới cho hệ sinh thái luaecs, giúp cân bằng giữa hiệu suất, tính ổn định và khả năng mở rộng trong dài hạn.