Case Study: TimSort + Redis ZSET — 2 algorithm chiến thắng production

Module 4 đã đi qua 7 sorting algorithm: Insertion, Merge, Quick, Heap, Counting/Radix, và Skip list. Mỗi bài giải thích cơ chế, độ phức tạp, và tradeoff. Nhưng nếu hỏi production thực tế dùng gì — câu trả lời ngắn hơn nhiều.

Hầu hết code bạn viết đang dùng đúng 2 family: TimSort khi gọi Arrays.sort(Object[]) trong Java, sorted() trong Python, Array.prototype.sort trong V8; và Skip list khi dùng Redis ZSET cho sorted set. Cả hai chiến thắng không phải vì worst-case complexity tốt hơn trên lý thuyết — mà vì chúng fit cực tốt với shape của real-world data.

Bài này dive 2 system: TimSort run detection + galloping merge, Redis ZSET kết hợp skip list + dict. Đọc source thật, hiểu vì sao 2 quyết định này thắng các alternative trong real workload.

1. Tech profile A — TimSort

Origin: Tim Peters viết năm 2002 cho Python list.sort(). Java port: OpenJDK 7+ cho Arrays.sort(Object[]) và Collections.sort(). Source Java: https://github.com/openjdk/jdk/blob/jdk-21+35/src/java.base/share/classes/java/util/TimSort.java Source Python: https://github.com/python/cpython/blob/main/Objects/listobject.c (hàm list_sort_impl)

TimSort không phải thuật toán mới phát minh từ đầu. Tim Peters quan sát một thực tế đơn giản: real-world data hiếm khi hoàn toàn ngẫu nhiên. Log file có timestamp tăng dần. Database row có ID monotonic. Event queue đã gần-sorted. TimSort được thiết kế để khai thác đặc tính này — nhanh trên data thực tế, không chỉ random benchmark.

2. Vì sao TimSort thắng trên real-world data

Tất cả 4 lý do TimSort vượt trội đều liên quan đến run — đoạn liên tiếp đã sorted hoặc reverse-sorted trong input.

Real-world data thường có run. Timestamp trong log tăng đơn điệu. Primary key trong SQL query trả về theo thứ tự insert. Event trong message queue đến theo thứ tự gần-sorted. Khi merge sort thông thường chia đôi mù quáng, TimSort tìm run trước — exploit structure đã có sẵn.

Detect run + extend. TimSort quét input, tìm consecutive ascending hoặc descending. Descending? Reverse in-place thành ascending. Run quá ngắn? Extend bằng insertion sort đến min_run_length (32-64). Insertion sort lý tưởng cho subarray nhỏ vì no overhead + cache-friendly trên dữ liệu gần-sorted (bài 02 đã phân tích: O(n) khi nearly-sorted).

Galloping merge. Khi merge 2 run, nếu 1 phía liên tục thắng (nhiều element liên tiếp đến từ cùng 1 run), TimSort chuyển sang exponential search — tìm vị trí chèn một batch thay vì từng element. Giảm số comparison đáng kể khi 1 run dominate.

Stable. Preserve order khi key bằng nhau — required cho Comparable<T> correctness, ví dụ sort List<Person> theo lastName sau khi đã sort theo department: stability đảm bảo order trong cùng department được giữ nguyên.

3. TimSort — 4 bước algorithm

3.1 Step 1: Compute min_run_length

TimSort tính min_run_length trong khoảng 32-64 sao cho n / min_run gần power of 2 — đảm bảo merge tree balanced.

// Compute min_run_length from n (simplified logic from TimSort.java)
// Result r: n / r is a power of 2 (or close), 32 <= r <= 64
static int minRunLength(int n) {
    int r = 0;
    while (n >= MIN_MERGE) {   // MIN_MERGE = 32
        r |= (n & 1);
        n >>= 1;
    }
    return n + r;
}
// MIN_MERGE = 32: any run shorter than 32 gets extended by insertion sort

Kết quả: sort 1000 element → min_run khoảng 40 → khoảng 25 run → merge tree có ~5 level, balanced tốt.

3.2 Step 2: Detect và extend run

// Simplified run detection (from TimSort.java countRunAndMakeAscending)
// Returns length of the ascending run starting at lo
private static int countRunAndMakeAscending(Object[] a, int lo, int hi, Comparator c) {
    int runHi = lo + 1;
    if (runHi == hi) return 1;

    // Is run descending?
    if (c.compare(a[runHi++], a[lo]) < 0) {
        while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
            runHi++;
        reverseRange(a, lo, runHi); // flip descending -> ascending in-place
    } else {
        while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
            runHi++;
    }
    return runHi - lo;
}

Sau khi detect run, nếu runLen < minRun: gọi binarySort (insertion sort với binary search) để extend run lên minRun element.

3.3 Step 3: Merge stack với invariant

Mỗi run được push vào stack. TimSort maintain 2 invariant để đảm bảo merge balanced:

