ulid

package module
v1.3.1 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Oct 2, 2018 License: Apache-2.0 Imports: 10 Imported by: 0

README

Universally Unique Lexicographically Sortable Identifier

Project status Build Status Go Report Card Coverage Status GoDoc Apache 2 licensed

A Go port of alizain/ulid with binary format implemented.

Background

A GUID/UUID can be suboptimal for many use-cases because:

  • It isn't the most character efficient way of encoding 128 bits
  • UUID v1/v2 is impractical in many environments, as it requires access to a unique, stable MAC address
  • UUID v3/v5 requires a unique seed and produces randomly distributed IDs, which can cause fragmentation in many data structures
  • UUID v4 provides no other information than randomness which can cause fragmentation in many data structures

A ULID however:

  • Is compatible with UUID/GUID's
  • 1.21e+24 unique ULIDs per millisecond (1,208,925,819,614,629,174,706,176 to be exact)
  • Lexicographically sortable
  • Canonically encoded as a 26 character string, as opposed to the 36 character UUID
  • Uses Crockford's base32 for better efficiency and readability (5 bits per character)
  • Case insensitive
  • No special characters (URL safe)
  • Monotonic sort order (correctly detects and handles the same millisecond)

Install

go get github.com/oklog/ulid

Usage

An ULID is constructed with a time.Time and an io.Reader entropy source. This design allows for greater flexibility in choosing your trade-offs.

Please note that rand.Rand from the math package is not safe for concurrent use. Instantiate one per long living go-routine or use a sync.Pool if you want to avoid the potential contention of a locked rand.Source as its been frequently observed in the package level functions.

func ExampleULID() {
	t := time.Unix(1000000, 0)
	entropy := ulid.Monotonic(rand.New(rand.NewSource(t.UnixNano())), 0)
	fmt.Println(ulid.MustNew(ulid.Timestamp(t), entropy))
	// Output: 0000XSNJG0MQJHBF4QX1EFD6Y3
}

Specification

Below is the current specification of ULID as implemented in this repository.

Components

Timestamp

  • 48 bits
  • UNIX-time in milliseconds
  • Won't run out of space till the year 10895 AD

Entropy

  • 80 bits
  • User defined entropy source.
  • Monotonicity within the same millisecond with ulid.Monotonic
Encoding

Crockford's Base32 is used as shown. This alphabet excludes the letters I, L, O, and U to avoid confusion and abuse.

0123456789ABCDEFGHJKMNPQRSTVWXYZ
Binary Layout and Byte Order

The components are encoded as 16 octets. Each component is encoded with the Most Significant Byte first (network byte order).

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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      32_bit_uint_time_high                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     16_bit_uint_time_low      |       16_bit_uint_random      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       32_bit_uint_random                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       32_bit_uint_random                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
String Representation
 01AN4Z07BY      79KA1307SR9X4MV3
|----------|    |----------------|
 Timestamp           Entropy
  10 chars           16 chars
   48bits             80bits
   base32             base32

Test

go test ./...

Benchmarks

On a Intel Core i7 Ivy Bridge 2.7 GHz, MacOS 10.12.1 and Go 1.8.0beta1

BenchmarkNew/WithCryptoEntropy-8      2000000        771 ns/op      20.73 MB/s   16 B/op   1 allocs/op
BenchmarkNew/WithEntropy-8            20000000      65.8 ns/op     243.01 MB/s   16 B/op   1 allocs/op
BenchmarkNew/WithoutEntropy-8         50000000      30.0 ns/op     534.06 MB/s   16 B/op   1 allocs/op
BenchmarkMustNew/WithCryptoEntropy-8  2000000        781 ns/op      20.48 MB/s   16 B/op   1 allocs/op
BenchmarkMustNew/WithEntropy-8        20000000      70.0 ns/op     228.51 MB/s   16 B/op   1 allocs/op
BenchmarkMustNew/WithoutEntropy-8     50000000      34.6 ns/op     462.98 MB/s   16 B/op   1 allocs/op
BenchmarkParse-8                      50000000      30.0 ns/op     866.16 MB/s    0 B/op   0 allocs/op
BenchmarkMustParse-8                  50000000      35.2 ns/op     738.94 MB/s    0 B/op   0 allocs/op
BenchmarkString-8                     20000000      64.9 ns/op     246.40 MB/s   32 B/op   1 allocs/op
BenchmarkMarshal/Text-8               20000000      55.8 ns/op     286.84 MB/s   32 B/op   1 allocs/op
BenchmarkMarshal/TextTo-8             100000000     22.4 ns/op     714.91 MB/s    0 B/op   0 allocs/op
BenchmarkMarshal/Binary-8             300000000     4.02 ns/op    3981.77 MB/s    0 B/op   0 allocs/op
BenchmarkMarshal/BinaryTo-8           2000000000    1.18 ns/op   13551.75 MB/s    0 B/op   0 allocs/op
BenchmarkUnmarshal/Text-8             100000000     20.5 ns/op    1265.27 MB/s    0 B/op   0 allocs/op
BenchmarkUnmarshal/Binary-8           300000000     4.94 ns/op    3240.01 MB/s    0 B/op   0 allocs/op
BenchmarkNow-8                        100000000     15.1 ns/op     528.09 MB/s    0 B/op   0 allocs/op
BenchmarkTimestamp-8                  2000000000    0.29 ns/op   27271.59 MB/s    0 B/op   0 allocs/op
BenchmarkTime-8                       2000000000    0.58 ns/op   13717.80 MB/s    0 B/op   0 allocs/op
BenchmarkSetTime-8                    2000000000    0.89 ns/op    9023.95 MB/s    0 B/op   0 allocs/op
BenchmarkEntropy-8                    200000000     7.62 ns/op    1311.66 MB/s    0 B/op   0 allocs/op
BenchmarkSetEntropy-8                 2000000000    0.88 ns/op   11376.54 MB/s    0 B/op   0 allocs/op
BenchmarkCompare-8                    200000000     7.34 ns/op    4359.23 MB/s    0 B/op   0 allocs/op

Prior Art

Documentation

Index

Examples

Constants

View Source
const EncodedSize = 26

EncodedSize is the length of a text encoded ULID.

View Source
const Encoding = "0123456789ABCDEFGHJKMNPQRSTVWXYZ"

Encoding is the base 32 encoding alphabet used in ULID strings.

Variables

View Source
var (
	// ErrDataSize is returned when parsing or unmarshaling ULIDs with the wrong
	// data size.
	ErrDataSize = errors.New("ulid: bad data size when unmarshaling")

	// ErrInvalidCharacters is returned when parsing or unmarshaling ULIDs with
	// invalid Base32 encodings.
	ErrInvalidCharacters = errors.New("ulid: bad data characters when unmarshaling")

	// ErrBufferSize is returned when marshalling ULIDs to a buffer of insufficient
	// size.
	ErrBufferSize = errors.New("ulid: bad buffer size when marshaling")

	// ErrBigTime is returned when constructing an ULID with a time that is larger
	// than MaxTime.
	ErrBigTime = errors.New("ulid: time too big")

	// ErrOverflow is returned when unmarshaling a ULID whose first character is
	// larger than 7, thereby exceeding the valid bit depth of 128.
	ErrOverflow = errors.New("ulid: overflow when unmarshaling")

	// ErrMonotonicOverflow is returned by a Monotonic entropy source when
	// incrementing the previous ULID's entropy bytes would result in overflow.
	ErrMonotonicOverflow = errors.New("ulid: monotonic entropy overflow")

	// ErrScanValue is returned when the value passed to scan cannot be unmarshaled
	// into the ULID.
	ErrScanValue = errors.New("ulid: source value must be a string or byte slice")
)

Functions

func MaxTime

func MaxTime() uint64

MaxTime returns the maximum Unix time in milliseconds that can be encoded in an ULID.

func Monotonic added in v1.3.0

func Monotonic(entropy io.Reader, inc uint64) io.Reader

Monotonic returns an entropy source that is guaranteed to yield strictly increasing entropy bytes for the same ULID timestamp. On conflicts, the previous ULID entropy is incremented with a random number between 1 and `inc` (inclusive).

The provided entropy source must actually yield random bytes or else monotonic reads are not guaranteed to terminate, since there isn't enough randomness to compute an increment number.

When `inc == 0`, it'll be set to a secure default of `math.MaxUint32`. The lower the value of `inc`, the easier the next ULID within the same millisecond is to guess. If your code depends on ULIDs having secure entropy bytes, then don't go under this default unless you know what you're doing.

The returned io.Reader isn't safe for concurrent use.

func Now

func Now() uint64

Now is a convenience function that returns the current UTC time in Unix milliseconds. Equivalent to:

Timestamp(time.Now().UTC())

func Time added in v1.2.0

func Time(ms uint64) time.Time

Time converts Unix milliseconds in the format returned by the Timestamp function to a time.Time.

func Timestamp

func Timestamp(t time.Time) uint64

Timestamp converts a time.Time to Unix milliseconds.

Because of the way ULID stores time, times from the year 10889 produces undefined results.

Types

type ULID

type ULID [16]byte

An ULID is a 16 byte Universally Unique Lexicographically Sortable Identifier

The components are encoded as 16 octets.
Each component is encoded with the MSB first (network byte order).

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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      32_bit_uint_time_high                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     16_bit_uint_time_low      |       16_bit_uint_random      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       32_bit_uint_random                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       32_bit_uint_random                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Example
package main

import (
	"fmt"
	"math/rand"
	"time"

	"github.com/oklog/ulid"
)

func main() {
	t := time.Unix(1000000, 0)
	entropy := ulid.Monotonic(rand.New(rand.NewSource(t.UnixNano())), 0)
	fmt.Println(ulid.MustNew(ulid.Timestamp(t), entropy))
}
Output:

0000XSNJG0MQJHBF4QX1EFD6Y3

func MustNew

func MustNew(ms uint64, entropy io.Reader) ULID

MustNew is a convenience function equivalent to New that panics on failure instead of returning an error.

func MustParse

func MustParse(ulid string) ULID

MustParse is a convenience function equivalent to Parse that panics on failure instead of returning an error.

func MustParseStrict added in v1.0.0

func MustParseStrict(ulid string) ULID

MustParseStrict is a convenience function equivalent to ParseStrict that panics on failure instead of returning an error.

func New

func New(ms uint64, entropy io.Reader) (id ULID, err error)

New returns an ULID with the given Unix milliseconds timestamp and an optional entropy source. Use the Timestamp function to convert a time.Time to Unix milliseconds.

ErrBigTime is returned when passing a timestamp bigger than MaxTime. Reading from the entropy source may also return an error.

func Parse

func Parse(ulid string) (id ULID, err error)

Parse parses an encoded ULID, returning an error in case of failure.

ErrDataSize is returned if the len(ulid) is different from an encoded ULID's length. Invalid encodings produce undefined ULIDs. For a version that returns an error instead, see ParseStrict.

func ParseStrict added in v1.0.0

func ParseStrict(ulid string) (id ULID, err error)

ParseStrict parses an encoded ULID, returning an error in case of failure.

It is like Parse, but additionally validates that the parsed ULID consists only of valid base32 characters. It is slightly slower than Parse.

ErrDataSize is returned if the len(ulid) is different from an encoded ULID's length. Invalid encodings return ErrInvalidCharacters.

func (ULID) Compare added in v0.3.0

func (id ULID) Compare(other ULID) int

Compare returns an integer comparing id and other lexicographically. The result will be 0 if id==other, -1 if id < other, and +1 if id > other.

func (ULID) Entropy

func (id ULID) Entropy() []byte

Entropy returns the entropy from the ULID.

func (ULID) MarshalBinary

func (id ULID) MarshalBinary() ([]byte, error)

MarshalBinary implements the encoding.BinaryMarshaler interface by returning the ULID as a byte slice.

func (ULID) MarshalBinaryTo

func (id ULID) MarshalBinaryTo(dst []byte) error

MarshalBinaryTo writes the binary encoding of the ULID to the given buffer. ErrBufferSize is returned when the len(dst) != 16.

func (ULID) MarshalText

func (id ULID) MarshalText() ([]byte, error)

MarshalText implements the encoding.TextMarshaler interface by returning the string encoded ULID.

func (ULID) MarshalTextTo

func (id ULID) MarshalTextTo(dst []byte) error

MarshalTextTo writes the ULID as a string to the given buffer. ErrBufferSize is returned when the len(dst) != 26.

func (*ULID) Scan added in v1.0.0

func (id *ULID) Scan(src interface{}) error

Scan implements the sql.Scanner interface. It supports scanning a string or byte slice.

func (*ULID) SetEntropy

func (id *ULID) SetEntropy(e []byte) error

SetEntropy sets the ULID entropy to the passed byte slice. ErrDataSize is returned if len(e) != 10.

func (*ULID) SetTime

func (id *ULID) SetTime(ms uint64) error

SetTime sets the time component of the ULID to the given Unix time in milliseconds.

func (ULID) String

func (id ULID) String() string

String returns a lexicographically sortable string encoded ULID (26 characters, non-standard base 32) e.g. 01AN4Z07BY79KA1307SR9X4MV3 Format: tttttttttteeeeeeeeeeeeeeee where t is time and e is entropy

func (ULID) Time

func (id ULID) Time() uint64

Time returns the Unix time in milliseconds encoded in the ULID. Use the top level Time function to convert the returned value to a time.Time.

func (*ULID) UnmarshalBinary

func (id *ULID) UnmarshalBinary(data []byte) error

UnmarshalBinary implements the encoding.BinaryUnmarshaler interface by copying the passed data and converting it to an ULID. ErrDataSize is returned if the data length is different from ULID length.

func (*ULID) UnmarshalText

func (id *ULID) UnmarshalText(v []byte) error

UnmarshalText implements the encoding.TextUnmarshaler interface by parsing the data as string encoded ULID.

ErrDataSize is returned if the len(v) is different from an encoded ULID's length. Invalid encodings produce undefined ULIDs.

func (ULID) Value added in v1.0.0

func (id ULID) Value() (driver.Value, error)

Value implements the sql/driver.Valuer interface. This returns the value represented as a byte slice. If instead a string is desirable, a wrapper type can be created that calls String().

// stringValuer wraps a ULID as a string-based driver.Valuer.
type stringValuer ULID

func (id stringValuer) Value() (driver.Value, error) {
	return ULID(id).String(), nil
}

// Example usage.
db.Exec("...", stringValuer(id))

Directories

Path Synopsis
cmd

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL