Chương 3 — Storage and Retrieval

🎯 Mục tiêu chương: Hiểu database lưu và tìm lại dữ liệu bên trong như thế nào, từ góc nhìn storage engine. Nắm hai trường phái storage engine cho OLTP (log-structured/LSM-tree và page-oriented/B-tree), sự khác biệt giữa OLTP và OLAP, và vì sao column-oriented storage thống trị data warehouse. Mục đích không phải để tự viết storage engine mà để chọn đúng engine và tune được nó cho workload của mình.

Data Structures That Power Your Database

Kleppmann mở đầu bằng "database đơn giản nhất thế giới": hai hàm Bash. db_set key value chỉ việc append một dòng key,value vào cuối file; db_get key dùng grep tìm mọi dòng có key đó rồi lấy dòng cuối cùng (tail -n 1) vì đó là giá trị mới nhất.

• Ghi rất nhanh: append vào cuối file là thao tác ghi đơn giản và rẻ nhất có thể. Rất nhiều database thật cũng dùng một log — chuỗi record chỉ append (append-only), không nhất thiết là text cho người đọc.
• Đọc rất chậm: mỗi lần db_get phải quét toàn bộ file → O(n). Gấp đôi dữ liệu thì gấp đôi thời gian lookup.

Giải pháp cho việc đọc là index: một cấu trúc phụ, được suy ra (derived) từ dữ liệu chính, giữ metadata làm "biển chỉ đường" để tìm nhanh. Thêm/xoá index không đổi nội dung database, chỉ đổi hiệu năng query.

Hash Indexes

Ý tưởng đơn giản nhất cho key-value data: dữ liệu vẫn là một log append-only trên disk, còn trong RAM giữ một hash map ánh xạ key → byte offset trong file. Ghi: append vào file rồi cập nhật offset trong hash map. Đọc: tra hash map lấy offset, seek tới đó, đọc value.

• Đây chính là cách Bitcask (storage engine mặc định của Riak) hoạt động. Read/write hiệu năng cao, với điều kiện toàn bộ key phải vừa RAM. Value có thể lớn hơn RAM vì chỉ cần một lần disk seek (thậm chí 0 nếu nằm trong filesystem cache).
• Phù hợp với workload nhiều lần ghi trên mỗi key nhưng số key không quá lớn — ví dụ trong sách: key là URL video mèo, value là số lượt xem, tăng mỗi lần có người bấm play.

Chống đầy disk — segment + compaction: chia log thành các segment có kích thước giới hạn; khi segment đủ lớn thì đóng lại và ghi sang file mới. Sau đó chạy compaction: bỏ các key trùng, chỉ giữ giá trị mới nhất. Có thể merge nhiều segment cùng lúc với compaction. Segment đã ghi thì không bao giờ sửa, nên kết quả merge ghi ra file mới; việc này chạy ở background thread, trong lúc đó vẫn phục vụ read/write bằng segment cũ, xong thì chuyển read sang segment mới và xoá segment cũ. Mỗi segment có hash map riêng; khi đọc thì tra từ segment mới nhất về cũ nhất.

Các chi tiết cần lo trong implementation thật:

• File format: dùng binary (length-prefix + raw bytes) thay vì CSV, khỏi phải escape.
• Deleting records: append một bản ghi xoá đặc biệt gọi là tombstone; khi merge, tombstone báo cho quá trình merge bỏ mọi giá trị cũ của key đó.
• Crash recovery: hash map trong RAM mất khi restart. Có thể rebuild bằng cách đọc lại toàn bộ segment (chậm), Bitcask thì lưu snapshot hash map của từng segment xuống disk để load nhanh.
• Partially written records: DB có thể crash giữa lúc đang append → Bitcask dùng checksum để phát hiện và bỏ qua phần hỏng.
• Concurrency control: thường chỉ có một writer thread; segment immutable nên nhiều thread đọc song song thoải mái.

Vì sao append-only chứ không update in-place?

• Append và merge là sequential write, nhanh hơn nhiều so với random write (đặc biệt trên HDD, và ở mức độ nào đó cả SSD).
• Concurrency và crash recovery đơn giản hơn nhiều: không bao giờ có chuyện file chứa nửa value cũ nửa value mới.
• Merge segment tránh fragmentation theo thời gian.

Giới hạn của hash index:

