K03. Identifiers: tags of ten characters

The corpus programme makes millions of nodes and tens of millions of inventory rows. A tag of six characters (spec 04.3) gives about 1.07 billion values. That is enough for the nodes, but it is too tight for random minting at the scale of the inventory, and it has no protection against a mistyped tag. This document replaces the tag format of spec 04.3 with a tag of ten characters. It also says what happens to the tags that already exist, how files are sharded, and what must change in the main spec and in the code.

K3.1 The decision

A new tag has ten characters: nine random characters and one check character, all from Crockford base32. The tags of six characters that exist on the day of the change stay valid forever, as a frozen legacy set. No new tag of six characters is minted after that day.

The three rules of spec 04.3 do not change. A tag is assigned once, it is never edited, and it is never reused. The legacy tags are not converted to long tags, because a conversion would edit a tag. A node with a legacy tag keeps it. A node never has two tags.

K3.2 Why ten characters

• Room for the inventory. The inventory (K04) has one row for each candidate item, and the research layer has 10 to 30 million rows (K2.7). Rows and nodes share one space of identifiers (K3.6), so that a bare identifier resolves to one thing. With 6 characters and 30 million identifiers in use, about 3% of random draws collide. With 9 random characters, the chance is below 1 in a million for each draw.
• Random minting without coordination. Spec 04.3 mints tags at random, so that two branches can mint without a central counter. A sparse space keeps collisions at merge rare. With 3.5 × 10^13 values and 100 million in use, the chance that one draw collides is about 3 in 10^6.
• A check character. People copy tags by hand into papers, emails and search boxes. One mistyped character in a tag of six characters gives another valid tag, which can be the tag of another node. The check character detects each error in one character and almost each swap of two adjacent characters. A tool can then say "this tag has a typo" and not show the wrong node.
• Still short. Ten characters fit in a citation, a URL and a Lean attribute. A Stacks tag has four characters, a Wikidata id has up to 10 characters, and a DOI is much longer.

Eleven or twelve characters would give more room, but we have no use for it. Ten characters give room for the research layer at a thousand times its estimated size.

K3.3 The format

A tag of ten characters is P1 P2 ... P9 C:

• P1 to P9 are random characters of the alphabet 0123456789ABCDEFGHJKMNPQRSTVWXYZ. The value of a character is its position in this alphabet, from 0 to 31.
• C is the check character. It is computed from P1 to P9 by the Luhn mod N algorithm with N = 32:
  1. Start at P9 and go to the left. The factor of P9 is 2, the factor of P8 is 1, then 2, then 1, and so on.
  2. For each character, multiply its value by its factor. Write the product in base 32 and add its digits: product / 32 + product mod 32.
  3. Add the results. The check value is (32 - (sum mod 32)) mod 32. C is the character with that value.
• To validate a tag, do the same over all ten characters with the factor 1 for C, then 2 for P9, and so on. The tag is valid when the sum is a multiple of 32.

Example: for 7K3QX2M9R the check character is 2, thus the tag is 7K3QX2M9R2. If a person types 7K3XQ2M9R2 (two characters swapped) or 7KZQX2M9R2 (one character changed), the validation fails.

These rules of spec 04.3 apply to long tags too:

• The seed prefix. A tag that starts with 0 belongs to the bootstrap seed. Mint never gives one. MintSeed gives one.
• No tag that reads as another kind of identifier. Mint does not give a tag that YAML reads as a number, or that starts with an MSC code (for example 20D60...). For long tags it also refuses a tag with fewer than two letters. That rule removes each tag that could be an ISBN-10 (nine digits and a digit or X) and each tag that looks like a phone number or a numeric id.

K3.4 Input and display

• The canonical form is ten capital characters with no separator: 7K3QX2M9R2. Files, registers, URIs and the API use only the canonical form.
• For reading, the workspace and printed works can show a tag in two groups of five: 7K3QX-2M9R2. The hyphen is not part of the tag.
• Normalization on input. The resolver accepts lower case, hyphens and spaces, and the Crockford substitutions I and L for 1 and O for 0. It normalizes, then it validates the check character. A long tag that fails the check gives the error "not a valid tag: the check character does not match". It never resolves to the nearest valid tag, because that can be another node.
• Legacy tags have no check character. The resolver accepts a six-character string only when it is in the legacy set of registers/tags.reg.

K3.5 Sharding

Spec 04.5 shards node files by the first two characters of the tag, which gives 1,024 directories. At a million nodes that is about 1,000 files in each directory. The corpus target for nodes is 1 to 5 million (K2.7), which would give up to 5,000 files in each directory. That makes git trees large and slow.

The new shard key is the first three characters of the tag, for long and legacy tags. That gives 32,768 directories:

The path of a node is nodes/<c1 c2 c3>/<tag>.md, for example nodes/7K3/7K3QX2M9R2.md and nodes/3C5/3C53TD.md. The same key shards prov/, reviews/ and compute/. A path is not an identity, so moving the three legacy node files to the new shards changes no tag. The migration (K3.8) moves them.

K3.6 One space for nodes and inventory rows

The inventory (K04) has one row for each candidate item. A row gets an identifier when the inventory first records it. The identifier has the format of a long tag, and it is minted from the same generator. It is recorded in the inventory register registers/inventory/, which is sharded like the nodes (K4.8), not in registers/tags.reg.

• A row identifier is never a node tag, and a node tag is never a row identifier. Rule T08 (K3.8) checks that the two registers have no value in common.
• With this rule, each bare identifier resolves to one thing: a node, or an inventory row. The URI of a row is m2://inv/<id>. The URI of a node stays m2://<tag>.
• When a row becomes a node, the node gets its own tag, and the row records it in its outcome. The row identifier is not reused as the tag, because a tag promises a node, and most rows of the research layer never become nodes.

The other identifiers of math2 do not change: provisional ids (~ and 8 hex characters), run ids, review ids, project ids and record ids of the record plane.

K3.7 What this changes in the main spec

The change is additive for readers of math2: each URI that worked before still works.

K3.8 What this changes in the code

The toolchain in tamnd/math2-agent holds the tag format in a few places. The change is one pull request for each repository, in this order:

1. tag: Len becomes 10 for new tags, with LegacyLen 6. IsTag accepts a long tag with a valid check character, or a legacy tag. IsLegacy reports the second case. Mint and MintSeed draw nine characters (45 bits, from 6 random bytes), refuse excluded values (K3.3), and append the check character. A new function Check(payload string) byte computes the check character, and Normalize(s string) (string, error) implements K3.4. Each exported function keeps a testable example.
2. schema/node.v1.json in both repositories: the tag pattern becomes ^([0-9A-HJKMNP-TV-Z]{6}|[0-9A-HJKMNP-TV-Z]{10})$. The check character cannot be expressed in JSON Schema, so rule T09 checks it. The review id pattern r-TAG-NN accepts both lengths. This is an additive change of node.v1 (spec 04.9), because each file that was valid stays valid.
3. The shard function (in node and its users: build, audit, site, prov, review, compute): three characters. m2 migrate shard3 moves the files of an existing tree, and it is safe to run again.
4. audit: T06 accepts both lengths. New rules T08, T09 and T10 as in K3.7. T10 reads the cut-over commit from registers/README.md.
5. The Lean attribute Math2.Meta.Attr, which checks the tag argument of @[math2 TAG], accepts both lengths and the check character.
6. The site and the API: the resolver normalizes input (K3.4). Pages and JSON use the canonical form. The display form with a hyphen is used only in printed works (K11).
7. tamnd/math2: run m2 migrate shard3, record the cut-over commit, and freeze the legacy set. On the day of this spec the legacy set is three tags: 3C53TD, AAYEQE and G5S1M9.

The test fixtures of the toolchain use legacy tags in many places. They stay as they are, because legacy tags stay valid. New fixtures use long tags.

K3.9 Rejected options

• Convert each legacy tag to a long tag. This would edit a tag, which spec 04.3 forbids. It would also break each link to the published pages of the three legacy nodes. The gain is only that all tags have one length.
• Ten random characters with no check character. This gives 32 times more values, which we do not need, and it loses typo detection, which we do need for tags that people type.
• The check symbol of Crockford's own scheme. It uses modulo 37 and needs the five extra symbols * ~ $ = U. These symbols are not safe in URLs, file names and Lean identifiers.
• A sequential counter. It needs coordination between branches, and it leaks the order of creation, which some contributors do not want to show.

Markdown · Source · Edit