TID spec details

[bnewbold]

The current docs for at:// URIs indicate that record-id (aka TID, aka rkey) can be arbitrarily long or short. In the examples, they are shown and described as something similar to a twitter snowflake ID: a numerical timestamp, sub-millisecond counter, and "clock identifier".

There are some more details in the current Javascript source code, but a few things are ambiguous. My understanding of how to generate a TID is:

• "clock ID" is a random 5-bit identifier that is constant for a given PDS process (eg, re-generated at process startup, doesn't need to persist across reboots/restarts)
• "counter ID" is an integer between 0 and 9999. starts with 0 and increments for each TID generated in the same milisecond by the same "clock ID"
• "timestamp" is miliseconds since UNIX epoch in UTC timezone, represented as a 64-bit number
• construct a 64-bit number by multiplying timestamp by 1000 and adding counter ID to it
• base32sortable-encode the resulting number, then base32sortable-encode the clock ID (resulting in a single character) and append that

From a standardization standpoint, it would make more sense to me to implement this as a 64-bit unsigned integer, with specific slices having meaning. AKA, timestamp is 49 bits, counter is 10 bits, clock ID is 5 bits. mask and shift these bits in to place, resulting in a uint64, then encode that with a specified byteorder as base32sortable. Potentially even better would be just using twitter snowflakes themselves, as there are already several implementations.

A couple other detail questions:

• what is the canonical hyphenation scheme for TIDs? some split of characters in the base32sortable output. to be ignored on parsing, I guess
• how should partially-compliant TIDs be handled? eg, the at:// URI scheme is flexible, so presumably implementations need to handle record keys like "1", for example in tests. how should keys with differing lengths get sorted (shorter values before or after long values with the same prefix)?
• what is the byte order and encoding supposed to be? i'm not a javascript expert but my understanding is that all numbers are 64bit floats (with unspecified byte order?)

[AaronGoldman]

https://github.com/bluesky-social/atproto/blob/main/packages/common/src/tid.ts

TID

 1 53                                                    10
 - ----------------------------------------------------- ----------
|0| μs since epoch                                      | clock id |
 - ----------------------------------------------------- ----------

The JavaScript run time gives milliseconds not microseconds. So we pad with 0s.

The time stamp part of the TID needs to be monotonicity increasing. So if we need a new TID and the clock has not ticked we add 1

next_timestamp = max(now(), last_timestamp + 1)

For a given PDS or client we want to have a monotonicity increasing ID.
We don't want any two committers to have the same clock ID so that the TIDs are guaranteed to be unique.
We would need to assign each committer their own ID.

However what do you do if a committer has no clock ID assigned to them. We need a way to say this is a clock that is not persistenting it's last_timestamp and risks collision or regression.

The clock ID space has been partitioned as such.

Clock ID	Purpose
0 - 31 \2[2-7a-z]\	ad-hoc space used by nodes not assigned a clock ID in the Repo
32 - 991 \[2-7a-z]{2}\	assigned in Repo for Repo unique TID
992 - 1023 \z[2-7a-z]\	reserved for Bluesky for globally unique TID

TTTT-TTT-TTTT-CC
11 * 5 bits = 55 > 53 Time stamp
2 * 5 bits = 10 ClockID

The string form sorts in the same order as the int64 form
TIDs can be stored as:
String // TTTT-TTT-TTTT-CC
Int64 // leading 0 always positive
Uint64 // leading 0 always < 2^63
(Timestamp: number, ClockID: number) // timestamp <= number.max_safe_integer 2^53-1

The repo should contain a record mapping Clock IDs to the keys of clients that commit to the repo and thus need to be able to generate repo unique TIDs offline.
If the PDS was the only committer we could use a server could just count to get a unique ID but since clients could be the committers we need a way to partition the ID space and keep them ruffly in order.
A timestamp and clock ID gives us a partitioned space and since the TIDs are monotonic any events with TIDs lower than the highest TID of the farthest behind clock are now in a final ordering.

[bnewbold]

What about byte order, can we assume network byte order (big-endian)? I assume so based on the clock ID coming last in the TID.

[bnewbold]

TIDs are now documented in the Record Key specs: https://atproto.com/specs/record-key#record-key-type-tid