Skip to content
Snippets Groups Projects
HACKING.org 5.76 KiB
Newer Older
Qiantan Hong's avatar
Qiantan Hong committed
* Algorithm

Qiantan Hong's avatar
Qiantan Hong committed
Background reading: [[https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type][CRDT]]

Qiantan Hong's avatar
Qiantan Hong committed
This packages implements the Logoot split algorithm
~André, Luc, et al. "Supporting adaptable granularity of changes for massive-scale collaborative editing." 9th IEEE International Conference on Collaborative Computing: Networking, Applications and Worksharing. IEEE, 2013.~
    
The CRDT-ID blocks are implemented by text property ='crdt-id=. A continous range of text with the same ='crdt-id'= property represent a CRDT-ID block. The ='crdt-id= is a a cons of =(ID-STRING . END-OF-BLOCK-P)=, where
=ID-STRING= represent the CRDT-ID of the leftmost character in the block. If =END-OF-BLOCK-P= is =NIL=, the block is a non-rightmost segment splitted from a larger block, so insertion at the right of this block shouldn't be merged into the block by sharing the base CRDT-ID and increasing offset.

=ID-STRING= is a unibyte string representing a CRDT-ID (for efficient comparison).
Every two bytes represent a big endian encoded integer.
For base IDs, last two bytes are always representing site ID.
Stored strings are BASE-ID:OFFSETs. So the last two bytes represent offset,
and second last two bytes represent site ID.

* Protocol
Qiantan Hong's avatar
Qiantan Hong committed
  Text-based version
  (it should be easy to migrate to a binary version.  Using text for better debugging for now)
Qiantan Hong's avatar
Qiantan Hong committed

  Every message takes the form =(type . body)=

Qiantan Hong's avatar
Qiantan Hong committed
  type can be: insert delete cursor hello challenge sync desync overlay-(add,move,put,remove)
Qiantan Hong's avatar
Qiantan Hong committed
  - insert ::
Qiantan Hong's avatar
Qiantan Hong committed
    body takes the form =(buffer-name crdt-id position-hint content)=
    - =position-hint= is the buffer position where the operation happens at the site
      which generates the operation.  Then we can play the trick that start search
      near this position at other sites to speedup CRDT ID search
    - =content= is the string to be inserted
Qiantan Hong's avatar
Qiantan Hong committed
  - delete ::
Qiantan Hong's avatar
Qiantan Hong committed
    body takes the form =(buffer-name position-hint (crdt-id . length)*)=
Qiantan Hong's avatar
Qiantan Hong committed
  - cursor ::
Qiantan Hong's avatar
Qiantan Hong committed
    body takes the form
         =(buffer-name site-id point-position-hint point-crdt-id mark-position-hint mark-crdt-id)=
Qiantan Hong's avatar
Qiantan Hong committed
    =*-crdt-id= can be either a CRDT ID, or
      - =nil=, which means clear the point/mark
      - =""=, which means =(point-max)=
Qiantan Hong's avatar
Qiantan Hong committed
  - contact ::
Qiantan Hong's avatar
Qiantan Hong committed
    body takes the form
         =(site-id name address port)=
    when name is =nil=, clear the contact for this =site-id=
Qiantan Hong's avatar
Qiantan Hong committed
  - focus ::
Qiantan Hong's avatar
Qiantan Hong committed
    body takes the form =(site-id buffer-name)=
Qiantan Hong's avatar
Qiantan Hong committed
  - hello ::
Qiantan Hong's avatar
Qiantan Hong committed
    This message is sent from client to server, when a client connect to the server.
    body takes the form =(client-name &optional response)=
  - leave ::
    This message is sometime sent from client to server to indicate disconnection, 
    if the underlying proxy doesn't handle it properly.
    body takes the form =()=

Qiantan Hong's avatar
Qiantan Hong committed
  - challenge ::
