from Hacker News

Ask HN: How do orgs detect conflicting hashes in sub-second timing?

by adam_ellsworth on 6/26/22, 6:51 AM with 5 comments

Today I was considering how organizations such as bitly, imgur, reddit, and even github handle hash collision prevention.

While for GH it (seems) easier as commit hashes are sufficiently long/unique, for others with character hashes that only span ~6 chars or so, there's bound to be instances where hashes conflict from a statistical standpoint. (iirc reading an article on a hash collision in GH a few years ago here on ycomb)

To my mind these orgs have to have a suite tools/algos requesting information from multiple services, checking whether or not a hash has been taken – and those processes have to optimize for time. (e.g. when a user makes a post, what's a reasonable time to do a lookup?)

So, what are the considerations which need to be made algorithmically to check such collisions while keeping runtime to an acceptable minimum?

  • by verdverm on 6/26/22, 1:06 PM

    Database indexes most likely. Consider GitHub...

    1. Hashes are determined outside of their context, by git.

    2. They store this is a database

    3. Conflicts are so rare that they can be ignored. They must happen within the same repository. If they are in different repos, then it is not a conflict.

  • by frogger8 on 6/26/22, 1:53 PM

    Not sure how these orgs do it but the system design book by Alex Xu uses timestamp + dataCenterID + machineId + sequence number that is reset every millisecond. This integer is then converted to base62.

  • by manx on 6/26/22, 3:39 PM

    If you have different workers to generate ids, give all of them their own ranges in advance. Once a worker used up their range, they can request a new range for their next N (e.g. 100k) ids.

  • by compressedgas on 6/26/22, 8:06 AM

    Do you mean "how do they do unique identifier generation"?

    Most use a combination of precoordination and a database that when an insert fails they just generate new and try again.

  • by ev1 on 6/26/22, 7:33 AM

    what parts specifically of those sites? most are not hashes.