Hacker News Reader

Hi! Thanks for the thoughtful question.

>List operations just work:

Fair point. Will change. What I really meant here was "(Many) list operations just work" (just like above I said "all kinds of things just work".

> All updates reach the server at the same time. What is the solution to that? Timestamps? Fallback to LLW?

There are a number of issues you might be pointing out, and I'm not sure which one you mean.

In general, you can't use list indexes as identifiers for edit/delete in Reflect because they aren't stable. That's why in this example I commented to use the item itself (if atomic) or more likely a stable ID: https://i.imgur.com/IKzmf0q.png

There is also the potential issue of User C's inserts getting deleted. This seems like a problem at first, but in a realtime collaborative context, nothing can fix this. User C's insert can land just before User A or B's delete. In this case, sync would be correct to delete user C's insert, no matter the protocol. But User C might still be sad. From her perspective, she just wrote something and it got deleted. This is the nature of two humans working in the same place at the same time and potentially having different intentions. For these problems, undo and presence indicators go a long way to avoid these problems through human/social mechanisms.

>nothing can fix this

Exactly.

>For these problems, undo and presence indicators go a long way to avoid these problems through human/social mechanisms.

x1,000 to this. This guy builds. That's exactly my takeaway as well from years working on this; provide a solid (by that I mean clearly defined) deterministic algo, and solve the rest w/ UX.

If you actually look at how people use most multiplayer editing tools they tend to avoid conflicts anyway. It’s extremely painful to have two people editing the same sentence in Google Docs let alone more than that even if it sort of works. Collaboration tends to be negotiated so you end up with I-go-you-go, reviews and other patterns forming around the use of the tools. People can also see and resolve conflicts in real-time.

That said this sort of reconciliation can be extremely painful if people are working separately offline for any length of time as arbitrarily resolving many conflicts doesn’t necessarily result in coherent results. But as I understand it that’s also an issue for other ways of solving the issue as well.

Another missing piece is signalling failure. For example two people trying to fill the last slot of a limited resource. Having to infer from the state that comes back whether your operation succeeded or not is not a fun way to write multiplayer code.

This points towards a big challenge that I think gets overlooked way too often. A lot of these sync libraries/frameworks claim to solve for both real-time interaction, and local-first, sync when you reconnect. But the UX needs are wildly different.

For the former you want (as mentioned) good presence info and undo. For the latter you (sometimes) want explicitly flagged conflicts and manual resolution, like we have in git etc.

With the Replicache/Reflect model, you could actually handle both approaches. Might not be easy but the model can support it.

If a client is offline for a while and makes a bunch of edits, would rebasing many thousands of mutations not be a major performance issue? (For example: if complexity is O(n) per edit, as is often the case with string insertions, the process might hang for a long time.)

It seems to me that maybe saying that CRDTs are "good for one particular problem," whereas Reflect can do anything, is a bit misleading? Reflect is eventually consistent, but if you want e.g. string mutations to make sense, you still need to de facto model your text as a CRDT. (Unique IDs per letter, tombstones, etc.) Otherwise, you'll end up with garbled text.

I didn't mean to say that Reflect can do _anything_. We do think it's a general model that ends up working well for very many things in practice.

You don’t even need to involve deletes; if all of these happen “simultaneously”:

  - client A appends “a” to list L
  - client B appends “b” to list L
  - client C appends “c” to list L

the server will arbitrarily apply the appends in some order, and then send the result back to the clients. But, each of the clients has applied its append locally and is showing those results until it gets different information from the server, so the next time step might be

  - client A thinks L is [“a”]
  - client B thinks L is [“b”]
  - client C thinks L is [“c”]
  - server sends state event to clients saying that L is [“c”,”b”,”a”]

Then when the clients receive the state from the server, I guess they all discard their pending mutations and use the state from the server as their state of the world. But what if each of the three appends results in that client winning the game if their mutation gets applied first? Do all the clients display “you win” for 300ms while waiting for the server’s update?

You modified the operations, I specifically chose a scenario where User C (in my example) introduces an undecidable situation. Appends are trivial to solve.

>If your answer is like "we just send them the whole array again", this breaks the transactional model (x2).

You also did that, whoops.

True. I was thinking of a simpler criticism that, if it held, would also make Reflect less useful. aboodman replied in the sibling that (of course) they thought of that, so my criticism doesn't apply.

We have the "game-winning" scenario on the reflect.net homepage right now: https://reflect.net/. It's a puzzle and when the last piece is placed, it shows a celebration and the puzzle resets moments later. But we only want that logic to run once. We can't do this client-side because there are many people and we'd end up having to choose a leader or something. This is the same exact situation as wanting to show in the UI who won (who placed the last piece) and only wanting to do that once.

Reflect has first-class support for this kind of situation by allowing mutators to run special code server-side. I talk about this a bit here:

https://rocicorp.dev/blog/ready-player-two#server-authority

You can use the same mechanism to have a branch in the code that places the piece that only runs server-side and chooses the winner.

Most of these systems do deletes with tombstones. Then you can safely insert after/inbetween deleted items.

Is the solution to that,

a) [1, 5]

or

b) [1, <new element>, 5]

?

By your example, 5 was marked as deleted, so it would just be [1, <new element>].

Most likely this would be implemented with a single mutator for each element. But if you implemented a "range delete", then it would depend on what the order of arrival was. Notably, the server has to sequence actions somehow, so there isn't going to be an issue of "all actions arriving at the same time". If C arrived last in that case, the new element would be there. But if C arrived first, you'd just be left with [1].

Whoops, you're right,

Is the solution to that,

a) [1]

or

b) [1, <new element>]

?

>Notably, the server has to sequence actions somehow [...]

Yes, that's my whole point, you have to fallback to something like LLW, and then it's over for the transactional model :P.

Edit: Btw, I'm not trying to be the snarky, pessimistic dude. This kind of models are really interesting and I love working with them. I am just trying to illustrate how things could go awry without much complexity involved.

No, the server is going to process the actions in a single queue. So again, it's whatever action arrives first.

Then it's LLW and you're no longer playing this game.

I don't know what LLW means, but you seem fixated on the acronym. It's just first come, first serve transaction ordering from the world I come from.

Perhaps it's a typo/braino for LWW, Last Write Wins.

It is! Thanks!

In a collaborative application the server could resolve the three operations in any order. The three users observe the result, realize that they are operating on the same data at the same moment and messed with the state. Then they fix it. Think about editing a document.

If they can't see each other working on the data together they could be surprised but they could eventually fix the data to the desired state.

If they don't check the result or can't check the result, the state won't be OK. However it's not what probably happens in interactive apps like collaborative editing or games.