loulid

package module
v2.0.0-...-d9cefa2 Latest Latest
Warning

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

 Go to latest Published: Oct 22, 2024 License: Apache-2.0 Imports: 11 Imported by: 0

README

Lowercased Universally Unique Lexicographically Sortable Identifier

Project status Build Status Go Report Card Coverage Status go.dev reference Apache 2 licensed

A Go port of ulid/javascript 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

This package requires Go modules.

go get github.com/GalvinGao/loulid/v2

Usage

ULIDs are constructed from two things: a timestamp with millisecond precision, and some random data.

Timestamps are modeled as uint64 values representing a Unix time in milliseconds. They can be produced by passing a time.Time to loulid.Timestamp, or by calling time.Time.UnixMilli and converting the returned value to uint64.

Random data is taken from a provided io.Reader. This design allows for greater flexibility when choosing trade-offs, but can be a bit confusing to newcomers.

If you just want to generate a ULID and don't (yet) care about details like performance, cryptographic security, etc., use the loulid.Make helper function. This function calls time.Now to get a timestamp, and uses a source of entropy which is process-global, pseudo-random, and monotonic.

fmt.Println(loulid.Make())
// 01G65Z755AFWAKHE12NY0CQ9FH

More advanced use cases should utilize loulid.New.

entropy := rand.New(rand.NewSource(time.Now().UnixNano()))
ms := loulid.Timestamp(time.Now())
fmt.Println(loulid.New(ms, entropy))
// 01G65Z755AFWAKHE12NY0CQ9FH

Care should be taken when providing a source of entropy.

The above example utilizes math/rand.Rand, which is not safe for concurrent use by multiple goroutines. Consider alternatives such as x/exp/rand. Security-sensitive use cases should always use cryptographically secure entropy provided by crypto/rand.

Performance-sensitive use cases should avoid synchronization when generating IDs. One option is to use a unique source of entropy for each concurrent goroutine, which results in no lock contention, but cannot provide strong guarantees about the random data, and does not provide monotonicity within a given millisecond. One common performance optimization is to pool sources of entropy using a sync.Pool.

Monotonicity is a property that says each ULID is "bigger than" the previous one. ULIDs are automatically monotonic, but only to millisecond precision. ULIDs generated within the same millisecond are ordered by their random component, which means they are by default un-ordered. You can use loulid.MonotonicEntropy or loulid.LockedMonotonicEntropy to create ULIDs that are monotonic within a given millisecond, with caveats. See the documentation for details.

If you don't care about time-based ordering of generated IDs, then there's no reason to use ULIDs! There are many other kinds of IDs that are easier, faster, smaller, etc. Consider UUIDs.

Commandline tool

This repo also provides a tool to generate and parse ULIDs at the command line.

go install github.com/GalvinGao/loulid/v2/cmd/ulid@latest

Usage:

Usage: ulid [-hlqz] [-f <format>] [parameters ...]
 -f, --format=<format>  when parsing, show times in this format: default, rfc3339, unix, ms
 -h, --help             print this help text
 -l, --local            when parsing, show local time instead of UTC
 -q, --quick            when generating, use non-crypto-grade entropy
 -z, --zero             when generating, fix entropy to all-zeroes

Examples:

$ ulid
01D78XYFJ1PRM1WPBCBT3VHMNV
$ ulid -z
01D78XZ44G0000000000000000
$ ulid 01D78XZ44G0000000000000000
Sun Mar 31 03:51:23.536 UTC 2019
$ ulid --format=rfc3339 --local 01D78XZ44G0000000000000000
2019-03-31T05:51:23.536+02:00

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 10889 AD

Entropy

  • 80 bits
  • User defined entropy source.
  • Monotonicity within the same millisecond with loulid.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 a 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")

	// Zero is a zero-value ULID.
	Zero ULID
)

Functions

func DefaultEntropy 

func DefaultEntropy() io.Reader

DefaultEntropy returns a thread-safe per process monotonically increasing entropy source.

func MaxTime 

func MaxTime() uint64

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

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 

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 LockedMonotonicReader 

type LockedMonotonicReader struct {
	MonotonicReader
	// contains filtered or unexported fields
}

LockedMonotonicReader wraps a MonotonicReader with a sync.Mutex for safe concurrent use.

func (*LockedMonotonicReader) MonotonicRead 

func (r *LockedMonotonicReader) MonotonicRead(ms uint64, p []byte) (err error)

MonotonicRead synchronizes calls to the wrapped MonotonicReader.

type MonotonicEntropy 

type MonotonicEntropy struct {
	io.Reader
	// contains filtered or unexported fields
}

MonotonicEntropy is an opaque type that provides monotonic entropy.

func Monotonic 

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

Monotonic returns a source of entropy that yields strictly increasing entropy bytes, to a limit governeed by the `inc` parameter.

Specifically, calls to MonotonicRead within the same ULID timestamp return entropy incremented by a random number between 1 and `inc` inclusive. If an increment results in entropy that would overflow available space, MonotonicRead returns ErrMonotonicOverflow.

Passing `inc == 0` results in the reasonable default `math.MaxUint32`. Lower values of `inc` provide more monotonic entropy in a single millisecond, at the cost of easier "guessability" of generated ULIDs. If your code depends on ULIDs having secure entropy bytes, then it's recommended to use the secure default value of `inc == 0`, unless you know what you're doing.

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

The returned type isn't safe for concurrent use.

func (*MonotonicEntropy) MonotonicRead 

func (m *MonotonicEntropy) MonotonicRead(ms uint64, entropy []byte) (err error)

MonotonicRead implements the MonotonicReader interface.

type MonotonicReader 

type MonotonicReader interface {
	io.Reader
	MonotonicRead(ms uint64, p []byte) error
}

MonotonicReader is an interface that should yield monotonically increasing entropy into the provided slice for all calls with the same ms parameter. If a MonotonicReader is provided to the New constructor, its MonotonicRead method will be used instead of Read.

type ULID 

type ULID [16]byte

A 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 
t := time.Unix(1000000, 0)
entropy := loulid.Monotonic(rand.New(rand.NewSource(t.UnixNano())), 0)
fmt.Println(loulid.MustNew(loulid.Timestamp(t), entropy))

Output:

0000xsnjg0mqjhbf4qx1efd6y3

func Make 

func Make() (id ULID)

Make returns a ULID with the current time in Unix milliseconds and monotonically increasing entropy for the same millisecond. It is safe for concurrent use, leveraging a sync.Pool underneath for minimal contention.

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 MustNewDefault 

func MustNewDefault(t time.Time) ULID

MustNewDefault is a convenience function equivalent to MustNew with DefaultEntropy as the entropy. It may panic if the given time.Time is too large or too small.

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 

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 a 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.

Safety for concurrent use is only dependent on the safety of the entropy source.

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 

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) Bytes 

func (id ULID) Bytes() []byte

Bytes returns bytes slice representation of ULID.

func (ULID) Compare 

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) IsZero 

func (id ULID) IsZero() bool

IsZero returns true if the ULID is a zero-value ULID, i.e. loulid.Zero.

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 

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) Timestamp 

func (id ULID) Timestamp() time.Time

Timestamp returns the time encoded in the ULID as 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 a 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 

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

Value implements the sql/driver.Valuer interface, returning the ULID as a slice of bytes, by invoking MarshalBinary. If your use case requires a string representation instead, you can create a wrapper type that calls String() instead. 

type stringValuer loulid.ULID

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

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

All valid ULIDs, including zero-value ULIDs, return a valid Value with a nil error. If your use case requires zero-value ULIDs to return a non-nil error, you can create a wrapper type that special-cases this behavior. 

var zeroValueULID loulid.ULID

type invalidZeroValuer loulid.ULID

func (v invalidZeroValuer) Value() (driver.Value, error) {
    if loulid.ULID(v).Compare(zeroValueULID) == 0 {
        return nil, fmt.Errorf("zero value")
    }
    return loulid.ULID(v).Value()
}

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

Source Files

View all Source files

Directories

Path Synopsis
cmd
ulid

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.