Scaling Fractional Indexes

Today we'll be talking about fractional indexes, how to scale them to efficiently support millions of entries with minimal memory footprint and how to encode them efficiently. We'll also cover some domain-specific ideas that you may find novel.

What is a fractional index

While it was discussed several times on this blog (1, 2), let's make quick recap on what fractional index actually is.

In short, Fractional Index is a Conflict Free Replicated Data Type (CRDT) that enables building indexable sequences with insert capabilities. The clue of its conflict resolution algorithm lies in creating byte string keys, which lexical order would match their insert order.

We're not going to cover the interleaving issues today - we did it already another time. For the use case described today interleaving is acceptable tradeoff.

A new fractional key byte string can be created at position N, by taking its neighbours and copying the bytes of the lower neighbour until the spare byte space is found, that would differentiate it from the upper neighbour. If there's no such space left, we simply append a new byte at the end of the key to differentiate it.

Since it's certainly possible, that two peers could generate the same fractional key, when defining an insert at the same position, we also append peer's unique ID at the end of it to make them distinct.

Problem statement

Since now we roughly know, how they work, let's clarify what are we going to use them for. Our case is building a collaborative spreadsheet. The baseline of this data structure was already presented before. The purpose of fractional index in this setup is to create an unique row/column IDs, that can be used to address individual cells in a stable manner.

There are several challenges here:

• The scale: it's not uncommon to find spreadsheets which can contain hundreds of thousands, possibly millions of rows.
• We care about memory: nowadays a lot of spreadsheet engines work in the browser, and are using WebAssembly modules to manage their state (which atm. are capped at 32bit (4GB) address space).
• Regular pattern of work includes shifting row/column position, which means we need to support move semantics.
• Most of the time rows are not inserted explicitly. You can just infini-scroll over the spreadsheet and fill the cell in there, acting as if it was always there. This imposes a special behaviour, which we'll cover at the end of this blog post.

Reducing memory footprint

First, we're going to cover an optimisation that we're going to leverage later. As we mentioned, fractional indexes are usually strings of bytes, which means they are heap allocated. Having millions of heap allocated objects may not be a big deal, but we can do better and remove all of the indirections and pointer jumping right away.

Since most of the keys are very short, we're going to optimise that and use smart pointers instead.

• top-first byte describes a length of the key in bytes: that means 255 byte length is our limit.
• the 4 bottom-most bytes describe the session id
• the middle 3 bytes are the generated key position itself, which is enough to represent 2^24 unique keys (over 16 mln entries)

Since we can fit entire key on 8 bytes, it means that we can represent it as a singe 64bit word. No need to heap alloc, as the entire struct is small enough to fit a single heap pointer - or just twice as much on WebAssembly.

Of course, sometimes we need to produce the key, that would run past 3 byte position. In that case we'll check if top-most byte length is over 7, and then reinterpret lower 7 bytes as a heap pointer address. It's fine since none of the existing OSes and hardware architectures makes use of more than 7 byte address space anyway.

Building fractional keys in batches

One of the issues in generating fractional keys and scale is that naive generation leads to quick explosion of the key size. 

Example: if we want to insert bunch of fractional keys in empty index, we can insert 255 of them at a cost of a single byte: (keys from: 00 - ff). But what about next bunch? If each of them is inserted in relation to previous one, the next 255 will occupy the space of ff 01 - ff ff (2 bytes), the next 255: ff ff 01 - ff ff ff (3 bytes). We already use 3 bytes per key and we haven't even inserted 1000 of them. How are we going to fit 1 million?

