Xây dựng trình phân tích cú pháp JSON hiệu năng cao

 (dave.cheney.net)
1 điểm bởi GN⁺ 2023-11-06 | 1 bình luận | Chia sẻ qua WhatsApp
  • Bài trình bày của Dave Cheney tại GopherCon Singapore 2023 nói về quá trình xây dựng trình phân tích JSON dạng streaming trong Go, giữ API tương tự encoding/json nhưng tăng thông lượng và giảm cấp phát
  • JSON không có chỉ dấu độ dài nên phải đọc tới hết đầu vào; cận dưới hiệu năng tối thiểu là read(N)+parse(N), vì vậy ràng buộc cốt lõi là giảm việc duyệt lại byte và token, sao chép, cấp phát, và gọi hàm trên đường nóng
  • encoding/json.Decoder.Token trả token dưới dạng interface{} nên tiện dùng, nhưng các giá trị cụ thể sẽ escape lên heap, tạo ra số lần cấp phát tỷ lệ với số token; ngay cả token đơn "hello" cũng tạo 3 allocs/op
  • pkg/json giảm chi phí đường nóng bằng NextToken trả về subslice []byte của đầu vào, sliding window của byteReader, inline thủ công, gọi trực tiếp các phương thức trạng thái, và loại bỏ bounds check
  • Cuối cùng, pkg/json.Scanner có thể token hóa không cấp phát khi được cung cấp buffer; Decoder.Token nhanh hơn encoding/json.Decoder.Token từ 2–3 lần, còn Decoder.NextToken với ít cấp phát hơn đạt hiệu năng nhanh hơn 8–10 lần

Mục tiêu và các ràng buộc cơ bản

  • Mục tiêu là xây dựng trình phân tích cú pháp JSON hiệu năng cao như một ví dụ thiết kế package Go
  • Có ba mục tiêu thiết kế
    • Hỗ trợ xử lý streaming mà không đưa toàn bộ đầu vào vào bộ nhớ
    • Tương thích hợp lý với API json.Decoder cấp cao của encoding/json, đồng thời cung cấp thông lượng cao hơn và ít cấp phát hơn
    • Cung cấp thêm API hiệu quả hơn, không cấp phát hoặc có giới hạn cấp phát, ngoài API của encoding/json
  • Nếu buffer toàn bộ đầu vào vào bộ nhớ trước, sẽ có rủi ro về tính sẵn sàng khi không biết kích thước đầu vào hoặc đầu vào là vô hạn, đồng thời làm tăng độ trễ trước khi xử lý
  • Đọc theo kiểu streaming cho phép xử lý ngay khi dữ liệu đến và có thể chồng lấp việc đọc với xử lý

Độ phức tạp thời gian của việc phân tích JSON

  • JSON không có dấu mốc độ dài, nên để biết cần đọc bao nhiêu thì phải đọc toàn bộ đầu vào
  • Để phân tích phần tử thứ 1.000 của một mảng JSON, vẫn phải đọc và xử lý 999 phần tử trước đó, nên không thể bỏ qua quá trình xử lý đầu vào
  • Cận dưới hiệu năng tỷ lệ với kích thước đầu vào; không chỉ đơn thuần là đọc mà còn phải đi qua state machine JSON để tìm điểm bắt đầu và kết thúc token, nên tối thiểu là read(N)+parse(N)
  • Các tiêu chí để giảm chi phí bổ sung như sau
    • Nếu đã đọc N byte thì mỗi byte nên được xử lý nhiều nhất có thể chỉ một lần
    • Mỗi token cũng chỉ nên được xử lý một lần
    • Trên đường nóng của Scanner hoặc Decoder, số lần gọi hàm nên bị giới hạn ở O(tokens) thay vì O(bytes)
    • Giảm sao chép để giảm số lần phải quay lại cùng một byte
    • Giảm cấp phát để hạ chi phí cấp phát heap, truy cập cấu trúc dữ liệu dùng chung, lock, tranh chấp cache và GC

