Chapter 6: StructStore #

In the previous chapter, Snapshot, we learned that a snapshot contains a miniature StructStore. But we didn’t open that door and look inside. Now it’s time to visit the warehouse.

Imagine Alice and Bob are syncing a shared todo list. Alice adds "learn Yjs" to the list, then sends Bob an update. When Bob’s Doc receives that update, it needs a place to unpack the incoming pieces. That place is the StructStore.

The StructStore is the internal warehouse that holds all low-level structs of a document. These structs include Items, GC markers, and Skip entries. You can imagine it as a giant, sorted shelf of building blocks. When a peer sends an update, the StructStore inserts or modifies blocks so the document can reconstruct its current state. It is one of the core data structures Yjs uses to remain efficient.

What problem does StructStore solve? #

Let’s use a concrete example.

Alice has a Doc with a todo array:

const aliceDoc = new Y.Doc()
const todo = aliceDoc.getArray('todo')
todo.push(['learn Yjs'])

When Alice makes this change, Yjs creates tiny structs behind the scenes. She then sends her document state to Bob:

const update = Y.encodeStateAsUpdate(aliceDoc)

Bob has his own empty Doc:

const bobDoc = new Y.Doc()
Y.applyUpdate(bobDoc, update)

What happens inside Bob’s Doc when he applies that update?

The update contains encoded structs. Bob’s Doc decodes the bytes and places the structs into Bob’s StructStore. Once the structs are in the warehouse, Yjs can walk through them and rebuild the shared array:

console.log(bobDoc.getArray('todo').toArray())
// ['learn Yjs']

The StructStore is the reason Yjs can unpack, organize, and rebuild collaborative data so quickly.

Key Concept: Structs are tiny building blocks #

A document is not stored as one big JavaScript object. Instead, it is stored as many small pieces called structs.

There are three kinds of structs you should know about:

Think of a document like a Lego model. Each Lego brick is a struct. Some bricks have color and form, like Items. Some are empty spacers, like Skip entries. Some are markers showing where a brick used to be, like GC markers.

When you edit a document, Yjs creates new structs and places them into the StructStore.

const doc = new Y.Doc()
const todo = doc.getArray('todo')
todo.push(['learn Yjs'])

After that code runs, doc.store.clients contains a Map with one shelf for Alice’s client ID, and that shelf has one Item struct.

// Only for exploring internals, not for app code!
console.log(doc.store.clients)
// Map(1) { 123456 => [ Item ] }

The exact numbers and names will be different, but the idea is there: the StructStore is already working.

Key Concept: The StructStore is a sorted shelf #

The StructStore sorts its structs carefully.

Imagine a library. Every bookshelf is labeled with a client ID. On each shelf, books are arranged by clock order. A struct’s position is its ID, which is made of two parts:

{
  id: { client: 7, clock: 0 },
  length: 1,
  content: 'learn Yjs'
}

• client says which device created the struct.
• clock says where it belongs in that device’s history.
• length says how many “slots” the struct occupies.

Yjs keeps structs sorted by clock on each client’s shelf. This makes finding a struct very fast, almost like looking up a word in a dictionary.

const doc = new Y.Doc()
const todo = doc.getArray('todo')
todo.push(['learn Yjs'])

console.log(doc.store)
// StructStore {
//   clients: Map(1) { 123456 => [ Item ] }
// }

Again, this is only for understanding. In a real app, you don’t need to touch the StructStore directly.

Key Concept: Updates bring new structs into the store #

When Bob applies Alice’s update, here is what happens at a high level:

1. The update bytes arrive.
2. Yjs decodes the bytes back into structs.
3. Yjs asks the StructStore to integrate each struct.
4. The StructStore finds the correct shelf and the correct position.
5. The struct is inserted, or an existing struct is modified, so the document stays consistent.

Here is a picture of that flow:

Bob never sees the raw structs. His Doc handles all the warehouse work for him.

Under the hood: how StructStore works #

The real StructStore class lives in src/utils/StructStore.js.

Here is a simplified version of its constructor:

// simplified from src/utils/StructStore.js
class StructStore {
  constructor() {
    // each client id maps to a sorted array of structs
    this.clients = new Map()
  }
}

