guid

package module
v3.1.0 Latest Latest
Warning

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

Go to latest
Published: Sep 27, 2026 License: Apache-2.0 Imports: 12 Imported by: 0

README

GUID

k-sorted unique identifiers in lock-free and decentralized manner for Golang applications


Package guid implements interface to generate k-sorted unique identifiers in lock-free and decentralized manner for Golang applications.

  𝑨[𝒊] ≤ 𝑨[𝒋]   whenever 𝒋 − 𝒊 ≥ 𝒌,    𝒌 = ρ·(Δ + 2σ)

𝑨 is the stream of identifiers allocated by every node of the cluster, indexed by the real time of allocation. That is the textbook k-sorted sequence. The familiar 𝑨[𝒊−𝒌] ≤ 𝑨[𝒊] ≤ 𝑨[𝒊+𝒌] is its 𝒋 − 𝒊 = 𝒌 case, and no identifier ever sits more than 𝒌 places from its sorted position. N nodes allocate with no lock, no sequencer, no NTP and no talk between them, and the stream still satisfies it.

The key order is total, exact and identical for every reader at every separation. 𝒌 bounds one thing only: how far that order may depart from wall-clock order.

population the cluster's whole allocation stream — every node, no coordination
observable A key order — bytes.Compare in the index you already have
observable B real allocation order — the index 𝒊
relation ≤ at distance 𝒌 — the two agree beyond 𝒌 places
tolerance 0 beyond 𝒌 — the bound is proven and tight, not typical
window 𝑾 = Δ + 2σ of wall clock; in entries, 𝒌 = ρ·𝑾

So: widen a range scan by 𝑾 and it cannot miss a row; buffer 𝒌 entries and the stream is fully sorted; restrict 𝑨 to one node and key order is allocation order, exactly, at any rate and under any clock.

Choose Δ by your failover interval, not by a wish for a small 𝒌. Since 𝑾 = Δ + 2σ, where σ is tens of seconds — hardware with no RTC, VMs resuming from a snapshot, phones back from airplane mode — a smaller Δ barely moves 𝑾, and it gives up what Δ is for: inside one Δ bucket each node's identifiers form a single contiguous block, so two writers that overlapped through a hand-over stay separable by a range scan. guid.DriftOf(d) picks the rung. Proven in doc/proof.md, machine-checked in doc/proof.lean, read first in doc/about.md.

Key features

This library aims important objectives:

  • The allocator's location is part of the sort order. The location outranks the fine fraction of time, so every node's identifiers occupy a contiguous, individually ordered run of the key space. The topology is readable from the keys themselves.
  • IDs allocation does not require centralized authority, coordination between nodes, or a synchronized clock.
  • IDs are suitable for partial event ordering in distributed environment and helps on detection of causality violation.
  • IDs are roughly sortable by allocation order ("time").
  • IDs reduce indexes footprints and optimize lookup latency.

Inspiration

The event ordering in distributed computing is resolved using various techniques, e.g. Lamport timestamps, Universal Unique Identifiers, Twitter Snowflake and many other techniques are offered by open source libraries. guid is a Golang port of Erlang's uid library.

All these solution made a common conclusion, globally unique ID is a triple ⟨𝒕, 𝒍, 𝒔⟩: ⟨𝒕⟩ monotonically increasing clock or timestamp is a primary dimension to roughly sort events, ⟨𝒍⟩ is spatially unique identifier of ID allocator so called node location, ⟨𝒔⟩ sequence is a monotonic integer, which prevents clock collisions. The guid library addresses few issues observed in other solutions.

Every byte counts when application is processing or storing large volume of events. This library implements fixed size 96-bit identity schema, which is castable to 64-bit under certain occasion. It is about 25% improvement to compare with UUID or similar 128-bit identity schemas (only Twitters Snowflake is 64-bit). The same schema is also offered at 128 bits as an RFC 9562 UUIDv8, guid.X, for deployments where interoperability outweighs the footprint.

Most of identity schemas uses monotonically increasing clock (timestamp) to roughly order events. The resolution of clock varies from nanoseconds to milliseconds. We found that usage of timestamp is not perfectly aligned with the goal of decentralized ID allocations. Usage of time synchronization protocol becomes necessary at distributed systems. Strictly speaking, NTP server becomes an authority to coordinate clock synchronization. This happens because schemas uses time fraction ⟨𝒕⟩ as a primary sorting key. In contrast with other libraries, guid do not give priority to single fraction of identity triple ⟨𝒕⟩ or ⟨𝒍⟩. It uses dynamic schema where the location fraction has higher priority than time only at particular precision.

This is what the library exists for. Inside one drift window the key space is partitioned by allocator: every node's identifiers form a contiguous run, and each run is exactly ordered — never interleaved with another node's. Consider a ring topology with leader-follower hand-over. A leader fails silently; for some interval two nodes believe they own the same range. Under a timestamp-primary schema their writes interleave, and recovering who wrote what means carrying the node identity somewhere else and filtering. Here the two nodes land in separate ranges: you scan a node's contribution directly, bound the overlap and reconcile, because the key space itself records the topology.

Neither Snowflake nor UUIDv7 can express this. Snowflake carries a machine id but places it below the whole timestamp, so grouping by node survives only within one millisecond. UUIDv7 has no location fraction at all — after the 48-bit millisecond it is entropy. The property is not a matter of tuning; the field has to be positioned to say it.

Identity Schema

A fixed size of 96-bit is used to implement identity schema

  3bit  47 bit - 𝒅 bit         32 bit      𝒅 bit  14 bit
   |-|-------------------|----------------|-----|-------|
   ⟨𝒅⟩        ⟨𝒕⟩                ⟨𝒍⟩         ⟨𝒕⟩     ⟨𝒔⟩

↣ ⟨𝒕⟩ is 47-bit UTC timestamp with a resolution of 131 µs — one tick is 2¹⁷ ns. It is derived from the nanosecond UNIX timestamp by shifting it right by 17 bits (time.Now().UnixNano() >> 17). The field spans 2⁴⁷ ticks of 2¹⁷ ns — 2⁶⁴ ns, about 584 years — so measured from the UNIX epoch it runs to the year 2555. The effective ceiling is earlier and comes from Go rather than from the schema: UnixNano is undefined beyond 2262, so ⟨𝒕⟩ never uses more than 46 of its 47 bits. A deployment that needs a different time base supplies its own ticker with guid.NewClock(guid.Clock, guid.WithClock(...)) (or seed from guid.Unclock for a descending one), which also gives that clock a private ⟨𝒕,𝒔⟩ sequence.

↣ ⟨𝒍⟩ is 32-bits node/allocator identifier. It is allocated randomly to each node using cryptographic random generator or application provided value. The node identity has higher sorting priority than the low bits of the timestamp, which is what makes each allocator's output a contiguous, exactly ordered run of the key space. The random allocation give an application ability to introduce about 65K allocators before it meets a high probability of collisions.

If ⟨𝒍⟩ is meant to carry topology, assign it rather than randomize it. guid.Clock/guid.Unclock already carry CONFIG_GUID_NODE_ID when a deployment sets it, a random ⟨𝒍⟩ otherwise — distinct allocators either way, but neither one follows topology: a random identity sorts arbitrarily, and an env-provided one is typically fixed per process rather than derived from ring position. Derive ⟨𝒍⟩ from the ring position with guid.NewClock(guid.Clock, guid.WithNodeID(...)) when you want the sort order to follow the topology.

↣ ⟨𝒅⟩ is 3 drift bits defines the width Δ of the window inside which ⟨𝒍⟩ outranks time. It shows the value of less important faction of time. The code selects a rung of an eight step ladder that runs from 131 µs to 39 hours, configured on the clock with guid.WithDrift(...) and defaulting to about 4.5 minutes.

Read Δ as a failover budget, not as a clock-skew budget. It has to cover the interval between a silent failure and the moment the cluster has converged on a new owner — because that is the interval during which two allocators write to the same range and you need their output kept apart:

constant Δ covers
guid.Drift131us 131 µs ordering only, no attribution — ⟨𝒙ₗ⟩ vanishes and the field order is Snowflake's
guid.Drift2s 2.15 s a consensus election plus lease expiry — Raft or etcd in one datacenter
guid.Drift17s 17.2 s gossip convergence, ZooKeeper and Consul sessions, fast failure detectors
guid.Drift68s 68.7 s Kubernetes node-NotReady plus reschedule, Kafka session timeout, health-check chains
guid.Drift275s (default) 274.9 s automated cross-AZ hand-over, phi-accrual detection, unmanaged clocks
guid.Drift1099s 1099 s slow membership convergence, paging, cross-region hand-over
guid.Drift4398s 4398 s human-in-the-loop failover
guid.Drift39h 39.1 h a split brain found the next morning, a fleet that syncs once a day, a region isolated a day

Only one rung sits below a second, and that is deliberate. The window is Δ + 2ε, so two rungs are distinguishable only where the wider Δ is large against 2ε — subdividing the sub-second range produces rungs that differ in name and not in 𝑾, since below a second it is the quality of your clocks, not the setting, that decides the ordering. The floor is kept because it is a useful extreme: at Δ = 131 µs the field order is exactly Snowflake's and the window is 2ε, the tightest any coordination-free schema reaches — but a run is one tick wide there, so it buys ordering and no attribution.

At the other end, Δ = 39.1 h is where the window stops being a failover budget: everything a deployment allocates falls into one epoch, so the partition by ⟨𝒍⟩ discriminates nothing while 𝒌 = ρ·𝑾 grows without return. A time range narrower than Δ also costs one seek per ⟨𝒍⟩ rather than one contiguous range, and only an assigned ⟨𝒍⟩ can be enumerated to make those seeks.

The same number is also the clock disagreement the ordering tolerates, which is why one knob serves both: two nodes whose clocks differ by less than Δ still sort into the same window. That matters because the target is not a managed cluster with datacenter NTP. On uncoordinated nodes — hardware without an RTC, devices behind firewalls that block NTP, VMs resuming from a snapshot, phones returning from airplane mode — tens of seconds of disagreement is the distribution, not a pathology. A timestamp-primary schema answers this by making an NTP server the coordinating authority, which is the coordination the library set out to avoid.

