ksuid

package module
v1.0.2 Latest Latest
Warning

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

 Go to latest Published: Oct 3, 2018 License: MIT Imports: 11 Imported by: 0

README

ksuid Go Report Card GoDoc Circle CI

ksuid is a Go library that can generate and parse KSUIDs.

Install

go get -u github.com/segmentio/ksuid

What is a KSUID?

KSUID is for K-Sortable Unique IDentifier. It's a way to generate globally unique IDs similar to RFC 4122 UUIDs, but contain a time component so they can be "roughly" sorted by time of creation. The remainder of the KSUID is randomly generated bytes.

Why use KSUIDs?

Distributed systems often require unique IDs. There are numerous solutions out there for doing this, so why KSUID?

1. Sortable by Timestamp

Unlike the more common choice of UUIDv4, KSUIDs contain a timestamp component that allows them to be roughly sorted by generation time. This is obviously not a strong guarantee as it depends on wall clocks, but is still incredibly useful in practice.

2. No Coordination Required

Snowflake IDs[1] and derivatives require coordination, which significantly increases the complexity of implementation and creates operations overhead. While RFC 4122 UUIDv1s do have a time component, there aren't enough bytes of randomness to provide strong protections against duplicate ID generation.

KSUIDs use 128-bits of pseudorandom data, which provides a 64-times larger number space than the 122-bits in the well-accepted RFC 4122 UUIDv4 standard. The additional timestamp component drives down the extremely rare chance of duplication to the point of near physical infeasibility, even assuming extreme clock skew (> 24-hours) that would cause other severe anomalies.

  1. https://blog.twitter.com/2010/announcing-snowflake

3. Lexographically Sortable, Portable Representations

The binary and string representations are lexicographically sortable, which allows them to be dropped into systems which do not natively support KSUIDs and retain their k-sortable characteristics.

The string representation is that it is base62-encoded, so that they can "fit" anywhere alphanumeric strings are accepted.

How do they work?

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 allow lexicographic sorting. The timestamp epoch is adjusted to March 5th, 2014, providing over 100 years of useful life starting at UNIX epoch + 14e8. The payload uses a cryptographically-strong pseudorandom number generator.

The string representation is fixed at 27-characters encoded using a base62 encoding that also sorts lexicographically.

Command Line Tool

This package comes with a simple command-line tool ksuid. This tool can generate KSUIDs as well as inspect the internal components for debugging purposes.

Usage examples

Generate 4 KSUID
$ ./ksuid -n 4
0ujsszwN8NRY24YaXiTIE2VWDTS
0ujsswThIGTUYm2K8FjOOfXtY1K
0ujssxh0cECutqzMgbtXSGnjorm
0ujsszgFvbiEr7CDgE3z8MAUPFt
Inspect the components of a KSUID

Using the inspect formatting on just 1 ksuid:

$ ./ksuid -f inspect $(./ksuid)

REPRESENTATION:

  String: 0ujtsYcgvSTl8PAuAdqWYSMnLOv
     Raw: 0669F7EFB5A1CD34B5F99D1154FB6853345C9735

COMPONENTS:

       Time: 2017-10-09 21:00:47 -0700 PDT
  Timestamp: 107608047
    Payload: B5A1CD34B5F99D1154FB6853345C9735

Using the template formatting on 4 ksuid:

$ ./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 detailed versions of new KSUID

Generate a new KSUID with the corresponding time using the time formatting:

$ go run cmd/ksuid/main.go -f time -v
0uk0ava2lavfJwMceJOOEFXEDxl: 2017-10-09 21:56:00 -0700 PDT

Generate 4 new KSUID with details 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"}

Display the detailed version of a new KSUID:

$ ./ksuid -f inspect

REPRESENTATION:

  String: 0ujzPyRiIAffKhBux4PvQdDqMHY
     Raw: 066A029C73FC1AA3B2446246D6E89FCD909E8FE8

COMPONENTS:

       Time: 2017-10-09 21:46:20 -0700 PDT
  Timestamp: 107610780
    Payload: 73FC1AA3B2446246D6E89FCD909E8FE8

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

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)

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

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.