Submitted: 14 June 2018
Rejected: 25 July 2018
The paper reports on applied research with respect to replication management middleware for web-based systems. The authors propose to apply CRDTs and combine them with merkle trees in order to enable an appropriate consistency protocol in the context of two web app scenarios.
The topics addressed by the authors are generally interesting in the context of web apps (as well as general distributed systems and middleware). While there is certainly considerable overlap with the conference focus, the authors do not explicitly relate their work to service computing.
The proposed approach mainly contributes a practical application of well known replication techniques. However some questions remain with respect to soundness. E.g. as regards the CRDT, the paper is quite sketchy but it seems to be missing lists. As the authors claim to represent JSON, such structure would be required to consider JSON arrays.
Also conflict resolution strategies, i.e. merge semantics, are not explicitly discussed but boil down to last-in/write-win. However some form of string editing seems required in the given scenarios. There are many related CRDT algorithms (LSEQ, Logoot, WOOT, Treedoc) for lists that could be used here.
In general, there is a large body of literature on related conceptual
work that I don't see well addressed here. E.g.
- Martin Kleppmann, Alastair R. Beresford, "A Conflict-Free Replicated
JSON Datatype",
https://arxiv.org/abs/1608.03960
In terms of presentation there is room for improvements. Generally there is sufficient structure and the writing is fair. However, the paper is sketchy in parts (e.g. section 3) and generally misses depth of discussion with respect to both formal grounding and illustrative examples. On the other hand, too much space (2 pages) is used for extensive diagrams with little information.
Minor issues:
The paper is very clear when stating the problem it seeks to solve, and in its presentation of the model through the description of the two case studies of continuous and sporadic connections. It proposes to augment state based Confict-free Replicated Data Types (CvRDTs) with the use of Merkle trees. These would help in the exchange of states between a client and a server by avoiding the exchange of unmodified data.
The potentially ever increasing size of the metadata of CvRDTs, and so the size of the messages exchanged by the nodes, is an important problem that has to be addressed when building a system that relies on them, and the Merkle tree could be an efficient solution.
However the architecture and deployment sections could be made clearer by presenting the tree synchronization protocol through the conventional algorithm pseudocode.
The evaluation of the system lacks a point of comparison and should be extended in scope. Some of the others systems or techniques that are present in the related works sections could have been evaluated alongside OWebSync.
The propagation time of an update to all clients also seems to be the main aim of the experiments. The evolution of the size of the messages could have been another comparison point. An expected benefit of the Merkle tree would be the reduction of the message's overhead during state exchange, but it has also been noted in the paper that the tree synchronization protocol can be very verbose. What benefits does the system offer when compared to a CvRDT exchange without Merkle tree, and does that hold when the system has been running for longer and the state exchange grows?
The experimental setup of having all browsers co-located with the server in an OpenStack does not seem faithful to the model of devices at the edge of the network, maybe some latencies could be artificially induced in the system.
Regarding the completeness of the related works, here are a couple of papers that could be included:
In this paper, the authors propose OWebSync, a CRDT-based data synchronization middleware to reconcile state for web applications. The authors claim that the middleware is general purpose and can be used by generic web applications to reconcile online and local state after offline updates. The Middleware consists of a client-side and a server-side component, where a middleware-client only interacts with the middleware's client-side component. The server-side component is only relevant for access control and to reduce communication complexity, since it avoid peer-to-peer coordination between clients. By applying a last-write wins strategy to a shared data-object, eventual consistency between clients is ensured.
The paper is generally well structured and addresses an interesting problem. However, the paper leaves open many questions the concrete design of the conflict-free JSON data type, the general advantages over a shared client-side last-write-wins data structure and the performance in web-scale deployments:
While section three has the title "Convergent replicated data types with Merkle-trees", the combination of Merkle-trees and the introduced CRDTs (from the Shapiro paper) is not explained. It is unclear how the JSON structure looks like in detail and which operations are supported in a non-conflicting way. Fig. 1 shows how the Shapiro CRDTs are constructed internally. Instead of explaining the used data types in detail, it would be beneficial to refer the reader to the original Shapiro paper for details and rather explain the core data structure OWebSync is based on. Furthermore, storage and computation overhead due to tombstones should likely be discussed. Not handling tombstones will eventually lead to clients failing. Use of storage space over time would be an interesting aspect of the evaluation.
How is a using a LWW register for all data in the JSON-Object superior to simple, traditional timestamp-based reconciliation? Isn't this what the proposal boils down to? Such a last-write-wins data structure is not really novel and used in various systems, e.g., Cassandra. (I'm partially guessing/making assumptions here, since the JSON data structure composed of CRDTs is not defined in detail.) On a related note: Since state is kept and managed on the client side, couldn’t clients overrule other clients and server state by lying about their timestamp?
The evaluation is based on max. 24 clients and 1 server. This is not realistic for web applications. How does the middleware perform for large numbers of clients? What is the expected scalability?
The system architecture resembles the system presented in the following paper, which is relevant related work: Eberhardt, Jacob, Dominik Ernst, and David Bermbach. "SMAC: State Management for Geo-Distributed Containers."
Besides the above mentioned points, the general idea of CRDT-based client-side shared data structures has been discussed before and should not be considered novel. Advantages of the proposed CRDT-based JSON data structure over commonly applied LWW-strategies should be highlighted and described in more detail. Web-scale performance benchmarks that highlight advantages over an existing approach would reinforce the arguments. Focusing on the specific requirements of web-scale applications and how employing such data structures could be beneficial in that context could be a promising direction.
All reviewers point out a lack of discussion of important technical details (such as JSON structure) and a lack of overall novelty of the proposed approach. Still, the paper tackles an interesting topic and the approach is promising.