permid64 0.1.0

Clock-free, persistent, reversible-permutation 64-bit ID generation

permid64

Clock-free, persistent, reversible-permutation 64-bit ID generation.

Counter in, permutation out.

permid64 generates unique 64-bit integer IDs without relying on wall-clock time. It combines a crash-safe persistent counter with an invertible permutation to produce IDs that look random but carry recoverable metadata.

# Raw counter (leaks business volume at a glance)
1001, 1002, 1003 ...

# permid64 (shuffled surface, recoverable structure)
12609531668580943872, 7349201938475629, 3847291038012847 ...
# decode(12609531668580943872)  →  instance_id=42, sequence=0

---

What it is

• A clock-free 64-bit ID generator — no timestamp, no NTP dependency
• IDs are unique because the source is a monotonically increasing counter
• IDs look shuffled because they pass through a reversible permutation
• The permutation is invertible — decode() recovers the original metadata

What it is not

• Not a timestamp-based scheme — there is no time component in the ID
• Not a UUID replacement for every scenario — if you need a globally unique random token with no infrastructure at all, UUID v4 is simpler
• Not cryptographic encryption — the permutation is an obfuscation layer, not authenticated encryption; do not use IDs as secrets or security tokens
• Not safe for multiple processes sharing one state file — PersistentCounterSource is single-process only; concurrent writes from multiple processes to the same state file will cause duplicates (see Limitations)

---

Design

seq  = source.next()                    # monotonic counter (persistent)
raw  = layout.compose(instance_id, seq) # pack 16-bit shard + 48-bit seq
id64 = permutation.forward(raw)         # obfuscate with invertible bijection

Layout — default 64-bit split:

[ instance_id : 16 bits ][ sequence : 48 bits ]

• Up to 65 535 independent shards
• Up to 281 trillion IDs per shard

Permutations — both are bijections over [0, 2^64):

Mode	Formula	Speed	Mixing
multiplicative	f(x) = (a·x + b) mod 2^64	~500 M/s	Good
feistel	64-bit Feistel network	~150 M/s	Excellent

Persistence — block reservation strategy:

1. On startup, read high-water mark from state file.
2. Reserve a block of N sequence numbers, write new high-water mark.
3. Serve IDs from memory until block exhausted.
4. If the process crashes, the unused block is lost (gap), but no duplicate is ever issued.

---

Quick start

from permid64 import Id64

# Multiplicative (fastest)
gen = Id64.multiplicative(
    instance_id=42,
    state_file="permid64.state",
    block_size=4096,
)

uid = gen.next_u64()          # e.g. 12609531668580943872
meta = gen.decode(uid)
# DecodedId(raw=2748779069440, instance_id=42, sequence=0)
print(meta.instance_id, meta.sequence)

# Feistel (better statistical mixing)
gen2 = Id64.feistel(
    instance_id=42,
    state_file="permid64.state",
    block_size=4096,
    key=0xDEADBEEFCAFEBABE,
    rounds=6,
)

Why decode() matters

In production, when an anomalous ID appears in a log or alert, you can decode it instantly — no DB lookup needed:

meta = gen.decode(12609531668580943872)
print(f"Issued by instance {meta.instance_id}, sequence #{meta.sequence}")
# Issued by instance 42, sequence #0

This makes incident tracing dramatically faster: you immediately know which shard issued the ID and its approximate position in the issuance history.

Assigning instance_id

Assign each process or deployment unit a distinct instance_id. Common patterns:

import os

# From environment variable (works in Docker / K8s)
instance_id = int(os.environ.get("INSTANCE_ID", "0"))

# From K8s StatefulSet pod name (e.g. "worker-3" -> 3)
import re
pod_name = os.environ.get("POD_NAME", "worker-0")
instance_id = int(re.search(r"(\d+)$", pod_name).group(1))

Each instance_id gets its own independent sequence space — no coordination needed between shards.

---

Installation

pip install permid64          # once published to PyPI
# or from source:
pip install -e ".[dev]"

---

Running tests

pytest

Five acceptance criteria are checked:

1. Uniqueness — 1 million IDs, zero duplicates
2. Invertibility — decode(next_u64()) recovers instance_id and sequence
3. Restart safety — sequence never resets across process restarts
4. Gap tolerance — crash causes a gap, never a duplicate
5. Thread safety — concurrent generation remains unique

---

Benchmark

python benchmarks/bench_id64.py

Sample output (Apple M2):

[Permutation comparison — block_size=4096]
  multiplicative (default keys)          ~480,000,000 IDs/sec
  feistel (6 rounds)                     ~140,000,000 IDs/sec
  feistel (12 rounds)                     ~80,000,000 IDs/sec

---

Guarantees

Guarantee	Notes
No duplicate IDs within a shard	Strict
No duplicates across restarts	Strict — state file must be on durable storage
Decodable	Only with the same permutation key / params
Gaps allowed	After a crash, some sequence numbers are skipped
No global coordination	Each instance_id is fully independent

---

Limitations

Single-process only

PersistentCounterSource is not safe for concurrent use across multiple processes sharing the same state file. A best-effort fcntl.flock advisory lock is applied during block reservation on POSIX systems, but this is not a hard guarantee — do not rely on it as a substitute for proper shard isolation.

The correct pattern for multiple processes is to assign each a distinct instance_id and a distinct state file. Multi-process coordination via a central allocator is planned for v0.3.

Feistel is obfuscation, not encryption

The Feistel permutation provides strong mixing and is reversible, but it is not a formally audited cryptographic primitive. Do not rely on it for access control, token authentication, or any security-sensitive use case.

instance_id must be assigned manually

There is no automatic shard coordination. Assign instance_id values via config or environment variables and ensure they are unique across your deployment.

Sequence space is large but finite

The default 48-bit sequence space supports ~281 trillion IDs per shard. This is enough for virtually all workloads, but it is not infinite.

---

Architecture

permid64/
  __init__.py       # public exports: Id64, DecodedId
  generator.py      # Id64 façade
  source.py         # PersistentCounterSource
  layout.py         # Layout64 — pack/unpack 64-bit raw value
  permutation.py    # MultiplyOddPermutation, Feistel64Permutation
  types.py          # DecodedId dataclass

tests/
  test_counter.py
  test_layout.py
  test_permutation.py
  test_id64_e2e.py   # the 5 MVP acceptance tests

benchmarks/
  bench_id64.py

---

Roadmap

Version	Focus
v0.1 (current)	Core: counter + permutation + decode
v0.2	IdentityPermutation, Base32/Base62 encoding, Id64Config
v0.3	Multi-process file locking, ReservedBlockSource (central allocator)
v0.4+	Rust/Go reference implementations, formal cross-language spec

---

License

MIT