Instantly share code, notes, and snippets.

Embed
What would you like to do?
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;
}
lastRandChars[i]++;
}
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;
};
})();
@azell

This comment has been minimized.

azell commented Feb 11, 2015

@sarciszewski

This comment has been minimized.

sarciszewski commented Feb 12, 2015

@jeremyworboys

This comment has been minimized.

jeremyworboys commented Feb 12, 2015

@risent

This comment has been minimized.

risent commented Feb 12, 2015

@jfbyers

This comment has been minimized.

jfbyers commented Feb 12, 2015

@oderwat

This comment has been minimized.

oderwat commented Feb 12, 2015

Port in Nim (aka Nimrod) https://gist.github.com/oderwat/04b8c8f586132909e8f0 ... Quality may vary I just code in Nim for some days.

@themartorana

This comment has been minimized.

themartorana commented Feb 12, 2015

@kjk

This comment has been minimized.

kjk commented Feb 12, 2015

@tst2005

This comment has been minimized.

@whatvn

This comment has been minimized.

whatvn commented Mar 2, 2015

Port in C (last gen time just work in real implementation):
https://gist.github.com/whatvn/15f5266d59320113d978

@pgherveou

This comment has been minimized.

@mikelehen

This comment has been minimized.

Owner

mikelehen commented Jul 7, 2015

Thanks everybody for all the ports! :-)

@dotproto

This comment has been minimized.

dotproto commented Jul 11, 2015

This may not be a practical concern, but i in this loop is hard coded to 7. As such, it will only work for dates between Mar 6, 1972 and May 15, 2109 (68719476737 and 4398046511104 respectively).

You could potentially make the algorithm a bit more robust at a relatively minor performance cost by doing something like this:

var i = Math.ceil( Math.log(now) / Math.log( 64 ) );
for (; i >= 0; i--) { /* ... */ }

Benchmark.js comparison

original x 786,235 ops/sec ±1.23% (93 runs sampled)
modified x 710,718 ops/sec ±1.41% (94 runs sampled)

NOTE: I forgot to take the array size into account. Of course, if you want a well-known key length this won't help anything 😉

@dotproto

This comment has been minimized.

dotproto commented Jul 12, 2015

In case it comes in handy for someone, I wrote a quick function that converts a Push ID to Unix Time: https://gist.github.com/svincent/ae4eead8f7a97620e963

@ZeroDragon

This comment has been minimized.

ZeroDragon commented May 5, 2016

@kcmoffat

This comment has been minimized.

kcmoffat commented May 5, 2016

@episage

This comment has been minimized.

episage commented May 17, 2016

@CitizenOfTheRomanEmpire

This comment has been minimized.

CitizenOfTheRomanEmpire commented Jun 2, 2016

@richardfrk

This comment has been minimized.

richardfrk commented Jul 5, 2016

Tested in Google App Script.

@AllanHasegawa

This comment has been minimized.

@chilts

This comment has been minimized.

chilts commented Oct 20, 2016

I've added a package called pushid to npm : https://www.npmjs.com/package/pushid :) Thanks.

var pushid = require('pushid')
 console.log(pushid())
// -> "-KQ40rgB96epAE7LZH2W" 
@kiliman

This comment has been minimized.

kiliman commented Oct 20, 2016

Port in C#: https://gist.github.com/kiliman/ca1d9f4135078a6b24c5005113bbeea4

Includes output showing timestamp collisions. Also added a method to convert PushID back into timestamp.

@DimuDesigns

This comment has been minimized.

DimuDesigns commented Dec 17, 2016

Port to MySQL stored procedure - MySQL Stored Procedure for generating Firebase Push IDs.

I've found this useful for migrating MySQL databases to Firebase.

@bernatfortet

This comment has been minimized.

bernatfortet commented Jan 22, 2017

Sorry for my ignorance but why does the generatePushID returns a function instead of the id?
Because as it is it means I have to do this: generatePushID()()

Could somebody kindly explain me?

Thanks

@doowb

This comment has been minimized.

doowb commented Feb 7, 2017

@bernatfortet the first call to the wrapped function is done for you at the bottom: })();

This essentially makes PUSH_CHARS, lastPushTime, and lastRandChars private variables but accessible to each call of the returned function assigned to generatePushID. This is creating a closure around those variables so they can be used inside that function, but not modified outside. This will also ensure that the memory for PUSH_CHARS is only allocated once and not each time the function is called.

@swftvsn

This comment has been minimized.

swftvsn commented Mar 15, 2017

Another Java port with JUnit test to verify correct multithreading operation: https://gist.github.com/swftvsn/438b4ed68619ad1f5d1c251dc3a5af6f

@origin1tech

This comment has been minimized.

origin1tech commented Mar 17, 2017

Cleaned up a little with both generator for uid and also timestamp extraction method (TypeScript)

https://gist.github.com/origin1tech/17eb8259084d2edab3f005c84f10d2bb

@jtexp

This comment has been minimized.

jtexp commented Mar 19, 2017

Can you license this with something permissive please?

@herberthobregon

This comment has been minimized.

herberthobregon commented Apr 9, 2017

thanks for all!

@GulinSS

This comment has been minimized.

GulinSS commented Apr 28, 2017

+1 for @jtexp

@lastmjs

This comment has been minimized.

lastmjs commented May 2, 2017

I would really like a license as well

@ryanucode

This comment has been minimized.

ryanucode commented May 2, 2017

@cjthomp

This comment has been minimized.

cjthomp commented Jul 21, 2017

SublimeText 3 plugin (no numpy)

@longkerdandy

This comment has been minimized.

longkerdandy commented Aug 21, 2017

Hi, after the code piece:
for (i = 11; i >= 0 && lastRandChars[i] === 63; i--) { lastRandChars[i] = 0; }
The var i could be -1 if all the lastRandChars is 63, and lead to index out of range error

@longkerdandy

This comment has been minimized.

longkerdandy commented Aug 28, 2017

Thread safe Java port with bug fixes and jmh benchmark:
https://gist.github.com/longkerdandy/a296b7a084fd191af6e4176eed168812

@iansamz

This comment has been minimized.

iansamz commented Oct 11, 2017

Could have taken me weeks to work this out on my own... thanks a bunch

@silverbeak

This comment has been minimized.

silverbeak commented Oct 13, 2017

I created a Rust version here: https://github.com/silverbeak/rust-push-id
Crate here: https://crates.io/crates/pushid

I will get to documentation soon, hopefully.
The reason I didn't turn it into a Gist is because Rust doesn't have native support for Random. It needs an external Crate for that, which makes it clumsy as a Gist.

Some nice submissions in this thread. Kudos, all!

@gaspard

This comment has been minimized.

gaspard commented Jan 3, 2018

@SVincent, you have your calculations wrong I think:

// 64 = 2^6
// So it actually uses Math.pow ( 64, 8 ) === Math.pow ( 2, 48 )
const maxTime = Math.pow ( 2, 48 ) - 1
let now = maxTime
for ( let i = 7; i >= 0; i-- ) {
  now = Math.floor ( now / 64 )
}
// ==> now === 0
const date = new Date ()
date.setTime ( maxTime )
d.toISOString ()
// ==> "+010889-08-02T05:31:50.655Z"
// This date is greater then year 10889
// It is actually somewhere in 10895
@amirh

This comment has been minimized.

@notapineapple

This comment has been minimized.

notapineapple commented May 3, 2018

Im so grateful finding this ❤️ thank you

@arturictus

This comment has been minimized.

arturictus commented May 13, 2018

@adamkoncz

This comment has been minimized.

adamkoncz commented Jun 13, 2018

Did pushid changed in firebase lately? None of the thousands of ids generated contains dash (-) or underscore (_). Or anything apart from alphanumeric characters.

@robdelacruz

This comment has been minimized.

@AhmedOS

This comment has been minimized.

AhmedOS commented Oct 8, 2018

Swift 4: https://gist.github.com/AhmedOS/512531b74da37f34331ecb206c77c20a
Modified version of pgherveou's one.

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