Bulleted is an outliner where every bullet is an AT Protocol record in the identity's PDS. An important design decision is that a bullet names its parent and there is no children array. That leaves a question the data model has to answer on its own: given a set of records that all point at the same parent, what order do they go in? This post covers the sort key scheme I landed on.

Where order can't live

Every bullet being its own record is the point of the design. A record has an AT-URI, so a bullet is something other data can address: notes attach to it, comments thread under it, other apps can point at it, and moving a subtree means re-pointing one parent reference. Identifiable, addressable data is where most of the value in this model comes from. It also means the order of a sibling group has nowhere obvious to live.

The first idea is to put the order back in one place: a managed index record per parent that lists its children in order. That works in a demo and becomes the worst record in the system at scale. A 3,000 child group is a record holding 3,000 references, every insert rewrites the whole thing, and it is the one record every client editing the list contends on. It is also a second source of truth about structure, so a node and its index can disagree about where the node lives.

The second idea is an integer position on each node. Then somebody inserts above position 3 and every sibling below has to be rewritten. In a local array that is a memmove. Here it is one network write per bullet, against a Personal Data Server that enforces a write budget, over a protocol where each write is a signed commit appended to a Merkle tree. Renumbering a 200 item list is 200 commits, and 200 chances to fail halfway and leave the list in a state no reader can interpret.

The third idea is already sitting there: the record key. Record keys in these collections are TIDs, timestamp identifiers minted at creation. They sort by when the record was made, which is not the order anyone wants, and they cannot change without deleting the record and recreating it under a new key, which breaks every inbound reference and throws away the addressability the design is built on.

Ultimately, I decided that ordering can be accomplished by setting a field of its own on app.bulleted.node:

Whatever goes in that field has one more constraint to satisfy. Two clients can write to the same repository, and records arrive from the firehose out of order or twice. An insert has to be computable from purely local information, the two neighbours, and the value has to still be correct when it lands.

Those constraints point at a fractional index: positions drawn from a dense ordered set, so there is always room between any two of them. An insert touches exactly one record and nothing ever gets renumbered.

Why the keys are strings

The textbook fractional index is a float. Between 1.0 and 2.0 is 1.5. It dies after about fifty inserts into the same gap, because an f64 has 52 bits of mantissa and each halving spends one. Worse, it does not fail when it runs out. The midpoint of two adjacent doubles returns one of the endpoints, and two bullets silently occupy one position.

Strings have no such limit. Between "a" and "b" is "aV", between "a" and "aV" is "aC", and you can keep going as long as you are willing to spend bytes. A string key is a number in base N written as digits after an implied decimal point, and the comparison is plain byte comparison.

The base is 62:

The load-bearing property is that those digits are in ASCII order. '0' < '9' < 'A' < 'Z' < 'a' < 'z' as bytes, 0 < 9 < 10 < 35 < 36 < 61 as values, and the two orderings agree at every position. That agreement is what lets nothing decode a key in order to sort it. SQLite orders a sibling group with a plain ORDER BY sort_key. The browser sorts with < on strings. Both get the same answer as the generator, which reasons in digit values. Pick base 64 with '-' and '' and you break it, since '-' sorts below '0' and '' sorts between 'Z' and 'a'. Base 62 in ASCII order is the largest alphabet where byte order and digit order coincide for free.

One small catch

In a pure fractional scheme every key is conceptually 0[something], a value strictly between 0 and 1. Appending at the end means generating something above the current last key and still below 1. Do it again and you need something above that. The sequence is strictly increasing and bounded above, so it converges, and the only way to keep going is to spend more digits. Measured against Bulleted's generator, a tail append costs about 0.175 bytes. A hundred appends is an 18 byte key. A thousand is 179 bytes. Around 2,900 you hit the 512 byte lexicon cap and the insert fails outright.

Now consider what a tail append is in an outliner. It is pressing Enter. A list typed top to bottom is one tail append per bullet. It is also what the importer does while assigning fresh keys to each sibling group of an imported tree, and a WorkFlowy export with 3,000 children under one parent is completely ordinary. That is a Tuesday, not an adversarial workload, and no amount of tuning fixes it because the growth is structural.

Give the key an integer part

The fix is to stop making every key a pure fraction. A key is an integer part followed by an optional fractional part:

Appending increments the integer part. Prepending decrements it. Only an insert strictly between two existing neighbours ever touches the fraction. The integer part is a positional numeral, so a run of n appends costs O(log n) bytes instead of O(n). Over 100,000 appends the length histogram is {2: 61, 3: 3844, 4: 96095}. The origin had already taken one of the 62 two byte slots, the next 3,844 appends need three bytes, and everything after that fits in four, which covers past 238,000.

The trick that makes this survive byte comparison is that the first character of the integer part encodes how long the integer part is. Lowercase letters are positive magnitudes, so 'a' means a two byte integer part and 'z' means 27. Uppercase letters are negative magnitudes, mirrored, so 'Z' means two bytes and 'A' means 27.

Why encode the width at all? Because a comparison must never need to know where the integer part ends. Take a9 and b00. As numbers the second is larger, it has more digits. As bytes, 'a' < 'b', so the comparison gets the right answer at the first character and never looks further. A longer positive magnitude always starts with a later letter, and a longer negative magnitude always starts with an earlier one, so the ordering falls out of the byte comparison on both sides of zero. That is also why the negative side counts backward. Zz sorts below a0 because 'Z' < 'a', and when the two byte negative band runs out at Z0, it widens downward into Yzz, which still sorts below everything in the Z band.

If you have used David Greenspan's fractional indexing design, the a0 origin and the width marking heads will look familiar. This is that shape of scheme. The differences are in how the branching digit gets picked, what happens to invalid keys, and where generation is allowed to run.

Two rules that look like nitpicks

A position must have exactly one spelling, because anywhere byte order and numeric order disagree, everything above falls apart.

First, a fraction never ends in '0'. Numerically a0V0 equals a0V. As bytes, a0V0 is greater. Allow both spellings and you have two keys that compare as different but denote the same position, which is the situation this whole design exists to prevent. A key with a trailing zero is rejected outright rather than normalized, because silently rewriting a caller's key is a worse surprise than refusing it. The rule also shapes generation: the digit that ends a fraction can never be 0, so a 0 only appears as a carried digit on the way deeper. That is what keeps a0 and a001 splittable. The interval between their fractions holds nothing but 0 at the first two positions, so the descent carries and continues, and between("a0", "a001") comes out as a five byte key starting with a000.

Second, the smallest integer part, 'A' followed by 26 zeros, is reserved. It is a valid prefix but never a valid key on its own. If a node could hold it, nothing could ever be prepended before that node. There is no lower integer part to move to and no fraction to go under. Reserving it means head insertion always has an answer.

Jitter, and why the middle half

When an insert does have to grow the fraction, the branching digit is not the exact midpoint. It is drawn at random from the middle 50% of the open interval. The randomness exists for concurrency: two clients inserting at the same position compute from the same pair of neighbours, and with a deterministic midpoint they would collide every time. The restriction to the middle half exists for length. A uniform draw across the whole interval keeps landing next to a boundary, which corners the next insert at that position and forces it a level deeper. Over a thousand inserts hammered into the same gap, the longest key comes to 184 bytes with the middle half, 202 with the exact midpoint, and 221 with a full width draw.

The tempting shortcut is to compute a midpoint and append random digits to it for collision resistance. When the upper neighbour shares that midpoint as a prefix, appending pushes the result past it, so the same thousand insert test produces keys near 1,000 bytes and keys that sort on the wrong side of the neighbour they were meant to sit below. Jitter belongs in the choice of branching digit. A digit strictly inside the open interval is strictly between the neighbours no matter what it is.

Where it runs

There is exactly one implementation of the generator, and it runs on the server. A client never sends a sortKey. It sends neighbour intent, {parentRkey, afterRkey, beforeRkey, position}, and the server resolves that against the current sibling group under a lock. A client supplied sortKey deserializes into nothing at all, which is deliberate: the server ignores unknown fields, so a write that carried one would succeed and land somewhere else, and that is worse than an error.

Two implementations of an ordering algorithm is two orderings. Keeping generation in one place is most of how you avoid that. The rest is the tiebreaker, because concurrent inserts into an interval with one candidate digit will occasionally produce the same key. The total order everywhere is the pair (sort_key, rkey), with the TID breaking ties the same way for every reader. The app view keeps its copy in SQLite behind a covering index:

Rendering a sibling group is a range scan over that index with no decoding and no sort step.

With that, there are some failure modes to keep in mind. First is that key_between refuses when before >= after, and that is reachable in normal operation. A valid scenario is that the server reads a node's two neighbors, and then another insert lands in the same group, so the captured pair becomes stale. The protocol is to re-read under the parent lock and retried exactly once. A second failure surfaces as a 409 to the client, refetch and re-apply, because nothing is actually broken. And since any client can write a record with a sortKey this code did not generate, a malformed key is not fatal on the read path. That node sorts to the end of its sibling group unordered and the page still renders. Strict on the write path, lenient on the read path.

Port it

There are three single-file implementations, one each in Python, TypeScript, and Go. Each embeds the conformance suite, so python3 sort_key.py, node sort_key.ts, and go run sort_key.go all verify themselves. The deterministic vectors are the place to start, since they are the cases that caught real bugs:

The suite also checks the exact 100,000 append histogram from above, its mirrored prepend twin, ten thousand increment and decrement round trips in each direction, the canonical form reject list, and a hammer test that must end in an Exhausted error rather than a truncated key. That last one matters more than it looks. A truncated key is still a valid key that sits somewhere else in the list, so truncating at the cap silently reorders the very list the caller was inserting into. Exhaustion has to surface as an error.

If you are porting to a fourth language, two mechanical mistakes are worth budgeting for. Compare bytes. A locale aware collation like localeCompare puts 'a' before 'B' on one machine and after it on another, and the keys are ASCII, so byte order is the specification. And in the width transitions, whether a digit gets pushed or popped is the easiest thing to invert. Positive magnitudes get wider as they climb, negative magnitudes get wider as they fall, and a property test that increment and decrement are exact inverses catches a mixup immediately.

The reference implementation is crates/bulleted-core/src/order_key.rs in bulleted-app, 681 lines of implementation and documentation plus 39 tests. If you port it somewhere new and the vectors pass, I would genuinely like to hear about it.