Skip to content

Instantly share code, notes, and snippets.

Created February 11, 2015 17:34
Show Gist options
  • Save mikelehen/3596a30bd69384624c11 to your computer and use it in GitHub Desktop.
Save mikelehen/3596a30bd69384624c11 to your computer and use it in GitHub Desktop.
JavaScript code for generating Firebase Push IDs
* Fancy ID generator that creates 20-character string identifiers with the following properties:
* 1. They're based on timestamp so that they sort *after* any existing ids.
* 2. They contain 72-bits of random data after the timestamp so that IDs won't collide with other clients' IDs.
* 3. They sort *lexicographically* (so the timestamp is converted to characters that will sort properly).
* 4. They're monotonically increasing. Even if you generate more than one in the same timestamp, the
* latter ones will sort after the former ones. We do this by using the previous random bits
* but "incrementing" them by 1 (only in the case of a timestamp collision).
generatePushID = (function() {
// Modeled after base64 web-safe chars, but ordered by ASCII.
var PUSH_CHARS = '-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz';
// Timestamp of last push, used to prevent local collisions if you push twice in one ms.
var lastPushTime = 0;
// We generate 72-bits of randomness which get turned into 12 characters and appended to the
// timestamp to prevent collisions with other clients. We store the last characters we
// generated because in the event of a collision, we'll use those same characters except
// "incremented" by one.
var lastRandChars = [];
return function() {
var now = new Date().getTime();
var duplicateTime = (now === lastPushTime);
lastPushTime = now;
var timeStampChars = new Array(8);
for (var i = 7; i >= 0; i--) {
timeStampChars[i] = PUSH_CHARS.charAt(now % 64);
// NOTE: Can't use << here because javascript will convert to int and lose the upper bits.
now = Math.floor(now / 64);
if (now !== 0) throw new Error('We should have converted the entire timestamp.');
var id = timeStampChars.join('');
if (!duplicateTime) {
for (i = 0; i < 12; i++) {
lastRandChars[i] = Math.floor(Math.random() * 64);
} else {
// If the timestamp hasn't changed since last push, use the same random number, except incremented by 1.
for (i = 11; i >= 0 && lastRandChars[i] === 63; i--) {
lastRandChars[i] = 0;
for (i = 0; i < 12; i++) {
id += PUSH_CHARS.charAt(lastRandChars[i]);
if(id.length != 20) throw new Error('Length should be 20.');
return id;
Copy link

dbechrd commented Aug 5, 2023

Line 48 is a buffer underflow when the random bytes are zzzzzzzzzzzz (either randomly, or due to the same-millisecond increment behavior). It will attempt to increment lastRandChars[-1]. In JavaScript, this will create a property on the object with key -1 and value NaN, but in other languages, it could cause far more insidious behavior.

In C, I chose to do this (rather than throw an error), but in your JS code, throwing an error seems more consistent with how other parts of it work.

// Prevent buffer underrun on overflow (when incrementing "zzzzzzzzzzzz")
// Warning: If this gets skipped, the id is no longer guaranteed to be unique,
// but most likely will be for quite awhile (it depends on where the random
// value for this millisecond started in the range).
if (i >= 0) {

Copy link


Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment