-
Notifications
You must be signed in to change notification settings - Fork 1
Protocol
Protocol issues and details are to be documented here. None of them are fixed, the protocol is going to evolve in parallel with colorg design. Hopefully, the protocol will stabilize as we are getting more experience.
A colorg client pushes a description of modifications made by the user to the buffer, which is meant as an image of the resource on the server. Modifications are accumulated on the client side and sent in batches, after a short lapse, rather than sent separately as they occur. By buffering the sending of these modifications, Emacs might stay a bit more responsive, and be a bit less demanding on the communication network.
When a batch is sent, a reply is expected, and that reply possibly contains many modifications accumulated in the server, coming from other clients, and meant to be transmitted and executed on the current one. While this round-trip is occurring, Emacs blocks and becomes unresponsive for a jiffy. Hopefully, these regular interruptions are not going to be overly noticeable and disturbing; only experimentation will tell.
To alleviate the problem a bit, sending batches are automatically delayed until Emacs gets quiescent for a short while, so if the user is currently typing at good speed, no interruption is going to occur. Also, to make sure others’ modifications are effected locally even when the user is not typing, batches should be sent at regular interval even if they are empty (they contain no modifications), for the sole effect for polling the server for incoming remote modifications.
Well, the above is not true! Currently, the Emacs server polls the server at regular intervals, regardless of Emacs being quiescent or not, because I did not find how to do better. Contrarily to my expectations, this is very bearable and apparently innocuous, at least when both the server and the client run on the same local network.
Notice that batching is not limited to a single resource. Changes to many different buffers may be batched together, and the returned batch of modifications may affect a mix of local buffers.
Protocol messages are encoded as JSON expressions. We explicitly avoid any transmission format based on Lisp, as a mild attempt to somewhat untie Org from Emacs. We could of course devise some specialized format that would terse and economical, but this would imply writing encoders and decoders for any colorg compatible client or server. JSON encoders and decoders are already available for most frameworks or languages. On the verbosity aspect, one could do much worse than JSON and pick XML :-). JSON seems to be an acceptable compromise.
JSON expressions need some kind of envelope to describe the extent of each, as the TCP/IP protocol does not itself have the concept of a delimiter between messages. As messages may be fragmented and transmitted as many packets, the notion of a transmitted chunk is meaningless.
colorg might support some popular messaging framework one day, but right now, we aim something overly simple and crude. So here is the convention: each JSON message is a text having no embedded newlines, and is followed by a newline.
When a colorg client initially contacts a colorg server, the server replies with:
"colorg v1"\n
where 1 is the protocol version number, and \n represents a newline.
From now on, the client may send commands, each being a JSON expression. A command may be represented by a mere JSON string naming it, or else, by a JSON list for which the first element is a string naming the command, the other elements of the list being the arguments for that command. The server replies to each command by another command, this time sent from the server to the client. Each replied command is also JSON expression using the same convention: either a mere JSON string naming the command, or a JSON list for which the first element is a string naming the command, the other elements being arguments.
The set of commands, as well as the detail, may differ depending if the command is sent from a colorg client to a colorg server, or the other way around, from a server to a client.
A server never asynchronously sends a command to the client, it only replies to a command previously sent by a client to the server. For each such command sent by a client to the server, there is exactly one reply, usually a done command or an exec command. If the server is unable or unwilling to comply with a client command, it may return a warn command instead, or even an error command.
In the following descriptions, RESOURCE may be the name of a resource on a colorg server, or else, an integer number for that resource on that server. On the client side, resource numbers may be resolved to resource names through the resources command. Such numbers may also be returned after a create command. Similarly, USER is either a user name or number. On the client side, user numbers may be resolved to user names through the users command.
Positions are zero-based, and may be seen as sitting between two adjacent characters. For example, the first character of a resource goes from position 0 to position 1. FIRST is the position before the first character of a resource fragment. If one prefers to think positions as being located on characters instead of between them, FIRST is the position of the first character. (Beware that within Emacs, positions are one-based, not zero-based.)
An alter command describes a local modification to the resource. Its format is:
["alter", RESOURCE, FIRST, DELETED, INSERT]
In the resource, a count of DELETED characters beginning at position FIRST are to be deleted, and replaced by the INSERT string. If INSERT is empty, the deleted characters are not replaced. If DELETED is zero, no characters are deleted, and INSERT is merely inserted at the given position.
A chat command is meant to send an out-of-band message to some other user:
["chat", USER, STRING]
The given STRING is to be sent for display to the specified USER.
A create command is meant to add a new resource on the server:
["create", RESOURCE]
Here, RESOURCE has to be given by name. If no resource is being named RESOURCE on the server, a new one is created empty, and the server replies with the resource number:
["done", NUMBER]
A join command associates a resource with a local buffer:
["join", RESOURCE, MD5SUM]
On receipt of this command, the server computes a MD5 check sum of the specified RESOURCE and compares it with the MD5SUM in the command. If they match, it starts monitoring that particular resource for us, notifying us of any modifications happening to this resource as part of the information returned in subsequent poll commands. As a special case, if MD5SUM indicates an empty file, the whole file contents is going to be sent in at the next opportunity. The server replies with the resource number:
["done", NUMBER]
A leave command stops monitoring a particular resource:
["leave", RESOURCE]
After this command is received by the colorg server, it will not send us notifications anymore about the modifications happening to this resource.
A login command identifies the current user to collaborating users:
["login", NAME]
The only goal of this command is to provide a USER field value to other users which is associated with our name instead of Anonymous. That command may later acquire some authentication value, but currently, there is just no password nor security. The function returns the current user number:
["done", NUMBER]
A logout command undoes the effect of the login command:
"logout"
The current user returns to the anonymous state. The function returns the current user number:
["done", NUMBER]
A poll command is the main vehicle for transporting modifications to the server, and getting back modifications coming from external sources. It has a variable number or arguments. Each argument is itself an outgoing subcommand.
"poll" ["poll"] ["poll", SUBCOMMAND1, SUBCOMMAND2, …]
Each subcommand represents a command aimed at the server or at all other clients connected to that resource. Unless there an error is detected, no reply is expected from any of these subcommands. Rather, the server responds with an exec command.
When the client has nothing special to say to the server, it may send a poll command with no subcommand, merely to give a change for the server to say something from its side. If the server has nothing to say, it replies with an empty exec command.
A resources command has the purpose of getting a list of all resources known to the server.
"resources"
The server returns many elements, each of which describes a resource as a sub-list of two elements: the string naming that resource, and the resource number:
["done", [STRING1, NUMBER1], [STRING2, NUMBER2], …]
A users command gives some meaning to user numbers:
"users"
The server returns many elements, each of which describes a user as a sub-list of two elements: the string naming that user, and the user number:
["done", [STRING1, NUMBER1], [STRING2, NUMBER2], …]
An alter command describes a local modification prescribed for the buffer associated with a resource. Its format is one of:
["alter", RESOURCE, FIRST, DELETED, INSERT, USER] ["alter", RESOURCE, FIRST, DELETED, NUMBER, USER]
The RESOURCE field gives the resource number to which the local buffer is associated.
In the buffer, a count of DELETED characters beginning at position FIRST are to be deleted, and replaced by the INSERT string. If INSERT is empty, the deleted characters are not replaced. If DELETED is zero, no characters are deleted, and INSERT is merely inserted at the given position. The field USER is the user number indicating from who the modification originates.
If the second form of the command is used, NUMBER represents the length of an arbitrary string to insert, the string itself is not specified. In fact, the actual characters making it have no importance, as they are going to be soon deleted by a later command. This form is likely to go away when the colorg server will implement some better optimization. (For the time being, we aim a working solution rather than an optimized one that would take longer to develop.)
A chat command is meant to send an out-of-band message from some other user:
["chat", USER, STRING]
The given STRING is to be displayed on some chat window, originating from the specified USER.
A done command is often the server’s reply to a client command. It may also contain one or more values returned from the command:
"done" ["done"] ["done", VALUE1, VALUE2, …]
An error command represents a diagnostic from the server:
["error", STRING]
The given STRING explains some abnormality or error condition seen by the server, which should normally be brought to the attention of the user by the colorg client.
There is an important difference between error and warn. Returning error is a way for the server to inform the client that it considers that the synchronization is not dependable anymore between the client buffer and the server resource, and that it severed the association, a bit as if the client sent a leave command. The client should react by abandoning the association on its side as well.
An exec command is a way for the server to batch a series of commands for the client to execute. There might be zero, one or more subcommands:
"exec" ["exec"] ["exec", SUBCOMMAND1, SUBCOMMAND2, …]
This is the normal reply from the server to a poll command received from a client. It conveys a batch of incoming commands meant for this client, originating either from the server or from other clients. If there is no such incoming command, the exec command is empty and has no subcommand.
A warn command represents a diagnostic from the server:
["warn", STRING]
The given STRING explains some abnormality or error condition seen by the server, which should normally be brought to the attention of the user by the colorg client.
Merging modifications simultaneously made by many users has its own difficulties. If an editor had to check with a remote server after every character inserted or deleted, before displaying the effect of that insertion or deletion, the editor would become unbearably unresponsive. There is no choice: the propagation of modifications has to be delayed, it just cannot be kept synchronous between all collaborators.
The next problem is the ordering of those delayed modifications. As modifications are described using absolute character positions in the buffer, the order in which these modifications are applied become important and should be the same for all collaborators, as we want them to all to use the same buffer contents. If the modifications are applied in varying order between users, it is likely that contents will diverge, making further collaboration progressively messy or impossible.
The colorg server is responsible to make sure all modifications are applied in the same order for everybody. One thing it cannot do, however, is preventing the modifications made by a user in her own buffer to be executed immediately, as this is done locally. The server may have to adjust local editions, to guarantee that everybody’s buffer has the same contents.
Synchronization difficulties are handled by the server, rather than by every client. The goal is to keep clients as simple as possible, so it would be easier to adapt the colorg protocol to other clients. In particular, clients do not add time stamps to editing actions, as other synchronizing tools do, there is no attempt at re-establishing the exact temporal order of commands between collaborators who work a bit asynchronously from one another. For each resource edited collaboratively, the server holds a copy as a reference, and instructs colorg clients about how to modify their associated buffer so it is kept identical to the server resource. This implies that, at least theoretically, all clients receive the same modification commands, in the same order.
For this to work flawlessly, just before transmitting a set of local modifications to the server, a client should undo them to bring back the local buffer in the state it has just after the preceding synchronization, because these modifications were applied prematurely by comparison to other modifications sent to the server by other collaborators. The server should then send instructions to reapply these modifications, but only once the accumulated modifications from other collaborators have been applied. This is the only way to really guarantee the exact same modifications in the exact same order for everybody.
However, if modifications do not clash, undoing modifications for re-applying them a bit later might be overkill, and various optimizations are possible. For the time being, the server does not do much, and sticks rather closely to the naive approach: the goal for the colorg project is quickly getting a dependable solution, leaving optimizations may come later. Synchronization protocols might be designed hairy, with optimizations deeply built-in, which might be an error: the best avenue is to devise a protocol by which optimizations are optional, and might be cautiously and progressively added within the server, while leaving the clients alone.
In the long run, the server knows best, and determines whether the undoing is needed or not, so the clients do not have to take any undoing initiative, and rather let the server decide. It is the server duty to figure out by itself, for each modification, if the prior undo and later redo could be safely spared. And if it cannot be, the server either send commands to undo a modification and to re-apply it later, or computes an adjustment to the buffer that repairs the damage created by the premature application of the modification. Briefly said: the server decides for the worse or for the best, and the clients comply.
The server proceeds in a few phases while receiving a batch of commands from a client. All altering commands are put aside on an incoming command queue. There is already a batch of outgoing commands queued in the server for that client, and waiting to be transmitted. These two queues might interact with one another. In the most naive approach, the server goes through these phases:
- each command on the incoming queue is turned into an undo commands, all of them being saved on a temporary undoing queue;
- each command of the incoming queue is corrected according to the contents of all commands on the client outgoing queue, the result is applied to the resource copy within the server, and added to all clients’ outgoing queue, including self.
- the undoing queue is added at the beginning of the client outgoing queue.
- optional optimization might remove commands from the client outgoing queue.
In less naive approaches, optimization might be more aggressive and pervasive: the server might avoid steps 1. and 3. above, and exclude self from the broadcast at end of step 2. But then, it needs to cleverly adjust each command the client own outgoing queue, according to changes announced by the client in the incoming queue. Clashing cases might force supplementary command to counteract the effect of premature local execution. The next sections study how this is done in some more detail.
Let’s assume there are three collaborators A, B and C having buffers identical to the associated server resource. Moreover in the examples, let’s say A, B, and C users are numbered 1, 2 and 3, and that the resource has number 7.
Let’s first consider a simple case where there is no overlap between modifications: user A deletes 2 character between positions 20 and 22; user B inserts 3 characters at position 30; user C replaces 4 characters starting at position 40 with 5 others. Let’s assume that all three of A, B and C transmit their modifications to the server, in that order. The corresponding commands are respectively:
["alter", 7, 20, 22, ""] ["alter", 7, 30, 30, "abc"] ["alter", 7, 40, 44, "defgh"]
These commands are received by the server in separate communications, since they come from different clients. Notice that, on receipt, the server adds the user identification to the command, so they respectively read:
["alter", 7, 20, 22, "", 1] ["alter", 7, 30, 30, "abc", 2] ["alter", 7, 40, 44, "defgh", 3]
To undo an altering command, deletions should be turned into insertions, and insertions turned into deletions, giving:
["alter", 7, 20, 20, 2, 1] ["alter", 7, 30, 33, 0, 2] ["alter", 7, 40, 45, 4, 3]
In the A case, the original command deleted two characters and inserted none, so the undo version deletes no character and inserts 2. In the B case, the original command deleted no characters and inserted 3, so the undo version deletes 3 characters and inserts none. In the C case, the original command deleted 4 characters and inserted 5, so the undo version deletes 5 characters and inserts 4.
Notice that if the undo version of the commands are sent back to the client in the exact opposite order of their receipt, there is no need for any adjustment of the character positions in the commands.
The undo versions use a number of characters to insert instead of an insert string. This is to save network bandwidth: given these inserted characters are soon going to all deleted by a later command, it is not mandatory to insert exactly those characters which were originally deleted: this is temporary and any character would do.
On receipt of the command from A, the server deletes 2 characters at position 20 in the resource, and adds ["alter", 7, 20, 22, "", 1] to both B queue and C queue. It replies ["exec"] to A, telling there is nothing to do. Simple enough.
On receipt of the command from B, the server notices that B’s outgoing queue is not empty, meaning that B sent its command prematurely, without knowing about the modification earlier made by A, and which is already applied in the resource. If B had known, it would have used 28 instead of 30, taking into account the deletion of 2 characters before position 30. So, the server rewrites the command as ["alter", 7, 28, 28, "abc", 2]. This rewritten command is then used to add 3 characters in the resource, and gets added to the A queue and the C queue. The contents of the B’s outgoing queue is to be returned, and because the 20 position is below any change locally made by B, no adjustment is necessary in this case:
["exec", ["alter", 7, 20, 22, "", 1]]
On receipt of the command from C, the server also notices that C’s outgoing queue is not empty: there are two waiting commands in it, meaning that C sent its command prematurely, without knowing about the modifications made by A and B, already applied to the resource. Taking these two in account, the command is rewritten ["alter", 7, 41, 45, "defgh", 3] as A deleted 2 characters and B added 3 before position 40. This rewritten command is then used to replace 4 characters by 5 in the resource, and gets added to the A queue and the B queue. Now, the contents of the C queue is to be returned, and because both the 22 and 28 positions are below any change locally made by C, no adjustment is necessary in this case as well:
["exec", ["alter", 7, 20, 22, "", 1], ["alter", 7, 28, 28, "abc", 2]]
These examples illustrate that, when the server receives a command from a client, it first handles that command corrected by the commands in the queue for that client, and second, it returns the outgoing queue contents, correcting the queue commands as appropriate from the received command. In the three cases given, the undoing queue may be wholly spared if the server excludes each client from receiving, in its outgoing queue, a copy of its incoming queue commands.
Now, instead of having A, B and C contacting the server in that order, consider that C contacts the server first, followed by B, then A. This is a much simpler situation, as each modification is made at an smaller position in the resource than for earlier commands, so incoming commands may be copied to other clients outgoing queues without any adjustment.
If the undoing queue is used, there is nothing else to say, and everything works out smoothly. However, if the undoing queue is not used, the outgoing commands need to be adjusted. Each command in the queue gets revised to account for any change announced by the client. If the client sent a batch of commands, all of them have to be considered for correcting the reply. This might be detalied in some later version of colorg.
If the undoing queue is used, clashing modifications cause no problems, no special consideration is needed. However, to spare the undoing queue, things get more complex. We might want to consider full deletion clashes, full insertion clashes, partial clashes and mixed clashes. This is all postponed to some later version of colorg.
[2013-01-28 lun] Well this is not fully true: special care is needed to handle clashes even if an undoing queue is used. More precisely, we have to forego these steps:
- The incoming queue should be simplified and optimized in such a way that all alterations become independant on one another: no alteration should delete text inserted earlier in another alteration. Inserts should ideally be concatenated when they are locate at the same point, yet the algorithm does not currently depend on this second property. The client already does such mild concatenation to alleviate transmission a bit, yet it might be a premature optimization. It
- The undoing queue is created from the incoming queue and saved aside, as described above. This could be done before step 1., but it is more elegant that the undo queue stays minimalistic.