0

What is the methodology for generating a unique ID that minimizes the chance for an overlap?

for(let i = 0; i < <Arbitrary Limit>; i++)
  generateID();

There are a few current solutions, but they are all roundabout ways of solving the problem.

Possible Solution 1: Use a database to generate the new ID. This does not work for me since I would like to do this in the frontend.

Possible Solution 2: Use Math.random()*Math.floor(LIMIT), where LIMIT is a numeric value. This does not work as minimizing the chance for overlap requires a large limit, and thus a massive ID. If working with hundreds of thousands of instances that need an ID, the chance increases greatly.

Possible Solution 3:

'_' + Math.random().toString(36).substr(2, 9);

This is close to working but I believe Math.random() is pseudo-random.

Possible Solution 4: Date.now(). Date.getTime(), etc. This does not work as generating [Date.now(), Date.now()] will cause the same ID. It arguably also needs a long ID to minimize overlap.

I do not require absolutely 0% chance of generating the same ID, I wish to minimize the chance as much as possible without:

  1. Storing a count
  2. Using 'other technology' (no database, no library, etc)
  3. Making a massive ID

This preferrably should be scalabe, eg. This should work for 10 or 1000000 IDs.

Edit: Unique IDs generated locally and without need for communication across users of the frontend. Ex: A component needs to render many instances of the same class and needs a key to assign to it. Keys must be different and upon unmounting the component with its generated keys/instances is removed.

  • Honestly the best way in my opinion is to have the unique ID come from a database. Actually much easier, and it can be auto generated so that you don't have to do things like this. I know this isn't what you prefer, but I don't condone creating unique ID's that aren't going to be stored somewhere. – Michael Jan 13 '21 at 21:52
  • 1
    See my section on [Unique Random Identifiers](https://peteroupc.github.io/random.html#Unique_Random_Identifiers) for advice on which kind of unique identifiers to use. There are many aspects besides uniqueness to keep in mind when generating such identifiers. In your case, one way to proceed, among many others, is to apply a reversible operation on sequential IDs. – Peter O. Jan 14 '21 at 05:02
  • @Peter O. The wording makes me very confused as to the algorithm you're describing.Ex: I have no idea what a "full-period' means. If you can give a walkthrough example of both situations ("random-looking" unique and unique) that would be what I'm looking for. –  Jan 14 '21 at 21:58

1 Answers1

1

It seems you want to generate unique IDs entirely on the front-end and without relying on a backend at all or "storing a count". Then the solution depends, in part, on how many different users you expect will access your application's frontend during its lifetime, and the size of IDs depends on how much you're willing to tolerate the risk of collisions (assuming you're generating IDs at random); for that, see Birthday problem.

Then, depending on the size of IDs you choose, you generate the IDs at random using a cryptographic RNG (such as the function crypto.randomBytes), which is the closest available to "truly" random IDs.

On the other hand, if only few users will access your front end, but each one generates many unique IDs, then you can assign each user a unique value from a central database, because then each front-end computer can use that unique value as part of unique identifiers it generates and ensure that the identifiers are unique across the application without further contacting other computers or the central database.

Notice that there are other considerations as well: You should also consider whether just anyone should access the resource an ID identifies simply by knowing the ID (even without being logged in or authorized in some way). If not, then additional access control will be necessary.

For your purposes, you can try applying sequential IDs. If sequential IDs alone are not adequate, then you can try applying a reversible operation on sequential IDs. One example of this operation is technically called a "linear congruential generator with a power of 2 modulus", such as the ones described in the following pages:

Peter O.
  • 32,158
  • 14
  • 82
  • 96
  • I don't believe this exactly answers my question. I was looking for more of a concrete example of the algorithm(s) in your blog you references when I responded to your comment on the post. I'll accept since it's the best answer so far. –  Jan 15 '21 at 10:15
  • Well, when I reread your question, you asked for generating IDs on the frontend only and without storing any counts or "using a database". With these constraints, my suggestion for doing a reversible operation on sequential IDs (as I wrote in a comment to your question) would not be the best answer, especially since there is virtually no way to coordinate the generation of these sequential IDs among users of the frontend without some form of communication. – Peter O. Jan 15 '21 at 10:36
  • Sorry, I did not add in the fact that I am looking for locally generated IDs that do not need to be communicated across users. Edited the question to contain that. I agree that your solution is adequate for the original question as I did not specify some key elements in the problem. –  Jan 15 '21 at 12:18