Mini-challenge — External merge sort: sort 10GB file với 1GB RAM

Production gặp OOM: bạn nhận task sort một file text 10GB chứa 1 integer mỗi dòng. Máy chỉ có 1GB RAM. Gọi sort trực tiếp sau khi load toàn bộ file? OOM tức thì.

Cùng vấn đề xảy ra trong database: ORDER BY trên result set vượt work_mem trong PostgreSQL sẽ spill xuống disk thay vì crash — nhưng logic bên dưới là y chang: chia dữ liệu thành chunk vừa RAM, sort từng chunk, rồi k-way merge.

Bài này luyện pattern external merge sort: split → sort chunks → k-way merge. Sau khi xong, bạn hiểu được sort algorithm mà Postgres, Lucene, và Hadoop dùng.

graph LR
    IN["File 10GB\n(không vừa RAM)"]
    P1["Phase 1 — Chia chunk\nĐọc chunkSize dòng\nSort trong RAM\nGhi ra file tạm"]
    P2["Phase 2 — K-way merge\nMở tất cả chunk\nMin-heap chọn min\nGhi ra output"]
    OUT["File output\n(đã sort)"]
    IN --> P1 --> P2 --> OUT

Yêu cầu bài toán

Viết class ExternalSorter với API sau:

• sort(inputFile, outputFile, chunkSize) — sort toàn bộ file thành output sorted ascending.
• Constraint: bộ nhớ chỉ giữ tối đa chunkSize integer cùng lúc (Phase 1) + buffer nhỏ cho merge (Phase 2, tối đa k integer với k = số chunk).
• Output: sorted ascending, mỗi integer một dòng.

Test scenario

Generate input: 1 triệu integer, 1 per line, file khoảng 10MB.

Sort với chunkSize = 100_000 (khoảng 100 nghìn integer mỗi chunk, khoảng 1MB).

Verify: output sorted, count giống input, sum giống input.

Starter code

Dưới đây là skeleton pseudocode mô tả API cần implement:

ExternalSorter.sort(inputFile, outputFile, chunkSize):
    -- Phase 1: chia input thành các chunk đã sorted
    chunks <- splitAndSort(inputFile, chunkSize)

    -- Phase 2: k-way merge tất cả chunk vào output
    kWayMerge(chunks, outputFile)

    -- Dọn dẹp file tạm
    for each chunk trong chunks:
        delete(chunk)

splitAndSort(inputFile, chunkSize):
    -- TODO: implement
    return []

kWayMerge(chunks, outputFile):
    -- TODO: implement

Dành 25-30 phút tự làm trước khi xem gợi ý.

Test harness (Java)

-- Sinh 1 triệu integer ngẫu nhiên vào file input
input  <- tempFile("sort-input.txt")
output <- tempFile("sort-output.txt")

expectedSum <- 0
for i <- 0 đến 999_999:
    v <- Random.nextInt(10_000_000)
    expectedSum <- expectedSum + v
    writeLine(input, v)

-- Chạy sort
start <- currentTimeNanos()
ExternalSorter.sort(input, output, chunkSize=100_000)
ms <- (currentTimeNanos() - start) / 1_000_000
print("Sort done in " + ms + " ms")

-- Verify: sorted + count đúng + sum đúng
count <- 0
actualSum <- 0
prev <- LONG_MIN
for each line trong output:
    v <- parseLong(line)
    if v < prev:
        throw "NOT SORTED at line " + count
    prev <- v
    actualSum <- actualSum + v
    count <- count + 1

assert count = 1_000_000
assert actualSum = expectedSum
print("PASS: sorted, count=1000000, sum verified")

Gợi ý

splitAndSort(inputFile, chunkSize):
    chunks <- []
    buffer[0..chunkSize-1] <- 0
    idx <- 0

    for each line trong inputFile:
        buffer[idx] <- parseInt(line)
        idx <- idx + 1
        if idx = chunkSize:
            chunks.append(writeSortedChunk(buffer, idx))
            idx <- 0

    if idx > 0:
        chunks.append(writeSortedChunk(buffer, idx))

    return chunks

