The Time-Ordered ID and base32lex Binary Encoding

1.1. Base32lex encoding

The 32 code points chosen to encode from binary, in order, are:¶

value               1111111111222222222233
          01234567890123456789012345678901
encoding  234567abcdefghijklmnopqrstuvwxyz

This differs from the canonical base32 encoding defined in [RFC4648] in two ways: firstly, the letters are lowercase, and secondly, the letters and numbers are inverted in the mapping sequence, such that bytewise ordering of binary TIDs and lexical sorting of base-encoded TIDs will always achieve the same ordering.¶

value                1111111111222222222233
           01234567890123456789012345678901
base32lex  234567abcdefghijklmnopqrstuvwxyz
base32     ABCDEFGHIJKLMNOPQRSTUVWXYZ234567

2.1. Timestamp Component

The form of timestamp used to generate a TID is the number of microseconds since the Unix epoch (1970-01-01T00:00:00+00:00), i.e. with three more digits than an [RFC5102] dateTimeMilliseconds. In cases where a timestamping service may be returning timestamps faster than 1000 times every millisecond, uniqueness should be favored over microsecond accuracy; i.e., the ID generator should return the current microsecond since epoch OR the last microsecond returned plus 1, whichever is greater.¶

The effective range of TIDs is limited by the compaction into int64 form and the 10 bytes used to encode the nodeId segment; for reasons that will be explained below, it is further limited by one byte to avoid some translation problems with the targeted encodings and type systems, leaving 53 bytes of signed space for a subset of unix microsecond timestamps. Effectively, this means that the range of microseconds before or after 1970, expressed as a signed integer, is not (-2^63+1) to (2^63-1), but (-2^53+1) to (2^53-1). The following tables shows the min, zero, and max values of the integer range of microseconds, expressed in the 11-codepoint base32lex encoding. The additional 2 codepoints for the nodeId segment, explained below, are omitted for clarity.¶

Note that half the possible range of values encodable in 11 codepoints are considered invalid TIDs, as their binary form would not fit safely in an int64 bytestring. As the canonical form of TIDs is an int64 bytestring, the invalid half of the string-encodable range should not be mistaken for valid TIDs and software handling these TID should validate strings accordingly.¶

2.2. Node Identifier Component

The node identifier, by analogy to the equivalent element in an [RFC9562] UUIDv6, is a spatially-unique identifier, but occupying a much smaller space (10 bits, as opposed to UUIDv6's 48 bits). It is divided into three contiguous ranges. The first 32 values (0-31, i.e. "20" - "2z" base-encoded) are reserved for "best effort" collision-resistance TIDs. The bulk of the range, (32-991, i.e. "30" - "yz" base-encoded) is reserved for context-dependent use. The remaining 32 entries (992-1023, i.e. "z0" - "zz" base-encoded) are reserved for globally unique TIDs.¶

"Best effort" node identifiers can be generated without coordination or deferral to external authorities, but are considered likely to collide when merged with data from external sources.¶

Context-dependent node identifiers should be use in the context of a specific application where they can be derived stably from application context. The application developer should take steps to ensure the that in any given time range, no node identifiers are in simultaneous use by two different actors. No process is specified for coordinating leases of node identifiers to actors.¶

Globally-unique node identifiers should only be used after being registered globally. At time of writing, there is only one public TimeID service operating.¶

2.3. Base-Encoded String Expression

The TimeID concatenates the timestamp and the node identifier. The string format is 11 code points of timestamp and 2 code points of node identifier, displayed for readability with - segment dividers after the 4th, 7th, and 11th code points:¶

STTT-TTT-TTTT-CC

Where:¶

• S represents a character with limited range, representing 3 bytes of timestamp¶

• each T represents 5-bytes of the timestamp, and¶

• each C represent a 5-byte character from the node identifier¶

The timestamp is expressed in a string-form TID as the first 11 codepoints, i.e. 55 bytes, but in the binary form as the first 54 bytes of an int64. Note that the range of times that fit into those 54 bytes is actually a little smaller than 0 +/- (2^55-1); namely, it is 0 +/- (2^53-1). This is to accomodate various type-system quirks in the targeted languages and encodings: firstly, unsigned integers are problematic for JSON encoding (particularly JSON tooling), requiring the "assumed byte" (the 55th byte hard-coded into the decoding process) to designate a positive or negative number. Similarly, the 54th byte has to "sign extend" that positive or negative sign to keep the total integer expressible in a sign-extended 63 bytes to accomodate a quirk of the Java type system that converts integers bigger than 63 bytes to float64s. Sacrificing these two bytes of range safeguards round-trip translation of these int64s to JSON or Java and back.¶

We can take the timestamp 2024-07-19T09:40:46.480310 as an example to show the process. This is 1721382046481000 microseconds since Unix epoch. On a node with identifer 01, this base-encodes to:¶

3kxn-lhr-3gxq-23
 | |   |    |  |
 | |   |    |  NodeID 0-1023
 | |   |    microsecond
 | |   second
 | 10 hours (9.54 hours)
 year (1.115 years)

When using TimeIDs in string form, "prefixes" can be used to mask ranges, i.e.¶

6.1. Normative References

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/rfc/rfc2119>.

[RFC8174]

Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

6.2. Informative References

[RFC4648]

Josefsson, S., "The Base16, Base32, and Base64 Data Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006, <https://www.rfc-editor.org/rfc/rfc4648>.

[RFC9562]

Davis, K., Peabody, B., and P. Leach, "Universally Unique IDentifiers (UUIDs)", RFC 9562, DOI 10.17487/RFC9562, May 2024, <https://www.rfc-editor.org/rfc/rfc9562>.

[RFC5102]

Quittek, J., Bryant, S., Claise, B., Aitken, P., and J. Meyer, "Information Model for IP Flow Information Export", RFC 5102, DOI 10.17487/RFC5102, January 2008, <https://www.rfc-editor.org/rfc/rfc5102>.