Koid

Koid generator yields k-ordered, conflict-free ids in a distributed environment, based on flake-idgen

Install

Install global deps for development

1npm i -g c8 lerna madge rollup tsx zx
2``````sh
3npm i koid

Koid Numbers Format

The Koid is made up of: timestamp, dataCenter, worker and counter. Examples in the following table:

Timestamp	Datacenter	Worker	Counter	Koid
0x8c20543b0	0b00000	0b00000	0x000	0x02308150ec000000
0x8c20543b1	0b00000	0b00000	0x000	0x02308150ec400000
0x8c20543b1	0b00000	0b00000	0x001	0x02308150ec400001
0x8c20543b1	0b00000	0b00000	0x002	0x02308150ec400002
0x8c20543b1	0b00000	0b00000	0x003	0x02308150ec400003
0x8c20c0335	0b00011	0b00001	0x000	0x02308300cd461000
0x8c20c0335	0b00011	0b00001	0x001	0x02308300cd461001

As you can see, each Koid is 64 bits long, consisting of:

• timestamp, a 42 bit long number of milliseconds elapsed since 1 January 1970 00:00:00 UTC
• dataCenter, a 5 bit long datacenter identifier. It can take up to 32 unique values (including 0)
• worker, a 5 bit long worker identifier. It can take up to 32 unique values (including 0)
• counter, a 12 bit long counter of ids in the same millisecond. It can take up to 4096 unique values.

Breakdown of bits for an id e.g. 5828128208445124608 (counter is 0, dataCenter is 7 and worker 3) is as follows:

 010100001110000110101011101110100001000111 00111 00011 000000000000
                                                       | ------------ | 12 bit counter |
                                                       | ------------ |5 bit worker
                                           |-----|                     5 bit datacenter
                                           | ----- ----- | 10 bit generator identifier |
                                           | ----------- |42 bit timestamp

Usage

Koid Generator returns 8 byte long node Buffer objects with its bytes representing 64 bit long id. Note that the number is stored in Big Endian format i.e. the most significant byte of the number is stored in the smallest address given and the least significant byte is stored in the largest.

Koid generator instance has one getter next returning generated id.

1import { KoidFactory } from 'koid'
2
3const koid = KoidFactory()
4
5console.log(koid.next)
6console.log(koid.next)
7console.log(koid.next)
8console.log(koid.nextBigint)

It would give something like:

<Buffer 50 dd d5 99 01 c0 00 00>
<Buffer 50 dd d5 99 02 80 00 00>
<Buffer 50 dd d5 99 02 80 00 01>
5827048346035945474n

Counter overflow

Koid generator can generate up to 4096 unique identifiers within a millisecond. When generator tries to generate more than 4096 identifiers within a millisecond, an error is thrown.

Additional generator setup parameters

Koid generator constructor takes optional parameter (generator configuration options) with the following properties:

• dataCenter (5 bit) - datacenter identifier. It can have values from 0 to 31.
• worker (5 bit) - worker identifier. It can have values from 0 to 31.
• id (10 bit) - generator identifier. It can have values from 0 to 1023. It can be provided instead of dataCenter and worker identifiers.
• epoch - number used to reduce value of a generated timestamp. Note that this number should not exceed number of milliseconds elapsed since 1 January 1970 00:00:00 UTC. It can be used to generate smaller ids.

Example of using dataCenter and worker identifiers:

1import { KoidFactory } from 'koid'
2
3const koid = KoidFactory()
4const koid2 = KoidFactory({ dataCenter: 9, worker: 7 })
5
6console.info(koid.next);
7console.info(koid2.next);

It would give something like:

<Buffer 50 dd da 8f 43 40 00 00>
<Buffer 50 dd da 8f 43 d2 70 00>

Properties

Koid generator has config getter that can be read from a generator instance:

• dataCenter - returns worker number used for generator creation
• worker - returns worker number used for generator creation

1import { KoidFactory } from 'koid'
2
3const koid = KoidFactory({ id: 34 })
4
5console.info(koid.dataCenter);   // 1
6console.info(koid.worker);       // 2

Clock moving backward

From time to time Node.js clock may move backward. In most cases it is only a few millisecond. However, as the generator relies on current timestamp, it won't be able to generate conflict-free identifiers (i.e. without duplicates) until the clock catches up with the last timestamp value. In case of clock move backward an error is thrown.

Formatting

Koid generator returns Node.js Buffer representing 64-bit number for the sake of future extensions or returned buffer modifications. Node Buffer can also be very easily converted to string format

1import { KoidFactory } from 'koid'
2
3const koid = KoidFactory()
4
5const buf: Buffer = koid.next
6const id = buf.readBigInt64BE() // also koid.nextBigint
7const hexId = buf.toString('hex')
8

It would give something like:

1<Buffer 5d c2 cd d1 f4 fd 30 00>
26756188692651257856n // bigint
35dc2cdd1f4fd3000 // hex string

Midway.js

Update imports:

1// file src/configuration.ts
2import * as koid from '@mwcp/koid'
3
4@Configuration({
5  imports: [
6    koid,
7  ],
8})
9export class ContainerConfiguration implements ILifeCycle {
10}

Inject component:

1import { Inject } from '@midwayjs/decorator'
2
3export class RootClass {
4  @Inject() readonly koid: KoidComponent
5}

Enable route:

1// file src/config/config.{prod|local|unittest}.ts
2// '2020-01-01T00:00:00Z'
3const epoch = 1577836800000
4const _koidConfig = genConfigRandom(epoch)
5export const koidConfig = {
6  ..._koidConfig,
7  enableDefaultRoute: true,
8}

then retrieve id from http api

• /koid/id return string
• /koid/hex return hext string

Benchmark

1.scripts/benchmark/start-benchmark.mjs --p midway-component-koid --api=koid/id

Packages

Package	Version
koid
@mwcp/koid

License

MIT

Languages

• English
• 中文