Pruebas de Estrés de Estado Mundial del Nodo RIF Consensus

Introducción

En 2016, RSK propuso la Unitrie como una alternativa a Merkle Patricia Trees para modelar el estado mundial de Ethereum (ver Ethereum Yellow Paper (Informe técnico de Ethereum), Apéndice D). A partir de enero de 2020, hemos agregado como característica opcional Unitrie al Nodo RIF Consensus de RSK (basado en el código de Besu ). En consecuencia, los usuarios ahora pueden elegir entre dos implementaciones de estado mundial:

1. Estado mundial de Besu, como se describe en el informe técnico.
2. Estado mundial de Unitrie, respaldado por Unitrie.

Tener la oportunidad de ejecutar un nodo RIF Consensus de dos implementaciones de estado mundial diferentes, nos permite estar en condiciones de comparar los méritos de cada variante de estado mundial. En este artículo compararemos ambas implementaciones, analizando los tiempos de construcción/búsqueda y la capacidad de asignación de cuentas antes de agotar el almacenamiento disponible.

Experimento 1: Tiempos de construcción y búsqueda

Para analizar los tiempos de construcción y búsqueda, ejecutamos un punto de referencia que consiste en agregar una cantidad determinada de cuentas a un estado mundial de Ethereum inicialmente vacío y hacer cambios (es decir, almacenar las cuentas creadas en trie/Unitrie del estado mundial) cincuenta veces durante la ejecución del punto de referencia. Una vez que todas las cuentas están asignadas, buscamos un millón de cuentas en función de dos variantes: 

1. Búsqueda de un millón de cuentas existentes (todas las cuentas encontradas).
2. Búsqueda de un millón de cuentas aleatorias (no se encontró ninguna cuenta en la práctica).

El punto de referencia finalmente informa los tiempos de construcción y búsqueda. Ejecutamos el punto de referencia en un almacenamiento heap Java de 4 Gb durante un intervalo que oscila entre 3 millones y 10 millones de cuentas de propiedad externa. Manejamos la varianza ejecutando el punto de referencia seis veces para cada cantidad de cuentas. La siguiente tabla muestra los tiempos promedio de construcción y búsqueda para 3 millones, 6 millones y 9 millones de cuentas. CT significa tiempo de construcción, ELT significa tiempo de búsqueda de cuentas existentes y RLT significa tiempo de búsqueda de cuentas aleatorias. Todos los tiempos se calculan en segundos.

Tabla 1. Tiempos de construcción y búsqueda

Nuestra implementación de Unitrie está diseñada para ser eficiente en la memoria, en la mayoría de los casos intercambiando felizmente el tiempo de ejecución por un menor consumo de memoria. Esta elección hace que Unitrie se compare desfavorablemente con el trie de Ethereum cuando se trata de tiempos de búsqueda: Unitrie es 1.2 a 1.8 veces más lento. Sin embargo, vale la pena cuando se considera la cantidad de cuentas asignadas. Unitrie puede manejar 9 millones de cuentas en la memoria, mientras que la implementación del estado mundial de Besu apenas alcanza la barrera de los 6 millones. En efecto, construir un trie con 6 millones de cuentas es 1.47 veces más lento para el trie clásico. Esto demuestra que Besu está controlando la JVM para operar en el umbral de los 6 millones de cuentas.

 

Tabla 2. Rendimiento de construcción y búsqueda

La tabla 2 resume el rendimiento de la construcción y la búsqueda. El acrónimo CTp es la abreviatura de Construction Throughput (rendimiento de construcción), y mide la cantidad de actualizaciones del estado mundial de Unitrie/Ethereum por segundo. De manera similar, ELTp y RLTp son abreviaturas de Exiting Account Lookup (búsqueda de cuenta saliente) y Random Account Lookup Throughput (rendimiento de búsqueda de cuenta aleatoria) (búsquedas por segundo), respectivamente. En términos generales, Unitrie puede realizar entre el 55% y el 80% de las operaciones que el estado mundial de Besu realizaría en un período de tiempo determinado. Notablemente y debido a la basura, el rendimiento de Unitrie se convierte en 1.5 veces el rendimiento del estado mundial de Besu al insertar 6 millones de cuentas. Además, para esa cantidad de cuentas, el rendimiento de búsqueda de Unitrie respecto de un millón de elementos aleatorios coincidía con el estado mundial de Besu. 

Tenga en cuenta que el rendimiento de búsqueda es de 67,000 búsquedas/segundo en el peor de los casos (9 millones de cuentas, búsqueda de cuentas existentes). Para convencernos de que esto es aceptable, consideremos la operación BALANCE (saldo), cuyo costo es de 400 Gas. Dado el límite de gas actual de un bloque RSK de gas de 6.8 millones, idealmente puede ejecutar operaciones de BALANCE de 6.8 millones/400 = 17 mil en un bloque; incluso a 67 mil búsquedas por segundo, la unidad funcionará en 0.25 segundos, suponiendo que el trie esté almacenado en la memoria.

Las figuras 1, 2 y 3 representan respectivamente la construcción y los tiempos de búsqueda de cuentas existentes/aleatorias al asignar cuentas en el rango [3 millones, 10 millones]. Los gráficos muestran la tendencia central y los intervalos de confianza para cada punto de datos. Tenga en cuenta que, para un almacenamiento heap Java de 4Gb, la Unitrie comienza a deshacerse en el umbral de los 9 millones de cuentas (cf., el estado mundial de Besu, se deshace en el umbral de los 6 millones). Además, Unitrie exhibe intervalos de confianza más amplios. Esto se puede atribuir a la implementación de Unitrie, que almacena rutas compartidas como referencias suaves; por lo tanto, agrega de manera no probabilista la sobrecarga del recálculo de rutas en tiempo de ejecución.

