Ý tưởng cốt lõi#
Để khắc phục nhược điểm của Log Structured Storage - nơi mỗi truy vấn đòi hỏi quét toàn bộ file, chúng ta có thể áp dụng một ý tưởng đơn giản nhưng hiệu quả: sử dụng HashMap trong RAM làm index. Ý tưởng lần này bắt nguồn từ sự tương đồng giữa Key-Value Store và cấu trúc dữ liệu HashMap (Hash Table) – thường đã có sẵn trong hầu hết các ngôn ngữ lập trình hiện nay. Ta sẽ tận dụng HashMap để lưu index cho dữ liệu trên disk vào trong RAM.
Đây chính là nguyên lý cơ bản của Hash Index. Trên thực tế, Bitcask - storage engine mặc định của Riak - hoạt động dựa trên nguyên lý này, mang lại hiệu suất đọc-ghi cao.
Cách thức hoạt động#
Nhớ lại từ phần trước, dữ liệu ở trong disk được lưu nối tiếp nhau trong 1 file, và được ngăn cách nhau bởi ký tự xuống dòng. Hạn chế của việc này đó là khi truy vấn, ta sẽ phải quét toàn bộ file từ đầu tới cuối, rồi chọn ra line cuối cùng trong các kết quả tìm được.
Giải pháp đơn giản cho vấn đề này đó là: lưu 1 HashMap ở trong RAM, trong đó mỗi key sẽ ánh xạ tới offset trong file log – nơi mà giá trị đang được lưu trữ (minh họa như trong hình bên dưới). Khi thêm hoặc cập nhật một cặp key-value, ta không chỉ ghi vào log mà còn cập nhật HashMap. Khi truy vấn, chỉ cần tra cứu offset trong HashMap, seek đến vị trí đó trong file và đọc giá trị.
Dữ liệu trong DB được load trực tiếp từ disk thông qua việc seek file nên không bị ảnh hưởng bởi kích thước bộ nhớ. Chưa kể, filesystem cũng có cơ chế cache, nên nhiều khi ta còn chẳng cần phải đụng tới thao tác disk IO để đọc dữ liệu. Điểm trừ của phương pháp này đó là index bị giới hạn bởi dung lượng RAM.
Storage engine như Bitcask phù hợp với những bài toán mà giá trị được cập nhật liên tục. Chẳng hạn, Key là URL của 1 video, và Value là số lượng lượt xem (tăng dần mỗi khi có người nhấn vào play video). Tổng quát hơn thì Hash Index phù hợp với bài toán mà có rất nhiều lượt ghi vào DB, tuy nhiên số lượng Key là không nhiều (đủ để chứa được trong bộ nhớ).
Những điểm cần lưu ý khi triển khai#
Để triển khai Hash Index trong thực tế, cần xử lý một số vấn đề sau:
Định dạng file: Thay vì dùng CSV, định dạng nhị phân sẽ hiệu quả hơn — lưu trữ độ dài dữ liệu kèm theo chuỗi byte được encode, giúp giảm overhead và tăng tốc độ xử lý.
Thao tác xóa: Để xóa một key, ta ghi một bản ghi đặc biệt (tombstone) vào log, đánh dấu key đó đã bị xóa.
Khôi phục sau sự cố: Khi DB khởi động lại, HashMap trong RAM bị mất. Để tránh quét lại toàn bộ log, có thể lưu snapshot của HashMap vào disk và khôi phục nhanh chóng từ đó.
Ghi bị gián đoạn: Sử dụng checksum để phát hiện và bỏ qua các bản ghi bị lỗi do crash giữa chừng.
Điều khiển đồng thời: Chỉ định một luồng duy nhất cho việc ghi, trong khi cho phép nhiều luồng đọc do tính bất biến của dữ liệu.
Tại sao lại là Append-Only?#
Việc ghi dữ liệu theo kiểu append-only nghe có vẻ lãng phí, nhưng thực tế lại mang lại nhiều lợi ích:
Hiệu suất ghi: Ghi tuần tự nhanh hơn và ít tốn I/O hơn ghi ngẫu nhiên, đặc biệt trên HDD. Tham khảo thêm bài viết ở đây: https://stackoverflow.com/a/61753068/4728650. Ngay cả với SSD, ghi tuần tự vẫn được ưu tiên do tối ưu cho garbage collection.
Đơn giản hóa đồng bộ và khôi phục: Tránh được tình trạng dữ liệu bị hỏng do ghi đè giữa chừng khi xảy ra sự cố.
Tránh phân mảnh: Dữ liệu luôn được ghi liên tục, giảm thiểu hiện tượng phân mảnh theo thời gian.
Compaction và Merge#
Nếu ta tính xa hơn, sẽ nhận ra rằng DB của mình chỉ toàn append vào file log mà không có xóa bớt đi, vậy cuối cùng rồi nó sẽ bị đầy dung lượng disk mất sao? Để giải quyết, khi file log đạt ngưỡng kích thước nhất định, ta chuyển sang ghi sang file mới. Một tiến trình nền gọi là compaction, sẽ được kích hoạt để xử lý các segment cũ: loại bỏ các bản ghi trùng lặp và chỉ giữ lại giá trị mới nhất.
Trong quá trình compaction, segment gốc không bị sửa đổi mà vẫn phục vụ truy vấn. Kết quả của quá trình compact sẽ được ghi ra 1 file mới (merged segment). Khi hoàn tất, DB chuyển hướng truy vấn sang file mới và lúc này ta có thể xóa các segment cũ đã được compact đi. Quá trình compact có thể xử lý cùng lúc 1 hoặc nhiều segment, như hình bên dưới:
Chú ý:
Mỗi segment có một HashMap riêng của nó. Khi truy vấn, DB kiểm tra lần lượt từ segment mới nhất đến cũ nhất: nếu Key không tồn tại trong HashMap, ta tiếp tục kiểm tra tới segment cũ hơn tiếp theo,… Nhờ compaction, số lượng segment được duy trì ở mức tối thiểu, giảm thiểu số lần tra cứu.
Nhược điểm của Hash Index#
Giới hạn bộ nhớ: HashMap phải nằm gọn trong RAM, không phù hợp với dataset cực lớn.
Không hỗ trợ truy vấn khoảng: Ví dụ bạn không thể scan những bản ghi có key trong đoạn
kitty00000-kitty99999, thay vào đó phải duyệt lần lượt từng key trong tất cả HashMap.
Để khắc phục những hạn chế này, chúng ta sẽ tìm hiểu các cấu trúc index tiên tiến hơn trong các phần tiếp theo.