JavaScript Math.random duplicate generation

user_6447123 0
Viewed 299

I have a unique field in a SQL table that currently has 200K rows

I use randomString(6, '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ') to insert data on that field, I have too many unique conflict error when I want to insert new rows

In my log , I see that randomString generated HEGDDX string today but it generated in 3 months ago too and I have an error on insert

'0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' has 36 character , I generate 6 length random string, So there is 36^6=2176782336 = 2.17E9 possible cases, So 200K rows in 2 billion has 0.00009 possibility for duplication

Is 0.00009 big enough for too may errors? is Math.random bad random generator? what is alternative for me?

const randomString = function(length, chars) {
  let str = '';
  const charsLen = chars.length;

  for (let i = 0; i < length; i++) {
    str += chars.charAt(Math.floor(Math.random() * charsLen));
  }
  return str;
}
random javascript
2 Answers

At first sight, your implementation seems ok.

The JS builtin Math.random may not be "cryptography-random-safe", but it's fine for your use-case.

The problem lies in the math, it's counter-intuitive that with billions of possibilities you get collisions with a few hundred thousands. This "paradox" is closely related to the birthday paradox. For instance, this blog post is very close to your issue.

Potential solutions

Since it's supposed to be a user-friendly number, you clearly don't want to use a UUID / GUID or such.

Instead I suggest the following options:

  • Use a retry strategy. That may seem a poor hack to fix the problem, but I think it is appropriate in this case. Just catch the DB error for non-unique value on insert, and generate a new one. Limit the retries at 10 times or such, because you want to avoid infinite error loop if something else goes wrong. The caveat of this basic approach is that may lead to some rare slowness if your db itself is slow to respond, for those cases.

  • You could also just load all existing coupons already generated in memory before insert and do the generation-retry in the code instead of waiting an error from db. That would make you read all coupons first, so you'd better index them.

  • If performance is more critical, you could even use a mix of the two: load a global cache of all coupons at regular intervals that fits your case (every hour, every day, etc...), so you can first quickly check in this list, without doing a big query in db. But collision may still happen since some values may have been added in the meantime, so you check for errors and retry.

  • You could also change strategy and don't enforce uniqueness. You need to check this with your requirements, but you could add some fields or a "child" "coupon" table for users.

  • Get some ideas to generate those values in DB here: Generating a random & unique 8 character string using MySQL (it's for MySQL, but some ideas could apply for all DBs)

user_4792510
  1. You can use uuid. I have used it in many applications of mine.
  2. If the rate of data coming is slow, not many requests are coming at the same time on the same server then you can also use the timestamp as an id too.
user_46851500
Related