Generating short ordered IDs with any insertion pattern

Articles

Introduction

Say you have a set of elements which need to be ordered, and you want to give each element an ID which reflects its position in the ordering.

This is easy; just give each element an increasing integer ID, and when inserting a new element just increment the IDs of the elements which come after the new element to reflect their new positions.

But what if we do not want to or cannot recalculate the IDs for the entire array? If the IDs could stay fixed once they are generated but still have the property that they are ordered correctly, we could insert elements at any point in the array efficiently without having to perform work for every following element.

Example

An example of this is a user interface which shows a list of items, where the user can insert an item at any point in the list. This might be a web application, where the items and their ordering are stored in a database.

It is common to use something like a column called `order` containing an integer which is used to sort the items when fetching for display, however this suffers the flaw that an insertion must lead to updating `order` of on average half of the rows which constitute the array, and in the worst case (which might be quite common) which is repeatedly inserting at the start of the array, every row needs to be updated on each insert.

CategoryID | CategoryTitle | CategoryOrder
1          | "Books"       | 4
2          | "Clothes"     | 3
3          | "Food"        | 1
4          | "Electronics" | 2
5          | "Garden"      | 5

The above table shows categories which would be displayed in this order based on the `CategoryOrder` column: Food, Electronics, Clothes, Books, Garden. If a new category is inserted between "Food" and "Electronics", it will have to be given an `CategoryOrder` of 2, and every current `CategoryOrder` greater than or equal to 2 will have to be incremented by 1 to make space for it.

You could try to be clever and select 2.5 as the `CategoryOrder` for the new category, but as we will see, this simple approach can easily lead to the order values becoming very long - with a number of digits proportional to the number of elements in the array (if another category is inserted between order 2 and 2.5, then its order in this scheme would be 2.25, which is already one digit longer).

CategoryID | CategoryTitle | CategoryOrder
1          | "Books"       | 4
2          | "Clothes"     | 3
3          | "Food"        | 1
4          | "Electronics" | 2
5          | "Garden"      | 5
6          | "Furniture"   | 2.5?

The Abstraction

Lets define a simple interface which the algorithm can hide behind.

Note that we are less interested in dealing with the IDs themselves, and more interested in creating an array data structure that makes use of them.

Firstly, we need a function which can find the ID between two others, this provides the core functionality we can build on:

//  ID1 < result < ID2
const result = generateIDBetween(ID1, ID2);
assert(ID1 < result && result < ID2);

Now, we can define an array-like abstraction which uses this function:

const array = arrayCreate();
arrayInsert( array, 0, "First" );
arrayInsert( array, 1, "Second" );
arrayInsert( array, 1, "Middle" );
arrayInsert( array, 3, "Last" );
arrayRemove( array, 1 );

console.log( arrayGet(array, 1) );  //  "Middle"

The IDs are strings which when sorted lexicographically, give the correct order of the items in the array, and the algorithm consists of a function for generating an ID which lies between two given IDs, ie.:

This would usually be wrapped up in an abstraction which acts like an array, with insert, delete, length operations. Insertion at an index in the array happens by generating an ID between the IDs of the element currently at that index and the element immediately preceding it.

A naive approach

Say we start with an array of 2 items, with these indices (note that the indices are strings which are increasing lexicographically):

Position | Index
0        | "0"
1        | "1"

Lets say we want to insert an item between "0" and "1". We could reindex the entire array, but that would be inefficient. Instead, we could just insert a new index between "0" and "1" by finding the decimal number between, potentially extending the length of an ID:

Position | Index
0        | "0"
1        | "0.5"
2        | "1"

Adding another element between "0" and "0.5" yields "0.25":

Position | Index
0        | "0"
1        | "0.25"
2        | "0.5"
3        | "1"

This works perfectly well for ordering, but the IDs grow in length linearly with the number of elements in the worst case, as in this example where elements are repeatedly inserted immediately after "0":

Position | Index
0        | "0"
1        | "0.015625"
2        | "0.03125"
3        | "0.0625"
4        | "0.125"
5        | "0.25"
6        | "0.5"
7        | "1"

What we need is a way to generate IDs which don't grow like this, because after inserting say a million elements into an array you don't want the risk that the IDs are a million characters long.

You might think that there would always be adversarial insertion patterns which would cause the IDs to grow linearly, but by introducing some randomness into the algorithm the probability that any sequence of inserts is adversarial can be made arbitrarily small.

LSEQ

The LSEQ algorithm allows for generating IDs which grow logarithmically with the number of elements in the array, independent of the insertion order.

Recall that the usage of the algorithm looks like this:

//  ID1 < result < ID2
const result = generateIDBetween(ID1, ID2);
assert(ID1 < result && result < ID2);

There are a couple of techniques used in the LSEQ algorithm which fit together to make this possible:

  • The ID strings describe a tree, where each layer of nodes is larger

than the previous by some factor.

  • There are a mixture of randomly selected insertion strategies, each

with different strengths and weaknesses.

The tree of IDs

Lets start with the first point. The IDs form a tree by taking the form of a path from the root to a particular leaf, for example:

Position | Index
0        | "0"
1        | "0.00"
2        | "0.05"
3        | "0.20"
4        | "0.39"
5        | "0.39.102"
5        | "0.39.398"
5        | "0.39.760"
6        | "0.10"
7        | "0.99"
8        | "1"

In this case, first layer of the tree has single digit branch IDs, the second layer has two digits, the third has three digits, and so on.

Thus, each layer can hold 10x as many branches as the previous layer.

Notice that each level is sparse, with a few branches with different IDs spread out over the possible values. There are various strategies for deciding how to fill out each layer.

Strategies

This does not seem to help on its own, because when inserting a new ID between two existing IDs, you still have to select where to place that new ID:

  • Close to (or even immediately after) the first ID
  • Close to (or even immediately before) the second ID
  • In the middle of the two IDs
  • In a completely random position between the two IDs

Each of these has strengths and weaknesses - near one or other end of the available range to place the new ID both allow for inserting a new ID in the same place over and over, with the length of the new ID increasing with every insertion and therefore being linear in the number of insertions.

However, if a strategy is chosen randomly, the probability of repeatedly choosing the same strategy decreases exponentially with the number of insertions.

Lets see how different strategy choices affect the lengths of the IDs using synthetic inserts in various patterns:

  • Inserting at the start of the ID list
  • Inserting at the end of the ID list
  • Inserting at the start and end of the ID list randomly
  • Inserting immediately before a specific ID
  • Inserting immediately after a specific ID
  • Inserting immediately before or after a specific ID randomly

Another axis of choice is how to pick the strategy for each insertion and which strategies to include.