उच्च-प्रदर्शन JSON parser बनाना

 (dave.cheney.net)
1 पॉइंट द्वारा GN⁺ 2023-11-06 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Dave Cheney का GopherCon Singapore 2023 प्रस्तुतीकरण Go में streaming JSON parser बनाने की डिज़ाइन प्रक्रिया पर केंद्रित है, जो encoding/json जैसी API बनाए रखते हुए throughput बढ़ाता है और allocations घटाता है
  • JSON में लंबाई का संकेत नहीं होता, इसलिए इनपुट को अंत तक पढ़ना पड़ता है, और performance की निचली सीमा कम से कम read(N)+parse(N) होती है; इसलिए bytes·tokens को दोबारा देखना, copy करना, allocation करना, और hot path में function calls घटाना मुख्य बाधाएँ हैं
  • encoding/json.Decoder.Token token को interface{} के रूप में लौटाता है, जो सुविधाजनक है, लेकिन concrete values heap पर escape हो जाती हैं, जिससे tokens की संख्या के अनुपात में allocations होते हैं, और एकल "hello" token में भी 3 allocs/op होते हैं
  • pkg/json इनपुट के []byte subslice लौटाने वाला NextToken, byteReader की sliding window, manual inlining, state methods को direct call, और bounds check हटाकर hot path cost कम करता है
  • अंततः pkg/json.Scanner, यदि buffer दिया जाए, तो बिना allocation के tokenization करता है; Decoder.Token, encoding/json.Decoder.Token से 2~3 गुना तेज है, और कम allocation वाला Decoder.NextToken 8~10 गुना तेज प्रदर्शन दिखाता है

लक्ष्य और मूल बाधाएँ

  • लक्ष्य Go package design के एक उदाहरण के रूप में उच्च-प्रदर्शन JSON parser बनाना है
  • डिज़ाइन के तीन लक्ष्य हैं
    • पूरे इनपुट को memory में लोड किए बिना streaming processing का समर्थन
    • encoding/json के high-level json.Decoder API के साथ उचित compatibility रखते हुए अधिक throughput और कम allocations देना
    • encoding/json API के अलावा अधिक efficient, zero-allocation या bounded-allocation API देना
  • यदि पूरे इनपुट को पहले memory में buffer किया जाए, तो इनपुट आकार अज्ञात या अनंत होने पर availability का जोखिम बढ़ता है, और processing शुरू होने से पहले latency भी बढ़ती है
  • streaming read में data आते ही processing शुरू की जा सकती है, और reading तथा processing को overlap किया जा सकता है

JSON parsing की समय जटिलता

  • JSON में length marker नहीं होता, इसलिए कितना पढ़ना है यह जानने के लिए पूरा इनपुट पढ़ना पड़ता है
  • JSON array के 1,000वें element को parse करने के लिए पहले के 999 elements भी पढ़ने और process करने पड़ते हैं, इसलिए इनपुट processing को छोड़ा नहीं जा सकता
  • performance की निचली सीमा इनपुट आकार के अनुपात में होती है; केवल पढ़ना पर्याप्त नहीं, JSON state machine से गुजरकर token की शुरुआत और अंत भी ढूँढना पड़ता है, इसलिए न्यूनतम लागत read(N)+parse(N) है
  • अतिरिक्त लागत घटाने के मानदंड ये हैं
    • यदि N bytes पढ़े गए हैं, तो हर byte को संभव हो तो केवल एक बार process किया जाए
    • एक ही token को भी केवल एक बार process किया जाए
    • Scanner या Decoder के hot path में function calls की संख्या O(bytes) नहीं बल्कि O(tokens) तक सीमित की जाए
    • copies घटाकर उन्हीं bytes को दोबारा देखने की संख्या कम की जाए
    • allocations घटाकर heap allocation, shared data structure access, lock, cache contention, और GC cost कम की जाए

Tokenization और API डिज़ाइन

  • JSON decoder मोटे तौर पर दो चरणों में बँटा होता है
    • byte stream को JSON token stream में बदलने वाला scanner या tokenizer
    • JSON token stream को Go objects पर लागू करने वाला unmarshaler
  • encoding/json.Decoder.Token token को interface{} के रूप में लौटाता है
    • string को string, number को float64, boolean को bool, null को nil, और delimiter को json.Delim के रूप में दर्शाया जाता है
    • यह तरीका token value और type को साथ में दिखाता है, इसलिए इस्तेमाल में सुविधाजनक है
  • लेकिन सुविधा की एक कीमत होती है
    • Brad Fitzpatrick ने Token API को garbage factory कहा था
    • Decoder.Token API डिज़ाइन के कारण हर token के लिए बनने वाली concrete value heap पर escape होती है
    • allocations की संख्या इनपुट के tokens की संख्या से बँध जाती है
  • एकल "hello" token benchmark में encoding/json ने 355ns/op, 19.7MB/s, 37.0B/op, 3.00 allocs/op दिखाए
  • API डिज़ाइन allocation को नियंत्रित करती है, और allocation सीधे performance को प्रभावित कर सकती है

[]byte tokens और implicit type information

  • JSON token का type पहले character से ही पता चल जाता है
    • {, }: object की शुरुआत और अंत
    • [, ]: array की शुरुआत और अंत
    • t: true
    • f: false
    • n: null
    • ": string
    • -, 0~9: number
  • pkg/json का Decoder.NextToken API इनपुट []byte को Go value में बदले बिना, token को दर्शाने वाले bytes को सीधे इनपुट से subslice के रूप में लौटाता है
  • लौटाए गए []byte का पहला byte token type बताता है
  • इस API की कुछ सीमाएँ हैं
    • output copy नहीं, बल्कि इनपुट का subslice है, इसलिए उसकी validity की अवधि सीमित होती है
    • यह bufio.Scanner API जैसा है
    • यदि token type या वास्तविक string·number value को अधिक सुविधाजनक रूप से संभालना हो, तो ऊपर की abstraction चाहिए

अधिक कुशल reading: byteReader

  • पारंपरिक io.Reader.Read तरीका reader से buffer में data copy करता है, और यह copy स्वयं भी लागत लाती है
  • io.Reader.Read buffer management caller पर छोड़ देता है
    • यदि एक-एक byte पढ़ा जाए, तो गुज़र चुके bytes को सुरक्षित रखने या पीछे लौटने के लिए जगह चाहिए हो सकती है
    • बड़े buffer में पढ़कर token की शुरुआत और अंत खोजने के तरीके में, यदि token का अंत buffer के भीतर न हो, तो काफी management, copying, और buffer growth की ज़रूरत पड़ सकती है
  • विकल्प के रूप में Steven Schveighoffer के iopipe और Phil Pearl के विचारों से प्रेरित byteReader का उपयोग किया गया
  • byteReader, io.Reader के ऊपर sliding window देता है; यह bufio.Reader जैसा है, लेकिन अधिक efficient API रखता है
    • window() वर्तमान में unread data window लौटाता है
    • release(n) window के आगे के n bytes हटा देता है
    • extend() नीचे के reader से और data पढ़कर window को बढ़ाता है
  • whitespace search benchmark एक baseline है, जिसमें हर character पर जाकर केवल यह जाँचा जाता है कि वह whitespace है या नहीं; कई inputs में इसका प्रदर्शन लगभग 2.04~2.07GB/s है
  • whitespace counter का example code github.com/davecheney/whitespace पर है

Scanner optimization

  • Scanner.Next बीच के whitespace को छोड़ता है, window के पहले character से token पहचानता है, और token के अंत तक पढ़ता है
  • शुरुआती Scanner.Next performance whitespace baseline की तुलना में लगभग 1/4~2/5 थी
    • उदाहरण: Scanner/canada 510MB/s, citm_catalog 677MB/s, sample 837MB/s
  • पहला optimization s.offset field update को local variable offset में बदलना था
    • function की entry और exit पर s.offset 0 होता है, इसलिए अंदर के बदलाव बाहर से दिखाई नहीं देते
    • local variable उपयोग करने से compiler temporary memory writes से बच सकता है
    • citm_catalog 2.52ms से 1.80ms, यानी 28.46% कम हुआ, और sample 828µs से 528µs, यानी 36.24% कम हुआ
  • अलग-अलग inputs पर प्रभाव अलग होने का कारण whitespace की संख्या का अंतर है
    • canada में केवल 33 whitespace हैं
    • citm में 1,227,563 whitespace हैं
  • दूसरा optimization Scanner.token को Scanner.Next में manual inlining करना था
    • Go compiler for loop और function complexity के कारण Scanner.token, parseString, parseNumber, Scanner.Next आदि को अपने-आप inline नहीं कर पाया
    • Scanner.Next और Scanner.token हर input token पर call होते हैं, इसलिए प्रति token दो function call की लागत आती है
  • manual inlining के बाद throughput में 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% वृद्धि
  • इन optimizations का असर दो बिंदुओं में समझा जा सकता है
    • s.offset updates को प्रति byte 1 बार से घटाकर प्रति token 1 बार करना
    • hot path में function calls से बचने पर performance बेहतर हो सकती है