Thiết kế token hóa và API

  • Bộ giải mã JSON được chia lớn thành hai giai đoạn
    • Bộ quét hoặc tokenizer biến luồng byte thành luồng token JSON
    • Unmarshaller áp dụng luồng token JSON vào đối tượng Go
  • encoding/json.Decoder.Token trả về token dưới dạng interface{}
    • Chuỗi được biểu diễn bằng string, số bằng float64, boolean bằng bool, null bằng nil, và dấu phân cách bằng json.Delim
    • Cách này tiện vì biểu diễn cùng lúc giá trị token và kiểu của nó
  • Nhưng sự tiện lợi có cái giá của nó
    • Brad Fitzpatrick gọi Token API là garbage factory
    • Theo thiết kế API của Decoder.Token, giá trị cụ thể được cấp phát cho mỗi token sẽ escape lên heap
    • Số lần cấp phát bị ràng buộc vào số token của đầu vào
  • Trong benchmark với token đơn "hello", encoding/json cho kết quả 355ns/op, 19.7MB/s, 37.0B/op, 3.00 allocs/op
  • Thiết kế API quyết định mức cấp phát, và cấp phát có thể ảnh hưởng trực tiếp tới hiệu năng

Token []byte và thông tin kiểu ngầm định

  • Kiểu của token JSON có thể biết chỉ từ ký tự đầu tiên
    • {, }: bắt đầu và kết thúc object
    • [, ]: bắt đầu và kết thúc array
    • t: true
    • f: false
    • n: null
    • ": chuỗi
    • -, 0~9: số
  • API Decoder.NextToken của pkg/json không chuyển []byte đầu vào thành giá trị Go, mà trả trực tiếp các byte biểu diễn token dưới dạng subslice của đầu vào
  • Byte đầu tiên của []byte được trả về cho biết kiểu token
  • API này có một số ràng buộc
    • Kết quả không phải bản sao mà là subslice của đầu vào nên có giới hạn về vòng đời sử dụng
    • Điều này tương tự API bufio.Scanner
    • Nếu muốn xử lý kiểu token hoặc giá trị chuỗi/số thực tế thuận tiện hơn thì cần tầng trừu tượng cao hơn

Đọc hiệu quả: byteReader

  • Cách truyền thống io.Reader.Read sẽ sao chép dữ liệu từ reader sang buffer, và chính thao tác sao chép đó cũng có chi phí
  • io.Reader.Read giao việc quản lý buffer cho bên gọi
    • Nếu đọc từng byte, có thể cần không gian để lưu lại hoặc quay lui các byte đã đi qua
    • Nếu đọc vào buffer lớn rồi tìm điểm đầu và cuối token, khi cuối token không nằm trong buffer sẽ cần nhiều công việc quản lý, sao chép và mở rộng buffer
  • Thay vào đó, dùng byteReader lấy cảm hứng từ iopipe của Steven Schveighoffer và ý tưởng của Phil Pearl
  • byteReader cung cấp sliding window trên io.Reader, giống bufio.Reader nhưng có API hiệu quả hơn
    • window() trả về cửa sổ dữ liệu hiện tại chưa đọc
    • release(n) loại bỏ n byte ở đầu cửa sổ
    • extend() đọc thêm dữ liệu từ reader bên dưới để mở rộng cửa sổ
  • Benchmark tìm ký tự khoảng trắng là đường cơ sở chỉ duyệt từng ký tự để kiểm tra xem có phải khoảng trắng hay không, và đạt khoảng 2.04~2.07GB/s trên nhiều đầu vào
  • Mã ví dụ bộ đếm khoảng trắng có tại github.com/davecheney/whitespace

Tối ưu bộ quét

  • Scanner.Next bỏ qua khoảng trắng ở giữa, xác định token từ ký tự đầu tiên của cửa sổ, rồi đọc đến cuối token
  • Hiệu năng ban đầu của Scanner.Next chỉ bằng khoảng 1/4 đến 2/5 so với đường cơ sở khoảng trắng
    • Ví dụ: Scanner/canada 510MB/s, citm_catalog 677MB/s, sample 837MB/s
  • Tối ưu đầu tiên là đổi việc cập nhật trường s.offset sang biến cục bộ offset
    • s.offset bằng 0 ở lúc vào và lúc ra khỏi hàm nên các thay đổi bên trong không thể quan sát từ bên ngoài
    • Dùng biến cục bộ giúp compiler tránh các lần ghi bộ nhớ tạm thời
    • citm_catalog giảm từ 2.52ms xuống 1.80ms, tức 28.46%, còn sample giảm từ 828µs xuống 528µs, tức 36.24%
  • Lý do hiệu quả khác nhau giữa các đầu vào là do số lượng khoảng trắng khác nhau
    • canada chỉ có 33 khoảng trắng
    • citm có 1.227.563 khoảng trắng
  • Tối ưu thứ hai là inline thủ công Scanner.token vào Scanner.Next
    • Trình biên dịch Go không thể tự động inline Scanner.token, parseString, parseNumber, Scanner.Next... do vòng for và độ phức tạp của hàm
    • Scanner.Next và Scanner.token được gọi cho mỗi token đầu vào, nên phát sinh chi phí hai lần gọi hàm trên mỗi token
  • Sau khi inline thủ công, thông lượng tăng từ 9~24%
    • canada tăng từ 512MB/s lên 642MB/s, tức 24.50%
    • citm_catalog tăng từ 960MB/s lên 1105MB/s, tức 15.16%
    • sample tăng từ 1.33GB/s lên 1.46GB/s, tức 9.11%
  • Hiệu quả của tối ưu có thể tóm lại thành hai điểm
    • Giảm việc cập nhật s.offset từ 1 lần mỗi byte xuống 1 lần mỗi token
    • Tránh gọi hàm trên đường nóng có thể cải thiện hiệu năng

