Improving the Multi-User Experience in Livelymerge

...and now we return to our regularly scheduled programming 😀

Recording of my screen during a Livelymerge session with Dan.

• Dan chases my ellipse with a bug morph. (0:00–0:10)
• I edit Ellipse’s render method while Dan rotates the ellipse; its fill vanishes mid-rotation, as soon as I save the method. (0:15–0:20)
• Dan drops the ellipse on my resized, rotated star. (0:22–0:26)
• I drag the star, with the ellipse on it, while Dan restores the fill; the ellipse changes in my hand. (0:27–0:36)

Everything Dan does shows up on my screen in real time; the document is only updated at the end of each gesture.

Introduction

Every object in Livelymerge lives in an Automerge document. That’s what makes the system persistent and multi-user, but it also means that every property write is, potentially, an Automerge operation… and some writes happen a lot. When you drag a persistent morph across the screen, for example, its position changes on every pointer move: thirty times a second, for the duration of the drag. In our notes on local state and performance, we saw where this leads: bloated documents, a sync server that hates our guts, and a multi-user experience that is nowhere near as lively™ as we would like.

In this note, I (Alex) will describe the idiom we use to avoid this problem. It has two steps:

• keep the rapidly changing state in an ephemeral object — one that lives outside the document — for the duration of the gesture that’s changing it, so that the document stays out of the loop, and
• broadcast the changes as they happen, using Automerge Repo’s ephemeral messages, so that other users can update their copies of those ephemeral objects and see what’s going on.

I’ll also show how we used the same two steps to implement hands, the objects that stand in for each user’s cursor, which everyone wants to see but that don’t belong in the document.

The problem: drags were quite a drag

Here’s what happens when you drag a morph, and how much it used to cost. The morph’s moveBy method updates its position as well as its cached bounds. That’s four numbers: translation.x, translation.y, and the x and y of the bounds’ top-left corner. This means four Automerge ops on every pointer move. Livelymerge runs at 30 frames per second, so a user dragging a morph generates ~120 ops per second, and every single one of them goes into the document’s history forever. A minute of fiddling with the layout of a panel is several thousand operations that nobody will ever want to read back — a big waste.

While the rapid growth of the document is bad, the multi-user experience is even more problematic. Other users see your drag through Automerge’s document sync, which is perfectly capable of delivering changes in real time. But Automerge wasn’t built for the kind of workload we’re giving it during a drag: 100+ operations per second, each of which has to be merged into everyone’s history, persisted by the sync server, and kept for ever and ever. As an optimization, these changes are coalesced into sync rounds rather than sent one by one. That’s a sensible design for state that matters, but it’s completely wrong for a position that’s only relevant for a thirtieth of a second. As a result, other users don’t see your morph glide — they see it jump from one synced position to the next, with a stutter that depends on how busy the server is.

This isn’t a Livelymerge quirk; it’s what happens to any naive Automerge application that makes lots of writes on every frame. The tldraw tool in Patchwork is a good example: whenever you change a shape (e.g., while moving or resizing a rectangle), it writes the change into the document. So it has the same two problems: the document grows really fast, and shapes lurch instead of moving smoothly across your collaborators’ screens. Each user’s cursor, on the other hand, doesn’t have this problem: it feels responsive and moves smoothly across the screen. This is because its position is not stored in the document; rather, it is transmitted via ephemeral messages. When I kept running into sync problems in Livelymerge, Peter suggested that I try using this mechanism, since it had worked well for the cursors in the tldraw tool. So that’s what we did — but we went further, and figured out how to also use it for drags, resizes, rotations, etc.

Step 1: make the state local while it’s changing rapidly

In our note about local state, we introduced ephemeral objects: local objects that live outside the document and are never persisted or synced, but survive from one transaction to the next. We were already using ephemeral objects for things like halos, which should only be visible to and manipulated by the user who created them. Step 1 is to use an ephemeral object to hold the latest version of some persistent state for the duration of a gesture, i.e., a drag, a rotation, a resize: any interaction that changes that state on every pointer move. While the gesture lasts, an ephemeral copy absorbs the writes, and the document only gets one write, with the final value, at the end.

A morph’s transform is stored in a persistent property called _transform. But nobody reads _transform directly; they read transform, which is a getter:

get transform() {
  return this.$transform ?? this._transform;
}

Normally, $transform is null and the getter returns the persistent value. When a gesture begins — e.g., when you press on a morph to drag it, or grab a halo handle — we make a copy of the transform and put it in $transform. Because $transform is a $-property, the copy is an ephemeral object:

