safe_int_id 1.1.1 safe_int_id: ^1.1.1 copied to clipboard
Uncoordinated unique ID that fits MAX_SAFE_INTEGER on web platform for long enough time.
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
- Max ID is
- 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';
- Get a new ID:
final id = safeIntId.getId();
- 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);
- To get
DateTime
when givenid
was created at:safeIntId.getCreatedAt(id) is DateTime
- 43 bits give us more than 278 years of millisecond-precise timestamps:
pow(2, 43) / (1000*60*60*24*365.2425) > 278
- So for the default first year 2023 the last safe year is 2300, good enough.
- Milliseconds since the UTC start of the first year you use this ID,
2023 by default, configurable:
- 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());
- 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);
- 43 bits of timestamp:
| 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 |
- 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 is
| 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% |
- If you generate a lot of IDs on the same device,
use
incId()
instead ofgetId()
: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 increaserandomValues
in exchange forsafeYears
. - This way you can get an increasing sequence of unique IDs.