• Hash table phải vừa RAM. Hash map trên disk thì khó làm nhanh: nhiều random I/O, grow tốn kém, xử lý collision rắc rối.
• Range query kém: không thể quét hiệu quả mọi key từ kitty00000 đến kitty99999, phải tra từng key.

SSTables and LSM-Trees

Thay đổi nhỏ nhưng mạnh: yêu cầu các cặp key-value trong mỗi segment được sắp xếp theo key, và mỗi key chỉ xuất hiện một lần trong segment đã merge. Định dạng này gọi là Sorted String Table (SSTable). Ưu điểm so với log + hash index:

1. Merge đơn giản và hiệu quả kể cả khi file lớn hơn RAM — giống bước merge trong mergesort: đọc song song các file, mỗi lần chép key nhỏ nhất ra output. Nếu cùng key xuất hiện ở nhiều segment, giữ giá trị ở segment mới nhất (mỗi segment ứng với một khoảng thời gian ghi).
2. Không cần index toàn bộ key trong RAM: chỉ cần sparse index — ví dụ biết offset của handbag và handsome thì handiwork chắc chắn nằm giữa, nhảy tới handbag rồi scan. Khoảng một key cho mỗi vài KB là đủ vì scan vài KB rất nhanh.
3. Nén theo block: vì đọc range kiểu gì cũng scan nhiều record, có thể gom record thành block rồi compress; mỗi entry sparse index trỏ tới đầu một block. Tiết kiệm disk và giảm I/O bandwidth.

Constructing and maintaining SSTables

Write đến theo thứ tự bất kỳ, vậy làm sao sort? Giữ sorted structure trên disk thì được (B-tree) nhưng trong RAM thì dễ hơn nhiều, dùng cây cân bằng như red-black tree hay AVL tree. Quy trình:

• Write đến → chèn vào cây cân bằng in-memory, gọi là memtable.
• Memtable vượt ngưỡng (thường vài MB) → flush ra disk thành một SSTable mới (đã sorted sẵn nên ghi rất nhanh). Trong lúc flush, write mới đi vào memtable mới.
• Read: tra memtable → segment mới nhất trên disk → segment cũ hơn...
• Định kỳ chạy merge + compaction ở background.

Vấn đề duy nhất: crash thì mất các write còn trong memtable. Giải pháp: giữ thêm một log append-only trên disk (không cần sorted), mỗi write append vào đó ngay; chỉ dùng để khôi phục memtable sau crash, và bỏ đi khi memtable tương ứng đã flush thành SSTable.

Making an LSM-tree out of SSTables

• Thuật toán này là lõi của LevelDB và RocksDB (thư viện key-value embedded; LevelDB có thể thay Bitcask trong Riak). Cassandra và HBase dùng engine tương tự, lấy cảm hứng từ paper Google Bigtable — nơi sinh ra thuật ngữ SSTable và memtable.
• Tên gốc: Log-Structured Merge-Tree (LSM-Tree) của Patrick O'Neil và cộng sự, dựa trên log-structured filesystem. Engine dựa trên nguyên lý merge + compact các file sorted gọi chung là LSM storage engine.
• Lucene (nền của Elasticsearch, Solr) dùng cách tương tự cho term dictionary: key là từ (term), value là danh sách ID document chứa từ đó (postings list), lưu trong các file kiểu SSTable và merge ở background.

Performance optimizations

• Bloom filter: lookup một key không tồn tại rất tốn — phải kiểm tra memtable rồi từng segment về tận cái cũ nhất. Bloom filter là cấu trúc tiết kiệm bộ nhớ, xấp xỉ một tập hợp, trả lời chắc chắn "key này không có" → tiết kiệm nhiều disk read.
• Chiến lược compaction:
  • Size-tiered: SSTable mới, nhỏ được merge dần vào SSTable cũ, lớn hơn. HBase dùng.
  • Leveled: key range chia thành nhiều SSTable nhỏ, dữ liệu cũ dời sang các "level" riêng → compaction tăng dần (incremental) và tốn ít disk hơn. LevelDB (nên mới tên vậy), RocksDB dùng. Cassandra hỗ trợ cả hai.

Tóm lại LSM-tree: vẫn chạy tốt khi dataset lớn hơn RAM nhiều, range query hiệu quả (dữ liệu sorted), và write throughput rất cao nhờ ghi tuần tự.

B-Trees

B-tree ra đời năm 1970, chưa tới 10 năm sau đã được gọi là "ubiquitous", và đến nay vẫn là index chuẩn của gần như mọi relational database và nhiều non-relational database.

• Giống SSTable: giữ key sorted → lookup và range query hiệu quả. Khác hoàn toàn về triết lý thiết kế.
• LSM chia DB thành segment kích thước biến đổi (vài MB trở lên), ghi tuần tự. B-tree chia DB thành page/block kích thước cố định, truyền thống 4 KB, đọc/ghi từng page — khớp với phần cứng vì disk cũng chia block cố định.
• Mỗi page có địa chỉ, page này tham chiếu page khác như con trỏ nhưng trên disk → tạo thành cây. Tra cứu bắt đầu từ root page; mỗi page chứa các key làm ranh giới và reference tới child page phụ trách từng range. Ví dụ tìm key 251: đi theo reference giữa ranh giới 200 và 300, xuống page chia nhỏ tiếp 200–300, cho đến leaf page chứa value (inline hoặc reference tới nơi lưu value).
• Branching factor = số reference tới child trong một page; ví dụ hình là 6, thực tế thường vài trăm.
• Update: tìm leaf page, sửa value, ghi page đó lại (reference tới page vẫn hợp lệ). Insert: tìm page có range phù hợp; nếu hết chỗ thì split thành hai page nửa đầy và cập nhật parent. (Delete mà giữ cây cân bằng thì phức tạp hơn.)
• Cây luôn cân bằng: n key → độ sâu O(log n). Hầu hết DB vừa trong cây 3–4 tầng. Con số đáng nhớ: cây 4 tầng, page 4 KB, branching factor 500 chứa được tới 256 TB.

Making B-trees reliable

• Thao tác ghi cơ bản của B-tree là ghi đè page tại chỗ (location không đổi) — ngược hẳn LSM chỉ append. Trên HDD là di chuyển đầu đọc + chờ đĩa quay; trên SSD còn phức tạp hơn vì phải erase/rewrite block lớn.
• Một số thao tác phải ghi nhiều page (split: ghi 2 page con + ghi đè parent). Crash giữa chừng → index hỏng, ví dụ orphan page không có parent.
• Giải pháp: write-ahead log (WAL / redo log) — file append-only, mọi thay đổi B-tree phải ghi vào đây trước khi áp dụng vào page. Sau crash dùng WAL khôi phục cây về trạng thái nhất quán.
• Concurrency: nhiều thread truy cập cây cần latch (lock nhẹ) để không thấy cây ở trạng thái dở dang. LSM đơn giản hơn vì merge ở background rồi swap segment một cách atomic.

B-tree optimizations

• Copy-on-write thay cho ghi đè + WAL (ví dụ LMDB): page sửa được ghi ra chỗ mới, tạo version mới của các parent trỏ tới nó — cũng hữu ích cho snapshot isolation (Chương 7).
• Viết tắt key trong page nội bộ (chỉ cần đủ làm ranh giới) → nhiều key/page hơn → branching factor cao hơn, ít tầng hơn (biến thể thường gọi là B+ tree).
• Cố gắng xếp leaf page tuần tự trên disk để range scan khỏi seek nhiều — nhưng khó giữ khi cây lớn dần. LSM làm việc này dễ hơn vì rewrite cả segment lớn khi merge.
• Thêm sibling pointer giữa các leaf để scan theo thứ tự mà không phải quay lên parent.
• Biến thể như fractal tree mượn ý tưởng log-structured để giảm disk seek.

Comparing B-Trees and LSM-Trees

Quy tắc ngón tay cái: LSM-tree thường nhanh hơn cho write, B-tree thường nhanh hơn cho read (LSM phải kiểm tra nhiều cấu trúc/SSTable ở các giai đoạn compaction khác nhau). Nhưng benchmark thường không kết luận được và rất nhạy với workload — phải test với workload của chính mình.

Advantages of LSM-trees

• Write amplification: một lần ghi vào DB dẫn tới nhiều lần ghi xuống disk trong suốt vòng đời dữ liệu. B-tree ghi mỗi dữ liệu ít nhất 2 lần (WAL + page), ghi nguyên page dù chỉ đổi vài byte, có engine còn ghi page 2 lần để tránh page dở dang khi mất điện. LSM cũng rewrite nhiều lần do compaction, nhưng thường vẫn write amplification thấp hơn (tuỳ cấu hình). Đặc biệt quan trọng với SSD vì block chỉ ghi đè được số lần giới hạn.
• Với ứng dụng write-heavy, bottleneck là tốc độ ghi disk → write amplification là chi phí trực tiếp. LSM chịu được write throughput cao hơn nhờ ghi tuần tự các SSTable gọn thay vì ghi đè nhiều page rải rác.
• Nén tốt hơn, file nhỏ hơn: B-tree để lại chỗ trống do fragmentation (khi split page). LSM không page-oriented và định kỳ rewrite nên overhead lưu trữ thấp, nhất là với leveled compaction.
• Nhiều SSD firmware đã tự dùng thuật toán log-structured bên trong nên chênh lệch pattern ghi bớt quan trọng, nhưng write amplification thấp và ít fragmentation vẫn có lợi về I/O bandwidth.

Downsides of LSM-trees

• Compaction ảnh hưởng read/write đang chạy: disk tài nguyên có hạn, request có thể phải chờ compaction. Throughput và latency trung bình ít bị ảnh hưởng, nhưng tail latency (percentile cao) có thể rất cao — B-tree dễ đoán hơn.
• Ở write throughput cao, bandwidth ghi phải chia giữa write ban đầu (log + flush memtable) và compaction; DB càng lớn càng cần nhiều bandwidth cho compaction.
• Nếu compaction không theo kịp tốc độ ghi: số segment chưa merge tăng dần tới khi hết disk, read cũng chậm đi vì phải check nhiều file. Engine SSTable thường không tự throttle write → phải monitor chủ động.
• B-tree: mỗi key nằm đúng một chỗ trong index, còn LSM có thể có nhiều bản sao ở nhiều segment. Điều này giúp B-tree hợp với transactional semantics mạnh: lock theo range key có thể gắn thẳng vào cây.

Other Indexing Structures

Đến giờ mới bàn primary key index. Rất phổ biến là secondary index (CREATE INDEX), cực quan trọng cho join — ví dụ index trên cột user_id. Khác biệt: key không unique. Giải quyết bằng cách value là danh sách row ID (như postings list) hoặc gắn thêm row ID vào key cho unique. Cả B-tree lẫn LSM đều dùng làm secondary index được.

Storing values within the index

• Value trong index có thể là chính row, hoặc reference tới row nằm ở heap file (lưu không theo thứ tự). Heap file phổ biến vì nhiều secondary index cùng trỏ vào một chỗ, không nhân bản dữ liệu.
• Update không đổi key: ghi đè tại chỗ trong heap nếu value mới không lớn hơn. Nếu lớn hơn phải dời chỗ → hoặc cập nhật mọi index, hoặc để lại forwarding pointer.
• Clustered index: lưu row ngay trong index để bỏ bước nhảy sang heap. Ví dụ MySQL InnoDB: primary key luôn là clustered index, secondary index trỏ tới primary key (không trỏ heap). SQL Server: chọn được một clustered index mỗi bảng.
• Covering index / index with included columns: trung gian — lưu một số cột trong index, để một số query được trả lời chỉ bằng index ("index covers the query").
• Trade-off: clustered/covering nhanh read nhưng tốn storage, tăng overhead write, và DB phải nỗ lực thêm để giữ transactional guarantee khi dữ liệu bị nhân bản.

Multi-column indexes

• Concatenated index: ghép nhiều field thành một key theo thứ tự định nghĩa, như danh bạ giấy theo (lastname, firstname). Tìm theo lastname hoặc lastname+firstname được, nhưng vô dụng nếu chỉ tìm theo firstname.
• Multi-dimensional index — quan trọng cho geospatial: tìm nhà hàng trong khung bản đồ cần range trên cả latitude và longitude cùng lúc. B-tree/LSM thường chỉ lọc được một chiều.
  • Cách 1: biến vị trí 2D thành một số bằng space-filling curve rồi dùng B-tree thường.
  • Cách 2 (phổ biến hơn): index chuyên dụng như R-tree; PostGIS cài R-tree bằng GiST của PostgreSQL.
  • Không chỉ cho địa lý: index 3 chiều (red, green, blue) cho tìm sản phẩm theo màu; index 2 chiều (date, temperature) để tìm các quan sát năm 2013 có nhiệt độ 25–30 ℃. HyperDex dùng kỹ thuật này.

Full-text search and fuzzy indexes