The drift must be the same for every value of a keyspace — ⟨𝒅⟩ is the most significant faction, so values allocated with different drift are segregated rather than interleaved. This is why it is a property of the clock and not an argument of NewG / NewL.

clock := guid.NewClock(guid.Clock, guid.WithDrift(guid.Drift17s))

// guid.DriftOf picks the smallest rung that covers a failover budget
clock := guid.NewClock(guid.Clock, guid.WithDrift(guid.DriftOf(45 * time.Second)))

↣ ⟨𝒔⟩ is 14-bit of monotonic strictly locally ordered integer. It helps to avoid collisions when multiple events happen during a single tick of ⟨𝒕⟩ — 131 µs — or when the clock is set backwards. The 14-bit value allows about 16K allocations per tick, a ceiling of 1.25·10⁸ per second per process. Read that as the saturation point rather than as a throughput figure: it is about the cost of the atomic increment itself, so a process cannot approach it while doing anything with the identifiers it allocates, and crossing it produces run-ahead rather than collisions — ⟨𝒕⟩ advances past the wall clock and the gap closes on its own once the burst ends. §3.6 of the proof has the rates.

The sequence is process-wide, not per-allocator: guid.Clock and guid.Unclock each bind to one, so values allocated across several instances of Chronos derived from either stay unique and each stays exactly ordered (WithClock is the exception — a custom ticker gets a private sequence, and so do WithSeed/WithCheckpoint, below). It is not unique between processes and is not what makes identifiers globally unique: two processes allocating in the same tick produce the same ⟨𝒕,𝒔⟩, and it is ⟨𝒍⟩ that keeps their identifiers apart. Within one process the implementation ensures that the same integer is not returned more than once.

Restart of the process resets the sequence to zero, which is safe on its own but stops mattering only as long as the wall clock keeps moving forward: a restart that coincides with the clock reading behind where the previous process left off. NTP step correction can make the new process hand out values that sort before ones the old process already issued. guid.WithCheckpoint(...) reports the sequence's high water mark to a channel the application persists on its own schedule (a file, a KV store, a row of whatever the identifiers are written into); guid.WithSeed(...) restores it on the next start:

hardened := guid.NewClock(guid.Clock, guid.WithSeed(restored), guid.WithCheckpoint(2*time.Second, ch))

Both give the result its own private sequence rather than reaching back into the one guid.Clock/guid.Unclock share, so deriving a hardened clock this way never changes how any other clock built from the same seed behaves. Pairing a stable ⟨𝒍⟩ (WithNodeID/WithNodeFromEnv, not WithNodeRandom) with a large enough Drift and, at the OS level, an NTP daemon configured to slew rather than step the clock, reduces how often this matters in the first place.

⟨𝒕⟩ and ⟨𝒔⟩ are allocated together, as a single atomic step, so that the pair ⟨𝒕,𝒔⟩ strictly increases with every allocation. ⟨𝒔⟩ counts within one tick of ⟨𝒕⟩ and restarts when the clock ticks; an allocator that exhausts a tick carries into the next one rather than folding ⟨𝒔⟩ back to zero. This makes values allocated by a single process ordered exactly as they were allocated — at any allocation rate, and even across a clock that is stepped backwards, where ⟨𝒕⟩ holds its high water mark until real time catches up. A process that saturates the allocator — a loop that allocates and discards, nothing else — makes ⟨𝒕⟩ run ahead of the wall clock; the ordering is unaffected and the gap closes on its own once the loop stops. §3.6 of the proof derives the rates, for readers who need Time to track real time under synthetic load.

The ordering guarantees are stated and proven in doc/proof.md; statement (2) is machine-checked in doc/proof.lean.

The library supports casting of 96-bit identifier to 64-bit by dropping ⟨𝒍⟩ fraction. This optimization reduces a storage footprint if application uses persistent allocators.

  3bit        47 bit            14 bit
   |-|------------------------|-------|
   ⟨𝒅⟩           ⟨𝒕⟩              ⟨𝒔⟩

The same schema is also defined at 128 bits, where ⟨𝒍⟩ is 58 bits wide and the 6 bits RFC 9562 reserves for the version and the variant make the value a UUID, see guid.X.

  3bit  47 bit - 𝒅 bit             58 bit          𝒅 bit  14 bit
   |-|-------------------|--------------------------|-----|-------|
   ⟨𝒅⟩        ⟨𝒕⟩                    ⟨𝒍⟩               ⟨𝒕⟩     ⟨𝒔⟩

Types

The library defines three types, each occupying exactly the bits its schema needs, so that an application storing millions of identifiers pays for nothing it does not use.

type schema size ⟨𝒍⟩ alignment allocator
guid.X ⟨𝒅,𝒕,𝒍,𝒔⟩ 16 bytes 58 bit 1 guid.NewX(clock)
guid.G ⟨𝒅,𝒕,𝒍,𝒔⟩ 12 bytes 32 bit 1 guid.NewG(clock)
guid.L ⟨𝒅,𝒕,𝒔⟩ 8 bytes — 8 guid.NewL(clock)

All three carry the same fractions in the same order, and share the same drift ladder, clock and sequencer. They differ only in how much room is left for the node identity, which is also what separates their use cases.

guid.G holds the big-endian representation of the 96-bit number the schema defines, and nothing else. The representation is the one the schema is defined in, so memory I/O costs nothing:

  • a []guid.G packs without padding, 12 bytes per value;
  • the wire format is the value itself — g[:] is a valid encoding and copy(g[:], buf) a valid decoding, neither shifts a single bit;
  • the byte order is the order of the identifiers, so bytes.Compare over the raw bytes agrees with g.Before. An index that sorts the stored bytes — a B-tree, a sorted file, a key-value store — orders the identifiers correctly without decoding them.

guid.L is the 64-bit number itself, one machine word: passed in registers, compared with a single instruction, stored in 8 bytes.

guid.X is the same schema at 128 bits, and it spends the extra 4 bytes on standards compliance rather than on the clock. Six of the 128 bits are the version and variant fields RFC 9562 fixes, which leaves 122 for the schema and widens ⟨𝒍⟩ to 58 bits — so an X is a UUID of version 8, not "UUID-shaped":

  • it drops into every uuid column in PostgreSQL, MySQL and SQL Server, every UUID library in every language, every debugger and log viewer — rendering correctly rather than as a malformed v7;
  • x.String() emits the canonical xxxxxxxx-xxxx-8xxx-yxxx-xxxxxxxxxxxx form rather than the private alphabet G and L use, because the whole point is that other systems recognise it. x.Base62() remains available as the compact representation;
  • it is readable by non-Go systems without porting anything — which matters for a schema whose premise is allocation across uncoordinated nodes, since a cluster of uncoordinated nodes is rarely a cluster of uniform Go processes.

The reserved bits cost 6 bits of payload and nothing else. They are constants of the format, so at each of those positions two values are identical and a most-significant-first comparison falls through to the next one: lexicographic order over the 128 bits is exactly lexicographic order over the variable payload, in field order. bytes.Compare still agrees with x.Before.

The three are distinct types, which is deliberate — values of different width are not comparable, and the compiler now says so. Values of two different types must never share a keyspace either: they are different widths with different field semantics and no ordering relation between them is defined. Convert explicitly at the boundary.

Decoding and casting

Only allocation is a package function. Everything that turns data you already hold into a value is a method on the destination, so the type you are building is the receiver and the compiler picks the decoder:

var uid guid.X
err := uid.FromString("06377f2a-0cb8-8a3f-b000-0000000003e9")

Every accessor has its inverse on the same type:

encode decode
uid.Bytes() uid.FromBytes(b)
uid.String() uid.FromString(s)
uid.Base62() uid.FromBase62(s)
uid.Split(n) uid.Fold(n, b)
uid.Epoch() uid.FromTime(clock, t)

Casts read in the direction of the assignment:

g.FromL(clock, l)   // 64-bit  -> 96-bit,  stamps the ⟨𝒍⟩ fraction
g.FromX(x)          // 128-bit -> 96-bit,  truncates ⟨𝒍⟩ to 32 bits
l.FromG(g)          // drops ⟨𝒍⟩
l.FromX(x)          // drops ⟨𝒍⟩
x.FromG(g)          // 96-bit  -> 128-bit, ⟨𝒍⟩ keeps the 32 bits it had
x.FromL(clock, l)   // 64-bit  -> 128-bit, stamps the ⟨𝒍⟩ fraction

A decoder that returns an error leaves the destination unchanged, so a value already there survives a failed decode rather than being half overwritten. The receiver has to be addressable — a variable, a struct field and a slice element are; a map element or a function result is not, and needs a temporary.

All three types implement encoding.TextMarshaler, TextUnmarshaler, BinaryMarshaler and BinaryUnmarshaler, so they travel through gob, yaml, toml or any other codec that speaks the stdlib interfaces without that codec knowing this package exists.

Which one to use

Reach for guid.L when you need a sortable key in a database. It is 8 bytes — half of a UUID, a third smaller than guid.G, and the same width as a BIGINT — and it is strictly ordered rather than k-ordered: values are returned in exactly the order they were allocated, at any rate, and across a clock that NTP steps backwards. There is no drift window to reason about because there is no ⟨𝒍⟩ fraction for time to rank against. For surrogate keys, event ids and sequence numbers this is the better instrument, and the cheaper one.

Its limit is in the name: a local value is unique within the allocator that issued it. Use it where the surrounding context already disambiguates — a per-tenant or per-partition key space, a single writer, or a row that already carries the node — and use guid.G where it does not.

Reach for guid.G when identifiers are allocated by many uncoordinated nodes and you want the topology in the key: a contiguous, exactly ordered run per allocator, so that overlapping writers can be told apart and reconciled. That is what the extra 4 bytes buy. Its ⟨𝒍⟩ is 32 bits, so randomly allocated node identities meet a birthday bound at about 65 000 allocators but using assignments widen it up to 2³².

