<commit_before># Muid Specification

This document describes three semantically equivalant 
formats for muids:

* A tuple/proto/stuct representation in which 
  the muid is a triplet of numbers (those three being
  timestamp, medallion, and offset, described below)

* A "packed" 128 bit representation.  This binary
  format comes from encoding the three numbers
  into specific bit ranges in big-endian order.
  Sorting these packed representations by bytes
  will also sort them according to the tuple of 
  three component numbers.

* A canonical textual representation of the 
  128 bytes.  This representation will simply
  be the bytes as 32 upper case hex digits.

This specification is heavily inspired by ULID
(https://github.com/ulid/spec) in that it intends to 
specify a scheme for identifiers that can be ordered,
increase over time, and very likely to be unique,
and fit into 128 bits.  

Muids have some additional objectives, however.
For one, we'd like to be able to keep track of
the database node that created a given muid.
Each node in the database will only create objects
with a monotonically increasing time and identifiers.
We may not receive an update from a distant node until well
after it was created, so will have trouble keeping *all*
updates in order, but separating them out by node source
will allow us to keep the updates from each node in order.

Secondly we'd like to be able to specify that a set of updates
from a node should be treated as happening all together 
(in a single atomic transaction).  Since all of these updates
will share the same timestamp and node identifier, some additional
bits need to be used to distinguish between the various updates
within a transaction.  To ensure that all updates within one
transaction are either before or after all updates from another,
the order of components will be: [timestamp, medallion, offset].

# Timestamp
As the name implies, muids have microsecond time resolution.
The first 14 hex digits (7 bytes) of a muid should be the 
number of microseconds since epoch, encoded big-endian.
This will ensure that lexical comparisons of muids will sort
according to time.  As an example, I see the (fractional) unix time
as of this writing to be 1642579230.975519 (generated by python's time.time()).
That corresponds to 1642579230975519 microseconds with hex digits
'5D5EAC793E61F'.  That's only 13 hex digits but muid leaves room for 14,
so a leading 0 should be added to the beginning for
the cononical hex representation of that time: '05D5EAC793E61F'.
Microsecond timestamps through the year 4253 can be represented,
and the microsecond count before the year 2167 can be represented
exactly in an IEEE double.

# Medallion
Each node in the system has a unique medallion to identify it.
A number of different schemes could be
used to assign these numbers, but for version 1, implementations should
randomly select numbers the range 
4503599627370496 to 9007199254740991 ('0x10000000000000' to '0x1FFFFFFFFFFFFF').
Numbers in this range will always have exactly 14 hex digits.
For example, one medallion randomly selected from that range could be
6227685815851846, which has the hex sequence '16200C18D39B46'.

Though this initial version specifies that the first hex digit should 
always be '1', future versions may allow for different digits, so 
implementations should not reject medallions outside the specified range,
though they may assume that the medallion as an integer can be exactly
represented in an IEEE Double.

A muid with a zero medallion ('00000000000000') 
may be used to designate pure timestamp and will 
should never be used as an object identifier
(and if the medallion is 0 the offset should be 0 as well).

# Offset
Only four hex digits remain for the offset, effectively bounding transactions
to have no more 65536 distinct objects a piece.  Additionally,
the offset "0" should be used to designate refer to the transaction itself,
when used with a non-zero medallion.

For example, one offset could be the number 11 which has the hex digits "000B".

# Combined Cononical Representation
Concatenating all of the upper case hex digits in the order:
timestamp, medallion, offset together produces the cononical representation.
Though adding dashes or underscores between components would have made 
the representation marginally easier to read 
(e.g., wrong: "05D5EAC793E61F-16200C18D39B46-000B"), 
the dashes introduce problems for systems that parse hex digits.
So the correct muid combining the examples from above 
should be "05D5EAC793E61F16200C18D39B46000B".
<commit_msg>switched back to a five hex digit offset<commit_after># Muid Specification

This document describes three semantically equivalant 
formats for muids:

* A tuple/proto/stuct representation in which 
  the muid is a triplet of numbers (those three being
  timestamp, medallion, and offset, described below)

* A "packed" 128 bit representation.  This binary
  format comes from encoding the three numbers
  into specific bit ranges in big-endian order.
  Sorting these packed representations by bytes
  will also sort them according to the tuple of 
  three component numbers.

* A canonical textual representation of the 
  128 bytes.  This representation will simply
  be the bytes as 32 upper case hex digits.

This specification is heavily inspired by ULID
(https://github.com/ulid/spec) in that it intends to 
specify a scheme for identifiers that can be ordered,
increase over time, and very likely to be unique,
and fit into 128 bits.  

Muids have some additional objectives, however.
For one, we'd like to be able to keep track of
the database node that created a given muid.
Each node in the database will only create objects
with a monotonically increasing time and identifiers.
We may not receive an update from a distant node until well
after it was created, so will have trouble keeping *all*
updates in order, but separating them out by node source
will allow us to keep the updates from each node in order.

Secondly we'd like to be able to specify that a set of updates
from a node should be treated as happening all together 
(in a single atomic transaction).  Since all of these updates
will share the same timestamp and node identifier, some additional
bits need to be used to distinguish between the various updates
within a transaction.  To ensure that all updates within one
transaction are either before or after all updates from another,
the order of components will be: [timestamp, medallion, offset].

# Timestamp
As the name implies, muids have microsecond time resolution.
The first 14 hex digits (7 bytes) of a muid should be the 
number of microseconds since epoch, encoded big-endian.
This will ensure that lexical comparisons of muids will sort
according to time.  As an example, I see the (fractional) unix time
as of this writing to be 1642579230.975519 (generated by python's time.time()).
That corresponds to 1642579230975519 microseconds with hex digits
'5D5EAC793E61F'.  That's only 13 hex digits but muid leaves room for 14,
so a leading 0 should be added to the beginning for
the cononical hex representation of that time: '05D5EAC793E61F'.
Microsecond timestamps through the year 4253 can be represented,
and the microsecond count before the year 2167 can be represented
exactly in an IEEE double.

# Medallion
Each node in the system has a unique medallion to identify it.
A number of different schemes could be
used to assign these numbers, but for version 1, implementations should
randomly select numbers the range 
281474976710656 to 562949953421312 (2 ** 48 to 2 ** 49).
Numbers in this range will always have exactly 13 hex digits.
For example, one medallion randomly selected from that range could be
555027746660010, which has the hex sequence `1F8CB77AE1EAA`.

Though this initial version specifies that the first hex digit should 
always be '1', future versions may allow for different digits, so 
implementations should not reject medallions outside the specified range,
though they may assume that the medallion as an integer can be exactly
represented in an IEEE Double.

A muid with a zero medallion (`00000000000000`) 
may be used to designate pure timestamp and will 
never be used as an object identifier
(and if the medallion is 0 the offset must be 0 as well).

# Offset
Only five hex digits remain for the offset, effectively bounding transactions
to have no more 1,048,576 distinct objects.  Additionally,
the offset "0" should be used to designate refer to the transaction itself,
when used with a non-zero medallion.

For example, one offset could be the number 11 which has the hex digits "0000B".

# Combined String Representation
Concatenating all of the upper case hex digits in the order:
timestamp, medallion, offset together produces the cononical string representation.
If the offset is 0 it may be omitted, and if both the offset and medallion are 0
they may both be omitted.

For example, combining the values from the prior explinations would give a muid who's string representation is `05D5EAC793E61F-1F8CB77AE1EAA-0000B`.

Replacing the offset with 0 (representing the containing transaction) would give
the muid `05D5EAC793E61F-1F8CB77AE1EAA-00000` that could also be written 
`05D5EAC793E61F-1F8CB77AE1EAA`.

Replacing both the offset and transaction numbers with 0 would result in a muid
who's representation would be `05D5EAC793E61F-0000000000000-00000` or
`05D5EAC793E61F-0000000000000` or `05D5EAC793E61F`.

{'fraction_non_alphanumeric': 0.034082515563997044, 'fraction_numerical': 0.05233723752242271, 'mean_word_length': 4.631610219845514, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 6, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3770339', 'n_tokens_mistral': 2837, 'n_tokens_neox': 2413, 'n_words': 1450}