Context Navigation

Version 4 (modified by armin, 6 years ago)
Explained state Vector Diffs

Infinote protocol

Please note: This document is by no means complete. Comments appreciated.

TODO: Session example(s)

TODO: List error domains and codes

The Infinote protocol is based on XMPP.

Terminology

Host: A machine within a network.
Directory: Instead of just a set of documents (as in obby), Infinote supports a hierarchical directory structure of documents. This structure is referred to when we talk about the 'Directory'.
Node: A 'node' is a subdirectory or document in the directory.
Explore: A subdirectory node can be explored by a client. When a client explores a node, the server sends it the nodes the subdirectory contains and notifies it of changes if nodes are later added or removed in that subdirectory.
Session: A currently running editing session in which a document is (collaboratively) modified. A session is related to a document node in the directory. Note that in a session, only a single document can be edited. However, it is possible to subscribe (see below) to multiple sessions.
Synchronization: The process of copying a session's state from one host to another is called Synchronization.
Subscription: A host is called subscribed to a session when it receives session updates when users change the document.
User: When a host is subscribed, it can join a User into the session. Only users can issue requests (see below)
Request: This has actually two different meanings, based on the context:
- When a user modifies the document, it sends a request to all subscribed hosts to inform them about the change of the document.
- A client may make a request to a server, waiting for a response. In all such requests the client may set the seq attribute to some integer value. The server will answer the request with the same seq.

TODO: Distinguish between those two meanings of "request". A thought of calling the document-modifying request a "record".

This allows especially some perhaps not-so-intuitive scenarios, such as:

Client-to-Server-Synchronization: A client synchronizes a session to the server to be stored in its directory.
Synchronization-Only: A session can be synchronized to a client without the client subscribing to the session.
No-User-Subscription: A host can subscribe to the session without joining a user (and therefore unable to modify the document). This is read-only access, in fact.
Multiple-User-Subscription: When subscribed, a host can join multiple users into the session. This allows a client to act as a proxy for more clients that only can connect to the proxy but not to the "real" server.

XMPP

All messages are sent as XMPP messages, such as:

<message from="armin@0x539.de" to="phil@0x539.de">
 <some-content />
</message>

Groups

All communication is done within so-called groups. A group is identified by its name. Hosts can be member of a group. Messages can be sent by a group member to either another member or to the whole group. Such a group-related message looks like this:

<message from="armin@0x539.de" to="phil@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <more-content />
 </group>
</message>

Scope can be either "ptp" (point-to-point) or "group". If scope is "ptp", the message is only for the recipient (here phil@…). If scope is "group", the message is for the whole group. In this case, phil@… has to relay the message to all the group members that do not yet have received the message. For example, in a client/server network, the server should relay the message to all other clients (except the one the message comes from).

When using the jabber network, nothing has to be done because the original sender (armin@…) already has "direct" connections to the other group members (actually their JID and a connection to the jabber server). Note that this is not yet fully designed, because all group members need to get to know the others JIDs. Some special <group-join> messages are probably required therefore. Note also that this could also be implemented by jabber groupchat to reduce bandwidth.

Each group has a publisher, this is the host that "opens" the group. This way, two groups with the same name opened on different hosts can coexist. Another thing I am not totally sure about is whether it would be a good idea to use IP address and port number for the publisher for direct connections (i.e. when not using the jabber network). However, a host has to be aware of the fact that the same group it opened may be addressed via different publisher strings in different networks.

Directory

Directory handling is done within the 'InfDirectory?' group. The following messages are defined:

Client Side

<explore-node id="node_id" seq="seq_id" />

id, Integer: The node ID to explore. Each node in the Directory has an ID. The root node has ID 0.
seq, Integer, optional: An optional ID for the request. The server reply will have the same seq set.

Explores the node with the given ID. The server replies with <explore-begin>, <add-node> and <explore-end> messages.

<add-node parent="node_id" type="Type" name="Name" seq="seq_id" />

parent, Integer: The node ID of the parent node. This must refer to a subdirectory node.
type, (InfSubdirectory?|InfText?): The type of the node to create. Different node types may be supported in the future.
name, String: The name of the new node. Must not contain the '/' character.
seq, Integer, optional: An optional ID for the request. The server reply will have the same seq set.

Adds a new node to the server's directory. The server replies with <add-node>.

<remove-node id="node_id" seq="seq_id" />

id, Integer: The node ID to remove. If it is a subdirectory, all children are removed recursively.
seq, Integer, optional: An optional ID for the request. The server reply will have the same seq set.

Removes a node from the server's directory. The server replies with <remove-node>

<subscribe-session id="node_id" seq="seq_id" />

id, Integer: The node ID of the document whose session to join. Must not refer to a subdirectory node.
seq, Integer, optional: An optional ID for the request. The server reply will have the same seq set.

Requests subscription to the session refered to by node_id. The server replies with <subscribe-session>

Server Side

<request-failed domain="error_domain" code="error_code" seq="seq_id">
 <text>Human-readable text</text>
</request-failed>

domain, String: The domain where the error came from. The most important domain is "INF_DIRECTORY_ERROR".
code, Integer: A numerical error code identifying what went wrong. This depends on the error domain.
seq, Integer: The seq_id the client had set in the original request that failed, if any.
text, optional: Human-readable error message in the server's language.

This is sent if a client request could not be processed, for example because it refered to a directory node that does not exist.

<explore-begin total="num" seq="seq_id" />

total, Integer: The number of nodes in the explored directory. This can be used to show a progress bar on the client.
seq, Integer: The seq_id the client had set in the original <explore-node> request, if any.

Server reply to a <explore-node> request. This is followed by total <add-node> and an <explore-end> message.

<explore-end seq="seq_id" />

seq, Integer: The seq_id the client had set in the original <explore-node> request, if any.

This is sent when all <add-node> messages that belong to the original <explore-node> request have been sent.

<add-node id="node_id" parent="node_id" type="Type" name="Name" seq="seq_id"/>

id, Integer: The node ID of the added node
parent, Integer: The node ID of the parent node (which is a subdirectory)
type, (InfSubdirectory?|InfText?): The type of the new node.
seq, Integer: The seq_id the client had set in the original <explore-node> or <add-node> request, if any.

The server notifies the client that a new node has been added to the directory, within a subdirectory that the client already explored. Also used when a client currently explores a subdirectory.

<remove-node id="node_id" seq="seq_id">

id, Integer: The node ID of the removed node.
seq_id, Integer: The seq_id the client had set in the original <remove-node> request, if any.

The server notifies the client that a node has been removed from the directory, within a subdirectory that the client already explored.

<subscribe-session id="node_id" group="group" seq="seq_id">

id, Integer: The ID of the document whose session the client is subscribed to. Must not be a subdirectory node.
group: The group for that subscription.
seq: The seq_id the client had set in the original <subscribe-session> request, if any.

Subscribes the client to a session. This goes on by synchronizing the session to the client within the specified group.

Example

<message from="phil@0x539.de" to="armin@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <explore-node seq="0" id="0"/>
 </group>
</message>

Client phil@… wants to explore the root node of the directory at armin@….

<message from="armin@0x539.de" to="phil@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <explore-begin total="3" seq="0"/>
 </group>
</message>
<message from="armin@0x539.de" to="phil@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <add-node id="3" parent="0" name="first" type="InfSubdirectory" seq="0"/>
 </group>
</message>
<message from="armin@0x539.de" to="phil@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <add-node id="2" parent="0" name="third" type="InfSubdirectory" seq="0"/>
 </group>
</message>
<message from="armin@0x539.de" to="phil@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <add-node id="1" parent="0" name="second" type="InfSubdirectory" seq="0"/>
 </group>
</message>
<message from="armin@0x539.de" to="phil@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <explore-end seq="0"/>
 </group>
</message>

Server reply. This could also be packed within a single <message> and <group>, respectively, but it would then be sent as a single XMPP message. The client then has no chance to get progress information before the exploration is finished, and a single, big message could block traffic in other groups that go through the same connection.

<message from="phil@0x539.de" to="armin@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <explore-node seq="1" id="1"/>
 </group>
</message>

Phil wants to explore another node.

<message from="armin@0x539.de" to="phil@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <explore-begin total="2" seq="1"/>
 </group>
</message>
<message from="armin@0x539.de" to="phil@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <add-node id="5" parent="1" name="bar" type="InfSubdirectory" seq="1"/>
 </group>
</message>
<message from="armin@0x539.de" to="phil@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <add-node id="4" parent="1" name="foo" type="InfSubdirectory" seq="1"/>
 </group>
</message>
<message from="armin@0x539.de" to="phil@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <explore-end seq="1"/>
 </group>
</message>

I think that is self-explanatory.

<message from="phil@0x539.de" to="armin@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <add-node seq="2" parent="1" type="InfSubdirectory" name="baz"/>
 </group>
</message>

Phil wants to create a new subdirectory called "baz" within the "second" subdirectory.

<message from="armin@0x539.de" to="phil@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <add-node id="6" parent="1" name="baz" type="InfSubdirectory" seq="2"/>
 </group>
</message>

Alright, subdirectory created with ID 6.

<message from="phil@0x539.de" to="armin@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <add-node seq="3" parent="1" type="InfSubdirectory" name="baz"/>
 </group>
</message>

This tries to create another subdirectory within the same parent also called "baz".

