I want to welcome now Bartosch, who will be talking about taming your timing, your YGS documents.
Please welcome him with the round of applause.
Thank you very much.
Thank you.
Okay, so first, we'll be talking about how YGS operates on the data that you are passing to it.
What patterns and anti patterns come out of it, because from what you might have known,
or not know, YGS is one of the most popular collaborative libraries for writing collaborative apps and mostly optimized for writing collaborative text editors.
So this is like a standard for YGS.
The thing that we are optimizing for collaborative text editors, and they are used for example in Evernote by now.
If you are using Jupyter Notebooks in collaborative mode, you are using Quires to work with mine.
If you are using, there are, let's say, plenty of notion alternatives, right?
In the open source or in the VCFM companies, and quite a few of them are actually using Quires or Wires under the hood for the collaborative features.
And from this experiences, we came up with different and weird ways, weird for us as creators of patterns that people are using for working with YGS documents, and we decided to address it on this talk.
So yeah.
And for first, on the, oh, can you see the left one?
Yeah, okay. So on the left there is a YGS, the standard YGS API, let's say, on the right is the Wires.
So last one, it's mimicking in the terms of behavior and fully compatible in the terms of binary format.
So you can work between Wires and Wires interchangeably.
And so with that tip number one, keep Wires sequential as long as possible.
So what does it mean sequential reading?
And in order to deep dive into it, we need to explain a little bit about how YGS and how Wires are storing your update and attaching metadata for a possible contribution.
Several people are writing in the same place, for example, we don't want them to override each other character style typing, right? And things like that.
So first, this is like a core element of YGS and Wires is called block or item.
And all of the updates that you are making, land in the YGS docs are wrapped in this block structure.
It has its identifier, it's relationship to other blocks when you are typing, inserting something at position, let's say, and actually we are storing information about the identifier of the element on the position and minus one and plus one.
So everything happens in your relationship because indexes are relative to the person who is looking at them and what is stored there changes over time.
And we are using those IDs to basically fix the position in time and in space as a relationship between different items that you are putting in.
So there is also the identifier of the collection, identifier of how to set end trends and trends of the key value map because YGS also supports key value maps.
And some of the extra metadata in there is finally your update and the thing is that your update can be quite big because of that because there is a lot of fields to that, right?
And when you are typing characters, you are inserting them individually in your document basically.
And every time you are inserting a character, we need to attach this metadata to it, right?
So there's a lot of fields that have some weight in memory and on this if you are avoiding to store them and putting them for every single character is expensive, right?
So what we are doing is basically operation called merging and the thing is that as long as you don't change the cursor position, you are typing one character after another, basically you are putting them in the relationship.
That you know, we are preserving this sequential information basically and like here.
A2 knows that it's left-wise a1.
So we know that if those two blocks were next to each other, that they were inserted after each other basically.
And once this is done, we can basically scratch them together into a single block, which now holds two values A and B.
And the amount of metadata that we stored is basically the same as if there was a single item because metadata stored per single item.
So technically those two notations are equivalent to each other, just one of them is compressed for another one is not.
Now, how can we keep this sequential, this ability to merge those blocks together?
First, they need to happen in the same session because every time you create a new dog by default, it's creating a client ID.
And it's very important that no-to-processes write under the same client ID at the same time because then we have duplicate IDs having different elements starts under them and this would cause the problems.
So we need to keep in mind that those client IDs needs to be used by one process at the time, which is hard for the browsers because this means that basically for every time you are opening the document in the new browser tab, you are generating a client ID.
Well, you can basically recycle the same client ID over and over, which is why wires is so great also.
Another is that they need to happen for the same collection because those marriages happen within the same collection boundaries.
Another, if you are using quiet map, they need to happen in the same key value entry.
So basically updating quantity value than another key value is similar to changing the course of position. So we are breaking this functionality of those updates basically and I will explain it a little bit more later on.
And yeah, if you are doing this on the text, as long as you don't move the course of position and start typing one after another, we can merge those together.
And also means that you can push more than one character at the time, right? You can basically copy paste the entire book and put it as a plain text and it counts as a single block with the single set of metadata it basically.
And also it needs to start the same type of object, which is why I called copy paste as a plain text because if you copy paste as a formatted text, then it will be broken into parts with the formatting attributes in between.
So this is also pretty important. So for how does this sequential it behaves? And now let's see an example. We are creating a wide map.
In one example, we are basically updating entries A and B 100,000 times. On the other, we are updating them.
First, A 10,000 times, then B 10,000 times. And let's encode those documents, see how big they are. So first one is two megabytes, basically. Second one is 77 bytes. So where the difference comes from? Well, first of all.
There's also a special size, because YGL is also to encode in one of two variants. Version V2 is not used by default by any of the default attachments to YGS. So I mean, in the persistence providers or network providers, but you can use it. And in this case, even this big sequential update would be still 74 bytes.
Because of how well YGS can compress the information in the V2 settings. However, here V2 is a little bit bigger, 79 bytes. So basically the role of the amp is used V1 for incremental updates, like single characters, small packages of the packages of data.
And for big chunk documents like you know, hold the constraint, V2 is quite a bit better. So the difference, where are the difference comes from? Right? Those 77 bytes versus two megabytes.
So how map sequential it works when it works as intended, right? So we are updating the same entrance over and over again. We are basically in YGS, basically every Y map is a set of lists, I would say, where the value is the last element of the list in the given entry.
So when we are inserting a new element, then we are inserting a new element again. And we are deleting the previous entry, and the previous value of that entry.
And there is a thing, YGS doesn't have really have updates, it has inserts, you can add it or insert the block or delete it. Once it's deleted, you can no longer access it with some caveys that are possible.
So when you are, again, inserting the next element, you'll see that we are adding a next block, delete the previous one, and as we can see, N0 and N1 are the block IDs of deleted elements. They are sequential, happening next after each other, so we can merge them together in a single block.
Okay. And this way, we can basically squash those hundreds of thousands of updates into several box.
However, when we are inserting elements, you know, one after another to different entries, we are breaking the sequentiality, so we can no longer preserve the merge those updates together, and we need to basically save them one by one.
This is where those two megabytes come from. So one of the ways to solve it, honestly, if you don't need to store the values on, you know, resolve conflicts on entry by entry basis, it's better to just save entire JavaScript objects or JSON objects.
And this way, our output size is 59 bytes, which is even lower than the sequential case previously, as long as you don't need to update, update A and B in collaborate manner, right?
Now, tip number two, not every object needs to be collaborative, going back to the same idea. For example, if you have let's say we are using quite just update the very vehicle position, right? So we are representing the position as a Y map with latitude and longitude, and two clients are updating it concurrently.
The problem is that if two of them are updating concurrently, and we cross sync them with one another, what we can end with is a consistent state, but invalid state, because we are basically resolving conflicts on entry by entry basis, right?
So one client might win on another and one entry, another might win on another entry, producing the result that is not satisfactorable, not satisfactionary for us. So the idea here is that we don't use Y map, more Y maps when we don't need it, it's just better to use a simple JSON objects, because JSON objects are treated as a single entry, and we resolve them as a, basically atomic value conflict, right? So this is another.
So basically, this is common pattern when people are building something like a crad application. So what they are doing, well, there is a user form that we can put into JSON, we update that data from JSON, put it back again, by basically saving all of the JSON data field by field in the YGS, Y map let's say, right?
The thing is that every time you are writing something to Y map, you aren't creating a new block, even if the value that was the previously is the same.
It's a way of saying, I really, really want this to have this value in case of concurrent conflicts that I can still fight with my value, basically, value from another person.
But the problem is that we are writing to two and three entries while only one was changed, and this means that we also breaking sequentiality.
So we are basically blowing up the document size by inserting the same value over and over again.
So of course, better to only write the values that change, never write the values that didn't change.
But for the collections, like why maps can't erase each other. So this is a problem that most people run into when they are saying, I've made applications in KJS, and now I've made some changes here and here, and my data disappeared, the sync was broken, I've lost my data, right?
Let's say that we have following them, we are having a map of users, trying to get a map representing a person and Alice, this is collaborative map, but it could not exist because it was not initialized here.
So if it doesn't exist, we create a new Y map, insert data from Alice, insert it into a user's Y map, parent Y map, then fill it with some data, right?
Then let's say we have two documents that represent concurrent update. On one, we are basically adding age equal 28, on another one, we are adding email, we are applying the update,
syncing those documents together, and the result is that on one of them, they both have the same value, but they both don't have email value, and why does it happen?
Basically, why JS has two levels of types, the replayable types created by the under the document itself are identified by their string name that you are giving them, in this case it's users.
But if you are inserting Y maps under the hood, then under those collections, they are getting a block ID as they are identifier, and this means that on every insert and you block ID is created,
and this Y map, even though it in our heads represents the same element, the same entity, on the wires side or on the YJ side, there are two different elements, and as such they are basically competing with each other.
So when the configuration happens, we see that under the Alice, we have one object that has this ID, another object that has this ID, one of those objects will win, and one of those objects will preserve the value.
If the ID is the same, because we synchronized it first before inserting something from another client, then all it's fine, really.
So, root level types are mostly, since we have a little bit of time, they are mostly for things like schema, if you are database developers think, like tables in SQL, right?
So, the value that is expected to be there already, and we are working with our application logic out against that schema.
Well, unless it types, they are just entities, it's better to have if you have the possibility of conflict, you need to have some person that is the first initializer of that element, and then, for example, refer to it by its unique ID, for example, right?
The ID that you have control over in this case, something like U, ID, or any kind of ID that has sense in your business logic, I say.
But, why did we take that peculiar choice? Like, why does the Y maps can delete each other? It's not like a very safe to lose user data, but there is a reason for that, and one is that, why types can be used to basically stabilize data?
Let's say, this is an example of two people, three people are really collaborating with each other and doing the changes in the document, but one of them is offline, right?
And there comes a time for a peer review, they are reviewing the document, those changes are fine, okay? The document is accepted, this is now we want to freeze the stay of the document, but then the third person comes in after a long period of being offline, and they also are editing this document and they didn't,
you know, that it was peer reviewed already, right? But anyway, their changes are jumping into it, right? So this is a problem, and basically using a new Y document can be used to optimize that in the moment.
And the other is garbage collection, because the biggest problem with document updates is that when we are deleting this data, a garbage starts to pile up, and it is present in document state,
as we've seen before with those two megabyte updates, right? So to close, YGS has three different ways of representing deleted data.
One is basically a bit marker that is used when you turn garbage collection off in YGS document, when you are creating it. It is necessary for things like snapshotting time travel debugging, sort of time travel, and on the riddle manager.
You can undo and redo operations, because we need that data, we cannot just delete it. Another one, the default one, is we are deleting the user data, just keeping information, how many elements were in there,
but we still keep the metadata around, because one person can delete a fragment of text, but two other people could possibly insert something in that deleted range,
and there are still subject of context, so we still need this metadata to resolve that context.
And the third one is when the parent collection is deleted, it's deleted forever basically, because once something, some element is deleted, you can no longer access it, so you can access basically, you can create a new one, of course, and put on top of it.
But this is another collection, but once the collection is deleted, all of the blogs that were referring to were also deleted, no longer accessible, there is no need for conflict resolution, and we can just put a very simple, very small place holder for it.
And you can use it, this is like the final slide, so you can use it basically to stabilize your data.
So we are doing some, for example, here we are doing a thousandth of, or insert and delete operations in random positions.
This is the string that I've generated from it. I can put it into JSON, which basically returns as string, a plain string.
I can then code the document as an update for this string, this update is six thousand bytes, because of those thousands of operations that we had to store, and they were in random positions, so probably no merge happened.
But you can create a new ytext object, which is yj's element used for each text as you think, and initialize it with this data from the previous text.
Now, anything that happened in the concurrent updates in between those will be erased, because ytext, text to will erase text, and all of the updates that happened on the original text, which is bad, but once it's, but if you are willing to accept it, because you want to have a stable version of the document, then you can encode it again, and now it counts as a single string of characters, which after our update and coding,
has 87 bytes in the document size, because we get rid of the previous text, got rid of all of the blocks, and all of the metadata that were associated with it, so we don't longer need those information that was basically six kilobytes long, right?
So that was very fast, but I hope that you managed to keep on with me.
So if you want those are the references, I'm writing mostly about wires, because this is my field, but if you want to see how yj's contribution work,
and this is like a tutorial, so you can write it yourself, this is the last link.
If you are interested in more in the details about how yj's and wires works under the hood, there are two different things, and how to write quite perform,
one CSV table, depending on how big CSVs we are talking about, but this one shows that it can work up to the certain points for sure.
So thank you.
Thank you so much, Barters, for your talk.
We're going to take questions in the room on the net, nothing. Please raise your hand if you want to ask.
It's a moment, or if everything was clear, we don't take questions.
Okay, then.
Sorry, originally this talk was said for like an hour, and slower and much more on the better pace than that.
No, really, we've very often used a much, I wouldn't throw much about why I'm trying to do that.
One burial challenge that we had a lot of work to do, I see previous problems.
You know, we didn't know why, once I write in it.
You play a big life on dinner, all your sort of fitted in it.
And we talk about it every day, and we talk in this day.
She can do it often, come and see each other today.
Because it can prevent updates being routed to the wrong object that tends to be in replace.
It's also desirable sometimes.
And I wonder if you've given any thought to, like, whether you could tune the semantics better or give different kinds of knobs,
that is the right thing for many years.
And you know, as a conversation, we had all the time.
I'm curious if you can give up that tip.
So what I was presenting here is based on the experiences I have with different people in different companies,
right?
And it turns out that more often people, you know, they are not interested in things like internal,
of facilities, as long as they are working.
As they expect, the problems that they usually don't expect that.
And this is why I was describing this problem on the first place.
I think that this is more common case when people are in certain things to the same place.
And they expect that, you know, the things will magically resolve themselves without losing their data.
Which is not what happens in wages.
From what they know, it doesn't also happen in the lower role.
I think that it also doesn't happen in automatic.
But...
What...
How much does it retain the whole history?
Is that everything?
So by default, you still have the data?
Yeah.
But if...
Yeah.
This is the visibility challenge.
So the same goes here.
If you will turn off the G.C.
And you are willing to store the whole history around.
Then you can go back to those previous variants of the document, right?
But...
You know, you cannot conduct a convict resolution on them, on there.
Right now, with the latest version of YGS that is still in the working,
there is possibility to basically build data in YGS.
And those data can be working like a G.C.
Basically, right?
So you can re-base.
You can re-base the changes onto some alternative history of updates,
which includes cherry picking the changes from YMAP that was deleted
onto YMAP that won the convict resolution.
Very cool.
Yeah.
Let's see.
Yeah.
Thanks.
Any other question in the room?
Is your time?
Yeah.
Doctor?
You won't have it again.
You're the one.
So we can wrap up.
Thank you very much.
Thanks.
Thank you.