beginEphemeralTransform() {
  if (this.$transform != null) return;
  const t = this.transform;
  this.$transform = new SimpleTransform(t.translation.copy(), t.rotation, t.scale.copy());
  // ...and the same for the cached bounds
}

For the rest of the gesture, every read and every write of transform hits the copy. The copy is an ephemeral object, so writes to it never come near the document: virtually free compared to Automerge writes. The methods moveBy and rotateBy, the rendering code, hit-testing — none of them know or care. Then, on release, we write the copy’s values back into the persistent object in place and drop the copy:

commitEphemeralTransform() {
  const et = this.$transform;
  if (et == null) return;
  this.$transform = null;
  const t = this.transform; // the persistent one again
  t.translation.x = et.translation.x;
  t.translation.y = et.translation.y;
  t.rotation = et.rotation;
  t.scale.x = et.scale.x;
  t.scale.y = et.scale.y;
  // ...and the same for the cached bounds
}

Now a drag, no matter how long, is only four writes to the document. These writes happen on pointer-up.

Bounds work the same way (we have $bounds, _bounds, and a bounds getter), and so do the vertex lists of polylines, whose control points you can drag individually. All of this is bracketed by one little pointer-drag protocol on Morph (begin on pointer down, commit on pointer up), so the code for a particular kind of drag only says what to do on each move.

And that would be the end of the story, except for one thing: we’ve made the drag invisible. Your collaborators no longer see 120 operations a second; they see nothing at all, until you let go and the morph “teleports”.

Step 2: broadcast changes as they happen

Step 2 is to use ephemeral messages to notify other users of changes as they happen. A DocHandle has a broadcast method that sends an arbitrary JSON message to every peer that is currently connected to the same document. These messages are relayed by the sync server just like sync messages, but they are not persisted or even guaranteed to arrive. On the other hand, because nothing has to be merged or persisted, they cost only a tiny fraction of what a change to the document costs, and since they aren’t coalesced into sync rounds, they arrive as soon as the network allows.

So, once per frame — at the end of the transaction, after events have been processed — we walk the list of morphs involved in the user’s current gesture and send a single message:

{
  type: "lm-eph-changes",
  objects: [
    { 
      id: "<morph id>",
      props: {
        transform: {
          c: "SimpleTransform",
          translation: { c: "Point", x: 130, y: 70 },
          rotation: 0,
          scale: { c: "Point", x: 1, y: 1 }
        },
        bounds: { c: "Rectangle", ... }
      }
    }
  ]
}

The values of the props are serialized objects with a class tag (c). A peer that receives this message will (i) deserialize the transform and bounds by creating an ephemeral object with the named class’s prototype and copying the fields in — we do this recursively, so the Points in translation and scale also get deserialized — then (ii) write the resulting objects into the morph’s $transform and $bounds properties. As we saw in step 1, the rendering code on the receiving side already favors $transform and $bounds over their non-$ counterparts, so now it will render the morph in the latest state it has received. So your drag will show up on my screen, in (close to) real time, without requiring any writes to the document.

(Note that an inbound message can only ever write $-properties, whose values don’t persist. This is a nice safety guarantee: a malformed or malicious message — from a buggy replica, or from someone who is trying to mess with you — cannot change the document. In the worst case it will result in a morph being drawn in the wrong place on the screen for a moment.)

Who decides when the gesture is over?

The sender never dictates timing; the receiver does. Every overlay it applies — that’s what we call the ephemeral copies a peer installs in a morph’s $transform and $bounds — comes with a lease: if no further message about that morph arrives within a second, the overlay is dropped (its $-properties are set back to null) and the morph snaps back to whatever the document says. This prevents network problems and closed laptops from leaving a ghost morph hanging in the air on everyone else’s screen.

When a drag ends normally, the sender’s final message is flagged end: true, and it is sent after the commit, so it carries the same values that were committed. You might expect the receiver to treat this overlay like any other and simply let its lease run out. Nope! The receiver keeps the end overlay until its own document actually contains the committed values, and only then does it drop the overlay.

We do this because the commit can take some time to arrive: at minimum a network round trip through the sync server, and in practice an unpredictable amount longer. If the overlay were dropped on a fixed deadline, then whenever the commit was late, the morph would snap back to its stale pre-drag position, then jump forward again when the commit finally landed — very janky! Waiting for the document to catch up means the morph will stay put, and the moment the commit lands, the overlay is dropped invisibly.

Hands, at last!

So far we’ve seen two kinds of state. Halos are local: mine, on my screen only. Some morphs are shared and persistent: everyone sees them, and they’re in the document for good. A user’s hand — the Morphic object that represents their cursor — is neither. You want to see where I’m pointing, and I want to see what you’ve picked up, so hands have to be shared. But nobody wants my hand fossilized in the document after I close my laptop, or to pay the 120 ops/sec it would take to keep it up to date while I move the mouse around, so hands must be ephemeral.