kWayMerge(chunks, outputFile):
    readers[0..N-1] <- mở từng chunk file
    heap <- MinHeap rỗng

    -- Nạp phần tử đầu tiên từ mỗi chunk
    for i <- 0 đến N-1:
        line <- readers[i].readLine()
        if line != null:
            heap.push((parseInt(line), i))

    -- Merge loop: luôn lấy global minimum
    writer <- mở outputFile để ghi
    while heap không rỗng:
        (value, fileIdx) <- heap.pop()
        writer.writeLine(value)

        -- Đọc phần tử tiếp theo từ file vừa đóng góp
        next <- readers[fileIdx].readLine()
        if next != null:
            heap.push((parseInt(next), fileIdx))

    đóng writer
    đóng tất cả readers

Lời giải

ExternalSorter.sort(input, output, chunkSize):
    chunks <- splitAndSort(input, chunkSize)
    kWayMerge(chunks, output)
    for each c trong chunks:
        deleteFile(c)

-- Phase 1: đọc input, chia chunk, sort, ghi file tạm
splitAndSort(input, chunkSize):
    chunks <- []
    buffer[0..chunkSize-1] <- 0
    idx <- 0

    for each line trong readLines(input):
        buffer[idx] <- parseInt(line)
        idx <- idx + 1
        if idx = chunkSize:
            chunks.append(writeSortedChunk(buffer, idx))
            idx <- 0

    if idx > 0:
        chunks.append(writeSortedChunk(buffer, idx))
    return chunks

-- Sort buffer[0..len-1] rồi ghi ra file tạm
writeSortedChunk(buffer, len):
    sorted <- copy(buffer, 0, len)
    Sort(sorted)                          -- in-memory sort (O(len log len))
    chunk <- createTempFile("ext-sort-")
    for each v trong sorted:
        writeLine(chunk, v)
    return chunk

-- Phase 2: mở tất cả chunk, k-way merge vào output
kWayMerge(chunks, output):
    N <- length(chunks)
    readers[0..N-1] <- mở từng chunk để đọc
    heap <- MinHeap rỗng (so sánh theo value)

    -- Nạp phần tử đầu từ mỗi chunk
    for i <- 0 đến N-1:
        line <- readers[i].readLine()
        if line != null:
            heap.push((parseInt(line), i))

    writer <- mở output để ghi
    while heap không rỗng:
        (val, fileIdx) <- heap.pop()      -- lấy minimum toàn cục
        writer.writeLine(val)
        next <- readers[fileIdx].readLine()
        if next != null:
            heap.push((parseInt(next), fileIdx))

    đóng writer
    đóng tất cả readers trong finally

Pitfall

Pitfall 1 — File handle leak: quên đóng reader trong finally.

-- BUG: exception trong kWayMerge bỏ qua lệnh đóng
kWayMerge(chunks, output):
    for i <- 0 đến N-1:
        readers[i] <- openFile(chunks[i])   -- mở file
    -- ... merge logic có thể throw ...
    for each r trong readers:
        r.close()   -- KHÔNG BAO GIỜ ĐẾN ĐÂY nếu có exception

-- ĐÚNG: dùng finally đảm bảo luôn đóng
kWayMerge(chunks, output):
    readers <- []
    try:
        for i <- 0 đến N-1:
            readers[i] <- openFile(chunks[i])
        -- ... merge logic ...
    finally:
        for each r trong readers:
            if r != null: r.close()

Với N lớn (nghìn chunk), mỗi reader mở 1 file descriptor. Khi exception xảy ra và close không được gọi, file descriptor leak tích lũy → "Too many open files" OS error.

Pitfall 2 — Charset encoding: giả định sai encoding của input file.

-- Luôn chỉ định charset tường minh khi mở file
reader <- openFile(path, charset=UTF_8)
writer <- openFile(path, charset=UTF_8)
-- Tránh dùng charset mặc định của hệ điều hành (có thể thay đổi)

File từ Windows editors có thể UTF-16 với BOM, hoặc Windows-1252. parseInt ném exception với ký tự lạ thay vì lỗi encoding rõ ràng — khó debug. Validate charset tường minh từ đầu.

Pitfall 3 — Quên flush writer: data mất ở cuối file.

-- NGUY HIỂM: close thủ công có thể bị bỏ qua khi exception
writer <- openFile(output)
-- ... ghi dữ liệu ...
writer.close()   -- gọi flush() bên trong, nhưng nếu exception xảy ra trước thì bỏ qua

-- AN TOÀN: try-with-resources đảm bảo flush + close luôn xảy ra
try writer <- openFile(output):
    -- ... ghi dữ liệu ...
-- auto flush + close ở đây, kể cả khi có exception

Benchmark tham khảo

Sort 10GB file (1 tỉ integer), chunkSize 100M:
  Naive load-all: OOM ngay lập tức
  External merge (10 chunk x 1GB mỗi chunk):
    Phase 1 split+sort: ~5 phút  (CPU-bound: sort 1B phần tử)
    Phase 2 k-way merge: ~3 phút (IO-bound: đọc+ghi 10GB tuần tự)
    Tổng: ~8 phút
  HDD sequential write/read: ~150 MB/s -> IO-bound
  SSD sequential: ~500 MB/s  -> nhanh hơn 2-3x Phase 2

Bottleneck Phase 1 là CPU (sort). Bottleneck Phase 2 là IO bandwidth — không phải CPU, không phải memory. Tăng RAM để tăng chunkSize → ít chunk hơn → Phase 2 ít file hơn → nhanh hơn chút. Tăng số thread sort chunk song song → Phase 1 nhanh hơn đáng kể.

Variant để tự thử

Variant 1 — Thay sort trong Phase 1 bằng Counting sort: Nếu biết range (ví dụ 0 đến 9,999,999), Counting sort O(n + range) thay O(n log n). Với n = 100k và range = 10M, trade-off không rõ ràng — thử đo benchmark thực tế.

Variant 2 — Multi-pass merge khi N vượt 1000: Nếu chunkSize nhỏ và file lớn, N chunk có thể vượt ulimit -n. Fix: merge tối đa 500 file thành 1 trong mỗi pass, lặp lại đến khi còn 1 file. Đây là cách sort trên Unix xử lý file khổng lồ.

Variant 3 — Compression chunk file: Ghi chunk qua nén (gzip). Trade IO bandwidth lấy CPU: chunk file nhỏ 3-5x, Phase 2 đọc ít bytes hơn. Hiệu quả khi disk IO là bottleneck (HDD).

Variant 4 — Parallel split phase: Phase 1 sort từng chunk độc lập nhau — hoàn toàn parallelizable. Dùng nhiều thread sort song song. Phase 2 vẫn sequential (single pass merge). Speedup Phase 1 gần tuyến tính với số core.

LeetCode liên quan

• 23. Merge k Sorted Lists — cùng k-way merge pattern, dữ liệu in-memory thay vì file.
• 295. Find Median from Data Stream — heap-based streaming processing.
• 692. Top K Frequent Words — min-heap top-K (đã gặp Module 3 lesson 10).

Applied note

PostgreSQL ORDER BY với work_mem: khi sort vượt work_mem (mặc định 4MB), Postgres dùng tuplesort — chia thành sorted run trên disk, k-way merge cuối. Cùng pattern bài này, ở production scale.

Hadoop MapReduce shuffle phase: sau map, records sort theo key trước khi gửi đến reducer. Mỗi mapper sort partition của mình (Phase 1), reducer fetch và k-way merge các sorted partition (Phase 2) — distributed external sort.

Apache Lucene segment merge: khi index flush memory buffer ra disk, tạo segment (sorted term list). Background merger dùng k-way merge ghép các segment nhỏ thành segment lớn — cùng cấu trúc external merge sort.

Unix sort -S 1G huge_file.txt: flag -S chỉ định buffer size, tương đương chunkSize. Khi buffer đầy, sort ghi chunk ra temp file, sau đó k-way merge. GNU sort còn hỗ trợ --parallel cho Phase 1.

Cross-link: Module 2 lesson 03 (Merge sort — k-way merge concept), Thuật toán Ứng dụng — Module 3 (Big data & streaming — external algorithms ở distributed scale).

Điều bạn vừa làm được

• Hiểu external merge sort hai phase: split+sort chunk trong RAM, k-way merge bằng min-heap.
• Hiểu tại sao min-heap trong Phase 2 chỉ giữ K integer (K = số chunk) — memory bounded bất kể kích thước file.
• Biết ba pitfall: file handle leak khi không dùng finally, charset mismatch, quên flush writer.
• Nhận ra pattern này là nền tảng của PostgreSQL tuplesort, Hadoop shuffle, Lucene segment merge, và Unix sort.
• Thấy hướng optimize thực tế: tăng chunkSize (ít chunk, ít merge pass), parallel Phase 1, compress chunk, multi-pass khi N chunk lớn.

Bài tiếp theo: Case Study: TimSort + Redis ZSET