ksuid

package module
v1.0.4 Latest Latest
Warning

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

 Go to latest Published: Jul 14, 2021 License: MIT Imports: 11 Imported by: 1,502

README

ksuid Go Report Card GoDoc Circle CI

ksuid is an efficient, comprehensive, battle-tested Go library for generating and parsing a specific kind of globally unique identifier called a KSUID. This library serves as its reference implementation.

Install

go get -u github.com/segmentio/ksuid

What is a KSUID?

KSUID is for K-Sortable Unique IDentifier. It is a kind of globally unique identifier similar to a RFC 4122 UUID, built from the ground-up to be "naturally" sorted by generation timestamp without any special type-aware logic.

In short, running a set of KSUIDs through the UNIX sort command will result in a list ordered by generation time.

Why use KSUIDs?

There are numerous methods for generating unique identifiers, so why KSUID?

  1. Naturally ordered by generation time
  2. Collision-free, coordination-free, dependency-free
  3. Highly portable representations

Even if only one of these properties are important to you, KSUID is a great choice! :) Many projects chose to use KSUIDs just because the text representation is copy-and-paste friendly.

1. Naturally Ordered By Generation Time

Unlike the more ubiquitous UUIDv4, a KSUID contains a timestamp component that allows them to be loosely sorted by generation time. This is not a strong guarantee (an invariant) as it depends on wall clocks, but is still incredibly useful in practice. Both the binary and text representations will sort by creation time without any special sorting logic.

2. Collision-free, Coordination-free, Dependency-free

While RFC 4122 UUIDv1s do include a time component, there aren't enough bytes of randomness to provide strong protection against collisions (duplicates). With such a low amount of entropy, it is feasible for a malicious party to guess generated IDs, creating a problem for systems whose security is, implicitly or explicitly, sensitive to an adversary guessing identifiers.

To fit into a 64-bit number space, Snowflake IDs and its derivatives require coordination to avoid collisions, which significantly increases the deployment complexity and operational burden.

A KSUID includes 128 bits of pseudorandom data ("entropy"). This number space is 64 times larger than the 122 bits used by the well-accepted RFC 4122 UUIDv4 standard. The additional timestamp component can be considered "bonus entropy" which further decreases the probability of collisions, to the point of physical infeasibility in any practical implementation.

Highly Portable Representations

The text and binary representations are lexicographically sortable, which allows them to be dropped into systems which do not natively support KSUIDs and retain their time-ordered property.

The text representation is an alphanumeric base62 encoding, so it "fits" anywhere alphanumeric strings are accepted. No delimiters are used, so stringified KSUIDs won't be inadvertently truncated or tokenized when interpreted by software that is designed for human-readable text, a common problem for the text representation of RFC 4122 UUIDs.

How do KSUIDs work?

Binary KSUIDs are 20-bytes: a 32-bit unsigned integer UTC timestamp and a 128-bit randomly generated payload. The timestamp uses big-endian encoding, to support lexicographic sorting. The timestamp epoch is adjusted to March 5th, 2014, providing over 100 years of life. The payload is generated by a cryptographically-strong pseudorandom number generator.

The text representation is always 27 characters, encoded in alphanumeric base62 that will lexicographically sort by timestamp.

High Performance

This library is designed to be used in code paths that are performance critical. Its code has been tuned to eliminate all non-essential overhead. The KSUID type is derived from a fixed-size array, which eliminates the additional reference chasing and allocation involved in a variable-width type.

The API provides an interface for use in code paths which are sensitive to allocation. For example, the Append method can be used to parse the text representation and replace the contents of a KSUID value without additional heap allocation.

All public package level "pure" functions are concurrency-safe, protected by a global mutex. For hot loops that generate a large amount of KSUIDs from a single Goroutine, the Sequence type is provided to elide the potential contention.

