고성능 JSON 파서 구축

 (dave.cheney.net)
1P by GN⁺ | ★ favorite | 댓글 1개
  • Dave Cheney의 GopherCon Singapore 2023 발표는 Go에서 스트리밍 JSON 파서를 만들며 encoding/json과 비슷한 API를 유지하되 처리량을 높이고 할당을 줄이는 설계 과정을 다룸
  • JSON은 길이 표시가 없어 입력을 끝까지 읽어야 하며, 성능 하한이 최소 read(N)+parse(N) 이라 바이트·토큰 재방문, 복사, 할당, 핫패스 함수 호출을 줄이는 일이 핵심 제약임
  • encoding/json.Decoder.Token은 토큰을 interface{}로 돌려줘 편리하지만, 구체 값이 힙으로 escape되어 토큰 수에 비례한 할당을 만들고 단일 "hello" 토큰에서도 3 allocs/op가 발생함
  • pkg/json은 입력의 []byte 서브슬라이스를 반환하는 NextToken, byteReader의 슬라이딩 윈도우, 수동 인라이닝, 상태 메서드 직접 호출, bounds check 제거로 핫패스 비용을 줄임
  • 최종적으로 pkg/json.Scanner는 버퍼가 주어지면 무할당으로 토큰화하고, Decoder.Token은 encoding/json.Decoder.Token보다 2~3배 빠르며, 할당이 적은 Decoder.NextToken은 8~10배 빠른 성능을 보임

목표와 기본 제약

  • 목표는 Go 패키지 설계 사례로 고성능 JSON 파서를 만드는 것임
  • 설계 목표는 세 가지임
    • 전체 입력을 메모리에 올리지 않는 스트리밍 처리 지원
    • encoding/json의 고수준 json.Decoder API와 합리적으로 호환되면서 더 높은 처리량과 적은 할당 제공
    • encoding/json API 외에 더 효율적인 무할당 또는 상한 있는 API 제공
  • 전체 입력을 먼저 메모리에 버퍼링하면 입력 크기를 알 수 없거나 무한할 때 가용성 위험이 생기고, 처리 전 대기 시간도 늘어남
  • 스트리밍 읽기는 데이터가 도착하는 즉시 처리하고, 읽기와 처리를 겹칠 수 있음

JSON 파싱의 시간 복잡도

  • JSON은 길이 마커가 없어 얼마나 읽어야 하는지 알려면 입력을 모두 읽어야 함
  • JSON 배열의 1,000번째 요소를 파싱하려면 앞의 999개 요소도 읽고 처리해야 하므로 입력 처리를 건너뛸 수 없음
  • 성능 하한은 입력 크기에 비례하며, 단순 읽기만이 아니라 JSON 상태 머신을 통과해 토큰 시작과 끝을 찾아야 하므로 최소 read(N)+parse(N)이 됨
  • 추가 비용을 줄이는 기준은 다음과 같음
    • N바이트를 읽었다면 각 바이트는 가능하면 한 번만 처리함
    • 같은 토큰도 한 번만 처리함
    • Scanner나 Decoder의 핫패스에서 함수 호출 수를 O(bytes)가 아니라 O(tokens)로 제한함
    • 복사를 줄여 같은 바이트를 다시 방문하는 횟수를 줄임
    • 할당을 줄여 힙 할당, 공유 자료구조 접근, 락, 캐시 경합, GC 비용을 낮춤