• Index thường chỉ query giá trị chính xác hoặc range. Fuzzy query (tìm key gần giống, sai chính tả) cần kỹ thuật khác: synonym, bỏ biến thể ngữ pháp, tìm từ đứng gần nhau...
• Lucene tìm được từ trong một edit distance nhất định (edit distance 1 = thêm/xoá/thay một chữ). In-memory index của Lucene là một finite state automaton trên ký tự của key (giống trie), có thể biến thành Levenshtein automaton để tìm hiệu quả theo edit distance. (So sánh: LevelDB dùng sparse index một số key.)

Keeping everything in memory

• Mọi cấu trúc trên là để đối phó với sự "khó chịu" của disk. Ta chịu disk vì durable và rẻ hơn/GB. RAM rẻ dần và nhiều dataset không lớn → in-memory database.
• Memcached: chỉ để cache, mất dữ liệu khi restart cũng chấp nhận được. In-memory DB muốn durability thì dùng: RAM có pin, ghi log thay đổi xuống disk, snapshot định kỳ, hoặc replicate sang máy khác. Disk lúc này chỉ là append-only log cho durability; read hoàn toàn từ RAM.
• Ví dụ: VoltDB, MemSQL, Oracle TimesTen (relational in-memory); RAMCloud (key-value, log-structured cả trong RAM lẫn disk); Redis, Couchbase (durability yếu, ghi disk bất đồng bộ).
• Điểm phản trực giác: in-memory DB nhanh không phải vì khỏi đọc disk — disk-based engine có đủ RAM thì OS page cache cũng giữ block trong RAM rồi. Chúng nhanh vì tránh được overhead encode cấu trúc in-memory sang dạng ghi được xuống disk.
• Còn cho phép data model khó làm với disk index: Redis cung cấp priority queue, set... với implementation đơn giản.
• Anti-caching: đẩy dữ liệu ít dùng (LRU) ra disk khi thiếu RAM, load lại khi cần — giống virtual memory/swap nhưng ở mức từng record nên hiệu quả hơn; vẫn cần index vừa RAM. Tương lai: non-volatile memory (NVM) có thể thay đổi thiết kế storage engine.

Transaction Processing or Analytics?

"Transaction" ban đầu là giao dịch thương mại, sau thành nhóm read/write tạo một đơn vị logic — không nhất thiết có ACID. Transaction processing chỉ nghĩa là client đọc/ghi với latency thấp, trái với batch processing chạy định kỳ.

• OLTP (online transaction processing): ứng dụng tương tác, tra ít record theo key qua index, insert/update theo input người dùng.
• OLAP (online analytic processing): query quét số lượng record khổng lồ, chỉ đọc vài cột, tính aggregate (count, sum, avg). Ví dụ: tổng doanh thu mỗi cửa hàng trong tháng 1? Khuyến mãi vừa rồi bán thêm được bao nhiêu chuối? Thương hiệu đồ ăn trẻ em nào hay được mua cùng tã hiệu X? Phục vụ business intelligence.

Ban đầu cùng một DB phục vụ cả hai (SQL linh hoạt cho cả hai). Từ cuối 1980s–đầu 1990s, các công ty tách analytics sang DB riêng: data warehouse.

Data Warehousing

• Doanh nghiệp có hàng chục hệ OLTP (website, POS, kho, định tuyến xe, nhà cung cấp, nhân sự...), mỗi hệ do một team vận hành độc lập. DBA bảo vệ OLTP kỹ, không muốn analyst chạy query ad hoc nặng làm ảnh hưởng transaction.
• Data warehouse: DB riêng, read-only copy của dữ liệu từ mọi hệ OLTP. Quy trình ETL (Extract–Transform–Load): trích xuất (dump định kỳ hoặc stream update liên tục), biến đổi sang schema thân thiện cho phân tích, làm sạch, rồi load vào warehouse.
• Công ty nhỏ hầu như không có warehouse vì ít hệ OLTP và dữ liệu nhỏ (SQL thường hoặc spreadsheet là đủ).
• Lợi thế lớn: warehouse được tối ưu cho access pattern analytics — các index ở nửa đầu chương tốt cho OLTP nhưng kém cho analytic query.

The divergence between OLTP databases and data warehouses

• Data model warehouse thường là relational vì SQL hợp với analytics; có nhiều công cụ GUI sinh SQL, hỗ trợ drill-down, slicing and dicing.
• Bề ngoài đều là SQL nhưng bên trong rất khác. Microsoft SQL Server, SAP HANA hỗ trợ cả hai trong một sản phẩm, nhưng thực chất ngày càng là hai engine riêng chung giao diện SQL.
• Vendor thương mại: Teradata, Vertica, SAP HANA, ParAccel (Amazon Redshift là bản hosted của ParAccel). Open source SQL-on-Hadoop: Apache Hive, Spark SQL, Cloudera Impala, Facebook Presto, Apache Tajo, Apache Drill — nhiều cái dựa trên ý tưởng Google Dremel.

Stars and Snowflakes: Schemas for Analytics

• Analytics ít đa dạng về data model; phổ biến nhất là star schema (còn gọi dimensional modeling).
• Trung tâm là fact table (ví dụ fact_sales của chuỗi siêu thị): mỗi row là một sự kiện (một lần khách mua một sản phẩm; với web analytics là một page view/click). Lưu sự kiện riêng lẻ để phân tích linh hoạt → fact table cực lớn: Apple, Walmart, eBay có hàng chục PB lịch sử giao dịch, phần lớn là fact table.
• Cột của fact table: thuộc tính (giá bán, giá nhập → tính margin) và foreign key tới dimension table. Dimension trả lời who, what, where, when, how, why của sự kiện. Ví dụ dim_product có SKU, mô tả, brand, category, hàm lượng chất béo, kích thước gói...
• Ngay cả ngày giờ cũng là dimension table (dim_date) để encode thêm thông tin như ngày lễ.
• Tên "star": fact table ở giữa, dimension table xung quanh như tia sao.
• Snowflake schema: dimension chia tiếp thành sub-dimension (ví dụ bảng brand, category riêng; dim_product tham chiếu bằng foreign key). Chuẩn hoá (normalized) hơn, nhưng star thường được ưa hơn vì analyst dùng dễ hơn.
• Bảng rất rộng: fact table thường hơn 100 cột, có khi vài trăm; dimension cũng rộng (ví dụ dim_store có dịch vụ, có bakery không, diện tích, ngày khai trương, khoảng cách tới đường cao tốc...).

Column-Oriented Storage

Fact table có hàng nghìn tỷ row và PB dữ liệu; dimension table nhỏ hơn nhiều (hàng triệu row) nên tập trung vào fact. Quan sát then chốt: dù fact table rộng hơn 100 cột, một query điển hình chỉ đụng 4–5 cột (SELECT * hiếm khi cần). Ví dụ query trong sách (người ta mua trái cây tươi hay kẹo nhiều hơn theo thứ trong tuần, năm 2013) chỉ cần date_key, product_sk, quantity của fact_sales.

• Row-oriented (hầu hết OLTP, document DB cũng vậy): mọi giá trị của một row nằm cạnh nhau. Dù có index trên date_key/product_sk, vẫn phải load cả row hơn 100 cột từ disk, parse, rồi lọc → chậm.
• Column-oriented: lưu tất cả giá trị của mỗi cột cùng nhau (thường mỗi cột một file). Query chỉ đọc và parse những cột cần.
• Không chỉ cho relational: Parquet là columnar format hỗ trợ document model, dựa trên Google Dremel.
• Điều kiện: mọi file cột lưu row theo cùng thứ tự — row thứ 23 = phần tử thứ 23 của mỗi file cột.

Column Compression

• Giá trị trong một cột thường lặp nhiều → nén tốt. Kỹ thuật đặc biệt hiệu quả: bitmap encoding.
• Số giá trị distinct thường nhỏ so với số row (tỷ giao dịch nhưng chỉ ~100,000 sản phẩm). Cột có n giá trị distinct → n bitmap, mỗi bitmap một bit/row (1 nếu row có giá trị đó).
• n nhỏ (cột country ~200 giá trị) → lưu một bit/row. n lớn → bitmap thưa (sparse), nhiều số 0 → thêm run-length encoding → cực gọn.
• Bitmap rất hợp với query warehouse:
  • WHERE product_sk IN (30, 68, 69) → load 3 bitmap, bitwise OR.
  • WHERE product_sk = 31 AND store_sk = 3 → bitwise AND hai bitmap (được vì bit thứ k ở mọi cột ứng với cùng row).

Lưu ý: column family ≠ column-oriented. Cassandra và HBase có column families (thừa hưởng từ Bigtable), nhưng trong mỗi column family vẫn lưu mọi cột của một row cùng nhau kèm row key, và không dùng column compression → Bigtable model về cơ bản vẫn row-oriented.

Memory bandwidth and vectorized processing