By default, out of an abundance of caution, the cryptographically-secure PRNG is used to generate the random bits of a KSUID. This can be relaxed in extremely performance-critical code using the included FastRander type. FastRander uses the standard PRNG with a seed generated by the cryptographically-secure PRNG.

NOTE: While there is no evidence that FastRander will increase the probability of a collision, it shouldn't be used in scenarios where uniqueness is important to security, as there is an increased chance the generated IDs can be predicted by an adversary.

Battle Tested

This code has been used in production at Segment for several years, across a diverse array of projects. Trillions upon trillions of KSUIDs have been generated in some of Segment's most performance-critical, large-scale distributed systems.

Plays Well With Others

Designed to be integrated with other libraries, the KSUID type implements many standard library interfaces, including:

  • Stringer
  • database/sql.Scanner and database/sql/driver.Valuer
  • encoding.BinaryMarshal and encoding.BinaryUnmarshal
  • encoding.TextMarshal and encoding.TextUnmarshal (encoding/json friendly!)

Command Line Tool

This package comes with a command-line tool ksuid, useful for generating KSUIDs as well as inspecting the internal components of existing KSUIDs. Machine-friendly output is provided for scripting use cases.

Given a Go build environment, it can be installed with the command:

$ go install github.com/segmentio/ksuid/cmd/ksuid

CLI Usage Examples

Generate a KSUID
$ ksuid
0ujsswThIGTUYm2K8FjOOfXtY1K
Generate 4 KSUIDs
$ ksuid -n 4
0ujsszwN8NRY24YaXiTIE2VWDTS
0ujsswThIGTUYm2K8FjOOfXtY1K
0ujssxh0cECutqzMgbtXSGnjorm
0ujsszgFvbiEr7CDgE3z8MAUPFt
Inspect the components of a KSUID
$ ksuid -f inspect 0ujtsYcgvSTl8PAuAdqWYSMnLOv

REPRESENTATION:

  String: 0ujtsYcgvSTl8PAuAdqWYSMnLOv
     Raw: 0669F7EFB5A1CD34B5F99D1154FB6853345C9735

COMPONENTS:

       Time: 2017-10-09 21:00:47 -0700 PDT
  Timestamp: 107608047
    Payload: B5A1CD34B5F99D1154FB6853345C9735
Generate a KSUID and inspect its components
$ ksuid -f inspect

REPRESENTATION:

  String: 0ujzPyRiIAffKhBux4PvQdDqMHY
     Raw: 066A029C73FC1AA3B2446246D6E89FCD909E8FE8

COMPONENTS:

       Time: 2017-10-09 21:46:20 -0700 PDT
  Timestamp: 107610780
    Payload: 73FC1AA3B2446246D6E89FCD909E8FE8
Inspect a KSUID with template formatted inspection output
$ ksuid -f template -t '{{ .Time }}: {{ .Payload }}' 0ujtsYcgvSTl8PAuAdqWYSMnLOv
2017-10-09 21:00:47 -0700 PDT: B5A1CD34B5F99D1154FB6853345C9735
Inspect multiple KSUIDs with template formatted output
$ ksuid -f template -t '{{ .Time }}: {{ .Payload }}' $(ksuid -n 4)
2017-10-09 21:05:37 -0700 PDT: 304102BC687E087CC3A811F21D113CCF
2017-10-09 21:05:37 -0700 PDT: EAF0B240A9BFA55E079D887120D962F0
2017-10-09 21:05:37 -0700 PDT: DF0761769909ABB0C7BB9D66F79FC041
2017-10-09 21:05:37 -0700 PDT: 1A8F0E3D0BDEB84A5FAD702876F46543
Generate KSUIDs and output JSON using template formatting
$ ksuid -f template -t '{ "timestamp": "{{ .Timestamp }}", "payload": "{{ .Payload }}", "ksuid": "{{.String}}"}' -n 4
{ "timestamp": "107611700", "payload": "9850EEEC191BF4FF26F99315CE43B0C8", "ksuid": "0uk1Hbc9dQ9pxyTqJ93IUrfhdGq"}
{ "timestamp": "107611700", "payload": "CC55072555316F45B8CA2D2979D3ED0A", "ksuid": "0uk1HdCJ6hUZKDgcxhpJwUl5ZEI"}
{ "timestamp": "107611700", "payload": "BA1C205D6177F0992D15EE606AE32238", "ksuid": "0uk1HcdvF0p8C20KtTfdRSB9XIm"}
{ "timestamp": "107611700", "payload": "67517BA309EA62AE7991B27BB6F2FCAC", "ksuid": "0uk1Ha7hGJ1Q9Xbnkt0yZgNwg3g"}

