External merge sort khi dữ liệu vượt RAM
Tính số đoạn, lượt trộn, vùng đệm và I/O, rồi công bố đầu ra hoàn chỉnh qua tệp tạm để lỗi giữa chừng không làm mất kết quả cũ.
External merge sort xử lý tệp lớn hơn RAM bằng cách tạo các đoạn đã sắp xếp vừa bộ nhớ, rồi trộn chúng bằng các vùng đệm nhỏ. Với kỹ sư xử lý tệp xuất dữ liệu hoặc kho nhật ký, các câu hỏi chính là một lần trộn chứa được bao nhiêu đoạn, dữ liệu cần đi qua bao nhiêu lượt đầy đủ và còn bao nhiêu đĩa cho dữ liệu tạm.
Xét bài toán kích thước minh họa: tệp 64 GiB, ngân sách bộ nhớ 256 MiB và mỗi đoạn đầu chứa 128 MiB bản ghi đã giải mã có kích thước cố định. Phần bộ nhớ còn lại dành cho vùng đệm vào, chi phí sắp xếp và thông tin quản lý. Đây là mô hình lập kế hoạch, không phải kết quả đo thông lượng hay khẳng định rằng 128 MiB đối tượng Python tùy ý chỉ chiếm 128 MiB RAM.
Tạo các đoạn với ngân sách bộ nhớ rõ ràng
Đọc một khối có giới hạn, sắp xếp trong bộ nhớ rồi ghi thành một đoạn đã có thứ tự. Lặp lại đến hết đầu vào. Với biểu diễn kích thước cố định đơn giản hóa, 64 GiB bằng 65.536 MiB, nên các đoạn 128 MiB tạo thành 512 đoạn ban đầu.
Giới hạn khối phải áp dụng lên biểu diễn thực sự được giữ trong bộ nhớ. Phân tích một hàng văn bản ngắn thành chuỗi, từ điển và đối tượng số nguyên có thể dùng nhiều bộ nhớ hơn số byte nguồn. Cài đặt thực tế cần đo hoặc giới hạn bộ nhớ dành cho biểu diễn đó, đồng thời dành chỗ cho bộ nhớ tạm của thuật toán sắp xếp.
Mọi đoạn phải dùng cùng định nghĩa khóa, mã hóa và quy tắc khi khóa bằng nhau. Nếu một đoạn sắp thời gian như văn bản còn đoạn khác dùng giá trị số, phép trộn đúng cũng không sửa được sự thiếu nhất quán. Hãy lưu phiên bản định dạng và khóa trong thông tin công việc để quá trình khôi phục không trộn nhầm các đoạn không tương thích.
Chọn số đoạn trộn từ vùng đệm và số tệp mở
Phép trộn k đoạn giữ một bản ghi kế tiếp từ mỗi đoạn trong min heap. Lấy ứng viên nhỏ nhất, ghi nó ra rồi thay bằng bản ghi tiếp theo của cùng đoạn. Đọc theo vùng đệm phân bổ chi phí truy cập lưu trữ cho nhiều bản ghi thay vì phải đọc vật lý từng bản ghi.
Với 32 đoạn đầu vào và vùng đệm 4 MiB cho mỗi đoạn, các vùng đệm vào chiếm 128 MiB. Thêm vùng đệm ra 4 MiB nâng tổng phụ lên 132 MiB, còn chỗ trong ngân sách 256 MiB cho mục heap, bản ghi đã giải mã, chi phí môi trường chạy và hệ điều hành. Số đoạn an toàn cụ thể còn phụ thuộc giới hạn bộ mô tả tệp và kích thước bản ghi.
heapq.merge của Python cung cấp phần iterator có thứ tự cho các đầu vào đã sắp xếp. Hàm nhỏ dưới đây minh họa bước trộn bằng mỗi dòng một số nguyên; đây không phải biểu diễn kích thước cố định dùng trong phép tính dung lượng ở trên.
from contextlib import ExitStack
from heapq import merge
from pathlib import Path
def merge_integer_runs(paths, destination):
source_paths = [Path(path).resolve() for path in paths]
target = Path(destination).resolve()
if target in source_paths or (target.exists() and
any(target.samefile(path) for path in source_paths)):
raise ValueError('destination must differ from all input runs')
with ExitStack() as stack:
files = [stack.enter_context(path.open()) for path in source_paths]
streams = [(int(line) for line in file) for file in files]
output = stack.enter_context(target.open('w'))
for value in merge(*streams):
output.write(f'{value}\n')Kiểm tra đích cũng từ chối một đường dẫn hard link có sẵn trỏ tới cùng tệp đầu vào. Ngăn xếp quản lý ngữ cảnh đóng mọi tệp đã mở nếu việc phân tích hoặc ghi thất bại. Hàm giả sử các đoạn đầu vào đều đã có thứ tự và bên gọi giới hạn số đường dẫn. Một công việc đầy đủ nên ghi vào đường dẫn tạm và chỉ công bố đầu ra sau khi hoàn tất thành công.
Đếm các lượt đọc và ghi đầy đủ
Trộn 512 đoạn theo nhóm 32 tạo ra 16 đoạn lớn hơn. Lượt thứ hai kết hợp 16 đoạn đó thành kết quả cuối. Như vậy có hai lượt trộn sau bước tạo đoạn ban đầu. Mỗi lượt đầy đủ đọc và ghi xấp xỉ toàn bộ tập 64 GiB nếu kích thước biểu diễn không đổi.
Bước tạo đoạn truyền khoảng 128 GiB: đọc 64 GiB và ghi 64 GiB. Mỗi lượt trong hai lượt trộn truyền thêm 128 GiB, tổng cộng 384 GiB theo mô hình đơn giản này. Nén, siêu dữ liệu hệ thống tệp, bộ nhớ đệm và thay đổi định dạng có thể làm I/O vật lý khác đi, nên đây là ước lượng lượng truyền của thuật toán.
Tăng số đoạn trộn cùng lúc có thể bỏ được một lượt, nhưng vùng đệm từng đoạn quá nhỏ có thể gây I/O kém và mở quá nhiều tệp. Quyết định không chỉ là tăng số đoạn lên tối đa. Hãy đo đường đọc, ghi và phân tích thực tế sau khi tính được phân bổ bộ nhớ khả thi.
Giữ dữ liệu tạm có thể khôi phục
Đầu vào gốc, các đoạn hiện tại và thế hệ tiếp theo đang ghi dở có thể cùng tồn tại. Trong ví dụ, giữ đủ cả ba tập có thể tiến gần 192 GiB trước khi dọn, chưa tính siêu dữ liệu và chi phí hệ thống tệp. Chỉ xóa đoạn nguồn sau khi bản thay thế đã được lưu bền vững giúp giảm rủi ro nhưng đòi hỏi đủ chỗ để hoàn tất mỗi nhóm trộn.
Danh sách quản lý đoạn có thể ghi đường dẫn, số bản ghi, phiên bản khóa và trạng thái hoàn tất. Chỉ đánh dấu hoàn tất sau khi đóng và kiểm tra đoạn. Nếu tiến trình dừng giữa lần trộn, hãy loại bỏ hoặc tiếp tục đầu ra chưa hoàn chỉnh theo khả năng của định dạng, thay vì coi nó là đoạn đã sắp xếp hợp lệ.
Tính ổn định cũng cần chính sách tường minh. Giữ thứ tự nguồn của các khóa bằng nhau bằng số thứ tự gốc hoặc quy tắc ưu tiên đoạn nhất quán qua mọi thế hệ trộn. Heap dùng tên tệp tình cờ để phân xử không tự động bảo toàn thứ tự đầu vào.
Đánh giá lưu lượng lưu trữ cùng số phép so sánh
Phép trộn dựa trên heap thực hiện O(log k) công việc heap cho mỗi bản ghi đầu ra, còn truyền dữ liệu có đệm phần lớn là tuần tự. Cấu trúc merge sort vẫn áp dụng, nhưng ranh giới bộ nhớ làm thay đổi loại chi phí chi phối. Thuật toán ít so sánh hơn có thể thua nếu liên tục đọc các vị trí đĩa rải rác.
Hệ cơ sở dữ liệu có các giới hạn liên quan. work_mem của PostgreSQL điều khiển bộ nhớ của một số thao tác truy vấn trước khi dùng tệp tạm. Tài liệu cảnh báo nhiều thao tác và phiên làm việc có thể dùng những hạn mức riêng. Vì vậy, ngân sách cho một phép sắp xếp không phải giới hạn bộ nhớ của cả máy.
Hãy kiểm thử trộn đoạn rỗng, số âm, giá trị trùng qua ranh giới đoạn và một dòng cố ý sai định dạng. So số bản ghi cuối và thứ tự với kết quả trong bộ nhớ đáng tin cậy trên tập nhỏ. Giữ các kiểm tra tính đúng này tách khỏi thí nghiệm tệp lớn, nơi bộ nhớ cực đại, byte truyền, dung lượng tạm và thời gian trả lời các câu hỏi vận hành khác nhau.
Công bố kết quả mà không lộ tệp đang ghi dở
Hàm trộn nhỏ mở đích để ghi trước khi phân tích hết mọi bản ghi. Nếu một dòng sau đó sai định dạng, đích có thể đã chứa kết quả dở dang. Muốn giữ kết quả hoàn chỉnh cũ cần bước công bố riêng: trộn vào tệp tạm trong thư mục đích rồi chỉ thay đích sau khi trộn thành công.
import os
from tempfile import NamedTemporaryFile
def publish_integer_merge(paths, destination):
source_paths = [Path(path).resolve() for path in paths]
target = Path(destination).resolve()
if target in source_paths or (target.exists() and
any(target.samefile(path) for path in source_paths)):
raise ValueError('destination must differ from all input runs')
with NamedTemporaryFile(
dir=target.parent, prefix='.merge-', suffix='.tmp', delete=False,
) as temporary:
temporary_path = Path(temporary.name)
try:
merge_integer_runs(source_paths, temporary_path)
os.replace(temporary_path, target)
finally:
temporary_path.unlink(missing_ok=True)Tệp tạm được đóng trước khi hàm trộn mở lại, nên không phụ thuộc vào khả năng mở lại một tệp tạm có tên vẫn đang mở. Đặt nó cùng thư mục đích giữ thao tác thay thế trong cùng hệ thống tệp. Python mô tả os.replace là phép đổi tên nguyên tử khi thành công và mô tả vòng đời tệp có tên trong tempfile.
Ở đây, nguyên tử nghĩa là người đọc mở đích thấy tệp hoàn chỉnh cũ hoặc tệp hoàn chỉnh mới, thay vì đầu ra đang lớn dần. Người đọc đã mở tệp cũ có thể tiếp tục truy cập nó theo ngữ nghĩa handle của hệ điều hành. Khả năng hiển thị nguyên tử chưa phải bảo đảm bền vững đầy đủ khi máy gặp sự cố: hàm không đồng bộ nội dung tệp hoặc siêu dữ liệu thư mục xuống lưu trữ bền vững. Thiết kế khôi phục cần bổ sung đồng bộ và giao thức quản lý đoạn phù hợp nền tảng.
Kiểm thử lỗi nhỏ nên bắt đầu với hai đoạn đã sắp xếp và đích chứa kết quả cũ dễ nhận biết. Đặt một dòng sai ở gần cuối một đoạn để lỗi xảy ra sau khi vài bản ghi hợp lệ đã được ghi vào tệp tạm. Lời gọi phải báo lỗi, đích vẫn chứa kết quả cũ và tệp tạm phải được dọn. Sau đó sửa dòng sai và xác nhận cùng đường dẫn đích trở thành kết quả trộn đầy đủ có thứ tự.
Bước dọn cuối chạy dù trộn, thay thế hay lần công bố thất bại. Sau khi thay thế thành công, đường dẫn tạm không còn tồn tại nên việc cho phép đường dẫn vắng mặt là có chủ ý. Tiến trình bị kết thúc đột ngột vẫn có thể để lại tệp tạm mồ côi vì mã dọn Python chưa chắc được chạy; công việc đầy đủ cần cách nhận diện và xóa các đoạn dở cũ khi khởi động lại.
Hàm bọc giả sử các đoạn đầu vào không đổi và vẫn có thứ tự trong lúc đọc. Nó cũng giả sử công việc kiểm soát đường dẫn nguồn và đích. Phép thay thế không phải khóa điều phối hai bên ghi: các công việc đồng thời nhắm cùng đích cần cơ chế riêng nếu không được phép ghi đè kết quả hoàn chỉnh của nhau.
Để luyện tập, thêm bước công bố này vào kế hoạch trộn hai thế hệ và mô phỏng lỗi sau từng nhóm hoàn tất. Ghi đoạn cũ nào còn cần và đoạn mới nào đã xong. Khôi phục nên dựa trên những trạng thái đã ghi, không chỉ việc tên tệp tồn tại. Bài tập nối trường hợp lỗi phân tích nhỏ với các quy tắc về thế hệ và dung lượng tạm của phép sắp xếp ngoài lớn hơn.