Construcción de un parser JSON de alto rendimiento

 (dave.cheney.net)
1 puntos por GN⁺ 2023-11-06 | 1 comentarios | Compartir por WhatsApp
  • La charla de Dave Cheney en GopherCon Singapore 2023 aborda el proceso de diseño de un parser JSON en streaming en Go, manteniendo una API similar a encoding/json pero con mayor throughput y menos asignaciones
  • JSON no tiene indicador de longitud, así que hay que leer toda la entrada hasta el final; el límite inferior de rendimiento es al menos read(N)+parse(N), por lo que la restricción clave es reducir revisitas de bytes y tokens, copias, asignaciones y llamadas a funciones en el hot path
  • encoding/json.Decoder.Token devuelve los tokens como interface{}, lo cual es conveniente, pero hace que los valores concretos escapen al heap y produzcan asignaciones proporcionales al número de tokens; incluso un solo token "hello" genera 3 allocs/op
  • pkg/json reduce el costo del hot path usando NextToken, que devuelve subslices de []byte de la entrada, una ventana deslizante en byteReader, inlining manual, llamadas directas a métodos de estado y eliminación de bounds checks
  • Al final, pkg/json.Scanner tokeniza sin asignaciones si se le da un búfer, Decoder.Token es 2 a 3 veces más rápido que encoding/json.Decoder.Token, y Decoder.NextToken, con menos asignaciones, muestra un rendimiento de 8 a 10 veces superior

Objetivos y restricciones básicas

  • El objetivo es crear un parser JSON de alto rendimiento como caso de estudio de diseño de paquetes en Go
  • Hay tres metas de diseño
    • Soportar procesamiento en streaming sin cargar toda la entrada en memoria
    • Ofrecer mayor throughput y menos asignaciones, manteniendo compatibilidad razonable con la API de alto nivel json.Decoder de encoding/json
    • Además de la API de encoding/json, ofrecer APIs más eficientes, sin asignaciones o con asignaciones acotadas
  • Si se almacena primero toda la entrada en memoria, hay riesgos de disponibilidad cuando el tamaño es desconocido o infinito, y también aumenta la latencia antes del procesamiento
  • La lectura en streaming procesa los datos tan pronto llegan y permite superponer lectura y procesamiento

Complejidad temporal del parsing de JSON

  • JSON no tiene marcador de longitud, así que para saber cuánto hay que leer se debe consumir toda la entrada
  • Para parsear el elemento 1,000 de un arreglo JSON, también hay que leer y procesar los 999 elementos anteriores, por lo que no se puede saltar el procesamiento de la entrada
  • El límite inferior de rendimiento es proporcional al tamaño de la entrada; no basta con leer, también hay que pasar por la máquina de estados de JSON para encontrar el inicio y fin de los tokens, así que el mínimo es read(N)+parse(N)
  • Los criterios para reducir costo adicional son estos
    • Si se leyeron N bytes, cada byte debería procesarse, idealmente, una sola vez
    • Cada token debería procesarse una sola vez
    • En el hot path de Scanner o Decoder, el número de llamadas a función debe limitarse a O(tokens) y no a O(bytes)
    • Reducir copias para disminuir la cantidad de veces que se vuelven a visitar los mismos bytes
    • Reducir asignaciones para bajar el costo de asignaciones en heap, acceso a estructuras compartidas, locks, contención de caché y GC

Tokenización y diseño de API

  • Un decodificador JSON se divide, en términos generales, en dos etapas
    • Un scanner o tokenizer que convierte el flujo de bytes en un flujo de tokens JSON
    • Un unmarshaler que aplica el flujo de tokens JSON a objetos de Go
  • encoding/json.Decoder.Token devuelve los tokens como interface{}
    • Las cadenas se representan como string, los números como float64, los booleanos como bool, null como nil y los delimitadores como json.Delim
    • Este enfoque es cómodo porque expresa al mismo tiempo el tipo y el valor del token
  • Esa comodidad tiene un costo
    • Brad Fitzpatrick llamó a la API Token una garbage factory
    • Por el diseño de la API Decoder.Token, el valor concreto asignado a cada token escapa al heap
    • El número de asignaciones queda atado al número de tokens de la entrada
  • En un benchmark con un solo token "hello", encoding/json muestra 355ns/op, 19.7MB/s, 37.0B/op y 3.00 allocs/op
  • El diseño de la API determina las asignaciones, y las asignaciones pueden afectar directamente el rendimiento

Tokens []byte e información de tipo implícita

  • El tipo de un token JSON puede saberse por su primer carácter
    • {, }: inicio y fin de objeto
    • [, ]: inicio y fin de arreglo
    • t: true
    • f: false
    • n: null
    • ": cadena
    • -, 0~9: número
  • La API Decoder.NextToken de pkg/json no convierte la entrada []byte en valores de Go; en cambio, devuelve directamente como subslices los bytes de la entrada que representan el token
  • El primer byte del []byte devuelto indica el tipo del token
  • Esta API tiene restricciones
    • La salida no es una copia, sino un subslice de la entrada, por lo que su tiempo de vida es limitado
    • Esto se parece a la API de bufio.Scanner
    • Si se quiere manejar con más comodidad el tipo del token o el valor real de una cadena o número, hace falta una abstracción de nivel superior

Lectura eficiente: byteReader

  • El enfoque tradicional con io.Reader.Read copia los datos del reader al búfer, y esa copia también tiene costo
  • io.Reader.Read deja la gestión del búfer al llamador
    • Si se lee de a un byte, puede hacer falta espacio para guardar bytes ya consumidos o retroceder
    • Si se lee en un búfer grande y luego se busca el inicio y fin del token, cuando el token no termina dentro del búfer se necesita mucho trabajo de gestión, copias y expansión del búfer
  • Como alternativa se usa byteReader, inspirado en iopipe de Steven Schveighoffer y en ideas de Phil Pearl
  • byteReader ofrece una ventana deslizante sobre io.Reader; se parece a bufio.Reader, pero con una API más eficiente
    • window() devuelve la ventana actual de datos aún no leídos
    • release(n) descarta los primeros n bytes de la ventana
    • extend() lee más datos del reader subyacente y amplía la ventana
  • El benchmark de búsqueda de espacios en blanco es la línea base que visita cada carácter y solo comprueba si es espacio en blanco; en varias entradas alcanza alrededor de 2.04~2.07GB/s
  • El código de ejemplo del contador de espacios en blanco está en github.com/davecheney/whitespace

Optimizaciones del scanner

  • Scanner.Next salta el espacio en blanco intermedio, identifica el token por el primer carácter de la ventana y luego lee hasta el final del token
  • El rendimiento inicial de Scanner.Next era aproximadamente de 1/4 a 2/5 de la línea base de espacios en blanco
    • Ejemplo: Scanner/canada 510MB/s, citm_catalog 677MB/s, sample 837MB/s
  • La primera optimización consiste en cambiar la actualización del campo s.offset por una variable local offset
    • s.offset vale 0 al entrar y al salir de la función, así que los cambios internos no son visibles externamente
    • Al usar una variable local, el compilador evita escrituras temporales en memoria
    • citm_catalog baja de 2.52ms a 1.80ms, una reducción de 28.46%, y sample baja de 828µs a 528µs, una reducción de 36.24%
  • La razón de que el efecto cambie según la entrada es la diferencia en la cantidad de espacios en blanco
    • canada tiene solo 33 espacios en blanco
    • citm tiene 1,227,563 espacios en blanco
  • La segunda optimización consiste en hacer inlining manual de Scanner.token dentro de Scanner.Next
    • El compilador de Go no puede hacer inline automáticamente de Scanner.token, parseString, parseNumber, Scanner.Next, etc., por el for y la complejidad de las funciones
    • Scanner.Next y Scanner.token se llaman por cada token de entrada, así que hay un costo de dos llamadas de función por token
  • Después del inlining manual, el throughput mejora entre 9% y 24%
    • canada sube de 512MB/s a 642MB/s, un aumento de 24.50%
    • citm_catalog sube de 960MB/s a 1105MB/s, un aumento de 15.16%
    • sample sube de 1.33GB/s a 1.46GB/s, un aumento de 9.11%
  • El efecto de la optimización puede resumirse en dos puntos
    • La actualización de s.offset pasa de una vez por byte a una vez por token
    • Evitar llamadas a función en el hot path puede mejorar el rendimiento

