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

TL;DR: Production sort hội tụ về 2 family: TimSort cho in-memory sort của Object (Java Arrays.sort(Object[]), Python sorted(), V8, Android) và Skip list cho sorted set cần range query (Redis ZSET). TimSort khai thác run — đoạn liên tiếp đã sorted trong real-world data — bằng run detection, galloping merge, và merge stack invariant; near-O(n) khi nearly-sorted. Redis ZSET kết hợp skip list (range scan tự nhiên) + dict (O(1) point lookup), trường span bổ sung cho phép ZRANK O(log n). Cả hai chiến thắng không phải vì worst-case tốt hơn trên lý thuyết — mà vì fit cực tốt với shape của real-world data.

Module 2 đã đi qua 8 bài về sorting: Quadratic sorts, Merge sort, Quick sort, Heap sort, Counting/Radix/Bucket sort, Skip list, và External merge sort. 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 Bước 1: Tính 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.

MinRunLength(n):
    -- Kết quả r: n / r gần power of 2; 32 <= r <= 64
    MIN_MERGE <- 32
    r <- 0
    while n >= MIN_MERGE:
        r <- r | (n & 1)    -- ghi nhận bit lẻ
        n <- n >> 1          -- dịch phải
    return n + r

Time: O(log n) Space: O(1)

Kết quả: sort 1000 element → min_run = 32 (minrun ∈ [32, 64]) → khoảng 32 run → merge tree có khoảng 5 level, balanced tốt.

3.2 Bước 2: Detect và extend run

CountRunAndMakeAscending(A, lo, hi, compare):
    -- Trả về độ dài của ascending run bắt đầu tại lo
    runHi <- lo + 1
    if runHi = hi: return 1

    -- Kiểm tra descending
    if compare(A[runHi], A[lo]) < 0:
        runHi <- runHi + 1
        while runHi < hi và compare(A[runHi], A[runHi-1]) < 0:
            runHi <- runHi + 1
        ReverseRange(A, lo, runHi)   -- lật descending thành ascending
    else:
        while runHi < hi và compare(A[runHi], A[runHi-1]) >= 0:
            runHi <- runHi + 1

    return runHi - lo

Time: O(k) với k = độ dài run Space: O(1)

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

3.3 Bước 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]

MergeCollapse(stack):
    while stackSize > 1:
        n <- stackSize - 2
        if n > 0 và runLen[n-1] <= runLen[n] + runLen[n+1]:
            if runLen[n-1] < runLen[n+1]:
                n <- n - 1
            MergeAt(n)      -- merge run n và run n+1
        else if runLen[n] <= runLen[n+1]:
            MergeAt(n)
        else:
            break           -- invariant thoả mãn, dừng

Time: O(n log n) tổng thể Space: O(n)

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 Bước 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:

MergeWithGallop(A, run1, run2, compare):
    -- Cắt bỏ prefix/suffix không cần merge
    k <- GallopRight(A[run2.start], A, run1.start, run1.len, 0, compare)
    run1.start <- run1.start + k
    run1.len   <- run1.len - k
    if run1.len = 0: return

    run2.len <- GallopLeft(A[run1.end], A, run2.start, run2.len, run2.len-1, compare)
    if run2.len = 0: return

    -- Merge phần còn lại với gallop mode khi 1 side dominate
    MergeLo(A, run1.start, run1.len, run2.start, run2.len)

Time: O(n log k) khi gallop hiệu quả (k = số element cần skip) Space: O(min(run1.len, run2.len))

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.

flowchart TD
    START["Bắt đầu — tính min_run_length"]
    DETECT["Detect run tại vị trí lo<br/>(ascending hoặc descending)"]
    EXTEND["Run ngắn hơn min_run?<br/>Extend bằng insertion sort"]
    PUSH["Push run vào stack"]
    COLLAPSE{"Vi phạm merge invariant?"}
    MERGE["MergeAt(n) — merge 2 run liền kề"]
    MORE{"Còn phần tử chưa xử lý?"}
    FINAL["MergeForceCollapse — merge tất cả run còn lại"]
    DONE["Kết quả đã sort"]

    START --> DETECT --> EXTEND --> PUSH --> COLLAPSE
    COLLAPSE -- "có" --> MERGE --> COLLAPSE
    COLLAPSE -- "không" --> MORE
    MORE -- "có" --> DETECT
    MORE -- "không" --> FINAL --> DONE

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:

graph TD
    ZSET["Redis ZSET\n(5 thành viên)"]

    ZSET --> SL["Skip list — thứ tự theo score"]
    ZSET --> DT["Dict — tra cứu theo member"]

    SL --> L2["Tầng 2: Alice:1.0 → Eve:4.5"]
    SL --> L1["Tầng 1: Alice:1.0 → Bob:2.5 → Eve:4.5"]
    SL --> L0["Tầng 0: Alice:1.0 → Bob:2.5 → Carol:3.0 → Dan:4.0 → Eve:4.5"]

    DT --> E1["Alice → 1.0"]
    DT --> E2["Bob → 2.5"]
    DT --> E3["Carol → 3.0"]
    DT --> E4["Dan → 4.0"]
    DT --> E5["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

Cấu trúc node Redis (C):

zskiplistNode:
    ele          -- member string (SDS)
    score        -- sort key (float64)
    backward     -- con trỏ về node trước (level 0, cho reverse scan)
    level[]:     -- mảng level (kích thước = random level của node)
        forward  -- con trỏ tới node kế tiếp tại level này
        span     -- số node ở level 0 bị skip khi đi từ đây tới forward

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).

Pseudocode ZRANK (lấy rank theo score + member):

ZGetRank(zsl, score, member):
    node <- zsl.header
    rank <- 0

    for i <- zsl.maxLevel-1 xuống 0:
        while node.level[i].forward != null và
              (node.level[i].forward.score < score hoặc
               (node.level[i].forward.score = score và
                node.level[i].forward.ele <= member)):
            rank <- rank + node.level[i].span   -- cộng dồn span khi nhảy
            node <- node.level[i].forward

        if node.ele = member:
            return rank

    return 0   -- không tìm thấy

Time: O(log n) Space: O(1)

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.
• Trường span 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: Module 2 — Tổng kết & cheat sheet