The 2^120 Ways to Ensure Unique Identifiers

Ever wondered about the magic behind Firebase’s push IDs? We get many questions from our developers about how our uniquely generated IDs work under the hood so I thought I’d explain them in more detail.

If you’re not familiar with Firebase’s push IDs, they are the chronological, 20-character unique IDs generated when you write lists of data to Firebase from any of our client libraries. Below is an example of some data stored in Firebase by push ID:

{
    "messages": {
        "-JhLeOlGIEjaIOFHR0xd": "Hello there!",
        "-JhQ76OEK_848CkIFhAq": "Push IDs are pretty magical.",
        "-JhQ7APk0UtyRTFO9-TS": "Look a white rabbit!"
    }
}

We created push IDs for collaborative, multi-user applications to handle situations where many clients are adding to a list at the same time. We needed IDs that could be generated client-side so that they wouldn’t need to wait for a round-trip to the server. And we needed them to be unique so that many clients could append data to the same location at the same time without worrying about conflicts.

How Push IDs are Generated

Push IDs are string identifiers that are generated client-side. They are a combination of a timestamp and some random bits. The timestamp ensures they are ordered chronologically, and the random bits ensure that each ID is unique, even if thousands of people are creating push IDs at the same time.

What’s in a Push ID?

A push ID contains 120 bits of information. The first 48 bits are a timestamp, which both reduces the chance of collision and allows consecutively created push IDs to sort chronologically. The timestamp is followed by 72 bits of randomness, which ensures that even two people creating push IDs at the exact same millisecond are extremely unlikely to generate identical IDs. One caveat to the randomness is that in order to preserve chronological ordering if a client creates multiple push IDs in the same millisecond, we just ‘increment’ the random bits by one.

To turn our 120 bits of information (timestamp + randomness) into an ID that can be used as a Firebase key, we basically base64 encode it into ASCII characters, but we use a modified base64 alphabet that ensures the IDs will still sort correctly when ordered lexicographically (since Firebase keys are ordered lexicographically).

Push ID Ordering Issues

There’s one caveat to the chronological ordering of push IDs. Since the timestamp is generated client-side, it’s at the mercy of the client’s local clock, which could be incorrect. We make an attempt to compensate for these ‘skewed’ clocks to some degree. When a Firebase client establishes a connection, the Firebase server sends an accurate timestamp to the client so it can use that to correct its incorrect clock when generating push IDs.

However, this correction only takes effect once the client has connected to Firebase, so if you generate a push ID before the client connects, we won’t make an attempt to correct it. You could even generate two push IDs on the same client and the second push ID will be ordered before the first one if we started compensating for your clock between when you generated them.

Guaranteed Chronological Ordering

To get guaranteed chronological ordering, you probably shouldn’t rely on push IDs but instead use our ServerValue.TIMESTAMP feature, which looks like this:

// Write some data with a timestamp
ref.push({
    foo: 'bar',
    date: Firebase.ServerValue.TIMESTAMP
});

// Later, retrieve the data by ordered date
ref.orderByChild('date').on('child_added', function(snapshot) {
    //Do something with ordered children
});
// Write some data with a timestamp
NSDictionary *data = @{
    @"foo": @"bar",
    @"date": kFirebaseServerValueTimestamp
};
[[ref childByAutoId] setValue: data];

//Later, retrieve the data by ordered date
[[ref queryOrderedByChild:@"date"]
    observeEventType:FEventTypeChildAdded withBlock:^(FDataSnapshot *snapshot) {

    //Do something with ordered children
}];
// Write some data with a timestamp
let data = [
    "foo":"bar",
    "date":FirebaseServerValue.timestamp()
]
ref.childByAutoId().setValue(data)

//Later, retrieve the data by ordered date
ref.queryOrderedByChild("date").observeEventType(.ChildAdded, withBlock: {
    snapshot in
    // Do something with ordered children
})
// Write some data with a timestamp
Map data = new HashMap();
data.put("foo", "bar");
data.put("date", ServerValue.TIMESTAMP);
ref.push().setValue(data);

//Later, retrieve the data by ordered date
Query queryRef = ref.orderByChild(“date”);

queryRef.addChildEventListener(new ChildEventListener() {
    @Override
    public void onChildAdded(DataSnapshot snapshot) {
        // Do something with ordered children
    }
    //...
});

This guarantees chronological ordering, since the ServerValue.TIMESTAMP will be resolved on the Firebase server to be an accurate timestamp.

Push IDs & Security

We also get questions on whether developers can rely on push IDs to be unguessable by others, which can be important if you’re trying to do security via unguessable Firebase paths. While push IDs are generally very hard to guess, if you’re relying on unguessable IDs you should generate them yourself using a more secure mechanism.

If you’d like to take a closer look at how push IDs work, we’ve published the code we use to generate them in a gist here.

Have other questions about push IDs that weren’t answered here? Let us know in our google group or by mentioning @Firebase on Twitter, we’d love to hear your feedback!