<message from="armin@0x539.de" to="phil@0x539.de">
 <group name="InfDirectory" publisher="armin@0x539.de" scope="ptp">
  <request-failed code="0" domain="INF_DIRECTORY_ERROR" seq="3"/>
 </group>
</message>

But this does not work. Error code 0 in the INF_DIRECTORY_ERROR domain means "Node already exists".

Session

Each session has a so-called subscription group, that is a group of which all subscribed connections are a member. The group name for that group is specified by the server (who is also the publisher of the group). Session joins can only be performed at the server, however, once joined, the session can go on even if the connection to the server is lost (assuming the other subscribed hosts are still reachable).

Synchronization Client

These messages are sent by the host to which a session is transmitted (also: to which a session is synchronized):

<sync-error domain="domain" code="code">
 <text>Human readable</text>
</sync-error>

domain, String: A domain from which the error comes. This is most likely "INF_SESSION_SYNCHRONIZATION_ERROR".
code, Integer: A numerical error code explaining what went wrong, depending on domain.
text, String, optional: A human-readable error message, in the synchronization client's language.

Sent when a message could not be processed during synchronization. This cancells the synchronization and possibly an upcoming subscription.

<sync-ack />

Tells the other end that all messages have been received and the synchronization was successful.

Synchronization Server

These messages are sent by the host that transmits the session data (also: from which the session is synchronized)

<sync-cancel />

Cancells the synchronization and a possible upcoming subscription.

<sync-begin num-messages="num" />

num-messages, Integer: The number of messages until the synchronization is complete, including <sync-begin> and <sync-end>.

The first message of a synchronization.

<sync-end />

The last message of a synchronization. When the synchronization acknowledges this message with <sync-ack>, the synchronization is complete.

<sync-user id="id" name="name" status="status" />

id, Integer: A unique user ID within the session.
name, String: The user's name.
status, (available|unavailable): Whether the user is currently available (=ready to modify the document) or not.

Tells about a user within the session. If status is unavailable, the user had joined the session some time ago, but has then left the session. Note that additional attributes specific to the InfText? session type may be set for text sessions, see below.

Also, more synchronization messages are used in InfText? sessions.

Client Side

These messages can only be sent when the initial synchronization is complete:

<user-join name="name" seq="seq_id" />

name, String: A unique user name within the session.
seq, Integer, optional: An optional ID for the request. The server reply will have the same seq set.

Requests a user join with the given name. The server will reply with <user-join> or <user-rejoin>

<user-leave id="user_id" seq="seq_id" />

id, Integer: The user ID of the user to leave the session.
seq, Integer, optional: An optional ID for the request. The server reply will have the same seq set.

Requests a user leave of the given user. The user must have joined from the same connection. When a user left the session, its status is set to unavailable.

<session-unsubscribe />

Unsubscribes from the session. The host leaves the subscription group.

Server Side

<request-failed domain="error_domain" code="error_code" seq="seq_id">
 <text>Human readable</text>
</request-failed>

domain, String: The domain the error comes from. This is most likely INF_SESSION_ERROR, INF_USER_JOIN_ERROR or INF_USER_LEAVE_ERROR.
code, Integer: A numerical error ID specifying what went wrong, depending on domain.
seq, Integer: The seq that the client set for the original request that failed, if any.
text, String, optional: Human-readable error message in the server's language.

Tells the client that a request it made could not be processed.

<user-join id="user_id" name="name" status="status" seq="seq_id" />

id, Integer: The (unique) ID of the joined user.
name, String: The user name of the joined user.
status, (available): The status of the joined user. This should always be available for now.
seq, Integer: The seq that the client set for the original <user-join> request, if any.

Tells the client that a new user joined the session.

<user-rejoin id="user_id" name="name" status="status" seq="seq_id" />

id, Integer: The (unique) ID of the rejoined user. The client should alredy be aware of it.
name, String: The user name of the rejoined user.
status, (available): The status of the rejoined user. This should always be available for now.
seq, Integer: The seq that the client set for the original <user-join> request, if any.

Tells the client that an already existing, but unavailable, user rejoined the session.

<user-leave id="user_id" seq="seq_id" />

id, Integer: The ID of the user that left the session.
seq, Integer: The seq that the client set for the original <user-join> request, if any.

Tells the client that a user has left the session.

<session-close />

Tells the client that the session has been closed. This means, no more changes can be made. The client can try still to resubscribe if the document still exists in the directory.

Additional InfText? messages

State vectors

The state of a document is completely defined by a so-called state vector specifying how many operations each user did. For example, if user A made 2 requests and user B made 3 requests, the document has a certain state. All users that processed these 5 requests are in the same state. Note that it does not matter in which order the requests are processed (as long as the causal order is kept), which is the key concept behind the adOPTed algorithm.

