Kiến Trúc Lưu Trữ Chuỗi Gián Đoạn

Hầu hết các cấu trúc dữ liệu cơ bản đều có độ dài cố định, điều này khiến cho việc tối ưu quản lý bộ nhớ trở nên dễ dàng hơn nhiều. Tuy nhiên, chuỗi ký tự lại là một trường hợp đặc biệt. Quản lý bộ nhớ có bản chất hoàn toàn khác biệt so với quản lý các tài nguyên khác. Nó giống như việc cắt bánh kem - ta có thể dễ dàng cắt lấy phần cần thiết từ khối bánh nguyên vẹn, nhưng việc ghép nối các mảnh vụn đã qua sử dụng lại cực kỳ khó khăn. Hãy tưởng tượng một ví dụ cực đoan: nếu heap bộ nhớ 2GB bị phân bổ vài byte ở chính giữa mà không bao giờ giải phóng, khối bộ nhớ này sẽ vĩnh viễn bị chia cắt thành hai phần dưới 1GB. Điều này khiến việc phân bổ block 1GB sau đó trở nên không thể thực hiện.

Dù cải tiến thuật toán phân bổ có thể giảm thiểu phân mảnh, nhưng ngay cả jemalloc - thư viện đã đầu tư rất nhiều cho vấn đề này - cũng không đáp ứng được kỳ vọng của người dùng thông thường. Kinh nghiệm của tôi cho thấy với heap 16GB dành cho ứng dụng chạy dài hạn với tần suất cấp phát/giải phóng bộ nhớ cao, hiệu suất sử dụng thực tế chỉ đạt khoảng 10GB. Con số này tính theo tổng kích thước các lần gọi malloc. Tùy cơ chế sử dụng bộ nhớ của từng ứng dụng, hiệu suất thực tế có thể dao động rất lớn.

Tỷ lệ sử dụng 60% nghe có vẻ ổn, nhưng vẫn khiến nhiều người thắc mắc: “Số bộ nhớ còn lại đã đi đâu?”. Một giải pháp hiệu quả là chuẩn hóa kích thước cấu trúc dữ liệu và áp dụng cơ chế quản lý bộ nhớ riêng biệt. Điều này tương đương với việc phân tầng quản lý tài nguyên thay vì dồn toàn bộ vào một heap toàn cục. Các cấu trúc có độ dài cố định có thể tái sử dụng trực tiếp sau khi thu hồi, giúp loại bỏ hầu hết phân mảnh bên ngoài.

Đáng chú ý, cấu trúc độ dài cố định cũng thân thiện hơn với quá trình lưu trữ bền vững (persistence). Bài viết này muốn thảo luận về kiểu chuỗi ký tự bất biến, liên tục, mang ý nghĩa nội tại - cụ thể là kiểu string trong Lua.

Trông qua thì chuỗi ký tự dường như bắt buộc phải lưu trữ liên tục trong bộ nhớ. Nhưng nếu phân tích kỹ, đây không phải yêu cầu bắt buộc. Điều duy nhất cần thiết là chuỗi phải thể hiện được dãy byte nhất quán với thế giới bên ngoài. Phần lớn các chức năng liên quan đến chuỗi chỉ yêu cầu tính duy nhất của nó. Trong Lua, chuỗi có thể được xem như một atom - thứ tự sắp xếp các byte bên trong không quan trọng bằng khả năng tham gia vào quá trình so sánh và làm khóa trong bảng băm. Những yêu cầu này không đòi hỏi truy cập ngẫu nhiên vào dữ liệu nội bộ.

Điều khiến Lua trở nên đặc biệt là nhu cầu trao đổi dữ liệu với thế giới bên ngoài thông qua API C. Khi kiểu dữ liệu nội bộ cần tương tác với môi trường bên ngoài, nó phải được biểu diễn dưới dạng vùng nhớ liên tục:

1

const char *lua_tolstring (lua_State *L, int index, size_t *len);

Thiết kế API này chính là lý do khiến Lua không thể triển khai cơ chế GC di động (di chuyển đối tượng trong quá trình dọn dẹp bộ nhớ) hay lưu trữ trực tiếp chuỗi ngắn trong cấu trúc Value (phải dùng GCObject riêng). Nếu thay đổi giao diện trao đổi dữ liệu, chúng ta có thể đạt được tính linh hoạt cao hơn. Ví dụ:

1

const char *lua_tolstring (lua_State *L, int index, size_t *len, char tmp[]);

Tham số bổ sung tmp[] cho phép sao chép dữ liệu chuỗi vào buffer bên ngoài. Tham số *len trở thành inout - nhận kích thước buffer đầu vào và trả về độ dài thực tế của chuỗi. Buffer tmp[] thường được đặt trên stack C, và Lua có thể chọn không sử dụng nó.

Tiếp theo là thiết kế cấu trúc dữ liệu chuỗi mới. Tôi đề xuất giải pháp phân đoạn 2+14 byte, với 64K đoạn nhỏ tạo thành một nhóm lớn:

1
2
3
4

struct stringid_page {
  unsigned short header[0x10000];
  unsigned char data[0x10000][14];
};

Mỗi trang 1MB có thể chứa tối đa 64K đoạn chuỗi. 2x64K byte cho header liên kết các đoạn, 14x64K byte cho dữ liệu thực tế.

Chuỗi ngắn chỉ cần một đoạn duy nhất, header trỏ về chính nó. Ví dụ đoạn 0 sẽ có header[0] = 0. Chuỗi dài hơn sẽ có header trỏ đến đoạn tiếp theo cho đến đoạn cuối cùng trỏ về chính nó. Thuật toán quản lý nếu ưu tiên phân bổ đoạn liên tục thì chuỗi vẫn giữ được tính liên tục (vì header và data được tách biệt).

Vấn đề còn lại là biểu diễn độ dài chuỗi. Thay vì lưu riêng độ dài, tôi đề xuất dùng ký tự kết thúc 0 nhưng đảm bảo an toàn với dữ liệu nhị phân. Trong đoạn cuối, sau nội dung chuỗi sẽ thêm 00 + n ký tự FF (n từ 0-13).

Với thiết kế này, một trang có thể đánh chỉ số 16bit cho từng đoạn, tạo ra chuỗi dài tối đa (64K * 14 -1) byte (~900KB) - đủ đáp ứng hầu hết nhu cầu. Hỗ trợ nhiều trang bằng cách mã hóa ID trang và chỉ số vào số 32bit.

Tôi đã dành thời gian viết một bản triển khai thử nghiệm ý tưởng này:

Phiên bản này bổ sung đếm tham chiếu để chia sẻ chuỗi trùng lặp. Khác với các đối tượng GC phức tạp, chuỗi chỉ có thể được tham chiếu chứ không tham chiếu đến đối tượng khác. Đếm tham chiếu tiết kiệm bộ nhớ hơn so với quét đánh dấu (không cần bit đánh dấu hay con trỏ danh sách liên kết).

Dù không thể thay thế trực tiếp chuỗi Lua, nhưng thiết kế này phù hợp cho các ứng dụng tương tự Redis. Mô hình bộ nhớ gọn nhẹ và thuận lợi cho việc lưu trữ bền vững hơn.