safe_int_id

Description:

safe int id

SafeIntId #
Uncoordinated unique ID that fits MAX_SAFE_INTEGER on web platform for long enough time.
Existing solutions #
There are a lot
of well-designed unique IDs. Few well-known ones are, alphabetically:
Cuid2,
KSUID,
Nano ID,
ObjectId,
Push ID,
Sharding ID,
Snowflake ID,
Sonyflake,
ULID,
UUID,
XID.
These IDs are great for their use cases, but none meets our special requirements.
Requirements #

ID should fit signed 64-bit int as in Isar Database ID.
ID should fit +/- (2⁵³-1) as in safe integers on web platform.
IDs should be generated at multiple places without coordination over the network
as in offline-first app running on multiple devices.
IDs created at different moments of time should have zero probability of collision,
not just small one.
IDs should be unique as much as possible given the constraints above.

Nice to have #

IDs could be sorted by their created-at timestamp.
This timestamp could be extractable from ID.
ID could be URL-friendly.

Max ID is 9007199254740991 which is URL-friendly as is.
If you need even shorter string, you can encode and decode ID, e.g:

9007199254740991.toRadixString(36) == "2gosa7pa2gv"
int.parse("2gosa7pa2gv", radix: 36) == 9007199254740991




ID could optionally contain an auto-incrementing counter instead of a random part.

Not required #

We don't require ID to be highly unpredictable:
we'd use auto-increment ID, but it would collide without coordination.

Design and usage #

Import:
import 'package:safe_int_id/safe_int_id.dart';
copied to clipboard

Get a new ID:
final id = safeIntId.getId();
copied to clipboard

ID is a positive integer less or equal than 2⁵³-1 for some number of years.
We could have 54 bits by using negative integers too,
but this would increase complexity and reduce compatibility.
So we have 53 bits.


ID contains, by default:

43 bits of timestamp:

Milliseconds since the UTC start of the first year you use this ID,
2023 by default, configurable:
final customId = SafeIntId(firstYear: 2024);
copied to clipboard

To get DateTime when given id was created at:
safeIntId.getCreatedAt(id) is DateTime
copied to clipboard

43 bits give us more than 278 years of millisecond-precise timestamps:
pow(2, 43) / (1000*60*60*24*365.2425) > 278
copied to clipboard

So for the default first year 2023 the last safe year is 2300, good enough.


10 bits of random:

Non-secure random generator is used by default:
it is always available and is faster than the secure one.
If you prefer secure random generator, it is configurable:
final customId = SafeIntId(random: Random.secure());
copied to clipboard

10 random bits give 1024 possible values per millisecond, configurable
in exchange for how many years since firstYear this ID will be safe:
final customId = SafeIntId(randomValues: 2048);
assert(customId.safeYears == 139);
assert(customId.lastSafeYear == 2161);
copied to clipboard






| random | default firstYear 2023 |
| bits | randomValues | safeYears | lastSafeYear |
| ------ | ------------ | --------- | ------------ |
| 8 | 256 | 1114 | 3136 |
| 9 | 512 | 557 | 2579 |
| 10 | default 1024 | 278 | 2300 |
| 11 | 2048 | 139 | 2161 |
| 12 | 4096 | 69 | 2091 |
| 13 | 8192 | 34 | 2056 |
| 14 | 16384 | 17 | 2039 |
| 15 | 32768 | 8 | 2030 |
| 16 | 65536 | 4 | 2026 |
copied to clipboard

Probability of generating more than one ID with the same value
is approximately N²/2M,
where:

M is randomValues - how many possible values we have.
N is how many IDs per millisecond we generate.
For N = 1 or less the probability is exactly zero for any M.
For N = 2 and default M = 1024 we have probability 0.002 = 0.2%.
2 IDs per millisecond means 2K IDs per second,
120K IDs per minute, 7.2M IDs per hour.
To get 1% probability of collision with default M = 1024 we need to generate
sqrt(2*1024*0.01) = 5 IDs per millisecond,
5K IDs per second, 272K IDs per minute, 16M IDs per hour.
Please check the table below to adjust SafeIntId(randomValues: M) if needed.
This approximation works well for probabilities of 50% or less,
so the higher ones are not shown.



| M | N |
| | 1 | 2 | 5 | 10 | 20 | 30 | 40 | 60 | 80 | 100 | 150 | 200 | 250 |
|------ | - | ------ | ----- | ---- | ---- | --- | --- | --- | --- | --- | --- | --- | --- |
| 256 | 0 | 0.8% | 4.9% | 20% | | | | | | | | | |
| 512 | 0 | 0.4% | 2.4% | 10% | 39% | | | | | | | | |
| 1024 | 0 | 0.2% | 1.2% | 4.9% | 20% | 44% | | | | | | | |
| 2048 | 0 | 0.1% | 0.6% | 2.4% | 10% | 22% | 39% | | | | | | |
| 4096 | 0 | 0.05% | 0.3% | 1.2% | 5% | 11% | 20% | 44% | | | | | |
| 8192 | 0 | 0.02% | 0.15% | 0.6% | 2% | 5% | 10% | 22% | 39% | | | | |
| 16384 | 0 | 0.01% | 0.08% | 0.3% | 1% | 3% | 5% | 11% | 20% | 31% | | | |
| 32768 | 0 | 0.01% | 0.04% | 0.2% | 1% | 1% | 2% | 5% | 10% | 15% | 34% | | |
| 65536 | 0 | 0.003% | 0.01% | 0.1% | 0.3% | 1% | 1% | 3% | 5% | 8% | 17% | 31% | 48% |
copied to clipboard

If you generate a lot of IDs on the same device,
use incId() instead of getId():

incId() increments a counter instead of using a random value.
This counter resets to zero each millisecond, and blocks reaching randomValues (1024 by default).
If a hot loop for less than 1 millisecond burns,
use await incIdAsync() or increase randomValues in exchange for safeYears.
This way you can get an increasing sequence of unique IDs.