flake2.0.0 • Public • Published
Generate practically unique approximately sortable IDs in a distributed environment.
There are 3.403e+38 (or 340,282,366,920,938,463,463,374,607,431,768,211,456) possible flake numbers. Use in distributed environments where you don't have a central service which can be a single point of failure - perfect when you want everything to be redundant and independent of each other.
The make-up of a Flake ID
Example Flake IDs from two different machines:
013c798f75ac-0000-1154-984be1b8b104 013c798f75ac-0001-1154-984be1b8b104 013c798f75ad-0000-1154-984be1b8b104 013c798f75ad-0001-1154-984be1b8b104 013c798f75ad-0002-1154-984be1b8b104 013c798f75ad-0003-1154-984be1b8b104 013c7990a044-0000-08ff-00027298bef9 013c7990a045-0000-08ff-00027298bef9 013c7990a045-0001-08ff-00027298bef9 013c7990a045-0002-08ff-00027298bef9 013c7990a045-0003-08ff-00027298bef9
As you can see, the Flake Id is made up of:
timestamp-counter-pid-macaddress and can be seen in the
+---------+--------------+---------+------+--------------+ | Machine | Timestamp | Counter | PID | Mac Address | +---------+--------------+---------+------+--------------+ | A | 013c798f75ac | 0000 | 1154 | 984be1b8b104 | | A | 013c798f75ac | 0001 | 1154 | 984be1b8b104 | | A | 013c798f75ad | 0000 | 1154 | 984be1b8b104 | | A | 013c798f75ad | 0001 | 1154 | 984be1b8b104 | | A | 013c798f75ad | 0002 | 1154 | 984be1b8b104 | | A | 013c798f75ad | 0003 | 1154 | 984be1b8b104 | | B | 013c7990a044 | 0000 | 11ff | 00027298bef9 | | B | 013c7990a045 | 0000 | 11ff | 00027298bef9 | | B | 013c7990a045 | 0001 | 11ff | 00027298bef9 | | B | 013c7990a045 | 0002 | 11ff | 00027298bef9 | | B | 013c7990a045 | 0003 | 11ff | 00027298bef9 | +---------+--------------+---------+------+--------------+
As you can see, each Flake ID is 128 bits long, consisting of a 48 bit timestamp, 16 bit counter, 16 bit PID and a 48 bit mac address.
All of these FlakeIDs are
approximately sortable and
Firstly, find a network interface you can use so you can obtain a mac address:
var os = require('os'); var interfaces = os.networkInterfaces(); console.log(Object.keys(interfaces));
Look for something like 'eth0', 'en0', 'wlan0', 'venet0' or 'net0' (Note: you may have a number other than 0.) Don't choose something like 'lo' or 'tun0'. Experiment to make sure it works. :)
In the following example, I'm using
eth0, but this is not guaranteed to work on your machine. You need to change
it to something which exists on your machine.
var flake = require('flake')('eth0'); console.log(flake()); console.log(flake()); console.log(flake());
Would give something like:
013b829b1520-0000-18f0-984be1b8b104 013b829b1527-0000-18f0-984be1b8b104 013b829b1527-0001-18f0-984be1b8b104
Running it again might give:
013b829b9680-0000-18f3-984be1b8b104 013b829b9680-0001-18f3-984be1b8b104 013b829b9685-0000-18f3-984be1b8b104
As you can see, the time has increased by a few seconds and the PID is different. The mac address is the same and the sequence always resets.
Note: these unique IDs are not the same as UUIDs or can be used in place of one.
Format of each Unique ID
Each unique ID has 4 sections which are:
013b83165f6a-00f9-314b-984be1b8b104 = 013b83165f6a -> timestamp in ms since epoch = 00f9 -> counter = 314b -> PID of the current process = 984be1b8b104 -> MAC address of the interface provided (e.g. 'eth0')
Unlike Twitter's Snowflake, we also use the PID since we want to be able to generate unique IDs on the same machine at the same time. This is because we're generating them within the program which needs them and not in a client/server architecture.
If you were to generate IDs in multiple processes on the same machine and on multiple machines, then whilst we can't guarantee that the IDs will be exactly sortable, they will be approximately sortable. In fact, to the millisecond (assuming your clocks aren't skew from each other).
e.g. some IDs generated on the same machine in two processes, using 'eth0' and 'wlan0' as the MAC address could be, and printing out alternately:
013b83571852-0000-4ae8-984be1b8b104 013b83571853-0000-4ae8-00027298bef9 013b83571853-0000-4ae9-984be1b8b104 013b83571853-0001-4ae8-00027298bef9 013b83571853-0001-4ae9-984be1b8b104 013b83571853-0002-4ae8-00027298bef9 013b83571853-0002-4ae9-984be1b8b104 013b83571853-0003-4ae8-00027298bef9 013b83571853-0003-4ae9-984be1b8b104
As you can see, the IDs are firstly sorted by timestamp, then sequence, the PID then mac address.
Currently there is a possibility to generate the same ID in the same process on the same machine. This is described by System Clock Depedency.
This situation hasn't yet been solved but is known about. Therefore, you should run NTP in a mode which doesn't move the clock backwards.
Copyright (c) 2012 Andrew Chilton.
MIT License : http://chilts.mit-license.org/2012/