README
¶
ksid: fast 63 bits unique IDs in Go
Properties
- 63 bits IDs that are guaranteed to be unique.
- Native base32 encoding, at most 13 characters.
- Both numerical and string forms are k-sortable.
- Shardable across up to 32768 servers.
- Valid until 2115, or 2204 using the 64th bit.
Performance
- ksid.ID is 50% smaller (8 bytes) than UUIDs (16 bytes) in binary form.
- ksid.ID string is at most 13 characters, 33% the size of UUIDs (36 characters).
- ksid.ID is faster to generate, encode and decode than UUIDs.
- Maximium generation throughput: 32768 ID/10µs and 3.27B ID/s.
Comparison with google/uuid:
- Generation: ksid (~33 ns) is at least ~7.5x faster than both uuid v4 (~250 ns) and uuid v7 (~290 ns).
- Encoding: ksid (~24 ns) is ~2.7x faster than uuid (~65 ns).
- Decoding: ksid (~8 ns) is ~1.8x faster than uuid (~15 ns).
$ go test -bench=.
goos: linux
goarch: amd64
pkg: github.com/maruel/ksid
cpu: 13th Gen Intel(R) Core(TM) i7-13700
BenchmarkID/ksid-gen-24 36123418 33.15 ns/op 0 B/op 0 allocs/op
BenchmarkID/uuidv4-gen-24 4740570 248.8 ns/op 16 B/op 1 allocs/op
BenchmarkID/uuidv7-gen-24 4138654 288.5 ns/op 16 B/op 1 allocs/op
BenchmarkID/ksid-encode-24 95906893 24.37 ns/op 16 B/op 1 allocs/op
BenchmarkID/uuid-encode-24 23047898 64.62 ns/op 48 B/op 1 allocs/op
BenchmarkID/ksid-decode-24 141703341 8.42 ns/op 0 B/op 0 allocs/op
BenchmarkID/uuid-decode-24 78804513 14.89 ns/op 0 B/op 0 allocs/op
When not to use
- Necessitate higher throughput than 1000 IDs per microsecond, or more than ten million IDs per second.
- More than 100 shards or an unbounded number of shards.
Algorithm
I (Marc-Antoine Ruel) invented this algorithm in 2014 while working on the Chromium infrastructure. I designed the algorithm so I could generate unique IDs that would fit 63 bits integers to use as database keys.
Structure
- Bit 63: sign (always 0, keeps int64 positive)
- Bits 62-15: 10µs intervals since epoch 2026-01-01 (48 bits)
- Bits 14-0: slice (15 bits = 32768 values per 10µs)
The library has 100% unit testing code coverage.
Documentation
¶
Overview ¶
Package ksid provides k-sortable, 64-bit unique identifiers.
IDs are generated with NewID, encoded to compact base32 Extended Hex strings (≤13 chars, lexicographically sortable), and decoded with Parse. They implement json.Marshaler, json.Unmarshaler, encoding.TextMarshaler, and encoding.TextUnmarshaler so they work transparently as JSON values and map keys.
For multi-process deployments, call InitIDSlice once at startup to partition the slice field and guarantee no collisions across instances.
IDList is a convenience type that marshals to/from comma-separated ID strings, useful for query parameters.
Index ¶
- func InitIDSlice(instance, totalInstances int) error
- type ID
- func (id ID) Compare(other ID) int
- func (id ID) IsZero() bool
- func (id ID) MarshalJSON() ([]byte, error)
- func (id ID) MarshalText() ([]byte, error)
- func (id ID) Slice() int
- func (id ID) String() string
- func (id ID) Time() time.Time
- func (id *ID) UnmarshalJSON(data []byte) error
- func (id *ID) UnmarshalText(text []byte) error
- type IDList
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func InitIDSlice ¶
InitIDSlice configures ID generation for multi-instance deployments.
When running multiple parallel processes that generate IDs, each process must call InitIDSlice with a unique instance number to prevent ID collisions. The slice field's low-order bits are partitioned among instances.
Parameters:
- instance: this process's instance number (0 to totalInstances-1)
- totalInstances: total number of parallel processes
Example: with 3 servers, call InitIDSlice(0, 3), InitIDSlice(1, 3), and InitIDSlice(2, 3) on each respective server. Each server will have a fraction of the maximum throughput.
Must be called before any NewID calls. Returns an error if parameters are invalid or if totalInstances exceeds the available slice bits.
Example ¶
package main
import (
"fmt"
"github.com/maruel/ksid"
)
func main() {
// In a multi-process environment, call InitIDSlice once at startup.
// For example, if this is instance 2 of 5:
err := ksid.InitIDSlice(2, 5)
if err != nil {
fmt.Printf("Error: %v\n", err)
return
}
id := ksid.NewID()
// The slice part of the ID will be partitioned.
if id.Slice()%5 == 2 {
fmt.Println("ID belongs to instance 2")
}
}
Output: ID belongs to instance 2
Types ¶
type ID ¶
type ID uint64
ID is a time-sortable 64-bit identifier resistant to collisions.
IDs encode a 10µs timestamp and a monotonically increasing slice for collision avoidance. They are lexicographically sortable when encoded as strings, making them suitable for use as table keys and filenames.
The zero value (0) represents an invalid/unset ID.
ID structure (64 bits):
- Bit 63: sign (always 0, keeps int64 positive)
- Bits 62-15: 10µs intervals since epoch (48 bits)
- Bits 14-0: slice (15 bits = 32768 values per 10µs)
The slice field can be partitioned across multiple processes using InitIDSlice. The lowest-order bits of the slice are reserved for the instance ID, ensuring IDs generated by different processes never collide.
Time span: ~89 years from epoch (until ~2115), doublable by leveraging the 63rd bit.
Max throughput: ~3.27B IDs/sec total (32768 per 10µs × 100,000 intervals/sec).
func NewID ¶
func NewID() ID
NewID generates a new time-based ID.
IDs are guaranteed to be unique and monotonically increasing within a process. Multiple calls in the same 10µs interval use an incrementing slice counter. When multiple instances are configured via InitIDSlice, the slice counter is partitioned so each instance uses non-overlapping values. If the slice overflows, it spins until the next interval to maintain uniqueness.
Example ¶
package main
import (
"fmt"
"github.com/maruel/ksid"
)
func main() {
id := ksid.NewID()
fmt.Printf("Generated a %d-bit ID\n", 64)
// We can't predict the ID, so we just check it's not zero.
if !id.IsZero() {
fmt.Println("ID is non-zero")
}
}
Output: Generated a 64-bit ID ID is non-zero
func Parse ¶
Parse parses an encoded string back to an ID.
Empty string or "0" decode to zero ID. Returns an error for invalid input. Decoding is case-insensitive.
Example ¶
package main
import (
"fmt"
"github.com/maruel/ksid"
)
func main() {
// Parse a known ID string
id, err := ksid.Parse("2")
if err != nil {
fmt.Printf("Error: %v\n", err)
return
}
fmt.Printf("Parsed ID: %d\n", id)
}
Output: Parsed ID: 1
func (ID) MarshalJSON ¶
MarshalJSON implements json.Marshaler.
func (ID) MarshalText ¶
MarshalText implements encoding.TextMarshaler. This allows ID to be used as a map key in JSON encoding.
func (ID) String ¶
String encodes the ID as a compact, sortable string.
Uses base32 "Extended Hex" alphabet (0-9A-V) which is ASCII-sorted, ensuring lexicographic string comparison matches numeric comparison. Leading zero-characters are stripped for compactness. Zero IDs return "0".
Example ¶
package main
import (
"fmt"
"github.com/maruel/ksid"
)
func main() {
id := ksid.ID(1)
fmt.Printf("ID 1 as string: %s\n", id.String())
}
Output: ID 1 as string: 2
func (ID) Time ¶
Time extracts the timestamp from an ID.
This is the moment this ID was generated, in UTC, at 10µs resolution.
Example ¶
package main
import (
"fmt"
"github.com/maruel/ksid"
)
func main() {
id := ksid.ID(1)
// The epoch is 2026-01-01 00:00:00 UTC.
// ID 1 is the very first possible ID at the epoch with slice 1.
fmt.Printf("ID 1 time: %s\n", id.Time().UTC())
}
Output: ID 1 time: 2026-01-01 00:00:00 +0000 UTC
func (*ID) UnmarshalJSON ¶
UnmarshalJSON implements json.Unmarshaler.
func (*ID) UnmarshalText ¶
UnmarshalText implements encoding.TextUnmarshaler. This allows ID to be used as a map key in JSON decoding.
type IDList ¶
type IDList []ID
IDList is a slice of IDs that can unmarshal from a comma-separated string. Useful for query parameters like ?ids=ABC,DEF,GHI.
func (IDList) MarshalText ¶
MarshalText implements encoding.TextMarshaler.
func (*IDList) UnmarshalText ¶
UnmarshalText implements encoding.TextUnmarshaler for query param parsing.
Source Files