Time, Ordering and Identifiers

Time, Ordering and Identifiers

A timestamp, an identifier and an ordering decision answer different questions. Time may express when a user wanted work to happen; an ID names one logical object; a protocol decides which conflicting operation wins. A time-prefixed ID can improve storage locality without proving that its numeric order matches real-time completion or causality across machines.

Choose the clock for the question

This original exercise schedules exports and records their results across regions. Users choose calendar times, workers need elapsed deadlines, and an authoritative store decides the winning result generation. Each boundary needs a different contract.

Wall clocks can be adjusted. Monotonic readings have a local origin and contract; do not serialize them as globally comparable timestamps. Suspend/restart behavior is platform-specific. A request budget must account for actual elapsed time and propagation assumptions. Sending the original full timeout to every dependency repeatedly spends the same time budget.

Work a clock rollback

An export attempt starts at wall time 10,000 ms and local monotonic time 200 ms. A wall-clock correction occurs; at completion the wall clock reads 9,900 ms and the monotonic clock reads 700 ms. Wall subtraction produces −100 ms; elapsed work was 500 ms in this model. A deadline of 600 elapsed ms has 100 ms left, regardless of the wall correction.

That local result says nothing about how far another worker's wall clock is ahead. For absolute schedules use the selected authoritative wall-time policy; for ownership use enforceable generations and state. Neither an NTP daemon nor a monotonic timer retracts an external effect sent by an obsolete worker.

Read the diagram

Worker issues an ID at clock millisecond 500 → Wall time moves backward to 499 → Generator refuses issuance below its saved watermark → New owner restores the allocation watermark → Issuance resumes at a unique eligible position

View full sizeOpen original

Time, Ordering and Identifiers

Reset viewClose

Waiting or failing safely is preferable to silently reusing identifier state after rollback.

Establish causality with a message history

For a scalar Lamport-style clock, increment on a local/send event; on receiving a message with timestamp M, assign max(local, M) + 1. Original trace: A sends at logical time 1, B receives at 2, B sends at 3 and A receives at 4. The send event precedes its receive event in this history. Two independent processes can both emit 1; a (logical_time, process_id) tie-break produces a deterministic total order consistent with this clock discipline, but does not discover a causal connection between those independent events.

The implication is one-way: causal precedence implies increasing logical time under the stated algorithm, while a smaller scalar value does not prove causal precedence. Vector clocks can represent more causal information, at state/metadata cost. Hybrid logical clocks combine physical-time information and logical advancement under their protocol. Neither is a generic substitute for a database's supported transaction/commit ordering or a consensus decision.

For a chat conversation, a server sequence can define one authoritative conversation order. It does not automatically order all chats, nor prove that every device displayed the event. Keep stream position, application acknowledgement and user-visible read state separate.

Select an identifier from its required properties

Use a well-tested standards-compliant library for actual UUIDs. RFC 9562 defines UUID versions and implementation considerations. A UUIDv4 has 122 random bits after fixed version/variant fields; with independent uniform draws, the birthday approximation for a billion IDs is about n(n−1)/2^123 ≈ 9.4×10^-20. This is a probability under assumptions, not a proof that broken entropy, copied generator state or software bugs cannot collide. Treat uniqueness constraints and collision handling as part of the design where appropriate. IDs do not grant access and should not be used as bearer secrets merely because they are hard to guess.

UUIDv7 uses a millisecond time prefix; its remaining fields and optional monotonic generation methods must follow the standard. Do not invent one custom layout and label it UUIDv7. Equal-millisecond ordering and clock rollback behavior depend on the implementation's supported contract.

Make a custom allocation contract explicit

For an illustrative 64-bit scheme, reserve one sign bit, 41 timestamp bits relative to an epoch, 10 worker bits and 12 counter bits. This permits 1,024 worker codes and 4,096 positions per millisecond per worker. Those are field capacities, not measured throughput. The timestamp range is about 69.7 years, so epoch exhaustion is an operational concern too.

require trusted current ownership of worker code W
load persisted last_timestamp and sequence for W
if clock_ms < last_timestamp: refuse/wait under bounded policy
if same millisecond: increment sequence only within its field capacity
if later millisecond: reset sequence under the allocation protocol
persist/reserve the issued position before acknowledging it
encode(timestamp, W, sequence)

Persisting every ID may defeat the desired throughput. An implementation can reserve disjoint ranges ahead of time, with safe recovery that never reissues a possibly used range. That creates gaps after a crash, which is usually better than duplicate identity. Reusing a worker code while an old owner still issues IDs also requires fencing or disjoint generation/range rules; worker names in configuration are insufficient.

If a same-tick counter is full, wait for an eligible later tick or reject. Wrapping to zero creates duplicates. If a process restarts, loading just the worker code while forgetting its watermark/sequence can do the same. The repository model scales the field widths down to make exhaustion easy to test; it is not a production Snowflake or UUID implementation.

Separate ID order from commit order

Transaction A allocates ID 100, pauses; B allocates 101 and commits; A commits later. Ascending IDs now disagree with completion order. Across workers, a fast wall clock can also issue a larger time prefix before another operation occurs. If the product needs a trustworthy auction-close winner, use the auction's authoritative admission/close decision, not the lexical maximum of client-generated IDs.

For pagination, (created_at, unique_id) can give deterministic tie-breaking, but concurrent inserts and edits still need a defined snapshot/keyset policy. An identifier cannot recover a missing history segment. For replay, preserve operation IDs rather than minting a new ID for each attempt.

Handle calendars without inventing elapsed guarantees

Store the original named timezone and a rule for nonexistent/repeated local times. Materialize eligible UTC instants into versioned occurrence identities. A UTC instant is unambiguous once chosen; it does not explain whether a repeated local 01:30 should execute once or twice. Timezone database changes and schedule edits need an effective-time/version policy.

The Job Scheduler deep dive works concrete gap/fold fixtures and misfire recovery. Do not interpret “daily” as always 86,400 seconds, or a due timestamp as proof that execution starts immediately under overload.

Check your understanding

Question: Wall time decreased by 100 ms during work, while local monotonic time advanced 500 ms. Was the operation's duration negative?

Question: A receives B's logical timestamp 7 while A's local clock is 4. What receive timestamp does the stated rule assign, and does scalar order alone prove causality for unrelated events?

Question: A worker's counter overflows within the same millisecond. May it wrap to zero because its worker code is unique?

Transfer exercise and scoring

For Job Scheduler, Online Auction and WhatsApp, name the time semantics, identity scope, authoritative ordering decision, restart/rollback policy and replay identity. Score one point per justified choice. Give a counterexample in which sorting timestamps or IDs chooses the wrong business result.

Prerequisites: Consensus, Leader Election and Fencing and Idempotency and Delivery Semantics.

Primary references and scope

• Lamport: Time, Clocks and the Ordering of Events for the causal-order/logical-clock distinction.
• RFC 9562 for UUID formats and generation considerations.

The clock readings, custom bit layout, message trace and allocation policy above are original exercises. Model tests do not synchronize real clocks, implement a distributed identifier service or prove a production ordering contract.