Tối ưu hóa hiệu năng IO cho xử lý PDF quy mô Gigabyte

Bản đọc hữu ích đầu tiên của một trình phân tích cú pháp PDF nằm ở sai đầu của tệp. Định dạng này đặt con trỏ startxref vào những byte cuối cùng, do đó việc xử lý một kho lưu trữ 1,8 GB bắt đầu bằng một lệnh seek (tìm kiếm) đến phần đuôi, đọc một kilobyte, sau đó nhảy đến bất cứ nơi nào mà bảng tham chiếu chéo nói rằng catalog của tài liệu đang sống. Từ đó, quá trình phân tích cú pháp là một cuộc đi bộ ngẫu nhiên trên toàn bộ dải byte. Mọi thứ mà IO có bộ đệm (buffered IO) làm tốt — đọc trước tuần tự phía sau con trỏ tệp — đều nhắm vào một khối lượng công việc mà PDF không có

Phiên bản đầu tiên của bài viết này tuyên bố rằng tệp được ánh xạ vào bộ nhớ (memory-mapped file) giải quyết lỗi hết bộ nhớ 32-bit mà TMemoryStream gặp phải trên đầu vào 2 GB. Tuyên bố đó đã sai, và cách mà nó sai lại chỉ ra bản sửa lỗi thực sự: một cửa sổ ánh xạ trượt (sliding mapping window). Những gì tiếp theo là mô hình truy cập, câu chuyện 32-bit được sửa chữa với một trình ánh xạ dạng cửa sổ có thể biên dịch, và số học lệnh gọi hệ thống (syscall) trên một tệp kiểm thử 1,8 GB, có 300.000 đối tượng

Tại sao bố cục PDF đánh bại các bản đọc có bộ đệm

Ba sự thật về cấu trúc định hình mô hình IO. Thứ nhất, việc điều hướng được điều khiển bằng độ lệch (offset-driven): bảng tham chiếu chéo ánh xạ mọi số đối tượng tới một vị trí byte tuyệt đối, và không gì bắt buộc các vị trí đó phải được sắp xếp. Sau nhiều năm cập nhật gia tăng, đối tượng 4102 có thể nằm ở độ lệch 1,6 GB trong khi đối tượng 4103 nằm ở 30 KB. Một vòng lặp TFileStream biến mọi lần tìm nạp thành một Seek cộng với một Read, hai lần chuyển tiếp kernel (nhân hệ điều hành), với một bộ đệm không đóng góp được gì vì lần tìm nạp tiếp theo cách đó hàng trăm megabyte

Thứ hai, các luồng đối tượng (ISO 32000-1 §7.5.7) đóng gói hàng chục hoặc hàng trăm từ điển nhỏ vào một vùng chứa được nén deflate. Việc tìm nạp một từ điển trang 300 byte có thể có nghĩa là đọc và phình to (inflate) một cụm (cluster) 100 KB. Mặt trái: các đối tượng được viết cùng nhau có xu hướng được đọc cùng nhau, do đó một bộ đệm được định cỡ bằng cụm sẽ phục vụ hàng tá lần tìm nạp tiếp theo một cách miễn phí — một tính quy luật có thể khai thác nhất trong định dạng

Thứ ba, tuyến tính hóa. Một tệp được tuyến tính hóa tải trước trang đầu tiên và bảng gợi ý (hint table) để các thực thể tiêu thụ có thể đọc nó từ trước ra sau. Các kho lưu trữ hàng gigabyte hầu như không bao giờ được tuyến tính hóa: tuyến tính hóa bị phá hủy bởi chính các bản cập nhật gia tăng và thao tác gộp (merge) đã làm cho tệp trở nên lớn. Hãy lập kế hoạch cho trường hợp thù địch: những bước nhảy xa, không có trật tự, lối vào đi từ đuôi (tail-first)

Câu chuyện 32-bit, đã được sửa chữa

Một tiến trình Windows 32-bit có 2 GB không gian địa chỉ người dùng, và MapViewOfFile với số lượng byte bằng 0 sẽ yêu cầu một khoản đặt trước liên tục bằng với kích thước của tệp. Đối với một đầu vào 2 GB, việc đặt trước đó không thể thành công: sau tệp EXE, các DLL rải rác, và các ngăn xếp luồng (thread stacks), khối liên tục trống lớn nhất trong một tiến trình Delphi 32-bit thông thường nằm ở đâu đó giữa 700 MB và 1,4 GB. Lệnh gọi thất bại với ERROR_NOT_ENOUGH_MEMORY, chính bức tường mà TMemoryStream.LoadFromFile đâm phải, chỉ là chuyển từ RAM đã cam kết (committed RAM) sang đặt trước không gian địa chỉ. Ánh xạ toàn bộ tệp không phải là giải pháp trên 32-bit, chỉ là cùng một sự thất bại phía sau những cái tên API nghe có vẻ hay hơn

Bản sửa lỗi là tách biệt hai công việc mà việc ánh xạ thực hiện. CreateFileMapping tạo ra đối tượng phần (section object) và hoàn toàn không tốn không gian địa chỉ, bất kể kích thước tệp là bao nhiêu. Chỉ MapViewOfFile tiêu tốn không gian địa chỉ, và không có gì bắt buộc nó phải ánh xạ toàn bộ phần đó: nó lấy một độ lệch bắt đầu 64-bit và độ dài của dạng xem. Tạo phần này một lần, ánh xạ một dạng xem từ 64 đến 256 MB qua vùng đang được phân tích cú pháp, hủy ánh xạ (unmap) trước khi trượt đi tiếp: chi phí không gian địa chỉ là một cửa sổ, không phải một tệp. Một hạn chế: độ lệch dạng xem phải là bội số của SYSTEM_INFO.dwAllocationGranularity, trong thực tế là 64 KB, do đó một yêu cầu ở độ lệch 1.000.000 sẽ được làm tròn xuống 983.040 và con trỏ của người gọi được điều chỉnh về phía trước bằng với khoảng chênh lệch

Trình ánh xạ cửa sổ trượt trong Delphi

Lớp dưới đây bọc toàn bộ kỷ luật này: một đối tượng phần, một dạng xem trực tiếp, tái điều chỉnh độ chi tiết (granularity), và các lần đọc vượt qua ranh giới cửa sổ được xử lý bằng cách nới rộng một dạng xem đó thay vì khâu hai dạng xem

uses
  Winapi.Windows, System.SysUtils;

type
  TWindowedFileMapper = class
  private
    FFile: THandle;
    FMapping: THandle;
    FFileSize: Int64;
    FGranularity: DWORD;      // SYSTEM_INFO.dwAllocationGranularity
    FWindowSize: NativeUInt;  // default view size
    FViewBase: PByte;         // base of the current view (aligned)
    FViewOffset: Int64;       // file offset FViewBase corresponds to
    FViewSize: NativeUInt;    // bytes mapped in the current view
    procedure Unmap;
  public
    constructor Create(const FileName: string;
      WindowSize: NativeUInt = 64 * 1024 * 1024);
    destructor Destroy; override;
    function Map(Offset: Int64; Size: NativeUInt): PByte;
    procedure ReadBytes(Offset: Int64; var Buffer; Count: NativeUInt);
    property FileSize: Int64 read FFileSize;
  end;

constructor TWindowedFileMapper.Create(const FileName: string;
  WindowSize: NativeUInt);
var
  Info: TSystemInfo;
begin
  inherited Create;
  FFile := CreateFile(PChar(FileName), GENERIC_READ, FILE_SHARE_READ, nil,
    OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, 0);
  if FFile = INVALID_HANDLE_VALUE then
    RaiseLastOSError;
  if not GetFileSizeEx(FFile, FFileSize) then
    RaiseLastOSError;
  // The section object reserves no address space, whatever the file size
  FMapping := CreateFileMapping(FFile, nil, PAGE_READONLY, 0, 0, nil);
  if FMapping = 0 then
    RaiseLastOSError;
  GetSystemInfo(Info);
  FGranularity := Info.dwAllocationGranularity;  // 64 KB in practice
  FWindowSize := WindowSize;
end;

destructor TWindowedFileMapper.Destroy;
begin
  Unmap;
  if FMapping <> 0 then CloseHandle(FMapping);
  if FFile <> INVALID_HANDLE_VALUE then CloseHandle(FFile);
  inherited;
end;

procedure TWindowedFileMapper.Unmap;
begin
  if FViewBase <> nil then
  begin
    UnmapViewOfFile(FViewBase);
    FViewBase := nil;
    FViewSize := 0;
  end;
end;

function TWindowedFileMapper.Map(Offset: Int64; Size: NativeUInt): PByte;
var
  AlignedOffset: Int64;
  Delta, MapSize: NativeUInt;
begin
  if (Offset < 0) or (Offset + Int64(Size) > FFileSize) then
    raise ERangeError.CreateFmt(
      'Map request at %d for %d bytes is outside the file',
      [Offset, Int64(Size)]);

  // Fast path: the requested range already sits inside the live view
  if (FViewBase <> nil) and (Offset >= FViewOffset) and
     (Offset + Int64(Size) <= FViewOffset + Int64(FViewSize)) then
    Exit(FViewBase + NativeInt(Offset - FViewOffset));

  Unmap;  // slide: never hold two views at once

  // Views must start on an allocation-granularity boundary
  AlignedOffset := Offset - (Offset mod FGranularity);
  Delta := NativeUInt(Offset - AlignedOffset);

  MapSize := FWindowSize;
  if MapSize < Size + Delta then   // request straddles the window end:
    MapSize := Size + Delta;       // grow this one view to cover it
  if AlignedOffset + Int64(MapSize) > FFileSize then
    MapSize := NativeUInt(FFileSize - AlignedOffset);  // clamp at EOF

  FViewBase := MapViewOfFile(FMapping, FILE_MAP_READ,
    DWORD(AlignedOffset shr 32), DWORD(AlignedOffset and $FFFFFFFF),
    MapSize);
  if FViewBase = nil then
    RaiseLastOSError;

  FViewOffset := AlignedOffset;
  FViewSize := MapSize;
  Result := FViewBase + NativeInt(Delta);
end;

procedure TWindowedFileMapper.ReadBytes(Offset: Int64; var Buffer;
  Count: NativeUInt);
begin
  Move(Map(Offset, Count)^, Buffer, Count);
end;

Hai chi tiết gánh vác sức nặng. Đường dẫn nhanh (fast path) ở phần đầu của Map trả về một con trỏ không có chuyển tiếp kernel nào khi phạm vi được yêu cầu đã nằm bên trong dạng xem trực tiếp; nhờ tính năng phân cụm luồng đối tượng, đây là trường hợp phổ biến và là nơi tạo ra sự tiết kiệm. Và một yêu cầu kéo dài qua phần cuối của cửa sổ mặc định sẽ làm tăng MapSize cho một dạng xem đó thay vì khâu hai cái lại, điều này giữ cho ReadBytes là mã một dòng (one-liner) và người gọi không phải chịu các vòng lặp đọc một phần (partial-read loops)

Kích thước cửa sổ là một núm xoay khoan dung: ở 64 MB, một lần quét toàn bộ tệp 1,8 GB là 29 dạng xem, ở 256 MB là 8 nhưng mỗi khoản đặt trước khó đặt hơn trong một không gian 32-bit bị phân mảnh, và ở dưới khoảng 16 MB, các tệp nhảy nhiều sẽ ánh xạ lại (remap) đủ thường xuyên để nhận ra. Bất cứ nơi nào trong phạm vi 64 đến 256 MB, lưu lượng ánh xạ chỉ là nhiễu thống kê

Đếm số lượng syscall

Bây giờ là phần tính toán số học. Tệp kiểm thử: 1,8 GB, 300.000 đối tượng gián tiếp trung bình khoảng 600 byte payload. Một trình phân tích cú pháp mỗi-đối-tượng tìm nạp từng cái bằng SetFilePointerEx cộng với một lệnh ReadFile 4 KB: 600.000 lần chuyển tiếp kernel. Một syscall đọc được lưu cache sẽ thực hiện chuyến đi khứ hồi (round-trip) trong khoảng 1,5 μs trên phần cứng x64 hiện tại, vậy tức là 600.000 × 1,5 μs ≈ 0,9 giây cho hao phí kernel thuần túy trước khi phân tích một byte đơn lẻ — trường hợp tốt nhất của cache ấm (warm-cache). Khi cache lạnh (cold), mỗi lần nhảy là một thao tác trên thiết bị: ở độ trễ hiệu quả ~20 μs của lệnh đọc ngẫu nhiên 4 KB NVMe, 300.000 trong số chúng tiêu tốn khoảng 6 giây thời gian của thiết bị; trên bộ lưu trữ hạng SATA, tính bằng phút

Các lần đọc cũng di chuyển dữ liệu sai: 300.000 × 4 KB đẩy 1,2 GB qua các bộ đệm người dùng để phân phối khoảng 180 MB payload — khuếch đại lên sáu lần, mỗi byte đều được sao chép từ kernel sang user

Bộ đệm đọc trước (read-ahead buffer) được định cỡ bằng các cụm luồng đối tượng là sự cải tiến trung thực đầu tiên: một lần đọc 256 KB cho mỗi cụm thay vì một lần đọc cho mỗi đối tượng sẽ cắt giảm số lần chuyển tiếp đi từ một đến hai bậc độ lớn. Nó cũng là công cụ phù hợp ở những nơi mà việc ánh xạ trở nên khó xử, thường là các mạng chia sẻ (network shares)

Trình ánh xạ dạng cửa sổ đi xa hơn. Một lần quét toàn bộ là 29 lệnh gọi MapViewOfFile và 29 lệnh gọi UnmapViewOfFile, 58 lần chuyển tiếp tường minh chống lại 600.000. Một quá trình phân tích cú pháp do xref điều khiển thực sự không phải là một lần quét sạch, nhưng đường dẫn nhanh sẽ hấp thụ mọi lần tìm nạp bên trong cửa sổ trực tiếp; một lần duyệt lập chỉ mục siêu dữ liệu qua kho lưu trữ thử nghiệm chỉ đọng lại ở một vài trăm lần remap. Việc ánh xạ không loại bỏ công việc của kernel: nó chuyển đổi các syscall tường minh thành các lỗi trang (page faults) mà trình quản lý bộ nhớ giải quyết trong các cụm nhiều trang, thẳng từ cache tệp mà không có sao chép user-space (không gian người dùng), và các vùng không bao giờ được chạm tới thì không tốn gì cả. Từ đầu đến cuối, lần duyệt lập chỉ mục đi từ 23 giây lạnh và 7,1 giây ấm với các lần đọc mỗi đối tượng thành 6,5 giây lạnh và 1,9 giây ấm với trình ánh xạ; phần còn lại là tính năng phình to zlib, không phải IO

FILE_FLAG_NO_BUFFERING phù hợp ở đâu

FILE_FLAG_NO_BUFFERING bỏ qua cache hệ thống để đổi lấy các quy tắc căn chỉnh cứng: độ lệch, độ dài, và địa chỉ bộ đệm tất cả phải được căn chỉnh theo sector (cung từ). Nó kiếm được giá trị duy trì ở các công việc tuần tự quét một lần (single-pass) thứ mà nếu không sẽ làm ngập cache với các byte không ai đọc hai lần — một quá trình tuần tự hóa lại hàng loạt viết lại toàn bộ kho lưu trữ, hoặc một lần duyệt tuyến tính hóa đối với đầu ra đã hoàn thành. Với các bộ đệm được căn chỉnh từ 4 đến 8 MB, nó tiếp cận băng thông tuần tự của thiết bị mà không làm ô nhiễm cache

Nó hoàn toàn sai đối với việc phân tích cú pháp. Những bước nhảy xref ngẫu nhiên thông qua một handle không được bộ đệm (unbuffered handle) biến mỗi lần tìm nạp từ điển 300 byte thành một lệnh đọc vật lý đầy đủ không có cache để hấp thụ lần ghé thăm thứ hai — và phân tích cú pháp PDF liên tục thăm lại các khu vực, vì các trang khác nhau phân giải thành các luồng đối tượng giống nhau. IO không có bộ đệm cho quá trình viết lại tuần tự, IO được ánh xạ hoặc có cache cho quá trình phân tích ngẫu nhiên; cờ này hoạt động theo mỗi handle, vì vậy một pipeline có thể giữ cả hai loại trên cùng một tệp

64-bit, working sets, và khía cạnh ghi

Trên bản dựng 64-bit, sự phản đối về không gian địa chỉ biến mất: chuyển kích thước tệp thành cửa sổ và lớp ở trên sẽ thoái hóa thành một ánh xạ đầy đủ duy nhất. Vấn đề (catch) ở các dịch vụ chạy trong thời gian dài: các trang đọc-chỉ được tệp hỗ trợ không tính phí cam kết (commit), do đó các bộ đếm commit vẫn bình yên, nhưng mọi trang được chạm tới đều tham gia working set (tập hợp làm việc); phân tích cú pháp hầu hết dung lượng 1,8 GB và working set sẽ phát triển cho tương xứng, đẩy đuổi (evicting) mọi thứ khác. Cửa sổ có giới hạn đặt mức trần cho điều đó, do đó mô hình trượt vẫn là chế độ mặc định đúng đắn ngay cả ở nơi mà không gian địa chỉ là miễn phí

Ở khía cạnh ghi, IO rẻ nhất là IO không bao giờ được ban hành. Cơ chế cập nhật gia tăng của PDF (ISO 32000-1 §7.5.6) nối thêm các đối tượng đã thay đổi và một phần tham chiếu chéo mới sau các byte ban đầu, những thứ không bao giờ di chuyển. Việc đóng dấu một trang lên kho lưu trữ 1,8 GB nối thêm hàng chục kilobyte; một lần viết lại toàn bộ sẽ di chuyển toàn bộ 1,8 GB, cách nhau năm bậc độ lớn, và việc nối thêm là lệnh xuất tuần tự thuần túy ở đuôi

Các thư viện của losLab phù hợp ở đâu

Cả hai thư viện PDF losLab đều xuất xưởng kỷ luật này dưới dạng bề mặt API. HotPDF Direct File API đọc số lượng trang và cấu trúc thông qua một handle của tệp mà không cần xây dựng cây đối tượng, sao chép và giải mã ở cấp độ tệp, và ghi các bản thay đổi (deltas) thông qua BeginIncrementalUpdate — chính là chiến lược chỉ-nối-thêm (append-only) ở trên, đã được đóng gói. PDFlibPas đi cùng một tuyến đường với lớp Direct Access của nó: một trình đọc luồng duyệt bảng tham chiếu chéo tại chỗ, tìm nạp các đối tượng một cách lười biếng (lazily), trích xuất các dải trang từ tệp sang tệp, và duy trì các nội dung chỉnh sửa dưới dạng bản sửa đổi gia tăng. Nếu bạn đang tự viết trình phân tích cú pháp của riêng mình, lớp trình ánh xạ là của bạn để sử dụng; nếu bạn đang chạy một pipeline tài liệu, hãy để thư viện giữ cho cửa sổ được trung thực

Lưu ý: Xử lý IO được tối ưu hóa cho tài liệu quy mô gigabyte được tích hợp trực tiếp vào HotPDF VCL Component cho Delphi và C++Builder