Collision probability of ObjectId vs UUID in a large distributed system

by

in my case most ids will be generated within a large number of mobile clients, not within a limited set of servers. I wonder if in this case, there is a justified concern.

That sounds like very bad architecture to me. Are you using a two-tier architecture? Why would the mobile clients have direct access to the db? Do you really want to rely on network-based security?

Anyway, some deliberations about the collision probability:

Neither UUID nor ObjectId rely on their sheer size, i.e. both are not random numbers, but they follow a scheme that tries to systematically reduce collision probability. In case of ObjectIds, their structure is:

  • 4 byte seconds since unix epoch
  • 3 byte machine id
  • 2 byte process id
  • 3 byte counter

This means that, contrary to UUIDs, ObjectIds are monotonic (except within a single second), which is probably their most important property. Monotonic indexes will cause the B-Tree to be filled more efficiently, it allows paging by id and allows a ‘default sort’ by id to make your cursors stable, and of course, they carry an easy-to-extract timestamp. These are the optimizations you should be aware of, and they can be huge.

As you can see from the structure of the other 3 components, collisions become very likely if you’re doing > 1k inserts/s on a single process (not really possible, not even from a server), or if the number of machines grows past about 10 (see birthday problem), or if the number of processes on a single machine grows too large (then again, those aren’t random numbers, but they are truly unique on a machine, but they must be shortened to two bytes).

Naturally, for a collision to occur, they must match in all these aspects, so even if two machines have the same machine hash, it’d still require a client to insert with the same counter value in the exact same second and the same process id, but yes, these values could collide.

More Related Contents:

  1. Find document with array that contains a specific value
  2. Update field in exact element array in MongoDB
  3. Mongodb sort inner array
  4. Return only matched sub-document elements within a nested array
  5. How to create a GUID/UUID using iOS
  6. MongoDB wildcard in the key of a query
  7. How to create a DB for MongoDB container on start up?
  8. How to access a preexisting collection with Mongoose?
  9. MongoDB field order and document position change after update
  10. MongoDB Full and Partial Text Search
  11. How to enable authentication on MongoDB through Docker?
  12. Mongodb Join on _id field from String to ObjectId
  13. Difference between count() and find().count() in MongoDB
  14. How do I do a “NOT IN” query in Mongo?
  15. How to efficiently perform “distinct” with multiple keys?
  16. Mongo, find through list of ids
  17. Using stored JavaScript functions in the Aggregation pipeline, MapReduce or runCommand
  18. MongoDB – The argument to $size must be an Array, but was of type: EOO / missing
  19. Build a reactive publication with additional fields in each document
  20. Mongodb query specific month|year not date
  21. How to flatten a subdocument into root level in MongoDB?
  22. Push to two separate arrays in one update call in mongodb
  23. How to toggle a boolean field in one document with atomic operation?
  24. How to delete documents by query efficiently in mongo?
  25. Update embedded object inside array inside array in MongoDB
  26. Modify and replay MongoDB oplog
  27. Creating custom Object ID in MongoDB
  28. Return actual type of a field in MongoDB
  29. Sort nested array of objects
  30. How to create a Mongo Docker Image with default collections and data?

Leave a Comment