Case Study: MySQL InnoDB B+tree index + Redis dict incremental rehash

TL;DR: MySQL InnoDB chọn B+tree vì sống trên disk và cần range query — leaf chain cho phép range scan tuần tự O(k), fanout 1000 giảm height xuống 3–4 cho 100 triệu row. Redis chọn hash table vì sống trong RAM và chỉ cần point query O(1) — nhưng phải giải quyết bài toán resize không blocking trên single-threaded event loop bằng incremental rehash: duy trì 2 hash table đồng thời, mỗi command migrate thêm vài bucket thay vì block 100–500ms để migrate 1 triệu entry cùng lúc. Cùng bài toán "tìm key nhanh", constraints khác nhau → cấu trúc tối ưu hoàn toàn khác nhau.

Module 3 đã đi qua hash table (bài 01 và 03), self-balancing tree (bài 06), và B+tree (bài 07). Tất cả đều giải cùng một vấn đề cốt lõi: tìm key trong tập dữ liệu lớn nhanh nhất có thể.

Vậy tại sao MySQL InnoDB — database được deploy nhiều nhất thế giới — lại chọn B+tree cho persistent index, trong khi Redis — in-memory key-value store phổ biến nhất thế giới — lại chọn hash table với incremental rehash? Cả hai đều cần tìm key nhanh. Cả hai đều phục vụ hàng triệu request mỗi ngày.

Câu trả lời không nằm ở thuật toán tốt hơn hay tệ hơn — mà ở workload khác nhau: MySQL sống trên disk và cần range query; Redis sống hoàn toàn trong RAM và chỉ cần point query. Workload khác → cấu trúc tối ưu khác.

Bài này dive vào hai system thật: MySQL InnoDB B+tree clustered index và Redis dict 2-table incremental rehash. Đọc source thật, hiểu vì sao mỗi quyết định đúng cho context của nó.

1. Tech profile A — MySQL InnoDB

Project: MySQL InnoDB (storage engine mặc định từ MySQL 5.5+) Version: MySQL 8.0 (current LTS) Source: https://github.com/mysql/mysql-server/tree/8.0/storage/innobase/btr/ License: GPL v2

InnoDB là storage engine mặc định của MySQL từ version 5.5. Trước đó là MyISAM — không có transaction, không có row-level lock, index chỉ là pointer đến heap. InnoDB thay thế MyISAM với ACID transaction, row-level locking, và clustered index — thiết kế quan trọng nhất mà bài này sẽ phân tích.

2. InnoDB B+tree clustered index — không phải pointer thông thường

Bài 07 đã giải thích B+tree: internal node chứa key để route, leaf node chứa data. Nhưng InnoDB làm một điều khác biệt căn bản so với hầu hết implementation khác: clustered index.

2.1 Clustered vs non-clustered

Clustered index (InnoDB primary key index): leaf node chứa toàn bộ row data — không phải pointer đến row, mà là row thật sự. Query theo primary key chỉ cần walk down tree một lần, lấy luôn data tại leaf.

Secondary index (InnoDB non-primary index): leaf node chứa primary key value — không phải row data, không phải physical pointer. Query theo secondary index cần hai bước: (1) walk xuống secondary B+tree để tìm primary key value, (2) walk lại primary B+tree để lấy row. Đây là double lookup.

InnoDB Clustered Index (PRIMARY KEY):

                     [20 | 50 | 80]          -- internal node
                    /    |    |    \
          [10|15|18] [25|30|45] [55|60|75] [85|90|95]  -- leaf node
          [row data] [row data] [row data]  [row data]  -- full row ở đây!

InnoDB Secondary Index (INDEX trên cột email):

                   [[email protected] | [email protected]]      -- internal node
                  /          |          \
        [a@...|b@...]   [c@...|m@...]   [n@...|z@...]  -- leaf node
        [pk=5 | pk=12]  [pk=3 | pk=22]  [pk=8 | pk=30] -- chỉ chứa primary key

Secondary index lookup:
  Bước 1: duyệt secondary tree -> tìm pk=12
  Bước 2: duyệt primary tree   -> fetch full row tại pk=12

