External merge sort — sắp xếp vượt RAM
Chia dữ liệu thành chunk vừa RAM, sort từng chunk, rồi k-way merge. Nền của ORDER BY trên database và shuffle MapReduce.
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. Đâ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), và mỗi khi hệ xử lý dữ liệu lớn dồn kết quả lại (shuffle của MapReduce: mô hình xử lý chia việc cho nhiều máy, rồi bước shuffle gom kết quả theo khoá về đúng máy cần).
Bạn vừa nhận việc sắp xếp một file log 100 GB trên máy chỉ có 8 GB RAM. Gọi Arrays.sort() thì chương trình tắt ngay với OutOfMemoryError, vì không thể nhét hết dữ liệu vào bàn làm việc cùng lúc. Bài toán này gọi là external sort: phải mượn ổ đĩa làm chỗ để tạm.
1. Trực giác: sắp một chồng hồ sơ quá lớn
Bạn có một chồng hồ sơ khổng lồ cần sắp theo tên, nhưng bàn chỉ để vừa một phần nhỏ. Cách tự nhiên gồm ba bước:
- 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.
- 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.
- 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.
Đây là ví dụ của phân rã bài toán. Bảng dưới ánh xạ việc đời thường sang tên kỹ thuật:
| Việc đời thường | Khái niệm trong thuật toán |
|---|---|
| Một xấp hồ sơ vừa bàn | Một "chunk" (xấp dữ liệu nhỏ vừa bộ nhớ) |
| Xấp đã sắp, để qua bên | Một "run" (xấp đã sắp ghi ra đĩa) |
| Trộn nhiều cọc bài đã sắp cùng lúc | "k-way merge" (trộn k xấp một lúc) |
| Nhặt lá nhỏ nhất ở đỉnh các cọc | Dùng "min-heap" (cấu trúc luôn cho ra phần tử nhỏ nhất) |
Hai từ cần nhớ thêm: min-heap là cái rổ thông minh, bỏ vài phần tử vào rồi hỏi "cái nhỏ nhất đâu?" thì nó đưa ra ngay; pass (lượt) là một lần đọc/ghi qua toàn bộ dữ liệu, mà 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ể.
Thứ chậm ở đây không phải CPU mà là đọc/ghi ổ đĩa. Đọc liền mạch (tuần tự) nhanh hơn đọc nhảy chỗ (ngẫu nhiên) hàng chục tới hàng trăm lần trên ổ cứng quay (HDD). Vì vậy thuật toán tốt là thuật toán đọc qua toàn bộ dữ liệu càng ít lượt càng tốt, chứ không phải tiết kiệm phép so sánh.
Bốn ký hiệu dùng ở phần công thức:
| Ký hiệu | Nghĩa đời thường |
|---|---|
N | tổng số bản ghi cần sắp (ví dụ 10 tỷ dòng) |
M | bộ nhớ chứa được tối đa bao nhiêu bản ghi (ví dụ 800 triệu) |
k | trộn bao nhiêu xấp cùng một lúc ở bước trộn |
R = ceil(N/M) | số xấp sinh ra sau bước 1 (chia hết đống lớn thành từng xấp) |
All-Access Pass
Phần còn lại của bài dành cho All-Access Pass
Bạn vừa đọc phần xem trước. Hai bài đầu của mỗi khoá luôn đọc trọn miễn phí.
- Đọc trọn mọi bài trong 6 khoá System Design và dữ liệu phân tán
- AI Mentor trả lời theo toàn bộ nội dung bài
- Trả một lần, không tự gia hạn, không tự trừ tiền
Trọn đời
1.690.000 ₫
Trả một lần, dùng mãi mãi
Gói năm
699.000 ₫
365 ngày · ≈ 58.000 ₫/tháng
Thanh toán bằng thẻ Visa/Master/JCB qua Polar. Xem bảng giá
Big data & streaming: tổng quan khi RAM không đủ
Bài tiếpReservoir sampling — mẫu ngẫu nhiên từ stream
Bài này có giúp bạn hiểu bản chất không?
Bài này đáng gửi cho bạn học cùng?
Copy link đã gắn nguồn — dán group, chat, hoặc LinkedIn.
Thảo luận & góp ý
Hỏi đáp về bài này