Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Port of Firebase Pushid generator in Java. See original at https://gist.github.com/mikelehen/3596a30bd69384624c11#file-generate-pushid-js
package com.firebase.utils;
import java.util.Date;
/**
* 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).
*
* @author jfbyers@about.me
* @see <a href="https://gist.github.com/mikelehen/3596a30bd69384624c11#file-generate-pushid-js">
Original port by mikelehen </a>
*/
public class FireBasePushIdGenerator {
// Modeled after base64 web-safe chars, but ordered by ASCII.
private final static String PUSH_CHARS = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz";
public static String generatePushId() {
// Timestamp of last push, used to prevent local collisions if you push twice in one ms.
long lastPushTime = 0L;
// 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.
char[] lastRandChars = new char[72];
long now = new Date().getTime();
boolean duplicateTime = (now == lastPushTime);
char[] timeStampChars = new char[8];
for (int i = 7; i >= 0; i--) {
final long module = now % 64;
timeStampChars[i] = PUSH_CHARS.charAt(Long.valueOf(module).intValue());
now = (long) Math.floor(now / 64);
}
if (now != 0)
throw new AssertionError("We should have converted the entire timestamp.");
String id = new String(timeStampChars);
if (!duplicateTime) {
for (int i = 0; i < 12; i++) {
final double times = Math.random() * 64;
lastRandChars[i] = (char) Math.floor(Double.valueOf(times).intValue());
}
} else {
// If the timestamp hasn't changed since last push, use the same random number,
//except incremented by 1.
int lastValueOfInt=0;
for (int i = 11; i >= 0 && lastRandChars[i] == 63; i--) {
lastValueOfInt = i;
lastRandChars[i] = 0;
}
lastRandChars[lastValueOfInt]++;
}
for (int i = 0; i < 12; i++) {
id += PUSH_CHARS.charAt(lastRandChars[i]);
}
if (id.length() != 20)
throw new AssertionError("Length should be 20.");
return id;
};
}
@aokholm

This comment has been minimized.

Copy link

@aokholm aokholm commented Sep 28, 2015

I believe that the char array size on line 36 should be 12 instead of 72 :)

@abeatte

This comment has been minimized.

Copy link

@abeatte abeatte commented Dec 31, 2015

No, he's fine. The 72 chars are the random bits to choose from. On lines 55 or 69 he dips into the lastRandChars[] to generate a 12 char id.

@pepijntb

This comment has been minimized.

Copy link

@pepijntb pepijntb commented Jan 7, 2016

I've made a Java port that works without Date and with minimal object creation.
https://gist.github.com/pepijntb/067db689459fd26949dc

@kalpeshp0310

This comment has been minimized.

Copy link

@kalpeshp0310 kalpeshp0310 commented Jun 13, 2016

@jfbyers Don't you think duplicateTime will be always false? As lastPushTime is not global variable and is set to zero, and now is current timestamp which is always non zero.

@kirtan403

This comment has been minimized.

Copy link

@kirtan403 kirtan403 commented Jul 29, 2016

@kalpeshp0310 I agree. It should be outside the method. It should be the member of Class and not the method. Else it will always be zero.

@speedymovil-interno

This comment has been minimized.

Copy link

@speedymovil-interno speedymovil-interno commented Dec 7, 2016

This doesn't work, some variables must be static, else will always fail some conditions. Also it is not very efficient using += with Strings as it will create a new String for every character added.

@Sam-WEI

This comment has been minimized.

Copy link

@Sam-WEI Sam-WEI commented Jan 10, 2017

The lastValueOfInt doesn't work properly

@swftvsn

This comment has been minimized.

Copy link

@swftvsn swftvsn commented Mar 15, 2017

I have added new, correctly working version to this gist: https://gist.github.com/swftvsn/438b4ed68619ad1f5d1c251dc3a5af6f that also contains a junit test to verify multithreaded operation.

@mwojterski

This comment has been minimized.

Copy link

@mwojterski mwojterski commented Jun 5, 2017

@aokholm is correct, lastRandChars should have length of 12.

@abeatte I think you misunderstood where 72 bits comes from: 12 chars of lastRandChars is filled with random value of 0-64 which is 6 bits.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.