Yüksek Performanslı Bir JSON Ayrıştırıcı Oluşturmak

 (dave.cheney.net)
1 puan yazan GN⁺ 2023-11-06 | 1 yorum | WhatsApp'ta paylaş
  • Dave Cheney’nin GopherCon Singapore 2023 sunumu, Go’da akış tabanlı bir JSON ayrıştırıcı oluştururken encoding/json ile benzer bir API’yi koruyup iş hacmini artıran ve ayırmaları azaltan tasarım sürecini ele alıyor
  • JSON’da uzunluk göstergesi olmadığından girdinin sonuna kadar okunması gerekir; performansın alt sınırı en az read(N)+parse(N) olduğundan baytları ve token’ları yeniden ziyaret etmeyi, kopyalamayı, ayırmaları ve hot path’teki fonksiyon çağrılarını azaltmak temel kısıttır
  • encoding/json.Decoder.Token, token’ları interface{} olarak döndürdüğü için kullanışlıdır; ancak somut değerler heap’e escape ettiğinden token sayısıyla orantılı ayırma yaratır ve tek bir "hello" token’ında bile 3 allocs/op oluşur
  • pkg/json, girdideki []byte alt dilimlerini döndüren NextToken, byteReader’ın kayan penceresi, manuel inline etme, durum metotlarını doğrudan çağırma ve bounds check kaldırma ile hot path maliyetini azaltır
  • Sonuçta pkg/json.Scanner, bir buffer verildiğinde ayırmasız token’laştırma yapar; Decoder.Token, encoding/json.Decoder.Token’dan 2–3 kat hızlıdır, daha az ayırma yapan Decoder.NextToken ise 8–10 kat hızlı performans gösterir

Hedefler ve temel kısıtlar

  • Hedef, bir Go paketi tasarım örneği olarak yüksek performanslı bir JSON ayrıştırıcı oluşturmaktır
  • Tasarım hedefleri üç tanedir
    • Tüm girdiyi belleğe almayan akış tabanlı işleme desteği
    • encoding/json’ın yüksek seviyeli json.Decoder API’siyle makul ölçüde uyumlu kalırken daha yüksek iş hacmi ve daha az ayırma sunmak
    • encoding/json API’sinin yanında daha verimli, ayırmasız veya üst sınırı olan API’ler sağlamak
  • Tüm girdiyi önce bellekte buffer’lamak, girdi boyutu bilinmediğinde veya sonsuz olduğunda kullanılabilirlik riski yaratır ve işlem öncesi bekleme süresini de artırır
  • Akış tabanlı okuma, veriyi gelir gelmez işler ve okuma ile işlemeyi örtüştürebilir

JSON ayrıştırmanın zaman karmaşıklığı

  • JSON’da uzunluk işaretçisi yoktur; ne kadar okunması gerektiğini bilmek için girdinin tamamını okumak gerekir
  • Bir JSON dizisinin 1.000’inci öğesini ayrıştırmak için önceki 999 öğeyi de okumak ve işlemek gerekir; bu yüzden girdi işleme atlanamaz
  • Performansın alt sınırı girdi boyutuyla orantılıdır; yalnızca basit okuma değil, token başlangıç ve bitişlerini bulmak için JSON durum makinesinden geçmek de gerektiğinden minimum read(N)+parse(N) olur
  • Ek maliyetleri azaltma ölçütleri şunlardır
    • N bayt okunduysa, her bayt mümkünse yalnızca bir kez işlenir
    • Aynı token da yalnızca bir kez işlenir
    • Scanner veya Decoder hot path’inde fonksiyon çağrısı sayısı O(bytes) değil O(tokens) ile sınırlanır
    • Kopyalama azaltılarak aynı baytların yeniden ziyaret edilme sayısı düşürülür
    • Ayırmalar azaltılarak heap ayırmaları, paylaşılan veri yapılarına erişim, kilitler, cache çekişmesi ve GC maliyeti düşürülür

Token’laştırma ve API tasarımı

  • Bir JSON decoder kabaca iki aşamaya ayrılır
    • Bayt akışını JSON token akışına dönüştüren scanner veya tokenizer
    • JSON token akışını Go nesnelerine uygulayan unmarshaller
  • encoding/json.Decoder.Token, token’ları interface{} olarak döndürür
    • Dizeler string, sayılar float64, boolean değerler bool, null ise nil, ayraçlar json.Delim olarak ifade edilir
    • Bu yaklaşım, token değerini ve tipini birlikte ifade ettiği için kullanımı kolaydır
  • Kolaylığın bir bedeli vardır
    • Brad Fitzpatrick, Token API’sini garbage factory olarak adlandırır
    • Decoder.Token API tasarımı gereği her token’a ayrılan somut değer heap’e escape eder
    • Ayırma sayısı, girdideki token sayısına bağlıdır
  • Tek bir "hello" token’ı benchmark’ında encoding/json 355ns/op, 19.7MB/s, 37.0B/op, 3.00 allocs/op gösterir
  • Ayırmayı API tasarımı belirler ve ayırmalar performansı doğrudan etkileyebilir

[]byte token’ları ve örtük tip bilgisi

  • JSON token’larının tipi yalnızca ilk karakterden anlaşılabilir
    • {, }: nesne başlangıcı ve sonu
    • [, ]: dizi başlangıcı ve sonu
    • t: true
    • f: false
    • n: null
    • ": dize
    • -, 0~9: sayı
  • pkg/json’ın Decoder.NextToken API’si, girdi []byte’ını Go değerlerine dönüştürmeden token’ı temsil eden baytları doğrudan girdiden alt dilim olarak döndürür
  • Döndürülen []byte’ın ilk baytı token tipini bildirir
  • Bu API’nin kısıtları vardır
    • Çıktı bir kopya değil, girdinin alt dilimi olduğundan geçerlilik süresi sınırlıdır
    • Bu, bufio.Scanner API’sine benzer
    • Token tipini veya gerçek dize/sayı değerlerini daha rahat ele almak için daha üst seviye bir soyutlama gerekir

Verimli okuma: byteReader

  • Geleneksel io.Reader.Read yaklaşımı, veriyi reader’dan buffer’a kopyalar ve bu kopyalamanın kendisi de maliyetlidir
  • io.Reader.Read, buffer yönetimini çağırana bırakır
    • Tek tek bayt okunduğunda, geçilen baytları saklamak veya geri almak için alan gerekebilir
    • Büyük bir buffer’a okuyup ardından token başlangıç ve bitişini bulma yaklaşımında, token sonu buffer içinde değilse çok sayıda yönetim işlemi, kopyalama ve buffer büyütme gerekir
  • Alternatif olarak Steven Schveighoffer’ın iopipe’ından ve Phil Pearl’ün fikirlerinden esinlenen byteReader kullanılır
  • byteReader, io.Reader üzerinde kayan pencere sunar; bufio.Reader’a benzer ama daha verimli bir API’ye sahiptir
    • window() mevcut okunmamış veri penceresini döndürür
    • release(n) pencerenin önündeki n baytı atar
    • extend() alttaki reader’dan daha fazla veri okuyarak pencereyi genişletir
  • Boşluk karakteri arama benchmark’ı, her karakteri ziyaret edip yalnızca boşluk olup olmadığını kontrol eden temel ölçüttür ve çeşitli girdilerde yaklaşık 2.04~2.07GB/s gösterir
  • Boşluk sayacı örnek kodu github.com/davecheney/whitespace adresindedir

Scanner optimizasyonu

  • Scanner.Next, aradaki boşlukları atlar, pencerenin ilk karakterinden token’ı belirler ve token sonuna kadar okur
  • İlk Scanner.Next performansı, boşluk temel ölçütüne kıyasla yaklaşık 1/4~2/5 düzeyindedir
    • Örnek: Scanner/canada 510MB/s, citm_catalog 677MB/s, sample 837MB/s
  • İlk optimizasyon, s.offset alanı güncellemesini yerel değişken offset ile değiştirmektir
    • s.offset, fonksiyona girişte ve çıkışta 0 olduğundan içerideki değişiklik dışarıdan görünmez
    • Yerel değişken kullanımı, derleyicinin geçici bellek yazmalarından kaçınmasını sağlar
    • citm_catalog 2.52ms’den 1.80ms’ye düşerek %28.46 azaldı; sample ise 828µs’den 528µs’ye düşerek %36.24 azaldı
  • Etkinin girdiye göre değişmesinin nedeni boşluk sayısı farkıdır
    • canada yalnızca 33 boşluk içerir
    • citm 1.227.563 boşluk içerir
  • İkinci optimizasyon, Scanner.token’ı Scanner.Next içine manuel olarak inline etmektir
    • Go derleyicisi, for döngüsü ve fonksiyon karmaşıklığı nedeniyle Scanner.token, parseString, parseNumber, Scanner.Next gibi fonksiyonları otomatik inline edemez
    • Scanner.Next ve Scanner.token, girdideki her token için çağrıldığından token başına iki fonksiyon çağrısı maliyeti oluşur
  • Manuel inline etmeden sonra iş hacmi %9~24 iyileşir
    • canada 512MB/s’den 642MB/s’ye çıkarak %24.50 artar
    • citm_catalog 960MB/s’den 1105MB/s’ye çıkarak %15.16 artar
    • sample 1.33GB/s’den 1.46GB/s’ye çıkarak %9.11 artar
  • Optimizasyonun etkisi iki noktada özetlenir
    • s.offset güncellemesi bayt başına 1 kezden token başına 1 keze indirilir
    • Hot path’te fonksiyon çağrılarından kaçınmak performansı iyileştirebilir

