jsongrep nhanh hơn jq

 (micahkepe.com)
17 điểm bởi GN⁺ 27 ngày trước | 3 bình luận | Chia sẻ qua WhatsApp
  • Đây là công cụ CLI Rust để tìm kiếm tài liệu JSON theo đường dẫn, có tốc độ tìm kiếm nhanh hơn các công cụ hiện có như jq, jmespath, jsonpath-rust, jql
  • Truy vấn được biểu diễn bằng ngôn ngữ chính quy và biên dịch thành DFA, rồi duyệt cây JSON trong một lượt duy nhất nên xử lý trong thời gian O(n)
  • Sử dụng serde_json_borrow hỗ trợ zero-copy parsing để giảm tối đa việc cấp phát bộ nhớ, và được thiết kế với triết lý hiệu năng lấy cảm hứng từ ripgrep
  • Kết quả benchmark cho thấy hiệu năng end-to-end vượt trội nhất ngay cả với JSON dung lượng lớn, đồng thời cung cấp ngôn ngữ truy vấn đơn giản tập trung vào tìm kiếm
  • Được phát hành theo giấy phép MIT, và có thể tái sử dụng engine truy vấn dựa trên DFA như một thư viện Rust

Tổng quan về jsongrep

  • jsongrep là công cụ CLI viết bằng Rust để tìm kiếm giá trị trong tài liệu JSON theo đường dẫn, với mục tiêu đạt hiệu năng nhanh hơn jq, jmespath, jsonpath-rust, jql
  • Công cụ xem tài liệu JSON như một cây, biểu diễn đường dẫn (path) bằng ngôn ngữ chính quy (regular language), biên dịch thành DFA (Deterministic Finite Automaton) rồi duyệt trong một lượt duy nhất
  • Ngôn ngữ truy vấn được giữ đơn giản, thiết kế tập trung vào tìm kiếm, không có tính năng biến đổi hay tính toán
  • Tối thiểu hóa cấp phát bộ nhớ bằng zero-copy parsing với serde_json_borrow
  • Được phát triển dựa trên triết lý thiết kế và cách tiếp cận hiệu năng của ripgrep

Ví dụ sử dụng jsongrep

  • Lệnh jg nhận truy vấn và đầu vào JSON, rồi in ra mọi giá trị có đường dẫn khớp với truy vấn
  • Truy cập trường lồng nhau bằng ký pháp dấu chấm (dot path)
    • jg 'roommates[0].name' → "Alice"
  • Dùng wildcard (*, [*]) để khớp mọi khóa hoặc mọi chỉ mục
  • Dùng alternation (|) để chọn một trong nhiều đường dẫn
  • Dùng duyệt đệ quy ((* | [*])*) để tìm trường ở độ sâu bất kỳ
  • Dùng optional (?) để hỗ trợ khớp 0 hoặc 1 lần
  • Có thể tìm nhanh theo tên trường cụ thể bằng tùy chọn -F
  • Khi dùng pipe (| less, | sort), chương trình tự động ẩn đường dẫn trong đầu ra; có thể buộc hiển thị bằng --with-path

Các khái niệm cốt lõi của jsongrep

  • JSON là cấu trúc cây, trong đó khóa của object và chỉ mục của mảng đóng vai trò cạnh (edge)
  • Truy vấn định nghĩa một tập hợp đường dẫn từ gốc đến các node cụ thể
  • Ngôn ngữ truy vấn được thiết kế như ngôn ngữ chính quy, nên có thể chuyển thành DFA
  • DFA chỉ đọc đầu vào một lần và duyệt trong thời gian O(n) mà không cần backtracking
  • Các công cụ hiện có (jq, jmespath...) diễn giải truy vấn và duyệt đệ quy, còn jsongrep dùng DFA đã biên dịch sẵn để duyệt trong một lượt duy nhất

Cấu trúc engine truy vấn dựa trên DFA

  • Pipeline gồm 5 bước
    1. Phân tích JSON thành cây bằng serde_json_borrow
    2. Phân tích truy vấn thành AST
    3. Tạo NFA bằng thuật toán Glushkov
    4. Chuyển sang DFA bằng Subset Construction
    5. Duyệt cây JSON bằng một DFS duy nhất theo các chuyển trạng thái của DFA

  • Phân tích truy vấn

    • Dùng ngữ pháp PEG (thư viện pest) để chuyển truy vấn thành AST Query
    • Các thành phần cú pháp chính: Field, Index, Range, FieldWildcard, ArrayWildcard, Optional, KleeneStar, Disjunction, Sequence
    • Ví dụ: roommates[*].name → Sequence(Field("roommates"), ArrayWildcard, Field("name"))

  • Mô hình cây JSON

    • Khóa object và chỉ mục mảng là cạnh, còn giá trị là node
    • Ví dụ: roommates[*].name sẽ duyệt theo đường roommates → [0] → name

  • Xây dựng NFA (thuật toán Glushkov)

    • Tạo NFA không có chuyển ε
    • Các bước
      1. Gán số vị trí cho các ký hiệu trong truy vấn
      2. Tính các tập First/Last/Follows
      3. Tạo các chuyển trạng thái giữa các vị trí
    • Với truy vấn ví dụ roommates[*].name, NFA có cấu trúc tuyến tính đơn giản gồm 4 trạng thái

  • Chuyển sang DFA (Subset Construction)

    • Tạo DFA xác định dựa trên các tập trạng thái của NFA
    • Mỗi trạng thái tương ứng với một tập trạng thái NFA
    • Thêm ký hiệu Other để bỏ qua hiệu quả các khóa không cần thiết
    • Với truy vấn đơn giản, DFA có thể có cùng cấu trúc với NFA

  • Duyệt dựa trên DFS

    • Bắt đầu từ gốc và thực hiện chuyển trạng thái DFA theo từng cạnh
    • Nếu không còn chuyển trạng thái phù hợp thì cắt tỉa (prune) cây con đó
    • Nếu trạng thái DFA là accepting thì ghi lại đường dẫn và giá trị
    • Mỗi node được thăm tối đa một lần, nên toàn bộ quá trình duyệt là O(n)
    • serde_json_borrow tham chiếu trực tiếp buffer gốc mà không cần sao chép chuỗi

Phương pháp benchmark

  • Benchmark thống kê được thực hiện bằng Criterion.rs

  • Bộ dữ liệu

    • simple.json (106B), kubernetes-definitions.json (~992KB), kestra-0.19.0.json (~7.6MB), citylots.json (~190MB)

  • Công cụ so sánh

    • jsongrep, jsonpath-rust, jmespath, jaq, jql

  • Nhóm benchmark

    1. document_parse: tốc độ phân tích JSON
    2. query_compile: thời gian biên dịch truy vấn
    3. query_search: chỉ thực hiện tìm kiếm
    4. end_to_end: toàn bộ pipeline

  • Yếu tố công bằng

    • Lợi thế của zero-copy parsing được đo riêng
    • Chi phí biên dịch DFA được tách riêng
    • Các công cụ không có tính năng tương ứng sẽ bị loại khỏi bài test đó
    • Chi phí sao chép dữ liệu được xử lý riêng

Kết quả benchmark

  • Thời gian phân tích tài liệu: serde_json_borrow nhanh nhất
  • Thời gian biên dịch truy vấn: jsongrep tốn kém nhất do phải tạo DFA, còn jmespath nhanh hơn nhiều
  • Thời gian tìm kiếm: jsongrep nhanh nhất trong tất cả các công cụ
  • Hiệu năng end-to-end: ngay cả với bộ dữ liệu 190MB, công cụ vẫn nhanh vượt trội so với jq, jmespath, jsonpath-rust, jql
  • Có thể xem toàn bộ kết quả tại trang benchmark trực tiếp

Giấy phép và ứng dụng

  • Phần mềm nguồn mở theo giấy phép MIT
  • Có sẵn trên GitHub, Crates.io và Docs.rs
  • Engine truy vấn dựa trên DFA có thể tái sử dụng dưới dạng thư viện, tích hợp trực tiếp vào dự án Rust

Tài liệu tham khảo

  • Glushkov, V. M. (1961), The Abstract Theory of Automata
  • Rabin, M. O., & Scott, D. (1959), Finite Automata and Their Decision Problems

Bài viết liên quan

3 bình luận

 
roxie 21 ngày trước

Tuyệt đấy
 
lamanus 27 ngày trước

| Tại sao dấu gạch dọc lại trông khác trong phần nội dung nhỉ? Thú vị thật..
 
GN⁺ 27 ngày trước
Ý kiến trên Hacker News

  • Cú pháp của jq quá khó hiểu, nên mỗi lần chỉ muốn lấy một giá trị JSON đơn giản thôi cũng phải đi tìm lại

    • Thú vị đấy. Tôi lại thấy cú pháp của jq khá trực quan, và đã quen với việc chỉ dùng dấu chấm, pipe và ngoặc vuông như một shell pipeline
      Tôi chủ yếu viết các bộ lọc dùng một lần, nên thời gian viết thường nhiều hơn thời gian đọc
      Có lẽ trường hợp sử dụng của tôi khá đơn giản, hoặc jq hợp với cách tôi suy nghĩ
      Tôi mơ về một thế giới nơi mọi công cụ CLI đều nhập/xuất JSON và được nối với nhau bằng jq, nhưng với bạn thì chắc đó là cơn ác mộng
    • Tôi không dùng jq thường xuyên, nên nó là kiểu công cụ luôn mắc kẹt trong “thung lũng học tập”
      Mỗi lần dùng lại phải học lại từ đầu nên không hề trực quan
      sed cũng Turing-complete, nhưng phần lớn mọi người chỉ dùng để thay thế bằng regex
    • Tôi đề xuất celq do mình tạo ra
      Tôi thích jq, nhưng từng có lúc chính tôi cũng không hiểu nổi truy vấn mình đã viết trước đó
      celq dùng ngôn ngữ CEL quen thuộc hơn
    • Tôi cũng tự làm một công cụ tên là dq vì lý do tương tự
      Nó đơn giản là cách xử lý JSON bằng JavaScript, và ngạc nhiên là lại nhanh hơn jq
      Dùng kiểu như $ cat package.json | dq 'Object.keys(data).slice(0, 5)'
    • Bản thân JSON đã có quá nhiều nhiễu cú pháp không cần thiết, nên khá phiền
      Nhờ học Clojure mà giờ tôi dùng EDN thay cho JSON
      Nó gọn hơn, dễ đọc hơn và dễ xử lý có cấu trúc hơn
      Dạo này tôi xử lý dữ liệu bằng borkdude/jet hoặc babashka, rồi trực quan hóa bằng djblue/portal
      Tôi không hiểu vì sao lại phải cố chấp với các toán tử phức tạp của jq

  • Tôi coi trọng hiệu năng, nhưng những so sánh ở mức nano giây lại giống kiểu trình diễn hiệu suất hơn
    Trong đa số trường hợp, công cụ hiện có là đủ dùng
    Ví dụ, tôi chỉ dùng rg thay cho grep khi làm việc với file lớn

    • Nếu nghĩ vậy thì chỉ cần xem như “tôi không phải người dùng mục tiêu” là được
      Khác biệt giữa 2ms và 0.2ms có vẻ nhỏ, nhưng với người xử lý stream ở mức TB thì lại quan trọng
    • Nhưng nếu ai cũng nghĩ thế thì những kém hiệu quả nhỏ sẽ cộng dồn lại và làm cả hệ thống chậm đi
      Phần cứng ngày càng nhanh hơn, nhưng phần mềm thì ngược lại lại chậm hơn
    • Để jq tạo khác biệt, nó cần cú pháp trực quan và nhiều ví dụ thực tế hơn
    • Câu “đủ nhanh rồi” lúc nào cũng khiến tôi lăn tăn
      Từ chối tối ưu hóa nghe như lười biếng và thiếu trí tưởng tượng
      Việc yên tâm chỉ vì nó nhanh hơn độ trễ mạng nghe giống một lời bào chữa
    • Tôi cũng coi trọng tính dễ dùng và tính năng hơn tốc độ
      Nếu JSON quá lớn thì nên dùng định dạng nhị phân thay vì JSON
      Nếu phải ghép các pipeline quá phức tạp trên CLI, tôi thấy viết hẳn một chương trình còn tốt hơn

  • Nhiều công cụ CLI mới luôn quảng bá là “nhanh hơn”, nhưng thực tế tôi hiếm khi thấy jq chậm

    • Tôi làm việc với các file ndjson ở quy mô TB
      Ngay cả tác vụ đơn giản như đổi tên field bằng jq cũng quá chậm, nên tôi tự xử lý bằng script Node hoặc Rust
    • Khi làm việc với file log cực lớn, jq có thể thực sự bị cảm nhận là chậm
      Trong môi trường hyperscaler, người ta tải trực tiếp vài TB log về để phân tích
    • Chúng tôi parse phản hồi JSON từ hàng nghìn node
      Tùy theo độ phân giải giám sát mà khác biệt hiệu năng có thể thấy rõ
    • Mỗi lần có công cụ mới lại lặp lại mô-típ “phiên bản viết lại bằng Rust nhanh hơn”
      Chỉ triển khai một phần tính năng rồi lấy benchmark để tuyên bố chiến thắng
      Dự án lần này cũng có vẻ là một phần của xu hướng “tập con thì nhanh hơn” đó
    • Chỉ khi công cụ thực sự chậm ở thời điểm cần dùng thì bạn mới nhận ra nó chậm
      Từ lúc đó trở đi mọi thứ đều thấy chậm
      Giống như ripgrep, một khi đã dùng công cụ nhanh thì rất khó quay lại

  • Tôi đã dùng cả jq lẫn yq, nhưng dù yq chậm hơn nhiều tôi cũng chưa từng phàn nàn
    Nếu có công cụ nhanh hơn jq thì rất hay, nhưng đó chỉ là nhu cầu của một nhóm người dùng nhất định
    Dù vậy, với tư cách người yêu tối ưu hóa, tôi vẫn dành sự tôn trọng

    • Tôi tò mò là bạn đang nói tới yq nào — bản Go hay bản Python?
    • Trong môi trường tích hợp server thì hiệu năng quan trọng, nhưng với CLI thì đa số trường hợp đều đủ nhanh
    • Tôi xử lý vài GB GeoJSON xuất từ ArcGIS bằng jq
      Ở bước ETL cũng mất khá nhiều thời gian
    • Không phải ai cũng dùng công cụ theo cùng một cách

  • Khi mới mở trang, tôi gặp lỗi màu ở light mode bị vỡ
    Chuyển sang dark mode rồi chuyển lại thì hết

    • Trang này cũng cho cảm giác được “vibe-code” giống như chính công cụ vậy
    • Tôi là tác giả đây, do không dùng light mode nên quên test, sẽ sửa ngay
    • Vấn đề là một số style dark mode trong CSS bị rò sang
    • Trên Android Firefox thì ổn, nhưng thang đo biểu đồ mỗi cái một kiểu nên khó so sánh
    • Giờ đã sửa xong

  • Tôi chuyển sang Jaq vì độ chính xác
    Nghe nói hiệu năng cũng tốt hơn jq

    • Cảm ơn vì gợi ý. jaq có vẻ đã phát triển theo hướng đúng đắn hơn jsongrep
    • Tuy vậy, dù jaq 3.0 nhanh hơn jq bản đóng gói sẵn trên distro, jq tự build vẫn nhanh hơn
      Có vẻ tiếng xấu “jq chậm” là do vấn đề đóng gói của bản phân phối

  • Trong công việc tôi thường xuyên xử lý newline-delimited JSON (jsonl)
    Mỗi dòng là một đối tượng JSON hoàn chỉnh, nên tôi tò mò không biết các công cụ CLI chính có hỗ trợ định dạng này không

  • Tôi từng dùng nhiều công cụ CLI xử lý dữ liệu như jq, mlr, htmlq, xsv, yq,
    nhưng từ khi biết đến Nushell thì tất cả đều được thay thế
    Việc có thể xử lý mọi định dạng bằng một cú pháp duy nhất là trải nghiệm rất mới mẻ

    • Từ giữa năm 2023 đến giờ tôi cũng dùng Nushell làm shell chính
      Chỉ khi cộng tác với đồng nghiệp thì mới dùng kèm jq, yq, mlr
    • Tôi cũng thay gần hết bằng Nushell
      Vẫn có đôi chút bất tiện ở phần cấu hình autocomplete và khả năng tìm kiếm lệnh, nhưng vẫn tốt hơn oh-my-zsh rất nhiều
      Nếu sau này có ép buộc annotation kiểu, biên dịch ra binary tĩnh, và cả thư viện TUI, thì chắc còn dùng để viết app nhỏ luôn
    • Tôi cũng đồng ý. Nhờ cú pháp trực quan và nhất quán mà Nushell giúp việc tự động hóa dễ hơn hẳn

  • Công cụ rất hay! Chỉ là phần trực quan hóa benchmark hơi đáng tiếc
    Mọi công cụ đều cùng một màu nên khó tìm jsongrep nằm ở đâu
    Ngay cả jq cũng không có trên biểu đồ nên càng thấy khó hiểu
    File xLarge chỉ 190MiB nên còn nhỏ, trong khi tôi thường xử lý JSON cỡ 400MiB~1GiB

    • Tôi là tác giả xin trả lời. Hiện phạm vi benchmark đang ở khoảng 106B~190MB
      Nếu có tài liệu JSON công khai lớn hơn thì rất mong được giới thiệu

  • Phần trực quan hóa benchmark tạo cảm giác hơi thô
    Sẽ tốt hơn nếu dùng màu sắc hoặc hình dạng để biểu đạt thêm nhiều chiều dữ liệu
    Việc phải tự đọc đường dẫn file mới hiểu được kết quả thì khá bất tiện