Xác thực và Decoder.NextToken

  • Chỉ riêng scanner có thể tách token, nhưng để xử lý JSON đầy đủ thì cần xác thực trạng thái
  • JSON là một state machine, và tùy token hiện tại mà token tiếp theo hợp lệ sẽ bị giới hạn
    • Ví dụ, sau khi đọc {, "username" thì chỉ : mới hợp lệ
  • Decoder.NextToken bổ sung logic trạng thái lên trên Scanner.Next để kiểm tra chuỗi token có hợp lệ hay không
  • Trạng thái được chia thành giá trị, chuỗi khóa object, dấu hai chấm của object, giá trị object, dấu phẩy object, giá trị array, dấu phẩy array, trạng thái kết thúc, v.v.
  • Ngay cả với phần hiện thực xác thực ban đầu, pkg/json vẫn nhanh hơn encoding/json từ 8–10 lần
    • 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

Tối ưu chuyển trạng thái

  • Tâm điểm của Decoder.NextToken là câu lệnh switch
  • switch thông thường có thể được hiện thực giống một chuỗi if, khiến chuỗi nhánh dài chia nhỏ luồng lệnh và tạo gánh nặng cho bộ dự đoán nhánh của CPU
  • Cũng có thể dùng bảng để tra cứu phương thức trạng thái từ giá trị trạng thái, nhưng ví dụ minh họa không biên dịch được vì vòng lặp khởi tạo
  • Thay vào đó, dùng method expression của Go để lưu trực tiếp phương thức vào d.state thay vì lưu giá trị enum trạng thái
    • Decoder.NextToken gọi trực tiếp phương thức trạng thái hiện tại như return d.state(d, tok)
  • Riêng cách computed goto này không cải thiện hiệu năng nhiều
    • Một số đầu vào gần như không thay đổi, còn ở twitter, code, example thì chậm hơn đôi chút
    • sample nhanh hơn 1.15%
  • Tuy vậy, thay đổi này tạo điều kiện cho tối ưu tiếp theo là outlining

Outlining và loại bỏ bounds check

  • Sau khi outlining, Decoder.NextToken chỉ làm return d.state(d), còn mỗi phương thức trạng thái sẽ tự gọi d.scanner.Next() trực tiếp
  • Không còn truyền tok làm tham số cho phương thức trạng thái nên giảm được 3 words trên call stack
  • Việc kiểm tra len(tok) < 1 và switch tok[0] nằm trong cùng một hàm giúp loại bỏ bounds check
    • Trước đó, kiểm tra len(tok) nằm trong Decoder.NextToken, còn các phương thức trạng thái được gọi qua method expression nên không được inline
    • Vì vậy, truy cập tok[0] trong phương thức trạng thái vẫn cần bounds check
    • Khi kiểm tra độ dài trong cùng một hàm, compiler có thể chứng minh rằng độ dài tok tối thiểu là 1
  • Bản thân Decoder.NextToken cũng trở nên đơn giản hơn nên có thể được inline
    • Bên gọi, thay vì dec.NextToken(), về thực chất sẽ thấy lời gọi trực tiếp tới phương thức trạng thái hiện tại
    • Chi phí gọi hàm được loại bỏ

Kết quả benchmark cuối cùng

  • pkg/json.Scanner ở tầng thấp nhất có thể thực hiện token hóa streaming không cấp phát nếu được cung cấp buffer vài 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 nhanh hơn encoding/json.Decoder.Token từ 2–3 lần
    • 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 có ít cấp phát hơn rất nhiều và nhanh hơn 8–10 lần
    • 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 cấp cao nhất, pkg/json có thể unmarshal vào đối tượng Go theo cùng cách như encoding/json
    • 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
  • Link bài trình bày tại dave.cheney.net/paste/gophercon-sg-2023.html, mã nguồn tại github.com/pkg/json

Các chủ đề rút ra từ thiết kế

  • Cấp phát ảnh hưởng tới hiệu năng

    • Dù GC có thể cấp phát nhanh và thu gom hiệu quả, không cấp phát vẫn luôn nhanh hơn
    • Có thể loại bỏ cấp phát thông qua thiết kế API
    • Phần lớn mức tăng tốc của package này đến từ việc giảm cấp phát
    • Thời gian không dùng cho đường đi cấp phát heap và chu kỳ GC được chuyển sang việc quét
    • API encoding/json.Decoder yêu cầu cấp phát vì nó trả về các giá trị primitive dưới dạng interface{}
    • Giá trị escape lên heap nên trên thực tế trở thành con trỏ tới giá trị
    • Trong xử lý dữ liệu, cấp phát có thể là chi phí hiệu năng lớn nhất của thuật toán
    • Việc cẩn thận giảm chi phí theo byte và theo token là yếu tố cải thiện hiệu năng lớn thứ hai
    • Hướng đi quan trọng là biến các lần gọi hàm theo byte thành gọi hàm theo token
    • Điểm xuất phát là giả định encoding/json có thể chậm hơn vì API của nó, và nếu chấp nhận API khác thì có thể đạt hiệu năng cao hơn 2–3 lần ở một số đường unmarshal, và 8–10 lần ở khâu token hóa

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-11-06
Ý kiến trên Hacker News

  • Trông khá ổn. Trong sự nghiệp của mình, tôi đã làm trình phân tích JSON quá nhiều lần rồi, nhưng thật sự rất tốt khi có một tài liệu tham khảo chỉ từng bước cách thiết kế một trình phân tích JSON hợp lý và nhanh
    Tuy nhiên JSON không nhất thiết cần một tokenizer tường minh. Có thể bỏ khái niệm token và gộp hoàn toàn parsing với tokenization. Thường làm như vậy thì tổng thể sẽ đơn giản hơn
    Với các ngôn ngữ như ECMAScript thì khó hơn nhiều, vì có những trường hợp trông như một tập con của cú pháp biểu thức trong ngoặc, chẳng hạn arrow function, rồi chỉ được xác định khi có =>, nên có thể cần nhìn trước với độ dài tùy ý

    • Tôi tò mò không biết phải làm công việc kiểu gì thì trong sự nghiệp mới có thể “làm quá nhiều trình phân tích JSON” như vậy

  • Đây là bài viết dễ theo dõi, và nắm được khá rõ luồng rằng nếu tự triển khai thì nên làm thế này
    Nếu nhắm tới hiệu năng thuần trong môi trường production, Daniel Lemire có https://github.com/simdjson/simdjson cũng đáng xem. Cũng có bản port Go của MinIO là https://github.com/minio/simdjson-go

    • Nếu dạng JSON luôn giống nhau thì có thể làm tốt hơn parser JSON tổng quát
    • Trước đây khi so sánh hiệu năng của nhiều parser JSON, parser dựa trên SIMD chậm một cách đáng thất vọng hơn kỳ vọng
    • Thư viện JSON nhanh nhất trong Go là do công ty đứng sau TikTok tạo ra
    • simdjson đã không còn giữ vị trí nhanh nhất từ rất lâu rồi

  • Những điều học được khi làm parser JSON nhanh có pha trộn khá nhiều đặc thù theo ngôn ngữ, nhưng khái quát lại thì như sau
    Khi token hóa, cần tránh cấp phát heap. Tokenizer nên trả về một struct được cấp phát trên stack, hoặc là một hàm trả về token int64 đã đóng gói vị trí bắt đầu, độ dài, offset kiểu của token, v.v.
    Khi parsing cũng nên tránh cấp phát heap, và có thể hỗ trợ interface như getString(key String) cho các client muốn cắt dùng buffer
    Khi deserialize thành object có các field đã biết tại thời điểm compile, thường sẽ sinh switch theo độ dài key trước khi so sánh giá trị chuỗi
    Trong các data pipeline xử lý nhiều JSON, chỉ riêng việc chọn thư viện JSON đã có thể tạo ra chênh lệch hiệu năng 3~10 lần, và các parser chính thống nhìn chung có xu hướng cấp phát object
    Nếu các class cần serialize/deserialize đã biết tại thời điểm compile thì Jackson của Java làm khá tốt, nhưng với việc code cẩn thận và profiling có thể kéo lên thêm khoảng 2 lần
    Ngược lại, nếu xử lý JSON tùy ý thì các parser phổ biến sẽ cố cấp phát rất nhiều, nên một parser tự viết theo kiểu can thiệp sâu hơn có thể tránh điều đó, và khi xử lý từ hàng nghìn đến hàng triệu object mỗi giây thì lợi ích hiệu năng là rất lớn

  • Tôi đã tạo GraphQL tokenizer và parser với cách tiếp cận tương tự, cũng không cấp phát bộ nhớ và khá nhanh. Nếu tò mò về code thì xem https://github.com/wundergraph/graphql-go-tools

    • Thứ quái dị của tôi cũng có thể đáng xem: https://github.com/graph-guard/gqlscan
      Tôi cũng từng thuyết trình về chủ đề này, tiếc là không được ghi hình. Cố vắt kiệt Go đến mức gần như phát điên :D
    • Với server GQL dựa trên allowlist biết trước mọi query, tôi tò mò đây là vấn đề lớn đến mức nào. Có thể cache hoặc ghi nhớ kết quả parse AST, nên có vẻ nó chỉ là vấn đề hiệu năng trong vài phút sau khi container khởi động
      Hoặc tôi cũng tò mò liệu nó còn ảnh hưởng theo cách khác không

  • Trong n2[1], tôi cần một tokenizer nhanh và cũng gặp cùng vấn đề máy tạo rác. Về cơ bản đó là vấn đề trộn giữa tập token hằng như json.Delim và các chuỗi gây cấp phát
    Giải pháp mà tôi thấy khá ổn là làm tokenizer generic theo một T nào đó, nhận một hàm biến byte slice thành T, rồi dùng T thay vì chuỗi
    Như vậy caller có thể cung cấp biểu diễn hiệu quả hơn, chẳng hạn biểu diễn ít cấp phát hơn, nếu họ có; đồng thời trong unit test có thể tiện dùng hàm đồng nhất để test tokenizer
    Theo một nghĩa nào đó, nó giống việc hợp nhất tokenizer và parser ở thời điểm build, nhưng nhờ generic mà vẫn giữ được các tầng vì tokenizer không cần biết biểu diễn của parser
    [1] https://github.com/evmar/n2

  • Có thể cải thiện so với thư viện chuẩn bằng thiết kế API tốt hơn, nhưng khi làm một parser streaming hoàn chỉnh, việc không điền dở struct rồi thoát giữa chừng trước khi phát hiện lỗi thực tế là rất khó. Có vẻ thư viện chuẩn cũng đặt điều này như một ràng buộc thiết kế rõ ràng

  • Có thể tôi đã bỏ sót gì đó, nhưng tác giả lặp lại rằng mình đã làm parser “streaming” mà không giải thích thực sự nó nghĩa là gì
    Đặc biệt không có giải thích cách xử lý key lặp lại trong “bảng băm”. Tôi tò mò nếu gặp key lặp thì gọi sink code hai lần, hay đợi đọc hết toàn bộ “bảng băm” rồi mới gọi sink code
    Theo tôi, JSON là cấu trúc phân cấp, không biết trước độ dài, và quan trọng nhất là có key lặp, nên về bản chất không phù hợp với streaming
    Có thể làm một số tập con của JSON thân thiện với streaming hơn, nhưng nếu vậy thì không có lý do gì phải sửa JSON. Nếu giải pháp là thay đổi JSON, tôi nghĩ tốt hơn là dùng hẳn một định dạng khác không phải JSON

  • Rất vui khi thấy nhắc đến Phil Pearl
    https://github.com/bytedance/sonic cũng đáng xem

  • Thật bất ngờ là không có cách nào để nói “hãy inline hàm này thật sự đi” với một hàm quá lớn nên không được inline
    Các thao tác cơ bản như đếm/tìm ký tự trắng có vẻ sẽ nhanh hơn nhiều nếu vector hóa bằng SIMD, nhưng tôi hiểu là nó nằm ngoài phạm vi của tác giả

    • Tất nhiên là có thể ép inline

  • Câu “kỳ vọng có thể giữ toàn bộ input trong bộ nhớ là không thực tế” là sai với phần lớn ứng dụng

    • Phần lớn ứng dụng đọc JSON từ mạng, và đó là stream. Dù JSON tương đối nhỏ, nếu buffer toàn bộ request vào bộ nhớ rồi xử lý lòng vòng thì độ trễ sẽ tăng đáng kể
    • Đúng, nhưng với các ứng dụng cần làm biến đổi kiểu ETL trên dataset lớn, streaming là một chiến lược cực kỳ hữu ích
      Có thể nói Go không phải công cụ phù hợp cho việc đó, nhưng tôi nghĩ với kiểu tối ưu này thì không có lý do gì là không làm được
    • Nếu làm thư viện thì hoặc phải nêu rõ giới hạn, hoặc phải hỗ trợ streaming
      Tôi từng đẩy dữ liệu JSON cỡ gigabyte vào nên rất biết ơn parser streaming. Hơn nữa, việc hỗ trợ streaming cũng là dấu hiệu cho thấy tác giả biết nhiều use case và làm kỹ thuật tốt hơn
      Bộ nhớ chỉ rẻ và gần như miễn phí trong lý thuyết, ngoài đời thì không như vậy
    • Nếu chỉ cần hài lòng ở mức “nằm vừa trên đĩa” thì mmap() cũng không phải là một lựa chọn khả thi sao? Những khi thật sự cần streaming, ví dụ cần xử lý sớm dữ liệu phần đầu như một stream giao dịch hay tác vụ trong một file JSON đơn lẻ, thì đó là chuyện riêng
    • Body của HTTP request cũng được tính là một phần của input à?