Playing Around with Unique Random Keys
December 07, 2019I had a project recently where I was trying to decide the optimal length for a nice human readable key, while making it unlikely to have collisions while keeping it semi-unguessable.
I wrote the code below so I could play around with different character sets, key lengths, and number of keys while seeing how those affected the timing and likelihood of collisions. The project allowed for retrying in the case of a collision, so this code below allows for those with a random delay to lookup whether a key has been taken already.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const assert = require("assert"); | |
| const { | |
| toPairs, | |
| toArray, | |
| countBy, | |
| times, | |
| random, | |
| snakeCase | |
| } = require("lodash"); | |
| const { | |
| KEY_LENGTH, | |
| ITERATIONS, | |
| MAX_RETRIES, | |
| DELAY_LOOKUP_MIN, | |
| DELAY_LOOKUP_MAX, | |
| CHAR_SET | |
| } = process.argv.slice(2).reduce( | |
| (acc, k, i, list) => { | |
| if (i % 2 > 0) return acc; | |
| const key = snakeCase(k.slice(2)).toUpperCase(); | |
| const value = list[i + 1]; | |
| acc[key] = /^\d+$/.test(value) ? Number(value) : value; | |
| return acc; | |
| }, | |
| { | |
| KEY_LENGTH: 4, | |
| ITERATIONS: 923521, | |
| MAX_RETRIES: Infinity, | |
| DELAY_LOOKUP_MIN: 0, | |
| DELAY_LOOKUP_MAX: 1, | |
| // Less ambiguous character set (no o, 0, 1, l, i, etc) | |
| CHAR_SET: "abcdefghjkmnpqrstuvwxyz23456789" | |
| } | |
| ); | |
| assert.ok( | |
| ITERATIONS <= Math.pow(CHAR_SET.length, KEY_LENGTH), | |
| "Iterations is too big for the max of char set and key length" | |
| ); | |
| const hrtimeN = hrtime => hrtime[0] * 1e9 + hrtime[1]; | |
| const hrtimeM = hrtime => hrtimeN(hrtime) / 1e6; | |
| const hrtimeS = hrtime => hrtimeM(hrtime) / 1e3; | |
| const sleep = time => { | |
| const stop = process.hrtime(); | |
| while (hrtimeM(process.hrtime(stop)) < time) {} | |
| return true; | |
| }; | |
| const generateKey = (length = KEY_LENGTH) => | |
| times(length, () => CHAR_SET.charAt(random(0, CHAR_SET.length - 1))).join(""); | |
| class DelayMap extends Map { | |
| has(key) { | |
| if (DELAY_LOOKUP_MAX) { | |
| sleep(random(DELAY_LOOKUP_MIN || 0, DELAY_LOOKUP_MAX)); | |
| } | |
| return super.has(key); | |
| } | |
| } | |
| const keys = new DelayMap(); | |
| const tryGenerateKey = () => { | |
| let key = null; | |
| let tries = 0; | |
| do { | |
| tries++; | |
| key = generateKey(); | |
| if (!keys.has(key)) { | |
| return { key, tries }; | |
| } | |
| if (tries >= MAX_RETRIES) { | |
| assert.fail(`Exceeded max retries ${MAX_RETRIES}`); | |
| } | |
| } while (true); | |
| }; | |
| const start = process.hrtime(); | |
| for (let i = 0; i < ITERATIONS; i++) { | |
| const startKey = process.hrtime(); | |
| const { key, tries } = tryGenerateKey(); | |
| keys.set(key, tries); | |
| const endKey = process.hrtime(startKey); | |
| console.log(key, tries, keys.size, `${hrtimeM(endKey)}ms`); | |
| } | |
| assert.equal(keys.size, ITERATIONS); | |
| const end = process.hrtime(start); | |
| const countByTries = toPairs(countBy(toArray(keys.values()))) | |
| .map(v => v.join(" ")) | |
| .join("\n"); | |
| console.log("-".repeat(40)); | |
| console.log(countByTries); | |
| console.log(`${hrtimeS(end)}s`); |