Each user maintains a state vector for each other user that describes in which state that user is. This vector is updated every time a request is received from a particular user. This requires every user to send no-op requests if it has been inactive for some time, so that others still know the state of this user.

Also, each user maintains a request log in which all requests the user made are stored. This is required for transforming incoming requests from other users that were made in a different state of the document. Details to the adOPTed algorithm and how these transformations are performed can be found in the papers at http://portal.acm.org/citation.cfm?id=240305 and http://portal.acm.org/citation.cfm?doid=320297.320312.

Some attributes of the following messages describe such a state vector. The state vector has the form "user_id:processed_requests;user_id:processed_requests;[...]" where user_id is the ID of a user and processed_requests describe the number of requests that this user is guaranteed to have already processed.

User attributes

The following attributes are used in the <sync-user> and <join-user> requests for text sessions:

time, StateVector?: The current state vector of the user
caret: The position of the user's cursor, in characters, from the document beginning
selection: The number of characters selected, starting at the character caret. Negative means selection towards the beginning of the document.

TODO: Viewport

Synchronization

These are additional messages sent during synchronization:

<sync-request user="user_id" time="time">
 <operation />
</sync-request>

user, Integer: The ID of the user that made the request.
time, State Vector: The state at which the request was made.
operation: The operation performed by the request, see below.

Tells that at the given time a user made a request. This should be added to the request log and might be necessary to transform incoming operations or to compute Undo operations.

<sync-segment author="user_id">Text</sync-segment>

author, optional: The user ID of the user that wrote the text.
Text: The text that user wrote.

Synchronizes a part of the initial document that was written by a single user. The <sync-segment> messages should be sent in-order so the document can be reconstructed.

Independant

These messages are sent no matter whether being client or server.

<request user="user_id" time="time">
 <operation />
</request>

user, Integer: The ID of the user that made the request.
time, State Vector diff: Describes the document state at which the request was made.
operation: The operation performed by the request, see below.

Whenever a user issues a request the <request> message is sent. The user must have joined via the connection the request message comes from. <request> is sent to the whole subscription group. The time sent with this message is not absolute, but relative to the time from the last request of this user. For, example, if time contains the value "2:3;1:1", this means that since the last request of that user, it processed 3 requests from user 2 and one request from user 1. Note that the value for the user itself is therefore always zero, because there cannot be any requests inbetween them. This requires the requests from some user to arrive in-order, but it state vector components from inactive (or users that have left the session) need not to be transmitted all the time.

Operations

There are two types of operations. Such operations that modify the document and such that do not. For example, inserting a character into the document does modify it, but moving the cursor of a user does not. If the operation of a request does not modify the document, the request is not recorded in the request log.

The following operations are defined:

<insert pos="pos">text</insert>
<insert-caret pos="pos">text</insert-caret>

pos, Integer: The character offset at which to insert text.
text, String: The text to insert.

An operation that inserts new text into the document. The <insert-caret> version additionally places the cursor of the user that made the request behind the inserted text.

<delete pos="pos" len="len" />
<delete-caret pos="pos" len="len" />

pos, Integer: The character offset at which to start deleting characters
len, Integer: The number of characters to delete.

Deletes text from the buffer. This operation is only used in <request> messages. Again, <delete-caret> additionally places the cursor of the user that made the request to the place where characters have been deleted.

<delete pos="pos"><segment author="user_id">text</segment>[...]</delete>

pos, Integer: The character offset at which to start deleting characters.
segments: The text that was deleted, including author information, i.e. which user wrote what text.

Deletes text from the buffer and specifies what text is deleted. This operation is only used in <sync-request> messages. The synchronization client cannot deduce what text was actually deleted, but must be able to compute the reverse operation in case someone undoes the request. In a normal <request> message, other users can deduce what text was deleted by having a look at the document and which transformations were required to transform the request to the current state before the operation is actually executed.

<no-op />

Does nothing, and does especially not modify the document (see above). This is used when a user was inactive for some time to report its current state vector to the other users.

<move caret="pos" selection="len" />

pos, Integer: The character offset to place the cursor to.
len, Integer: The length of the selection area, in characters. Negative values mean selection towards the beginning of the document.

Changes the position of the user's cursor position and selection area. This operation does not modify the document.

<undo />
<undo-caret />

Undoes the last request of the user. The <undo-caret> version also places the user's cursor to the position where the operation was performed.

<redo />
<redo-caret />

Redoes the last request of the user. The <redo-caret> version also places the user's cursor to the position where the operation was performed.

Discussion

Please ask if things remain unclear.

Armin: Things I did not yet think about (too much): Access restriction, xmlns, user colors, viewport.

Download in other formats:

Plain Text