Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Firebase push id algorithm in Nim (aka Nimrod) (ref: https://www.firebase.com/blog/2015-02-11-firebase-unique-identifiers.html)
# 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).
#
# Based on https://www.firebase.com/blog/2015-02-11-firebase-unique-identifiers.html
# Nim version by H. Raaf / GitHub: OderWat with a little help from GitHub: Def-
import times, math
proc generatePushID(): string =
# Modeled after base64 web-safe chars, but ordered by ASCII.
const PUSH_CHARS = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"
# Timestamp of last push, used to prevent local collisions if you push twice in one ms.
var lastPushTime {.global.} = 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 {.global.}: array[12, int8]
var now = int(getTime().toSeconds())
let duplicateTime = now == lastPushTime
lastPushTime = now;
result = newString(20)
for i in countdown(7,0):
result[i]=PUSH_CHARS[now mod 64]
now = now div 64
assert now == 0 # We should have converted the entire timestamp.
if not duplicateTime:
for c in lastRandChars.mitems:
c = int8(random(64))
else:
# If the timestamp hasn't changed since last push,
# use the same random number, except incremented by 1.
var i=lastRandChars.high
while i >= 0 and lastRandChars[i] == 63:
lastRandChars[i]=0
dec i
# here could be an overflow but Nim catches it anyway
# as long as range-checks are enabled for the executable
# assert i>=0
inc lastRandChars[i]
for i, o in lastRandChars:
result[8+i]=PUSH_CHARS[o]
when isMainModule:
randomize()
echo generatePushID()
echo generatePushID()
echo generatePushID()
for i in 1..1_000_000:
discard generatePushID()
echo generatePushID()
@oderwat

This comment has been minimized.

Copy link
Owner Author

@oderwat oderwat commented Feb 12, 2015

There is another Version by Nim fellow which helped me to clean that up! You find his version here: https://gist.github.com/def-/e473d087445344c03629

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.