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

TL;DR: Bạn cần sắp một đống dữ liệu khổng lồ (100 GB) nhưng máy chỉ chứa được 8 GB cùng lúc — như sắp một chồng hồ sơ quá lớn, không để hết lên bàn được. Cách làm: chia đống lớn thành từng xấp nhỏ vừa bàn, sắp gọn từng xấp một, rồi trộn các xấp đã sắp lại thành một đống sắp hoàn chỉnh. Mẹo trộn nhanh: cứ nhặt tờ nhỏ nhất đang nằm trên đỉnh các xấp. Đây là external merge sort — chạy mỗi khi cơ sở dữ liệu sắp xếp một bảng lớn (ORDER BY trong Postgres), mỗi khi hệ xử lý dữ liệu lớn dồn kết quả lại (shuffle của MapReduce), hay khi Kafka gộp log.

Bạn vừa nhận việc: sắp xếp một file log 100 GB từ server. Máy chỉ có 8 GB bộ nhớ (RAM). Gọi hàm sắp xếp có sẵn (Arrays.sort())? Chương trình tắt ngay với lỗi hết bộ nhớ (OutOfMemoryError) — vì không thể nhét hết dữ liệu vào bàn làm việc cùng lúc. Đây là bài toán sắp xếp khi dữ liệu vượt bộ nhớ (external sort): phải mượn ổ đĩa làm chỗ để tạm.

Cách làm này không phải chuyện hiếm gặp: mỗi lần Postgres sắp xếp một bảng lớn (ORDER BY mà không đủ bộ nhớ), mỗi lần MapReduce gom dữ liệu từ nhiều máy lại, mỗi lần Kafka gộp log — đều chạy một biến thể của thuật toán này.

1. Trực giác — sắp một chồng hồ sơ quá lớn

Trước khi đụng tới công thức, hãy hình dung một việc đời thường. Bạn có một chồng hồ sơ khổng lồ cần sắp theo thứ tự tên, nhưng bàn làm việc chỉ để vừa một phần nhỏ. Bạn làm gì?

Cách tự nhiên gồm ba bước:

1. Chia thành từng xấp vừa bàn. Lấy mỗi lần một xấp đủ để đặt lên bàn.
2. Sắp gọn từng xấp. Với mỗi xấp đã trên bàn, sắp theo thứ tự rồi để qua một bên.
3. Trộn các xấp đã sắp. Đặt các xấp đã sắp cạnh nhau, rồi cứ nhặt tờ có tên đứng trước nhất đang nằm trên đỉnh mỗi xấp, đặt vào chồng kết quả. Lặp đến khi hết.

Bước 3 chính là mẹo trộn nhiều cọc bài đã sắp: bạn không cần nhìn cả cọc, chỉ cần nhìn lá trên đỉnh mỗi cọc, nhặt lá nhỏ nhất, rồi lật lá kế tiếp lên.

Thuật toán làm đúng ba bước này trên dữ liệu. Bảng dưới ánh xạ việc đời thường sang tên kỹ thuật (đặt trong ngoặc để gặp lại sau):

Vài từ ngữ sẽ dùng suốt bài:

• chunk = một xấp dữ liệu nhỏ vừa bộ nhớ (đọc vào để sắp).
• run = một xấp đã được sắp xong và ghi ra đĩa.
• min-heap = một cái rổ thông minh: bạn bỏ vài phần tử vào, hỏi "cái nhỏ nhất đâu?" thì nó đưa ra ngay, không cần dò cả rổ.
• pass (lượt) = một lần đọc qua toàn bộ dữ liệu và ghi kết quả ra. Mỗi lượt đọc/ghi đĩa rất tốn thời gian, nên mục tiêu là ít lượt nhất có thể.

Bốn ký hiệu sẽ gặp ở phần công thức (chỉ cần nhớ ý nghĩa, chưa cần dùng ngay):

2. Bước 1 — chia thành từng xấp đã sắp (tạo sorted run)

Đọc một xấp dữ liệu vừa bộ nhớ vào RAM, sắp gọn ngay trong bộ nhớ (dùng bất kỳ cách sắp xếp quen thuộc nào), rồi ghi xấp đã sắp đó ra đĩa thành một "run". Lặp cho đến khi đọc hết đầu vào.

function createRuns(inputFile, M):
    runs <- []                              -- danh sách các xấp đã sắp trên đĩa
    while inputFile chưa hết:
        chunk <- đọc M bản ghi từ inputFile -- một xấp vừa bộ nhớ
        sort(chunk)                         -- sắp gọn ngay trong bộ nhớ
        runFile <- ghi chunk ra đĩa
        runs.append(runFile)
    return runs
// (phần chi phí — xem mục 4): đọc qua toàn bộ 1 lượt + ghi 1 lượt = 2N lần I/O

Với 100 GB dữ liệu và 8 GB bộ nhớ: chia thành ceil(100/8) = 13 xấp (run), mỗi xấp 8 GB đã sắp xong.

3. Bước 2 — trộn các xấp đã sắp (k-way merge)

Giờ có R xấp đã sắp nằm trên đĩa. Cần trộn chúng thành một đống sắp hoàn chỉnh. Cách ngây thơ là trộn từng cặp một (như khi học merge sort) — nhưng cách đó phải đọc đi đọc lại toàn bộ dữ liệu nhiều vòng. Thay vào đó, ta trộn k xấp cùng một lúc (gọi là "k-way merge") để giảm số vòng đọc đĩa.

Mẹo trộn nhanh chính là việc nhặt lá bài: nhìn tờ trên đỉnh mỗi xấp, nhặt tờ nhỏ nhất, ghi ra kết quả, rồi lật tờ kế tiếp của xấp vừa nhặt lên. Để khỏi phải dò qua từng đỉnh mỗi lần, ta dùng min-heap — cái rổ thông minh luôn đưa ra phần tử nhỏ nhất. Mỗi bước: lấy phần tử nhỏ nhất ra khỏi rổ (đó cũng là phần tử nhỏ nhất của toàn bộ dữ liệu còn lại), ghi vào kết quả, rồi bỏ tờ kế tiếp của xấp đó vào rổ.

function kWayMerge(runs[0..k-1], outputFile):
    H <- MinHeap()
    for i từ 0 đến k-1:                    -- bỏ tờ trên đỉnh mỗi xấp vào rổ
        if runs[i] không rỗng:
            H.push((runs[i].readNext(), i)) -- (giá trị, xấp số mấy)

    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))  -- lật tờ kế của xấp đó
// (phần chi phí — xem mục 4): rổ chỉ giữ k phần tử nên rất nhẹ bộ nhớ

Vì sao mẹo này luôn cho ra đúng thứ tự? Tại mọi thời điểm, cái rổ giữ đúng k ứng viên — một tờ từ đỉnh mỗi xấp. Tờ nhỏ nhất trong rổ là tờ nhỏ nhất trong k ứng viên đó; mà vì mỗi xấp đã sắp sẵn, tờ đó cũng là tờ nhỏ nhất trong tất cả dữ liệu còn lại. Cứ thế, mỗi lần lấy ra đều là phần tử đúng vị trí kế tiếp (lập luận chặt chẽ ở phần tự kiểm tra cuối bài).

Câu hỏi hay tự đặt ở đây: trộn 13 xấp 8 GB thì chẳng phải cần 104 GB bộ nhớ à? Không — dữ liệu vẫn nằm trên đĩa và chỉ chảy qua bộ nhớ theo dòng. Cái rổ giữ đúng 13 tờ, mỗi xấp một tờ trên đỉnh; đó là chỗ duy nhất trong sơ đồ có kích thước không phụ thuộc con số 100 GB.

3.1 Chạy thử trộn 3 xấp (k=3)

3 xấp đã sắp:

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

Kết quả cuối: 1 2 3 4 5 6 7 8 9 — đúng thứ tự.

4. Phần chi phí — vì sao trộn nhiều xấp một lúc thì nhanh?

Trực giác trước: mỗi vòng đọc qua toàn bộ dữ liệu trên đĩa rất tốn thời gian. Nếu mỗi lần chỉ trộn được 2 xấp, ta phải đọc đi đọc lại nhiều vòng mới gộp xong; trộn được nhiều xấp cùng lúc thì ít vòng hơn. Giờ tới phần con số để thấy tiết kiệm bao nhiêu.

Đếm số lượt (mỗi lượt = một lần đọc/ghi qua toàn bộ N bản ghi):

Tổng số lượt = 1 (bước 1: tạo xấp) + ceil(log_k(R))   -- R = ceil(N/M)

Với N=100 GB, M=8 GB → R=13 xấp:

Khi k=13 (trộn tất cả 13 xấp trong một vòng), chỉ cần 2 lượt tổng cộng — tiết kiệm khoảng 60% lượng đọc/ghi đĩa so với k=2. Nhưng trộn càng nhiều xấp một lúc thì càng cần nhiều vùng nhớ đệm (buffer): mỗi xấp đang trộn cần một vùng đệm riêng trong RAM. Vì thế k không thể lớn vô hạn — nó bị giới hạn bởi lượng RAM có sẵn.

Mỗi ô là một lần đọc và ghi qua trọn 100 GB — nên bớt được một ô là bớt 200 GB đọc/ghi. Trộn nhiều xấp một lúc không làm mỗi lượt nhanh hơn, nó làm bớt lượt.

5. Gặp cách làm này ở đâu trong thực tế?

Cơ sở dữ liệu Postgres: khi bạn yêu cầu sắp xếp một bảng lớn (ORDER BY) mà bộ nhớ cho phép (work_mem) không đủ, Postgres tự chia thành các xấp ghi ra đĩa rồi trộn lại — đúng thuật toán này. Lệnh chẩn đoán EXPLAIN ANALYZE hiện dòng Sort Method: external merge khi điều này xảy ra (gọi là "tràn ra đĩa", spill to disk).

MapReduce shuffle: sau bước Map, mỗi máy sắp output của mình (đây là bước 1); máy Reduce nhận nhiều xấp đã sắp từ nhiều máy rồi trộn lại (bước 2). Đây chính là lý do bước "shuffle" của MapReduce tốn kém — nó là external sort trải trên cả cụm máy.

