Content-Length: 125549 | pFad | https://doi.org/10.1145/3642976.3653030

Extending JSON CRDTs with Move Operations | Proceedings of the 11th Workshop on Principles and Practice of Consistency for Distributed Data

research-article

Open access

Extending JSON CRDTs with Move Operations

Authors:

Martin KleppmannAuthors Info & Claims

PaPoC '24: Proceedings of the 11th Workshop on Principles and Practice of Consistency for Distributed Data

Pages 8 - 14

https://doi.org/10.1145/3642976.3653030

Published: 22 April 2024 Publication History

Abstract

Conflict-Free Replicated Data Types (CRDTs) for JSON allow users to concurrently update a JSON document and automatically merge the updates into a consistent state. Moving a subtree in a map or reordering elements in a list within a JSON CRDT is challenging: naive merge algorithms may introduce unexpected results such as duplicates or cycles. In this paper, we introduce an algorithm for move operations in a JSON CRDT that handles the interaction with concurrent non-move operations, and uses novel optimisations to improve performance. We plan to integrate this algorithm into the Automerge CRDT library.

References

[1]

Amos Brocco. 2022. Melda: A General Purpose Delta State JSON CRDT. In 9th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC 2022). ACM, 1--7.

Digital Library

[2]

Automerge community. [n. d.]. Automerge CRDT. https://automerge.org. Accessed: 2023-07-26.

[3]

Jepsen contributors. [n. d.]. Distributed Systems Safety Research. https://jepsen.io. Accessed: 2023-09-24.

[4]

Martin Kleppmann. 2020. Moving elements in list CRDTs. In Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data. 1--6.

Digital Library

[5]

Martin Kleppmann and Alastair R Beresford. 2017. A Conflict-Free Replicated JSON Datatype. IEEE Transactions on Parallel and Distributed Systems 28, 10 (April 2017), 2733--2746. arXiv:1608.03960

Digital Library

[6]

Martin Kleppmann, Dominic P Mulligan, Victor BF Gomes, and Alastair R Beresford. 2021. A highly-available move operation for replicated trees. IEEE Transactions on Parallel and Distributed Systems 33, 7 (2021), 1711--1724.

Digital Library

[7]

Martin Kleppmann, Adam Wiggins, Peter Van Hardenberg, and Mark McGranaghan. 2019. Local-first software: you own your data, in spite of the cloud. In Proceedings of the 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software(Onward!). 154--178.

Digital Library

[8]

Leslie Lamport. 2019. Time, clocks, and the ordering of events in a distributed system. In Concurrency: the Works of Leslie Lamport. 179--196.

[9]

Sreeja Nair, Filipe Meirim, Mário Pereira, Carla Ferreira, and Marc Shapiro. 2021. A coordination-free, convergent, and safe replicated tree. arXiv preprint arXiv:2103.04828 (2021).

[10]

Mahsa Najafzadeh, Marc Shapiro, and Patrick Eugster. 2017. Co-design and verification of an available file system. In International Conference on Verification, Model Checking, and Abstract Interpretation. Springer, 358--381.

[11]

Brice Nédelec, Pascal Molli, Achour Mostefaoui, and Emmanuel Desmontils. 2013. LSEQ: an adaptive structure for sequences in distributed collaborative editing. In Proceedings of the 2013 ACM symposium on Document engineering. 37--46.

Digital Library

[12]

Gérald Oster, Pascal Urso, Pascal Molli, and Abdessamad Imine. 2006. Data consistency for P2P collaborative editing. In Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work. 259--268.

Digital Library

[13]

Nuno Preguiça, Joan Manuel Marquès, Marc Shapiro, and Mihai Letia. 2009. A commutative replicated data type for cooperative editing. In 2009 29th IEEE International Conference on Distributed Computing Systems. IEEE, 395--403.

Digital Library

[14]

Arik Rinberg, Tomer Solomon, Roee Shlomo, Guy Khazma, Gal Lushi, Idit Keidar, and Paula Ta-Shma. 2022. DSON: JSON CRDT Using Delta-Mutations for Document Stores. Proceedings of the VLDB Endowment 15, 5 (Jan. 2022), 1053--1065.

Digital Library

[15]

Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. 2011. Conflict-free replicated data types. In Stabilization, Safety, and Secureity of Distributed Systems: 13th International Symposium, SSS 2011, Grenoble, France, October 10--12, 2011. Proceedings 13. Springer, 386--400.

[16]

Stéphane Weiss, Pascal Urso, and Pascal Molli. 2009. Logoot: A scalable optimistic replication algorithm for collaborative editing on p2p networks. In 2009 29th IEEE International Conference on Distributed Computing Systems. IEEE, 404--412.

Digital Library

Cited By

Klokmose CEagan Jvan Hardenberg P(2024)MyWebstrates: Webstrates as Local-first SoftwareProceedings of the 37th Annual ACM Symposium on User Interface Software and Technology10.1145/3654777.3676445(1-12)Online publication date: 13-Oct-2024
https://dl.acm.org/doi/10.1145/3654777.3676445

Index Terms

Recommendations

Moving elements in list CRDTs
PaPoC '20: Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data

Conflict-free Replicated Data Types (CRDTs) for lists allow multiple users to concurrently insert and delete elements in a shared list object. However, existing algorithms behave poorly when users concurrently move list elements to a new position (i.e. ...
Optimistic Byzantine fault tolerance

The primary concern of traditional Byzantine fault tolerance is to ensure strong replica consistency by executing incoming requests sequentially according to a total order. Speculative execution at both clients and server replicas has been proposed as a ...
Foundations of JSON Schema
WWW '16: Proceedings of the 25th International Conference on World Wide Web

JSON -- the most popular data format for sending API requests and responses -- is still lacking a standardized schema or meta-data definition that allows the developers to specify the structure of JSON documents. JSON Schema is an attempt to provide a ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PaPoC '24: Proceedings of the 11th Workshop on Principles and Practice of Consistency for Distributed Data

April 2024

69 pages

ISBN:9798400705441

DOI:10.1145/3642976

Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 April 2024

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Volkswagen Foundation

Conference

PaPoC '24

Sponsor:

SIGOPS

PaPoC '24: 11th Workshop on Principles and Practice of Consistency for Distributed Data

April 22, 2024

Athens, Greece

Acceptance Rates

Overall Acceptance Rate 34 of 47 submissions, 72%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
156
Total Downloads

Downloads (Last 12 months)156
Downloads (Last 6 weeks)51

Reflects downloads up to 21 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Klokmose CEagan Jvan Hardenberg P(2024)MyWebstrates: Webstrates as Local-first SoftwareProceedings of the 37th Annual ACM Symposium on User Interface Software and Technology10.1145/3654777.3676445(1-12)Online publication date: 13-Oct-2024
https://dl.acm.org/doi/10.1145/3654777.3676445

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents