Short Distributed ID generator module
This module was inspired by icicle and snowflake. The ideas is to be able to generate non-colliding, URL friendly, and relatively short IDs that could be used in any application that requires to create URIs for arbitrary resources.
Looking around for what is available, I failed to find anything that would be simple and easy to implement. As a result, this module was born.
The id is a 64bit unsigned integer with 42 bits used for current timestamp in milliseconds, 10 bits used for shard id, and final 12 bits are used for revolving sequence.
- Trying to fix build CI and npm publising, no code or functionality changes.
- Update of test dependencies, not code or functional changes.
- Native code clean-up and optimizations, slightly improved hashid encoding and unique ID generation performance.
- Fix bug where hashidEncode would cause segfault if non-array argument was passed.
- No API changes. Changed dev dependency to use bn.js instead of bignum. confirmed compatibility with node 0.11, 0.12, iojs 2.5, 3
- No API changes. Added benchmarking code and made it run as part of CI. Minor improvements to README.md file.
- No impact on actual functionality, use steady_clock vs system_clock, cleanup, native code improvements, added one more test, example code improvements
- No impact on actual functionality, improved C++ code and updated README with two additional API calls
- No impact on actual functionality, added examples and reworked unit tests
- A lot of fixes and test additions, also API breaking change: custom_epoch is expecting milliseconds instead of seconds
- Initial public release
- gcc 4.7+ with C++11 or clang 3.4+
- node.js 0.11+ or iojs 2+/3+
- Time and sequence based numeric unique ID generation
- Time and sequence based alphanumeric URL-safe unique ID generation
- Designed to be distributed among 1024 shards, no need to synchronize runtime or after setup
- Can generate 4096 unique IDs per millisecond per shard
- Can generate unique IDs for 139 years without overflow or collision
- Resilient to time drift or sequence overflow, does not delay ID generation
- Allows to set custom epoch, prolong unique ID generation and shorten the ID
- Written in C++11, fast
- No runtime dependencies
- (Convenient Add-on) Encode and decode hashids
- (Convenient Add-on) Random password generator
- (Convenient Add-on) Random URL-safe API key generator
- Simple to use
- Using single core of bare-metal
Intel(R) Xeon(R) CPU E5-2620 v3 @ 2.40GHz(as of 2015 Aug 3) I was able to perform 1,126,104 ops/sec, generating integer IDs
- Running benchmark on
Macbook Pro with 2.8 GHz Intel Core i7, on a single core:
- 2,061,897 ops/sec (single integer ID request) ==> 2,061,897 IDs per second
- 276,886 ops/sec (10 integer ID requests) ==> 2,768,860 IDs per second
- 2,843 ops/sec (1024 integer ID requests) ==> 2,911,232 IDs per second
- 725 ops/sec (4096 integer ID requests) ==> 2,969,600 IDs per second
- 630,942 ops/sec (single alphanumeric ID request) ==> 630,942 IDs per second
- 69,094 ops/sec (10 alphanumeric ID requests) ==> 690,940 IDs per second
- You can perform benchmark tests on your H/W by running
git clone https://gotfix.com/pixnr/short-duid.gitand
cd short-duid && npm install && npm run-script bench
npm install node-gyp -g && npm install short-duid
How to use
This module is very simple to use, first you will need to initialize it and then start using its instance.
short_duid.init(shard_id, salt, epoch_start)
Instantiates short-duid and sets parameters for the life of instance.
- Short Distributed ID module instance or
- Initializes new instance of the module with the given parameters
shard_id- ID of this instance of short-duid, should be unique and not shared with other instances in the cluster; from 0 to 1023. This parameter will be converted into signed 32 bit integer and masked to fit in 12 bits.
salt- Salt that is used by hashid encoder/decoder, should be constant and shared across all nodes in the cluster. Do not change this parameter once used in production, or you will have collisions in the alphanumeric IDs. Good way to generate salt on Linux:
dd if=/dev/random bs=1 count=102400 2>/dev/null| sha256sum
epoch_start- Number of milliseconds since unix epoch (1970, Jan 1 00:00:00 GMT). This should be some date in the near past and should never be changed further into the future once in production. Example: 1433116800000; //Mon, 01 Jun 2015 00:00:00 GMT. This parameter will be converted to unsigned 64bit integer.
Method to retrieve array of DUIDs in alphanumeric form. Length of the array is specified by
[ "XLz0E3MvkEL" ]
count- Number of alphanumeric DUIDs to return, from 0 to 8192.
Essential same method as
_instance_.getDUID but instead of hashid converted integer, will return unique ID in a numeric form as string.
[ "12534941854212112" ]
count- Number of numeric DUIDs to return, from 0 to 8192.
Method to get currently set shard ID of ShortDUID
numbercurrent shard ID of ShortDUID
Method to get currently set custom epoch starting time in milliseconds of ShortDUID
stringcurrently set custom epoch of ShortDUID
_instance_, since it is unsigned 64bit integer, we return it as string.
Method to get current salt of ShortDUID
_instance_. Salt is used to generate alphanumeric DUIDs and also in
stringcurrently set salt that is used in hashid conversion of ShortDUID
"this is my salt"
Method to hash(encode) array of unsigned 64bit integers (in
stringhashid array of unsigned 64bit integers
Decode previously encoded array of numbers with hashid method.
['1', '2', '3']
hashid_string- Hashid in a string form. Example:
Method to return randomly generated string of URL-friendly characters that is suitable for use as an API key.
stringrandomly generated string that is suitable for usage in URL and can serve as good static API key
length- Length of the random API key to return, default to 64, can be in the range from 0 to 4096.
Method to generate and return string of random characters that are not URL-friendly and is mostly suitable as a temporary password.
stringrandomly generated string that is suitable for usage as a temporary password and is not URL-friendly
length- Length of the random password to return, default to 16, can be in the range from 0 to 1024.
This API is mainly used by unit tests and should not be required for normal usage of the module. Use it at your own risk.
Method to get current time since unix epoch in milliseconds as seen by the module, not adjusted for custom epoch. This method can be useful in testing and also in capturing reference time to ensure timer stability across restarts.
stringof numbers, current time since unix epoch in milliseconds as seen by the module.
Method to help simulate
system_clock drift, can accept positive or negative integers.
stringnumber of milliseconds to drift ShortDUID's internal clock
milliseconds(optional) number of milliseconds to drif system_clock by, can be a positive or negative integer.
Simplest example to execute all of the major methods of the module.
var duid = ;var duid_instance = duid;console;console;console;console;console;console;
More complete example that will create API server with help of koajs and reply to queries.
'use strict';var pm2 = ;var cpus = length;var procs = Math;pm2;
'use strict';var koa = ;var router = ;var app = moduleexports = ;var duid = ;//Define app name and port for koa-clustervar cpus = length;appname = "ShortDUID";appnode_id = 0;appnid = processenvNODE_APP_INSTANCE ? processenvNODE_APP_INSTANCE : processpid % cpus; //nodejs instance IDappshard_id = appnode_id + appnid;appport = 65000;appsalt = "this is my super secret salt";appepoch_start = 1433116800 * 1000; //Mon, 01 Jun 2015 00:00:00 GMT//Instantiate short-duidvar duid_instance = appshard_id appsalt appepoch_start;//Setup routesrouter;//Setup middlewareapp;app;
And then you should install application with
npm install --save and start the server by
node index.js. You can check the logs and also list the processes with
./node_modules/.bin/pm2 list. Getting fresh id can be done by curl:
For more examples please see
examples folder, which I plan to keep adding to. You are free to contribute more examples.
Projects using ShortDUID
So far I know of none, if you are using it in your project and do not mind sharing this information, please drop me a note at email@example.com, and I will add you to this list.
Testing and benchmarking
npm install node-gyp -g && git clone https://gotfix.com/pixnr/short-duid.git && cd short-duid && npm install --save-dev
To run only benchmark, execute
npm run-script bench after installation.
MacBook-Pro:short-duid ian$ npm test && npm run bench > firstname.lastname@example.org test /Users/ian/GIT/short-duid > ./node_modules/mocha/bin/mocha —reporter spec ./test/*.js Short DUID #hashidEncode() and #hashidDecode() ✓ should produce identical hashids from both instances for: 233596 ✓ should produce different hashids for two different integers: 233596 and 727342 ✓ decode should return same integer given output of encode as argument passed to encode: 17052 ✓ decode should return same array of integers given output of encode as argument passed to encode: 233596,727342,17052 ✓ should return hashid that is equal to “LeGxr” given  as argument ✓ should return hashid that is equal to [ “123456” ] given “LeGxr” as argument ✓ should return hashid that is equal to “reG4QhO4NCpm” given [123456,7890,123] as argument ✓ should return hashid that is equal to [123456,7890,123] given “reG4QhO4NCpm” as argument ✓ should return different hashids given same value and different salt #getRandomAPIKey() ✓ should return random API key 64 characters long ✓ should return random API key each time called, should not be equal #getRandomPassword() ✓ should return random password 16 characters long ✓ should return random password each time called, should not be equal #getEpochStart() ✓ should return set epoch start, for instance #1: 1433116800000 ✓ should return set epoch start, for instance #2: 1433116800000 ✓ instance #1 and instance #2 should return same epoch start: 1433116800000 ✓ should reset custom epoch to zero if given one larger than real epoch ✓ should accept custom epoch that is even 1 millisecond in the past #getSalt() ✓ should return set salt, for instance #1: 39622feb2b3e7aa7208f50f45ec36fd513baadad6977b53295a3b28aeaed4a54 ✓ should return set salt, for instance #2: 39622feb2b3e7aa7208f50f45ec36fd513baadad6977b53295a3b28aeaed4a54 ✓ instance #1 and instance #2 should return same salt: 39622feb2b3e7aa7208f50f45ec36fd513baadad6977b53295a3b28aeaed4a54 #getShardID() ✓ should overflow if shard_id is set to integer that does not fit in 10 bits: 1024 —> 0 ✓ should return set shard id for instance #1: 123 ✓ should return set shard id for instance #2: 12 ✓ should return different shard ids for instance #1 and instance #2 #getDUID() ✓ Asked for 1 DUIDs, correctly returns 1 DUIDs ✓ Asked for 0 DUIDs, correctly returns 0 DUIDs ✓ Asked for 8192 DUIDs, correctly returns 8192 DUIDs ✓ Asked for 8193 DUIDs, correctly returns 1 DUIDs ✓ should have no duplicates in the returned arrays, 8192 IDs each, and combined. (58ms) #getDUIDInt() ✓ Asked for 1 Int DUIDs, correctly returns 1 Integer DUIDs ✓ Asked for 0 Int DUIDs, correctly returns 0 Integer DUIDs ✓ Asked for 8192 Int DUIDs, correctly returns 8192 Integer DUIDs ✓ Asked for 8193 Int DUIDs, correctly returns 1 Integer DUIDs ✓ should have no duplicates in the returned arrays, 8192 IDs each, and combined. DUID with drifting time ✓ should generate ID with -5046 millisecond drift into the past from now( 1439209924972 ), 25556418438868992 should be numerically smaller than 25556439607521280 ✓ should consistently generate unique IDs even when time is drifting backwards constantly (95ms) 37 passing (237ms) > email@example.com bench /Users/ian/GIT/short-duid > /usr/bin/env node benchmarks/test.js single DUIDInt generation x 1,853,262 ops/sec ±2.36% (87 runs sampled) batch of 10 DUIDInt generation (multiply by 10 to get IDs per second) x 243,338 ops/sec ±2.10% (80 runs sampled) batch of 1024 DUIDInt generation (multiply by 1024 to get IDs per second) x 2,533 ops/sec ±1.96% (87 runs sampled) batch of 4096 DUIDInt generation (multiply by 4096 to get IDs per second) x 690 ops/sec ±1.73% (93 runs sampled) single DUID generation x 596,227 ops/sec ±2.08% (88 runs sampled) batch of 10 DUID generation (multiply by 10 to get IDs per second) x 68,513 ops/sec ±1.76% (91 runs sampled) batch of 64 DUID generation (multiply by 64 to get IDs per second) x 11,204 ops/sec ±0.64% (92 runs sampled) single DUID generation (1 character salt) x 694,772 ops/sec ±1.05% (89 runs sampled) batch of 10 DUID generation (1 character salt) x 75,430 ops/sec ±1.04% (94 runs sampled) singe getRandomAPIKey generation x 130,049 ops/sec ±1.15% (87 runs sampled) single getRandomPassword generation x 149,621 ops/sec ±1.81% (89 runs sampled)
- Add more tests, time drifting and sequence overflow could be done better than now
- Simplify API further
- Improve error handling, at the moment most of them are silent and prefer overflow
- Add more examples
All are welcome to submit pull requests and patches
The MIT License (MIT)
Copyright (c) 2015 Ian Matyssik firstname.lastname@example.org
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.