Experimento 2: Cuentas de contrato

Unitrie almacena cada cuenta con una clave derivada de su hash de dirección. Por construcción, las claves de cuenta tienen un prefijo aleatorio y una longitud equivalente, por lo cual el resultado será en promedio un árbol binario equilibrado, con cuentas en las hojas. Esto significa que N cuentas de propiedad externa requerirán 2N – 1 nodos.

Al considerar las cuentas contractuales, la capacidad de almacenamiento de Unitrie se reducirá necesariamente en relación con el cálculo anterior. Esto se debe a que Unitrie almacena el código como el hijo derecho del nodo de cuenta correspondiente. Por lo tanto, para N cuentas donde α es la relación entre el contrato.

Figura 1. Tiempo de construcción del estado mundial

Figura 2. Tiempos de búsqueda (cuentas existentes)

Figura 3. Tiempos de búsqueda (cuentas aleatorias)

y cuentas de propiedad externa, el tamaño de Unitrie se convierte en (2 + α) N – 1 nodos. Esto varía de 2N – 1 nodos cuando α = 0 (por lo tanto, sumando el cálculo inicial para N cuentas de propiedad externa) a 3N – 1 nodos cuando α = 1 (todas las cuentas son contratos). Por el contrario, el estado mundial de Ethereum almacena el código de cuenta fuera del trie, por lo que la capacidad de almacenamiento del trie no se verá afectada al considerar las cuentas de contrato.

Para medir la variación de la capacidad de almacenamiento de Unitrie inducida por diferentes valores de α, ejecutamos un punto de referencia asignando tantas cuentas como fuera posible en un almacenamiento heap Java de 4 Gb antes de la eliminación. Ejecutamos el experimento con varios valores de α en el intervalo [0,1]. El punto de referencia utiliza un contrato ERC20 de 2114 bytes del mundo real para el código de cuenta. La figura 4 muestra los resultados, estableciendo α = 0.8 como el punto donde Unitrie cruza la capacidad máxima de almacenamiento del estado mundial de Besu Ethereum. También muestra el rango operativo de Unitrie en un almacenamiento heap de 4 Gb: puede almacenar entre 9.5 millones/9 millones de cuentas de propiedad externa (α = 0) y 4.9 millones de cuentas de contrato (α = 1).

Figura 4. Variación de capacidad de almacenamiento inducida por cuentas de contrato

Conclusiones

Unitrie cambia el tiempo de cálculo por consumo de memoria. Las figuras 2 y 3 muestran que los tiempos de búsqueda de Unitrie son de 1.5 a 2 veces más lentos para las cuentas en el rango [3 millones, 5 millones]. Sin embargo, esa diferencia se desvanecería en un entorno en el que el estado mundial de Besu termina leyendo nodos del disco porque no puede almacenar lo suficiente del estado mundial en la memoria. En ese caso, la latencia de E/S de disco dominaría los tiempos de búsqueda. Nuestros experimentos muestran que Unitrie puede almacenar en un almacenamiento heap de 4 Gb un estado mundial que consta de 9 millones de cuentas de propiedad externa, mientras que el estado mundial de Besu comienza a degradarse en el límite de las 6 millones de cuentas. En general, Unitrie tiene un mayor potencial para evitar E/S de disco, a expensas de búsquedas más lentas 1.8X (en el peor de los casos) en comparación con el estado mundial de Besu.

Al considerar las cuentas de contrato, la capacidad de almacenamiento se determina en función de α, la relación entre el contrato y las cuentas de propiedad externa. Cuanto menor sea el valor de α, más nodos pueden almacenarse en la memoria, lo que maximiza las posibilidades de evitar la latencia de E/S del disco. El experimento dos muestra que la capacidad de almacenamiento de Unitrie se mantiene por encima de la de Besu para el valor α <0.8.

¿Qué es una estimación para α? A partir de noviembre de 2020, Etherscan informa 80.28 millones de cuentas únicas en Mainnet. En la misma fecha, la cantidad de cuentas de contrato era de 12.4 millones. Eso arroja un α = 0.154. Al momento de la redacción de este documento, Mainnet cuenta con 94.14 millones de direcciones únicas. Suponiendo de manera poco realista que cada cuenta creada desde noviembre de 2020 fuera un contrato, eso arroja un límite superior extremadamente sobreestimado para α = 0.28. Aun así, ¡ese valor aun se encuentra en la zona de confort de Unitrie!

Apéndice A: ejecución de los experimentos

Todo el código del experimento está alojado en el proyecto nodo RIF Consensus, y requiere JDK 11 o posterior. Después de clonar el proyecto, puede ejecutar la prueba de estrés de Unitrie o la prueba de estado mundial clásica de Ethereum ingresando a la carpeta raíz del proyecto y ejecutando:

Where accounts_to_create define el número de cuentas a crear, y el parámetro alpha_ratio corresponde a la relación entre el contrato y las cuentas de propiedad externa definidas en el Experimento dos.

Realizamos nuestros experimentos en MacBook Pro con un procesador Intel i5 2.3 GHz de doble núcleo, 16Gb de RAM y un SSD de 250GB. Todos los experimentos se ejecutaron en un almacenamiento heap JVM de tamaño máximo de 4Gb, utilizando el recolector de basura G1.