With both pieces of the idiom in hand (ba-dum tish!), shared-but-not-persistent state costs almost nothing extra. Each session has exactly one hand. It is created the first time the pointer enters the world and kept in a $-property of the world, which makes it an ephemeral object: it doesn’t live in the document, so moving it is virtually free.

Users broadcast their hands’ state using the same (per-frame) message that we used for the drag overlays, in a new field:

{
  type: "lm-eph-changes",
  objects: [...],
  hand: {
    x: 412,
    y: 288,
    colorIndex: 3,
    name: "Alex",
    carrying: null // or the id of the morph that's being carried
  }
}

A receiver that sees a hand from a session it doesn’t yet know about creates one — a real HandMorph, in the specified color, with a little name tag taken from the sender’s Patchwork contact document — and keeps it in the world’s $hands list, where its own hand is kept. Subsequent messages may move it to a new position.

We track the lifecycle of a hand using the same “lease” idea that we used for the overlays:

• a hand that’s not moving will still send a heartbeat once a second;
• a hand that has been silent for four seconds is removed;
• a session that is closing sends a bye message, and peers who receive this message remove the associated hand right away.

Hands can also carry morphs; in fact, when you drag a morph, that’s your hand carrying it. The way other Morphic implementations do this is to temporarily make the morph that’s being carried a submorph of the hand, so that it goes wherever the hand goes. But a Livelymerge hand is an ephemeral morph, which means it can only have ephemeral submorphs: if we were to set a persistent morph’s owner property to the hand, the next garbage collection would dutifully promote the hand into the document, which is not what we want. (This is one of the gotchas from the local state note.) And that’s not the only problem. If the person who’s doing the carrying were to suddenly lose their network connection, the morph they were carrying would be inside a hand that no longer exists on anyone’s screen. Where would it go?

So a morph that’s being carried stays right where it is in the scene graph, and we move it by making changes to its ephemeral transform, as described in the previous sections. The carrying field holds the id of the morph the hand is carrying, and everyone who receives it tints that morph’s drop shadow with the carrier’s color — the effect Dan mentioned in the previous note. And if the carrying hand does disappear, no problem: the overlay lapses, and the morph is right back where it started.

The video at the top of this note shows all of these mechanisms in action. What you see is my screen in a shared session with Dan. See how smoothly his changes, which are being streamed via ephemeral messages, show up on my end? Yeah, you do!!

The real price of all this stuff

I said that our idiom costs “almost nothing extra,” and performance-wise that’s true: the document doesn’t grow, and each user sends at most one small ephemeral message per frame. Definitely a win! But the programmer had to pay the price, albeit a modest one. Every fast-changing thing that we wanted to stream required the following code changes:

• splitting a persistent property foo into _foo and $foo
• adding a getter for foo that favors $foo when it’s not null
• adding a pair of begin and commit methods
  (begin makes a deep copy of the state, and commit writes it back, in place, i.e., property by property)

Hands required a more elaborate version of the overlay’s lifecycle: create on first sight, heartbeat, time out, say goodbye. A morph’s transform already exists in everyone’s document, so an overlay just borrows it, but a hand exists nowhere until a message announces it, so peers have to create it and, eventually, get rid of it.

None of this stuff is specific to transforms or hands, but it does come in two flavors:

• Splitting properties and writing begin/commit pairs implement something that’s missing in Livelymerge: state that lives in the document but is temporarily shared-but-not-persisted, for the duration of a gesture. It would be nice to have an abstraction for this, and eliminate the need for all this boilerplate.
• The lifecycle code we wrote for hands implements something else that’s missing: objects that are shared but never persisted. They have no home in the document, so nothing in the document will ever tell peers to create or remove them; the lifecycle has to do that. We didn’t mind writing it once, but if we end up with several kinds of such objects, we’ll want an abstraction for this, too.

Coming Up

Dan and I have been meeting regularly with Gilad Bracha to talk about the design aspects of multi-user programming kernels like Livelymerge and Newspeak. These conversations have been very interesting, and I plan to document some of the ideas and questions that are coming up as Livelymerge lab notes.

We have also started to experiment with the integration of AI into Livelymerge. (Gilad has also been exploring AI in Newspeak.) This has some overlap with the topic above. For example, does it make sense to think of the agent as just another user? I think so, and we’ll probably want support for branching so that several changes can be made and tested before they’re committed (atomically, natch) to the document that we’re all living in.

Stay tuned!