Gobby

Gregory Haynes is working on Kobby featuring collaborative text editing in your favourite KDE text editor as a GSoC project. He started to wrap the (still unreleased!) libinfinity (my infinote implementation) API for C++ for this task. I'm really excited to see other collaborative text editors coming up that work together with Gobby, since this is exactly one of the reasons why I took the burden to write the library in GObject-based C.

Speaking of which; I didn't blog on it for a long time. We have moved to git in the meantime. I'm currently working on porting Gobby to use libinfinity instead of obby, heading towards a first usable release, so that the hard work pays off. There are still some things in libinfinity that need to be fixed (performance issues, a few known bugs and way more testing) which are probably easier to fix when a usable Gobby version using it exists. I hope to have these done in a few months, though the most difficult part is always to get the little details right, which is probably why I'm not good at meeting (self-set) deadlines.

Many people using gobby complain that it does not support Undo, and some do not even use it therefore. Of course, they are right. It is not only convenient but may also save you lots of data in case you accidentally delete it. However, it is not easy to implement it in a collaborative editor because between your own do and undo operation pairs others might have altered the document. It is thus not reverted to a previous state as with a single user editor. We got suggestions to add some sort of "primitive" Undo like just undoing the last operation, no matter from whom it was. I didn't like that, though, because I prefer to either do things correctly or not at all.

Fortunately, other people also thought about how to achieve collaborative Undo. I read some papers [1] describing an algorithm (adOPTed) that not only achieves convergence, meaning that two users don't end up with a different document after having applied some operations concurrently (which the obby algorithm (called Jupiter) obviously also achieves), but also allows Undo/Redo (which Jupiter does not when more than two users are involved). This is however not the one-and-only solution. There are other approaches to collaborative Undo (or resolving collisions in general), like the AbiCollab one. adOPTed has some nice properties though:

• It has enough information to not only undo your own but also any other's operation. Actually, when a user wants to Undo something, it just says "I am doing an Undo now" and the others calculate the required operation. This especially allows to easily restore user colors when a deletion is being undone (without allowing arbitrary insertion of text colored with another user's color). It could also be used to undo vandalism issued by another user.
• You can always undo and redo your operations, independent of what others have done in between. However, it might happen that an undo has no effect (for example, if you type something, another one deletes it and you press undo then). I wonder by the way what a user expects in that case: Imagine you are typing two letters, and another user deletes the second one. When you press Undo now, would you expect nothing to happen (because another one already "manually" undid your latest operation) or would you expect that the first letter also disappears (because of exactly the same reason)?
• It doesn't need a server to make some final decisions or to keep things in order. You just have to make the other participants receive your requests somehow. Also, there are no conflict situations or something requiring additional round-trips.

However, as always, everything has its price:

• My implementation requires already a lot of CPU power in my simple test cases to calculate the required transformations, especially when there are lots of operations between a do/undo pair.
• As every user calculates the undo operation by itself, every user needs to keep track of every request made by any user. This also requires to send the whole request log to a joining user. Of course, this can be limited to the latest N operations, but it is still a considerable amount of data (especially when many users are working together) and restricts the number of operations people can undo.

My proof of concept featuring Undo and Redo is here. However, you probably won't understand the interesting part of that code without having read the papers referenced above (which you should do as well if you are interested in more details, by the way). There a still a couple of issues before that can be used in a real-world environment, though. I think the performance problems mentioned above can be fixed by caching transformed requests, so that it does not have to compute the same requests all over again. Another problem that needs to be solved is a dynamic amount of users. My test code only works for a fixed number of users. The difficulty is to find out when it is safe to forget about operations from a user that has left the editing session, to save memory and bandwidth.

I hope to get that done really soon now so that it can be used in Infinote and perhaps even Gobby (I have not yet decided whether I want to implement that in Gobby because it is still a considerable amount of work).

I am off to Ireland at the 23th of July and am visiting some friends near Osnabrück right after that, but when I am back home (presumably at 12th of August) I really hope to get something usable (read: a gedit plugin) before my third semester at university begins in October. Unfortunately, I cannot make it to GUADEC this year because I have to be at university that week, but I really look forward to finally get there next year.