Implementations for other languages

License

ksuid source code is available under an MIT License.

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var FastRander = newRBG()

FastRander is an io.Reader that uses math/rand and is optimized for generating 16 bytes KSUID payloads. It is intended to be used as a performance improvements for programs that have no need for cryptographically secure KSUIDs and are generating a lot of them.

Functions

func Compare 

func Compare(a, b KSUID) int

Implements comparison for KSUID type

func IsSorted 

func IsSorted(ids []KSUID) bool

IsSorted checks whether a slice of KSUIDs is sorted

func SetRand 

func SetRand(r io.Reader)

Sets the global source of random bytes for KSUID generation. This should probably only be set once globally. While this is technically thread-safe as in it won't cause corruption, there's no guarantee on ordering.

func Sort 

func Sort(ids []KSUID)

Sorts the given slice of KSUIDs

Types

type CompressedSet 

type CompressedSet []byte

CompressedSet is an immutable data type which stores a set of KSUIDs.

func AppendCompressed 

func AppendCompressed(set []byte, ids ...KSUID) CompressedSet

AppendCompressed uses the given byte slice as pre-allocated storage space to build a KSUID set.

Note that the set uses a compression technique to store the KSUIDs, so the resuling length is not 20 x len(ids). The rule of thumb here is for the given byte slice to reserve the amount of memory that the application would be OK to waste.

func Compress 

func Compress(ids ...KSUID) CompressedSet

Compress creates and returns a compressed set of KSUIDs from the list given as arguments.

func (CompressedSet) GoString 

func (set CompressedSet) GoString() string

String satisfies the fmt.GoStringer interface, returns a Go representation of the set.

func (CompressedSet) Iter 

func (set CompressedSet) Iter() CompressedSetIter

Iter returns an iterator that produces all KSUIDs in the set.

func (CompressedSet) String 

func (set CompressedSet) String() string

String satisfies the fmt.Stringer interface, returns a human-readable string representation of the set.

type CompressedSetIter 

type CompressedSetIter struct {
	// KSUID is modified by calls to the Next method to hold the KSUID loaded
	// by the iterator.
	KSUID KSUID
	// contains filtered or unexported fields
}

CompressedSetIter is an iterator type returned by Set.Iter to produce the list of KSUIDs stored in a set.

Here's is how the iterator type is commonly used: 

for it := set.Iter(); it.Next(); {
	id := it.KSUID
	// ...
}

CompressedSetIter values are not safe to use concurrently from multiple goroutines.

func (*CompressedSetIter) Next 

func (it *CompressedSetIter) Next() bool

Next moves the iterator forward, returning true if there a KSUID was found, or false if the iterator as reached the end of the set it was created from.

type KSUID 

type KSUID [byteLength]byte

KSUIDs are 20 bytes: 

00-03 byte: uint32 BE UTC timestamp with custom epoch
04-19 byte: random "payload"

var (

	// Represents a completely empty (invalid) KSUID
	Nil KSUID
	// Represents the highest value a KSUID can have
	Max = KSUID{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
)

func FromBytes 

func FromBytes(b []byte) (KSUID, error)

Constructs a KSUID from a 20-byte binary representation

func FromParts 

func FromParts(t time.Time, payload []byte) (KSUID, error)

Constructs a KSUID from constituent parts

func New 

func New() KSUID

Generates a new KSUID. In the strange case that random bytes can't be read, it will panic.

func NewRandom 

func NewRandom() (ksuid KSUID, err error)

Generates a new KSUID

func NewRandomWithTime 

func NewRandomWithTime(t time.Time) (ksuid KSUID, err error)

func Parse 

func Parse(s string) (KSUID, error)

Parse decodes a string-encoded representation of a KSUID object

func (KSUID) Append 

func (i KSUID) Append(b []byte) []byte

Append appends the string representation of i to b, returning a slice to a potentially larger memory area.

func (KSUID) Bytes 

func (i KSUID) Bytes() []byte

Raw byte representation of KSUID

func (KSUID) Get 

func (i KSUID) Get() interface{}

Get satisfies the flag.Getter interface, making it possible to use KSUIDs as part of of the command line options of a program.

func (KSUID) IsNil 

func (i KSUID) IsNil() bool

IsNil returns true if this is a "nil" KSUID

func (KSUID) MarshalBinary 

func (i KSUID) MarshalBinary() ([]byte, error)

func (KSUID) MarshalText 

func (i KSUID) MarshalText() ([]byte, error)

func (KSUID) Next 

func (id KSUID) Next() KSUID

Next returns the next KSUID after id.

func (KSUID) Payload 

func (i KSUID) Payload() []byte

The 16-byte random payload without the timestamp

func (KSUID) Prev 

func (id KSUID) Prev() KSUID

Prev returns the previoud KSUID before id.

func (*KSUID) Scan 

func (i *KSUID) Scan(src interface{}) error

Scan implements the sql.Scanner interface. It supports converting from string, []byte, or nil into a KSUID value. Attempting to convert from another type will return an error.

func (*KSUID) Set 

func (i *KSUID) Set(s string) error

Set satisfies the flag.Value interface, making it possible to use KSUIDs as part of of the command line options of a program.

func (KSUID) String 

func (i KSUID) String() string

String-encoded representation that can be passed through Parse()

func (KSUID) Time 

func (i KSUID) Time() time.Time

The timestamp portion of the ID as a Time object

func (KSUID) Timestamp 

func (i KSUID) Timestamp() uint32

The timestamp portion of the ID as a bare integer which is uncorrected for KSUID's special epoch.

func (*KSUID) UnmarshalBinary 

func (i *KSUID) UnmarshalBinary(b []byte) error

func (*KSUID) UnmarshalText 

func (i *KSUID) UnmarshalText(b []byte) error

func (KSUID) Value 

func (i KSUID) Value() (driver.Value, error)

Value converts the KSUID into a SQL driver value which can be used to directly use the KSUID as parameter to a SQL query.

type Sequence 

type Sequence struct {
	// The seed is used as base for the KSUID generator, all generated KSUIDs
	// share the same leading 18 bytes of the seed.
	Seed KSUID
	// contains filtered or unexported fields
}

Sequence is a KSUID generator which produces a sequence of ordered KSUIDs from a seed.

Up to 65536 KSUIDs can be generated by for a single seed.

A typical usage of a Sequence looks like this: 

seq := ksuid.Sequence{
	Seed: ksuid.New(),
}
id, err := seq.Next()

Sequence values are not safe to use concurrently from multiple goroutines.

func (*Sequence) Bounds 

func (seq *Sequence) Bounds() (min KSUID, max KSUID)

Bounds returns the inclusive min and max bounds of the KSUIDs that may be generated by the sequence. If all ids have been generated already then the returned min value is equal to the max.

func (*Sequence) Next 

func (seq *Sequence) Next() (KSUID, error)

Next produces the next KSUID in the sequence, or returns an error if the sequence has been exhausted.

Source Files

View all Source files

Directories

Path Synopsis
cmd
ksuid

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.