Validación y Decoder.NextToken

  • El scanner por sí solo puede dividir tokens, pero para un procesamiento JSON completo hace falta validación de estado
  • JSON es una máquina de estados y, según el token actual, los tokens siguientes válidos están restringidos
    • Por ejemplo, después de leer {, "username", solo : es válido
  • Decoder.NextToken agrega lógica de estado sobre Scanner.Next para verificar que la secuencia de tokens sea válida
  • El estado se divide en valor, cadena clave de objeto, dos puntos de objeto, valor de objeto, coma de objeto, valor de arreglo, coma de arreglo, estado final, etc.
  • Incluso en la implementación inicial de validación, pkg/json es de 8 a 10 veces más rápido que encoding/json
    • 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

Optimización de transiciones de estado

  • En el centro de Decoder.NextToken hay un switch
  • Un switch general puede implementarse como una serie de if, de modo que una cadena larga de ramas divide el flujo de instrucciones y carga al predictor de saltos del CPU
  • Otra opción sería usar una tabla para buscar el método de estado a partir del valor de estado, pero la implementación de ejemplo no compila debido al loop de inicialización
  • En su lugar, se usa una method expression de Go para guardar directamente en d.state el método, en vez de un valor enumerado de estado
    • Decoder.NextToken hace una llamada directa al método de estado actual, como return d.state(d, tok)
  • Este enfoque de computed goto por sí solo no mejora mucho el rendimiento
    • En algunas entradas casi no hay cambios y en twitter, code, example es ligeramente más lento
    • sample mejora 1.15%
  • Este cambio sí habilita la siguiente optimización: outline

Outline y eliminación de bounds checks

  • Después del outline, Decoder.NextToken solo hace return d.state(d), y cada método de estado llama directamente a d.scanner.Next()
  • Como tok ya no se pasa como argumento a los métodos de estado, se reducen 3 words en la pila de llamadas
  • Al quedar la verificación len(tok) < 1 y el switch tok[0] dentro de la misma función, se vuelve posible la eliminación de bounds checks
    • Antes, la verificación de len(tok) estaba en Decoder.NextToken y los métodos de estado se llamaban mediante method expressions, así que no se hacían inline
    • Por eso, tok[0] dentro del método de estado necesitaba un bounds check
    • Si la verificación de longitud ocurre dentro de la misma función, el compilador puede demostrar que tok tiene longitud mínima 1
  • Decoder.NextToken también se simplifica lo suficiente como para poder hacerse inline
    • En vez de ver dec.NextToken(), el llamador termina viendo, en la práctica, una llamada directa al método de estado actual
    • Se elimina el costo de la llamada de función

Resultados finales de benchmark

  • El pkg/json.Scanner de nivel más bajo realiza tokenización en streaming sin asignaciones si se le da un búfer de algunos 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 es 2 a 3 veces más rápido que encoding/json.Decoder.Token
    • 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 tiene muchas menos asignaciones y es de 8 a 10 veces más rápido
    • 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 la API de más alto nivel, pkg/json puede hacer unmarshal a objetos de Go del mismo modo que 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
  • El enlace de la charla está en dave.cheney.net/paste/gophercon-sg-2023.html, y el código está en github.com/pkg/json

Temas que deja el diseño

  • Las asignaciones afectan el rendimiento

    • Aunque el GC asigne rápido y recolecte con eficiencia, no asignar siempre es más rápido
    • El diseño de la API puede eliminar asignaciones
    • La mayor parte de la mejora de velocidad de este paquete viene de reducir asignaciones
    • El tiempo que no se usa en la ruta de asignación en heap ni en los ciclos del GC se dedica al escaneo
    • La API de encoding/json.Decoder exige asignaciones porque devuelve valores primitivos como interface{}
    • Los valores escapan al heap y en la práctica se convierten en punteros a esos valores
    • En procesamiento de datos, las asignaciones pueden ser el mayor costo de rendimiento del algoritmo
    • Reducir con cuidado el costo por byte y el costo por token es el segundo factor más importante en la mejora de rendimiento
    • Es importante pasar de llamadas a función por byte a llamadas a función por token
    • La idea de partida era que encoding/json podría ser más lento por su API, y si se puede aceptar otra API, es posible obtener 2 a 3 veces más rendimiento en algunas rutas de unmarshal y de 8 a 10 veces más en tokenización

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-11-06
Comentarios en Hacker News

  • Se ve bastante bien. Ya he hecho demasiados parsers de JSON a lo largo de mi carrera, pero está muy bueno tener una referencia que muestre paso a paso cómo diseñar un parser de JSON razonable y rápido.
    Dicho eso, JSON no necesita necesariamente un tokenizador explícito. Se puede eliminar el concepto de token y fusionar por completo el parsing y la tokenización. Normalmente se hace así y todo queda más simple.
    En lenguajes como ECMAScript es mucho más difícil, porque hay casos como las funciones flecha que parecen un subconjunto de una gramática de expresiones entre paréntesis, y solo se confirman según aparezca =>, así que puede hacer falta una vista previa arbitrariamente larga.

    • Me pregunto en qué habrás trabajado para que sea posible eso de “hice demasiados parsers de JSON” a lo largo de tu carrera.

  • Es un buen artículo para seguir paso a paso y deja bien claro el flujo de cómo hacerlo si uno quisiera implementarlo.
    Si en producción te importa el rendimiento puro, también vale la pena ver el https://github.com/simdjson/simdjson de Daniel Lemire. También está el port para Go de MinIO: https://github.com/minio/simdjson-go

    • Si el formato JSON es siempre el mismo, puede que se logre algo mejor que con un parser JSON genérico.
    • Hace tiempo comparé el rendimiento de varios parsers JSON y los parsers basados en SIMD fueron decepcionantemente lentos para lo que esperaba.
    • La biblioteca JSON más rápida en Go la hizo la empresa detrás de TikTok.
    • simdjson no ocupa el primer lugar desde hace muchísimo tiempo.

  • Lo que aprendí haciendo parsers JSON rápidos tiene bastante mezcla de particularidades de cada lenguaje, pero generalizando sería algo así:
    En la tokenización hay que evitar las asignaciones en el heap. Conviene que el tokenizador devuelva structs asignados en la pila, o que sea una función que devuelva tokens int64 con la posición inicial, longitud y desplazamientos del tipo de token empaquetados.
    En el parsing también hay que evitar asignaciones en el heap, y para clientes que quieran trabajar sobre slices del buffer se puede ofrecer una interfaz como getString(key String).
    Al deserializar hacia objetos cuyos campos se conocen en tiempo de compilación, normalmente se genera un switch por longitud de clave antes de comparar valores de string.
    En pipelines de datos que procesan mucho JSON, solo elegir la biblioteca JSON podía producir una diferencia de rendimiento de 3 a 10 veces, y los parsers principales por lo general intentan asignar objetos.
    Si las clases a serializar y deserializar se conocen en tiempo de compilación, Jackson de Java funciona bastante bien, pero con código cuidadoso y profiling se le puede sacar como 2x más.
    En cambio, si procesas JSON arbitrario, los parsers convencionales intentan hacer muchas asignaciones, así que un parser propio más invasivo puede evitarlas, y la ganancia de rendimiento se vuelve enorme cuando procesas de miles a millones de objetos por segundo.

  • Hice un tokenizador y parser de GraphQL con un enfoque parecido, y también es sin asignaciones de memoria y bastante rápido. Si quieren ver el código, está en https://github.com/wundergraph/graphql-go-tools

    • Mi engendro raro también podría interesar: https://github.com/graph-guard/gqlscan
      Di una charla sobre este tema, pero por desgracia no quedó grabada. Casi me vuelvo loco intentando exprimir Go al máximo :D
    • Me pregunto qué tan grande es este problema en un servidor GQL basado en listas de permitidos, donde todas las queries ya se conocen de antemano. Se podría cachear o recordar el resultado del parsing del AST, así que parecería que el problema de rendimiento solo existe durante los primeros minutos tras iniciar el contenedor.
      O me pregunto si también afecta de otras maneras.

  • En n2[1] necesitábamos un tokenizador rápido y nos topamos con el mismo problema de generación de basura. Básicamente, se mezclaba un conjunto de tokens constantes como json.Delim con strings que sí provocaban asignaciones.
    Una solución que me parece bastante buena es hacer el tokenizador genérico sobre algún T, recibiendo una función que convierta slices de bytes a T, y usar T en lugar de strings.
    Así, cuando el llamador ya tiene una representación más eficiente, por ejemplo una con menos asignaciones, puede pasarla; y al mismo tiempo en tests unitarios se puede usar cómodamente la función identidad para probar el tokenizador.
    En cierto sentido esto se parece a fusionar tokenizador y parser en tiempo de compilación, pero gracias a los genéricos el tokenizador puede mantener la separación por capas sin conocer la representación del parser.
    [1] https://github.com/evmar/n2

  • Se puede mejorar la biblioteca estándar con un mejor diseño de API, pero al hacer un parser totalmente de streaming es prácticamente difícil no dejar structs medio llenos antes de detectar un error y salir a mitad del proceso. Parece que la biblioteca estándar también tomó esto como una restricción explícita de diseño.

  • Puede que se me haya pasado algo, pero el autor repite que hizo un parser de streaming sin explicar qué significa eso en la práctica.
    En particular, no explica cómo manejó claves repetidas en una “tabla hash”. Si cuando aparece una clave repetida llama dos veces al código de destino, o si espera a leer toda la “tabla hash” antes de llamar al código de destino.
    En mi opinión, JSON es jerárquico, no se conoce su longitud por adelantado y, sobre todo, tiene claves repetidas, así que por naturaleza no es apto para streaming.
    Se podrían hacer algunos subconjuntos de JSON más amigables con streaming, pero si vas a hacer eso, no veo para qué arreglar JSON. Si la solución pasa por cambiar JSON, entonces probablemente convenga usar otro formato que no sea JSON.

  • Qué bueno ver que mencionaron a Phil Pearl.
    También vale la pena mirar https://github.com/bytedance/sonic

  • Sorprende que no haya manera de decir “de verdad, inlinea esta función” para funciones demasiado grandes como para ser inlineadas automáticamente.
    Da la impresión de que operaciones básicas de contar y buscar espacios en blanco serían mucho más rápidas si se vectorizaran con SIMD, aunque entiendo que eso ya se sale del alcance del autor.

    • Claro que se puede forzar inline.

  • La frase “no es realista esperar poder cargar toda la entrada en memoria” es falsa para la mayoría de las aplicaciones.

    • La mayoría de las aplicaciones leen JSON desde la red, y eso es un stream. Incluso si el JSON es relativamente pequeño, bufferizar todo el request en memoria y andar manoseándolo aumenta bastante la latencia.
    • Sí, pero en aplicaciones que hacen transformaciones tipo ETL sobre conjuntos de datos grandes, el streaming es una estrategia tremendamente útil.
      Se podría decir que Go no es la herramienta adecuada para ese trabajo, pero con este tipo de optimizaciones no veo por qué no podría serlo.
    • Si vas a crear una biblioteca, deberías dejar claras sus limitaciones o soportar streaming.
      He tenido que pasarle datos JSON de tamaño de gigabytes a herramientas así que agradezco un parser de streaming. Además, que soporte streaming también es una señal de que el autor conoce varios casos de uso y hace mejor ingeniería.
      La memoria solo es barata y casi gratis en teoría; en la práctica no lo es.
    • Si te conforma con que “quepa en disco”, ¿mmap() no sería también una opción válida? Lo de necesitar streaming real sería aparte, por ejemplo cuando quieres procesar temprano datos del principio en un solo archivo JSON, como si fuera un flujo de transacciones o trabajos.
    • ¿También estás contando el cuerpo de una petición HTTP como parte de la entrada?