R1.0 HID Generation

(deprecated)

Requirement

Should be 10 digits long, and not guessable. Also, the generation of the id can happen from multiple nodes of a server cluster.

The ids will be distributed to the entire population.

Implementation

n bits long.
Most significant m bits: Timestamp in some unit after 01 Jan 2015 (random date)
Next (n-m) bits: worker id + random number
The worker id, which is node specific, will decrease collisions in a cluster setup.

Q. What should n, m and unit of timestamp be?

HID should be a 10 digits long decimal number. To make the hid always 10 digits long, the generated value should be added to 1,000,000,000. So the generated value cannot be more than 8,999,999,999.

8,999,999,999 requires 34 bits (1,000,011,000,011,100,010,001,100,111,111,111).

But largest 34 bits binary is an 11 digit decimal no. – 17,179,869,183.

References:

http://www.binaryhexconverter.com/decimal-to-binary-converter

http://www.miniwebtool.com/geometric-sequence-calculator/?a1=1&r=2&n=34

So, n should be 34. The implementation should check whether the hid generated is 10 digits long decimal number. 

17,179,869,183 millisecs (largest 34 bit binary no. in decimal) = 0.544 yrs
So unit of the timestamp cannot be milli secs, but some bigger unit. Depending on the value of m we should decide the unit of timestamp.

For m = 24 and unit is sec, hid can be generated for 0.531 yrs.
For m = 24 and unit is min, hid can be generated for 31.89 yrs.
(Largest 24 bit binary no. is 16,777,215 in decimal)

Note: One may use Google to convert between units of time.

Conclusion:

n = 34 bits.

m = 24 bits. So first 24 bits represent timestamp in mins after 01 Jan 2015.

Next 9 bits (n-m), worker id (3 bits) + random number (7 bits).

This implies, max no. of nodes allowed in MCI cluster is 8 (0-7) and max random number value is 127 (0-127).

What is the max timestamp possible?

8,999,999,999 in binary is 100001100001110001000110-011-1111111 (timestamp-workerId-random bits). However, the max worker id possible is 111 in binary.

For max worker id (7), and max random number (127), the max value of the 24 timestamp bits so that the entire 34 bits binary in decimal is less than or equal to 8,999,999,999 is 1000001111111111111111111111111111.

100000111111111111111111-111-1111111 in binary is 8,858,370,047 in decimal.

100000111111111111111111 in binary is 8650751 in decimal.

8650751 minutes is 16.44 years. So, max possible timestamp is 01 June 2031 (approx).

References:

http://www.boundary.com/blog/2012/01/flake-a-decentralized-k-ordered-unique-id-generator-in-erlang/

http://engineering.custommade.com/simpleflake-distributed-id-generation-for-the-lazy/