Hệ quả quan trọng: thứ tự primary key chiến lược. Nếu primary key tăng đơn điệu (AUTO_INCREMENT integer), insert luôn vào cuối leaf node cuối cùng — minimal page split. Nếu primary key random (UUID v4), mỗi insert rơi vào vị trí ngẫu nhiên trong tree — page split xảy ra khắp nơi, fragmentation tích lũy.

2.2 Fanout và height

InnoDB page size mặc định là 16KB. Với integer primary key (8 byte) và page overhead, một internal node chứa được khoảng 1000 key. Fanout 1000 → height 3–4 cho 100 triệu row:

Fanout = 1000 (xấp xỉ cho int PK, page 16KB)

Height 1: 1.000 record (root là leaf)
Height 2: 1.000 × 1.000 = 1.000.000 record
Height 3: 1.000 × 1.000 × 1.000 = 1.000.000.000 (1 tỷ) record
Height 4: 1.000^4 = 1 nghìn tỷ record

Cho 100 triệu row:
  log_1000(100.000.000) = log(10^8) / log(10^3) = 8/3 ≈ 2,67
  => Height 3 đủ. Cộng 1 cho root = tổng height 3.
  => 3 disk seek để fetch bất kỳ row nào qua primary key.

Ba disk seek trên SSD (mỗi seek khoảng 0,1ms) = 0,3ms. Buffer pool cache internal nodes thường xuyên truy cập — trên thực tế thường chỉ 1–2 seeks sau khi warm cache.

graph TD
    ROOT["Internal node tầng 1<br/>[20 | 50 | 80]"]
    I1["Internal node tầng 2<br/>[10|15|18]"]
    I2["Internal node tầng 2<br/>[25|30|45]"]
    I3["Internal node tầng 2<br/>[55|60|75]"]
    L1["Leaf — row data<br/>pk=10..18"]
    L2["Leaf — row data<br/>pk=25..45"]
    L3["Leaf — row data<br/>pk=55..75"]
    ROOT --> I1
    ROOT --> I2
    ROOT --> I3
    I1 --> L1
    I2 --> L2
    I3 --> L3
    L1 -- "next →" --> L2
    L2 -- "next →" --> L3

3. InnoDB page structure — B+tree trên disk

InnoDB không đọc/ghi từng byte — đơn vị làm việc là page 16KB. Mỗi page là một node trong B+tree.

InnoDB Page (16KB):
+------------------+
|  Page Header     |  38 byte: page number, level, prev/next sibling pointer
|  (infimum rec)   |  pseudo-record: lower bound sentinel
|  (supremum rec)  |  pseudo-record: upper bound sentinel
+------------------+
|                  |
|   User Records   |  actual key-value pair, sắp xếp tăng dần
|                  |
+------------------+
|   Free Space     |  tăng từ dưới lên
+------------------+
|  Page Directory  |  sparse index: pointer đến mỗi 4-8 record
|  (slot array)    |  để binary search trong page
+------------------+
|  File Trailer    |  checksum để phát hiện corruption
+------------------+

Page directory là sparse index trong page: thay vì duyệt tuyến tính 500 record trong page, InnoDB dùng page directory để binary search xuống còn 4–8 record rồi scan linear. Tổng: binary search qua pages (disk IO) + binary search trong page (RAM).

Buffer pool cache pages trong RAM. Production setting: innodb_buffer_pool_size = 70% RAM. Database server 64GB RAM → 45GB buffer pool → hàng triệu pages được cache, giảm disk IO xuống gần 0 cho working set.

Đoạn pseudocode sau mô phỏng logic trong btr/btr0sea.cc — InnoDB adaptive hash search:

-- InnoDB adaptive hash search (đơn giản hóa từ btr0sea.cc)
-- Tính số field cần thiết cho hash search dựa trên thông tin hash hiện tại.
btr_search_get_n_fields(n_fields, n_bytes):
    return n_fields + (if n_bytes > 0 then 1 else 0)

