README
¶
Universally Unique Lexicographically Sortable Identifier
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 ¶
- Constants
- Variables
- func MaxTime() uint64
- func Monotonic(entropy io.Reader, inc uint64) io.Reader
- func Now() uint64
- func Time(ms uint64) time.Time
- func Timestamp(t time.Time) uint64
- type ULID
- func (id ULID) Compare(other ULID) int
- func (id ULID) Entropy() []byte
- func (id ULID) MarshalBinary() ([]byte, error)
- func (id ULID) MarshalBinaryTo(dst []byte) error
- func (id ULID) MarshalText() ([]byte, error)
- func (id ULID) MarshalTextTo(dst []byte) error
- func (id *ULID) Scan(src interface{}) error
- func (id *ULID) SetEntropy(e []byte) error
- func (id *ULID) SetTime(ms uint64) error
- func (id ULID) String() string
- func (id ULID) Time() uint64
- func (id *ULID) UnmarshalBinary(data []byte) error
- func (id *ULID) UnmarshalText(v []byte) error
- func (id ULID) Value() (driver.Value, error)
Examples ¶
Constants ¶
const EncodedSize = 26
EncodedSize is the length of a text encoded ULID.
const Encoding = "0123456789ABCDEFGHJKMNPQRSTVWXYZ"
Encoding is the base 32 encoding alphabet used in ULID strings.
Variables ¶
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
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())
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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
func MustNew ¶
MustNew is a convenience function equivalent to New that panics on failure instead of returning an error.
func MustParse ¶
MustParse is a convenience function equivalent to Parse that panics on failure instead of returning an error.
func MustParseStrict ¶ added in v1.0.0
MustParseStrict is a convenience function equivalent to ParseStrict that panics on failure instead of returning an error.
func New ¶
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 ¶
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
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
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) MarshalBinary ¶
MarshalBinary implements the encoding.BinaryMarshaler interface by returning the ULID as a byte slice.
func (ULID) MarshalBinaryTo ¶
MarshalBinaryTo writes the binary encoding of the ULID to the given buffer. ErrBufferSize is returned when the len(dst) != 16.
func (ULID) MarshalText ¶
MarshalText implements the encoding.TextMarshaler interface by returning the string encoded ULID.
func (ULID) MarshalTextTo ¶
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
Scan implements the sql.Scanner interface. It supports scanning a string or byte slice.
func (*ULID) SetEntropy ¶
SetEntropy sets the ULID entropy to the passed byte slice. ErrDataSize is returned if len(e) != 10.
func (*ULID) SetTime ¶
SetTime sets the time component of the ULID to the given Unix time in milliseconds.
func (ULID) 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 ¶
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 ¶
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 ¶
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
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))