Distributed collaborative editors such as Google Docs or Etherpad allow to distribute the work across time, space and organizations. In this paper, we focus on distributed collaborative editors based on the Con ict-free Replicated Data Type approach (CRDT). CRDTs encompass a set of well-known data types such as sets, graphs, sequences, etc. CRDTs for sequences model a document as a set of elements (character, line, paragraph, etc.) with unique identi ers, providing two commutative update operations: insert and delete. The identi ers of elements can be either of xed-size or variable-size. Recently, a strategy for assigning variable-size identi ers called LSEQ has been proposed for CRDTs for sequences. LSEQ lowers the space complexity of variable-size identi ers CRDTs from linear to sub-linear. While experiments show that it works locally, it fails to provide this bound with multiple users and latency. In this paper, we propose h-LSEQ, an improvement of LSEQ that preserves its space complexity among multiple collaborators, regardless of the latency. Ultimately, this improvement allows to safely build distributed collaborative editors based on CRDTs. We validate our approach with simulations involving latency and multiple users.
This work is licensed under the Creative Commons AttributionShareAlike 3.0 Unported License (CC BY-SA 3.0). To view a copy of the license, visit http://creativecommons.org/licenses/by-sa/3.0/.
Distributed collaborative editors allow to distribute the
work across space, time and organizations. Some trending
editors such as Google Docs [
The CRDTs belong to the optimistic replication [
We distinguish two types of sequence CRDTs: (i) The
tombstone CRDTs [
To overcome their respective limitations, these approaches
need an additional protocol [
Recently, LSEQ [
The contributions of this paper are: (i) experiments that highlight the negative e ect of multiple users edition on the size of LSEQ identi ers (ii) experiments that highlight that an increasing latency does not have a negative impact on the size of LSEQ identi ers. (iii) an improvement of LSEQ called h-LSEQ that extends the single user sub-linear upper bound on space complexity to any number of users, regardless of the latency, and without any additional cost.
Ultimately, h-LSEQ allows distributed collaborative editors to safely use variable-size identi ers CRDTs.
The rest of the paper is organized as follow: Section 2 details variable-size identi ers CRDTs for sequences, the allocation strategy LSEQ, and highlights the motivation of this paper. Section 3 presents h-LSEQ a combination of LSEQ and a hash-based choice strategy to overcome the LSEQ limitations. Section 4 shows the results of experiments over LSEQ and h-LSEQ considering latency and multiple users. Finally, Section 5 reviews the related works.
Con ict-free Replicated Data Types belong to the
optimistic replication approach [
To provide the convergence property, CRDTs for sequences
model a document as a set of couples helt; idi where id 2
(I; <id), <id being a strict and dense total order over I,
and elt any element, e.g., a character, a line. Two
commutative operations allow to update the document:
{ insert(p 2 I; elt; q 2 I) that generates an identi er idelt
with p < idelt < q and adds helt; idelti to the document.
{ delete(idelt) that removes helt; idelti from the document.
The variable-size identi ers CRDTs [
Despite the fact that numerous experiments have been
performed using LSEQ including real documents extracted
from Wikipedia, they did not include any concurrency.
Although, Wikipedia's revisions already present a serialization
of the document without explicit concurrency, experiments
with this type of documents are of great importance [
De nition 1 from [
The identi ed problem concerns the preservation of the space complexity of LSEQ from single user to multiple users edition. Using multiple antagonist strategies without any coordination between collaborators leads to a quadratic growth of identi ers. Consequently, providing a mechanism of agreement in the choice of strategies would greatly improve LSEQ as well as any composition of allocation strategies. Furthermore, such improvement would make variable-size identi ers CRDTs actually usable in the distributed collaborative editing context.
The h-LSEQ allocation strategy is mainly based on LSEQ, they di er in the strategy choice component. Using LSEQ, each replica involved in the collaboration makes independent random choices. However, Section 2 showed that such strategy fails to provide sub-linearly upper-bounded identi ers in collaboration involving multiple users.
The solution is to reach a global agreement over replicas on which is the allocation strategy used at each depth of the underlying tree model. Since LSEQ aims to get rid of protocols related to garbage collecting mechanisms, any solution that requires additional communication is inconceivable.
We propose to use a hash strategy choice component which have the same local behaviour than the original random strategy choice, but it also provides the required implicit global agreement. Indeed, instead of synchronizing the set of users, we provide an a priori agreement by the mean of a hash function. This agreement avoids the possibility of antagonist choices which would have led to a bad global allocation of identi ers. Furthermore, it does not introduce any additional cost to LSEQ.
Algorithm 1 details the h-LSEQ allocation strategy. The
changes over LSEQ are simply highlighted. This section
explains this algorithm. Extracted from [
The functions boundary+ and boundary are two allocation strategies, note that they do not strictly respect the alloc function signature in order to factorize the computation of depth and step. 3.1
The strategy choice function is surjective and its signature is: h(depth 2 N ) : N. The returned value corresponds to an allocation strategy unique identi er. The algorithm of the allocation strategy h-LSEQ follows 3 steps: 1. lines 8-11: computes the depth of the future identi ers to allocate 2. line 13: calls the strategy choice function h using the depth 3. line 15: calls the allocation strategy using the identi er returned by h
The strategy choice function returns strategy identi ers following a uniform law. Thus, frequencies of appearance of each strategy are equal and does not favor any editing behaviour. Furthermore, the unpredictability due to randomness preserves the model from intentional and malicious attacks.
The hash function ful lls the requirement of the strategy choice function h. However, contrarily to the random strategy choice component, it requires an initialization. Indeed, the creator of the document must share a hidden seed (cf. line 2) within the document that each collaborator will use to generate the hash function speci c to this document. In Algorithm 1 at line 21, we simply use the common random function initialized with the seed and the depth. Algorithm 1 h-LSEQ allocation function 1: let boundary := 10 2: let seed := 123456789
Init with document 3: let S := fh0; boundary+i; h1; boundary ig; 4: map<id, allocation strategy> 5: 6: function alloc(p, q 2 I) 7: let depth := 0; interval := 0; 8: while (interval < 1) do Not enough for 1 insert 9: depth + +; 10: interval := pref ix(q; depth) pref ix(p; depth) 1; 11: end while 12: let step := min(boundary; interval); maximum step to stay between p and q
let idStrat := h(depth); 13: 14: Call the hash function 15: let id := S:get(idStrat):invoke(p; q; depth; step); 16: Call the allocation strategy according to hash 17: return id; 18: end function 19: 20: function h ( depth 2 N ) Process the 21:
return Random(seed depth):nextInt(0; 1); 22: end function 23: 24: function boundary+(p, q 2 I, depth, step 2 N ) 25: let addV al := RandInt(0; step) + 1; 26: return pref ix(p; depth) + addV al; 27: end function 28: 29: function boundary{(p, q 2 I, depth, step 2 N ) 30: let subV al := RandInt(0; step) + 1; 31: return pref ix(q; depth) subV al; 32: end function 33: 34: function prefix(id 2 I, depth 2 N ) 35: let idCopy := [ ]; 36: for (cpt := 1 to depth) do 37: if (cpt < id:size) then Copy the value 38: idCopy := idCopy:append(id:at(cpt)); 39: else Add 0 encoded in the right base 40: idCopy := idCopy:append(0base(cpt)); 41: end if 42: end for 43: return idCopy; 44: end function 3.2
Each collaborator generates the same hash function thanks to the shared seed. Also, all collaborators use the same mapping id ! allocation strategy (cf. line 3). Consequently, all hash functions map the same depth to the same allocation strategies. The idea is to reach a consensus on which strategies to employ in order to avoid the waste of identi ers' space due to the choice of antagonist strategies.
Figure 2 highlights the di erences between the original random strategy choice and our hash strategy choice. Both cases present two collaborators inserting 2 elements one after the other. The expected result is the sequence \abcd". Hence, Collaborator 1 generates the \a" and \c" and Collaborator 2 generates the \b" and \d". In both cases they draw the same numbers. However, in the case of random strategy choice, one collaborator randomly chooses boundary+ twice while the other randomly chooses boundary{ twice. When the editing behaviour is monotonic, the size of identi ers
9
30
quickly grows. On the opposite, the collaborators using
hLSEQ implicitly agree on using boundary+ at depth-1,
consequently the allocation follows the properties of the one
user edition presented in [
The next section aims to corroborate our assumptions by performing experiments on di erent setups with varying the number of collaborators and the latency of the network.
This section is composed of two parts. First, the experimentation focuses on the in uence of the number of collaborators on the size of LSEQ and h-LSEQ identi ers. A set of synthetic collaborators generates a document by successively performing insert operations at the end. This experiment aims to show the behaviour of the two strategy choices, and compare the results with the expected sub-linear space complexity.
The second part of experiments consists in highlighting the e ect of latency on a document edited by multiple users. Once again, it aims to compare LSEQ and h-LSEQ and to show the impact of concurrency on the average size of identi ers in the document.
The experiments focus on the digit bit-length of generated identi ers. Indeed, all variable-size CRDTs rely on source and clock to guarantee the unicity of identi ers, nevertheless, the space complexity mainly depends on the digit choice made by the allocation strategy.
To perform these experiments, we implemented a simulation framework called HumbleSimulator. The sources are available on the Github platform under the terms of the GPL licence 1. 4.1
Objective: show that the random strategy choice without taking into account the strategies employed by other collaborators leads to a quick growth in the size of identiers. On the opposite, when all collaborators uses a common allocation strategy at a given depth, the space complexity remains sub-linearly upper-bounded.
Description: we evaluate LSEQ and h-LSEQ strategies on a group of 10 collaborators. Thus, the setups are (i) a random strategy choice (rand) and (ii) a hash strategy choice 1. https://github.com/Chat-Wane/HumbleSimulator revision 250 LSEQ+rand 200 LSEQ+hash tghn 150 e litbd 100 i 50 (hash). Both of these setups use boundary+ and boundary{ and have the same variable values boundary = 10 and base = 24+depth. A set of 10 collaborators produces a document of 100 lines by performing 10 insert operations each.
Results: Figure 3 shows on the top part the spectrum of
the synthetic document, i.e., the revision date of each line.
Since the bars are getting taller when they are closer of the
end of the document, it indicates that the users edited at
the end monotonically. On the second part of the Figure 3,
it shows the identi er bit-length associated to each line. We
observe that the identi ers of rand setup quickly increase
while the hash identi ers remain similar to the ones in the
experiment made for one user in [
Reasons: both setups use boundary+ and boundary{ allocation strategies. However, each collaborator in the rand setup makes independent choices of allocation strategies when required. Thus, if a collaborator chooses a particular strategy, and another user chooses the antagonist strategy, then a large number of identi ers is wasted when their operations are delivered to each other. On the other hand, when the same hash function spread over all collaborators generates the same strategy choices, it keeps the random behaviour locally and also makes an implicit agreement on which strategy to employ at any given depth. 4.2
Objective: show that increasing the latency, i.e., the time between the generation and the delivery of an operation, does not imply a growth in the size of identi ers. On the contrary, when the latency increases, the average size of allocated identi ers decreases. This behaviour is expected for LSEQ and h-LSEQ strategies.
Description: we simulate the production of a 100 lines document by a set of 10 collaborators. Each one of these collaborators performs 10 insert operations at the end of the LSEQ+rand LSEQ+hash 100 200 300 400 500 600
700 latency document. The users generate operations following the Poisson distribution of parameter = 100, i.e., users more likely generate an operation after 100 rounds (arbitrary unit) from their previous operation. Measurements are done at a latency of 5, 10, 20, 40, 80, 160, 320, 640 rounds. They concern the average bit-length of identi ers in the document. We evaluate two setups: the random strategy choice (rand) and the hash strategy choice (hash). Both setups use the allocation strategies boundary+ and boundary with boundary = 10 and departure base = 24+depth.
Results: Figure 4 shows the results of the latency experiments. As expected, the two setups allocate identi ers with an average bit-length that quickly decreases when the latency increases. Therefore, the latency does not badly a ect LSEQ and h-LSEQ allocation strategies. Also, it conrms observations made in the previous experiment: hash performs better than rand, especially under low latency.
Reasons: increasing the latency delays the arrival of operations to the remote collaborators. Thus, each collaborator works locally until operations generated by other users are delivered. Considering the extreme case with the maximum latency, each collaborator generates his 10 insertions, and then merges the others' 90 operations. Consequently, the 100 operations share the same space, i.e., the digit part of identi ers can be the same for multiple elements, and the total order is maintained by the source and clock. 4.3
The experiments evaluated the e ect of concurrency on the average bit-length of identi ers by varying the number of collaborators and the latency. They showed that an implicit and a priori agreement on allocation strategy choice is required to maintain the sub-linear upper-bound on space complexity. Employing the same hash function to choose the allocation strategy permits to reach this agreement. Consequently, the improvement of LSEQ called h-LSEQ can be safely used in distributed collaborative editing. The latency experiment shows that increasing the latency parameter only results in sharing the identi er space, and consequently lowers the size of identi ers. As a corollary, considering an immediate delivery of operations constitutes an upper-bound on the behaviour of the overall system for any latency. 5.
Current distributed collaborative editors use optimistic
replication [
Operational Transform approach (OT) and Con ict-free Replicated Data Type approach (CRDT) belong to the optimistic class of replication. While CRDTs share the computational cost of operations between the local and remote parts of the replication protocol, the OT approaches prefer to o er free local generation and pay an additional cost on the integration of remote operations. Since the number of remote operations quadratically grows when the number of collaborators increases, the CRDTs scale better than OT approaches.
We distinguish two classes of CRDTs for sequences. The
tombstone based CRDT approaches use death certi cate on
removed elements. Henceforth, these elements are hidden
to the users, but still remain in the underlying model and
undermine the performance. For instance, the number of
tombstones in popular or controversial pages in Wikipedia
pages would be very high due to vandalism and recoveries.
The representatives of this class of CRDTs are WOOT [
To get rid of these marked elements, the tombstone based
CRDTs require additional protocols related to garbage
collecting mechanisms. In [
The alternative to tombstones is the variable-size
identiers CRDT approach. These CRDTs directly encode the
total order of elements into their unique identi ers. Thus,
they do not require tombstones. However, the identi ers
can grow. In Logoot [
The LSEQ approach uses two antagonist allocation
strategies. Although paper [
In this paper, we propose to replace the random strategy choice component of LSEQ by a hash-based choice strategy to reach an implicit consensus on which strategy to employ. This con guration called h-LSEQ, does not require additional computation and extends the sub-linear complexity bound of LSEQ from a single user to multiple collaborators regardless of the latency. Thus, h-LSEQ constitutes a safe allocation strategy for sequences CRDTs, even in concurrent cases.
In this paper, we presented an improvement of the allocation strategy LSEQ called h-LSEQ. Contrarily to the original approach, our con guration supports multiple users regardless of the latency. Indeed, replacing the random strategy choice by the hash-based choice strategy allows to reach a global sub-linear upper-bound on space complexity. As a consequence, distributed collaborative editors can safely use h-LSEQ and show better scalability than current trending editors such as Google Docs, Etherpad, etc.
The hash-based choice strategy is a common function over participants that maps a depth in the underlying tree to an allocation strategy identi er. This surjective function initialized with a shared seed allows to reach an agreement on strategies with no additional synchronization cost. Consequently, there is no loss in the identi ers' space due to antagonist allocation strategies.
This paper highlights the importance of multiple users analysis in CRDTs for sequences, particularly in the case of multiple underlying allocation strategies. We also showed that latency does not badly a ect the size of identi ers in variable-size identi ers CRDTs. However, we performed experiments with synthetic documents in order to show the general behaviour of the allocation without considering semantically consistent documents.
Future works include the formal proof of the sub-linear upper-bound on space complexity of h-LSEQ. A probability analysis of the worst-case scenario is mandatory to show that it seldom happens. We plan to experiment h-LSEQ on a corpus of real documents including multiple collaborators and concurrency. Finally, we aim to build a real distributed collaborative editor based on a variable-size identi ers CRDT using h-LSEQ as allocation strategy.