Triển Khai Bảng Băm Đa Luồng
Trong Lua, các chuỗi ngắn được áp dụng kỹ thuật interning chuỗi, nghĩa là trong cùng một máy ảo, các chuỗi có giá trị giống nhau chỉ tồn tại duy nhất một bản. Điều này giúp tăng tốc độ tra cứu bảng băm sử dụng chuỗi làm khóa lên đáng kể. Vì độ phức tạp của phép so sánh chuỗi giảm từ O(n) xuống còn O(1), việc kiểm tra sự trùng khớp giữa khóa truy vấn và khóa trong bảng băm chỉ cần so sánh địa chỉ con trỏ của đối tượng chuỗi.
Khi giải quyết bài toán chia sẻ đối tượng chuỗi giữa nhiều máy ảo Lua, tôi đã hợp nhất các bảng chuỗi ngắn của các máy ảo khác nhau thành một bảng chuỗi chung (SSM - Shared String Module) cho toàn bộ máy ảo trong cùng một tiến trình. Ban đầu, để đơn giản hóa việc thu gom rác (GC) phức tạp giữa các máy ảo, tôi áp dụng cơ chế “chỉ thêm vào, không xóa” cho SSM. Cụ thể, các chuỗi ngắn được đưa vào SSM đến khi đạt ngưỡng giới hạn, tránh tình trạng bảng phình to vô hạn. Tuy nhiên, Lua không phân biệt rõ ràng giữa chuỗi được interning và chuỗi thông thường - hiện tại chỉ dựa vào độ dài chuỗi để quyết định. Điều này khiến chuỗi chưa qua interning không thể tồn tại song song với chuỗi trong SSM. Do đó, các chuỗi đã tồn tại trong bảng chuỗi cục bộ (LSM - Local String Module) của máy ảo sẽ không được lấy từ SSM.
Thuật toán interning chuỗi trong Lua sau khi sửa đổi hoạt động như sau:
- Kiểm tra LSM: Nếu chuỗi đã tồn tại trong bảng chuỗi cục bộ, trả về ngay lập tức (giữ nguyên cơ chế gốc của Lua).
- Tra cứu SSM: Nếu tìm thấy chuỗi trong bảng chia sẻ, trả về kết quả.
- Kiểm tra ngưỡng SSM: Nếu SSM đã đầy, thêm chuỗi vào LSM và trả về.
- Thêm vào SSM: Đưa chuỗi vào bảng chia sẻ và trả về.
Với việc vận hành hàng nghìn máy ảo Lua trong một tiến trình, SSM cần một cấu trúc bảng băm có khả năng xử lý truy cập đồng thời cực cao. Trong thiết kế ban đầu, tôi dự đoán kích thước SSM dựa trên ngưỡng giới hạn để xác định số lượng bucket phù hợp, giảm thiểu va chạm hash tối đa. Thay vì xử lý cơ chế rehash động, tôi cố định số bucket để đơn giản hóa đồng thời tăng hiệu năng đồng thời.
Giải pháp tối ưu hiệu năng đồng thời áp dụng khóa đọc/ghi theo bucket:
- Không khóa khi tính hash: Việc xác định bucket dựa trên giá trị hash được thực hiện mà không cần khóa.
- Phân tách quyền truy cập: Mỗi bucket có một khóa đọc/ghi riêng. Vì phần lớn thao tác là đọc (khi máy ảo chạy, chỉ các chuỗi mới tạo từ bên ngoài mới cần interning), cơ chế này giảm thiểu cạnh tranh khóa.
- Hiệu quả thực tế: Thử nghiệm với hàng triệu chuỗi cho thấy tỷ lệ xung đột hash trung bình chỉ khoảng 1.2-1.3 chuỗi/bucket khi bảng đầy, gần như đạt hiệu năng O(1).
Sự cố từ việc chia sẻ hằng số prototype
Khi mở rộng tính năng chia sẻ bảng hằng số trong prototype hàm, một sự cố nghiêm trọng đã xảy ra. Cơ chế tạm thời mở rộng SSM khi tải mã mới được kích hoạt, nhưng do vị trí kích hoạt không hợp lý:
- Lỗi logic: Mỗi lần gọi
requiretrong Lua, toàn bộ quá trình tìm kiếm tệp (kể cả các tệp không tồn tại) đều kích hoạt mở rộng SSM. - Tích lũy ngưỡng: Việc tăng ngưỡng SSM thêm 4096 bucket mỗi lần mở rộng không được hoàn tác sau khi hoàn tất, dẫn đến SSM phình to liên tục.
Hậu quả là sau 2 ngày vận hành, số lượng phần tử trong SSM vượt xa dự kiến, khiến mỗi bucket chứa hàng trăm chuỗi (có bucket lên đến hơn 1000). Điều này phá vỡ giả định ban đầu về hiệu năng O(1), làm tăng tải CPU và gây chậm trễ nghiệm trọng cho người dùng.
Giải pháp khắc phục và cải tiến
- Tạm thời: Vô hiệu hóa cơ chế tự động mở rộng SSM khi tải mã nguồn.
- Cải tiến lâu dài: Thêm khả năng mở rộng bucket động cho SSM mà không cần dừng hệ thống (stop-the-world). Cụ thể:
- Cấu trúc hai bảng A/B:
- Bảng A: Cho phép đọc/ghi, nhận phần tử mới.
- Bảng B: Chỉ đọc, chứa dữ liệu cũ.
- Cơ chế chuyển đổi:
- Khi cần resize, tạo bảng B từ A (chuyển A sang chế độ chỉ đọc), sau đó khởi tạo bảng A mới. Quá trình này chỉ cần 2 thao tác con trỏ, đảm bảo thời gian dừng gần như bằng 0.
- Resize tuần tự từng bucket của bảng B (với khóa riêng cho từng bucket), cho phép các thao tác đọc khác vẫn diễn ra bình thường.
- Dọn dẹp B: Sau khi resize hoàn tất, bảng B (đã rỗng) sẽ bị xóa dưới sự kiểm soát của khóa ghi.
- Cấu trúc hai bảng A/B: