jsongrep: DFA 기반으로 jq보다 훨씬 빠른 JSON 검색 도구 (Rust)

jsongrep: jq보다 빠른 JSON 검색 도구가 나옴

• Rust로 작성된 jsongrep이라는 JSON 쿼리 도구가 나왔는데, ripgrep에서 영감을 받은 프로젝트임. jq처럼 JSON을 변환하는 게 아니라 JSON 트리에서 값을 검색하는 것에 특화된 도구
• 핵심 아이디어: JSON 쿼리를 정규 언어(regular language)로 취급하고, 이를 DFA(결정적 유한 오토마타)로 컴파일해서 JSON 트리를 딱 한 번만 순회하면서 매칭함. 노드당 O(1) 전이, 백트래킹 없음, 재귀 스택 없음
• jq, jmespath, jsonpath-rust 같은 기존 도구들은 경로 표현식을 해석(interpret)하는 방식이라 각 노드에서 쿼리를 평가하고 재귀적으로 내려가야 함. jsongrep은 검색 전에 쿼리를 DFA로 컴파일해놓으니 검색 자체는 거의 공짜

쿼리 언어: 정규표현식인데 문자 대신 JSON 경로를 매칭

• roommates[0].name — 점(.)으로 중첩 필드 접근
• favorite_drinks[*] — 와일드카드로 모든 배열 인덱스 매칭
• name | roommates — 파이프로 OR 매칭 (정규표현식의 alternation)
• (* | [*])*.name — 클레이니 스타로 재귀 하강. 아무 키/인덱스를 0번 이상 따라간 뒤 name 필드를 찾음
• -F name 플래그로 재귀 하강 단축 가능 — 모든 깊이에서 name 필드를 찾아줌

내부 구조: 5단계 파이프라인

• 1단계: serde_json_borrow로 JSON을 제로카피(zero-copy) 파싱. 원본 버퍼의 &str을 빌려 쓰므로 문자열 할당이 없음
• 2단계: 쿼리 문자열을 PEG 문법(pest 라이브러리)으로 AST로 파싱
• 3단계: Glushkov 알고리즘으로 NFA 구성. Thompson 방식과 달리 ε-전이가 없는 NFA를 만들어서 후속 처리가 깔끔함
• 4단계: 부분집합 구성(subset construction)으로 NFA → DFA 변환. 각 DFA 상태는 NFA 상태들의 집합에 대응
• 5단계: JSON 트리를 DFS로 순회하면서 DFA 상태 전이. 전이가 없는 엣지를 만나면 해당 서브트리 전체를 O(1)에 가지치기 — 대형 문서에서 이게 속도의 핵심

벤치마크: 190MB JSON에서 압도적

• Criterion.rs로 벤치마킹. 4개 데이터셋(106B, 992KB, 7.6MB, 190MB)에서 테스트
• 비교 대상: jsonpath-rust, jmespath, jaq (jq 호환), jql
• 파싱: serde_json_borrow(제로카피)가 serde_json::Value(할당형)보다 빠름 — 예상대로
• 컴파일: jsongrep의 가장 큰 비용이 여기 있음. DFA 구성에 시간이 걸림. jmespath보다 한 자릿수 느림
• 검색만 따로 측정: DFA 기반이라 검색 자체는 다른 도구들을 압도
• 엔드투엔드(파싱+컴파일+검색): xlarge(190MB) 데이터셋에서 "비교가 안 됨(it's not even close)"이라고 본인이 직접 표현할 정도로 차이가 큼

솔직한 안티피치

• jq만큼 범용적이지 않음 — jsongrep은 검색 도구이지 변환 도구가 아님. 필터, 산술 연산, 문자열 보간 없음
• 아직 신생 프로젝트라 실전에서 검증되지 않았음
• jq를 대체하는 게 아니라 "JSON에서 특정 값을 빠르게 찾고 싶다"는 유스케이스에 특화된 도구로 보면 됨