Re: [Xournal-devel] "White boarding" aka "networking"

[Denis A. <au...@ma...>]

Hi Felix,

Collaborative editing in xournal is indeed a major future goal. I 
actually once spent about 3 months on an aborted attempt to implement 
it, but hope to return it when I have significant amount of time to 
spend on xournal over several months (hmm, how likely is that? my next 
sabbatical is in 6 years only, sigh). The main issue is that, if it is 
to be done the right way (which it should), then it will take a major 
code rewrite. Here are some thoughts and lessons learned from my first 
attempt.

The goal should be to allow simultaneous editing of a same document by 
various participants over the network, while preserving everyone's 
freedom to draw, undo changes, etc., and dealing reasonably with 
simultaneous-editing conflicts (e.g., I'm writing on a page while my 
collaborator is erasing in the same area, or even deleting the entire 
page). It should also deal reasonably with loss of network connection / 
time lags.

The major changes in architecture this requires are:

1. in order to handle simultaneous editing and time lag issues, and 
allow each participant to undo/redo their changes independently of what 
the others have been doing in the meantime, every data structure should 
become persistent and timeline-aware. For example, a text area might 
carry within it information such as "I was created by person A at time 
step 243 with contents 'Hello'; then at step 357 my font was changed by 
person B to size 14; then at step 432 my color changed to blue by person 
C ; then at step 573 I was deleted by person B". All this history has to 
remain in memory, until the collaborative session is closed and the file 
is saved, so that participants can undo/redo individual events. Every 
timeline event needs to be individually undo/redoable, out-of-order. In 
the example above, person A might undo their creation of the text box, 
which would cause it to disappear from the visible document even if B 
undid the deletion (and make all the subsequent modifications performed 
by B and C irrelevant; but still they need to be kept around). And of 
course the whole timeline of the text area might live on a page whose 
creation at step 15 might actually have been undone (so the 
"un-realization" of step 15 makes the whole subsequent story of the text 
area irrelevant). Simultaneous editing conflicts or time lags can then 
be handled by the same process: the various instances of xournal just 
have to agree on a common timeline (which may have to be negotiated 
after-the-fact in case of major time lags), and operations performed by 
remote collaborators can be inserted after-the-fact into the editing 
history, possibly *before* operations that the local instance of xournal 
has already processed. (In the example above, person D who had a very 
poor network connection might come in 10 seconds later and say "wait, at 
step 457 I moved the text box to page 5", and instances A,B,C will 
insert that into their time line).

2. the flow of operation processing needs to be modified substantially. 
Currently, the code for each user action mixes together two things: (a) 
interpreting the user actions and deciding what operations are to be 
done on which items of the journal, and (b) performing those. Part (b) 
is also re-implemented separately also as part of the undo/redo feature.
In a collaborative environment, operations on the journal can be caused 
by the reception of network messages rather than by a user action; so 
the internal processing flow needs to be modified to separate (a) from 
(b). In fact one could argue that the user action should lead not to an 
action on the journal data structures, but to the serialization of the 
operation to be performed into a network message; that message is then 
both sent to the local instance for local processing, and to all remote 
participants.

3. another issue is the interplay between lengthy user operations (say, 
I spend 30 seconds editing a text box or drawing very carefully a long 
stroke or erasing stuff) and network messages. Currently, while the user 
is erasing, the journal data structures are in a transient state which 
is not suitable for interaction with network-based modifications. One 
could imagine blocking the processing of network messages (i.e., not 
showing what remote participants are doing) while the user is performing 
an action -- which is fine due to item (1) above, which means all the 
stuff that happened in the meantime will be inserted before the action 
just performed. Or, if remote updates are to be processed and displayed 
while the user is editing the journal, one needs to modify the code so 
that the process of drawing / editing does not actually operate on the 
journal data structures but only on on-screen representations. (There 
remains the question of what to do, user interface-wise, if the page on 
which one is drawing/editing gets deleted partway through the operation. 
Not processing things concurrently would simplify that issue.)


Therefore, in my view, before even implementing any actual network 
collaboration feature, there's a need for a near-complete code rewrite 
to implement these features internally. Then it becomes simply a matter 
of adding actual network collaboration (i.e., handshake / initial state 
synchronization; sending/receiving the messages, and maintaining the 
common timeline; handling disconnects and termination of the network 
session).


Item 2. is pretty much a requirement for any reasonable collaboration 
architecture. Item 1. is more debatable -- it is an ambitious idea, and 
has implications even for single-user editing. Namely, with a suitable 
user interface, it allows non-linear undo/redo within a session: so for 
instance I could undo some major and catastrophic change I made an hour 
ago on page 12 without having to lose the changes I made in the 
meantime. One issue of course, besides difficulty of implementation, is 
memory growth over time during the session as everything remains stored 
for speculative undo/redo. A possibility is to "flatten the history" 
once in a while, with user approval (or with a time margin, e.g. one 
only flattens revisions that are more than 30 minutes old or some other 
set time), especially on memory-constrained platforms like the N900.

More traditional alternatives to the above are:

(a) a client/server architecture (one of the instances of xournal is in 
charge of maintaining the document and dispatching editing changes 
across other instances). I don't like that option at all: clients with 
time lag will have a vastly degraded user interface if strokes drawn 
locally don't appear until the message has made a round-trip from the 
server; whereas, if local actions are processed locally without 
consulting the server, then they may need to be undone and reprocessed 
in a different order if a conflicting action took place remotely in the 
meantime, which leads to significant complexity again.

(b) the use of locks: to draw something I need to obtain a lock on the 
layer I'm editing (which I will release immediately after the user lifts 
the pen). The main difficulty here is that I'd like these locks to be 
handled automatically, and not be affected by network lags or 
disconnects. I think this would be easier to implement in first 
approximation, but that a lock-based architecture that allows users to 
just go ahead and draw without any noticeable time lags would be as 
complex (and perhaps more prone to bugs) as what I propose above, even 
though it'd be a less drastic code rewrite.

* Note: there is also a smaller, "baby" whiteboarding implementation, 
which can be done with less code reorganization (though it would still 
be useful to implement item 2. above first). We'd have one master 
instance of xournal, which has sole control over major operations such 
as adding/deleting pages, changing backgrounds, etc.; those require an 
exclusive lock and prevent anyone in the collaborative session from 
doing anything while they're happening (the same goes for undo/redoing 
such a page operation, which also can only be done by the master). If 
anyone is in the process of editing (so the master cannot obtain the 
lock), the master has to wait until the operations end (or time out). 
Then, on each page, there are multiple layers, each of which belongs to 
a specific participant and is read-only to the others; that participant 
is the only one who can draw, erase, move, etc. items on that layer. (Of 
course, a small modification from the current mode is that, even if 
layers are globally ordered, everyone can see all the other layers that 
they'd like to see on the page).

This is presumably significantly easier than proposed item 1. above, but 
it's still a serious code rewrite, and the inability to edit any item on 
someone else's layer will probably be an annoying restriction, so I'd 
rather aim to do the right thing.

In any case, while I understand Daniel's remark about the benefits of a 
modular architecture (and do think that this would be a great idea 
especially for user interface features), I don't think network 
collaboration is something that can be handled as an add-on -- it 
requires a serious rethinking of everything in xournal.

Denis

-- 
Denis Auroux                             au...@ma...
University of California, Berkeley       Tel: 510-642-4367
Department of Mathematics                Fax: 510-642-8204
817 Evans Hall # 3840
Berkeley, CA 94720-3840