Reach for guid.X when the identifiers leave Go, or when there are more allocators than 32 bits of ⟨𝒍⟩ can keep apart. Its 58-bit ⟨𝒍⟩ moves the birthday bound to about 5.4·10⁸, which takes node collision out of the set of things an operator has to think about — and uniqueness, not ordering, is this library's real exposure: the ordering is machine-checked, the node distinctness is assumed. Against UUIDv7, which it costs exactly as much to store, it adds strict ordering within a millisecond, topology in the key, 131 µs time resolution, exact intra-node sequencing and a proof. Against UUIDv7 it also asks for two things UUIDv7 never asks for — a drift held constant across the cluster and across the lifetime of the data, and node identities that stay distinct. Both are easy on day one and are the shape of a year-three incident; if a sortable primary key is all you need, UUIDv7's zero configuration and unconditional uniqueness are the better trade.

situation type
sortable key, one allocator or a disambiguating context guid.L — 8 B
many uncoordinated allocators, storage footprint matters guid.G — 12 B
many uncoordinated allocators, interop or node count matters guid.X — 16 B, a UUID
x := guid.NewX(guid.Clock)   // 128-bit, globally unique, an RFC 9562 UUIDv8
g := guid.NewG(guid.Clock)   // 96-bit, globally unique
l := guid.NewL(guid.Clock)   // 64-bit, unique within this allocator

g.Time()  g.Node()  g.Seq()  g.Epoch()
g.Before(other)  g.After(other)  g.Equal(other)
g.String()  g.Base62()  g.Bytes()

x.String()                   // "0198c4f1-a35c-8b7e-b2a0-91d5e0c00001"
err := x.FromString(s)       // the decoder is a method on what it builds

Comparing on a ring

Before ranks ⟨𝒍⟩ with <, whose least element is 0. A consistent hashing ring has no least element — it has one order per cut point, and the one a key 𝒌 means is a <𝒌 b ⟺ (a − 𝒌) mod 2ᴺ < (b − 𝒌) mod 2ᴺ, a strict total order for every fixed 𝒌. Before is the member of that family cut at the origin, so on a ring it answers for 𝒌 = 0 whatever key was asked about: it agrees with the successor list only where that list does not wrap the origin, and misfires on (N−1)/M of the key space for M addresses and replication factor N — two thirds of it with three nodes.

OrdRingG and OrdRingX are that order, cut where you ask:

ord := guid.OrdRingG(key >> 32)   // the order cut at this key
slices.SortFunc(uids, ord.Compare)   // uids[0] belongs to the primary for key
ord.Before(a, b)                     // and the pairwise form

The primary for 𝒌 is by construction the least element of <𝒌, at every key and for any placement of tokens, so the misfire is zero rather than small. OrdRingG(0) — the zero value — is exactly Before.

It costs what Before does not. Before is two word comparisons, and the byte order of a stored value is that order, so an external index sorts correctly without decoding; ring order has to read ⟨𝒍⟩ out of the middle of the value — at the default rung it straddles the word boundary of a G — rotate it, and compare it apart from the fields around it, which no index can do, and which cannot be folded into storage because 𝒌 varies per query. It is meant for conflict resolution over the few values contending for one key, not for the index path: scanning does not need it, since a node's run stays contiguous inside an epoch under Before already and rotation permutes runs without splitting them. See doc/vnode.md.

Migrating from v2

v3 is a compatibility break — new types, a re-based drift ladder, and a guid.G decoded with plain FromString/FromBase62 will silently misread ⟨𝒍⟩ and ⟨𝒕⟩ for a v2 value. Use guid.FromV2(isBase62, s) instead. The full API mapping and the reasoning behind each behavioural change are in CHANGELOG.md.

Getting started

The latest version of the library is available at main branch. All development, including new features and bug fixes, take place on the main branch using forking and pull requests as described in contribution guidelines. The stable version is available via Golang modules.

Use go get to retrieve the library and add it as dependency to your application.

go get github.com/fogfish/guid/v3

Here is minimal example:

package main

import (
  "fmt"
  "time"

  "github.com/fogfish/guid/v3"
)

func useDefaultClock() {
  a := guid.NewG(guid.Clock)
  time.Sleep(1 * time.Second)
  b := guid.NewG(guid.Clock)
  fmt.Printf("%s < %s is %v\n", a, b, a.Before(b))
}

func useCustomClock() {
  clock := guid.NewClock(guid.Clock, guid.WithNodeID(0xffffffff))

  c := guid.NewG(clock)
  time.Sleep(1 * time.Second)
  d := guid.NewG(clock)
  fmt.Printf("%s < %s is %v\n", c, d, c.Before(d))
}

func main() {
  useDefaultClock()
  useCustomClock()
}

The library api specification is available via Go doc.

The example command

examples/guid is a runnable generator — it allocates identifiers of any of the three types and writes them to stdout, one per line.

go run ./examples/guid -x -n 42 -t 5ms -c 20
flag
-l -g -x which type to allocate; -g by default, at most one
-n node identity ⟨𝒍⟩, random when not given
-t sleep a random interval in (0, t] between allocations
-c how many to allocate, 0 for no limit

Only the identifiers go to stdout, so the output pipes. Run two instances side by side with different -n to see the property the schema exists for — each allocator's output is a contiguous, individually ordered run of the key space:

go run ./examples/guid -x -c 1000 2>/dev/null | sort -c && echo "allocated in sort order"

How To Contribute

The library is Apache 2.0 licensed and accepts contributions via GitHub pull requests:

  1. Fork it
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -am 'Added some feature')
  4. Push to the branch (git push origin my-new-feature)
  5. Create new Pull Request

The build and testing process requires Go version 1.13 or later.

Build and run in your development console.

git clone https://github.com/fogfish/guid
cd guid
go test

License

See LICENSE

References

  1. Lamport timestamps
  2. Universal Unique Identifiers,
  3. Twitter Snowflake
  4. Flake
  5. K-sorted sequence

Documentation

Overview

Package guid implements interface to generate k-ordered unique identifiers in lock-free and decentralized manner for Golang applications. We says that sequence A is k-ordered if it consists of strictly ordered subsequences of length k:

𝑨[𝒊 − 𝒌] ≤ 𝑨[𝒊] ≤ 𝑨[𝒊 + 𝒌] for all 𝒊 such that 𝒌 < 𝒊 ≤ 𝒏−𝒌.

Key features

This library aims important objectives:

↣ IDs allocation does not require centralized authority or coordination with other nodes.

↣ IDs are suitable for partial event ordering in distributed environment and helps on detection of causality violation.

↣ IDs are roughly sortable by allocation order ("time").

↣ IDs reduce indexes footprints and optimize lookup latency.

Inspiration