토큰화와 API 설계

  • JSON 디코더는 크게 두 단계로 나뉨
    • 바이트 스트림을 JSON 토큰 스트림으로 바꾸는 스캐너 또는 토크나이저
    • JSON 토큰 스트림을 Go 객체에 적용하는 언마셜러
  • encoding/json.Decoder.Token은 토큰을 interface{}로 반환함
    • 문자열은 string, 숫자는 float64, 불리언은 bool, null은 nil, 구분자는 json.Delim으로 표현됨
    • 이 방식은 토큰 값과 타입을 함께 표현해 사용하기 편함
  • 편의성에는 비용이 따름
    • Brad Fitzpatrick은 Token API를 garbage factory라고 부름
    • Decoder.Token API 설계상 각 토큰에 할당되는 구체 값이 힙으로 escape됨
    • 할당 수가 입력의 토큰 수에 묶임
  • 단일 "hello" 토큰 벤치마크에서 encoding/json은 355ns/op, 19.7MB/s, 37.0B/op, 3.00 allocs/op를 보임
  • API 설계가 할당을 좌우하고, 할당은 성능에 직접 영향을 줄 수 있음

[]byte 토큰과 암묵적 타입 정보

  • JSON 토큰은 첫 글자만으로 타입을 알 수 있음
    • {, }: 객체 시작과 끝
    • [, ]: 배열 시작과 끝
    • t: true
    • f: false
    • n: null
    • ": 문자열
    • -, 0~9: 숫자
  • pkg/json의 Decoder.NextToken API는 입력 []byte를 Go 값으로 변환하지 않고, 토큰을 나타내는 바이트를 입력에서 바로 서브슬라이스로 반환함
  • 반환된 []byte의 첫 바이트가 토큰 타입을 알려줌
  • 이 API에는 제약이 있음
    • 출력은 복사본이 아니라 입력의 서브슬라이스이므로 유효 기간 제한이 있음
    • 이는 bufio.Scanner API와 비슷함
    • 토큰 타입이나 실제 문자열·숫자 값을 더 편하게 다루려면 상위 추상화가 필요함

효율적인 읽기: byteReader

  • 전통적인 io.Reader.Read 방식은 데이터를 리더에서 버퍼로 복사하며, 이 복사 자체도 비용이 듦
  • io.Reader.Read는 버퍼 관리를 호출자에게 맡김
    • 한 바이트씩 읽으면 지나온 바이트를 저장하거나 되돌릴 공간이 필요할 수 있음
    • 큰 버퍼에 읽은 뒤 토큰 시작과 끝을 찾는 방식은 토큰 끝이 버퍼 안에 없을 때 많은 관리 작업, 복사, 버퍼 확장이 필요함
  • 대안으로 Steven Schveighoffer의 iopipe와 Phil Pearl의 아이디어에서 영감을 받은 byteReader를 사용함
  • byteReader는 io.Reader 위에 슬라이딩 윈도우를 제공하며 bufio.Reader와 비슷하지만 더 효율적인 API를 가짐
    • window()는 현재 읽지 않은 데이터 창을 반환함
    • release(n)은 창 앞쪽의 n바이트를 버림
    • extend()는 하위 리더에서 데이터를 더 읽어 창을 확장함
  • 공백 문자 검색 벤치마크는 각 문자를 방문해 공백 여부만 검사하는 기준선이며, 여러 입력에서 약 2.04~2.07GB/s를 보임
  • 공백 카운터 예제 코드는 github.com/davecheney/whitespace에 있음

스캐너 최적화

  • Scanner.Next는 중간 공백을 건너뛰고, 윈도우의 첫 문자로 토큰을 판별한 뒤 토큰 끝까지 읽음
  • 초기 Scanner.Next 성능은 공백 기준선 대비 약 1/4~2/5 수준임
    • 예: Scanner/canada 510MB/s, citm_catalog 677MB/s, sample 837MB/s
  • 첫 최적화는 s.offset 필드 갱신을 지역 변수 offset으로 바꾸는 것임
    • s.offset은 함수 진입과 종료 시 0이므로 내부 변경은 외부에서 보이지 않음
    • 지역 변수 사용으로 컴파일러가 임시 메모리 쓰기를 피함
    • citm_catalog는 2.52ms에서 1.80ms로 28.46% 감소, sample은 828µs에서 528µs로 36.24% 감소함
  • 입력마다 효과가 다른 이유는 공백 수 차이 때문임
    • canada는 공백이 33개뿐임
    • citm은 공백이 1,227,563개임
  • 두 번째 최적화는 Scanner.token을 Scanner.Next에 수동 인라이닝하는 것임
    • Go 컴파일러는 for 문과 함수 복잡도 때문에 Scanner.token, parseString, parseNumber, Scanner.Next 등을 자동 인라인하지 못함
    • Scanner.Next와 Scanner.token은 입력 토큰마다 호출되므로 토큰당 두 번의 함수 호출 비용이 발생함
  • 수동 인라이닝 후 처리량은 9~24% 개선됨
    • canada는 512MB/s에서 642MB/s로 24.50% 증가
    • citm_catalog는 960MB/s에서 1105MB/s로 15.16% 증가
    • sample은 1.33GB/s에서 1.46GB/s로 9.11% 증가
  • 최적화의 효과는 두 가지로 정리됨
    • s.offset 갱신을 바이트당 1회에서 토큰당 1회로 줄임
    • 핫패스에서 함수 호출을 피하면 성능이 개선될 수 있음

검증과 Decoder.NextToken

  • 스캐너만으로는 토큰을 나눌 수 있지만, 완전한 JSON 처리에는 상태 검증이 필요함
  • JSON은 상태 머신이며, 현재 토큰에 따라 다음에 올 수 있는 토큰이 제한됨
    • 예를 들어 {, "username"을 읽은 뒤에는 :만 유효함
  • Decoder.NextToken은 Scanner.Next 위에 상태 로직을 얹어 토큰 시퀀스가 유효한지 확인함
  • 상태는 값, 객체 키 문자열, 객체 콜론, 객체 값, 객체 콤마, 배열 값, 배열 콤마, 종료 상태 등으로 나뉨
  • 초기 검증 구현에서도 pkg/json은 encoding/json보다 8~10배 빠른 결과를 보임
    • canada: pkg/json 399MB/s, encoding/json 34.6MB/s
    • citm_catalog: pkg/json 713MB/s, encoding/json 87.1MB/s
    • sample: pkg/json 1.23GB/s, encoding/json 216MB/s

상태 전이 최적화

  • Decoder.NextToken의 중심에는 switch 문이 있음
  • 일반적인 switch는 일련의 if 문처럼 구현될 수 있어 긴 분기열이 명령 스트림을 나누고 CPU의 분기 예측기에 부담을 줌
  • 상태 값에서 상태 메서드를 찾기 위해 테이블을 쓰는 방법도 있지만, 예시 구현은 초기화 루프 때문에 컴파일되지 않음
  • 대신 Go의 method expression을 사용해 d.state에 상태 열거값 대신 메서드를 직접 저장함
    • Decoder.NextToken은 return d.state(d, tok)처럼 현재 상태 메서드를 직접 호출함
  • 이 computed goto 방식만으로는 성능 개선이 크지 않음
    • 일부 입력은 거의 변화가 없고, twitter, code, example에서는 소폭 느려짐
    • sample은 1.15% 빨라짐
  • 이 변경은 다음 최적화인 아웃라이닝을 가능하게 함

아웃라이닝과 bounds check 제거

  • 아웃라이닝 후 Decoder.NextToken은 return d.state(d)만 수행하고, 각 상태 메서드가 직접 d.scanner.Next()를 호출함
  • tok를 상태 메서드 인자로 넘기지 않으므로 호출 스택에서 3 words를 줄임
  • len(tok) < 1 검사와 switch tok[0]가 같은 함수 안에 들어가면서 bounds check 제거가 가능해짐
    • 이전에는 len(tok) 검사가 Decoder.NextToken에 있고 상태 메서드는 메서드 표현식으로 호출되어 인라인되지 않음
    • 따라서 상태 메서드의 tok[0]에는 bounds check가 필요했음
    • 같은 함수 안에서 길이 검사를 수행하면 컴파일러가 tok 길이가 최소 1임을 증명할 수 있음
  • Decoder.NextToken 자체도 단순해져 인라인 가능해짐
    • 호출자는 dec.NextToken() 대신 사실상 현재 상태 메서드 직접 호출을 보게 됨
    • 함수 호출 비용이 제거됨

최종 벤치마크 결과

  • 최하위 pkg/json.Scanner는 몇 KB 버퍼가 주어지면 무할당 스트리밍 토큰화를 수행함
    • canada: 638.78MB/s, 0 B/op, 0 allocs/op
    • citm_catalog: 1110.51MB/s, 0 B/op, 0 allocs/op
    • sample: 1471.01MB/s, 0 B/op, 0 allocs/op
  • pkg/json.Decoder.Token은 encoding/json.Decoder.Token보다 2~3배 빠름
    • canada: 101.98MB/s vs 33.19MB/s
    • citm_catalog: 333.23MB/s vs 82.71MB/s
    • sample: 788.59MB/s vs 209.12MB/s
  • pkg/json.Decoder.NextToken은 할당이 훨씬 적고 8~10배 빠름
    • canada: 466.52MB/s, 136 B/op, 3 allocs/op vs 34.42MB/s, 17,740,399 B/op, 889,106 allocs/op
    • citm_catalog: 798.58MB/s, 136 B/op, 3 allocs/op vs 86.08MB/s, 5,661,597 B/op, 324,692 allocs/op
    • sample: 1346.85MB/s, 1144 B/op, 9 allocs/op vs 217.44MB/s, 723,781 B/op, 26,095 allocs/op
  • 가장 높은 수준의 API에서 pkg/json은 encoding/json과 같은 방식으로 Go 객체에 unmarshal할 수 있음
    • canada: 82.08MB/s vs 58.70MB/s
    • citm_catalog: 215.66MB/s vs 104.00MB/s
    • sample: 615.99MB/s vs 128.04MB/s
  • 발표 링크는 dave.cheney.net/paste/gophercon-sg-2023.html, 코드는 github.com/pkg/json에 있음

설계에서 얻은 주제

  • 할당은 성능에 영향을 줌

    • GC가 빠르게 할당하고 효율적으로 수집하더라도, 할당하지 않는 편이 항상 더 빠름
    • API 설계로 할당을 없앨 수 있음
    • 이 패키지의 속도 향상 대부분은 할당 감소에서 나옴
    • 힙 할당 경로와 GC 사이클에 쓰지 않은 시간이 스캔에 사용됨
    • encoding/json.Decoder API는 primitive 값을 interface{}로 반환하기 때문에 할당을 요구함
    • 값이 힙으로 escape되어 사실상 값에 대한 포인터가 됨
    • 데이터 처리에서 할당은 알고리듬의 가장 큰 성능 비용이 될 수 있음
    • 바이트당 비용과 토큰당 비용을 주의 깊게 줄이는 것이 두 번째로 큰 성능 개선 요인임
    • 바이트당 함수 호출을 토큰당 함수 호출로 바꾸는 방향이 중요함
    • encoding/json이 API 때문에 더 느릴 수 있다는 가정에서 시작했고, 다른 API를 받아들일 수 있다면 일부 unmarshal 경로에서 2~3배, 토큰화에서 8~10배 성능을 얻을 수 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 꽤 좋아 보임. 커리어 동안 JSON 파서를 이미 너무 많이 만들어봤지만, 합리적이고 빠른 JSON 파서를 어떻게 설계할지 단계별로 보여주는 참고 자료가 있다는 건 정말 좋음
    다만 JSON에는 명시적인 토크나이저가 꼭 필요하지 않음. 토큰 개념을 없애고 파싱과 토큰화를 완전히 합칠 수 있음. 보통 이렇게 하는데 전체가 더 단순해짐
    ECMAScript 같은 언어에서는 훨씬 어려운데, 화살표 함수처럼 괄호식 문법의 부분집합처럼 보이다가 =>가 나오느냐에 따라 확정되는 경우가 있어 임의로 긴 미리보기가 필요해질 수 있음

    • 커리어 동안 “JSON 파서를 너무 많이 만들었다”는 건 대체 어떤 일을 했길래 가능한 건지 궁금함

  • 따라가며 보기 좋은 글이고, 직접 구현한다면 이렇게 하면 된다는 흐름이 잘 잡혀 있음
    운영 환경에서 순수 성능을 노린다면 Daniel Lemire의 https://github.com/simdjson/simdjson도 볼 만함. Go 포트인 MinIO의 https://github.com/minio/simdjson-go도 있음

    • JSON 형태가 항상 같다면 범용 JSON 파서보다 더 잘할 수도 있음
    • 예전에 여러 JSON 파서 성능을 비교했을 때 SIMD 기반 파서가 기대보다 실망스럽게 느렸음
    • Go에서 가장 빠른 JSON 라이브러리는 TikTok 뒤의 회사가 만든 것임
    • simdjson은 아주 오래전부터 가장 빠른 자리가 아니었음

  • 빠른 JSON 파서를 만들며 배운 점은 언어별 특성이 많이 섞여 있지만, 일반화하면 이렇다
    토큰화에서는 힙 할당을 피해야 함. 토크나이저는 스택에 할당되는 구조체를 반환하거나, 토큰의 시작 위치·길이·타입 오프셋 등을 패킹한 int64 토큰을 반환하는 함수로 두는 편이 좋음
    파싱에서도 힙 할당을 피하고, 버퍼를 잘라 쓰려는 클라이언트를 위해 getString(key String) 같은 인터페이스를 지원할 수 있음
    컴파일 시점에 필드를 아는 객체로 역직렬화할 때는 문자열 값을 비교하기 전에 보통 키 길이 기준 switch를 생성함
    JSON을 많이 처리하는 데이터 파이프라인에서는 JSON 라이브러리 선택만으로 3~10배 성능 차이가 날 수 있었고, 주요 파서들은 대체로 객체를 할당하려고 함
    직렬화·역직렬화할 클래스가 컴파일 시점에 알려져 있다면 Java의 Jackson은 꽤 잘하지만, 신중한 코딩과 프로파일링으로 2배 정도 더 끌어올릴 수 있음
    반대로 임의의 JSON을 처리한다면 주류 파서들은 많은 할당을 하려 하므로, 직접 쓴 더 침투적인 파서가 이를 피할 수 있고 초당 수천~수백만 객체를 처리할 때 성능 이득이 매우 커짐

  • 비슷한 접근으로 GraphQL 토크나이저와 파서를 만들었고, 이것도 메모리 할당이 없고 꽤 빠름. 코드가 궁금하면 https://github.com/wundergraph/graphql-go-tools를 보면 됨

    • 내 괴작도 볼 만할 수 있음: https://github.com/graph-guard/gqlscan
      이 주제로 발표도 했는데 아쉽게도 녹화는 안 됨. Go에서 최대한 뽑아내려고 하다가 거의 미쳐버렸음 :D
    • 모든 쿼리를 미리 알고 있는 허용 목록 기반 GQL 서버에서는 이게 얼마나 큰 문제인지 궁금함. AST 파싱 결과를 캐시하거나 기억해둘 수 있어서, 컨테이너 시작 후 몇 분 동안만 성능 문제가 되는 것 아닌가 싶음
      아니면 다른 방식으로도 영향을 주는지 궁금함

  • n2[1]에서 빠른 토크나이저가 필요했고, 같은 쓰레기 생성기 문제를 겪었음. 기본적으로 json.Delim 같은 상수 토큰 집합과, 할당을 유발하는 문자열이 섞이는 문제였음
    꽤 괜찮다고 생각하는 해결책은 토크나이저를 어떤 T에 대해 제네릭으로 만들고, 바이트 슬라이스를 T로 바꾸는 함수를 받아 문자열 대신 T를 쓰는 것임
    이렇게 하면 호출자가 더 효율적인 표현, 예를 들어 할당이 적은 표현을 갖고 있을 때 그걸 제공할 수 있고, 동시에 단위 테스트에서는 편하게 항등 함수를 써서 토크나이저를 테스트할 수 있음
    어떤 의미에서는 빌드 시점에 토크나이저와 파서를 융합하는 것과 비슷하지만, 제네릭 덕분에 토크나이저가 파서의 표현을 몰라도 계층을 유지할 수 있음
    [1] https://github.com/evmar/n2

  • 더 나은 API 설계로 표준 라이브러리보다 개선하는 건 가능하지만, 완전한 스트리밍 파서를 만들면서 오류를 발견하기 전까지 구조체를 반쯤 채워놓고 중간에 빠져나오지 않는 건 사실상 어렵다. 표준 라이브러리는 이것도 명시적인 설계 제약으로 둔 것으로 보임

  • 뭔가 놓쳤을 수도 있지만, 글쓴이는 “스트리밍” 파서를 만들었다고 반복하면서도 그게 실제로 무엇을 뜻하는지 설명하지 않음
    특히 “해시 테이블”에서 반복 키를 어떻게 처리했는지 설명이 없음. 반복 키가 나오면 싱크 코드를 두 번 호출하는지, 전체 “해시 테이블”을 다 읽을 때까지 기다렸다가 싱크 코드를 호출하는지 궁금함
    내 생각에 JSON은 계층 구조이고, 길이를 미리 알 수 없으며, 무엇보다 반복 키가 있어서 본질적으로 스트리밍에 부적합함
    JSON의 일부 부분집합을 더 스트리밍 친화적으로 만들 수는 있겠지만, 그럴 거면 굳이 JSON을 고칠 이유가 없음. 해결책이 JSON을 바꾸는 것이라면, 아예 JSON이 아닌 다른 형식이 더 낫다고 봄

  • Phil Pearl을 언급한 게 반가움
    https://github.com/bytedance/sonic도 볼 만함

  • 너무 커서 인라인되지 않은 함수에 대해 “정말로 이 함수는 인라인하라”고 말할 방법이 없다는 게 의외임
    기본 공백 문자 세기·검색 작업은 SIMD로 벡터화하면 훨씬 빨라질 것 같지만, 글쓴이 범위를 벗어난다는 건 이해됨

    • 당연히 강제 인라인은 가능함

  • “전체 입력을 메모리에 올려둘 수 있다고 기대하는 건 비현실적이다”라는 말은 대부분의 애플리케이션에는 틀림

    • 대부분의 애플리케이션은 네트워크에서 JSON을 읽고, 그건 스트림임. JSON이 비교적 작더라도 전체 요청을 메모리에 버퍼링하고 만지작거리면 지연 시간이 크게 늘어남
    • 맞지만, 큰 데이터셋에 대해 ETL식 변환을 해야 하는 애플리케이션에서는 스트리밍이 엄청나게 유용한 전략임
      Go가 그 작업에 맞는 도구가 아니라고 말할 수도 있겠지만, 이런 식의 최적화를 하면 못 할 이유는 없다고 봄
    • 라이브러리를 만든다면 한계를 명시적으로 밝혀야 하거나 스트리밍을 지원해야 함
      기가바이트 단위 JSON 데이터를 밀어 넣어본 적이 있어서 스트리밍 파서는 고맙다. 게다가 스트리밍을 지원한다는 건 작성자가 여러 사용 사례를 알고 있고 엔지니어링을 더 잘한다는 신호이기도 함
      메모리는 이론에서나 싸고 공짜에 가깝지, 현실에서는 그렇지 않음
    • “디스크에 들어간다” 정도로 만족할 수 있다면 mmap()도 가능한 선택지 아닌가? 진짜 스트리밍이 필요할 때, 예를 들어 단일 JSON 파일에서 거래나 작업 스트림처럼 앞부분 데이터를 일찍 처리해야 하는 경우는 별도임
    • HTTP 요청 본문도 입력의 일부로 보는 건가?
답변달기