Invariant 1: runLen[i-3] > runLen[i-2] + runLen[i-1]
Invariant 2: runLen[i-2] > runLen[i-1]

Mỗi khi push run mới, kiểm tra invariant. Vi phạm → merge 2 run gần nhất:

// mergeCollapse: enforce merge invariants
private void mergeCollapse() {
    while (stackSize > 1) {
        int n = stackSize - 2;
        if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
            if (runLen[n-1] < runLen[n+1]) n--;
            mergeAt(n);      // merge run n and n+1
        } else if (runLen[n] <= runLen[n+1]) {
            mergeAt(n);
        } else {
            break;           // invariant satisfied
        }
    }
}

Invariant này đảm bảo: các run được merge khi có kích thước tương đương nhau — merge balanced giống Merge sort, không phải degenerate left-skewed merge.

3.4 Step 4: Galloping mode trong merge

Trong merge 2 run, TimSort đếm "consecutive win" của mỗi side. Nếu một side thắng liên tục MIN_GALLOP lần (default 7), switch sang gallop mode:

// Simplified mergeAt (TimSort.java)
private void mergeAt(int i) {
    int base1 = runBase[i];
    int len1  = runLen[i];
    int base2 = runBase[i + 1];
    int len2  = runLen[i + 1];

    // Find first element of run2 in run1 -- skip prefix of run1 < a[base2]
    int k = gallopRight(a[base2], a, base1, len1, 0);
    base1 += k;
    len1  -= k;
    if (len1 == 0) return;  // run1 entirely <= run2[0], already in order

    // Find last element of run1 in run2 -- skip suffix of run2 > a[base1+len1-1]
    len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1);
    if (len2 == 0) return;

    // Merge remaining portions with galloping
    mergeLo(base1, len1, base2, len2);
}

gallopRight dùng exponential search: thử offset 1, 2, 4, 8, 16, ... → tìm vị trí trong O(log k) thay vì O(k) nếu cần skip k element. Khi data có long run dominance, gallop skip hàng trăm comparison trong một lần.

4. TimSort empirical — so sánh real workload

Java dùng 2 algorithm khác nhau: Arrays.sort(int[]) dùng Dual-Pivot Quicksort (Yaroslavskiy 2009) — không cần stable, in-place, nhanh hơn trên primitive array random. Arrays.sort(Object[]) dùng TimSort — cần stable (Comparable contract), Object array có overhead boxing nên cache miss nhiều hơn, nearly-sorted data common khi sort domain object.

5. JEP 273 bug — proof không đủ, test mới đủ

Năm 2015, Stijn de Gouw et al. dùng formal verification (KeY theorem prover) phát hiện bug trong Java TimSort:

mergeCollapse có off-by-one trong invariant check. Bug: khi stack có đúng 4 run và size thỏa mãn condition cụ thể, invariant được check sai thứ tự → run stack không được merge kịp → runBase array overflow → ArrayIndexOutOfBoundsException.

Bug này cực rare: cần array size hàng chục nghìn element, specific size ratio giữa run, và exact execution path. Hầu hết production code không bao giờ hit — nhưng khi hit, crash runtime với exception không rõ nguồn gốc.

Fix trong JEP 273 (2016): adjust stack size formula và sửa invariant check order. Sau fix, formal proof hoàn chỉnh.

6. Tech profile B — Redis ZSET

Project: Redis 7.x Source: src/t_zset.c (ZADD, ZRANGE, ZRANGEBYSCORE, ZRANK, ZREM) và src/server.h (struct definitions) Operations: ZADD O(log n), ZRANGE O(log n + k), ZRANGEBYSCORE O(log n + k), ZRANK O(log n), ZREM O(log n)

Redis ZSET là sorted set: mỗi member có một score (float64), set luôn duy trì thứ tự theo (score, member) lexicographic. Use case điển hình: leaderboard, timeline feed, priority queue.

7. Redis ZSET — dual structure skip list + dict

ZSET không phải một cấu trúc đơn giản. Nó dùng hai cấu trúc song song:

Redis ZSET (5 members):

Skip list (ordered by score):
  header
  L2: -----> [Alice:1.0] -----------------------> [Eve:4.5] -> null
  L1: -----> [Alice:1.0] -> [Bob:2.5] ----------> [Eve:4.5] -> null
  L0: -----> [Alice:1.0] -> [Bob:2.5] -> [Carol:3.0] -> [Dan:4.0] -> [Eve:4.5] -> null

Dict (hash table member -> score):
  "Alice" -> 1.0
  "Bob"   -> 2.5
  "Carol" -> 3.0
  "Dan"   -> 4.0
  "Eve"   -> 4.5

Skip list sorted theo (score, member):

• ZRANGEBYSCORE min max → O(log n + k): traverse từ header xuống đến score min, rồi scan level 0 forward lấy k result.
• ZRANGE (in-order scan) → O(1) per next: level 0 là sorted linked list, next pointer tự nhiên.

