Hash Indexes, SSTables, LSM-Trees & B-Trees — Cấu trúc dữ liệu đằng sau storage engine (DDIA) | Blog

Mở đầu

Ảnh: panumas nikhomkhai — Pexels

Khi bạn dùng database, bạn hiểu rõ chuyện gì đang xảy ra bên dưới cái query SELECT * FROM users WHERE id = 42 không? Nếu không có index, database phải quét toàn bộ bảng — O(n) — đọc từng row cho tới khi tìm ra row có id=42. Rất chậm khi dữ liệu lớn.

Chương 3 của Designing Data-Intensive Applications (DDIA) nói về storage engines — cơ chế lưu trữ và truy xuất dữ liệu dưới bề mặt của database. Trong phần này (Section 3.1), Martin Kleppmann phân tích 4 cấu trúc dữ liệu cốt lõi: Hash Indexes, SSTables, LSM-Trees, và B-Trees. Đây là nền tảng để hiểu cách database như PostgreSQL, MySQL, Cassandra, LevelDB, hay RocksDB làm việc.

Bài này mình sẽ tóm tắt những ý chính, kèm phân tích ưu nhược điểm của từng approach.

Hash Indexes — Index đơn giản nhất

Ảnh: Element5 Digital — Pexels

Hash index là cách đơn giản nhất để implement index: bạn lưu một hash map trong memory, map từ key → offset của record trong file. Khi cần tìm key nào, bạn tra hash map, nhảy tới offset đó, đọc record. O(1) — cực nhanh.

Cách này rất phù hợp với log-structured storage — kiểu ghi append-only. Dữ liệu mới được ghi vào cuối file, hash map cập nhật trỏ tới vị trí mới nhất. Bitcask — storage engine của Riak — dùng chính xác approach này.

Ưu điểm:

Write nhanh vì chỉ append vào cuối file (sequential write)
Read nhanh nếu key nằm trong memory (O(1))
Concurrency handling đơn giản — mỗi writer có segment riêng

Nhược điểm:

Tốn RAM — tất cả key phải nằm trong memory
Range query không hiệu quả — phải đọc toàn bộ file
Cần compaction (dọn dẹp các bản ghi cũ) định kỳ để tránh đầy disk

Hash index hoạt động tốt cho workload write-heavy, key-value lookup (như caching layer), nhưng không phù hợp khi cần scan range hay có nhiều key hơn RAM.

SSTables — Sorted String Tables

Nếu dữ liệu trong segment được sắp xếp theo key (sorted), ta có SSTable (Sorted String Table). SSTable là bước cải tiến so với hash index ở nhiều mặt:

Merge dễ hơn: Khi compaction (gộp nhiều segment), bạn chỉ cần mergesort giống merge trong merge sort — O(n) thay vì phải xử lý random access
Tốn ít RAM hơn: Bạn không cần lưu tất cả key trong memory. Chỉ cần lưu sparse index — vài key làm "marker" là đủ. Khi cần tìm key không có trong sparse index, bạn search giữa 2 marker gần nhất
Range query khả thi: Vì dữ liệu đã sorted, bạn chỉ cần scan tuần tự từ start key tới end key
Compression tốt hơn: Dữ liệu sorted nén hiệu quả hơn (vì các giá trị gần nhau thường giống nhau)

Nhưng SSTable chỉ là format lưu trữ. Câu hỏi lớn hơn là: làm sao để dữ liệu ghi vào (write) được sorted trên disk khi mà dữ liệu đến không theo thứ tự?

Đây là lúc LSM-Tree xuất hiện.

LSM-Trees — Log-Structured Merge-Trees

LSM-Tree là cấu trúc dữ liệu giải quyết bài toán "ghi dữ liệu vào sorted structure". Ý tưởng:

Khi ghi, dữ liệu được insert vào memtable (cây balanced trong memory như Red-Black Tree) — dữ liệu tự động sorted
Khi memtable đầy, flush xuống disk thành 1 SSTable segment
Background process (compaction) định kỳ merge các SSTable segments lại với nhau
Khi đọc, kiểm tra memtable trước, rồi tới các segment từ mới nhất tới cũ nhất

Cassandra, LevelDB, RocksDB đều dùng LSM-Tree variant. Đây cũng là storage engine mặc định của ScyllaDB.

Ưu điểm:

Write throughput rất cao — vì chỉ append + ghi sequential
Compression tốt nhờ sorted data
Bloom filter có thể tối ưu read: kiểm tra nhanh key có tồn tại trong segment không

Nhược điểm:

Read có latency cao hơn B-Tree ở worst case (phải check nhiều segment)
Compaction tốn CPU + I/O, ảnh hưởng tới foreground operations (write amplification)
Không mạnh về transactional workload (do phải check nhiều phiên bản của 1 key)

B-Trees — Cây balance cho disk

Ảnh: Rômulo Queiroz — Pexels

Ngược với LSM-Tree (ghi sequential rồi merge), B-Tree là cấu trúc in-place update — overwrite trực tiếp trang dữ liệu trên disk. Đây là storage engine của hầu hết relational database (PostgreSQL, MySQL InnoDB, Oracle, SQL Server).

B-Tree chia database thành các pages (thường 4KB hoặc 8KB). Mỗi page có thể chứa nhiều key-value pairs. Các page được tổ chức thành cây cân bằng:

Root page → internal pages (branch nodes) → leaf pages (chứa dữ liệu thật)
Mỗi page có pointer tới page con
Depth của cây thường rất nông — 3-4 levels cho hàng triệu records

Khi muốn tìm key, bạn đi từ root xuống leaf — chỉ cần 3-4 disk seeks. Ổn định, predictable.

Ưu điểm so với LSM:

Read latency thấp và ổn định — không có compaction ảnh hưởng
Mỗi key chỉ tồn tại ở 1 nơi (trong tree) — transactional semantics dễ implement
Range query cũng hiệu quả (vì leaf pages được linked list kết nối)

Nhược điểm:

Write amplification — mỗi lần ghi nhỏ cũng có thể ghi cả page (~8KB)
Write chậm hơn LSM vì random I/O (overwrite page thay vì append)
Cần WAL (Write-Ahead Log) để crash recovery — double write overhead
Fragmentation — page có thể không đầy, lãng phí space

So sánh tổng quan: LSM-Tree vs B-Tree

Tiêu chí	LSM-Tree	B-Tree
Write throughput	Cao (sequential)	Trung bình (random)
Read latency	Không ổn định (check nhiều segment)	Ổn định (cây balanced)
Range query	Tốt	Tốt
Memory usage	Bloom filter + cache	Page cache
Crash recovery	Phức tạp hơn	WAL + checkpoint
Write amplification	Cao (compaction)	Trung bình (page write)
Concurrency	Latches trên memtable	Latches trên pages

Không có cái nào "tốt hơn" tuyệt đối — tuỳ workload. Cassandra (LSM) ghi siêu nhanh nhưng read có thể chậm. PostgreSQL (B-Tree) đọc ổn định nhưng ghi kém hơn trong write-heavy scenario.

Key Takeaways

Hash Index — đơn giản, O(1) lookup, nhưng range query kém, tốn RAM (Bitcask)
SSTable — sorted segments giúp merge + compression hiệu quả, sparse index tiết kiệm RAM
LSM-Tree — memtable + SSTable compaction, write throughput cao nhất, phù hợp write-heavy (Cassandra, RocksDB, LevelDB)
B-Tree — in-place update, read latency ổn định, transactional semantics dễ implement (PostgreSQL, MySQL, SQLite)
Lựa chọn storage engine phụ thuộc vào workload — không có silver bullet

Glossary

Thuật ngữ	Ý nghĩa
Compaction	Quá trình gộp các segment cũ, loại bỏ bản ghi trùng/đã xoá
Memtable	Cấu trúc trong memory (thường là Red-Black Tree) chứa dữ liệu sắp xếp trước khi flush xuống disk
SSTable	Sorted String Table — file trên disk chứa key-value pairs đã sắp xếp
Bloom Filter	Cấu trúc xác suất kiểm tra nhanh key có tồn tại trong set không
Write Amplification	Lượng dữ liệu ghi vật lý nhiều hơn dữ liệu logic do cơ chế internal
WAL (Write-Ahead Log)	Log ghi trước khi ghi dữ liệu thật, dùng cho crash recovery
Page	Đơn vị lưu trữ nhỏ nhất trong B-Tree (thường 4KB-8KB)

Kết

Bốn cấu trúc dữ liệu này — Hash Index, SSTable, LSM-Tree, B-Tree — là nền tảng để hiểu cách database lưu trữ và truy xuất dữ liệu. Biết được ưu nhược của từng loại giúp bạn chọn đúng database cho đúng workload. PostgreSQL không phải lúc nào cũng là đáp án — nếu workload của bạn write-heavy, Cassandra hay RocksDB có thể là lựa chọn tốt hơn.

Bài tiếp theo trong series DDIA sẽ nói về Secondary Indexes, Column-Oriented Storage, và các kỹ thuật tối ưu cho analytical workloads. Hẹn gặp lại!