Validation और Decoder.NextToken

  • केवल scanner token अलग कर सकता है, लेकिन पूर्ण JSON processing के लिए state validation चाहिए
  • JSON एक state machine है, और मौजूदा token के आधार पर अगला token सीमित होता है
    • उदाहरण के लिए {, "username" पढ़ने के बाद केवल : ही वैध है
  • Decoder.NextToken, Scanner.Next के ऊपर state logic जोड़कर token sequence की वैधता की जाँच करता है
  • states में value, object key string, object colon, object value, object comma, array value, array comma, end state आदि शामिल हैं
  • शुरुआती validation implementation में भी 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

State transition optimization

  • Decoder.NextToken के केंद्र में एक switch statement है
  • सामान्य switch अक्सर if statements की श्रृंखला की तरह implement हो सकता है, जिससे लंबी branch chain instruction stream को तोड़ती है और CPU के branch predictor पर दबाव डालती है
  • state value से state method खोजने के लिए table का उपयोग भी संभव है, लेकिन उदाहरण implementation initialization loop के कारण compile नहीं होता
  • इसके बजाय Go के method expression का उपयोग कर d.state में state enum के बजाय method को सीधे store किया गया
    • Decoder.NextToken अब return d.state(d, tok) की तरह वर्तमान state method को सीधे call करता है
  • केवल इस computed goto तरीके से performance में बड़ा सुधार नहीं हुआ
    • कुछ inputs में लगभग कोई बदलाव नहीं आया, और twitter, code, example में थोड़ा धीमा हुआ
    • sample 1.15% तेज हुआ
  • लेकिन इस बदलाव ने अगले optimization, यानी outlining, को संभव बनाया

Outlining और bounds check हटाना

  • outlining के बाद Decoder.NextToken केवल return d.state(d) करता है, और हर state method सीधे d.scanner.Next() call करती है
  • tok को state method argument के रूप में न भेजने से call stack में 3 words कम हो जाते हैं
  • len(tok) < 1 check और switch tok[0] एक ही function में आने से bounds check elimination संभव हो जाता है
    • पहले len(tok) check Decoder.NextToken में था, और state methods method expression से call होती थीं, इसलिए inline नहीं होती थीं
    • इसलिए state methods के tok[0] पर bounds check ज़रूरी था
    • जब length check उसी function में होता है, तो compiler साबित कर सकता है कि tok की लंबाई कम-से-कम 1 है
  • Decoder.NextToken स्वयं भी इतना सरल हो जाता है कि inline हो सके
    • caller को dec.NextToken() के बजाय व्यवहार में वर्तमान state method का direct call दिखाई देता है
    • function call की लागत हट जाती है

अंतिम benchmark परिणाम

  • सबसे निचले स्तर का pkg/json.Scanner, यदि कुछ KB का buffer दिया जाए, तो zero-allocation streaming tokenization करता है
    • 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 में allocations बहुत कम हैं और यह 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 objects में 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 है, और code github.com/pkg/json पर उपलब्ध है

डिज़ाइन से मिले मुख्य निष्कर्ष

  • allocation performance को प्रभावित करती है

    • भले ही GC तेज़ी से allocate और efficiently collect करे, allocation न करना हमेशा अधिक तेज़ होता है
    • API डिज़ाइन के माध्यम से allocation हटाई जा सकती है
    • इस package की अधिकांश speedup allocation घटने से आती है
    • heap allocation path और GC cycle पर न खर्च हुआ समय scanning में इस्तेमाल होता है
    • encoding/json.Decoder API primitive values को interface{} के रूप में लौटाती है, इसलिए allocation की आवश्यकता होती है
    • values heap पर escape होकर व्यवहार में value के pointer जैसी बन जाती हैं
    • data processing में allocation algorithm की सबसे बड़ी performance cost बन सकती है
    • प्रति byte लागत और प्रति token लागत को सावधानी से घटाना दूसरा सबसे बड़ा performance factor है
    • प्रति byte function call को प्रति token function call में बदलना महत्वपूर्ण दिशा है
    • शुरुआत यह मानकर हुई कि encoding/json API के कारण धीमा हो सकता है, और यदि अलग API स्वीकार्य हो, तो कुछ unmarshal paths में 2~3 गुना और tokenization में 8~10 गुना performance मिल सकती है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-11-06
Hacker News टिप्पणियाँ

  • काफ़ी अच्छा लग रहा है। अपने करियर में मैं पहले ही बहुत ज़्यादा JSON parser बना चुका हूँ, लेकिन यह बहुत अच्छा है कि एक ऐसा reference material है जो step-by-step दिखाता है कि एक समझदार और तेज़ JSON parser कैसे design किया जाए
    हालांकि JSON में अलग से tokenizer होना ज़रूरी नहीं है। token की concept हटाकर parsing और tokenization को पूरी तरह merge किया जा सकता है। आम तौर पर ऐसा ही किया जाता है और पूरा design ज़्यादा सरल हो जाता है
    ECMAScript जैसी languages में यह कहीं ज़्यादा मुश्किल है, क्योंकि arrow function जैसी चीज़ें parentheses-expression syntax के subset जैसी दिखती हैं और => आने या न आने पर ही तय होती हैं, इसलिए मनमाने रूप से लंबा lookahead चाहिए हो सकता है

    • करियर में “बहुत ज़्यादा JSON parser बनाए” — आखिर ऐसा कौन-सा काम किया कि यह संभव हुआ, जानने की इच्छा है

  • साथ-साथ follow करने के लिए अच्छा article है, और अगर खुद implement करना हो तो किस flow में करना चाहिए, यह अच्छी तरह पकड़ता है
    production environment में pure performance चाहिए तो Daniel Lemire का https://github.com/simdjson/simdjson भी देखने लायक है। Go port के रूप में MinIO का https://github.com/minio/simdjson-go भी है

    • अगर JSON shape हमेशा एक जैसी हो, तो आप general-purpose JSON parser से बेहतर कर सकते हैं
    • पहले जब मैंने कई JSON parsers की performance compare की थी, तो SIMD-based parser उम्मीद से ज़्यादा निराशाजनक रूप से धीमा लगा था
    • Go में सबसे तेज़ JSON library TikTok के पीछे वाली company ने बनाई है
    • simdjson बहुत पहले से ही सबसे तेज़ नहीं रहा है

  • तेज़ JSON parser बनाते हुए सीखी बातें language-specific details से काफ़ी भरी हैं, लेकिन generalize करें तो यह हैं
    tokenization में heap allocation से बचना चाहिए। tokenizer को ऐसा रखना बेहतर है जो stack पर allocated struct return करे, या token की start position, length, type offset वगैरह pack किया हुआ int64 token return करने वाला function हो
    parsing में भी heap allocation से बचें, और buffer slice करके इस्तेमाल करना चाहने वाले clients के लिए getString(key String) जैसा interface support किया जा सकता है
    compile time पर fields पता होने वाले object में deserialize करते समय, string values compare करने से पहले आम तौर पर key length के आधार पर switch generate किया जाता है
    बहुत ज़्यादा JSON process करने वाली data pipelines में सिर्फ JSON library चुनने से 3–10 गुना performance difference आ सकता था, और प्रमुख parsers आम तौर पर objects allocate करना चाहते हैं
    अगर serialize/deserialize की जाने वाली classes compile time पर known हों, तो Java का Jackson काफ़ी अच्छा करता है, लेकिन careful coding और profiling से इसे लगभग 2 गुना और बेहतर किया जा सकता है
    उलटे, अगर arbitrary JSON process करना हो, तो mainstream parsers बहुत allocations करने की कोशिश करते हैं, इसलिए खुद लिखा गया ज़्यादा intrusive parser इससे बच सकता है, और प्रति सेकंड हजारों से लाखों objects process करते समय performance gain बहुत बड़ा हो जाता है

  • इसी तरह के approach से GraphQL tokenizer और parser बनाया था, और इसमें भी memory allocation नहीं है और यह काफ़ी तेज़ है। code में रुचि हो तो https://github.com/wundergraph/graphql-go-tools देख सकते हैं

    • मेरी अजीब-सी रचना भी देखने लायक हो सकती है: https://github.com/graph-guard/gqlscan
      इस topic पर presentation भी दिया था, मगर अफ़सोस recording नहीं हुई। Go से जितना हो सके उतना निकालने की कोशिश करते-करते लगभग पागल हो गया था :D
    • सभी queries पहले से known होने वाले allowlist-based GQL server में यह कितना बड़ा issue है, जानने की इच्छा है। AST parsing result cache या याद रखा जा सकता है, इसलिए शायद container start होने के बाद सिर्फ कुछ मिनटों तक ही performance issue रहता हो
      या क्या यह किसी और तरीके से भी असर डालता है?

  • n2[1] में तेज़ tokenizer की ज़रूरत थी, और वही garbage generator वाली समस्या आई। मूल रूप से समस्या यह थी कि json.Delim जैसे constant tokens के set और allocation करवाने वाली strings mix हो रही थीं
    मुझे जो समाधान काफ़ी अच्छा लगता है, वह है tokenizer को किसी T के लिए generic बनाना, और byte slice को T में बदलने वाला function लेना, ताकि string की जगह T इस्तेमाल हो
    इससे caller के पास अगर ज़्यादा efficient representation हो, जैसे कम allocation वाला representation, तो वह उसे दे सकता है, और साथ ही unit tests में आराम से identity function इस्तेमाल करके tokenizer test किया जा सकता है
    एक तरह से यह build time पर tokenizer और parser को fuse करने जैसा है, लेकिन generics की वजह से tokenizer parser की representation जाने बिना भी layering बनाए रख सकता है
    [1] https://github.com/evmar/n2

  • बेहतर API design से standard library से improvement करना संभव है, लेकिन एक complete streaming parser बनाते हुए error मिलने से पहले struct को आधा भरकर बीच में निकलने से बचना वास्तव में मुश्किल है। लगता है standard library ने इसे भी explicit design constraint के रूप में रखा है

  • हो सकता है मैंने कुछ miss किया हो, लेकिन लेखक बार-बार कहता है कि उसने “streaming” parser बनाया है, फिर भी यह वास्तव में क्या मतलब रखता है, समझाता नहीं
    खासकर “hash table” में repeated keys को कैसे handle किया, इसकी कोई explanation नहीं है। repeated key आए तो क्या sink code को दो बार call करता है, या पूरी “hash table” पढ़ लेने तक इंतज़ार करके sink code call करता है, यह जानना चाहूँगा
    मेरे हिसाब से JSON hierarchical है, length पहले से पता नहीं होती, और सबसे अहम, इसमें repeated keys हो सकती हैं, इसलिए यह intrinsically streaming के लिए suitable नहीं है
    JSON के कुछ subsets को ज़्यादा streaming-friendly बनाया जा सकता है, लेकिन अगर ऐसा ही करना है तो JSON को patch करने की ज़रूरत ही क्या है। अगर solution JSON को बदलना है, तो मेरे हिसाब से JSON के बजाय कोई अलग format बेहतर है

  • Phil Pearl का ज़िक्र देखकर अच्छा लगा
    https://github.com/bytedance/sonic भी देखने लायक है

  • यह surprising है कि किसी function के लिए, जो बहुत बड़ा होने की वजह से inline नहीं हुआ, “सच में इस function को inline करो” कहने का कोई तरीका नहीं है
    basic whitespace counting/search operations को SIMD से vectorize करें तो वे बहुत तेज़ हो सकते हैं, लेकिन समझ आता है कि यह लेखक के scope से बाहर है

    • ज़ाहिर है forced inline करना संभव है

  • “यह उम्मीद करना कि पूरा input memory में रखा जा सकता है, realistic नहीं है” — यह बात ज़्यादातर applications के लिए गलत है

    • ज़्यादातर applications network से JSON पढ़ती हैं, और वह stream होता है। JSON अपेक्षाकृत छोटा हो तब भी पूरा request memory में buffer करके छेड़छाड़ करने से latency काफ़ी बढ़ जाती है
    • सही है, लेकिन बड़े datasets पर ETL-style transformation करने वाली applications में streaming बहुत उपयोगी strategy है
      आप कह सकते हैं कि Go उस काम के लिए सही tool नहीं है, लेकिन इस तरह की optimization करें तो न कर पाने की कोई वजह नहीं दिखती
    • अगर library बना रहे हैं तो limitations साफ़-साफ़ बतानी होंगी या streaming support करनी होगी
      मैंने gigabytes के JSON data feed किए हैं, इसलिए streaming parserありがたい है। इसके अलावा streaming support करना यह signal भी है कि author कई use cases जानता है और engineering बेहतर करता है
      memory theory में ही सस्ती और लगभग free होती है; reality में ऐसा नहीं है
    • अगर “disk में fit हो जाता है” इतना काफी है, तो mmap() भी एक option नहीं है क्या? असली streaming की ज़रूरत हो, जैसे एक single JSON file से transactions या jobs की stream की तरह शुरुआती data जल्दी process करना हो, तो वह अलग बात है
    • क्या HTTP request body को भी input का हिस्सा माना जा रहा है?