Skip to content

Latest commit

 

History

History
98 lines (77 loc) · 4.89 KB

eight-byte-id-structure.md

File metadata and controls

98 lines (77 loc) · 4.89 KB
Raw

Structure of the eight byte unique IDs

The eight byte IDs generated by the LocalUniqueIDGenerator and SynchronizedUniqueIDGenerator classes conform to the following structure:

TTTTTTTT TTTTTTTT TTTTTTTT TTTTTTTT TTTTTTTT TTSSSSSS GGGMGGGG GGGGCCCC
|                                              |      |  ||        |
v                                              |      |  |\        |
                                               |      v  \ \       |
Date of ID creation, measured in milliseconds  |          \ \      |
ellapsed since 1970-01-01T00:00:00.000,        | Generator \ \     |
represented in reverse byte-order (in SPREAD   | ID, see    | |    |
mode) to guarantee an even spread of IDs.      | below.     | |    |
                                               |            | |    |
                                               v            | |    |
                                                            | |    |
              Sequence. This field is incremented by the    | |    |
              generator for each ID generated during the    | |    |
              same timestamp.                               | |    |
                                                            | |    |
                                                            v |    |
                                                              |    |
                                                   Mode flag. |    |
                                                              |    |                                              
                                                              v    |
                                                                   |
                    Generator ID, manually assigned, or acquired   |
                    through negotiation via Etcd. Limited to 2048  |
                    per Cluster ID.                                |
                                                                   v

                                     Cluster ID. Always manually assigned
                                     or statically configured. Limited to
                                     16 (active) clusters.

This approach offers a few useful features:

  • Possible to generate a unique ID, in a computing environment that can have up to 256 processes generating IDs at the same time
  • Can generate IDs in isolation (e.g., on a backup database cluster, or off-line for maintenance) as long as there are no more than 16 of such isolated clusters
  • Can generate unique IDs at a decent rate (up to 64 IDs per millisecond, per generator)
  • IDs are lexicographically spread over the full byte range, making these IDs suitable for use in NoSQL or other key-value data stores as row/object keys.
  • Very short at only 8 bytes, and as such suitable as part of longer compound IDs, such as those used in key-value data stores.

Structure

Timestamp

The timestamp serves a dual purpose. Firstly, it helps guarantee uniqueness. As long as a generator has the exclusive use of a certain generator-ID/cluster-ID pair, and it uses the current time as the basis of the ID it is generating, it can be fairly sure that the resulting ID is unique. Secondly, the timestamp is a permanent record of the date of creation of the ID, which may be useful if is used as ID for a database record the moment it is created.

Because of the limited bit-size of the timestamp, only dates until the year 2109 are supported. As this library generates only 'now' timestamps, this should not be practical limitation.

Sequence counter

To prevent the generators from being limited to one ID per millisecond, the sequence counter adds 6 bits to the address space so up to 64 IDs per millisecond can be generated by a single generator. This is useful when a batch of IDs is pre-generated.

Reserved for future use

Unused bits. These are always zero in the current implementation, but may be used for future revisions.

Mode flag

Shows which mode the ID was generated in: SPREAD or TIME_SEQUENTIAL.

Generator IDs

Multiple generators can simultaneously generate IDs, as long as every generator holds a unique generator-ID/cluster-ID combination. The generator ID becomes part of the generated ID.

Within a single cluster generator IDs can either be assigned statically, or managed through a resource pool. There are 256 generator IDs available per cluster.

Cluster IDs

Usually, all your data resides within a single cluster. That is, a single computing environment wherein ID generation can be coordinated. The cluster ID enables you to generate IDs in separate clusters (or by means of an off-line operation separate from the primary cluster) that are unique across all clusters.

In contrast to the generator ID, which may be automatically assigned from a resource pool, the cluster ID is assigned statically per cluster, with a maximum of 16 (simultaneously) active clusters.