External merge sort — sắp xếp vượt RAM

TL;DR: Khi dữ liệu vượt RAM (100 GB với 8 GB RAM), không thể sort in-memory. External merge sort chia thành hai phase: Phase 1 đọc từng chunk vừa RAM, sort in-memory, ghi ra "run" trên disk; Phase 2 dùng min-heap k-way merge gộp tất cả run thành kết quả sắp xếp mà chỉ giữ k phần tử đầu mỗi run trong RAM. Số pass đọc/ghi I/O = ceil(log_k(N/M)) — tăng k giảm số pass. Đây là nền của ORDER BY trong Postgres, shuffle phase của MapReduce, và external dedup ở mọi hệ pipeline lớn.

Bạn vừa nhận task: sort log file 100 GB từ server production. Máy chỉ có 8 GB RAM. Gọi Arrays.sort() hay sort() built-in? Chương trình crash ngay với OutOfMemoryError — vì toàn bộ dữ liệu không vừa RAM. Đây là vấn đề external sort: sort tập dữ liệu lớn hơn bộ nhớ khả dụng, phải tận dụng disk làm bộ nhớ phụ.

External sort không phải niche: mỗi lần Postgres thực thi ORDER BY trên bảng lớn (không vừa work_mem), mỗi lần MapReduce shuffle dữ liệu giữa mapper và reducer, mỗi lần Kafka compact log — đều chạy một variant của thuật toán này.

1. Mô hình bài toán và giới hạn I/O

Cho N record cần sort, RAM khả dụng M (tính theo số record). Constraint chính không phải CPU — là số lần đọc/ghi disk (I/O). Đọc/ghi tuần tự (sequential) nhanh hơn random I/O ~100 lần; thuật toán tốt tối thiểu hoá số pass qua toàn bộ dữ liệu.

Định nghĩa: một pass là đọc qua toàn bộ N record + ghi kết quả. Mục tiêu: tối thiểu số pass.

2. Phase 1 — tạo sorted run

Đọc từng chunk M record vào RAM, sort in-memory (bằng bất kỳ thuật toán O(n log n)), ghi ra file "run" trên disk. Lặp cho đến hết input.

function createRuns(inputFile, M):
    runs <- []                              -- danh sách file run trên disk
    while inputFile chưa hết:
        chunk <- đọc M record từ inputFile  -- đọc vừa đủ RAM
        sort(chunk)                         -- sort in-memory, O(M log M)
        runFile <- ghi chunk ra disk
        runs.append(runFile)
    return runs
// Time: O(N log M)  Space: O(M) RAM
// I/O: 1 pass đọc + 1 pass ghi = 2N I/O

Với 100 GB dữ liệu và 8 GB RAM: sinh ra ceil(100/8) = 13 run, mỗi run 8 GB đã sorted.

3. Phase 2 — k-way merge bằng min-heap

Có R run đã sorted trên disk. Cần gộp thành 1 file sorted. Naive: merge từng cặp như merge sort — nhưng cần log2(R) lần duyệt lại toàn bộ dữ liệu. k-way merge gộp k run cùng lúc, giảm số pass xuống ceil(log_k(R)).

Cơ chế: dùng min-heap kích thước k. Mỗi slot heap giữ phần tử nhỏ nhất hiện tại của một run, kèm con trỏ biết lấy từ run nào. Mỗi bước: pop phần tử nhỏ nhất từ heap (là phần tử nhỏ nhất toàn bộ), ghi vào output, nạp phần tử kế của run đó vào heap.

function kWayMerge(runs[0..k-1], outputFile):
    H <- MinHeap()
    for i từ 0 đến k-1:                    -- khởi tạo heap với phần tử đầu mỗi run
        if runs[i] không rỗng:
            H.push((runs[i].readNext(), i)) -- (giá trị, chỉ số run)

    while H không rỗng:
        (val, runIdx) <- H.pop()            -- lấy phần tử nhỏ nhất toàn bộ
        outputFile.write(val)
        if runs[runIdx] không rỗng:
            H.push((runs[runIdx].readNext(), runIdx))  -- nạp phần tử kế
// Time: O(N log k)  Space: O(k) trên RAM (heap chỉ giữ k phần tử)
// I/O mỗi pass: 2N (đọc + ghi); số pass = ceil(log_k(R))

Tại sao min-heap đúng? Tại mọi thời điểm, heap chứa đúng k ứng viên — một từ mỗi run. Phần tử đầu heap nhỏ nhất trong k ứng viên, và vì mỗi run đã sorted, phần tử đó nhỏ nhất trong tất cả dữ liệu còn lại. Bằng chứng bằng induction: sau mỗi pop, invariant được duy trì.

3.1 Trace k-way merge với k=3

3 run đã sorted:

Run 0: [1, 5, 9]
Run 1: [2, 4, 8]
Run 2: [3, 6, 7]

Output cuối: 1 2 3 4 5 6 7 8 9 — đúng.

4. Phân tích I/O — vì sao tăng k quan trọng

Tổng I/O (đơn vị: số lần đọc/ghi N record):

Tổng pass = 1 (Phase 1) + ceil(log_k(R))   -- R = ceil(N/M)

Với N=100 GB, M=8 GB → R=13 run:

Với k=13 (merge tất cả run trong 1 pass), chỉ cần 2 pass tổng — tiết kiệm ~60% I/O so với k=2. Nhưng k lớn đòi hỏi k buffer page RAM cho mỗi run; giới hạn thực tế của k phụ thuộc RAM/page-size.

flowchart TD
    INPUT["Dữ liệu 100 GB\n(chưa sắp xếp)"]
    C1["Chunk 8 GB → sort → Run 1"]
    C2["Chunk 8 GB → sort → Run 2"]
    C3["... → Run 13"]
    HEAP["Min-Heap (k=13)\ngiữ 13 phần tử đầu"]
    OUT["Output sorted\n100 GB"]

    INPUT --> C1
    INPUT --> C2
    INPUT --> C3
    C1 --> HEAP
    C2 --> HEAP
    C3 --> HEAP
    HEAP --> OUT

5. Ứng dụng thực tế

Postgres tuplesort: khi ORDER BY không vừa work_mem, Postgres dùng external sort với k-way merge. Parameter work_mem điều chỉnh M; EXPLAIN ANALYZE hiện Sort Method: external merge khi bị spill to disk.

MapReduce shuffle: sau Map phase, mỗi mapper sort output của mình (Phase 1); Reducer nhận nhiều sorted partition từ nhiều mapper và k-way merge (Phase 2). Đây chính là lý do MapReduce "shuffle" tốn kém — nó là external sort toàn cluster.

External dedup: thay vì sort để tìm unique, pipeline lớn (Spark distinct(), Flink dedup) sort trước rồi quét liên tiếp loại bản sao — linear scan sau external sort rẻ hơn hash table khi data vượt RAM.

6. Pitfall

Pitfall 1 — Chọn k quá lớn, buffer mỗi run quá nhỏ

-- SAI: k = 1000 run, mỗi buffer chỉ còn 8 KB
-- → random I/O liên tục (mỗi lần readNext đọc 8 KB) → chậm hơn k nhỏ hơn

-- ĐÚNG: k = floor(M / buffer_per_run)
-- Đảm bảo mỗi run có buffer đủ lớn để sequential read
-- Ví dụ: M = 8 GB, buffer_per_run = 4 MB → k = 2048, nhưng thực tế
-- Postgres/DBMS giới hạn k ~500 vì quản lý nhiều file descriptor tốn kém

Pitfall 2 — Bỏ quên double buffering gây I/O stall

-- SAI: đọc buffer → process → đọc buffer → process (tuần tự, CPU chờ I/O)

-- ĐÚNG: double buffer — trong khi CPU xử lý buffer A,
-- I/O đọc sẵn buffer B (prefetch); xong đổi vai
-- Tăng throughput ~2x trên HDD/SSD thông thường

Pitfall 3 — Không xử lý run cuối nhỏ hơn M

-- SAI: giả định mọi run đều M record
-- → nếu N không chia hết M, run cuối nhỏ hơn
-- → heap push sai số lượng / index out of bounds

-- ĐÚNG: kiểm tra "runs[i] không rỗng" trước mỗi readNext
-- (đã có trong pseudocode kWayMerge ở trên)

7. Liên hệ các bài khác

• Heap & heapsort: min-heap là cốt lõi của k-way merge — hiểu cách push/pop O(log k) là cách hiểu tại sao Phase 2 chạy O(N log k). Đọc bài đó trước nếu chưa quen heap.
• Merge sort: external sort là generalisation của merge sort lên disk. Phase 1 tương đương base case; Phase 2 tương đương merge pass. Khác biệt: merge sort recursive in-memory; external sort iterative, k-way, I/O-aware.
• Amortized analysis: phân tích "số pass × 2N I/O mỗi pass" là amortized nhìn từ góc độ I/O thay vì CPU cycle.
• Count-Min Sketch: cùng context big-data streaming — khi sort quá đắt (data vô tận), dùng probabilistic structure thay thế; cross-reference hiểu tradeoff exact vs approximate.
• Case study Redis & Kafka: Kafka log compaction dùng external sort để merge segment — đọc case study để thấy thuật toán này trong hệ thống production thực.

📚 Deep Dive

Tóm tắt

• External sort chia thành Phase 1 (tạo sorted run in-memory) và Phase 2 (k-way merge bằng min-heap).
• Phase 1 I/O: 2N (1 pass đọc + 1 pass ghi); Phase 2 I/O: 2N × ceil(log_k(R)) pass.
• Min-heap giữ chỉ k phần tử trong RAM; mỗi pop O(log k); tổng Phase 2 O(N log k).
• Tăng k giảm số pass I/O nhưng đòi hỏi nhiều buffer RAM hơn — cân bằng thực tế phụ thuộc work_mem và kích thước buffer.
• Postgres dùng external merge sort khi ORDER BY không vừa work_mem; MapReduce shuffle là external sort phân tán.
• Double buffering (prefetch) tăng throughput ~2x; replacement selection tăng kích thước run trung bình lên ~2M.

Tự kiểm tra

Bài tiếp theo: Reservoir sampling — mẫu ngẫu nhiên từ stream