Escribimos nuestro propio generador de ID para aplicaciones móviles / Sudo Null IT News

Hola, mi nombre es Andrey Bogomolov, soy desarrollador de Android en el equipo de Rendimiento de la aplicación Wildberries.

Un día, mientras trabajaba en código, noté el uso de UUID en la interfaz de usuario y me pregunté sobre su impacto en el rendimiento. Las pruebas han demostrado que una solución personalizada puede ser significativamente más rápida que la implementación estándar de UUID de Java.

En este artículo, veremos diferentes enfoques para generar identificadores únicos, compararemos su rendimiento y escribiremos nuestra propia solución optimizada para aplicaciones móviles.

Descargo de responsabilidad: el artículo está más dirigido a estudiar la generación de ID en el desarrollo móvil. El generador de ID del artículo no se utilizó en código real.

Contenido

Análisis de métodos populares de generación de identificaciones.

Los UUID ocupan un lugar especial entre los métodos de creación de identificaciones debido a su versatilidad, escalabilidad y amplia aplicación en la industria. Estas características hacen de los UUID un punto de partida ideal para el análisis.

Los UUID vienen en varias versiones (de 1 a 8), cada una de las cuales tiene sus propias características, lo que los hace adecuados para diferentes escenarios. En la siguiente tabla se muestra una breve estructura.

Estructura de diferentes versiones de UUID

Versiones UUID 1 se crea en función de la hora y la dirección MAC, pero puede revelar información del dispositivo. UUID versiones 2 similar a la primera versión, pero agrega información de dominio, que es útil en sistemas empresariales pero limitada en otras áreas. Versiones UUID 6 mejora la versión 1 al proporcionar una clasificación de tiempo más lógica, pero también puede exponer datos del sistema. Versiones UUID 7 utiliza marcas de tiempo y datos aleatorios, ofreciendo un equilibrio entre unicidad, privacidad y orden, sin depender de la dirección MAC.

UUID versiones 3 y 5 utilice hash para crear identificadores. La versión 3 utiliza MD5 que, aunque elimina la dependencia del hardware, es vulnerable a colisiones, lo que lo hace menos seguro. La versión 5, con hash SHA-1, es más resistente a las colisiones y adecuada para aplicaciones sensibles a la seguridad.

UUID versiones 4 se crea de forma aleatoria, lo que lo hace popular debido a su simplicidad y alto nivel de singularidad sin referencia a los datos del sistema. Versiones UUID 8 le permite almacenar datos arbitrarios, proporcionando flexibilidad de uso.

La versión 4 de UUID es la más utilizada en el desarrollo de Android debido a su implementación estándar en Java (UUID.randomUUID()). Las versiones 4 y 7 parecen ser las más preferibles debido a su simplicidad, seguridad y ausencia de riesgo de divulgación de información del sistema. UUID tiene muchas alternativas creadas por grandes empresas, pero sigue siendo la opción óptima en el desarrollo móvil, ya que es un estándar y equilibrado para tareas comunes.

Comparación de rendimiento

Para analizar el rendimiento de los métodos de generación de ID, se utilizó la biblioteca. com.github.f4b6a3 en Java. Se comparó la implementación estándar de UUID versión 4 en Java (UUID.randomUUID()), así como las versiones UUID 6 y 7. El objetivo era evaluar el impacto del uso de un generador de números aleatorios seguro en la velocidad de generación. Además, la prueba involucró GUID de versiones similares con un generador de números aleatorios desprotegido y un método de generación incremental usando AtomicLong.

La principal diferencia entre protegido (SecureRandom) y desprotegido (Random) mediante generadores de números aleatorios es el nivel de previsibilidad y seguridad. Un generador seguro utiliza algoritmos criptográficamente sólidos para garantizar la imprevisibilidad de los números, mientras que un generador no seguro es predecible y menos seguro. El uso de un generador seguro en las versiones UUID 4 y 7 cumple con la especificación RFC 9562que recomienda un generador criptográficamente sólido (CSPRNG) para máxima seguridad y singularidad.

Se prestó especial atención al tiempo que lleva convertir los identificadores en una cadena, ya que esta es la forma estándar de trabajar con ID en el desarrollo móvil. Aunque los objetos de identificación son más eficientes en cuanto a rendimiento y memoria, las representaciones de cadenas son más fáciles de usar. Por lo general, el UUID se convierte inmediatamente en una cadena cuando se crea para que sea más fácil trabajar con él.

Las pruebas se realizaron en un dispositivo OnePlus 10 Pro con Android 14. Para las mediciones se utilizaron Jetpack Microbenchmark y Kotlin versión 2.0.20-RC. La prueba incluyó 10 ejecuciones, cada una de las cuales incluyó muchas iteraciones (su número lo determina el propio Microbenchmark). El código, el script de inicio de la prueba y las medidas están disponibles en el enlace al final del artículo.

Comparación del tiempo de generación de ID

Los resultados mostraron que las versiones 4 y 7 de UUID tardan más en generarse debido al uso de un generador seguro. La versión 6 de UUID es más rápida porque no depende de la generación de números aleatorios. Los GUID con un generador desprotegido también mostraron una mayor velocidad.

Sin embargo, incluso los GUID resultaron ser 20 o más veces más lentos al generar ID de cadena en comparación con la generación incremental mediante AtomicLong. Esto puede ser aceptable en la mayoría de los escenarios, como cuando se envían datos a análisis o a la funcionalidad de una aplicación estándar. Sin embargo, en el contexto de pantallas con una gran cantidad de usuarios activos, donde cada milisegundo importa, la desaceleración puede degradar la experiencia del usuario y afectar el negocio. Del mismo modo, incluso pequeñas aceleraciones de cientos de nanosegundos en componentes compartidos pueden mejorar significativamente el rendimiento de la aplicación.

Desarrollando su propio método de generación de ID

private val counter = AtomicLong(INITIAL_COUNTER_VALUE)
private val mostSigBits = generateMSB()
private val prefix = mostSigBits.toCompactString() + "-"


private fun generateMSB(): Long {
    val random24Bits = SecureRandom().nextLong() and 0xFFFFFFL
    val currentTimeMillis = System.currentTimeMillis() and 0xFFFFFFFFFFL
    return (currentTimeMillis shl 24) or random24Bits
}


fun newId() = LocalId(
    mostSigBits = mostSigBits,
    leastSigBits = counter.getAndIncrement(),
)


fun newIdString(): String {
    return prefix + counter.getAndIncrement().toCompactString()
}

Comparación de rendimiento final

Como se puede ver en los gráficos a continuación, el método de generación del identificador LocalID mostró una mayor velocidad en comparación con UUID y GUID. Su desempeño resultó ser cercano a la generación incremental vía AtomicLong.

Comparación del tiempo de generación de ID con LocalID

LocalID realiza solo 3 asignaciones al generar una cadena, mientras que diferentes versiones de UUID requieren más de 20:

atómicoLong: 1
identificación local: 3
guid4: 21
guid7: 21
uuid6: 21
uuid4: 22
uuid7: 23

También se hizo una comparación entre LocalID y UUID.randomUUID() en diferentes cantidades de datos. ID local es superior UUID.randomUUID() en términos de tiempo y asignaciones aproximadamente 10 veces.

Comparación del tiempo de generación de LocalId con UUID.randomUUID() para diferente número de iteraciones — Comparación del tiempo de generación de LocalId con `UUID.randomUUID()` para diferentes números de iteraciones

Para HashMap Es importante distribuir las identificaciones de manera uniforme entre los depósitos para minimizar las colisiones y acelerar el acceso a los datos. El coeficiente de variación de distribución de UUID en 1024 depósitos con 1 millón de objetos es del 3,13% para cadenas y del 3,17% para objetos. LocalID tiene tasas más bajas del 2,15% para cadenas y del 0,05% para objetos, lo que indica una distribución más uniforme de LocalID.

Para determinar el índice del depósito, se utiliza un algoritmo de HashMap:

val hash = key.hashCode() xor (key.hashCode() ushr 16)
val bucketIndex = (bucketCount - 1) and hash

El código para calcular el código hash de un objeto LocalID es similar al utilizado para UUID:

(mostSigBits xor leastSigBits).hashCode()

Los ID creados en una ejecución tienen una distribución perfecta debido a que difieren en 1. Los objetos de diferentes ejecuciones se aproximan a una distribución uniforme.

El código de generación de cadenas LocalID utiliza un conjunto de caracteres especiales que proporciona una buena distribución. Aunque se puede mejorar aún más, requerirá un esfuerzo importante. Cuantos más caracteres haya en el conjunto, más corta será la representación de la cadena y más rápido se calculará el código hash, lo que mejora la eficiencia. HashMap.

private const val CHARS = "BJmkQCdLHlPobfKZsiuRqDwtzINTWOYA"
private const val MASK = 0x1FL
private const val BASE32_MAX_LENGTH = 13


fun Long.toCompactString(): String {
    val result = CharArray(BASE32_MAX_LENGTH)
    var number = this
    var index = BASE32_MAX_LENGTH - 1


    do {
        result(index--) = CHARS((number and MASK).toInt())
        number = number ushr 5
    } while (number != 0L)


    return String(result, index + 1, BASE32_MAX_LENGTH - index - 1)
}

Tasa de generación general hashcode() LocalID es comparable a UUIDv4 tanto para el ID de objeto como para el ID de cadena, con una ligera ganancia para el LocalID de cadena debido a su longitud más corta.

Para tareas sencillas, vale la pena utilizar UUIDv4. Es mejor utilizar su identificación muy raramente y sólo en partes críticas de la aplicación. Si es posible, utilice las identificaciones proporcionadas por el backend. Si los datos se almacenan en una base de datos, es preferible utilizar identificadores incrementales de la misma. Si no se utiliza la base de datos y los datos solo se necesitan para otras capas de la aplicación, vale la pena usar LocalID. UUID es adecuado para situaciones en las que se envían datos al servidor, por ejemplo, para análisis o para garantizar la idempotencia de las solicitudes. Sin embargo, puede negociar su propia versión del UUID con el backend para mejorar el rendimiento generando previamente algunas partes del UUID.

Rutas de optimización y más investigaciones.

Puede explorar más a fondo los siguientes temas:

Desarrollo de un método para generar un paquete (conjunto) de ID en una sola llamada.
Un estudio del impacto del ID ordenado por tiempo versus el UUID aleatorio en el rendimiento en SQLite.
Análisis del formato de almacenamiento UUID más eficiente en SQLite (fuentes útiles para comenzar: enlace 1 y enlace 2).

Campo de golf

Todas las medidas y códigos están disponibles en enlace.
Inspiración para este artículo: IncrementingUuidGenerator y Pepino.
RFC 9562 – una especificación que define la estructura de los UUID y recomendaciones para su implementación.
Las implementaciones de UUID (v6 y v7) y GUID (v4 y v7) se toman de la biblioteca. creador de uuid.