Lọc trùng dữ liệu lớn (dedup): thay vì dùng bảng tra để tìm phần tử khác nhau, các hệ lớn (Spark distinct(), Flink) sắp dữ liệu trước rồi quét một lượt loại bản trùng cạnh nhau — quét một lượt sau khi đã sắp thì rẻ hơn dùng bảng tra khi dữ liệu vượt bộ nhớ.

6. Những chỗ dễ sai

Sai 1 — Trộn quá nhiều xấp một lúc, mỗi xấp đệm quá nhỏ

-- SAI: trộn k = 1000 xấp một lúc, mỗi vùng đệm chỉ còn 8 KB
-- -> mỗi lần lấy tờ kế chỉ đọc 8 KB, đọc đĩa nhảy chỗ liên tục (ngẫu nhiên)
-- -> còn chậm hơn trộn ít xấp hơn

-- ĐÚNG: chọn k = bộ nhớ chia cho kích thước đệm mỗi xấp
-- Mỗi xấp có vùng đệm đủ lớn để đọc liền mạch (tuần tự)
-- Thực tế Postgres/DBMS giới hạn k khoảng 500 vì mở quá nhiều
-- file cùng lúc cũng tốn tài nguyên hệ điều hành

Sai 2 — Quên đọc trước (double buffering) khiến CPU ngồi chờ đĩa

-- SAI: đọc một đệm -> xử lý -> đọc đệm kế -> xử lý (CPU phải chờ mỗi lần đọc)

-- ĐÚNG: dùng hai vùng đệm luân phiên — trong khi CPU xử lý đệm A,
-- ổ đĩa đã đọc sẵn đệm B (đọc trước, prefetch); xong thì đổi vai
-- Tăng tốc khoảng 2 lần trên ổ đĩa thông thường

Sai 3 — Quên xấp cuối có thể nhỏ hơn các xấp khác

-- SAI: tưởng mọi xấp đều đúng M bản ghi
-- -> nếu N không chia hết cho M, xấp cuối nhỏ hơn
-- -> lật tờ kế khi xấp đã hết -> lỗi vượt giới hạn

-- ĐÚNG: luôn kiểm tra "xấp còn tờ nào không" trước khi lật tờ kế
-- (đã có trong pseudocode kWayMerge ở trên: "if runs[runIdx] không rỗng")

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

• Heap & heapsort: min-heap (cái rổ luôn cho ra phần tử nhỏ nhất) là cốt lõi của bước trộn. Mỗi lần bỏ một tờ vào rổ hay lấy tờ nhỏ nhất ra đều chậm theo số xấp đang trộn (gần như tức thời với vài chục xấp). Đó là lý do bước trộn nhanh. Đọc bài đó trước nếu chưa quen min-heap.
• Merge sort: external sort là phiên bản mở rộng (generalisation) của merge sort khi dữ liệu phải để trên đĩa. Bước 1 (tạo xấp đã sắp) giống trường hợp nhỏ nhất (base case) của merge sort; bước 2 (trộn) giống vòng trộn của nó. Khác ở chỗ: merge sort gốc gọi đệ quy và làm hết trong bộ nhớ, còn external sort làm theo vòng lặp, trộn nhiều xấp một lúc, và được thiết kế để đọc/ghi đĩa ít nhất có thể.
• Amortized analysis: cách tính "số lượt × 2 lần đọc/ghi mỗi lượt" là một kiểu phân tích chi phí trung bình (amortized), nhưng nhìn theo số lần đọc/ghi đĩa thay vì số phép tính của CPU (bộ xử lý).
• Count-Min Sketch: cùng chủ đề dữ liệu lớn dạng dòng chảy (streaming). Khi sắp xếp quá đắt (dữ liệu chảy về vô tận, không bao giờ "hết"), người ta dùng cấu trúc đếm gần đúng (probabilistic) thay thế. Đọc chéo để hiểu sự đánh đổi giữa "chính xác tuyệt đối" và "gần đúng nhưng rẻ".
• Case study Redis & Kafka: Kafka gộp log (log compaction) dùng external sort để trộn các đoạn file lại — đọc case study để thấy thuật toán này chạy trong một hệ thống thật.

📚 Deep Dive

Tóm tắt

• Chia xấp nhỏ vừa bộ nhớ, sắp từng xấp (bước 1: 1 lượt đọc/ghi), rồi trộn bằng min-heap nhặt tờ nhỏ nhất ở đỉnh từng xấp.
• Trộn nhiều xấp cùng lúc thì ít vòng đọc đĩa hơn, nhưng mỗi xấp cần vùng đệm riêng — k bị giới hạn bởi RAM có sẵn.
• Postgres hiện Sort Method: external merge Disk khi ORDER BY không đủ bộ nhớ; bước shuffle của MapReduce là external sort trải trên cả cụm máy.
• Double buffering giúp CPU không chờ đĩa (~2 lần nhanh hơn); replacement selection làm mỗi xấp trung bình dài gấp đôi, ít xấp hơn (chi tiết ở Deep Dive).

Tự kiểm tra

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