Qiantan Hong's avatar
Qiantan Hong committed
    body takes the form =(salt)=
Qiantan Hong's avatar
Qiantan Hong committed
  - login ::
Qiantan Hong's avatar
Qiantan Hong committed
    It's always sent after server receives a hello message.
    Assigns an ID to the client
    body takes the form =(site-id session-name)=.
Qiantan Hong's avatar
Qiantan Hong committed
  - sync ::
Qiantan Hong's avatar
Qiantan Hong committed
    This message is sent from server to client to get it sync to the state on the server.
    Might be used for error recovery or other optimization in the future.
    One optimization I have in mind is let server try to merge all CRDT item into a single
    one and try to synchronize this state to clients at best effort.
    body takes the form =(buffer-name . crdt-id-list)=
Qiantan Hong's avatar
Qiantan Hong committed
    - =crdt-id-list= is generated from =CRDT--DUMP-IDS=
  - ready ::
    body takes the form =(buffer-name major-mode-symbol)=
    Indicates the end of a batch of synchronization messages
    (which usually contains some =cursor= messages, a =sync= message,
    and some =overlay-*= messages).
    The client should now try to enable =major-mode-symbol= in the
    synchronized buffer.

  - add ::
    Indicates that the server has started sharing some buffers.
    body takes the form =buffer-name-list=

  - remove ::
    Indicates that the server has stopped sharing some buffers.
    body takes the form =buffer-name-list=
Qiantan Hong's avatar
Qiantan Hong committed
    Request the server to resend =sync= message for a buffer.
    body takes the form =(buffer-name)=

Qiantan Hong's avatar
Qiantan Hong committed
  - overlay-add ::
Qiantan Hong's avatar
Qiantan Hong committed
    body takes the form 
#+BEGIN_SRC
(buffer-name site-id logical-clock species
  front-advance rear-advance
  start-position-hint start-crdt-id
  end-position-hint end-crdt-id)
#+END_SRC
Qiantan Hong's avatar
Qiantan Hong committed
  - overlay-move ::
Qiantan Hong's avatar
Qiantan Hong committed
    body takes the form
#+BEGIN_SRC
(buffer-name site-id logical-clock
  start-position-hint start-crdt-id
  end-position-hint end-crdt-id)
#+END_SRC
Qiantan Hong's avatar
Qiantan Hong committed
  - overlay-put ::
Qiantan Hong's avatar
Qiantan Hong committed
    body takes the form =(buffer-name site-id logical-clock prop value)=
Qiantan Hong's avatar
Qiantan Hong committed
  - overlay-remove ::
Qiantan Hong's avatar
Qiantan Hong committed
    body takes the form =(buffer-name site-id logical-clock)=
Qiantan Hong's avatar
Qiantan Hong committed
  
  - process ::
    body takes the form =(buffer-name string)=
    Sent from client to server, request sending =string= 
    to the process buffer associated to =buffer-name=.
Qiantan Hong's avatar
Qiantan Hong committed
* Emacs as a collaborative operating system

The goal: With a few annotations, developer should be able to make any Emacs application 
collaboration-powered. Emacs should be one of the most powerful collaboration platforms.

How: There're plenty of Emacs applications centered around the buffer and buffer-local-variables.
By implementing synchronization primitives for all components in a buffer,
pretty much everything can be made collaborative.
Synchronize arbitrary buffer-local-variable reasonably is hard, but user annotations can help.

** TODO list
   - [X] synchronize buffer text (insert/delete)
   - [X] synchronize overlays
   - [-] synchronize major/minor modes
     + [X] initial synchronization of major modes
     + [ ] toggle minor modes on the fly
     + [ ] change major modes on the fly
   - [ ] set of synchronization primitives for buffer local variables
     + [ ] server dictated
     + [ ] a library of CRDTs
   - [ ] synchronize text properties (any use case for this?)
   - [ ] synchronize markers (any use case for this?)