If we can predetermine how many keys are we going to create, we can spread the key length beforehand to accommodate them all. If we want to insert million of elements, we know that this would require at least 3 bytes (since 2^16 won't fit million entries, but 2^24 can). With that our first batch of 255 keys will use space of 00 00 00 - 00 00 ff, next one 00 01 00 - 00 01 ff, then 00 02 00 - 00 02 ff etc.

As mentioned before, the shortest possible key is already aligned to 8 bytes anyway and can spare 3 bytes for generated key position, so it's enough to fit even 16 mln keys. In practice we don't need that much, so we'll apply one more trick: we'll create subsequent keys in offsets by 2, instead of by 1. This leaves us with enough space for 8 mln rows. It also leaves a spare room for single row to be inserted in-between any two others at a later time if necessary (eg. insert_between(0x01, 0x03) => 0x02), without having to generate the key that would need to grow and potentially spill onto the heap (insert_between(0x01, 0x02) => 0x0101).

Moving fractional keys

Since moving rows/columns is a common operation, we want to support it as well. The issue here is: row/column ids (fractional keys) are used to uniquely identify the cell. They are also used to setup a stable position. Changing the row location means generating a new fractional key, but the cell cannot use it since that would make cell's own address unstable for concurrent edits.

This is not a new problem and it was originally discussed in existing literature. We also did some work on that end in Yrs, but eventually moved (xD) to another solution, one much more similar to what you'll see here.

In order to implement move on fractional index, we need to define two different cases of fractional keys: regular ones (origins) and the destinations, that serve as a new position linked to an origin's identity represented by key. For that our fractional key index will be split into two spaces:

• active: current read-ready position of the key. It stores unmoved keys and move destinations.
• moved: a list of moved and tombstoned keys.

An important note here: we can hit two birds with one stone here and represent key removal as a special case of move operation. Remove essentially becomes a move pointing to a NULL fractional key - represented by all zeros, which is impossible to generate from algorithm perspective, but still can appear in byte representation.

Essentially, each space has a list of entries, each containing 3 fields:

• A fractional key which is an entry's identity itself.
• Timestamp, updated every time entry is (re)moved.
• Moved field, used to point to another linked entry:
  • In active space it points to origin entry that was subject to move.
  • In moved space it points to the destination entry, where it was moved to. For removed keys, it always points to NULL key.

Fractional key generated due to move operation is never used as an identity. It's made only for establishing the order for indexing purposes. If we need entry identity, we trace back to its origin entry instead. This also allows us to flatten the link chain to a single pair: moving an entry multiple times will always move origin only, while tombstoning the entries of corresponding move destinations.

Column-delta run length encoding

Let's say that I've got a csv file that has 1,000,000 rows and 5 columns. It takes ~34MB. The entry schema we introduced above is essentially at least 24B per RowID/ColumnID, so more or less 24MB in fractional keys alone - in-memory, even more if we use i.e. JSON to serialize it.

In practice it's not so hard to see collaborative documents that outweigh user data several times. It's even worse in case of log-based variants that keep history of changes around and require to replay it on the user device. You could run into the situation where a new collaborator needs to fetch hundreds of MB from the network before even reading the first character.

While you could probably get some success by using compression, you can go much further by doing custom formatting, targeting specifically the workload patterns that cause fractional indexes to grow.

First we're going to split our entries into columns by their fields:

1. entry.timestamp: since it represent UNIX epoch timestamp, we're going optimise it in two ways:
   1. We encode first timestamp as is - current UNIX epoch timestamp could fit 6 bytes (varint encoded). Then every next timestamp is zig zag varint delta from the previous entry.
   2. When creating keys in bulk, we assign them the same timestamp. It's a special case (delta 0). If we find it, we branch our logic a little: the next varint describes how many subsequent entries share the same timestamp instead. This way encoding timestamps of 1mln entries created at the same time would only take 10 bytes in total: 6B for the first one, then 4B for remaining 999 999.
2. entry.key: it's a fractional key, but inside it's composed of 2 parts:
   1. Session ID suffix describing peer creating given key. In practice even with millions of entries there would be only a handful of peers who initially created them. We again encode it as session_id * count (4B + varint).
   2. While regular prefix position can only be encoded verbatim, there's a special pattern that we already introduced: subsequent key are can be generated with a given offset, that repeats itself for all keys in a given bulk, as long as there's a space left until the upper bound fractional key. We can encode that offset * count(varint + varint). 
3. entry.moved is also a fractional key, but unlike regular entry.key it quite often can point to NULL entry. We'll also special case for it: whenever a fractional key length is 0 the next varint will describe a count again to mark number of subsequent entries that are using it.

With all of that let's do some math: let's say we want to initialise our doc with 1mln rows, for which we need to generate fractional key identifiers. Their combined serialized formula would be as follows:

• 3B : number of active entries (varint)
• 1B (first entry.key length/discriminator) + 3B (first entry.key position/prefix)
• 1B (discriminator) + 1B (next entry.key delta) + 3B (number of entries diffing by given delta)
• 4B (first entry.key suffix) + 3B (number of entries)
• 6B (first entry.timestamp) + 1B (next entry delta) + 3B (number of entries)
• 1B (first entry.moved length: NULL) + 3B (number of entries)
• 1B: number of (re)moved entries (0 in this case, varint) 

That's roughly 34B to describe 1mln entries. Probably much better than any compression algorithm you'll find.

Virtual fractional keys

The last trick is specific to spreadsheet document design: when creating a sheet, it's empty (no cells initialised). However as a user, you can see it with in a window with a number of predefined rows/columns. Moreover, you can scroll over it infinitely, and the cells still won't be initialised until you edit them.

However this comes with a problem: Imagine that 2 users - Alice and Bob - concurrently want to edit cell A3 of an empty sheet. Alice edits a cell, but since the corresponding rows/columns haven't been created yet, we need to initialise their fractional key IDs automatically (eg. 1:Alice, 2:Alice, 3:Alice ). The same goes for Bob (1:Bob, 2:Bob, 3:Bob). Since both users initialised key with their distinctive identifiers, after sync we'll end up with 6 rows and 2 cells being edited separately (which now will be shifted into positions A5 and A6).

The problem above comes from corresponding duality: we want to distinguish rows inserted (explicitly) by users, even if they were inserted at the same position, but when users are editing the same cell, we don't want it to bear consequences of implicit row creation. In fact, we welcome the conflict over the same cell occurring. But how do determine "the same cell"?

Our solution here is as follows: we create a virtual fractional keys - these are not created explicitly. Instead whenever a user wants to touch a cell at a given index, we precalculate all fractional keys up to that index. In order for these indexes to not differentiate between each users (so that they point the same position after sync), we'll assign them with session ID 0 instead.

The drift between virtual fractional keys would still be possible, since manually inserted rows would shift the generated virtual key position prefix itself. But the solution for that can be inferred from our bulk key generation algorithm: we know that in an empty sheet bulk generated fractional keys have the offset of 2. As long as we know the max number of supported virtual keys we can deterministically tell the keys at a given row position, eg.:

row 1: 01 00 00 02 00 00 00 00
row 2: 01 00 00 04 00 00 00 00
row 3: 01 00 00 06 00 00 00 00
row 4: 01 00 00 08 00 00 00 00
row 5: 01 00 00 0a 00 00 00 00
... 

Even if we want to enlarge computed virtual keys space for already initialised sheet where users explicitly inserted some keys, we still can do it as long as we know how many keys were inserted by users and up to which index (high watermark) we have generated them.

row 1: 01 00 00 02 00 00 00 00
row 2: 01 00 00 03 23 1a cc 03 (inserted by user)
row 3: 01 00 00 04 00 00 00 00
row 4: 01 00 00 06 00 00 00 00 (watermark of virtual keys made so far: 3)

-- create a new virtual key for position 5
row 5: 01 00 00 08 00 00 00 00 (new watermak: 4)
... 

The formula is pretty simple - for explicitly inserted keys I and watermark of generated virtual keys V, if you want to create new virtual key at position X , that'd beyond currently materialised index:

M = X - length(row_index) // how many virtual keys we need to reach X
virt_key(X) = (V + M) * 2

Where 2 is our shift/offset between auto generated keys. Additionally virtual keys generated this way follow our pattern of bulk key generation, that we optimised our custom serialization so well for. 

Summary

In this post we described a bunch of tricks and tips for building fractional index CRDT to support multiple millions of elements. Some of these are specific to a field we're developing this solution for - a collaborative spreadsheets - which required us to use an unique approach.

In the future we're also planning to show some other optimisations targeting usage of fractional keys in different domains, such as collaborative text editing, which was historically the most problematic use case this CRDT.