• Ngoài bandwidth disk → RAM, còn phải lo bandwidth RAM → CPU cache, tránh branch misprediction và bubble trong pipeline CPU, tận dụng SIMD.
• Column layout giúp dùng CPU hiệu quả: lấy một chunk dữ liệu cột đã nén vừa L1 cache, lặp trong tight loop (không gọi hàm) — nhanh hơn nhiều so với code có nhiều function call/điều kiện cho mỗi record. Nén giúp nhiều row hơn vừa L1. Toán tử như AND/OR bitmap chạy thẳng trên chunk nén. Kỹ thuật này gọi là vectorized processing.

Sort Order in Column Storage

• Mặc định lưu theo thứ tự insert (chỉ việc append mỗi file cột). Nhưng có thể áp một thứ tự sort (như SSTable) làm cơ chế index.
• Không sort từng cột độc lập (mất liên kết row). Phải sort cả row, dù lưu theo cột.
• Admin chọn sort key theo query phổ biến: query hay lọc theo khoảng ngày → date_key là sort key đầu tiên, optimizer chỉ quét tháng gần nhất. Sort key thứ hai (ví dụ product_sk) gom các sale cùng sản phẩm cùng ngày.
• Lợi ích phụ: nén tốt hơn. Cột sort đầu tiên ít giá trị distinct → chuỗi lặp dài → run-length encoding nén xuống vài KB dù bảng có hàng tỷ row. Hiệu ứng mạnh nhất ở sort key đầu, giảm dần ở key thứ 2, 3; các cột sau gần như ngẫu nhiên.

Several different sort orders

• Ý tưởng từ C-Store, được Vertica thương mại hoá: dữ liệu vốn phải replicate sang nhiều máy để chống mất → lưu mỗi bản replica sorted theo cách khác nhau, query dùng bản phù hợp nhất.
• Giống có nhiều secondary index ở row store, nhưng khác: row store giữ row ở một chỗ (heap/clustered index), secondary index chỉ chứa pointer; column store thường không có pointer, chỉ có các cột chứa value.

Writing to Column-Oriented Storage

• Column storage + nén + sort làm read nhanh nhưng write khó: update in-place kiểu B-tree không làm được với cột đã nén; chèn một row vào giữa bảng sorted gần như phải viết lại mọi file cột (row được xác định bằng vị trí, phải cập nhật mọi cột nhất quán).
• Giải pháp: LSM-tree. Write vào in-memory store (sorted, row hay column đều được), đủ nhiều thì merge với file cột trên disk và ghi file mới hàng loạt. Vertica làm đúng như vậy.
• Query phải kết hợp dữ liệu cột trên disk + write gần đây trong RAM; optimizer che giấu điều này, analyst thấy insert/update/delete phản ánh ngay.

Aggregation: Data Cubes and Materialized Views

• Không phải warehouse nào cũng là column store, nhưng columnar nhanh hơn đáng kể cho ad hoc query nên phổ biến nhanh.
• Materialized aggregates: nhiều query dùng cùng COUNT/SUM/AVG/MIN/MAX → cache lại.
• Materialized view: bản copy thật của kết quả query, ghi xuống disk; khác virtual view chỉ là shortcut, SQL engine expand thành query gốc khi đọc. Dữ liệu gốc đổi thì materialized view phải cập nhật (vì là bản denormalized) → write đắt hơn → ít dùng ở OLTP, hợp lý hơn ở warehouse nặng read.
• Data cube / OLAP cube: lưới aggregate nhóm theo các dimension. Ví dụ 2 chiều date × product, mỗi ô là SUM(net_price); cộng dọc/ngang được tổng theo product hoặc theo date. Thực tế nhiều chiều hơn (hình star schema có 5: date, product, store, promotion, customer) → hypercube.
• Ưu: một số query cực nhanh vì đã tính trước (tổng sale mỗi store hôm qua). Nhược: kém linh hoạt — không trả lời được "tỷ lệ doanh số từ món giá trên $100" vì price không phải dimension. Nên warehouse giữ raw data càng nhiều càng tốt, cube chỉ là tăng tốc cho một số query.

Summary

