sno

A spec for unique IDs in distributed systems based on the Snowflake design, e.g. a coordination-based ID variant. It aims to be friendly to both machines and humans, compact, versatile and fast.

This repository contains a Go library for generating such IDs.

go get -u github.com/muyo/sno

Status

Nearing stable - spec and API may fluctuate until a 1.0 tag expected around 2019/07.

Features

• 10 bytes in its binary representation, canonically encoded as 16 characters (➜ Encoding).
  The encoding is URL-safe and non-ambiguous. It also happens to be at the binary length of UUIDs - meaning snos can be stored as UUIDs in your database of choice, if that is preferred.
• K-sortable in either representation
• Embedded timestamp with a 4msec resolution, bounded within the years 2010 - 2079. Handles time regressions gracefully, without waiting (➜ Time and sequence)
• Embedded byte for arbitrary data (➜ Metabyte)
• ‭A pool of at minimum 16,384,000 IDs per second:
  65,536 guaranteed unique IDs per 4msec per partition (65,536 combinations) per metabyte (256 combinations) per tick-tock (1 bit adjustment for clock drifts ➜ Time and sequence). 549,755,813,888,000 is the global pool per second when the metabyte, partition and tick-tock are taken into account.
• Data layout straightforward to inspect or encode/decode (➜ Layout)
• Configuration and coordination optional (➜ Usage)
• Fast, wait-free, safe for concurrent use (➜ Benchmarks)
• Fills a niche (➜ Alternatives)

Non-features / cons

• True randomness. snos embed a counter and have no entropy. They are not suitable in a context where unpredictability of IDs is a must. They still, however, meet the common requirement of keeping internal counts (e.g. total number of entitites) unguessable and appear obfuscated;
• Time precision. While good enough for many use cases, not quite there for others. The ➜ Metabyte can be used to get around this limitation, however.
• It's 10 bytes, not 8. This is suboptimal as far as memory alignment is considered (platform dependent).

Usage

sno comes with a package-level generator on top of letting you configure your own generators.

Generating a new ID using the defaults takes no more than importing the package and:

id := sno.New(0)

Where 0 is the ➜ Metabyte.
Vide godoc for the entire API.

The global generator is immutable and private. It's therefore also not possible to restore it using a Snapshot. It uses 2 random bytes as its partition, meaning its partition changes across restarts.

As soon as you run more than 1 generator, you should start coordinating the creation of generators to actually guarantee a collision-free ride. This applies to all ID specs of the Snowflake variant.

Partitions

Partitions are one of several friends you have to get you those guarantees. A partition is 2 bytes. What they mean and how you define them is up to you.

generator, err := sno.NewGenerator(&sno.GeneratorSnapshot{
	Partition: sno.Partition{65, 255}, // the same as: sno.Partition{'A', 255}
}, nil)

Multiple generators can share a partition by dividing the sequence pool between them (➜ Sequence sharding).

Snapshots

Snapshots happen to serve both as configuration and a means of saving and restoring generator data. They are optional - simply pass nil to NewGenerator(), and what you get will be configured like the package-level generator, tied to a random partition.

Snapshots can be taken at runtime:

s := generator.Snapshot()

This exposes most of a generator's internal bookkeeping data. In an ideal world where programmers are not lazy even until their system runs into an edge case - you'd persist that snapshot across restarts and restore generators instead of just creating them from scratch each time. This will keep you safe both if a large clock drift happens during the restart -- or before, and you just happen to come back online again "in the past", relative to IDs that had already been generated.

A snapshot is a sample in time - it will very quickly get stale. Only take snapshots meant for restoring them later when generators are already offline - or for metrics purposes when online.

Layout

A sno is simply 80-bits comprised of two 40-bit blocks: the timestamp and the payload. The bytes are stored in big-endian order in all representations to retain their sortable property. Both blocks can be inspected and mutated independently in either representation. Bits of the components in the binary representation don't spill over into other bytes which means no additional bit twiddling voodoo is necessary* to extract them.

*The tick-tock bit in the timestamp is the only exception (➜ Time and sequence).

Time and sequence

Time

snos embed a timestamp comprised of 39 bits with the epoch milliseconds at a 4msec resolution (floored, unsigned) and one bit, the LSB of the entire block - for the tick-tock toggle.

Epoch

The epoch is custom and constant. It is bounded within 2010-01-01 00:00:00 UTC and 2079-09-07 15:47:35.548 UTC. The lower bound is 1262304000 seconds relative to Unix.

If you really have to break out of the epoch - or want to store higher precision - the metabyte is your friend.

Precision

Higher precision is not necessarily a good thing. Think in dataset and sorting terms, or in sampling rates. You want to grab all requests with an error code of 403 in a given second, where the code may be encoded in the metabyte. At a resolution of 1 second, you binary search for just one index and then proceed straight up linearly. That's simple enough.

At a resolution of 1msec however, you now need to find the corresponding 1000 potential starting offsets because your 403 requests are interleaved with the 200 requests (potentially). At 4msec, this is 250 steps.

Everything has tradeoffs. This was a compromise between precision, size, simple data layout -- and factors like that above.

Sequence

snos embed a sequence (2 bytes) that is relative to time. It does not overflow and resets on each new time unit (4msec). A higher sequence within a given timeframe does not necessarily indicate order of creation. It is not advertised as monotonic because its monotonicity is dependent on usage. A single generator writing to a single partition, ceteris paribus, will result in monotonic increments and will represent order of creation.

With multiple writers in the same partition, increment order is undefined. If the generator moves back in time, the order will still be monotonic but sorted either 2msec after or before IDs previously already written at that time (see tick-tock).

Sequence sharding

The sequence pool has a range of [0..65535] (inclusive). sno supports partition sharing out of the box by further sharding the sequence - that is multiple writers (generators) in the same partition.

This is done by dividing the pool between all writers, via user-specified bounds.

A generator will reset to its lower bound on each new time unit - and will never overflow its upper bound. Collisions are therefore guaranteed impossible unless misconfigured and they overlap with another currently online generator.

var PeoplePartition = sno.Partition{'P', 0}

// In process/container/remote host #1
generator1, err := sno.NewGenerator(&sno.GeneratorSnapshot{
	Partition: PeoplePartition,
	SequenceMin: 0,
	SequenceMax: 32767 // 32768 - 1
}, nil)

// In process/container/remote host #2
generator2, err := sno.NewGenerator(&sno.GeneratorSnapshot{
	Partition: PeoplePartition,
	SequenceMin: 32768,
	SequenceMax: 65535 // 65536 - 1
}, nil)

var requestIDGenerator, _ = sno.NewGenerator(&GeneratorSnapshot{
    SequenceMax: 32767,
}, nil)

type Service byte
type Call byte

const (
    UsersSvc   Service = 1
    UserList   Call    = 1
    UserCreate Call    = 2
    UserDelete Call    = 3
)

func genRequestID(svc Service, methodID Call) sno.ID {
    id := requestIDGenerator.New(byte(svc))
    // Overwrites the upper byte of the fixed partition. 
    // In our case - we didn't define it but gave a non-nil snapshot, so it is {0, 0}.
    id[6] = byte(methodID)

    return id
}

Sequence overflow

Remember that limiting the sequence pool also limits max throughput of each generator. For an explanation on what happens when you're running at or over capacity, see the details below or take a look at ➜ Benchmarks which explains the numbers involved.

type SequenceOverflowNotification struct {
    Now   time.Time // Time of tick.
    Count uint32    // Number of currently overflowing generation calls.
    Ticks uint32    // For how many ticks in total we've already been dealing with the *current* overflow.
}

Clock drift and the tick-tock toggle

Just like all other specs that rely on clock times to resolve ambiguity, snos are prone to clock drifts. But unlike all those others specs, sno adjusts itself to the new time - instead of waiting (blocking), it tick-tocks.

The tl;dr applying to any system, really: ensure your deployments use properly synchronized system clocks (via NTP) to mitigate the size of drifts. Ideally, use a NTP server pool that applies a gradual smear for leap seconds. Despite the original Snowflake spec suggesting otherwise, using NTP in slew mode (to avoid regressions entirely) is not always a good idea.

Also remember that containers tend to get paused meaning their clocks are paused with them.

As far as sno, collisions and performance are concerned, in typical scenarios you can enjoy a wait-free ride
without requiring slew mode nor having to worry about even large drifts.

Metabyte

The metabyte is unique to sno across the specs the author researched, but the concept of embedding metadata in IDs is an ancient one. It's effectively just a byte-of-whatever-you-want-it-to-be - but perhaps 8-bits-of-whatever-you-want-them-to-be does a better job of explaining its versatility.

0 is a valid metabyte

sno is agnostic as to what that byte represents and it is optional. None of the properties of snos get violated if you simply pass a 0.

However, if you can't find use for it, then you may be better served using a different ID spec/library altogether (➜ Alternatives). You'd be wasting a byte that could give you benefits elsewhere.

Why?

Many databases, especially embedded ones, are extremely efficient when all you need is the keys - not all the data all those keys represent. None of the Snowflake-like specs would provide a means to do that without excessive overrides (or too small a pool to work with), essentially a different format altogether, and so - sno.

const (
	PersonType = iota
	OtherType
)

type Person struct {
	ID   sno.ID
	Name string
}

person := Person{
	ID:    sno.New(PersonType),
	Name: "A Special Snöflinga",
}

Information that describes something has the nice property of also helping to identify something across a sea of possibilities. It's a natural fit.

Do everyone a favor, though, and don't embed confidential information. It will stop being confidential and become public knowledge the moment you do that. Let's stick to nice property, avoiding PEBKAC.

Sort order and placement

The metabyte follows the timestamp. This clusters IDs by the timestamp and then by the metabyte (for example - the type of the entity), before the fixed partition.

If you were to use machine-ID based partitions across a cluster generating, say, Person entities, where Person corresponds to a metabyte of 1 - this has the neat property of grouping all People generated across the entirety of your system in the given timeframe in a sortable manner. In database terms, you could think of the metabyte as identifying a table that is sharded across many partitions - or as part of a compound key. But that's just one of many ways it can be utilized.

Placement at the beginning of the second block allows the metabyte to potentially both extend the timestamp block or provide additional semantics to the payload block. Even if you always leave it empty, sort order nor sort/insert performance won't be hampered.

But it's just a single byte!

A single byte is plenty.

Encoding

The encoding is a custom base32 variant stemming from base32hex. Let's not call it sno32. A canonically encoded sno is a regexp of [2-9a-x]{16}.

The following alphabet is used:

23456789abcdefghijklmnopqrstuvwx

This is 2 contiguous ASCII ranges: 50..57 (digits) and 97..120 (strictly lowercase letters).

On amd64 the enc/dec steps are vectorized and extremely cheap (➜ Benchmarks) if the CPU supports them.

Alternatives

All of the above link to Go implementations based on popularity (GH stars) or per recommended implementations in specs.

* Using canonical encoding.
** When used with a proper CSPRNG. The more important aspect is the distinction between entropy-based and coordination-based IDs. Sandflake and cuid do contain entropy, but not sufficient to rely on entropy alone to avoid collisions (3 bytes and 4 bytes respectively).
*** Had to.

Benchmarks

Platform: Go 1.12 | i7 4770K (Haswell; 4 physical, 8 logical cores) @ 4.4GHz | Win 10, ran on 2019/06/03 using tip branches of all libs.

Generation

Disclaimer: this comparison must not be taken for its raw numbers. See the explanation (primarily about the Unbounded suffix) afterwards.

BenchmarkSnoUnbounded   100000000               13.2 ns/op             0 B/op          0 allocs/op
BenchmarkXid            50000000                19.9 ns/op             0 B/op          0 allocs/op
BenchmarkSno            20000000                61.0 ns/op             0 B/op          0 allocs/op
BenchmarkUUIDv1         20000000                80.7 ns/op             0 B/op          0 allocs/op
BenchmarkSnowflake       5000000               244 ns/op               0 B/op          0 allocs/op
BenchmarkKSUID           5000000               264 ns/op               0 B/op          0 allocs/op
BenchmarkUUIDv4          5000000               269 ns/op              16 B/op          1 allocs/op
BenchmarkULID            5000000               282 ns/op              16 B/op          1 allocs/op
BenchmarkSandflake       5000000               297 ns/op               3 B/op          1 allocs/op
BenchmarkCuid            5000000               363 ns/op              55 B/op          4 allocs/op
BenchmarkSonyflake         50000             38969 ns/op               0 B/op          0 allocs/op

BenchmarkSnoUnbounded-8 100000000               17.8 ns/op             0 B/op          0 allocs/op
BenchmarkXid-8          100000000               18.2 ns/op             0 B/op          0 allocs/op
BenchmarkSno-8          20000000                61.0 ns/op             0 B/op          0 allocs/op
BenchmarkUUIDv4-8       10000000               143 ns/op              16 B/op          1 allocs/op
BenchmarkSandflake-8    10000000               179 ns/op               3 B/op          1 allocs/op
BenchmarkUUIDv1-8       10000000               181 ns/op               0 B/op          0 allocs/op
BenchmarkSnowflake-8     5000000               244 ns/op               0 B/op          0 allocs/op
BenchmarkCuid-8          5000000               344 ns/op              55 B/op          4 allocs/op
BenchmarkULID-8          5000000               392 ns/op              16 B/op          1 allocs/op
BenchmarkKSUID-8         3000000               404 ns/op               0 B/op          0 allocs/op
BenchmarkSonyflake-8       50000             38995 ns/op               0 B/op          0 allocs/op

Notes: Each ran in isolation, averages from 10 runs each. The increase in sno's unbounded case was somewhat unexpected in the parallel test (branch prediction?) but remained consistent.

Encoding/decoding

BenchmarkSnoEncodeVector-8          2000000000               0.85 ns/op           0 B/op          0 allocs/op
BenchmarkSnoEncodeScalar-8          1000000000               2.21 ns/op           0 B/op          0 allocs/op
BenchmarkSnoEncodePureGoFallback-8  1000000000               2.66 ns/op           0 B/op          0 allocs/op
BenchmarkStdLibEncode-8             30000000                12.5 ns/op            0 B/op          0 allocs/op

BenchmarkSnoDecodeVector-8          2000000000               1.02 ns/op           0 B/op          0 allocs/op
BenchmarkSnoDecodeScalar-8          500000000                2.41 ns/op           0 B/op          0 allocs/op
BenchmarkSnoDecodePureGoFallback-8  500000000                3.10 ns/op           0 B/op          0 allocs/op
BenchmarkStdLibDecode-8             50000000                31.8 ns/op            0 B/op          0 allocs/op

The above forms the baseline. Comparisons below use the vectorized assembly code in sno's case.

Go's std library for reference only, as a cost estimate - it handles arbitrary sizes, padding and validation, and can't make assumptions like our libraries can.

Comparison

Encoding

BenchmarkSno-8          2000000000               1.19 ns/op            0 B/op          0 allocs/op
BenchmarkXid-8          500000000                3.79 ns/op            0 B/op          0 allocs/op
BenchmarkULID-8         300000000                5.82 ns/op            0 B/op          0 allocs/op
BenchmarkSnowflake-8    100000000               16.1 ns/op            32 B/op          1 allocs/op
BenchmarkSandflake-8    100000000               18.2 ns/op            32 B/op          1 allocs/op
BenchmarkUUIDv4-8       100000000               18.3 ns/op            48 B/op          1 allocs/op
BenchmarkUUIDv1-8       100000000               18.9 ns/op            48 B/op          1 allocs/op
BenchmarkKSUID-8        30000000                55.2 ns/op             0 B/op          0 allocs/op

Using: String(), provided by all packages.

Decoding

BenchmarkSno-8          2000000000               1.14 ns/op            0 B/op          0 allocs/op
BenchmarkUlid-8         300000000                5.05 ns/op            0 B/op          0 allocs/op
BenchmarkXid-8          200000000                6.90 ns/op            0 B/op          0 allocs/op
BenchmarkSnowflake-8    200000000                7.32 ns/op            0 B/op          0 allocs/op
BenchmarkKSUID-8        30000000                36.0 ns/op             0 B/op          0 allocs/op
BenchmarkUUIDv1-8       50000000                36.1 ns/op            48 B/op          1 allocs/op
BenchmarkUUIDv4-8       50000000                36.4 ns/op            48 B/op          1 allocs/op
BenchmarkSandflake-8    20000000                89.5 ns/op            32 B/op          1 allocs/op

Using: sno.FromEncodedString, xid.FromString, snowflake.ParseString, sandflake.Parse, ksuid.Parse,
ulid.Parse, uuid.FromString

Sonyflake has no canonical encoding and cuid is base36 only (no binary representation) so they were not included. Expect JSON (un)marshal performance to be similar.

Attributions

sno is both based on and inspired by xid - more so than by the original Snowflake - but the changes it introduces are unfortunately incompatible with xid's spec.

Further reading

• Original Snowflake implementation and related post
• Mongo ObjectIds
• Instagram: Sharding & IDs at Instagram
• Flickr: Ticket Servers: Distributed Unique Primary Keys on the Cheap
• Segment: A brief history of the UUID - about KSUID and the shortcomings of UUIDs.
• Farfetch: Unique integer generation in distributed systems - uint32 utilizing Cassandra to coordinate.

Also potentially of interest:

• Lamport timestamps (vector/logical clocks)
• The Bloom Clock by Lum Ramabaja