3
\$\begingroup\$

I've finally finished these 2 scripts and would like to get some feedback.

  • Seeking feedback on a modernized ULID (Universally Unique Lexicographically Sortable Identifier) generator in Javascript.
  • Reduced size compared to examples on GitHub.
  • Code includes functions for encoding BigInt as Base32, decoding timestamps, and generating ULIDs.
  • Looking for code review and optimization suggestions if it isn't already compliant.

As you can see, Monotonic fills the Set almost twice as fast from sheer uniqueness.

See you later UUID?

Test Results - randomULID()
  
- Processor.....: Intel Xeon W-1390P @ 3.5GHz 32GB RAM
- Duration......: 2.7 sec @ 366,032/s @ 366/ms
- Iterations....: 1,000,000
- Collisions....: 0
- Set Bytes.....: 26,000,000 bytes
- Set Kilobytes.: 25,391 Kilobytes
- Set Megabytes.: 25 Megabytes

- Collision Test complete!
Test Results - randomMULID()

- Processor.....: Intel Xeon W-1390P @ 3.5GHz 32GB RAM
- Duration......: 1.9 sec @ 531,350/s @ 531/ms
- Iterations....: 1,000,000
- Collisions....: 0
- Set Bytes.....: 26,000,000 bytes
- Set Kilobytes.: 25,391 Kilobytes
- Set Megabytes.: 25 Megabytes

- Collision Test complete!

ULID.js

"use strict";
/**
 * Global variables to keep track of the last generated timestamp and random value.
 */
let lastTimestamp = 0n; // Initialize a variable to store the last used timestamp.
let lastRandomValue = 0n; // Initialize a variable to store the last used random value.
/**
 * Crockford's Base32 alphabet for encoding.
 */
const alphabet = "0123456789ABCDEFGHJKMNPQRSTVWXYZ";
/**
 * Encodes a given BigInt number into a Base32 string.
 * @param {bigint} number - The BigInt number to encode.
 * @param {number} length - The length of the encoded string.
 * @returns {string} The Base32 encoded string.
 */
function encodeBase32(number, length) {
  // Initialize an empty string to hold the Base32 output.
  let output = "";
  // Loop `length` times to create the Base32 string.
  for (let i = 0; i < length; i++) {
    // Mask the last 5 bits of `number`, find the corresponding alphabet, and prepend to `output`.
    output = alphabet[Number(number & 0x1fn)] + output;
    // Right-shift `number` by 5 bits, effectively removing the bits that were just processed.
    number >>= 5n;
  }
  // Return the Base32-encoded string.
  return output;
}
/**
 * Decodes the timestamp from a given ULID string.
 * The function decodeTimestamp takes a ULID string ulid and returns a
 * JavaScript Date object representing the timestamp encoded in the first
 * 10 characters (48 bits) of the ULID.
 * @param {string} ulid - The ULID string to decode.
 * @returns {Date} The decoded timestamp as a JavaScript Date object.
 */
function decodeTimestamp(ulid) {
  // 01HAYR6EKZ QDS8N9Y9PPBVG7EQ
  // Extract the first 10 characters (48 bits) from the ULID string, representing the timestamp.
  const timePart = ulid.slice(0, 10);
  // Initialize a BigInt to hold the decoded timestamp.
  let timestamp = 0n;
  // Loop through each character in the time part of the ULID.
  for (const char of timePart) {
    // Left-shift `timestamp` by 5 bits and OR it with the index of `char` in the alphabet, converted to BigInt.
    timestamp = (timestamp << 5n) | BigInt(alphabet.indexOf(char));
  }
  // Convert the BigInt timestamp to Number and return it as a JavaScript Date object.
  return new Date(Number(timestamp));
}
/**
 * Generates a ULID (Universally Unique Lexicographically Sortable Identifier).
 * @returns {Promise<string>} A promise that resolves to a ULID string.
 *
 * - The function `randomULID` asynchronously generates a ULID string by
 *   combining a 48-bit timestamp and 80 bits of cryptographically secure
 *   random data. It returns a Promise that resolves to this ULID string.
 */
async function randomULID() {
  // Get the current timestamp as a BigInt.
  const timestamp = BigInt(Date.now());
  // Create a buffer to hold 10 bytes of random data.
  const randomBuffer = new Uint8Array(10);
  // Populate the buffer with Web Crypto API cryptographically secure random values.
  crypto.getRandomValues(randomBuffer);
  // Initialize a BigInt to hold the random value.
  let randomValue = 0n;
  // Loop through the random buffer.
  for (const byte of randomBuffer) {
    // Left-shift `randomValue` by 8 bits and OR it with each byte, converted to BigInt.
    randomValue = (randomValue << 8n) | BigInt(byte);
  }
  // Encode the timestamp using the encodeBase32 function, 10 characters long.
  const timePart = encodeBase32(timestamp, 10);
  // Encode the random value using the encodeBase32 function, 16 characters long.
  const randomPart = encodeBase32(randomValue, 16);
  // Concatenate the time and random parts to form the ULID, and return it.
  return timePart + randomPart;
}
/**
 * Generates a monotonic MULID (Monotonic Universally Unique Lexicographically Sortable Identifier).
 * @returns {Promise<string>} A promise that resolves to a MULID string.
 *
 * - The function `randomMULID` asynchronously generates a "Monotonic"
 *   MULID string by combining a 48-bit timestamp and 80 bits of
 *   cryptographically secure random data. It ensures that ULIDs generated
 *   in the same millisecond are still unique by incrementing lastRandomValue.
 *   It returns a Promise that resolves to this MULID string.
 *
 */
async function randomMULID() {
  // Get the current timestamp as a BigInt.
  const currentTimestamp = BigInt(Date.now());
  // If the current timestamp equals the last used timestamp,
  if (currentTimestamp === lastTimestamp) {
    // Increment the last random value to ensure uniqueness.
    lastRandomValue++;
  } else {
    // Update the last used timestamp.
    lastTimestamp = currentTimestamp;
    // Create a buffer to hold 10 bytes of random data.
    const randomBuffer = new Uint8Array(10);
    // Populate the buffer with cryptographically secure random values.
    crypto.getRandomValues(randomBuffer);
    // Reset the last used random value.
    lastRandomValue = 0n;
    // Loop through the random buffer.
    for (const byte of randomBuffer) {
      // Left-shift `lastRandomValue` by 8 bits and OR it with each byte, converted to BigInt.
      lastRandomValue = (lastRandomValue << 8n) | BigInt(byte);
    }
  }
  // Encode the last used timestamp using encodeBase32 function, 10 characters long.
  const timePart = encodeBase32(lastTimestamp, 10);
  // Encode the last used random value using encodeBase32 function, 16 characters long.
  const randomPart = encodeBase32(lastRandomValue, 16);
  // Concatenate the time and random parts to form the ULID, and return it.
  return timePart + randomPart;
}
/**
 * Performs a collision test for a given ID generator function.
 *
 * @async
 * @param {number} _iterations - The number of iterations to perform.
 * @param {() => Promise<string>} generator - The generator function for producing IDs.
 * @returns {Promise<string>} A string containing various metrics and results of the test.
 */
async function collisionTest(_iterations, generator) {
  const idSet = new Set();
  let collisions = 0;
  const start = Date.now();
  for (let i = 0; i < _iterations; i++) {
    const newId = await generator();
    if (idSet.has(newId)) {
      collisions++;
    } else {
      idSet.add(newId);
    }
  }
  const end = Date.now();
  // Calculate the duration of the test in milliseconds
  const _durationMiliSecond = (end - start);
  // Calculate the rate of ULID generation per millisecond
  const _idPerMiliSecond = (_iterations / _durationMiliSecond);
  // Calculate the duration of the test in seconds
  const _durationSecond = ((end - start) / 1000);
  // Calculate the rate of ULID generation per second
  const _idPerSecond = (_iterations / _durationSecond);
  // Format the duration in milliseconds to a string with 1 decimal point
  const _durationMiliSecondFormatted = (_durationMiliSecond).toLocaleString('en-US', {
    maximumFractionDigits: 1
  });
  // Format the duration in seconds to a string with 1 decimal point
  const _durationSecondFormatted = (_durationSecond).toLocaleString('en-US', {
    maximumFractionDigits: 1
  });
  // Format the rate per millisecond to a string with 0 decimal points
  const _rateMiliSecondFormatted = (_idPerMiliSecond).toLocaleString('en-US', {
    maximumFractionDigits: 0
  });
  // Format the rate per second to a string with 0 decimal points
  const _ratePerSecondFormatted = (_idPerSecond).toLocaleString('en-US', {
    maximumFractionDigits: 0
  });
  // Format the number of iterations to a string with 0 decimal points
  const _iterationsFormatted = _iterations.toLocaleString('en-US', {
    maximumFractionDigits: 0
  });
  // Define the byte length of a single ULID for use in size calculations
  const ID_FIXED_BYTE_LENGTH = 26;
  // Calculate the total byte length of all the ULIDs stored in the Set
  const _setByteLength = idSet.size * ID_FIXED_BYTE_LENGTH;
  // Format the total byte length to a string with 0 decimal points
  const _setByteLengthFormatted = (_setByteLength).toLocaleString('en-US', {
    maximumFractionDigits: 0
  });
  // Convert the total byte length to kilobytes
  const _setKilobyteLength = _setByteLength / 1024;
  // Format the total kilobyte length to a string with 0 decimal points
  const _setKilobyteLengthFormatted = (_setKilobyteLength).toLocaleString('en-US', {
    maximumFractionDigits: 0
  });
  // Convert the total kilobyte length to megabytes
  const _setMegabyteLength = _setKilobyteLength / 1024;
  // Format the total megabyte length to a string with 0 decimal points
  const _setMegabyteLengthFormatted = (_setMegabyteLength).toLocaleString('en-US', {
    maximumFractionDigits: 0
  });
  // Clear/Remove all ULIDs from this set (Free Memory)
  idSet.clear();
  // The return statement assembles the formatted test results.
  return `
Test Results - ${generator.name}()
  
- Processor.....: Intel Xeon W-1390P @ 3.5GHz 32GB RAM
- Duration......: ${_durationSecondFormatted} sec @ ${_ratePerSecondFormatted}/s @ ${_rateMiliSecondFormatted}/ms
- Iterations....: ${_iterationsFormatted}
- Collisions....: ${collisions}
- Set Bytes.....: ${_setByteLengthFormatted} bytes
- Set Kilobytes.: ${_setKilobyteLengthFormatted} Kilobytes
- Set Megabytes.: ${_setMegabyteLengthFormatted} Megabytes

- Collision Test complete!`;
}
// Initialize Collision Tests
(async () => {
  const ulidTestResults = await collisionTest(1000000, randomULID);
  console.log(ulidTestResults);
  const mulidTestResults = await collisionTest(1000000, randomMULID);
  console.log(mulidTestResults);
})();

\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$

A short review;

this is very interesting, and something I might use on a personal project, it is nice to have sortable UUIDs.

There are, however, far too many comments. I mean..

// Get the current timestamp as a BigInt.
const timestamp = BigInt(Date.now());

I am not a big fan of randomMULID, UUIDs are meant for local processing, and then when we merge into a larger database/collection there will be no collisions. Incrementing lastRandomValue by 1 will help with the local uniqueness, but I fail to see how this can bring Universal uniqueness.

Other than that, very cool, I learned about the crypto object in JS, and the code seems to be lightning fast.

\$\endgroup\$
4
  • \$\begingroup\$ Haha! Thank you. The comments on every line were meant to leave nothing to interpretation for those who wish to use AND profoundly understand it prior to implementation. Keeps the comments section nice and empty, hehe. \$\endgroup\$
    – suchislife
    Oct 15, 2023 at 19:47
  • \$\begingroup\$ The comments on every line ... === "Can't see the forest for the trees" \$\endgroup\$
    – radarbob
    Oct 16, 2023 at 1:08
  • \$\begingroup\$ The comments on every line ... makes the code exceptionally hard to read. Every line is visual noise of mutual interference with the next line. Can't read the comments for the code and can't read the code for the comments. Imagine reading two novels like this. \$\endgroup\$
    – radarbob
    Oct 17, 2023 at 13:58
  • \$\begingroup\$ One can always you know.. save to file and remove the comments? Most cannot however intuit Bitwise operations without some context. \$\endgroup\$
    – suchislife
    Oct 21, 2023 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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