Skip to content

Instantly share code, notes, and snippets.

@swftvsn
Created March 15, 2017 10:36
Show Gist options
  • Save swftvsn/438b4ed68619ad1f5d1c251dc3a5af6f to your computer and use it in GitHub Desktop.
Save swftvsn/438b4ed68619ad1f5d1c251dc3a5af6f to your computer and use it in GitHub Desktop.
Firebase Java Push Id Generator
package firebase;
public class FirebasePushIdGenerator {
// Modeled after base64 web-safe chars, but ordered by ASCII.
private final static String PUSH_CHARS = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz";
// Timestamp of last push, used to prevent local collisions if you push twice in one ms.
private static long LAST_PUSH_TIME = 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.
private static int[] LAST_RAND_CHARS = new int[72];
public static synchronized String generate() {
long now = System.currentTimeMillis();
boolean duplicateTime = now == LAST_PUSH_TIME;
LAST_PUSH_TIME = now;
char[] timeStampChars = new char[8];
for (int i = 7; i >= 0; i--) {
timeStampChars[i] = PUSH_CHARS.charAt((int)(now % 64));
now = (long) Math.floor(now / 64);
}
if (now != 0) {
throw new AssertionError("We should have converted the entire timestamp.");
}
StringBuilder id = new StringBuilder(20);
for (char c : timeStampChars) {
id.append(c);
}
if (!duplicateTime) {
for (int i = 0; i < 12; i++) {
LAST_RAND_CHARS[i] = (int) Math.floor(Double.valueOf(Math.random() * 64).intValue());
}
} else {
// If the timestamp hasn't changed since last push, use the same random number,
//except incremented by 1.
int i=0;
for (i = 11; i >= 0 && LAST_RAND_CHARS[i] == 63; i--) {
LAST_RAND_CHARS[i] = 0;
}
LAST_RAND_CHARS[i]++;
}
for (int i = 0; i < 12; i++) {
id.append(PUSH_CHARS.charAt(LAST_RAND_CHARS[i]));
}
if (id.length() != 20) {
throw new AssertionError("Length should be 20.");
}
return id.toString();
}
}
package firebase;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;
import org.junit.Assert;
import org.junit.Test;
import firebase.FirebasePushIdGenerator;
public class FirebasePushIdGeneratorTest {
@Test
public void testGeneration() throws InterruptedException, ExecutionException {
final ExecutorService es = new ThreadPoolExecutor(20, 20, 10000, TimeUnit.DAYS, new ArrayBlockingQueue<>(10000));
final ConcurrentMap<String, Boolean> set = new ConcurrentHashMap<>(1000000);
final AtomicBoolean hasDuplicates = new AtomicBoolean(false);
final List<Future<?>> futures = new ArrayList<>();
for (int i=0; i<100; i++) {
Future<?> f = es.submit(new Runnable() {
@Override
public void run() {
for (int i=0; i<10000; i++) {
final String id = FirebasePushIdGenerator.generate();
if (set.putIfAbsent(id, Boolean.TRUE) != null) {
hasDuplicates.set(true);
System.out.println("Duplicate detected! " + id);
}
}
}
});
futures.add(f);
}
for (Future<?> f : futures) {
f.get();
}
es.shutdown();
es.awaitTermination(20L, TimeUnit.MINUTES);
Assert.assertFalse("There are duplicate keys!", hasDuplicates.get());
}
}
@swftvsn
Copy link
Author

swftvsn commented Mar 15, 2017

@mwojterski
Copy link

LAST_RAND_CHARS ought to have length 12. @aokholm mentioned this in the comments for the original gist.

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