Logootish

This assumes that you've read the section in "Home" and are familiar with Logoot. If you want the documentation for the logootish-js package, you can check out the JSDoc here. However, I would urge you to read this before reading the JSDoc. Finally, these concepts are really weird to wrap your head around so it's normal to be confused -- I still find myself having to re-think a lot!

Terminology

Out of context, the abstract terminology may not make much sense. I'd recommend that you skim the terminology section first and scroll back to it when reading the later sections of this explanation.

• Atom, character -- The two terms are used somewhat interchangeably. This is the smallest segment of text that cannot be split into smaller pieces. In this implementation, characters and atoms are the same thing, but in other Logoot implementations, lines could be used as atoms, for example. The downside to this would be that you couldn't insert text in the middle of the line. So for this algorithm, characters are used as atoms. At the moment, I'm planning modifications to logootish-js to allow array indexes to be used as atoms, but in the explanation below, I'll be using single characters because it's much easier to explain that way
• Position -- A unique value for the atom that specifies its position
  • These positions must be able to be ordered in a set (I will explain ordering a bit later)
  • The current implementation used for a position is an array of numbers in a class used to provide utility functions. Examples of positions in text format are [0] or [0,0] or [1,2,3]
  • For any two positions, another position must be able to be created between them. If just integers are used, this poses a problem, since there's nothing between 0 and 1, for example. The solution to this is to add another integer to the array to make the position more specific
• Levels -- The number of elements in the position array. For example, [0] would have 1 level. Be careful though! When getting the variable levels from a LogootPosition, 0 represents one level, not 1 like you would expect from an array length. That way, myposition.level(myposition.levels) will return the lowest level.
• Vector Clock, rclk -- Imagine that you first insert a single atom at a particular position and then remove it to insert a different letter. If these edits came out of order, how would the client know that the second letter should be used and not removed? The solution is the vector clock, which is named rclk in the code and in events. The vector clock is incremented with every removal
• Events -- This refers to the Matrix events actually sent in JSON form. Since it would be inefficient to have one event per insertion or removal, any length properties used are simply added on to the lowest level to find the end position. For example, if I insert hi at [0,1,0], the message would have a start position of [0,1,0] and the body of hi. The client would then figure out that the end position, or the position where the next node would be, is [0,1,2]
• Node -- Since text is sent in longer chunks, to save on RAM, it is stored in longer chunks as well. A single segment spanning between two positions with (and this is key!) no nodes in the middle of it is a single node. Any nodes placed in the middle must cause the parent node to be split in two. (Though I will explain it in more detail later, this is one of the many jobs of the _mergeNode function) The reason for the necessary split is because the binary search tree must not have overlap to find nodes
• Document -- A term used to refer to a single client's view of a collaboration room. While 'room' is used to refer to the event DAG as seen by the servers, 'Document' refers to the specific view seen by the clients. Since this algorithm sacrifices Consistency for Availability and Partition Tolerance (https://en.wikipedia.org/wiki/CAP_theorem), these views are allowed to diverge. They are, however, eventually consistent, just like Matrix DAGs

Insertions

These are the simplest type of modification. Let's assume that our document looks like acd, where the a has the position of [0] and the c and d have the positions [2] and [3], respectively. If b is inserted between the a and c, it's easy to find a position in between their positions. Since a has the position [0] and c has the position [2], the position [1] is conveniently located right between them. So the new b can be given the position [1].

The final document would be represented like this:

[0]     - 'a'
[1]     - 'b'
[2]-[3] - 'cd'

Of course, usually it is never that easy. Let's assume that we have the same acd as before, but this time the positions are [0], [1] and [2], respectively. Now, we try to insert b between a and c, as before. This time, we must create a new position between [0] and [1] by adding a new level. Remember that the node with more levels comes first, so the new position would be [1,0]. It seems counter-intuitive to have [1,0] come before [1], but it greatly simplifies the code in the compare functions.

The final document would be represented like this:

[0]     - 'a'
[1,0]   - 'b'
[1]-[2] - 'cd'

Removals

Obviously, having text that can only be added is not super useful. The solution is another type of event: The removal event. Removal events have an array of removals. This is because one region of text that is continuous on the user's screen may have positions are not continuous. In order to reduce the number of events sent, multiple different removals can be packed into one event. Removals function pretty much like you'd expect them to: An array of removals has elements with both a start position and length. Like additions, the end position of a removal is determined by adding the length to the lowest level of the start position.

For example, let's assume that our document looks like a-c and the positions are sequential from [0] to [2]. Let's say that we want to remove -, which has the position [1]. A removal would be created with the first position at [1] and a length of 1, of course. Now, the text b could be added at position [1] to replace the 5.

However, this creates a problem. Let's say the events are reversed in order. The first document would read abc, but then the removal and addition would be performed second leading to a document reading a-c. This is the exact opposite of what we want! The solution is to establish an order of events. This is where the vector clock comes in. Though I didn't mention it before, each event (including insertions) has a variable called rclk, which is the vector clock. The vector clock is incremented with each removal, hence rclk: Removal CLocK.

To re-explain the previous example in context of the vector clock, let's assume that our document looks like a-c and the positions are sequential from [0] to [2] all with the vector clock of 0. Now we remove - at the position [1] with a length of 1. The removal event would be sent with a vector clock of 0, but the vector clock inside the Document class would be incremented. The future b that would be inserted would be sent with the vector clock of 1. If the client received this new event first, the - event and the removal event would be rejected since they have a lower vector clock.

Conflicts

The original Logoot algorithm added a "site ID" (this would be a combination of MXID and device ID in Matrix) to each part of a position. This was so that constant order could be established. This meant that no two nodes could have the same position since "site ID" became a part of the position. I decided that while this was a perfectly valid way of ensuring that there are no conflicts, it not desirable for UI/UX. Here's why:

Consider two users. The first stays connected and the other boards an airplane with no WiFi. Both edit the same section of the document and re-word a sentence a different way. When the second user lands, his or her events are sent to the server and are mixed with the first user's events. This would result in interleaved text and, assuming that one user sends text with a higher vector clock, the loss of one of the user's work. This type of operation would be perfectly valid in real-time collaboration, where edits are small and easily fixed, but it becomes a nightmare during large partitions.

My conclusion was that I needed a method for finding a conflict and showing both users what it is before just merging it. This is especially difficult because in the case of a partition between homeservers, it is impossible to tell which events occurred during a partition. At the moment, I am still working on a solution, but I think it's just a matter of figuring out some finer details right now. My current idea is to have each user implicitly working on their own branch. If one user wanted to delete another user's text, they would have to merge from their branch at the particular vector time and increment the vector clock. Then a removal event could be sent. Any clients seeing one branch overwriting another branch without a prior merge would flag this as a conflict.

This would also pave the way for user-defined branches in the future, which would allow more complex behavior such as suggestions.

Now, hopefully, I clarified a few things. If I explained it poorly and it's confusing, feel free to ask any questions on #matrix-collaboration:kb1rd.net and I'd be happy to clarity it. (And hopefully fix this page!)