uid

README

Unique ID Generator Design

A distributed unique ID generator. Storing as a 60-bit integer while displaying as a 10-character long base64-like string.

Storage and Generator

Storage Format

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0|                      Timestamp                        :
+---------------------------------------------------------------+
:       |    10     |     9     |     8     |     7     |   6   :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
:         Timestamp         | Sequence Number |   Random Bits   |
+---------------------------------------------------------------+
: 6 |     5     |     4     |     3     |     2     |     1     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1. Timestamp: 48-bit

Milliseconds elapsed since '2018-03-01T00:00:00.000Z'.

2. Sequence Number: 9-bit

A self-incremental number generated by a Worker. Increases from 0 to 511, then back to 0 again.

Sequence number must be unique in one millisecond. If all sequence numbers are used in that second, the generator must wait until the next second. So the generator can generate 2 ** 9 unique IDs per millisecond. Considering the following random 9-bits, it's can't be deplicated in usual usage.

3. Random bits: 9-bit

No special requirements.

Display Format

Storage format is designed for conveniently saving, indexing and comparing in the database. When displaying to users, storage format is converted to a base64-like string for better readability.

Frequently variable parts of the string are placed at the beginning and the end of it on purpose, so it looks like a complete random ID.

Characters

Every 6 bits are converted to the following characters (from 000000 to 111111):

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_

Rule

Decoding from the storage format to display format: convert to base64 string, and move last two character to the base64 string's header.

Encoding is the reverse of decoding.

For example, generated an new storage format which is "11093174944930914", convert it to base64 is "naS8QBhxi":, and the display format is: "xinaS8QBh".

Documentation

Index

• func RandomBase64Str(length int) string
• type Generator
  • func (g *Generator) NewUID() UID
• type UID
  • func NewUID() UID
  • func ParseUID(s string) (UID, error)
  • func (u UID) GetTime() time.Time
  • func (u UID) MarshalGQL(w io.Writer)
  • func (u UID) ToBase64String() string
  • func (u *UID) UnmarshalGQL(v interface{}) error

Functions

func RandomBase64Str

func RandomBase64Str(length int) string

Types

type Generator

type Generator struct {
	// contains filtered or unexported fields
}

func (*Generator) NewUID

func (g *Generator) NewUID() UID

type UID

type UID int64

func NewUID

func NewUID() UID

func ParseUID

func ParseUID(s string) (UID, error)

func (UID) GetTime

func (u UID) GetTime() time.Time

func (UID) MarshalGQL

func (u UID) MarshalGQL(w io.Writer)

MarshalGQL for UID scalar type in graphql

func (UID) ToBase64String

func (u UID) ToBase64String() string

func (*UID) UnmarshalGQL

func (u *UID) UnmarshalGQL(v interface{}) error

UnmarshalGQL for UID scalar type in graphql