Doğrulama ve Decoder.NextToken

  • Scanner tek başına token’ları ayırabilir; ancak eksiksiz JSON işleme için durum doğrulaması gerekir
  • JSON bir durum makinesidir ve mevcut token’a göre bir sonraki token’ın ne olabileceği sınırlıdır
    • Örneğin {, "username" okunduktan sonra yalnızca : geçerlidir
  • Decoder.NextToken, Scanner.Next üzerine durum mantığı ekleyerek token dizisinin geçerli olup olmadığını kontrol eder
  • Durumlar; değer, nesne anahtar dizesi, nesne iki noktası, nesne değeri, nesne virgülü, dizi değeri, dizi virgülü ve bitiş durumu gibi parçalara ayrılır
  • İlk doğrulama uygulamasında bile pkg/json, encoding/json’dan 8~10 kat hızlı sonuçlar gösterir
    • 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

Durum geçişi optimizasyonu

  • Decoder.NextToken’ın merkezinde bir switch ifadesi vardır
  • Tipik bir switch, bir dizi if ifadesi gibi uygulanabilir; bu da uzun dallanma zincirlerinin komut akışını bölmesine ve CPU’nun branch predictor’ına yük bindirmesine yol açar
  • Durum değerinden durum metodunu bulmak için tablo kullanma yöntemi de vardır, ancak örnek uygulama başlatma döngüsü nedeniyle derlenmez
  • Bunun yerine Go’nun method expression özelliği kullanılarak d.state içine durum enum değeri yerine metodun kendisi kaydedilir
    • Decoder.NextToken, return d.state(d, tok) gibi mevcut durum metodunu doğrudan çağırır
  • Bu computed goto yaklaşımı tek başına büyük bir performans artışı sağlamaz
    • Bazı girdilerde neredeyse hiç değişim olmaz; twitter, code, example girdilerinde ise küçük ölçüde yavaşlar
    • sample %1.15 hızlanır
  • Bu değişiklik, bir sonraki optimizasyon olan outlinining’i mümkün kılar

Outlining ve bounds check kaldırma

  • Outlining sonrasında Decoder.NextToken yalnızca return d.state(d) yapar; her durum metodu doğrudan d.scanner.Next() çağırır
  • tok durum metoduna argüman olarak geçirilmediğinden çağrı stack’inden 3 words azaltılır
  • len(tok) < 1 kontrolü ile switch tok[0] aynı fonksiyonun içine girdiğinde bounds check kaldırma mümkün olur
    • Önceden len(tok) kontrolü Decoder.NextToken içindeydi ve durum metodu method expression ile çağrıldığından inline edilmiyordu
    • Bu nedenle durum metodundaki tok[0] için bounds check gerekiyordu
    • Uzunluk kontrolü aynı fonksiyonda yapılınca derleyici tok uzunluğunun en az 1 olduğunu kanıtlayabilir
  • Decoder.NextToken’ın kendisi de sadeleştiğinden inline edilebilir hale gelir
    • Çağıran taraf, dec.NextToken() yerine fiilen mevcut durum metoduna doğrudan çağrıyı görür
    • Fonksiyon çağrısı maliyeti ortadan kalkar

Nihai benchmark sonuçları

  • En alt seviyedeki pkg/json.Scanner, birkaç KB’lık buffer verildiğinde ayırmasız akış tabanlı token’laştırma yapar
    • 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’dan 2~3 kat hızlıdır
    • 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 çok daha az ayırma yapar ve 8~10 kat hızlıdır
    • 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
  • En yüksek seviyeli API’de pkg/json, encoding/json ile aynı şekilde Go nesnelerine unmarshal yapabilir
    • 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
  • Sunum bağlantısı dave.cheney.net/paste/gophercon-sg-2023.html, kod ise github.com/pkg/json adresindedir

Tasarımdan çıkarılan başlıklar

  • Ayırmalar performansı etkiler

    • GC hızlı ayırma yapıp verimli toplama gerçekleştirse bile, ayırma yapmamak her zaman daha hızlıdır
    • API tasarımıyla ayırmalar ortadan kaldırılabilir
    • Bu paketteki hız artışının büyük kısmı ayırmaların azaltılmasından gelir
    • Heap ayırma yoluna ve GC döngüsüne harcanmayan zaman taramaya ayrılır
    • encoding/json.Decoder API’si primitive değerleri interface{} olarak döndürdüğü için ayırma gerektirir
    • Değer heap’e escape eder ve fiilen değere işaret eden bir pointer haline gelir
    • Veri işlemede ayırma, algoritmanın en büyük performans maliyeti olabilir
    • Bayt başına ve token başına maliyetleri dikkatle azaltmak, ikinci en büyük performans iyileştirme etkenidir
    • Bayt başına fonksiyon çağrılarını token başına fonksiyon çağrılarına dönüştürme yönü önemlidir
    • encoding/json’ın API nedeniyle daha yavaş olabileceği varsayımıyla başlandı; farklı bir API kabul edilebilirse bazı unmarshal yollarında 2~3 kat, token’laştırmada 8~10 kat performans elde edilebilir

İlgili okumalar

1 yorum

 
GN⁺ 2023-11-06
Hacker News görüşleri

  • Oldukça iyi görünüyor. Kariyerim boyunca zaten fazlasıyla JSON parser yazdım ama makul ve hızlı bir JSON parser’ın nasıl tasarlanacağını adım adım gösteren bir referansın olması gerçekten güzel
    Yine de JSON için açık bir tokenizer şart değil. Token kavramını kaldırıp parsing ile tokenization’ı tamamen birleştirebilirsiniz. Genelde bunu böyle yaparım; bütün yapı daha basit olur
    ECMAScript gibi dillerde bu çok daha zordur; çünkü arrow function gibi, parantezli ifade sözdiziminin bir alt kümesi gibi görünüp ancak => çıkarsa kesinleşen durumlar vardır, bu da keyfi uzunlukta lookahead gerektirebilir

    • Kariyer boyunca “çok fazla JSON parser yazdım” demek için nasıl bir iş yapmış olmak gerekiyor, merak ettim

  • Takip etmesi keyifli bir yazı; kendin uygularsanız bunu böyle yaparsınız diye iyi bir akış kuruyor
    Üretim ortamında saf performans hedefliyorsanız Daniel Lemire’in https://github.com/simdjson/simdjson projesine de bakmaya değer. Go portu olarak MinIO’nun https://github.com/minio/simdjson-go sürümü de var

    • JSON biçimi hep aynıysa, genel amaçlı bir JSON parser’dan daha iyi sonuç verebilir
    • Eskiden çeşitli JSON parser’ların performansını karşılaştırdığımda SIMD tabanlı parser beklediğimden hayal kırıklığı yaratacak kadar yavaştı
    • Go’daki en hızlı JSON kütüphanesi TikTok’un arkasındaki şirketin yaptığı kütüphane
    • simdjson çok uzun zamandır en hızlı seçenek değil

  • Hızlı bir JSON parser yaparken öğrendiğim şeyler, dillere özgü özelliklerle epey iç içe ama genelleyince şöyle
    Tokenization aşamasında heap allocation’dan kaçınmak gerekir. Tokenizer’ın stack üzerinde ayrılan struct’lar döndürmesi ya da token başlangıç konumu, uzunluk ve type offset’lerini paketleyen int64 token’lar döndüren bir fonksiyon olması iyi olur
    Parsing sırasında da heap allocation’dan kaçının; buffer’ı dilimleyerek kullanmak isteyen istemciler için getString(key String) gibi bir arayüz desteklenebilir
    Derleme zamanında alanları bilinen nesnelere deserialize ederken, string değerlerini karşılaştırmadan önce genelde anahtar uzunluğuna göre bir switch üretilir
    Çok JSON işleyen veri pipeline’larında yalnızca JSON kütüphanesi seçimi bile 3 ila 10 kat performans farkı yaratabiliyordu ve başlıca parser’lar genelde nesne allocate etmeye çalışıyor
    Serialize/deserialize edilecek sınıflar derleme zamanında biliniyorsa Java’daki Jackson oldukça iyidir ama dikkatli kodlama ve profiling ile yaklaşık 2 kat daha fazla performans alınabilir
    Buna karşılık rastgele JSON işlenecekse, ana akım parser’lar çok fazla allocation yapma eğilimindedir; bu yüzden elle yazılmış daha invaziv bir parser bunu önleyebilir ve saniyede binlerce ya da yüz binlerce nesne işlerken performans kazancı çok büyük olur

  • Benzer bir yaklaşımla GraphQL tokenizer ve parser yaptım; bunda da bellek allocation’ı yok ve oldukça hızlı. Kod ilgini çekerse https://github.com/wundergraph/graphql-go-tools adresine bakabilirsin

    • Benim ucubem de ilginizi çekebilir: https://github.com/graph-guard/gqlscan
      Bu konuda bir konuşma da yaptım ama ne yazık ki kaydı alınmadı. Go’dan olabildiğince performans çıkarmaya çalışırken neredeyse kafayı yiyordum :D
    • Tüm sorguların önceden bilindiği allowlist tabanlı GQL sunucularında bunun ne kadar büyük bir sorun olduğunu merak ediyorum. AST parse sonucunu cache’leyebilir veya hatırlayabilirsiniz; dolayısıyla performans sorunu yalnızca container başladıktan sonraki birkaç dakika için mi geçerli diye düşünüyorum
      Yoksa başka şekillerde de etkisi oluyor mu, merak ettim

  • n2[1] içinde hızlı bir tokenizer’a ihtiyacım vardı ve aynı çöp üretici sorununu yaşadım. Temelde json.Delim gibi sabit token kümesi ile allocation yaratan string’lerin karışması problemiydi
    Oldukça iyi bulduğum çözüm, tokenizer’ı herhangi bir T için generic yapmak ve byte slice’ı T’ye çeviren bir fonksiyon alıp string yerine T kullanmak
    Böylece çağıran taraf, daha verimli bir temsile — örneğin daha az allocation yapan bir temsile — sahipse onu verebilir; aynı zamanda unit testlerde tokenizer’ı rahatça test etmek için identity function kullanılabilir
    Bir bakıma bu, build zamanında tokenizer ile parser’ı birleştirmeye benziyor ama generics sayesinde tokenizer, parser’ın temsilini bilmeden katmanlı yapı korunabiliyor
    [1] https://github.com/evmar/n2

  • Daha iyi API tasarımı ile standart kütüphaneye göre iyileştirme yapmak mümkün ama tam bir streaming parser yazıp, bir hata tespit edilene kadar struct’ı yarım doldurup sonra da ortada bırakmamak pratikte zor. Standart kütüphane de bunu açık bir tasarım kısıtı olarak ele almış gibi görünüyor

  • Bir şeyi kaçırmış olabilirim ama yazar, sürekli bir “streaming” parser yaptığını söylemesine rağmen bunun pratikte ne anlama geldiğini açıklamıyor
    Özellikle “hash table” içinde tekrar eden anahtarları nasıl ele aldığını anlatmıyor. Tekrarlanan anahtar çıkınca sink kodunu iki kez mi çağırıyor, yoksa tüm “hash table” okunana kadar bekleyip sonra mı sink kodunu çağırıyor, merak ediyorum
    Bence JSON hiyerarşik bir yapı, uzunluğu önceden bilinmiyor ve hepsinden önemlisi tekrarlanan anahtarlar içeriyor; bu yüzden özünde streaming için uygun değil
    JSON’un bazı alt kümeleri daha streaming dostu hale getirilebilir ama o noktada neden hâlâ JSON’la uğraşılsın ki? Çözüm JSON’u değiştirmekse, o zaman bence doğrudan JSON olmayan başka bir format daha iyi olur

  • Phil Pearl’den bahsedildiğini görmek güzel
    https://github.com/bytedance/sonic de bakmaya değer

  • Fazla büyük olduğu için inline edilmeyen bir fonksiyona “bu fonksiyonu gerçekten inline et” demenin bir yolu olmaması şaşırtıcı
    Temel whitespace sayma ve arama işleri SIMD ile vektörize edilirse çok daha hızlı olur gibi geliyor ama bunun yazarın kapsamı dışında olduğunu anlamak mümkün

    • Elbette zorunlu inline mümkün

  • “Tüm girdiyi belleğe alabileceğinizi varsaymak gerçekçi değil” sözü çoğu uygulama için yanlış

    • Uygulamaların çoğu JSON’u ağ üzerinden okur ve bu bir stream’dir. JSON nispeten küçük olsa bile tüm isteği bellekte buffer’layıp üzerinde oynamak latency’yi ciddi biçimde artırır
    • Doğru, ama büyük veri kümeleri üzerinde ETL tarzı dönüşüm yapması gereken uygulamalarda streaming son derece faydalı bir strateji
      Go’nun bu iş için doğru araç olmadığını söyleyebilirsiniz ama bu tür optimizasyonlarla neden olmasın diye düşünüyorum
    • Bir kütüphane yapıyorsanız sınırlarını açıkça belirtmeli ya da streaming desteği sunmalısınız
      Gigabayt boyutunda JSON verisi beslemek zorunda kaldım; bu yüzden streaming parser’lar için minnettarım. Ayrıca streaming desteği sunmak, yazarın birden fazla kullanım senaryosunu bildiğine ve mühendisliği daha iyi yaptığına da işaret eder
      Bellek sadece teoride ucuz ve neredeyse bedavadır; pratikte öyle değildir
    • “Diske sığması yeter” noktasındaysanız mmap() da bir seçenek değil mi? Gerçek streaming ihtiyacı, örneğin tek bir JSON dosyasındaki işlem ya da iş akışı benzeri verinin baş tarafını erkenden işlemek gerektiğinde ayrı bir konu
    • HTTP istek gövdesi de girdinin bir parçası sayılıyor mu?