• Storage engine chia 2 nhóm lớn: tối ưu OLTP (user-facing, nhiều request, mỗi request ít record theo key, bottleneck là disk seek) và tối ưu analytics (ít query nhưng mỗi query quét hàng triệu record, bottleneck là disk bandwidth → column-oriented storage).
• Phía OLTP có hai trường phái:
  • Log-structured: chỉ append và xoá file cũ, không sửa file đã ghi — Bitcask, SSTables, LSM-trees, LevelDB, Cassandra, HBase, Lucene. Ý tưởng chính: biến random write thành sequential write → write throughput cao.
  • Update-in-place: coi disk là tập page cố định có thể ghi đè — B-tree, dùng trong mọi RDBMS lớn và nhiều NoSQL.
• Với analytics, index kém quan trọng; điều quan trọng là encode dữ liệu cực gọn để giảm lượng đọc từ disk.

⚠️ Hiểu lầm & cạm bẫy thường gặp

• "Thêm index là luôn tốt" — sai. Mỗi index làm chậm write và tốn storage; chỉ index theo query pattern thật.
• "LSM luôn nhanh hơn B-tree cho write, B-tree luôn nhanh hơn cho read" — chỉ là rule of thumb; benchmark phụ thuộc workload, phải đo với workload của mình.
• "In-memory DB nhanh vì không đọc disk" — sai. OS page cache cũng giữ dữ liệu nóng trong RAM; lợi thế thật là bỏ được overhead encode cấu trúc dữ liệu cho disk.
• "Cassandra/HBase là column-oriented database" — gây hiểu lầm. Column family vẫn lưu theo row, không nén cột; khác hẳn column store như Vertica, Parquet, Redshift.
• Quên monitor compaction ở LSM: compaction không theo kịp → segment tích tụ, hết disk, read chậm dần; engine thường không tự throttle write.
• Bỏ qua tail latency: trung bình của LSM trông ổn nhưng p99 có thể tăng vọt khi compaction chạy.
• Concatenated index (a, b) không giúp query chỉ lọc theo b — thứ tự cột trong index quan trọng (leftmost prefix).
• Delete trong log-structured không xoá ngay — chỉ ghi tombstone; dữ liệu còn chiếm disk tới khi compaction.
• Chạy analytic query nặng trên OLTP DB production — có thể làm chậm transaction của khách hàng; đó là lý do có data warehouse/read replica.
• Nghĩ clustered/covering index "miễn phí" — chúng nhân bản dữ liệu, tăng chi phí write và độ phức tạp giữ nhất quán.
• Data cube thay được raw data — không; cube chỉ trả lời query trên các dimension đã chọn.

💼 Áp dụng thực tế & phỏng vấn

• Chọn storage engine theo workload: write-heavy (logging, metrics, IoT, event tracking, feed) → nghĩ tới LSM (Cassandra, RocksDB, HBase, ScyllaDB). Read-heavy, transaction mạnh, range lock → B-tree (PostgreSQL, MySQL InnoDB).
• Trong phỏng vấn system design, khi chọn DB hãy nói được vì sao: "Cassandra dùng LSM nên ghi tuần tự, throughput ghi cao, hợp cho timeline/message; đổi lại read có thể phải check nhiều SSTable, dùng Bloom filter giảm chi phí."
• Tách OLTP và OLAP: kiến trúc chuẩn là OLTP DB → CDC/ETL (Kafka, Debezium, Airflow) → warehouse (Snowflake, BigQuery, Redshift, ClickHouse) hoặc data lake (Parquet trên S3). Nêu được star schema với fact/dimension là điểm cộng.
• Thiết kế index trong SQL: thứ tự cột trong composite index, covering index để tránh lookup về bảng, InnoDB secondary index trỏ về primary key (nên primary key ngắn là tốt).
• Geospatial (Uber, Yelp, "tìm tài xế gần nhất"): nhắc tới R-tree (PostGIS), geohash/space-filling curve (quadtree, S2) trên B-tree thường.
• Search/autocomplete: Elasticsearch/Lucene = inverted index (term → postings list) lưu kiểu SSTable, hỗ trợ fuzzy query theo edit distance.
• Cache/counter: Redis cho counter, leaderboard (sorted set), rate limiter — nhưng nhớ durability yếu (ghi disk async).
• Các con số nên nhớ: page B-tree ~4 KB; branching factor vài trăm; 4 tầng × 500 nhánh ≈ 256 TB; memtable vài MB; fact table >100 cột, query chỉ đọc 4–5 cột.
• Tuning thực tế: chọn compaction strategy (size-tiered cho write-heavy, leveled cho read-heavy/tiết kiệm disk trong Cassandra), cấu hình Bloom filter false-positive rate, theo dõi pending compactions.

❓ Câu hỏi ôn tập