That’s not a lot of code, but the Map is the core of the whole warehouse. The keys are client IDs, and the values are arrays of structs.

When a new struct arrives, Yjs needs to insert it into the correct array at the correct position:

// simplified idea: find the right shelf position
function insertStruct(store, struct) {
  const shelf = store.clients.get(struct.id.client)
  const pos = lowerBound(shelf, struct.id.clock)
  shelf.splice(pos, 0, struct)
}

lowerBound is a helper that finds the first place where a struct with that clock should go. This is much faster than scanning the whole shelf.

The real integrate method looks more like this:

// simplified from src/utils/StructStore.js
integrate(struct) {
  const client = struct.id.client
  if (!this.clients.has(client)) {
    this.clients.set(client, [])
  }
  const shelf = this.clients.get(client)
  const pos = lowerBound(shelf, struct.id.clock)
  shelf.splice(pos, 0, struct)
}

That inserts the struct. But there is one more important problem: what if a new struct overlaps an existing struct?

What happens when structs overlap? #

Sometimes an incoming struct needs to fit inside a space that is already occupied.

Imagine a shelf for client 7 looks like this:

Before: [Item(clock 0, len 5)]
Incoming: Item(clock 2, len 1)
After:  [Item(clock 0, len 2), Item(clock 2, len 1), Item(clock 3, len 2)]

Yjs splits the old struct into two pieces so the new struct can fit in the middle. This is how Yjs can merge changes from different peers without losing information.

The real integration code handles these splits carefully. For a beginner, the important thing is:

• Structs are sorted.
• Incoming structs are inserted in order.
• Overlapping structs are split so the document can be rebuilt correctly.

Yjs also handles GC and Skip structs during integration. The logic is similar, but the structs have different purposes.

// pseudo-code inside StructStore.integrate
if (struct instanceof Item) {
  // store actual content
} else if (struct instanceof GC) {
  // remember that this range is garbage
} else if (struct instanceof Skip) {
  // reserve space with no content
}

You will meet Item and its cousins in the next chapter.

Snapshot connection #

In Snapshot, we saw that a snapshot contains a miniature StructStore. That is exactly the same kind of warehouse, but frozen in time.

When Yjs creates a snapshot, it captures the current shelves of the StructStore. When you restore a snapshot, Yjs creates a new StructStore from those saved shelves.

So if you understand the StructStore, you also understand the quiet heart of snapshots.

Use case: applying Alice’s update to Bob’s Doc #

Let’s put everything together with the todo list example.

Alice inserts "learn Yjs":

const aliceDoc = new Y.Doc()
const aliceTodo = aliceDoc.getArray('todo')
aliceTodo.push(['learn Yjs'])

Alice sends an update to Bob:

const update = Y.encodeStateAsUpdate(aliceDoc)

Bob applies the update:

const bobDoc = new Y.Doc()
Y.applyUpdate(bobDoc, update)

When Bob calls Y.applyUpdate, Yjs decodes the update, creates the structs, and inserts them into Bob’s StructStore. Bob’s shared array can then be constructed from those structs:

console.log(bobDoc.getArray('todo').toArray())
// ['learn Yjs']

The update was just a suitcase of packed structs. Bob’s StructStore was the shelf where those structs found their correct home.

Common beginner questions #

Can I use StructStore directly? #

You usually don’t need to. Transactions, updates, and shared types all use the StructStore for you. It is an internal implementation detail, like the engine of a car. You can drive the car without opening the hood.

Do I need to understand GC and Skip right now? #

No. But it helps to know they exist. When you see them in the source code, you won’t be confused. They are just two more kinds of structs that live in the same warehouse.

Is StructStore the same as the document state? #

It is the low-level memory of the document state. But the document also has shared types and transactions that build on top of that memory. You can think of the StructStore as the foundation.

Conclusion #

The StructStore is the warehouse where every piece of a Yjs document lives.

• It stores structs called Item, GC, and Skip.
• It keeps structs sorted by client ID and clock.
• It integrates incoming updates by inserting or splitting structs.
• Transactions and shared types use it behind the scenes.
• Snapshots use it as a frozen copy of the document.

Now that we know the warehouse, it’s time to look closely at the most important struct that lives inside it: the Item.

Next up: Item / AbstractStruct

Generated by AI Codebase Knowledge Builder