Probabilità di collisione di ObjectId vs UUID in un sistema distribuito di grandi dimensioni

Considerando che un UUID rfc 4122 (16 byte) è molto più grande di un ObjectId MongoDB (12 byte), sto cercando di scoprire come confrontare la loro probabilità di collisione.

So che è qualcosa di abbastanza improbabile , ma nel mio caso la maggior parte degli ID verrà generata all’interno di un gran numero di client mobili, non all’interno di un insieme limitato di server. Mi chiedo se in questo caso ci sia una preoccupazione giustificata .

Rispetto al caso normale in cui tutti gli ID sono generati da un numero limitato di client:

  • Potrebbero essere necessari mesi per rilevare una collisione dalla creazione del documento
  • Gli ID sono generati da una base di clienti molto più ampia
  • Ogni cliente ha un tasso di generazione ID inferiore

nel mio caso la maggior parte degli ID verrà generata in un numero elevato di client mobili, non all’interno di un gruppo limitato di server. Mi chiedo se in questo caso ci sia una preoccupazione giustificata.

Mi sembra un’architettura pessima. Stai usando un’architettura a due livelli? Perché i client mobili hanno accesso diretto al db? Vuoi veramente fare affidamento sulla sicurezza basata sulla rete?

Ad ogni modo, alcune riflessioni sulla probabilità di collisione:

Né UUID né ObjectId si basano sulla loro dimensione pura, ovvero entrambi non sono numeri casuali, ma seguono uno schema che tenta di ridurre sistematicamente la probabilità di collisione. In caso di ObjectIds, la loro struttura è :

  • 4 byte secondi da unix epoca
  • ID macchina a 3 byte
  • ID processo a 2 byte
  • Contatore a 3 byte

Ciò significa che, contrariamente agli UUID, gli ObjectId sono monotoni (eccetto entro un secondo), che è probabilmente la loro proprietà più importante. Gli indici monotoni faranno riempire il B-Tree in modo più efficiente, consentiranno il paging con id e permetteranno un ‘ordinamento predefinito’ con id per rendere i cursori stabili e, naturalmente, hanno un timestamp facile da estrarre. Queste sono le ottimizzazioni di cui dovresti essere consapevole e possono essere enormi.

Come puoi vedere dalla struttura degli altri 3 componenti, le collisioni diventano molto probabili se stai facendo> 1k inserts / s su un singolo processo (non è realmente ansible, nemmeno da un server), o se il numero di macchine cresce passato circa 10 (vedi problema di compleanno), o se il numero di processi su una singola macchina diventa troppo grande (poi di nuovo, quelli non sono numeri casuali, ma sono veramente unici su una macchina, ma devono essere abbreviati a due byte ).

Naturalmente, perché si verifichi una collisione, devono corrispondere a tutti questi aspetti, quindi anche se due macchine hanno lo stesso hash della macchina, sarebbe comunque necessario che un client inserisca lo stesso valore contatore nello stesso esatto secondo e nello stesso processo id, ma sì, questi valori potrebbero collidere.

Diamo un’occhiata alle specifiche per “ObjectId” dalla documentazione :

Panoramica

ObjectId è un tipo BSON a 12 byte, costruito utilizzando:

  • un valore di 4 byte che rappresenta i secondi dall’epoca Unix,
  • un identificatore macchina a 3 byte,
  • un ID di processo a 2 byte e
  • un contatore da 3 byte, che inizia con un valore casuale.

Consideriamo questo nel contesto di un “client mobile”.

Nota: il contesto qui non significa utilizzare una connessione “diretta” del “client mobile” al database. Questo non dovrebbe essere fatto. Ma la generazione “_id” può essere fatta semplicemente.

Quindi i punti:

  1. Valore per i “secondi dall’epoca”. Questo sarà abbastanza casuale per richiesta. Quindi impatto minimo sulla collisione solo su quel componente. Anche se in “secondi”.

  2. “Identificatore macchina”. Quindi questo è un client diverso che genera il valore _id . Questo sta rimuovendo la possibilità di ulteriori “collisioni”.

  3. Il “processo id”. Quindi, laddove è accessibile a seed (e dovrebbe essere), allora il _id generato ha più possibilità di evitare la collisione.

  4. Il “valore casuale”. Così un altro “client” è riuscito in qualche modo a generare tutti gli stessi valori di cui sopra e comunque è riuscito a generare lo stesso valore casuale.

La linea di fondo è, se questo non è un argomento sufficientemente convincente da digerire, quindi semplicemente fornire le proprie voci “uuid” come valori della “chiave primaria”.

Ma IMHO, questa dovrebbe essere una giusta argomentazione convincente per considerare che gli aspetti di collisione qui sono molto ampi. Per non dire altro.

L’argomento completo è probabilmente solo un po ‘”troppo ampio”. Ma spero che questo allontani un po ‘di più la considerazione da “Abbastanza improbabile” e verso qualcosa di un po’ più concreto.