idsmall

idsmall allocates short, human-typable identifiers that carry a reversibly scrambled timestamp. A canonical identifier is seven case-sensitive Bitcoin Base58 characters: one seed character followed by six characters encoding the universal time, scrambled by a bijection derived from that seed.

(idsmall:identifier-generate)
;; => "31uWB8L"

(idsmall:identifier-display "31uWB8L")
;; => "3-1uWB8L"

(idsmall:identifier-timestamp "31uWB8L")
;; => 3993000000

Identifiers are short enough to read aloud and type. They sort into no meaningful order. The timestamp is recoverable with this library.

Format

The alphabet omits 0, O, I, and l, so no two characters look alike. The seed character selects an odd multiplier and an offset, both derived from the seed index by the MurmurHash3 32-bit finalizer over two fixed domain constants. The multiplier is forced odd, which makes the scramble a bijection modulo two to the thirty-second and therefore exactly reversible.

Every intermediate product is reduced modulo two to the thirty-second, so identifiers are portable across hosts of any fixnum width. Six Base58 characters span more than two to the thirty-second values, so every unsigned 32-bit input has one fixed-width encoding.

The format is fixed. The internal alphabet and suffix width define every identifier already stored.

Display form

identifier-display inserts a hyphen after the seed character, which makes the two parts distinguishable when a person reads an identifier back. Every function accepting an identifier accepts both forms, and identifier-normalize converts either to the canonical form. Both signal identifier-error on anything else, so callers holding foreign or legacy values should guard those calls.

Allocation

One namespace holds at most identifier-base identifiers per second, one per seed, so allocation checks for collisions. The caller supplies occupancy:

(idsmall:identifier-generate
 :occupied-p (lambda (candidate)
               (probe-file (merge-pathnames (format nil "~A.sexp" candidate)
                                            #p"/var/lib/example/"))))

The first seed comes from *random-index-function*, which is seeded from the operating system. A taken candidate causes every remaining seed to be probed exactly once, so allocation either succeeds or signals identifier-space-exhausted for a full second. Entropy quality only spreads identifiers across seeds. Bind *random-index-function* to make allocation reproducible under test.

occupied-p runs while the allocation lock is held.

Reservations

A generated identifier is reserved in this process until it is released, so two threads receive distinct values while the first has yet to persist it.

(let ((identifier (idsmall:identifier-generate :namespace :conversations)))
  (unwind-protect
       (persist identifier)
    (idsmall:identifier-release identifier :namespace :conversations)))

Release an identifier once the caller’s own storage holds it, or once the work that requested it is abandoned. A leaked reservation costs one seed for one second. Reservations are process-local: they coordinate threads. Concurrent processes sharing storage must make occupied-p authoritative.

:namespace separates independent identifier spaces in one process; it defaults to t. identifier-clear-reservations drops every reservation, which suits test teardown.

Timestamp range

identifier-timestamp is exact for every universal time below two to the thirty-second seconds, which covers dates before 2036. Later timestamps encode and decode modulo that bound.

Tests

(asdf:test-system :idsmall)

License

Licensed under COLL-Attribution. See LICENSE.lisp for the authoritative terms.

Part of the Lambda Symbolics library shelf.