The event ordering in distributed computing is resolved using various techniques, e.g. Lamport timestamps (https://en.wikipedia.org/wiki/Lamport_timestamps), Universal Unique Identifiers (https://tools.ietf.org/html/rfc4122), Twitter Snowflake (https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake.html) and many other techniques are offered by open source libraries. `guid` is a Golang port of https://github.com/fogfish/uid.

All these solution made a common conclusion, globally unique ID is a triple ⟨𝒕, 𝒍, 𝒔⟩:

↣ ⟨𝒕⟩ monotonically increasing clock or timestamp is a primary dimension to roughly sort events,

↣ ⟨𝒍⟩ is spatially unique identifier of ID allocator so called node location,

↣ ⟨𝒔⟩ sequence is a monotonic integer, which prevents clock collisions. The value is global for the node

The `guid` library addresses few issues observed in other solutions.

Every byte counts when application is processing or storing large volume of events. This library implements fixed size 96-bit identity schema, which is castable to 64-bit under certain occasion. It is about 25% improvement to compare with UUID or similar 128-bit identity schemas. Twitters Snowflake is also 64-bit. The same schema is also offered at 128 bits, as an RFC 9562 UUIDv8, for deployments where interoperability outweighs the footprint.

Most of identity schemas uses monotonically increasing clock (timestamp) to roughly order events. The resolution of clock varies from nanoseconds to milliseconds. We found that usage of timestamp is not perfectly aligned with the goal of decentralized ID allocations. Usage of time synchronization protocol becomes necessary at distributed systems. Strictly speaking, NTP server becomes an authority to coordinate clock synchronization. This happens because schemas uses time fraction ⟨𝒕⟩ as a primary sorting key. In contrast with other libraries, `guid` do not give priority to single ⟨𝒕⟩ or ⟨𝒍⟩ fraction of identity triple. It uses dynamic schema where the location fraction has higher priority than time only at particular precision. It allows to keep ordering consistent even if clocks on other node is skewed.

Identity Schema

A fixed size of 96-bit is used to implement identity schema

3bit  47 bit - 𝒅 bit         32 bit      𝒅 bit  14 bit
 |-|-------------------|----------------|-----|-------|
 ⟨𝒅⟩        ⟨𝒕⟩                ⟨𝒍⟩         ⟨𝒕⟩     ⟨𝒔⟩

↣ ⟨𝒕⟩ is 47-bit UTC timestamp with millisecond precision. It is derived from nanosecond UNIX timesamp by shifting it by 17 bits (time.Now().UnixNano() >> 17). The library is able to change the base timestamp to any value in-order to address Year 2038 problem.

↣ ⟨𝒍⟩ is 32-bits node/spacial identifier. It is allocated randomly to each node using cryptographic random generator or application provided value. The node identity has higher sorting priority than the low bits of the timestamp, which is what makes each allocator's output a contiguous, exactly ordered run of the key space. If ⟨𝒍⟩ is meant to carry topology, assign it with WithNodeID rather than leaving the random default: random identities sort arbitrarily, so adjacent ring positions land far apart. The random allocation give an application ability to introduce about 65K allocators before it meets a high probability of collisions.

↣ ⟨𝒅⟩ is 3 drift bits defines the width of the window inside which ⟨𝒍⟩ outranks time. Read it as a failover budget rather than as a clock-skew budget: it has to cover the interval between a silent failure and the moment the cluster has converged on a new owner, because that is the interval during which two allocators write to the same range. The same number is also the clock disagreement the ordering tolerates, which is why one knob serves both — and on uncoordinated nodes, hardware without an RTC or devices behind firewalls that block NTP, tens of seconds of disagreement is the distribution rather than a pathology. It shows the value of less important faction of time. The code selects a rung of an eight step ladder, Drift131us to Drift39h, which runs from 131 µs to 39 hours, configured on the clock with WithDrift and defaulting to Drift275s, about 4.5 minutes. Use DriftOf to pick the smallest rung that covers a budget expressed as a duration. The drift must be the same for every value of a keyspace: ⟨𝒅⟩ is the most significant faction, so values allocated with different drift are segregated rather than interleaved. This is why it is a property of Chronos and not an argument of NewG and NewL.

↣ ⟨𝒔⟩ is 14-bit of monotonic strictly locally ordered integer. It helps to avoid collisions when multiple events happens during single millisecond or when the clock set backwards. The 14-bit value allows to have about 16K allocations per tick of ⟨𝒕⟩ and over 100M per second on single node. Each instance of application process runs a unique sequence of integers. The implementation ensures that the same integer is not returned more than once on the current process. Restart of the process resets the sequence.

⟨𝒕⟩ and ⟨𝒔⟩ are allocated together, as a single atomic step, so that the pair strictly increases with every allocation. ⟨𝒔⟩ counts within one tick of ⟨𝒕⟩ and restarts when the clock ticks; an allocator that exhausts a tick carries into the next one rather than folding ⟨𝒔⟩ back to zero. Two consequences are worth knowing:

↣ Values allocated by one process are ordered exactly as they were allocated, whatever the allocation rate and even if the clock is stepped backwards, in which case ⟨𝒕⟩ holds its high water mark until real time catches up.

↣ A process that saturates the allocator, a loop that allocates and discards and does nothing else, makes ⟨𝒕⟩ run ahead of the wall clock. The ordering is unaffected and the gap closes on its own once the loop stops. See §3.6 of doc/proof.md for the rates.

The library supports casting of 96-bit identifier to 64-bit by dropping ⟨𝒍⟩ fraction. This optimization reduces a storage footprint if application uses persistent allocators.

3bit        47 bit            14 bit
 |-|------------------------|-------|
 ⟨𝒅⟩           ⟨𝒕⟩              ⟨𝒔⟩

The same schema is also defined at 128 bits, where ⟨𝒍⟩ is 58 bits wide and the 6 bits RFC 9562 reserves make the value a UUID of version 8, see guid.X.

3bit  47 bit - 𝒅 bit             58 bit          𝒅 bit  14 bit
 |-|-------------------|--------------------------|-----|-------|
 ⟨𝒅⟩        ⟨𝒕⟩                    ⟨𝒍⟩               ⟨𝒕⟩     ⟨𝒔⟩

Types

The library defines three types, each occupying exactly the bits its schema needs, so that an application storing millions of identifiers pays for nothing it does not use:

guid.X  128-bit globally unique value, 16 bytes, allocated by NewX
guid.G   96-bit globally unique value, 12 bytes, allocated by NewG
guid.L   64-bit locally unique value,   8 bytes, allocated by NewL

x := guid.NewX(guid.Clock)
g := guid.NewG(guid.Clock)
l := guid.NewL(guid.Clock)

All three carry the same fractions in the same order and share the same drift ladder, clock and sequencer. They differ only in how much room is left for the node: none for L, 32 bits for G, 58 bits for X.

G holds the big-endian representation of the 96-bit number the schema defines, and nothing else. The type is therefore 12 bytes wide with single byte alignment, so a []G packs without padding; the wire format is the value itself, g[:] is a valid encoding and copy(g[:], buf) a valid decoding; and the byte order is the order of the identifiers, so bytes.Compare over the raw bytes and g.Before agree. An index that sorts the stored bytes orders the identifiers correctly without decoding them.

L is the 64-bit number itself, one machine word, passed in registers and compared with a single instruction.

X is the 128-bit case, and it spends its extra 4 bytes on being an RFC 9562 UUID of version 8 rather than on the clock. Six of the 128 bits are the version and variant fields the RFC fixes, which leaves 122 for the schema and widens ⟨𝒍⟩ to 58 bits. The result renders, parses and stores as a UUID everywhere a UUID does — a uuid column, a log viewer, a UUID library in another language — instead of showing up as a malformed v7. The reserved bits are constants of the format and therefore transparent to comparison, so the byte order is still the order of the identifiers.

The types are distinct, which is deliberate: values of different width are not comparable, and the compiler now says so. Values of two different types must never share a keyspace either — they are different widths with different field semantics, and no ordering relation between them is defined.

Decoding and casting

Only allocation is a package function. Everything that turns data you already hold into a value is a method on the destination, so the type you are building is the receiver and the compiler picks the decoder:

var uid guid.X
err := uid.FromString("06377f2a-0cb8-8a3f-b000-0000000003e9")

uid.FromBytes(b)     // inverse of Bytes
uid.FromString(s)    // inverse of String
uid.FromBase62(s)    // inverse of Base62
uid.Fold(n, b)       // inverse of Split
uid.FromTime(clock, t)

This is the one place the schema's cardinal rule can be broken by a typo — a value of the wrong type decoded into a keyspace is unrecoverable — so it is not left to a suffix on a function name that the reader has to notice. There is no FromStringG to write instead of FromStringX; g.FromString reads a G because g is a G.

Casts work the same way and read in the direction of the assignment:

g.FromL(clock, l)   // 64-bit  -> 96-bit,  stamps the ⟨𝒍⟩ fraction
err := g.FromX(x)   // 128-bit -> 96-bit,  truncates ⟨𝒍⟩ to 32 bits
l.FromG(g)          // drops ⟨𝒍⟩
l.FromX(x)          // drops ⟨𝒍⟩
x.FromG(g)          // 96-bit  -> 128-bit, ⟨𝒍⟩ keeps the 32 bits it had
x.FromL(clock, l)   // 64-bit  -> 128-bit, stamps the ⟨𝒍⟩ fraction

All six preserve the ⟨𝒕,𝒔⟩ fraction exactly. FromX is the one that can fail: a node identity wider than 32 bits has no G to land on, so the cast returns an error rather than silently colliding two nodes onto the same value.

A decoder that returns an error leaves the destination unchanged, so a value that was already there survives a failed decode rather than being half overwritten. The receiver has to be addressable, which a variable, a struct field and a slice element are, and a map element or a function result is not — those need a temporary.

All three types also implement encoding.TextMarshaler, TextUnmarshaler, BinaryMarshaler and BinaryUnmarshaler, so they travel through gob, yaml, toml, a struct tag or any other codec that speaks the stdlib interfaces without that codec knowing this package exists. UnmarshalText is FromString and UnmarshalBinary is FromBytes, under the names the stdlib expects.

Which one to use

Reach for guid.L when you need a sortable key in a database. It is 8 bytes, half of a UUID, a third smaller than guid.G and the same width as a BIGINT, and it is strictly ordered rather than k-ordered: values are returned in exactly the order they were allocated, at any rate, and across a clock that NTP steps backwards. There is no drift window to reason about because there is no ⟨𝒍⟩ fraction for time to rank against. For surrogate keys, event ids and sequence numbers it is the better instrument and the cheaper one.

Its limit is in the name: a local value is unique within the allocator that issued it. Use it where the surrounding context already disambiguates, a per-tenant or per-partition key space, a single writer, or a row that already carries the node, and use guid.G where it does not.

Reach for guid.G when identifiers are allocated by many uncoordinated nodes and the topology belongs in the key: a contiguous, exactly ordered run per allocator, so that overlapping writers can be told apart and reconciled. That is what the extra 4 bytes buy. Its ⟨𝒍⟩ is 32 bits, so randomly allocated node identities meet a birthday bound at about 65 000 allocators.

Reach for guid.X when the identifiers leave Go, or when there are more allocators than 32 bits of ⟨𝒍⟩ can keep apart. It is a real UUID, so other systems read it without porting anything — which matters for a schema whose premise is uncoordinated allocation, since a cluster of uncoordinated nodes is rarely a cluster of uniform Go processes — and its 58-bit ⟨𝒍⟩ moves the birthday bound to about 5.4·10⁸ allocators. At 16 bytes it costs the same as the UUIDv7 it replaces, and adds sub-millisecond ordering, topology in the key, exact intra-node sequencing and a machine-checked proof. It is not free of the library's own conditions: X asks for a drift held constant across the cluster and for node identities to stay distinct, where UUIDv7 asks nothing and is unconditionally unique. In one table:

sortable key, one allocator or a disambiguating context   guid.L    8 B
many uncoordinated allocators, footprint matters          guid.G   12 B
many uncoordinated allocators, interop or node count      guid.X   16 B

Applications

The schema has wide range of applications where globally unique id are required.

↣ object identity: use library to generate unique identifiers.

↣ replacement of auto increment types: out-of-the-box replacement for auto increment fields in databases.

↣ vector clock: defines a logical clock for each process.

↣ CRDTs: LWW Register, OR-set and others.

Index

Constants

View Source
const (
	// SizeX is the size of X in bytes, both in memory and on the wire
	SizeX = 16
	// SizeG is the size of G in bytes, both in memory and on the wire
	SizeG = 12
	// SizeL is the size of L in bytes on the wire
	SizeL = 8
	// SizeString is the length of the lexicographically sortable string
	// encoding produced by String, for both G and L
	SizeString = 16
	// SizeStringX is the length of the canonical UUID string produced by
	// X.String, e.g. "06377f2a-0cb8-8000-8000-000000000001"
	SizeStringX = 36
)

Variables

View Source
var (
	Clock   = newDefaultClock(unixtime, ForwardTime, seqAscending)
	Unclock = newDefaultClock(inversetime, InverseTime, seqDescending)
	Mock    = &Chronometer{order: ForwardTime, drift: driftDefault, mock: true}
)

Clock, Unclock and Mock are the process-wide instances of the logical clock every application starts from — most never need anything else.

  • Clock allocates from the ascending unix-time domain, ⟨𝒕⟩ = UnixNano.
  • Unclock allocates from the descending domain, ⟨𝒕⟩ = MaxUint64 − UnixNano, so that recently allocated values sort first.
  • Mock is deterministic, pinning every allocation to ⟨0,0⟩; it is for tests that assert on a fixed value and must not be used in production.

Clock and Unclock take their ⟨𝒍⟩ from defaultNode: CONFIG_GUID_NODE_ID when the deployment sets it, so every process that sets the same value gets the same stable node identity, and a random one otherwise. Mock's is ⟨0⟩.

All three are plain, already-resolved values — T reads a field, nothing more. An application that wants its own node identity, drift or ticker does not configure one of these in place; it derives a new Chrono from one with NewClock, see below.

Functions

This section is empty.

Types

type Chronometer added in v3.1.0

type Chronometer struct {
	// contains filtered or unexported fields
}

Chronometer is the concrete Chronos NewClock returns. Clock, Unclock and Mock are its three process-wide instances; an application names the type itself only when it needs to hold a configured clock in a variable or struct field before passing it on, or before deriving further from it.

A Chronometer is inert once built: nothing here is ever mutated after NewClock returns it, so T needs no synchronization of its own beyond whatever the sequence it draws from already provides.

func NewClock

func NewClock(seed *Chronometer, opts ...Config) *Chronometer

NewClock creates a clock for allocating k-ordered values from a seed clock. The seed is mandatory. Use the default Clock or Unclock — the two the library provides — but can be any Chronos.

c := guid.NewClock(guid.Clock, guid.WithNodeID(0xffffffff))
h := guid.NewClock(guid.Clock, guid.WithSeed(restored), guid.WithCheckpoint(2*time.Second, ch))

func (*Chronometer) Drift added in v3.1.0

func (c *Chronometer) Drift() Drift

func (*Chronometer) Node added in v3.1.0

func (c *Chronometer) Node() uint64

func (*Chronometer) Order added in v3.1.0

func (c *Chronometer) Order() TimeOrder

func (*Chronometer) T added in v3.1.0

func (c *Chronometer) T() (uint64, uint64)

T allocates the ⟨𝒕,𝒔⟩ fraction of a k-ordered value.

⟨𝒕⟩ and ⟨𝒔⟩ are allocated together, as one atomic step, so that the pair strictly increases with every call and values are ordered exactly as they are allocated. See sequence for why the two cannot be drawn independently.

type Chronos

type Chronos interface {
	// Spatially unique identifier ⟨𝒍⟩ of ID allocator so called node location
	//
	// The identity is carried at the 58 bits X gives it, the widest of the
	// types. G truncates it to its own 32 bits when it stamps a value, so a
	// clock serves both without being configured twice.
	Node() uint64

	// Allocates the coupled ⟨𝒕,𝒔⟩ fraction of a k-ordered value
	T() (uint64, uint64)

	// ⟨𝒅⟩ drift, the rung of the ladder the clock allocates with.
	//
	// The drift decides how much clock disagreement the k-ordering tolerates
	// and it must be the same for every value of a keyspace. It is a property
	// of the clock so that a process cannot vary it per allocation.
	Drift() Drift

	// ⟨𝒐⟩ direction of the time domain.
	//
	// Like the drift it must be the same for every value of a keyspace, and it
	// is a property of the clock so that a process cannot vary it per
	// allocation. It is needed to place a wall clock instant into the domain,
	// see L.FromTime and G.FromTime; reading ⟨𝒕⟩ back does not need it, see
	// Epoch.
	Order() TimeOrder
}

Chronos is an abstraction of logical clock used by library.

type Config

type Config func(*config)

Config is a functional option NewClock applies when deriving a Chrono from a seed. See WithDrift, WithNodeID, WithNodeRandom, WithNodeFromEnv, WithClock, WithSeed and WithCheckpoint.

func WithCheckpoint added in v3.1.0

func WithCheckpoint(interval time.Duration, out chan<- uint64) Config

WithCheckpoint arranges for the clock's ⟨𝒕,𝒔⟩ high-water mark to be sent to out on genuine forward progress of the sequence, throttled to at most once per interval. The application drains out at its own pace — its own goroutine, its own schedule — and persists whatever it last received: a file, a KV store, a row of the database the identifiers themselves land in. Feeding that value back through WithSeed on the next start is the other half of the pair.

The send is non-blocking: a consumer that is not ready simply misses that value. Nothing is lost by this that matters, since only the highest value the application ever sees is needed to seed a future restart — out should be buffered (a capacity of 1 is enough) so a slow-starting consumer does not miss the first checkpoint, but no amount of buffering changes the guarantee, which is "eventually delivers the latest", not "delivers every value".

Like WithSeed, WithCheckpoint always forces a private sequence, so what it reports is exactly the clock the caller configured, never a value folded in from every other clock sharing a time domain's default sequence. WithSeed and WithCheckpoint compose regardless of which is given first — NewClock reads every opt's effect back together after all of them have run, rather than resolving anything as each one is applied.

func WithClock

func WithClock(ticker func() uint64) Config

WithClock overrides the timestamp generator with a custom ticker, keeping the direction (and so the ascending/descending choice of next/prev) of whatever seed NewClock was given — guid.NewClock(guid.Clock, ...) stays ascending, guid.NewClock(guid.Unclock, ...) stays descending, and there is no separate "descending" option: seeding from Unclock already is one.

The generator should be non-decreasing: it defines the direction in which allocated values sort, and a wandering generator costs Epoch its accuracy, see below.

⟨𝒕,𝒔⟩ ordering itself does not depend on it. Every clock allocates through the same coupled sequence, which every call advances by one, unconditionally; a generator reading may raise the sequence but can never lower it, so values allocated from one Chronos strictly increase in the order they were allocated regardless of what the generator returns repeating, decreasing, or constant. What a non-monotonic generator costs is accuracy, not order.

The generator is assumed to yield unix nanoseconds. Epoch reads ⟨𝒕⟩ back on that assumption; a generator in any other unit allocates ordered values but does not report a meaningful wall clock time.

WithClock always gives the result its own private ⟨𝒕,𝒔⟩ sequence, since the library cannot know whether a custom generator shares a time domain with any other clock. Values allocated from two such clocks are therefore unique only if the clocks also carry distinct ⟨𝒍⟩ node identity.

func WithDrift

func WithDrift(drift Drift) Config

WithDrift configures ⟨𝒅⟩, the failover budget the k-ordering absorbs.

The ladder has eight rungs, from Drift131us to Drift39h, and defaults to Drift275s. A larger drift attributes a longer overlap, a smaller one yields a tighter k. Use DriftOf to select the rung that covers a budget expressed as a duration:

guid.NewClock(guid.Clock, guid.WithDrift(guid.Drift17s))
guid.NewClock(guid.Clock, guid.WithDrift(guid.DriftOf(45 * time.Second)))

Every clock of a keyspace must be configured with the same drift, otherwise values are ordered by their drift rather than by their time.

func WithNodeFromEnv

func WithNodeFromEnv() Config

WithNodeFromEnv configures ⟨𝒍⟩ spatially unique identifier using env variable.

CONFIG_GUID_NODE_ID - defines location id as a string

The identity is the leading bytes of the SHA-256 of the variable, taken to the 58 bits X gives ⟨𝒍⟩. The four bytes a G reads are kept at the bottom of the identity rather than at its top, so that the G a given variable names does not depend on how wide the clock's node field happens to be.

The variable must be set and defined, otherwise it panics. See defaultNode for the fallback Clock and Unclock use instead of panicking.

func WithNodeID

func WithNodeID(id uint64) Config

WithNodeID explicitly configures ⟨𝒍⟩ spatially unique identifier.

The identifier is truncated to 58 bits, the width X gives it. A value of G keeps only its low 32 bits, so an identity meant for both types has to fit the narrower one.

func WithNodeRandom

func WithNodeRandom() Config

WithNodeRandom configures ⟨𝒍⟩ spatially unique identifier using cryptographic random generator.

The identity is 58 random bits, which is what makes the allocator coordinator-free: the birthday bound is ≈ 5.4·10⁸ allocators for X. A G keeps only 32 of those bits and its bound is ≈ 6.5·10⁴ — the number to plan against if the keyspace is G rather than X.

Clock and Unclock already carry ⟨𝒍⟩ from defaultNode — CONFIG_GUID_NODE_ID when it is set, random otherwise; WithNodeRandom is for re-rolling a random one explicitly, overriding whichever of the two a derived value inherited.

func WithSeed added in v3.1.0

func WithSeed(v uint64) Config

WithSeed configures the sequence's initial ⟨𝒕,𝒔⟩ high-water mark instead of starting from zero, so a process resumes at or above where a previous one — persisted via WithCheckpoint — left off, rather than resetting to zero. That gap is what lets a restart coinciding with a backward clock step (an NTP correction) violate k-ordering: the in-process ratchet that already tolerates a backward-stepping ticker (see WithClock) does not survive the process that held it.

The value is opaque: it is whatever WithCheckpoint delivered, fed back unchanged, and it is only meaningful for a clock built with the same Drift and time domain as the one that produced it. A seed at or below the sequence's own first reading has no effect — T applies the same max(...) ratchet sequence.go already uses — so an absent, zero, or stale seed is always safe, merely non-optimal.

WithSeed always gives the result its own private sequence, never the process-wide one Clock/Unclock otherwise share: seeding is a deliberate, local override and must not silently move the floor every other clock of the shared default allocates from. This, like WithCheckpoint, is an option for an operator who has already decided to take on that responsibility — most applications never need either.

type Drift

type Drift uint64

Drift is ⟨𝒅⟩, the rung of the ladder that sets the width Δ of the window inside which ⟨𝒍⟩ location outranks ⟨𝒕⟩ time.

It is the one policy decision the schema asks for, and it is a failover budget: Δ has to cover the interval between a silent failure and the moment the cluster has converged on a new owner, because that is the interval during which two allocators write to the same range and their output has to stay apart. Two values allocated further apart than Δ + 2ε are always ordered by their time; inside that window they are ordered by their allocator, each allocator's values forming one contiguous run.

The same number is the clock disagreement the ordering tolerates, which is why one knob serves both. A larger Δ attributes a longer overlap, a smaller one yields a tighter k.

The type is the 3-bit code the value carries, not the window itself, so the ladder has exactly eight rungs, see the constants below. Read the window of a rung with Window, pick a rung for a tolerance with DriftOf.

The drift must be the same for every value of a keyspace: ⟨𝒅⟩ is the most significant fraction, so values allocated with different drift are segregated rather than interleaved. This is why it is a property of Chronos and not an argument of the allocators.

const (
	// Δ ≈ 131 µs (𝑫 = 0) — ordering only, no attribution. ⟨𝒙ₗ⟩ vanishes and
	// the field order degenerates to ⟨𝒅⟩·⟨𝑬⟩·⟨𝒍⟩·⟨𝒔⟩, which is Snowflake's;
	// the window is 2ε, the tightest any coordination-free schema reaches.
	// A run is one tick wide, so this rung buys no attribution — pick it to
	// track real time, not to tell two writers apart.
	Drift131us Drift = iota
	// Δ ≈ 2.15 s (𝑫 = 14) — a consensus election plus lease expiry, Raft or
	// etcd in one datacenter. The lowest rung with a failover story.
	Drift2s
	// Δ ≈ 17.2 s (𝑫 = 17) — gossip convergence, ZooKeeper and Consul
	// sessions, fast failure detectors.
	Drift17s
	// Δ ≈ 68.7 s (𝑫 = 19) — Kubernetes node-NotReady plus reschedule, Kafka
	// session timeout, load balancer health-check chains.
	Drift68s
	// Δ ≈ 274.9 s (𝑫 = 21) — automated cross-AZ hand-over, phi-accrual
	// detection, unmanaged clocks. The default, see WithDrift.
	Drift275s
	// Δ ≈ 1099 s, 18.3 min (𝑫 = 23) — slow membership convergence, paging,
	// cross-region hand-over.
	Drift1099s
	// Δ ≈ 4398 s, 73.3 min (𝑫 = 25) — on-call human-in-the-loop failover.
	Drift4398s
	// Δ ≈ 140737 s, 39.1 h (𝑫 = 30) — a split brain discovered the next
	// morning, a fleet that syncs once a day, a region isolated for a
	// working day. A time range narrower than Δ costs one seek per ⟨𝒍⟩
	// rather than one contiguous range, and only an assigned ⟨𝒍⟩ can be
	// enumerated to make those seeks, see WithNodeID.
	Drift39h
)

The drift ladder.

⟨𝒅⟩ is 3 bits, so the ladder has eight rungs while the layout admits every 𝑫 ∈ {0,…,46}. The rungs are therefore chosen rather than contiguous, and they are chosen as failover budgets: seven of the eight lie between a consensus election and a split brain found the next morning, the eighth is the floor, for a deployment that wants ordering and no attribution at all.

Two rungs are only operationally distinct where the wider Δ is large against 2ε, since the window is Δ + 2ε — which is why the ladder does not subdivide the sub-second range: below a second the rung stops deciding the window and the quality of the deployment's clocks decides it instead.

Each constant is named for its window Δ rounded down, the exact value and the deployment it is intended for are given below.

func DriftOf

func DriftOf(drift time.Duration) Drift

DriftOf selects the smallest rung of the ladder whose window Δ covers the requested budget, so that the k-ordering absorbs at least that much.

The budget is a failover interval — detection plus convergence, the longest single overlap two owners of one range can have — and never less than the deployment's worst clock skew ε, since a rung below ε is decided by the clocks rather than by the setting. A budget above the top rung selects the top rung.

func (Drift) Bits

func (d Drift) Bits() uint64

Bits returns 𝑫, the number of ⟨𝒕⟩ bits that rank below ⟨𝒍⟩ at this rung. E.g. 𝑫 = 21 makes the last 21 bits of the truncated timestamp less significant than the location.

func (Drift) String

func (d Drift) String() string

String returns the window of the rung, e.g. "274.877906944s".

func (Drift) Window

func (d Drift) Window() time.Duration

Window returns Δ, the width of the window inside which ⟨𝒍⟩ outranks ⟨𝒕⟩.

Δ = 2^(17+𝑫) nanoseconds. It is the schema's half of the drift window 𝑾 = Δ + 2ε; the other half is the quality of the deployment's clocks.

type G

type G [SizeG]byte

G is a globally unique 96-bit k-ordered value. It requires no central registration process.

3bit  47 bit - 𝒅 bit         32 bit     𝒅 bit  14 bit
|-|-------------------|----------------|-----|-------|
⟨𝒅⟩        ⟨𝒕⟩                ⟨𝒍⟩         ⟨𝒕⟩     ⟨𝒔⟩

The type holds the big-endian representation of that 96-bit number and nothing else, which makes it exactly 12 bytes wide with single byte alignment. The representation is the one the schema is defined in, so memory I/O costs nothing:

↣ a [n]G or []G packs without padding, 12 bytes per value;

↣ the wire format is the value itself, g[:] is a valid encoding and
  copy(g[:], buf) a valid decoding, neither shifts a single bit;

↣ the byte order is the order of the identifiers, so bytes.Compare,
  bytes.Equal and sort.Slice over the raw bytes agree with Before,
  After and Equal.

Unlike X, G reserves no version or variant field: every 96-bit number is a syntactically valid G, so FromBytes, FromString and FromBase62 can reject a malformed length but not a garbage payload of the right one — there is no bit pattern left for the schema to check, and widening the layout to make room for one would cost every value of the type, not only the decoded ones. An application that must tell a genuine G from arbitrary data has to keep that guarantee on its own side, e.g. by wrapping G in a type nothing outside this package can construct, or by storing a provenance tag alongside it. Reach for X when that validation matters more than the footprint; its FromString, FromBytes and FromBase62 all check the version and variant RFC 9562 fixes.

func FromV2

func FromV2(isBase62 bool, val string) (G, error)

FromV2 decodes a G produced by v2 of this library (module path github.com/fogfish/guid, before the /v3 split): val is a v2 String encoding if isBase62 is false, a v2 Base62 encoding if true. See the package comment above for why this needs to exist at all — do not decode a v2 value with G's own FromString or FromBase62, both silently misread ⟨𝒍⟩ and ⟨𝒕⟩ for seven of v2's eight drift settings.

Use it once, to rewrite a v2 keyspace; the result is an ordinary v3 G and needs no further special handling.

func NewG

func NewG(clock Chronos) G

NewG allocates globally unique 96-bit k-ordered value.

The ⟨𝒅⟩ drift is taken from the clock, see WithDrift, so that every value of a keyspace is allocated with the same one.

func ZeroG

func ZeroG(clock Chronos) G

ZeroG returns the "zero" 96-bit k-ordered value, the value that precedes every value allocated by the clock.

func (G) After

func (uid G) After(b G) bool

After checks if k-ordered value A is after value B

func (G) Base62

func (uid G) Base62() string

Base62 encodes k-ordered value to a lexicographically sortable base62 string. The output is zero-padded to a fixed width per type, which is what makes it sortable: a positional numeral system only orders lexicographically at a fixed width, since a shorter, unpadded string can otherwise sort after a longer one representing a larger value.

func (G) Before

func (uid G) Before(b G) bool

Before checks if k-ordered value A is before value B

func (G) Bytes

func (uid G) Bytes() []byte

Bytes encodes k-ordered value to byte slice.

The value is already its own encoding, uid[:] is the same bytes without the copy. Use it on the hot path when the slice does not outlive the value.

func (G) Diff

func (uid G) Diff(b G) G

Diff approximates distance between k-ordered values.

func (G) Drift

func (uid G) Drift() Drift

Drift returns the ⟨𝒅⟩ fraction, the rung of the ladder the value was allocated with. The code occupies the 3 most significant bits of the value.

func (G) Epoch

func (uid G) Epoch() time.Time

Epoch returns the wall clock instant the value was allocated at.

The instant is a fact about the allocation, not about the layout of the keyspace: a value allocated by a descending clock reports the same time as one allocated by a forward clock at the same moment, see TimeOrder. Ordering questions are answered by Before, After and Time instead.

The instant is accurate to one tick, 2¹⁷ ns ≈ 131 µs, and is meaningful only for a clock whose ⟨𝒕⟩ is unix nanoseconds, which is every clock but one built on a custom generator in other units, see WithClock.

func (G) Equal

func (uid G) Equal(b G) bool

Equal compares k-ordered values, returns true if values are equal

func (*G) Fold

func (uid *G) Fold(n uint64, bytes []byte)

Fold composes the value from a byte slice. It is the inverse of Split, the value n being the number of bits each cell of the slice carries.

func (*G) FromBase62

func (uid *G) FromBase62(val string) error

FromBase62 decodes the value from the base62 string. It is the inverse of Base62.

func (*G) FromBytes

func (uid *G) FromBytes(val []byte) error

FromBytes decodes the value from its wire format. It is the inverse of Bytes.

func (*G) FromL

func (uid *G) FromL(clock Chronos, val L)

FromL casts a locally unique 64-bit value to this globally unique 96-bit one by stamping it with the ⟨𝒍⟩ fraction of the clock.

func (*G) FromString

func (uid *G) FromString(val string) error

FromString decodes the value from the lexicographically sortable string. It is the inverse of String.

func (*G) FromTime

func (uid *G) FromTime(clock Chronos, t time.Time)

FromTime sets the value to a wall clock instant.

The instant is placed into the time domain of the clock, so that the value sorts against values the clock allocates, see TimeOrder.

func (*G) FromX

func (uid *G) FromX(val X) error

FromX casts a globally unique 128-bit value to this compact 96-bit one.

The conversion is lossy: ⟨𝒍⟩ has to narrow from 58 bits to the 32 that G gives it, and two nodes that differ only above bit 32 would collapse onto the same G. Rather than let that collision happen silently, the cast fails when val's node does not fit in 32 bits — the application has to resolve the conflict, e.g. by reassigning the colliding node, before the two can share a G keyspace. The two types must not share a keyspace in any case, see X.

func (G) MarshalBinary

func (uid G) MarshalBinary() ([]byte, error)

MarshalBinary implements encoding.BinaryMarshaler, see Bytes.

func (G) MarshalJSON

func (uid G) MarshalJSON() ([]byte, error)

MarshalJSON encodes k-ordered value to lexicographically sortable JSON string

func (G) MarshalText

func (uid G) MarshalText() ([]byte, error)

MarshalText implements encoding.TextMarshaler, so that the value travels through any codec that speaks it — yaml, toml, a struct tag, a map key.

func (G) Node

func (uid G) Node() uint64

Node returns ⟨𝒍⟩ location fraction from identifier.

func (G) Seq

func (uid G) Seq() uint64

Seq returns ⟨𝒔⟩ sequence value. The value of monotonic unique integer at the time of k-ordered value creation.

func (G) Split

func (uid G) Split(n uint64) []byte

Split decomposes the value to bytes slice. The function acts as binary comprehension, the value n defines number of bits to extract into each cell.

func (G) String

func (uid G) String() string

String encodes k-ordered value to lexicographically sortable string

func (G) Time

func (uid G) Time() uint64

Time returns ⟨𝒕⟩ timestamp fraction from identifier in nano seconds.

⟨𝒕⟩ is split around ⟨𝒍⟩: the epoch ⟨𝑬⟩ = ⌊𝒙/2^𝑫⌋ ranks above the location and the low bits ⟨𝒙ₗ⟩ = 𝒙 mod 2^𝑫 below it, see makeG.

  3      47 − 𝑫        32          𝑫       14
|---|--------------|------------|-------|--------|
 ⟨𝒅⟩      ⟨𝑬⟩           ⟨𝒍⟩       ⟨𝒙ₗ⟩      ⟨𝒔⟩

func (*G) UnmarshalBinary

func (uid *G) UnmarshalBinary(b []byte) error

UnmarshalBinary implements encoding.BinaryUnmarshaler, see FromBytes.

func (*G) UnmarshalJSON

func (uid *G) UnmarshalJSON(b []byte) error

UnmarshalJSON decodes lexicographically sortable string to k-ordered value

func (*G) UnmarshalText

func (uid *G) UnmarshalText(b []byte) error

UnmarshalText implements encoding.TextUnmarshaler, see FromString.

type L

type L uint64

L is a locally unique 64-bit k-ordered value. It carries no ⟨𝒍⟩ location fraction, values are therefore unique only within the allocator that produced them.

3bit        47 bit           14 bit
|-|------------------------|-------|
⟨𝒅⟩           ⟨𝒕⟩              ⟨𝒔⟩

The type is the 64-bit number itself, one machine word. It is passed in registers, compared with a single instruction and stored in 8 bytes, so it costs no more than the uint64 an application would otherwise use as a surrogate key.

Like G, L reserves no version or variant field: every 64-bit number is a syntactically valid L, so FromBytes, FromString and FromBase62 can reject a malformed length but not a garbage payload of the right one. An application that must tell a genuine L from arbitrary data has to keep that guarantee on its own side, e.g. by wrapping L in a type nothing outside this package can construct, or by storing a provenance tag alongside it, see G for the same note in full.

func NewL

func NewL(clock Chronos) L

NewL allocates locally unique 64-bit k-ordered value.

The ⟨𝒅⟩ drift is taken from the clock, see WithDrift. A local value has no ⟨𝒍⟩ fraction for the drift to rank against, so the code only travels with the value, to be restored by G.FromL.

func ZeroL

func ZeroL(clock Chronos) L

ZeroL returns the "zero" 64-bit k-ordered value, the value that precedes every value allocated by the clock.

func (L) After

func (uid L) After(b L) bool

After checks if k-ordered value A is after value B

func (L) Base62

func (uid L) Base62() string

Base62 encodes k-ordered value to a lexicographically sortable base62 string. The output is zero-padded to a fixed width per type, which is what makes it sortable: a positional numeral system only orders lexicographically at a fixed width, since a shorter, unpadded string can otherwise sort after a longer one representing a larger value.

func (L) Before

func (uid L) Before(b L) bool

Before checks if k-ordered value A is before value B

func (L) Bytes

func (uid L) Bytes() []byte

Bytes encodes k-ordered value to byte slice

func (L) Diff

func (uid L) Diff(b L) L

Diff approximates distance between k-ordered values.

func (L) Drift

func (uid L) Drift() Drift

Drift returns the ⟨𝒅⟩ fraction, the rung of the ladder the value was allocated with, which ranks ⟨𝒕⟩ against ⟨𝒍⟩ once the value is cast to G. The code occupies the 3 most significant bits of the value.

func (L) Epoch

func (uid L) Epoch() time.Time

Epoch returns the wall clock instant the value was allocated at.

The instant is a fact about the allocation, not about the layout of the keyspace: a value allocated by a descending clock reports the same time as one allocated by a forward clock at the same moment, see TimeOrder. Ordering questions are answered by Before, After and Time instead.

The instant is accurate to one tick, 2¹⁷ ns ≈ 131 µs, and is meaningful only for a clock whose ⟨𝒕⟩ is unix nanoseconds, which is every clock but one built on a custom generator in other units, see WithClock.

func (L) Equal

func (uid L) Equal(b L) bool

Equal compares k-ordered values, returns true if values are equal

func (*L) Fold

func (uid *L) Fold(n uint64, bytes []byte)

Fold composes the value from a byte slice. It is the inverse of Split, the value n being the number of bits each cell of the slice carries.

func (*L) FromBase62

func (uid *L) FromBase62(val string) error

FromBase62 decodes the value from the base62 string. It is the inverse of Base62.

func (*L) FromBytes

func (uid *L) FromBytes(val []byte) error

FromBytes decodes the value from its wire format. It is the inverse of Bytes.

func (*L) FromG

func (uid *L) FromG(val G)

FromG casts a globally unique 96-bit value to this locally unique 64-bit one by dropping the ⟨𝒍⟩ fraction.

func (*L) FromString

func (uid *L) FromString(val string) error

FromString decodes the value from the lexicographically sortable string. It is the inverse of String.

func (*L) FromTime

func (uid *L) FromTime(clock Chronos, t time.Time)

FromTime sets the value to a wall clock instant.

The instant is placed into the time domain of the clock, so that the value sorts against values the clock allocates, see TimeOrder.

func (*L) FromX

func (uid *L) FromX(val X) error

FromX casts a globally unique 128-bit value to this locally unique 64-bit one by dropping the ⟨𝒍⟩ fraction.

func (L) MarshalBinary

func (uid L) MarshalBinary() ([]byte, error)

MarshalBinary implements encoding.BinaryMarshaler, see Bytes.

func (L) MarshalJSON

func (uid L) MarshalJSON() ([]byte, error)

MarshalJSON encodes k-ordered value to lexicographically sortable JSON string

func (L) MarshalText

func (uid L) MarshalText() ([]byte, error)

MarshalText implements encoding.TextMarshaler, so that the value travels through any codec that speaks it — yaml, toml, a struct tag, a map key.

func (L) Seq

func (uid L) Seq() uint64

Seq returns ⟨𝒔⟩ sequence value. The value of monotonic unique integer at the time of k-ordered value creation.

func (L) Split

func (uid L) Split(n uint64) []byte

Split decomposes the value to bytes slice. The function acts as binary comprehension, the value n defines number of bits to extract into each cell.

func (L) String

func (uid L) String() string

String encodes k-ordered value to lexicographically sortable string

func (L) Time

func (uid L) Time() uint64

Time returns ⟨𝒕⟩ timestamp fraction from identifier in nano seconds

func (*L) UnmarshalBinary

func (uid *L) UnmarshalBinary(b []byte) error

UnmarshalBinary implements encoding.BinaryUnmarshaler, see FromBytes.

func (*L) UnmarshalJSON

func (uid *L) UnmarshalJSON(b []byte) error

UnmarshalJSON decodes lexicographically sortable string to k-ordered value

func (*L) UnmarshalText

func (uid *L) UnmarshalText(b []byte) error

UnmarshalText implements encoding.TextUnmarshaler, see FromString.

type OrdRingG

type OrdRingG uint64

OrdRingG is the order on G cut at a ring position — the key whose successor list the order is to agree with. It is that position, so the conversion is the constructor:

ord := guid.OrdRingG(token >> 32)
slices.SortFunc(uids, ord.Compare)

The position is taken at the width G gives ⟨𝒍⟩ and masked to it, the same truncation WithNodeID undergoes when a value is stamped, so a token wider than the field is to be shifted down here exactly as it is there. Ref reports the position actually compared against.

The zero value is the order cut at the origin, which is Before.

func (OrdRingG) After

func (ord OrdRingG) After(a, b G) bool

After reports whether a follows b in the order cut at Ref.

func (OrdRingG) Before

func (ord OrdRingG) Before(a, b G) bool

Before reports whether a precedes b in the order cut at Ref.

func (OrdRingG) Compare

func (ord OrdRingG) Compare(a, b G) int

Compare orders a and b relative to Ref, returning -1, 0 or +1. The signature is the one slices.SortFunc and slices.BinarySearchFunc take.

The comparison is lexicographic on ⟨𝒅⟩, ⟨𝑬⟩, the rotated ⟨𝒍⟩ and ⟨𝒙ₗ⟩⟨𝒔⟩. Only ⟨𝒍⟩ is rotated: ⟨𝒅⟩ segregates the rungs and ⟨𝑬⟩ dominates everything below it exactly as it does under Before, so ring order permutes values within one epoch of one rung and nowhere else.

func (OrdRingG) Ref

func (ord OrdRingG) Ref() uint64

Ref returns the ring position the order is cut at, at the width of ⟨𝒍⟩. A position wider than the field reads back truncated, because that is the part of it the comparison uses.

type OrdRingX

type OrdRingX uint64

OrdRingX is the order on X cut at a ring position, see OrdRingG. X gives ⟨𝒍⟩ 58 bits rather than 32, so a 64-bit ring token is shifted by 6:

ord := guid.OrdRingX(token >> 6)
slices.SortFunc(uids, ord.Compare)

The zero value is the order cut at the origin, which is Before.

func (OrdRingX) After

func (ord OrdRingX) After(a, b X) bool

After reports whether a follows b in the order cut at Ref.

func (OrdRingX) Before

func (ord OrdRingX) Before(a, b X) bool

Before reports whether a precedes b in the order cut at Ref.

func (OrdRingX) Compare

func (ord OrdRingX) Compare(a, b X) int

Compare orders a and b relative to Ref, returning -1, 0 or +1. The signature is the one slices.SortFunc and slices.BinarySearchFunc take.

The comparison is lexicographic on ⟨𝒅⟩, ⟨𝑬⟩, the rotated ⟨𝒍⟩ and ⟨𝒙ₗ⟩⟨𝒔⟩ of the payload, so the version and variant RFC 9562 fixes take no part in it — they are constants, and §1.2′ of doc/proof.md shows the splice changes no order.

func (OrdRingX) Ref

func (ord OrdRingX) Ref() uint64

Ref returns the ring position the order is cut at, at the width of ⟨𝒍⟩. A position wider than the field reads back truncated, because that is the part of it the comparison uses.

type TimeOrder

type TimeOrder int

TimeOrder is the direction of the time domain a clock allocates from, the way its ⟨𝒕⟩ fraction moves as real time advances.

The direction is a decision about keyspace layout, not a fact about the events being identified: the same instant is the same instant whichever way the index is laid out. Epoch therefore reports wall clock time regardless of it, while the sort order of values follows it.

const (
	// ForwardTime domain, ⟨𝒕⟩ = UnixNano. Older values sort first.
	ForwardTime TimeOrder = iota
	// InverseTime domain, ⟨𝒕⟩ = MaxUint64 − UnixNano. Recent values sort
	// first, e.g. so that a range scan returns the newest rows without a
	// reverse.
	InverseTime
)

type X

type X [SizeX]byte

X is a globally unique 128-bit k-ordered value that is also a well-formed RFC 9562 UUID of version 8.

It carries the same five fractions as G in the same order, so everything proven about the ordering of G holds for it, with the ⟨𝒍⟩ location widened from 32 to 58 bits:

3bit  47 bit - 𝒅 bit             58 bit          𝒅 bit  14 bit
|-|-------------------|--------------------------|-----|-------|
⟨𝒅⟩        ⟨𝒕⟩                    ⟨𝒍⟩               ⟨𝒕⟩     ⟨𝒔⟩

The widening is the point of the type rather than a side effect of its width. The birthday bound on randomly allocated node identities moves from ≈ 6.5·10⁴ allocators for G to ≈ 5.4·10⁸ for X, which takes node collision out of the set of things an operator has to reason about. Ordering is proven; uniqueness is the assumption that bites, see §5 of doc/proof.md.

An identifier other systems understand

Those five fractions occupy 122 bits. The remaining 6 are the version and variant fields RFC 9562 fixes, so the value is not merely UUID-shaped: it renders as a UUID, parses as a UUID, and drops into a uuid column in PostgreSQL, MySQL or SQL Server, into every UUID library of every language, and into every debugger and log viewer, rather than showing up as a malformed v7. A schema whose premise is allocation across uncoordinated nodes should be readable by more than one language, and a cluster of uncoordinated nodes is rarely a cluster of uniform Go processes.

The reserved bits cost 6 bits of payload and nothing else. They are constants of the format, so at every one of those bit positions two values are identical and a most-significant-first comparison falls through to the next position: lexicographic order over the 128 bits is exactly lexicographic order over the variable payload, in field order. bytes.Compare over the raw bytes therefore still agrees with Before, exactly as for G.

Choosing between X, G and L

many uncoordinated allocators, interop or node count matters  X  16 B
many uncoordinated allocators, storage footprint matters      G  12 B
one allocator, or a context that disambiguates                L   8 B

X and G values must never share a keyspace. They are different widths with different field semantics and no ordering relation between them is defined; convert explicitly at the boundary with G.FromX.

func NewX

func NewX(clock Chronos) X

NewX allocates a globally unique 128-bit k-ordered value.

The ⟨𝒅⟩ drift is taken from the clock, see WithDrift, so that every value of a keyspace is allocated with the same one. The clock's ⟨𝒍⟩ node identity is used at its full 58-bit width, unlike NewG which truncates it to 32 bits.

func ZeroX

func ZeroX(clock Chronos) X

ZeroX returns the "zero" 128-bit k-ordered value, the value that precedes every value allocated by the clock.

Its payload is zero; its bytes are not, since the version and variant fields are present in every value of the format.

func (X) After

func (uid X) After(b X) bool

After checks if k-ordered value A is after value B

func (X) Base62

func (uid X) Base62() string

Base62 encodes k-ordered value to a lexicographically sortable base62 string. The output is zero-padded to a fixed width per type, which is what makes it sortable: a positional numeral system only orders lexicographically at a fixed width, since a shorter, unpadded string can otherwise sort after a longer one representing a larger value.

func (X) Before

func (uid X) Before(b X) bool

Before checks if k-ordered value A is before value B

func (X) Bytes

func (uid X) Bytes() []byte

Bytes encodes k-ordered value to byte slice.

The value is already its own encoding, uid[:] is the same bytes without the copy. Use it on the hot path when the slice does not outlive the value.

func (X) Diff

func (uid X) Diff(b X) X

Diff approximates distance between k-ordered values.

func (X) Drift

func (uid X) Drift() Drift

Drift returns the ⟨𝒅⟩ fraction, the rung of the ladder the value was allocated with. The code occupies the 3 most significant bits of the value, as it does in G and L — the first reserved field of the UUID sits well below it, at bit 48.

func (X) Epoch

func (uid X) Epoch() time.Time

Epoch returns the wall clock instant the value was allocated at.

The instant is a fact about the allocation, not about the layout of the keyspace: a value allocated by a descending clock reports the same time as one allocated by a forward clock at the same moment, see TimeOrder. Ordering questions are answered by Before, After and Time instead.

The instant is accurate to one tick, 2¹⁷ ns ≈ 131 µs, and is meaningful only for a clock whose ⟨𝒕⟩ is unix nanoseconds, which is every clock but one built on a custom generator in other units, see WithClock.

func (X) Equal

func (uid X) Equal(b X) bool

Equal compares k-ordered values, returns true if values are equal

func (*X) Fold

func (uid *X) Fold(n uint64, bytes []byte)

Fold composes the value from a byte slice. It is the inverse of Split, the value n being the number of bits each cell of the slice carries.

func (*X) FromBase62

func (uid *X) FromBase62(val string) error

FromBase62 decodes the value from the base62 string. It is the inverse of Base62.

The version and variant fields are checked, see FromString.

func (*X) FromBytes

func (uid *X) FromBytes(val []byte) error

FromBytes decodes the value from its wire format. It is the inverse of Bytes.

The version and variant fields are checked, see FromString.

func (*X) FromG

func (uid *X) FromG(val G) error

FromG casts a globally unique 96-bit value to this 128-bit one.

The conversion is exact but it does not invent node identity: ⟨𝒍⟩ keeps the 32 bits it had, the 26 bits X adds are zero, and so is the birthday bound of the original value. Only values allocated by NewX carry a 58-bit node.

func (*X) FromL

func (uid *X) FromL(clock Chronos, val L) error

FromL casts a locally unique 64-bit value to this globally unique 128-bit one by stamping it with the ⟨𝒍⟩ fraction of the clock.

func (*X) FromString

func (uid *X) FromString(val string) error

FromString decodes the value from the canonical UUID string, in either case, e.g. "06377f2a-0cb8-8000-8000-000000000001". It is the inverse of String.

The version and variant fields are checked: a UUID of another version does not carry these fractions at these positions, so decoding one would report a time and a node that were never allocated. It is not checked, because it cannot be, that a v8 UUID was minted by this library rather than by another application of the same version.

func (*X) FromTime

func (uid *X) FromTime(clock Chronos, t time.Time)

FromTime sets the value to a wall clock instant.

The instant is placed into the time domain of the clock, so that the value sorts against values the clock allocates, see TimeOrder.

func (X) MarshalBinary

func (uid X) MarshalBinary() ([]byte, error)

MarshalBinary implements encoding.BinaryMarshaler, see Bytes.

func (X) MarshalJSON

func (uid X) MarshalJSON() ([]byte, error)

MarshalJSON encodes k-ordered value to the canonical UUID string

func (X) MarshalText

func (uid X) MarshalText() ([]byte, error)

MarshalText implements encoding.TextMarshaler. It is what makes the value render as a UUID in yaml, toml, a struct tag or a map key, and not only in JSON.

func (X) Node

func (uid X) Node() uint64

Node returns ⟨𝒍⟩ location fraction from identifier, at the full 58 bits X gives it.

func (X) Seq

func (uid X) Seq() uint64

Seq returns ⟨𝒔⟩ sequence value. The value of monotonic unique integer at the time of k-ordered value creation.

func (X) Split

func (uid X) Split(n uint64) []byte

Split decomposes the value to bytes slice. The function acts as binary comprehension, the value n defines number of bits to extract into each cell. It has to divide 128.

func (X) String

func (uid X) String() string

String encodes the value into the canonical UUID string, xxxxxxxx-xxxx-8xxx-yxxx-xxxxxxxxxxxx.

Unlike G and L, which use a private alphabet chosen so that the string sorts the way the value does, X emits the form every other system recognises — that recognition being the whole reason for the type. The canonical form is hexadecimal and big-endian, so it sorts correctly anyway, as long as the comparison is case sensitive and the dashes line up, which for a fixed-width encoding they do. Base62 remains available as the compact representation.

func (X) Time

func (uid X) Time() uint64

Time returns ⟨𝒕⟩ timestamp fraction from identifier in nano seconds.

⟨𝒕⟩ is split around ⟨𝒍⟩: the epoch ⟨𝑬⟩ = ⌊𝒙/2^𝑫⌋ ranks above the location and the low bits ⟨𝒙ₗ⟩ = 𝒙 mod 2^𝑫 below it, see makeX.

  3      47 − 𝑫            58            𝑫       14
|---|--------------|------------------|-------|--------|
 ⟨𝒅⟩      ⟨𝑬⟩              ⟨𝒍⟩          ⟨𝒙ₗ⟩      ⟨𝒔⟩

func (*X) UnmarshalBinary

func (uid *X) UnmarshalBinary(b []byte) error

UnmarshalBinary implements encoding.BinaryUnmarshaler, see FromBytes.

func (*X) UnmarshalJSON

func (uid *X) UnmarshalJSON(b []byte) error

UnmarshalJSON decodes the canonical UUID string to k-ordered value

func (*X) UnmarshalText

func (uid *X) UnmarshalText(b []byte) error

UnmarshalText implements encoding.TextUnmarshaler, see FromString.

Directories

Path Synopsis
examples
guid command
Command guid allocates k-ordered identifiers and writes them to stdout, one per line.
Command guid allocates k-ordered identifiers and writes them to stdout, one per line.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL