Probabilidad de colisión de ObjectId frente a UUID en un gran sistema distribuido

Teniendo en cuenta que un UUID rfc 4122 (16 bytes) es mucho más grande que un MongoDB ObjectId (12 bytes), estoy tratando de averiguar cómo se compara la probabilidad de colisión.

Sé que es algo completamente improbable , pero en mi caso la mayoría de los identificadores se generarán dentro de una gran cantidad de clientes móviles, no dentro de un conjunto limitado de servidores. Me pregunto si en este caso, hay una preocupación justificada .

Comparado con el caso normal donde todos los ID son generados por un pequeño número de clientes:

  • Puede llevar meses detectar una colisión desde la creación del documento
  • Los ID se generan a partir de una base de clientes mucho más grande
  • Cada cliente tiene una tasa de generación de ID más baja

en mi caso, la mayoría de los ID se generarán dentro de una gran cantidad de clientes móviles, no dentro de un conjunto limitado de servidores. Me pregunto si en este caso, hay una preocupación justificada.

Eso me parece una architecture muy mala. ¿Estás usando una architecture de dos niveles? ¿Por qué los clientes móviles tendrían acceso directo a la base de datos? ¿De verdad quieres confiar en la seguridad basada en la red?

De todos modos, algunas deliberaciones sobre la probabilidad de colisión:

Ni UUID ni ObjectId se basan en su gran tamaño, es decir, no son números aleatorios, sino que siguen un esquema que intenta reducir sistemáticamente la probabilidad de colisión. En el caso de ObjectIds, su estructura es :

  • 4 byte segundos desde la época de Unix
  • ID de máquina de 3 bytes
  • ID de proceso de 2 bytes
  • Contador de 3 bytes

Esto significa que, contrariamente a los UUID, los ObjectIds son monótonos (excepto en un solo segundo), que es probablemente su propiedad más importante. Los índices monotónicos harán que el B-Tree se llene de manera más eficiente, permite paginación por id y permite un ‘ordenamiento predeterminado’ por id para hacer que sus cursores sean estables, y por supuesto, llevan una marca de tiempo fácil de extraer. Estas son las optimizaciones que debe tener en cuenta, y pueden ser enormes.

Como se puede ver en la estructura de los otros 3 componentes, las colisiones son muy probables si estás haciendo> 1k inserciones / s en un solo proceso (realmente imposible, ni siquiera desde un servidor), o si el número de máquinas crece más allá de 10 (ver problema de cumpleaños), o si el número de procesos en una sola máquina crece demasiado (de nuevo, esos no son números aleatorios, pero son verdaderamente únicos en una máquina, pero deben acortarse a dos bytes )

Naturalmente, para que se produzca una colisión, deben coincidir en todos estos aspectos, por lo que incluso si dos máquinas tienen el mismo hash de máquina, todavía requeriría que un cliente inserte con el mismo valor de contador en el mismo segundo y el mismo proceso. id, pero sí, estos valores podrían colisionar.

Miremos la especificación para “ObjectId” de la documentación :

Visión de conjunto

ObjectId es un tipo de BSON de 12 bytes, construido utilizando:

  • un valor de 4 bytes que representa los segundos desde la época de Unix,
  • un identificador de máquina de 3 bytes,
  • una identificación de proceso de 2 bytes, y
  • un contador de 3 bytes, comenzando con un valor aleatorio.

Así que consideremos esto en el contexto de un “cliente móvil”.

Nota: El contexto aquí no significa usar una conexión “directa” del “cliente móvil” a la base de datos. Eso no debería hacerse. Pero la generación “_id” se puede hacer de manera muy simple.

Entonces los puntos:

  1. Valor para los “segundos desde época”. Eso va a ser bastante aleatorio por solicitud. Por lo tanto, el impacto mínimo de la colisión solo en ese componente. Aunque en “segundos”.

  2. El “identificador de la máquina”. Entonces este es un cliente diferente que genera el valor _id . Esto está eliminando la posibilidad de una mayor “colisión”.

  3. La “identificación del proceso”. Entonces, cuando eso es accesible para la semilla (y debería ser), entonces el _id generado tiene más posibilidades de evitar la colisión.

  4. El “valor aleatorio”. Entonces, otro “cliente” de alguna manera logró generar todos los mismos valores que antes y aún así logró generar el mismo valor aleatorio.

En pocas palabras, si ese argumento no es lo suficientemente convincente como para digerirlo, simplemente proporcione sus propias entradas “uuid” como valores de “clave principal”.

Pero en mi humilde opinión, ese debería ser un argumento convincente para considerar que los aspectos de colisión aquí son muy amplios. Por decir lo menos.

El tema completo probablemente sea solo un poco “demasiado amplio”. Pero espero que esto mueva la consideración un poco más lejos de “Muy poco probable” y en algo un poco más concreto.