mongodb - Collision probability of ObjectId vs UUID in a large distributed system -


considering uuid rfc 4122 (16 bytes) larger mongodb objectid (12 bytes), trying find out how collision probability compare.

i know around quite unlikely, in case ids generated within large number of mobile clients, not within limited set of servers. i wonder if in case, there justified concern.

compared normal case ids generated small number of clients:

  • it might take months detect collision since document creation
  • ids generated larger client base
  • each client has lower id generation rate

in case ids generated within large number of mobile clients, not within limited set of servers. wonder if in case, there justified concern.

that sounds bad architecture me. using two-tier architecture? why mobile clients have direct access db? want rely on network-based security?

anyway, deliberations collision probability:

neither uuid nor objectid rely on sheer size, i.e. both not random numbers, follow scheme tries systematically reduce collision probability. in case of objectids, structure is:

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

this means that, contrary uuids, objectids monotonic (except within single second), important property. monotonic indexes cause b-tree filled more efficiently, allows paging id , allows 'default sort' id make cursors stable, , of course, carry easy-to-extract timestamp. these optimizations should aware of, , can huge.

as can see structure of other 3 components, collisions become if you're doing > 1k inserts/s on single process (not possible, not server), or if number of machines grows past 10 (see birthday problem), or if number of processes on single machine grows large (then again, aren't random numbers, unique on machine, must shortened 2 bytes).

naturally, collision occur, must match in all these aspects, if 2 machines have same machine hash, it'd still require client insert same counter value in exact same second , same process id, yes, these values collide.


Comments

Post a Comment

Popular posts from this blog

android - Get AccessToken using signpost OAuth without opening a browser (Two legged Oauth) -

i using signpost oauth access data magento server. have read various tutorials on same , reach point open browser user can enter credentials. however, per requirement have automate part. hence, user should not browser page. have set-up done on server side ( magento ), hit url , returned call page. same through program in android. i have tried below, consumer = new commonshttpoauthconsumer(key, secret); provider = new commonshttpoauthprovider(oauth_init_url,access_token_url, authorize_url); try { provider.retrieverequesttoken(consumer, oauth.out_of_band); log.d("tokens" , consumer.gettoken() + " -- " + consumer.gettokensecret()); } and request tokens. dont know how bypass next step. tried directly accessing accesstoken (stupid of me) provider.retrieveaccesstoken(consumer, "mycallback://callback"); no luck, ends in oauth.signpost.exception.oauthnotauthorizedexception: authorization failed (server replied 401). ...
Read more

org.mockito.exceptions.misusing.InvalidUseOfMatchersException: mockito -

getting error org.mockito.exceptions.misusing.invaliduseofmatchersexception: invalid use of argument matchers! 1 matchers expected, 2 recorded. exception may occur if matchers combined raw values: //incorrect: somemethod(anyobject(), "raw string"); when using matchers, arguments have provided matchers. example: //correct: somemethod(anyobject(), eq("string matcher")); at when( getprogramservice .callservice(any(getprogramtype.class))) .thenreturn(jaxbresponse); please explain error , possible resolution the code posted looks fine; don't see problem it. code before or above causing exception. key here: invalid use of argument matchers! 1 matchers expected, 2 recorded. any , used above, doesn't return "special kind of null" or "special kind of getprogramtype"; don't exist. instead, returns null , side effect puts matcher on stack. whe...
Read more

google shop client API returns 400 bad request error while adding an item -

i'm working on solution add items in google shopping market java application. following tutorial real mess because of missing classes of laste release, after setting 1.5-beta maven managed make base example typecheck correctly classes. still can make simple task of adding 1 item. instead of posting whole code i'm posting part creates product feed. private product createproduct(string id) { product product = new product(); product.title = "red wool sweater"; product.content = new content( "text", "comfortable , soft, sweater keep warm on " + "cold winter nights. red , blue stripes."); product.appcontrol = new appcontrol(); product.appcontrol.addrequireddestination("productads"); product.externalid = id; product.lang = "it"; product.country = "it"; product.condition = "nuovo"; product.price = new price("eu...
Read more