[1] Achieving Convergence with Operational Transformation in Distributed Groupware Systems (by Abdessamad Imine et al.)
An Integrating, Transformation-Oriented Approach to Concurrency Control and Undo in Group Editors (by Matthias Ressel, Rul Gunzenhäuser and Doris Nitsche-Ruhland)
Reducing the problems of group undo (by Matthias Ressel and Rul Gunzenhäuser)

Today, I read the GtkSourceview 1.90 release announcement on gedit-list. After having finished my math excerises much earlier then expected I decided to hack GtkSourceview2 support into Gobby. I committed it a few minutes ago into SVN, after having received some advice from Yevgen Muntyan to get it to work (You have to associate a style theme by hand to get highlighting, which will hopefully be changed in the future so that a default theme is used if none is given).

GtkSourceView2 basically comes with a new syntax highlighting engine that allows embedding languages into others (such as JavaScript into HTML, as shown on the screenshot). It also has theming support and mapping between filename patterns and language definitions, which Gobby had to implement before (and it still does since GtkSourceView1 is still supported).

Gobby development has not stalled. We released 0.4.3 with native Avahi support a few weeks ago. However, it is not planned to add any great new features in favor of the sequel I already announced half a year ago. Unfortunately, it does not make as much progress as one could expect it to do, and especially not as much as I would like it to do. My second semester at university began three weeks ago, so I also don't think I get too much done in the following two to three months, either.

The successor of Gobby is going to be called Infinote. It will offer some (long-requested) features the current Gobby architecture does not support, such as different document types, XMPP-based messaging and showing remote cursors/selections. However, the fundamental change is that I want to provide a kind of framework rather than an editor, and to get people to implement Infinote support into their editors so that ideally you can just continue to use your favorite editor for collaborative work. For this to work, I need to properly document the API and network protocol which is also one of the points Gobby is rather weak in currently.

A propos protocol: More and more collaborative editing efforts pop up lately, like Pisara Editor, AbiCollab (which I should really try out in the near feature...) seems to be mature and a GUADEC session description mentions some gedit/collab (over which I did not find out any further details, though). Then, there are of course ACE and MateEdit which I am already aware of. All of these (including Gobby) use different protocols, and are therefore unable to interoperate with each other. Most seem to agree that XMPP is a good base, but there is still the application-specific stuff on top of it that needs to be compatible. It would be great if there was some project like freedesktop.org to agree on a standard for collaborative (text) editing.

The current Infinote code is available in a public SVN at svn://svn.0x539.de/inifinote for those who want to have a look at it. However, most of the ideas do only exist in my head by now and are not written down somewhere in there.

Do you remember back in school when you learned stuff you certainly would not need anymore in your future life? I thought the same thing when we programmed things in Delphi (those things actually were quite interesting, though). After Phil poked me once again yesterday, I finally decided to fix long-standing bug #145. So, guess what, the setup system we use (InnoSetup) is not only written in Delphi but also allows custom Pascal Code to be executed during setup. So this is what I came up with, and it would certainly have taken me some more hours if I did not know Delphi before.

I wonder however whether I will have to use Java for some real-world application one day. I would be nearly as good prepared as I was for the Delphi task.

We released Gobby 0.4.2 today. It does not support that much new features, but fixes some annoyances people have complained about: The urgency hint (the window flashing when a user wrote something in the chat) is configurable, documents can be subscribed to by double-clicking them in the user list and the editor tries to keep the line you are currently editing at the same position within the viewport if others add or remove lines elsewhere.

Sobby, the dedicated server, supports initial loading of regular documents instead of serialized obby sessions. Just pass them on the command line as with sessions, sobby will detect whether its a session, and if it is not, it will open it as a document. Sobby now also allows autosaving individual documents into a directory, via the --autosave-directory command line option or the autosave_directory entry in the configuration file, respectively.

Grab them on the Downloads page on our wiki.

Furthermore, I will attend this year's FOSTEL on April 4-5 to represent Gobby there (Thanks to Openismus for making this possible). So if you ever wanted to talk to one of the Gobby developers, be sure to meet me there.

The current draft for the new obby protocol plans to use a peer-to-peer-like mechanism for transport via jabber, so every jabber participant talks to other jabber participants directly instead of tunnelung through the publisher. This should reduce bandwidth usage quite a lot but raises quite a few other questions regarding peer-to-peer: Could new users join the obby network via any peer instead of just the publisher? Could the session stay alive when the original publisher leaves? I met Phil yesterday and we discussed these questions, and we even came up with some results. But first of all, what are the problems?

