firebase_id.py

"""Firebase-style 120-bit unique identifiers.
https://www.firebase.com/blog/2015-02-11-firebase-unique-identifiers.html
"""
from math import floor
from random import random
from string import ascii_lowercase
from string import ascii_uppercase
from string import digits
from time import time


# Modeled after web-safe base64 alphabet, but in ASCII ordered.
ALPHABET = '-' + digits + ascii_uppercase + '_' + ascii_lowercase
ALPHABET_SIZE = len(ALPHABET)

# Timestamp of last ID generated. Used to prevent local collisions more than
# one ID is generated in the same ms.
_LAST_TS = 0

# We generate 72 random bits which are encoded into 12 characters and
# appended to the timestamp. In the event of a time collision, we use the last
# set of random characters "incremented" by one.
_LAST_RANDOM_CHARS = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


def firebase_id():
    now = floor(time() * 1000)  # whole ms
    time_collision = (now == _LAST_TS)

    global _LAST_TS
    _LAST_TS = now

    # 48 time bits become 8 characters
    timestamp_chars = [0, 0, 0, 0, 0, 0, 0, 0]
    for i in range(len(timestamp_chars), 0, -1):
        timestamp_chars[i - 1] = ALPHABET[now % ALPHABET_SIZE]
        now = floor(now / 64)

    if now != 0:
        # Interestingly enough, this only works until some time in 2109...
        raise Exception('Failed to convert entire timestamp')

    uid = ''.join(timestamp_chars)

    if time_collision is False:
        for i in range(12):
            _LAST_RANDOM_CHARS[i] = floor(random() * ALPHABET_SIZE)
    else:
        # If the timestamp hasn't changed since the last ID we generated, use
        # the same random number, incremented by 1.
        for i in range(11, -1, -1):
            if _LAST_RANDOM_CHARS[i] != ALPHABET_SIZE - 1:
                break
            else:
                _LAST_RANDOM_CHARS[i] = 0
        _LAST_RANDOM_CHARS[i] += 1

    for i in range(12):
        uid += ALPHABET[_LAST_RANDOM_CHARS[i]]

    if len(uid) != 20:
        raise Exception('Generated ID should have length 20')

    return uid