Quần Cam

[Phỏng vấn] Parse file XML kích thước lớn như thế nào?

Bài toán đặt ra

Parse một file XML kích thước 10GB chứa thông tin kết quả tất cả các trận bóng đá trong lịch sử và ghi vào database.

<?xml version="1.0" encoding="UTF-8" ?>
<data>
  <match>
    <home_team>
      <id>1</id>
      <name>Germany</name>
    </home_team>
    <away_team>
      <id>2</id>
      <name>Brazil</name>
    </away_team>
    <result>7:1</result>
  </match>
  <match>
    <home_team>
      <id>3</id>
      <name>Vietnam</name>
    </home_team>
    <away_team>
      <id>4</id>
      <name>Thailand</name>
    </away_team>
    <result>3:0</result>
  </match>
  ...
</data>

Một phút suy ngẫm

Cách thông thường nhất để parse một file XML là dùng DOM Parser. DOM parser nhận vào một chuỗi XML và trả về một DOM. Qua DOM, ta dùng xpath để tương tác lấy dữ liệu.

document = Nokogiri::XML(xml_string)
document.xpath("//data/match").each do |match_element|
  home_team_element = match_element.xpath("/home_team")
  away_team_element = match_element.xpath("/away_team")
  result_element = match_element.xpath("/away_team")
  # code eaten by the Internet
end

Tuy nhiên DOM Parser không phải là một giải pháp hiệu quả cho bài toán ở trên vì:

  • Hao tốn memory: DOM Parser lưu toàn bộ dữ liệu DOM vào memory rồi từ đó ta tương tác với dữ liệu của nó. Thông thường bạn cần đến 10 bytes memory để lưu DOM cho 1 byte XML (#MagicNumber!). Ứng dụng vào đề bài thì dĩ nhiên 100GB là một con số rất lớn.
  • Time = Parsing Time + Processing Time: Giả sử ta được cấp cho 100GB để giải quyết bài toán này với DOM Parser, ta chỉ có thể bắt đầu tương tác với dữ liệu khi file được parse xong, như vậy thì không hiệu quả về mặt thời gian.

SAX Parser

Cách thứ hai là dùng SAX, là một event-based XML parser. Không như DOM Parser, SAX Parser không lưu cây DOM vào memory mà thay vào đó, nó sẽ trigger các event trong quá trình parse từ trên xuống dưới.

Với đoạn XML ở trên, các event được SAX Parser nhả ra lần lượt là:

start_document
start_element   {"name": "data", "attributes": []}
start_element   {"name": "match", "attributes": []}
start_element   {"name": "home_team", "attributes": []}
start_element   {"name": "id", "attributes": []}
characters      "1"
end_element     {"name": "id"}
start_element   {"name": "name", "attributes": []}
characters      "Germany"
end_element     {"name": "name"}
end_element     {"name": "home_team"}
end_element     {"name": "data"}
...
end_document

Như vậy với SAX Parser, bạn sẽ lấy dữ liệu thông qua cách handle các events thay vì dùng xpath như DOM parser.

Vì sao SAX parser lại hiệu quả hơn trong bài toán này?

  • Không ngốn quá nhiều memory: Như đã nói ở trên, SAX không lưu DOM nên ta không cần phải có 100GB trong memory để parse được một file XML 10GB.
  • Time = Parsing Time = Processing Time: Dữ liệu ở một XML node sẽ sẵn sàng ngay khi parser đi tới vị trí của nó. Khi parse xong một node <match> nào đó, ta đã có thể ngay lập tức process các dữ liệu home team, away team, v.v của nó. Nói một cách khác, việc processing diễn ra đồng thời với parsing.

Parsing

SAX Parser sẽ cung cấp cho bạn một event interface mà ở đó bạn cài đặt xử lý cho những event mà bạn quan tâm. Ở bài viết này tui sẽ dùng Saxy, SAX parser tui tự phát triển bằng Elixir, để làm ví dụ, tuy vậy cách handle SAX parser khá tương đồng ở các ngôn ngữ khác.

Ta sẽ tiến hành cài đặt các handler cần thiết. Mỗi handler sẽ đi kèm với thông tin của event tương ứng và state, state là biến được pass giữa các event trong suốt quá trình file XML được parse. Thế nên mỗi event cần phải trả về biến state mới.

defmodule FootballXMLHandler do
  @behaviour Saxy.EventHandler

  def start_element({name, attributes}, state) do
    state
  end

  def characters(string, state) do
    state
  end

  def end_element({name}, state) do
    state
  end
end

Một trong những cái khó khi làm việc với SAX là bạn phải tự nội/ngoại suy thông tin event dựa trên các dữ kiện và tự cấu trúc dữ liệu trả về.

Ví dụ ở mỗi characters event, ta không biết được nó thuộc về node nào, vì dữ kiện cung cấp chỉ gồm event type và characters. Muốn suy được điều đó, ta phải dùng thêm thủ thuật. Có người thích dùng các flag như isHomeTeamNode, isMatchNode, còn tui hay dùng thủ thuật parent stack.

Lưu lại parent stack

Nếu bạn có đọc bài My Engineering Life, tui có viết một chút về cách dùng parent stack trong SAX Parser. Đại khái là ta sẽ tiến hành lưu thông tin các node vào một stack và sử dụng nó để biết vị trí node hiện tại.

Vì sao phải là Stack? XML là cấu trúc cây mà thao tác duyệt cây kinh điển là DFS và stack được sử dụng để mô tả quá trình này với chi phí memory thấp và tránh phát sinh stack frame. (Xin cám ơn anh @linxGnu đã đóng góp giải thích chỗ này)

Khi một XML element bắt đầu, ta bỏ nó vào stack.

def start_element({name, attributes}, %{stack: stack} = state) do
  new_stack = [name | stack]  # Elixir syntax to put something into a list
  Map.put(state, :stack, new_stack) # return new state
end

Khi một XML element kết thúc, ta sẽ pop nó ra khỏi stack.

def end_element({name}, %{stack: stack} = state) do
  [^name | new_stack] = stack  # Pop something from stack
  Map.put(state, :stack, new_stack)
end

Để cho bạn dễ mường tượng, khi XML được parse stack sẽ có dạng như sau:

[data]                            # put <data>
[match, data]                     # put <match>
[home_team, match, data]          # put <home_team>
[id, home_team, match, data]      # put <id>
[home_team, match, data]          # pop <id>
[name, home_team, match, data]    # put <name>
[home_team, match, data]          # pop <name>
[match, data]                     # pop <home_team>
[away_team, match, data]          # put <away_team>
...
[]                                # pop <data>, EOF

Do đó khi nhận được characters event, ta sẽ biết được nó thuộc về node nào thông qua parent stack.

def characters(string, %{stack: stack} = state) do
  case stack do
    ["id" | ["home_team" | _rest]] -> # <id> characters in <home_team>
    ["id" | ["away_team" | _rest]] -> # <id> characters in <away_team>
    ["name" | ["away_team" | _rest]] -> # <name> characters in <away_team>
    _ -> # others
  end

  state # return old state
end

Processing

Giờ ta có thể tiến hành thực hiện yêu cầu thứ hai của bài toán là lưu dữ liệu vào database.

Khi parser đọc đến một <match> element mới, ta sẽ khởi tạo một Map lưu vào key last_match của state.

def start_element({"match", attributes}, state) do
  new_stack = [name | stack]  # Elixir syntax to put something into a list
  match = %{}

  state
  |> Map.put(:last_match, match)
  |> Map.put(:stack, new_stack)
end

Sau đó tùy vào từng node cụ thể mà ta sẽ map dữ liệu vào last_match.

def characters({chars}, %{stack: stack, last_match: match} = state) do
  new_match =
    case stack do
      ["id" | ["home_team" | _rest]] ->
        Map.put(match, :home_team_id, chars)
      ["id" | ["away_team" | _rest]] ->
        Map.put(match, :away_team_id, chars)
      ["name" | ["home_team" | _rest]] ->
        Map.put(match, :home_team_name, chars)
      ["name" | ["away_team" | _rest]] ->
        Map.put(match, :away_team_name, chars)
      ["result" | _rest]] ->
        Map.put(match, :result, chars)
      _ -> match
    end

  Map.put(state, :last_match, new_match)
end

Đến khi ta gặp sự kiện end_element của <match>, toàn bộ dữ liệu cho một trận đấu đều nằm trong last_match. Lúc này ta tiến hành ghi chúng vào database.

def end_element({name}, %{stack: stack, last_match: match} = state) do
  [^name | new_stack] = stack
  DB.write_to_db(match)
  Map.put(state, :stack, stack)
end

Bây giờ thì ta đã cơ bản hoàn thành yêu cầu bài toán đưa ra. Việc còn lại là sử dụng module ta vừa viết vào SAX parser.

init_state = %{stack: [], last_match: nil}
xml = File.read!("/path/to/football.xml")
Saxy.parse(xml, init_state, FootballXMLHandler)

Bài viết này sẽ giúp tui tăng lương như thế nào?

Lời khuyên của tui dành cho bạn là Tích cực gõ máy vận may sẽ tới.

Mặc dù vậy ở trên vẫn tồn tại một khuyết điểm là File.read! sẽ load 10GB data vào trong memory. Để tối ưu hóa điều này các SAX parser thường hỗ trợ thêm streaming parsing. Với streaming parsing thì thay vì truyền vào toàn bộ file XML, bạn sẽ cung cấp dữ liệu một cách nhỏ giọt theo từng chunk cho parser qua một continuation function/module để tiếp dữ liệu cho parser khi nó không tiếp tục parse được nội dung hiện tai.

Mặc dù vậy, với Saxy thì tính năng này vẫn còn đang trong quá trình phát triển. Bạn có thể hình dung :trollface: mã giả là như sau:

init_state = %{stack: [], last_match: nil}
stream = File.stream!("/path/to/football.xml", [], 2048) # read in 2048 byte chunks
Saxy.parse(xml, init_state, FootballXMLHandler)

NGUY HIỂM! KHU VỰC NHIỀU GIÓ!
Khuyến cáo giữ chặt bàn phím và lướt thật nhanh khi đi qua khu vực này.
Chức năng này hỗ trợ markdown và các thứ liên quan.

Bài viết cùng chủ đề

Elixir - Ngôn ngữ được viết bằng macros

Macro không những là một trong những viên gạch giúp bạn meta-program với Elixir, mà nó còn là công cụ giúp Elixir meta-program … chính nó nữa.

Một số kĩ thuật caching với HTTP/1.1

Giới thiệu RFC7234 và một số kỹ thuật tăng tốc web với HTTP/1.1 Caching.

IO data và Vectored IO

Bài viết giới thiệu về IO data, Vectored I/O và tối ưu hóa hệ thống dùng Elixir bằng cách tận dụng Vectored I/O.