1

I've been reading on instagram's approach to generate unique identifiers.

Besides remaining content I'd like to understand on of the points their making as a con of client-generated (by client I mean here an app-server, not untrusted userland), specifically:

  • Generally requires more storage space (96 bits or higher) to make reasonable uniqueness guarantees [app-generated ID vs DB generated]

How is current time in millis + shardID + modulo counter in 64bit space (long/bigint) better than app generated something like current time millis + random 23 bits (64bits total)? (So that app generated needs at least 96bits)

1

23 bits means you get a 50% collision at around 3000 Ids per millisecond. So it compares badly against their 1000 per shard per millisecond approach.

Im guessing they need ids for more than just the 25 photos per second they get.

Having said that, I think they have gone for the wrong solution here. a GUID approach would be far superior, the sortablity and size constraints are largely artificial and this quote stands out as a massive red flag for me:

41 bits for time in milliseconds (gives us 41 years of IDs with a custom epoch)

41 years! thats more time that we need right? who's gona worry about those old pics in 30 years? no-one right?

Why are you hardcoding in your own millenium bug?

What's the plan for when that day rolls around, how much will it cost and why arent we just doing it in the first place?

  • Great, thanks, just one last thing, how did you estimate that 23 bits gives a 50% chance of collision at this rate? – canni Nov 11 '18 at 15:30
  • the birthday paradox. apparently 50% is roughly √n – Ewan Nov 11 '18 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.