4. Production gotcha MySQL

4.1 Composite index — thứ tự column quan trọng

INDEX(a, b) là B+tree được sort theo (a, b). Query WHERE a = 1 AND b = 2 dùng được index. Query WHERE b = 2 không dùng được — không có prefix a, không thể dùng leftmost prefix của index.

-- Bảng: orders(id, customer_id, status, created_at)
-- Index: INDEX idx_cust_status (customer_id, status)

-- Dùng được index (cả hai column, leftmost prefix)
SELECT * FROM orders WHERE customer_id = 42 AND status = 'pending';

-- Dùng được index (chỉ leftmost prefix)
SELECT * FROM orders WHERE customer_id = 42;

-- KHÔNG dùng được index (bỏ qua leftmost column)
SELECT * FROM orders WHERE status = 'pending';

Rule: đặt column selectivity cao (nhiều giá trị distinct) làm leftmost prefix để index pruning hiệu quả nhất.

4.2 Low cardinality column — index vô dụng

INDEX(gender) với 3 giá trị distinct (M, F, X) trên bảng 10 triệu row: mỗi bucket index sẽ trỏ đến khoảng 3 triệu row. MySQL query optimizer thấy rằng scan full table còn rẻ hơn dùng index vì locality của heap traversal tốt hơn random B+tree lookup khi fetch nhiều row.

4.3 InnoDB Adaptive Hash Index

InnoDB tự động xây dựng hash index trên các page được truy cập thường xuyên. Khi pattern truy cập đủ đều (cùng key liên tục), InnoDB cache result của B+tree traversal vào hash table — biến point query O(log n) thành O(1).

Boost điển hình: 10–30% cho workload point query nặng. Disable bằng innodb_adaptive_hash_index = OFF nếu workload đa dạng (adaptive hash index overhead là negative khi pattern không đủ uniform).

4.4 UUID v4 PK và page split storm

UUID v4 là random 128-bit. Insert UUID v4 làm primary key → mỗi insert rơi vào vị trí ngẫu nhiên trong B+tree → page split ở khắp nơi.

AUTO_INCREMENT insert (tuần tự):
  [1][2][3][4][5]...[N] -> luôn append vào leaf cuối -> split tối thiểu

UUID v4 insert (ngẫu nhiên):
  [7f3b...][2a1c...][8e4d...] -> vị trí ngẫu nhiên -> split thường xuyên giữa page
  Mỗi split: InnoDB alloc page mới, chuyển nửa record sang -> tốn kém
  Sau 1M insert: tree bị fragmented, nhiều half-full page, lãng phí không gian

Solution: UUID v7 (RFC 9562, timestamp prefix monotonic) hoặc AUTO_INCREMENT BIGINT. UUID v7 bắt đầu bằng millisecond timestamp → insert gần-sequential → split ít hơn đáng kể.

5. Tech profile B — Redis dict

Project: Redis (in-memory data structure store) Version: Redis 7.0+ Source: https://github.com/redis/redis/blob/7.4/src/dict.c License: RSALv2/SSPL (Redis 7.4+), BSD-3 (phiên bản cũ hơn)

Redis là in-memory key-value store single-threaded (main command loop). Mọi GET, SET, DEL đều chạy trên một thread duy nhất — đây là quyết định thiết kế có chủ ý để tránh lock overhead và đảm bảo atomicity. Hệ quả: bất kỳ operation nào block thread chính đều block toàn bộ Redis.

6. Redis dict structure — 2-table design

Redis dict không phải một hash table đơn giản. Nó có hai hash table ht[0] và ht[1] để phục vụ incremental rehash:

-- Cấu trúc dict (đơn giản hóa từ Redis src/dict.h)
dict:
    type: dictType
    ht_table[2]: mảng hai hash table    -- hai hash table
    ht_used[2]: số entry trong mỗi table
    rehashidx: long                     -- -1 nếu không rehash, ngược lại = bucket tiếp theo cần migrate

Steady state: chỉ ht[0] active, ht[1] là null. rehashidx = -1.