As soon as every peer in the network is allowed to accept new peers, we have to handle the case that two peers join the same network via two different nodes at the same time.

• This affects ID generation. Currently, every user is assigned a unique user ID for the session. This is required because the protocol allows multiple users per connection (which is again required for the good old client/server model used by the TCP subsystem, but this option also allows another nice feature (republishing) I want to keep in mind for the future). An incoming request however is user-related rather than connection-related, so it must be clear which user generated it. It is still possible to produce unique IDs as soon as an ID is variable in length. When a peer has to generate a user ID, it just takes its own ID and appends something to it to generate a new one.

• We cannot catch name collision. Two users with the same names could join the same network via two different peers at the same time. However, this does not matter at all since we could just allow duplicate names in the session. If we want to distinguish between them UI-wise we could suffix one client-side, maybe sorted by the user ID to keep it the same on all peers (but which would lead to renamings if a new user with the same name joins and gets an ID which is sorted before the ID of the existing user).

• How to do user authentication? obby 0.4 allows each user to set a password which is stored on the server (respectively publisher) and recognizes users by name. So, if a user with the same name as a user which was in the session some time ago joins, the server looks whether a password has been set, and if the authentication was successful, the old user ID (with all text written by that user) is reassigned to the joining user. This is especially useful when the session has been serialized and should be continued later or when a user has lost the internet connection, perhaps by an automatically disconnection performed by the ISP (which is rather common at least in Germany, but that's another story).

  So, let's assume we want to implement a similar feature into the new obby. Since we just said that names could appear twice, we would need another criteria to recognize a user after disconnection. The user ID comes to mind. So each client could store a table assigning a session to the user ID he had. But since the user ID is known to all participants this feature could easily be misused, so some form of authentication would still be required. The only solution I see here is that you tell the peer through which you have joined (or perhaps others that you trust) a password and if you want to be recognized lateron, you have to join through one of these trusted peers. If all of them have left the session, well, bad luck. I you have some suggestions concerning this point feel free to add a comment or drop me a mail.

• We cannot just assign a vector time index to the new user because this could lead to conflicts as well. The solution would be an association between the user ID and the vector time component. This requires some more data to be stored in the state space and sent through the network.

As a last case, imagine the original publisher has left the session. In the flavour of a real peer-to-peer network the session would just go on as if nothing had happend. The only problem that could arise is that the publisher must not use the session ID that this session had for other sessions, because he cannot be sure that the old session with this ID might still be running somewhere. As sessions are identified by publisher and a session ID this could lead to conflicts. An easy approach would be to just generate a 32 bit random number as the session ID and assuming that we never generated this one before, but I do not like these approaches that only work in 99.999% of all cases and not in 100% (maybe just because I saw it too often that a mage in Wesnoth missed three times...). Having an ID counter somewhere in the user's home directory is not enough as well because another user might publish a session on the same port and with the same ID as another user on the same host (or just use the same jabber account). As above, I am open to any suggestions regarding this point.

Note however that these are just ideas and no final decisions and they only apply to the jabber communication level. All TCP communication is done as Server/Client as before because it is not guaranteed that all TCP participants can get direct connections to each others (think of NATs, different subnets and so on). This also means that Obby currently relies on all jabber users having direct connections (well, direct as in "I just need to send it to the jabber server and the other one will get it eventually").

The final release of Gobby 0.4.0 is now pretty close. 0.4.0rc3 has been released just recently and fixed a nasty bug that caused desynchronization, meaning that data consistency between multiple users has been lost. Currently, Phil and I perform some minor tweaks like supporting IPv6 in obby (net6 had this capability since the beginning) which seems to work already as we had an IPv6 session yesterday. Some other final fixes include still broken chat highlighting and UI stuff.

The sequel to the current version (currently codenamed obby 0.5, but most likely this will change before a first release to prevent name conflicts with obby <=0.4.0) will be developped in C, not C++. This has several reasons:

• C++ has a quite huge impact on code size. The same program written in C makes the shared library and the executable much smaller. This might only apply to GCC and probably because it links half of the STL into each and every binary, but it hurts when I see that it is not necessary for a working library.
• Binary compatibility is easier to maintain. First of all, net6 and obby made extensive use of templates which caused them to be linked statically into gobby and sobby. With handsight this was not a good idea at all since one always had to recompile gobby when libobby was upraded. On the one hand, I am convinced that API/ABI stability can be achieved with C++ (as gtkmm proves), but on the other hand one has to take very much care. Just adding another base class or a virtual function might break ABI (for example, this is why Gtk::ComboBox does still not derive from Gtk::CellEditable) whereas this would be no problem in C since there are not any virtual functions nor base classes.
• C++ makes it hard to create language bindings. There was already an attempt to create haskell bindings for obby, but it turned out that prior C bindings to the C++ library would have been required. I am however not an expert in this area, so I cannot say for sure whether there would have been other ways, but writing the library directly in C does not make it worse.

First of all, this means a complete rewrite of the library. This is a great opportunity to change the complete architecture. We want to get rid of the classic strict client/server architecture and get more into the peer-to-peer direction. We now follow an approach that kind of mixes both variants. The networking shall be divided into two tasks: Discovery and Transport. Discovery means finding running obby sessions within the network and transport means actual communication during a session.

A session now also only contains only one document instead of an arbitrary amount of documents. Instead, the library allows joining and creating multiple sessions using the same network connection. This reduces the concept of subscribing to a document to just joining another session.

Apart from this, obby 0.5 shall support the following key features:

• Multidimensional state space collaboration algorithm: Multiple two-dimensional state spaces (as currently used by obby) are easier to implement and maintain but cause a loss of data that makes it impossible to implement a proper Undo operation. It is however still very unsure whether Undo will be implemented in a first Version of obby 0.5 because some questions remain still open.
• Enhanced networking: obby 0.5 is going to offer the possibilty to use jabber for networking beyond a local area network. This allows easy NAT traversal with IPv4 and automatic session discovery in a WAN. Avahi will be used for discovering sessions in the local area network, and it is still possible to establish TCP connections directly, as it is still the case in obby 0.4. The only requirement is that sessions discovered via TCP or Avahi must be joined using TCP as transport and sessions discovered via Jabber must be joined using Jabber as transport.
• Display remote viewports, carets and selections: This is one of the most requested features for obby (probably right after Undo...). Whenever the local cursor position, selection or viewport (viewport as in scrolling position) changes, the event is transmitted to others. However, this must be controlled to save bandwidth usage, so, say, only once every 500ms such a request may be sent. This number could also be made adjustible at runtime to reduce latency in a LAN.
• Different character encodings per user: In obby 0.4, an encoding is set for the whole session and all participants have to deal with this. This will not much change in obby 0.5 since Jabber requires text to be in UTF-8, so this will be the encoding used for transport. However, obby is going to perform possible character set conversions by itself when you tell it what encoding you expect. This also allows offsets of insertions and deletions to be given in characters rather than in bytes, avoiding unnecessary calculations from offsets to byte indices and vice versa.
• Record and playback of sessions: Everything that has to be done is to serialize every incoming and outgoing operation with a timestamp included. This allows to go back in a session's history and view earlier versions of the document.
• Read-only users: They would not need an extra dimension in the state space, so apart from a bit more network traffic there is almost no overhead.

Like obby 0.4.0, obby 0.5 should have not that much dependencies (avahi is optional, iksemel is included since we had to apply one or two fixes to it and it seems not to be actively developed anymore). This allows it to be used on a variety of platforms and desktops without being required to use some uncommon dependency (like GTK+ on Mac OS X).

So, these are our plans for obby, but what about Gobby? Well, I also have some changes in mind, although they are even more far away. As I am a convinced GNOME user after all, I would like to integrate Gobby more into the GNOME desktop and become eventuelly even part of GNOME. This is why I am going to try to build an obby plugin for gedit after obby 0.5 has been released. Since we want to collaborate with non-GNOME-users as well, something is also going to replace Gobby as a stand-alone editor. I even consider using wxWidgets to achieve a more native look and feel on the corresponding platform.

However, this is very far away from now. The current obby 0.5 code has about something more than 10.000 lines of code and implements only most of the networking stuff including discovery via jabber and avahi. All those nice features mentioned above still have to be implemented and tested.