Valkey: Tái thiết bảng băm cho phần cứng hiện đại giúp tăng hiệu suất và tiết kiệm bộ nhớ

Madelyn Olson – kỹ sư phần mềm phụ trách dự án Valkey và làm việc tại Amazon ElastiCache – đã chia sẻ câu chuyện về quá trình phát triển cấu trúc bảng băm (hash table) cho hệ thống lưu cache Valkey, một bản sao tương thích với Redis được cải tiến về mặt kiến trúc để tận dụng phần cứng hiện đại.

Bài trình bày đi sâu vào cách Valkey rời bỏ thiết kế bảng băm truyền thống dựa trên con trỏ (pointer chasing) vốn còn nhiều điểm hạn chế về bộ nhớ đệm (cache) của CPU, thay vào đó áp dụng các bảng băm kiểu “Swedish table” – lấy cảm hứng từ Swiss table của Google giúp tăng mật độ bộ nhớ lưu trữ và giảm độ trễ truy xuất dữ liệu.

Từ Redis tới Valkey: động lực cải tiến

Redis vốn là một dự án mature, được sử dụng rộng rãi làm cache dữ liệu với nhiều tính năng phong phú nhưng có điểm yếu về mặt hiệu suất và tối ưu bộ nhớ, đặc biệt khi chạy trên phần cứng hiện đại. Nhưng Valkey, được phát triển bởi nhóm cựu maintainers Redis, cam kết giữ tương thích ngược đồng thời thử nghiệm các cải tiến mới.

Valkey hướng tới hỗ trợ đa dạng kiểu dữ liệu, các giá trị nhỏ phổ biến trong cache với TTL (time to live) linh hoạt, phục vụ đa dạng nhu cầu người dùng. Đặc biệt, họ chú trọng làm sao để việc mở rộng bảng băm diễn ra dần dần (incremental rehashing) tránh gián đoạn hệ thống.

Vấn đề với bảng băm cũ

Bảng băm truyền thống sử dụng linked list để xử lý xung đột (collision). Mỗi phần tử mất 3 con trỏ, dẫn tới overhead bộ nhớ lớn, các truy xuất chậm bởi nhiều bước pointer chasing gây ra cache miss. Truy xuất dữ liệu và xử lý xung đột càng khiến độ trễ tăng cao, một điểm tối kỵ với cache dữ liệu quan trọng.

Đặc biệt, chi phí truy cập RAM chính (main memory) rất lớn so với truy cập cache CPU. Valkey đã áp dụng kỹ thuật memory prefetching để tải trước vùng nhớ cần thiết vào bộ nhớ đệm nhằm giảm độ trễ.

Ý tưởng cải tiến: các bảng băm cache-aware “Swedish table”

Valkey áp dụng thiết kế dựa trên Swiss table tối ưu bộ nhớ cache:

• Bảng dữ liệu chia thành các bucket lớn (64 byte) chứa 7 entry.
• Mỗi bucket kèm dữ liệu metadata nhỏ gọn giúp tăng tốc độ truy xuất.
• Thay vì linked list, Valkey sử dụng phương pháp open addressing, tìm vị trí kế tiếp lưu giữ phần tử khi xung đột xảy ra.
• Kết hợp thêm phương pháp chaining nhẹ giữa bucket khi bucket đầy.
• Hỗ trợ dynamic sized struct cho phép nhúng dữ liệu metadata và key trực tiếp vào bảng giúp giảm thiểu pointer không cần thiết.

Điều này giúp giảm khoảng 40% chi phí bộ nhớ so với kiểu bảng băm truyền thống, đồng thời tăng khả năng cache hit và tăng hiệu suất qua việc giảm lượng pointer bị đuổi theo trong bộ nhớ.

Đánh đổi trong thực tế và kiểm thử nghiêm ngặt

Valkey xây dựng hệ thống kiểm thử rất nghiêm khắc:

• Unit tests, integration tests chạy trên address sanitizer để phát hiện lỗi truy cập bộ nhớ.
• Tích hợp các assertion trong code để tự kiểm tra các giả định về bộ nhớ trong thực tế.
• Tiến hành benchmark cả mức micro (đo đếm từng thao tác hash table) và macro (đo throughput hệ thống) trên các kịch bản hit/miss cache khác nhau.
• Sử dụng flame graphs để phân tích điểm nghẽn hiệu suất.

Trong quá trình ra mắt, Valkey gặp phải một số bug liên quan đến thao tác random lấy phần tử (SPOP) và việc preload cache bị sai offset, tuy nhiên cộng đồng Open Source đã giúp phát hiện và sửa chữa kịp thời.

Có nên chuyển sang Rust?

Madelyn Olson chia sẻ quan điểm cá nhân: Rust rất tuyệt, an toàn và là lựa chọn tốt cho dự án mới. Tuy nhiên với một hệ thống cơ sở mã C đã phát triển phức tạp như Valkey, việc rewrite toàn bộ sang Rust chưa chắc hữu ích mà có thể tạo thêm các lỗi tiềm ẩn. Do đó, nhóm hiện trung thành với C nhưng xây dựng các wrapper an toàn bằng Rust ở lớp trên để tận dụng lợi ích của Rust.

Bài học và lời khuyên

• Hiểu sâu sắc mô hình truy cập dữ liệu để thiết kế cấu trúc phù hợp.
• Luôn kiểm thử kỹ lưỡng, tích hợp nhiều lớp kiểm tra chặt chẽ.
• Benchmark sớm và thường xuyên, không chỉ về tốc độ mà còn về hiệu quả bộ nhớ.
• Mở rộng kiến thức qua nhiều dự án, tận dụng nền tảng và kinh nghiệm cộng đồng.

Valkey là một ví dụ thiết thực cho việc xây dựng phần mềm hệ thống hiện đại: cần linh hoạt, tối ưu theo đặc điểm phần cứng mới, đồng thời đảm bảo hiệu năng và độ tin cậy trong môi trường sản xuất.

---

Tham khảo

• Bài trình bày Swiss Table Deep Dive tại CppCon
• Blog chi tiết của Viktor – tác giả chính về cấu trúc bảng băm mới của Valkey
• Các buổi meetup về Valkey tại Seattle

Valkey là dự án mở và đang phát triển, mang lại góc nhìn quý giá cho cộng đồng phần mềm đặc biệt là các hệ thống cache độ trễ thấp.