Khi cần resize (load factor vượt ngưỡng hoặc xuống quá thấp): ht[1] được alloc với capacity mới (thường gấp đôi), rehashidx = 0. Bắt đầu incremental rehash.

rehashidx là progress counter: chỉ đến bucket tiếp theo cần migrate từ ht[0] sang ht[1]. Không phải migrate một lần — migrate dần dần, mỗi lần một vài bucket.

Redis dict -- steady state:

  ht[0]: [bucket_0] -> [entry: "user:1" -> "Alice"]
         [bucket_1] -> [entry: "product:5" -> "Laptop"] -> [entry: "product:9" -> "Phone"]
         [bucket_2] -> null
         ...
  ht[1]: null
  rehashidx: -1

Redis dict -- trong quá trình rehash (ht[0] size 4 -> ht[1] size 8):

  ht[0]: [bucket_0] -> null  (đã migrate)
         [bucket_1] -> null  (đã migrate)
         [bucket_2] -> [entry: "foo" -> "bar"]    <- chưa migrate
         [bucket_3] -> [entry: "baz" -> "qux"]    <- chưa migrate
  ht[1]: [bucket_0] -> [entry: "user:1" -> "Alice"]   <- đã migrate
         [bucket_1] -> [entry: "product:5" -> "Laptop"]
         ... 8 bucket tổng...
  rehashidx: 2   <- bucket tiếp theo cần migrate

7. Vì sao Redis cần incremental rehash

Redis single-threaded command loop. Nếu resize hash table thông thường (blocking rehash):

Thời gian    Sự kiện
t=0          SET command đến
t=0.001      resize triggered: alloc bảng mới, bắt đầu migrate 1M entry
t=0.001      ... đang migrate ... đang migrate ... (100-500ms bị block)
t=0.500      toàn bộ 1M entry đã migrate, resize xong
t=0.500      command tiếp theo được xử lý (trễ 499ms)

499ms stall trên một Redis instance production:

• Client timeout (thường set 100–200ms) → error cascade
• Replication lag → replica out of sync
• Monitoring alert spam
• Toàn bộ throughput về 0 trong khoảng thời gian đó

Solution: incremental rehash. Chia 1 lần migrate 1M entry thành N lần migrate 10 bucket. Mỗi command thực hiện thêm một chút migration — latency mỗi command tăng từ khoảng 1µs lên khoảng 2µs, nhưng max latency vẫn dưới 1ms.

-- Incremental rehash (đơn giản hóa từ Redis src/dict.c -- dictRehash())
-- Thực hiện n bước rehash tăng dần.
-- Trả về 1 nếu còn đang rehash, 0 nếu xong.
dictRehash(d, n):
    empty_visits <- n * 10    -- tối đa số bucket rỗng được phép visit

    if d không đang rehash: return 0

    while n > 0 và d.ht_used[0] != 0:
        -- bỏ qua bucket rỗng, nhưng giới hạn số lần iterate
        while d.ht_table[0][d.rehashidx] = null:
            d.rehashidx <- d.rehashidx + 1
            empty_visits <- empty_visits - 1
            if empty_visits = 0: return 1

        -- migrate toàn bộ entry trong bucket hiện tại
        de <- d.ht_table[0][d.rehashidx]
        while de != null:
            nextde <- de.next
            -- tính hash lại cho kích thước table mới
            h <- hash(de.key) mod d.ht_size[1]
            de.next <- d.ht_table[1][h]
            d.ht_table[1][h] <- de
            d.ht_used[0] <- d.ht_used[0] - 1
            d.ht_used[1] <- d.ht_used[1] + 1
            de <- nextde

        d.ht_table[0][d.rehashidx] <- null
        d.rehashidx <- d.rehashidx + 1
        n <- n - 1

    -- kiểm tra rehash xong chưa
    if d.ht_used[0] = 0:
        -- swap: ht[1] trở thành ht[0], reset ht[1]
        free(d.ht_table[0])
        d.ht_table[0] <- d.ht_table[1]
        d.ht_used[0] <- d.ht_used[1]
        d.ht_table[1] <- null
        d.ht_used[1] <- 0
        d.rehashidx <- -1
        return 0
    return 1

Time mỗi bước: O(bucket_size)  Space: O(1) cho mỗi bước

Lookup trong rehash phase phải check cả 2 table: dict GET tìm trong ht[0] trước — nếu không thấy, tìm tiếp trong ht[1]. Điều này đảm bảo không bỏ sót key đã migrate sang ht[1] lẫn key chưa migrate còn ở ht[0].

-- GET trong rehash phase: check cả hai table
dictFind(d, key):
    if d rỗng: return null
    if d đang rehash: thực hiện 1 bước rehash    -- mỗi access đóng góp 1 bước

    for table <- 0 đến 1:
        h <- hash(key) mod d.ht_size[table]
        he <- d.ht_table[table][h]
        while he != null:
            if he.key = key: return he
            he <- he.next
        if d không đang rehash: break    -- chỉ cần check ht[0] khi không rehash
    return null

Time: O(1) amortized  Space: O(1)

graph LR
    CMD["Command đến<br/>(GET/SET/DEL)"]
    STEP["Thực hiện 1 bước<br/>rehash<br/>(migrate vài bucket)"]
    EXEC["Thực thi command<br/>check cả ht[0] và ht[1]"]
    DONE{"ht[0]<br/>rỗng?"}
    SWAP["Swap: ht[1] → ht[0]<br/>rehashidx = -1"]
    NEXT["Command tiếp theo"]
    CMD --> STEP
    STEP --> EXEC
    EXEC --> DONE
    DONE -- "chưa" --> NEXT
    DONE -- "rồi" --> SWAP
    SWAP --> NEXT

8. Bảng so sánh quyết định MySQL vs Redis

Insight cốt lõi: cùng problem "tìm key" nhưng constraints hoàn toàn khác. InnoDB sống trên disk → minimize disk IO là ưu tiên → B+tree fanout 1000 + leaf chain cho range scan. Redis single-threaded in-memory → blocking resize là fatal → hash table O(1) + incremental rehash tránh stall.

9. Production gotcha Redis

9.1 Big key và rehash stall trên RDB save

Redis HGETALL trên Hash key với 10 triệu field — Redis phải iterate toàn bộ internal dict của key đó. Nếu dict đang rehash, traverse thêm phức tạp hơn. RDB fork snapshot đọc toàn bộ memory, các big key làm thời gian fork dài hơn.

Monitor key sizes định kỳ:

-- Scan để tìm key lớn (Redis 4.0+)
redis-cli --bigkeys

-- Hoặc kiểm tra key cụ thể
redis-cli OBJECT ENCODING mykey
redis-cli HLEN myhashkey  -- số field trong Hash

Nếu Hash key vượt vài triệu field, chia thành nhiều key nhỏ: user:1000:profile, user:1000:settings, ... thay vì một key user:1000 chứa tất cả.

9.2 SLOWLOG để catch slow operation

Redis SLOWLOG ghi lại các command tốn hơn ngưỡng (default 10ms):

-- Cấu hình ngưỡng 10ms (đơn vị microsecond)
redis-cli CONFIG SET slowlog-log-slower-than 10000
redis-cli SLOWLOG GET 10  -- 10 entry gần nhất

Các nguyên nhân phổ biến của slow op:

1. Rehash phase trên dict lớn: dictRehashMilliseconds() chạy background nhưng mỗi command vẫn thực hiện 1 rehash step — dict với triệu entry, một step migrate bucket lớn tốn vài ms.
2. Big key operation: SMEMBERS trên Set 100k member, LRANGE key 0 -1 trên List 500k element.
3. KEYS * pattern scan: O(N) trên toàn database — không bao giờ dùng trong production, thay bằng SCAN cursor.

9.3 maxmemory-policy và cross-link Module 2

Redis maxmemory-policy quyết định eviction khi RAM đầy:

• allkeys-lru: evict key ít dùng nhất gần đây nhất (LRU)
• allkeys-lfu: evict key ít dùng nhất về tần suất (LFU)
• volatile-ttl: evict key có TTL ngắn nhất

LRU implementation của Redis dùng một doubly linked list và dict. Cross-link: Thuật toán Căn bản — Module 2 bài 07 LRU mini-challenge giải thích cơ chế đằng sau allkeys-lru.

10. Applied to tech

PostgreSQL — heap + B-tree, khác với InnoDB clustered

PostgreSQL dùng heap storage: rows được lưu trong heap files, không phải trong B-tree leaf. B-tree index của PostgreSQL lưu heap tuple ID (TID) — physical pointer (page_number, slot) trỏ đến row trong heap.

Hệ quả: tất cả index PostgreSQL đều là non-clustered về cơ bản. Query qua bất kỳ index nào cũng cần 2 random IO: (1) traverse B-tree → TID, (2) heap fetch. So với InnoDB clustered primary key chỉ cần 1 walk.

PostgreSQL 12+ thêm INCLUDE index (covering index): lưu thêm column vào leaf node để tránh heap fetch:

-- PostgreSQL covering index: không cần heap fetch cho query dùng id + email
CREATE INDEX idx_user_cover ON users (id) INCLUDE (email, name);
-- Query: SELECT email, name FROM users WHERE id = 42
-- -> duyệt B-tree -> tìm leaf có email + name -> xong, không cần heap fetch

MongoDB / WiredTiger — document B-tree

MongoDB dùng WiredTiger storage engine, cũng dùng B-tree. Document-level locking thay vì row-level. Field _id mặc định là clustered index (ObjectID timestamp-ordered → sequential insert). Secondary index lưu _id reference giống InnoDB lưu primary key.

DynamoDB — partition key + sort key B-tree

DynamoDB dùng hash của partition key để route đến partition server. Bên trong mỗi partition: B-tree được sort theo sort key cho range query. Kết hợp: O(1) partition lookup (hash) + O(log n) range query trong partition (B-tree). Đây là hybrid tương tự cách InnoDB secondary index hoạt động nhưng ở distributed scale.

etcd / Consul — B-tree trên Raft

etcd lưu data trong bbolt B-tree (key-value sorted). Mọi write đi qua Raft consensus trước khi commit vào B-tree. B-tree sorted property cho phép RANGE query (watch prefix, list keys) — thiết yếu cho Kubernetes service discovery. Thuật toán Ứng dụng — Module 4 phân tích sâu distributed consensus layer.

11. Deep Dive tài liệu gốc

12. Tóm tắt

• InnoDB clustered index: primary key leaf chứa toàn bộ row — 1 walk để fetch row. Secondary index leaf chứa primary key → cần double lookup (2 tree traversal). Chọn primary key sequential (AUTO_INCREMENT hoặc UUID v7) để tránh page split storm.
• InnoDB page 16KB: fanout khoảng 1000 với integer key → height 3–4 cho 100 triệu row → 3–4 disk seek per query. Buffer pool cache pages trong RAM, hot working set về gần 0 disk IO.
• Redis dict 2-table: ht[0] active + ht[1] resize target. rehashidx track migration progress. Mỗi command thực hiện thêm 1 migration step — incremental, không blocking.
• Incremental rehash: Redis single-threaded → blocking resize 1M entry tốn 100–500ms → toàn bộ Redis stall. Incremental chia nhỏ thành N bước, max latency per command vẫn dưới 1ms.
• Lookup trong rehash phase: check cả ht[0] và ht[1] để không bỏ sót key chưa hoặc đã migrate.
• MySQL chọn B+tree vì: disk workload + range query cần leaf chain. Redis chọn hash table vì: in-memory + point query only + single-threaded cần incremental resize.
• Production pitfall MySQL: UUID v4 PK gây page split, composite index column order, low cardinality index vô dụng.
• Production pitfall Redis: big key làm rehash/RDB stall, KEYS * O(N) full scan, SLOWLOG để detect slow op.

13. Tự kiểm tra

Bài tiếp theo: Module 1 — Tổng kết & cheat sheet