Dict mapping member → score:

• ZSCORE member → O(1): hash lookup trực tiếp.
• ZADD update: lookup old score qua dict O(1), remove từ skip list O(log n) bằng old score, insert với score mới O(log n).

Trade-off: khoảng 2x memory so với single structure — mỗi member được lưu 2 lần (skip list node + dict entry). Acceptable vì Redis là in-memory store — RAM đắt nhưng đã được accept từ đầu khi chọn Redis.

8. Skip list node trong Redis source

// src/server.h (Redis 7.x)
typedef struct zskiplistNode {
    sds ele;                          // member string
    double score;                     // sort key
    struct zskiplistNode *backward;   // prev pointer (level 0 only, for reverse scan)
    struct zskiplistLevel {
        struct zskiplistNode *forward; // next node at this level
        unsigned long span;            // number of nodes skipped at this level
    } level[];                        // flexible array -- actual size = random level
} zskiplistNode;

Trường span là đặc trưng của Redis, không có trong skip list chuẩn. span tại level[i] = số node ở level 0 bị skip khi đi từ node hiện tại sang forward[i]. Tích lũy span khi traverse từ header xuống leaf → biết chính xác rank của node đích → ZRANK chạy trong O(log n) thay vì O(n).

// Simplified ZRANK computation (from t_zset.c zslGetRank)
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *x = zsl->header;
    unsigned long rank = 0;

    for (int i = zsl->level - 1; i >= 0; i--) {
        while (x->level[i].forward &&
               (x->level[i].forward->score < score ||
               (x->level[i].forward->score == score &&
                sdscmp(x->level[i].forward->ele, ele) <= 0))) {
            rank += x->level[i].span;  // accumulate span as we jump
            x = x->level[i].forward;
        }
        if (x->ele && sdscmp(x->ele, ele) == 0) return rank;
    }
    return 0; // not found
}

9. Vì sao Redis chọn skip list thay Red-Black tree

Salvatore Sanfilippo (Redis author) giải thích thẳng trong comment source code: skip list dễ implement hơn RB tree và cho range scan tự nhiên hơn. Redis single-threaded nên concurrent advantage của skip list không phải lý do chính — simplicity và range scan mới là.

Red-Black tree vẫn tốt hơn khi cần O(log n) worst-case guaranteed (không phải expected) và không cần range scan thường xuyên — ví dụ Java TreeMap.

10. Bảng decision matrix

11. Applied to tech

Python sorted() / list.sort() — TimSort gốc (Tim Peters 2002, viết cho CPython). Mọi Python sorted() call đều là TimSort.

Android Collections.sort — Android dùng OpenJDK port. Collections.sort delegate sang Arrays.sort(Object[]) → TimSort. Consistent với JDK behavior.

V8 Array.prototype.sort — V8 (Node.js + Chrome) dùng QuickSort trước năm 2018. Từ V8 7.0 (Chrome 70, Node 11), chuyển sang TimSort (viết bằng Torque, V8's typed TypeScript DSL). Lý do: ES2019 spec yêu cầu stable sort, TimSort đáp ứng.

Twitter/X timeline feed — Redis ZSET cho user feed với (timestamp, tweet_id) làm score. ZRANGEBYSCORE để paginate timeline theo thời gian. ZADD mỗi khi có tweet mới. Với follower count cao (celebrity account), fan-out write cần cẩn thận — nhưng ZSET operation per user là O(log n).

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

13. Tóm tắt

• TimSort khai thác run trong real-world data: detect ascending/descending run, extend bằng insertion sort, merge với galloping. Nearly-sorted input chạy near-O(n).
• min_run_length (32-64) được tính để số run gần power of 2 → balanced merge tree → ít level merge hơn.
• Gallop mode trigger sau 7 consecutive win của 1 side: exponential search skip batch element thay từng cái → giảm comparison khi 1 run dominate.
• JEP 273: formal verification phát hiện off-by-one trong mergeCollapse năm 2015 — proof informal không đủ, property-based test mới đủ.
• Redis ZSET dùng 2 structure song song: skip list cho range query O(log n + k) và in-order scan, dict cho point lookup ZSCORE O(1). Trade-off: 2x memory.
• span field trong Redis skip list node tích lũy khi traverse → ZRANK O(log n) — innovation so với skip list chuẩn.
• Skip list thắng RB tree trong Redis vì: ít code hơn 3x, range scan tự nhiên qua level 0 linked list, dễ debug. RB tree vẫn tốt hơn khi cần O(log n) worst-case guaranteed.
• Java dùng 2 algorithm: Dual-Pivot Quick cho int[] (no stability needed, fast on random), TimSort cho Object[] (stable required, nearly-sorted common).

14. Tự kiểm tra

Bài tiếp theo: Graph representation — adjacency list vs matrix