{"owner":"fetsorn","repo":"pijul-spec","channel":"main","channels":["main"],"can_delete":true,"inode":{"File":{"path":[{"basename":"resources","pos":"4NBQFWD6E7ZJM.OVHAA","meta":576},{"basename":"20220210_designing_data_structures_for_collaborative_apps.md","pos":"4NBQFWD6E7ZJM.MUFQ6","meta":0}],"file":"# Document Title\n\n\nDesigning Data Structures for Collaborative Apps\n\nMatthew Weidner | Feb 10th, 2022\nHome | RSS Feed\nKeywords: collaborative apps, CRDTs, composition\n\n I’ve put many of the ideas from this post into practice in a library, Collabs. You can learn more about Collabs, and see how open-source collaborative apps might work in practice, in my Local-First Web talk: Video, Slides, Live demo.\n\n\nSuppose you’re building a collaborative app, along the lines of Google Docs/Sheets/Slides, Figma, Notion, etc. One challenge you’ll face is the actual collaboration: when one user changes the shared state, their changes need to show up for every other user. For example, if multiple users type at the same time in a text field, the result should reflect all of their changes and be consistent (identical for all users).\n\nConflict-free Replicated Data Types (CRDTs) provide a solution to this challenge. They are data structures that look like ordinary data structures (maps, sets, text strings, etc.), except that they are collaborative: when one user updates their copy of a CRDT, their changes automatically show up for everyone else. Each user sees their own changes immediately, while under the hood, the CRDT broadcasts a message describing the change to everyone else. Other users see the change once they receive this message.\n\nCRDTs broadcast messages to relay changes\n\nNote that multiple users might make changes at the same time, e.g., both typing at once. Since each user sees their own changes immediately, their views of the document will temporarily diverge. However, CRDTs guarantee that once the users receive each others’ messages, they’ll see identical document states again: this is the definition of CRDT correctness. Ideally, this state will also be “reasonable”, i.e., it will incorporate both of their edits in the way that the users expect.\n\n In distributed systems terms, CRDTs are Available, Partition tolerant, and have Strong Eventual Consistency.\n\n\nCRDTs work even if messages might be arbitrarily delayed, or delivered to different users in different orders. This lets you make collaborative experiences that don’t need a central server, work offline, and/or are end-to-end encrypted (local-first software).\n\nGoogle Docs doesn't let you type while offline\n\nCRDTs allow offline editing, unlike Google Docs.\n\nI’m particularly excited by the potential for open-source collaborative apps that anyone can distribute or modify, without requiring app-specific hosting.\n# The Challenge: Designing CRDTs\n\nHaving read all that, let’s say you choose to use a CRDT for your collaborative app. All you need is a CRDT representing your app’s state, a frontend UI, and a network of your choice (or a way for users to pick the network themselves). But where do you get a CRDT for your specific app?\n\nIf you’re lucky, it’s described in a paper, or even better, implemented in a library. But those tend to have simple or one-size-fits-all data structures: maps, text strings, JSON, etc. You can usually rearrange your app’s state to make it fit in these CRDTs; and if users make changes at the same time, CRDT correctness guarantees that you’ll get some consistent result. However, it might not be what you or your users expect. Worse, you have little leeway to customize this behavior.\n\nAnomaly in many map CRDTs: In a collaborative todo-list, concurrently deleting an item and marking it done results in a nonsense list item with no text field.\n\nIn many map CRDTs, when representing a todo-list using items with \"title\" and \"done\" fields, you can end up with an item {\"done\": true} having no \"title\" field. Image credit: Figure 6 by Kleppmann and Beresford.\n\nSimulated user complaint: In a collaborative spreadsheet, concurrently moving a column and entering data might delete the entered data. If you don't control the CRDT implementation, then you can't fix this.\n\nIf a user asks you to change some behavior that comes from a CRDT library, but you don't understand the library inside and out, then it will be a hard fix.\n\nThis blog post will instead teach you how to design CRDTs from the ground up. I’ll present a few simple CRDTs that are obviously correct, plus ways to compose them together into complicated whole-app CRDTs that are still obviously correct. I’ll also present principles of CRDT design to help guide you through the process. To cap it off, we’ll design a CRDT for a collaborative spreadsheet.\n\nUltimately, I hope that you will gain not just an understanding of some existing CRDT designs, but also the confidence to tweak them and create your own!\n# Basic Designs\n\nI’ll start by going over some basic CRDT designs.\n# Unique Set CRDT\n\nOur foundational CRDT is the Unique Set. It is a set in which each added element is considered unique.\n\nFormally, the user-facing operations on the set, and their collaborative implementations, are as follows:\n\n add(x): Adds an element e = (t, x) to the set, where t is a unique new tag, used to ensure that (t, x) is unique. To implement this, the adding user generates t, e.g., as a pair (device id, device-specific counter), then serializes (t, x) and broadcasts it to the other users. The receivers deserialize (t, x) and add it to their local copy of the set.\n delete(t): Deletes the element e = (t, x) from the set. To implement this, the deleting user serializes t and broadcasts it to the other users. The receivers deserialize t and remove the element with tag t from their local copy, if it has not been deleted already.\n\nIn response to user input, the operator calls \"Output message\". The message is then delivered to every user's \"Receive & Update display\" function.\n\nThe lifecycle of an add or delete operation.\n\nWhen displaying the set to the user, you ignore the tags and just list out the data values x, keeping in mind that (1) they are not ordered (at least not consistently across different users), and (2) there may be duplicates.\n\nExample: In a collaborative flash card app, you could represent the deck of cards as a Unique Set, using x to hold the flash card’s value (e.g., its front and back strings). Users can edit the deck by adding a new card or deleting an existing one, and duplicate cards are allowed.\n\nWhen broadcasting messages, we require that they are delivered reliably and in causal order, but it’s okay if they are arbitarily delayed. (These rules apply to all CRDTs, not just the Unique Set.) Delivery in causal order means that if a user sends a message m after receiving or sending a message m’, then all users delay receiving m until after receiving m’. This is the strictest ordering we can implement without a central server and without extra round-trips between users, e.g., by using vector clocks.\n\nMessages that aren’t ordered by the causal order are concurrent, and different users might receive them in different orders. But for CRDT correctness, we must ensure that all users end up in the same state regardless, once they have received the same messages.\n\nFor the Unique Set, it is obvious that the state of the set, as seen by a specific user, is always the set of elements for which they have received an add message but no delete messages. This holds regardless of the order in which they received concurrent messages. Thus the Unique Set is correct.\n\n Note that delivery in causal order is important—a delete operation only works if it is received after its corresponding add operation.\n\n\nWe now have our first principle of CRDT design:\n\nPrinciple 1. Use the Unique Set CRDT for operations that “add” or “create” a unique new thing.\n\nAlthough it is simple, the Unique Set forms the basis for the rest of our CRDTs.\n\n Aside. Traditionally, one proves CRDT correctness by proving that concurrent messages commute—they have the same effect regardless of delivery order (Shapiro et al. 2011)—or that the final state is a function of the causally-ordered message history (Baquero, Almeida, and Shoker 2014). However, as long as you stick to the techniques in this blog post, you won’t need explicit proofs: everything builds on the Unique Set in ways that trivially preserve CRDT correctness. For example, a deterministic view of a Unique Set (or any CRDT) is obviously still a CRDT.\n\n\n Aside. I have described the Unique Set in terms of operations and broadcast messages, i.e., as an operation-based CRDT. However, with some extra metadata, it is also possible to implement a merge function for the Unique Set, in the style of a state-based CRDT. Or, you can perform VCS-style 3-way merges without needing extra metadata.\n\n\n# List CRDT\n\nOur next CRDT is a List CRDT. It represents a list of elements, with insert and delete operations. For example, you can use a List CRDT of characters to store the text in a collaborative text editor, using insert to type a new character and delete for backspace.\n\nFormally, the operations on a List CRDT are:\n\n insert(i, x): Inserts a new element with value x at index i, between the existing elements at indices i and i+1. All later elements (index >= i+1) are shifted one to the right.\n delete(i): Deletes the element at index i. All later elements (index >= i+1) are shifted one to the left.\n\nWe now need to decide on the semantics, i.e., what is the result of various insert and delete operations, possibly concurrent. The fact that insertions are unique suggests using a Unique Set (Principle 1). However, we also have to account for indices and the list order.\n\nOne approach would use indices directly: when a user calls insert(i, x), they send (i, x) to the other users, who use i to insert x at the appropriate location. The challenge is that your intended insertion index might move around as a result of users’ inserting/deleting in front of i.\n\nThe *gray* cat jumped on **the** table.\n\nAlice typed \" the\" at index 17, but concurrently, Bob typed \" gray\" in front of her. From Bob's perspective, Alice's insert should happen at index 22.\n\nIt’s possible to work around this by “transforming” i to account for concurrent edits. That idea leads to Operational Transformation (OT), the earliest-invented approach to collaborative text editing, and the one used in Google Docs and most existing apps. Unfortunately, OT algorithms are quite complicated, leading to numerous flawed algorithms. You can reduce complexity by using a central server to manage the document, like Google Docs does, but that precludes decentralized networks, end-to-end encryption, and server-optional open-source apps.\n\nList CRDTs use a different perspective from OT. When you type a character in a text document, you probably don’t think of its position as “index 17” or whatever; instead, its position is at a certain place within the existing text.\n\n“A certain place within the existing text” is vague, but at a minimum, it should be between the characters left and right of your insertion point (“on” and “ table” in the example above) Also, unlike an index, this intuitive position doesn’t change if other users concurrently type earlier in the document; your new text should go between the same characters as before. That is, the position is immutable.\n\nThis leads to the following implementation. The list’s state is a Unique Set whose values are pairs (p, x), where x is the actual value (e.g., a character), and p is a unique immutable position drawn from some abstract total order. The user-visible state of the list is the list of values x ordered by their positions p. Operations are implemented as:\n\n insert(i, x): The inserting user looks up the positions pL, pR of the values to the left and right (indices i and i+1), generates a unique new position p such that pL < p < pR, and calls add((p, x)) on the Unique Set.\n delete(i): The deleting user finds the Unique Set tag t of the value at index i, then calls delete(t) on the Unique Set.\n\nOf course, we need a way to create the positions p. That’s the hard part—in fact, the hardest part of any CRDT—and I don’t have space to go into it here; you should use an existing algorithm (e.g., RGA) or implementation (e.g., Yjs’s Y.Array). Update: I’ve since published two libraries for creating and using CRDT-style positions in TypeScript: list-positions (most efficient), position-strings (most flexible). Both use the Fugue algorithm.\n\nThe important lesson here is that we had to translate indices (the language of normal, non-CRDT lists) into unique immutable positions (what the user intuitively means when they say “insert here”). That leads to our second principle of CRDT design:\n\nPrinciple 2. Express operations in terms of user intention—what the operation means to the user, intuitively. This might differ from the closest ordinary data type operation.\n\nThis principle works because users often have some idea what one operation should do in the face of concurrent operations. If you can capture that intuition, then the resulting operations won’t conflict.\n# Registers\n\nOur last basic CRDT is the Register. This is a variable that holds an arbitrary value that can be set and get. If multiple users set the value at the same time, you pick one of them arbitrarily, or perhaps average them together.\n\nExample uses for Registers:\n\n The font size of a character in a collaborative rich-text editor.\n The name of a document.\n The color of a specific pixel in a collaborative whiteboard.\n Basically, anything where you’re fine with users overwriting each others’ concurrent changes and you don’t want to use a more complicated CRDT.\n\nRegisters are very useful and suffice for many tasks (e.g., Figma and Hex use them almost exclusively).\n\nThe only operation on a Register is set(x), which sets the value to x (in the absence of concurrent operations). We can’t perform these operations literally, since if two users receive concurrent set operations in different orders, they’ll end up with different values.\n\nHowever, we can add the value x to a Unique Set, following Principle 1. The state is now a set of values instead of a single value, but we’ll address that soon. We can also delete old values each time set(x) is called, overwriting them.\n\nThus the implementation of set(x) becomes:\n\n For each element e in the Unique Set, call delete(e) on the Unique Set; then call add(x).\n\nThe result is that at any time, the Register’s state is the set of all the most recent concurrently-set values.\n\nLoops of the form “for each element of a collection, do something” are common in programming. We just saw a way to extend them to CRDTs: “for each element of a Unique Set, do some CRDT operation”. I call this a causal for-each operation because it only affects elements that are prior to the for-each operation in the causal order. It’s useful enough that we make it our next principle of CRDT design:\n\nPrinciple 3a. For operations that do something “for each” element of a collection, one option is to use a causal for-each operation on a Unique Set (or List CRDT).\n\n(Later we will expand on this with Principle 3b, which also concerns for-each operations.)\n\nReturning to Registers, we still need to handle the fact that our state is a set of values, instead of a specific value.\n\nOne option is to accept this as the state, and present all conflicting values to the user. That gives the Multi-Value Register (MVR).\n\nAnother option is to pick a value arbitrarily but deterministically. E.g., the Last-Writer Wins (LWW) Register tags each value with the wall-clock time when it is set, then picks the value with the latest timestamp.\n\nGrid of pixels, some conflicting (outlined in red). One conflicting pixel has been clicked on, revealing the conflicting choices.\n\nIn Pixelpusher, a collaborative pixel art editor, each pixel shows one color by default (LWW Register), but you can click to pop out all conflicting colors (MVR). Image credit: Peter van Hardenberg (original).\n\nIn general, you can define the value getter to be an arbitrary deterministic function of the set of values.\n\nExamples:\n\n If the values are colors, you can average their RGB coordinates. That seems like fine behavior for pixels in a collaborative whiteboard.\n\n If the values are booleans, you can choose to prefer true values, i.e., the Register’s value is true if its set contains any true values. That gives the Enable-Wins Flag.\n\n# Composing CRDTs\n\nWe now have enough basic CRDTs to start making more complicated data structures through composition. I’ll describe three techniques: CRDT Objects, CRDT-Valued Maps, and collections of CRDTs.\n# CRDT Objects\n\nThe simplest composition technique is to use multiple CRDTs side-by-side. By making them instance fields in a class, you obtain a CRDT Object, which is itself a CRDT (trivially correct). The power of CRDT Objects comes from using standard OOP techniques, e.g., implementation hiding.\n\nExamples:\n\n In a collaborative flash card app, to make individual cards editable, you could represent each card as a CRDT Object with two text CRDT (List CRDT of characters) instance fields, one for the front and one for the back.\n You can represent the position and size of an image in a collaborative slide editor by using separate Registers for the left, top, width, and height.\n\nTo implement a CRDT Object, each time an instance field requests to broadcast a message, the CRDT Object broadcasts that message tagged with the field’s name. Receivers then deliver the message to their own instance field with the same name.\n# CRDT-Valued Map\n\nA CRDT-Valued Map is like a CRDT Object but with potentially infinite instance fields, one for each allowed map key. Every key/value pair is implicitly always present in the map, but values are only explicitly constructed in memory as needed, using a predefined factory method (like Apache Commons’ LazyMap).\n\nExamples:\n\n Consider a shared notes app in which users can archive notes, then restore them later. To indicate which notes are normal (not archived), we want to store them in a set. A Unique Set won’t work, since the same note can be added (restored) multiple times. Instead, you can use a CRDT-Valued Map whose keys are the documents and whose values are Enable-Wins Flags; the value of the flag for key doc indicates whether doc is in the set. This gives the Add-Wins Set.\n Quill lets you easily display and edit rich text in a browser app. In a Quill document, each character has an attributes map, which contains arbitrary key-value pairs describing formatting (e.g., \"bold\": true). You can model this using a CRDT-Valued Map with arbitrary keys and LWW Register values; the value of the Register for key attr indicates the current value for attr.\n\nA CRDT-Valued Map is implemented like a CRDT Object: each message broadcast by a value CRDT is tagged with its serialized key. Internally, the map stores only the explicitly-constructed key-value pairs; each value is constructed using the factory method the first time it is accessed by the local user or receives a message. However, this is not visible externally—from the outside, the other values still appear present, just in their initial states. (If you want an explicit set of “present” keys, you can track them using an Add-Wins Set.)\n\n\n# Collections of CRDTs\n\nOur above definition of a Unique Set implicitly assumed that the data values x were immutable and serializable (capable of being sent over the network). However, we can also make a Unique Set of CRDTs, whose values are dynamically-created CRDTs.\n\nTo add a new value CRDT, a user sends a unique new tag and any arguments needed to construct the value. Each recipient passes those arguments to a predefined factory method, then stores the returned CRDT in their copy of the set. When a value CRDT is deleted, it is forgotten and can no longer be used.\n\nNote that unlike in a CRDT-Valued Map, values are explicitly created (with dynamic constructor arguments) and deleted—the set effectively provides collaborative new and free operations.\n\nWe can likewise make a List of CRDTs.\n\nExamples:\n\n In a shared folder containing multiple collaborative documents, you can define your document CRDT, then use a Unique Set of document CRDTs to model the whole folder. (You can also use a CRDT-Valued Map from names to documents, but then documents can’t be renamed, and documents “created” concurrently with the same name will end up merged.)\n Continuing the Quill rich-text example from the previous section, you can model a rich-text document as a List of “rich character CRDTs”, where each “rich character CRDT” consists of an immutable (non-CRDT) character plus the attributes map CRDT. This is sufficient to build a simple but inefficient Google Docs-style app with CRDTs.\n\n# Using Composition\n\nYou can use the above composition techniques and basic CRDTs to design CRDTs for many collaborative apps. Choosing the exact structure, and how operations and user-visible state map onto that structure, is the main challenge.\n\nA good starting point is to design an ordinary (non-CRDT) data model, using ordinary objects, collections, etc., then convert it to a CRDT version. So variables become Registers, objects become CRDT Objects, lists become List CRDTs, sets become Unique Sets or Add-Wins Sets, etc. You can then tweak the design as needed to accommodate extra operations or fix weird concurrent behaviors.\n\nTo accommodate as many operations as possible while preserving user intention, I recommend:\n\nPrinciple 4. Independent operations (in the user’s mind) should act on independent state.\n\nExamples:\n\n As mentioned earlier, you can represent the position and size of an image in a collaborative slide editor by using separate Registers for the left, top, width, and height. If you wanted, you could instead use a single Register whose value is a tuple (left, top, width, height), but this would violate Principle 4. Indeed, then if one user moved the image while another resized it, one of their changes would overwrite the other, instead of both moving and resizing.\n Again in a collaborative slide editor, you might initially model the slide list as a List of slide CRDTs. However, this provides no way for users to move slides around in the list, e.g., swap the order of two slides. You could implement a move operation using cut-and-paste, but then slide edits concurrent to a move will be lost, even though they are intuitively independent operations.\n\n Following Principle 4, you should instead implement move operations by modifying some state independent of the slide itself. You can do this by replacing the List of slide CRDTs with a Unique Set of CRDT Objects { slide, positionReg }, where positionReg is an LWW Register indicating the position. To move a slide, you create a unique new position like in a List CRDT, then set the value of positionReg equal to that position. This construction gives the List-with-Move CRDT.\n\n# New: Concurrent+Causal For-Each Operations\n\nThere’s one more trick I want to show you. Sometimes, when performing a for-each operation on a Unique Set or List CRDT (Principle 3a), you don’t just want to affect existing (causally prior) elements. You also want to affect elements that are added/inserted concurrently.\n\nFor example:\n\n In a rich text editor, if one user bolds a range of text, while concurrently, another user types in the middle of the range, the latter text should also be bolded.\n One user bolds a range of text, while concurrently, another user types \" the\" in the middle. In the final result, \" the\" is also bolded.\n In other words, the first user’s intended operation is “for each character in the range including ones inserted concurrently, bold it”.\n In a collaborative recipe editor, if one user clicks a “double the recipe” button, while concurrently, another user edits an amount, then their edit should also be doubled. Otherwise, the recipe will be out of proportion, and the meal will be ruined!\n\nI call such an operation a concurrent+causal for-each operation. To accomodate the above examples, I propose the following addendum to Principle 3a:\n\nPrinciple 3b. For operations that do something “for each” element of a collection, another option is to use a concurrent+causal for-each operation on a Unique Set (or List CRDT).\n\nTo implement this, the initiating user first does a causal (normal) for-each operation. They then send a message describing how to perform the operation on concurrently added elements. The receivers apply the operation to any concurrently added elements they’ve received already (and haven’t yet deleted), then store the message in a log. Later, each time they receive a new element, they check if it’s concurrent to the stored message; if so, they apply the operation.\n\n Aside. It would be more general to split Principle 3 into “causal for-each” and “concurrent for-each” operations, and indeed, this is how the previous paragraph describes it. However, I haven’t yet found a good use case for a concurrent for-each operation that isn’t part of a concurrent+causal for-each.\n\n\nConcurrent+causal for-each operations are novel as far as I’m aware. They are based on a paper I, Heather Miller, and Christopher Meiklejohn wrote last year, about a composition technique we call the semidirect product, which can implement them (albeit in a confusing way). Unfortunately, the paper doesn’t make clear what the semidirect product is doing intuitively, since we didn’t understand this ourselves! My current opinion is that concurrent+causal for-each operations are what it’s really trying to do; the semidirect product itself is (a special case of) an optimized implementation, improving memory usage at the cost of simplicity.\n# Summary: CRDT Design Techniques\n\nThat’s it for our CRDT design techniques. Before continuing to the spreadsheet case study, here is a summary cheat sheet.\n\n Start with our basic CRDTs: Unique Set, List CRDT, and Registers.\n Compose these into steadily more complex pieces using CRDT Objects, CRDT-Valued Maps, and Collections of CRDTs.\n When choosing basic CRDTs or how to compose things, keep in mind these principles:\n\n Principle 1. Use the Unique Set CRDT for operations that “add” or “create” a unique new thing.\n\n Principle 2. Express operations in terms of user intention—what the operation means to the user, intuitively. This might differ from the closest ordinary data type operation.\n\n Principle 3(a, b). For operations that do something “for each” element of a collection, use a causal for-each operation or a concurrent+causal for-each operation on a Unique Set (or List CRDT).\n\n Principle 4. Independent operations (in the user’s mind) should act on independent state.\n\n# Case Study: A Collaborative Spreadsheet\n\nNow let’s get practical: we’re going to design a CRDT for a collaborative spreadsheet editor (think Google Sheets).\n\nAs practice, try sketching a design yourself before reading any further. The rest of this section describes how I would do it, but don’t worry if you come up with something different—there’s no one right answer! The point of this blog post is to give you the confidence to design and tweak CRDTs like this yourself, not to dictate “the one true spreadsheet CRDT™”.\n# Design Walkthrough\n\nTo start off, consider an individual cell. Fundamentally, it consists of a text string. We could make this a Text (List) CRDT, but usually, you don’t edit individual cells collaboratively; instead, you type the new value of the cell, hit enter, and then its value shows up for everyone else. This suggests instead using a Register, e.g., an LWW Register.\n\nBesides the text content, a cell can have properties like its font size, whether word wrap is enabled, etc. Since changing these properties are all independent operations, following Principle 4, they should have independent state. This suggests using a CRDT Object to represent the cell, with a different CRDT instance field for each property. In pseudocode (using extends CRDTObject to indicate CRDT Objects):\n\nclass Cell extends CRDTObject {\n content: LWWRegister;\n fontSize: LWWRegister;\n wordWrap: EnableWinsFlag;\n // ...\n}\n\nThe spreadsheet itself is a grid of cells. Each cell is indexed by its location (row, column), suggesting a map from locations to cells. (A 2D list could work too, but then we’d have to put rows and columns on an unequal footing, which might cause trouble later.) Thus let’s use a Cell-CRDT-Valued Map.\n\nWhat about the map keys? It’s tempting to use conventional row-column indicators like “A1”, “B3”, etc. However, then we can’t easily insert or delete rows/columns, since doing so renames other cells’ indicators. (We could try making a “rename” operation, but that violates Principle 2, since it does not match the user’s original intention: inserting/deleting a different row/column.)\n\nInstead, let’s identify cell locations using pairs (row, column), where “row” means “the line of cells horizontally adjacent to this cell”, independent of that row’s literal location (1, 2, etc.), and likewise for “column”. That is, we create an opaque Row object to represent each row, and likewise for columns, then use pairs (Row, Column) for our map keys.\n\nThe word “create” suggests using Unique Sets (Principle 1), although since the rows and columns are ordered, we actually want List CRDTs. Hence our app state looks like:\n\nrows: ListCRDT;\ncolumns: ListCRDT;\ncells: CRDTValuedMap<[row: Row, column: Column], Cell>;\n\nNow you can insert or delete rows and columns by calling the appropriate operations on columns and rows, without affecting the cells map at all. (Due to the lazy nature of the map, we don’t have to explicitly create cells to fill a new row or column; they implicitly already exist.)\n\nSpeaking of rows and columns, there’s more we can do here. For example, rows have editable properties like their height, whether they are visible, etc. These properties are independent, so they should have independent states (Principle 4). This suggests making Row into a CRDT Object:\n\nclass Row extends CRDTObject {\n height: LWWRegister;\n isVisible: EnableWinsFlag;\n // ...\n}\n\nAlso, we want to be able to move rows and columns around. We already described how to do this using a List-with-Move CRDT:\n\nclass MovableListEntry extends CRDTObject {\n value: C;\n positionReg: LWWRegister;\n}\n\nclass MovableListOfCRDTs extends CRDTObject {\n state: UniqueSetOfCRDTs>;\n}\n\n\nrows: MovableListOfCRDTs;\ncolumns: MovableListOfCRDTs;\n\nNext, we can also perform operations on every cell in a row, like changing the font size of every cell. For each such operation, we have three options:\n\n Use a causal for-each operation (Principle 3a). This will affect all current cells in the row, but not any cells that are created concurrently (when a new column is inserted). E.g., a “clear” operation that sets every cell’s value to \"\".\n Use a concurrent+causal for-each operation (Principle 3b). This will affect all current cells in the row and any created concurrently. E.g., changing the font size of a whole row.\n Use an independent state that affects the row itself, not the cells (Principle 4). E.g., our usage of Row.height for the height of a row.\n\n# Finished Design\n\nIn summary, the state of our spreadsheet is as follows.\n\n// ---- CRDT Objects ----\nclass Row extends CRDTObject {\n height: LWWRegister;\n isVisible: EnableWinsFlag;\n // ...\n}\n\nclass Column extends CRDTObject {\n width: LWWRegister;\n isVisible: EnableWinsFlag;\n // ...\n}\n\nclass Cell extends CRDTObject {\n content: LWWRegister;\n fontSize: LWWRegister;\n wordWrap: EnableWinsFlag;\n // ...\n}\n\nclass MovableListEntry extends CRDTObject {\n value: C;\n positionReg: LWWRegister;\n}\n\nclass MovableListOfCRDTs extends CRDTObject {\n state: UniqueSetOfCRDTs>;\n}\n\n// ---- App state ----\nrows: MovableListOfCRDTs;\ncolumns: MovableListOfCRDTs;\ncells: CRDTValuedMap<[row: Row, column: Column], Cell>;\n\nNote that I never explicitly mentioned CRDT correctness—the claim that all users see the same document state after receiving the same messages. Because we assembled the design from existing CRDTs using composition techniques that preserve CRDT correctness, it is trivially correct. Plus, it should be straightforward to reason out what would happen in various concurrency scenarios.\n\nAs exercises, here are some further tweaks you can make to this design, phrased as user requests:\n\n “I’d like to have multiple sheets in the same document, accessible by tabs at the bottom of the screen, like in Excel.” Hint (highlight to reveal): Use a List of CRDTs.\n “I’ve noticed that if I change the font size of a cell, while at the same time someone else changes the font size for the whole row, sometimes their change overwrites mine. I’d rather keep my change, since it’s more specific.” Hint: Use a Register with a custom getter.\n “I want to reference other cells in formulas, e.g., = A2 + B3. Later, if B3 moves to C3, its references should update too.” Hint: Store the reference as something immutable.\n\n# Conclusion\n\nI hope you’ve gained an understanding of how CRDTs work, plus perhaps a desire to apply them in your own apps. We covered a lot:\n\n Traditional CRDTs: Unique Set, List/Text, LWW Register, Enable-Wins Flag, Add-Wins Set, CRDT-Valued Map, and List-with-Move.\n Novel Operations: Concurrent+causal for-each operations on a Unique Set or List CRDT.\n Whole Apps: Spreadsheet, rich text, and pieces of various other apps.\n\nFor more info, crdt.tech collects most CRDT resources in one place. For traditional CRDTs, the classic reference is Shapiro et al. 2011, while Preguiça 2018 gives a more modern overview.\n\nI’ve also put many of these ideas into practice in a library, Collabs. You can learn more about Collabs, and see how open-source collaborative apps might work in practice, in my Local-First Web talk: Video, Slides, Live demo.\n# Related Work\n\nThis blog post’s approach to CRDT design - using simple CRDTs plus composition techniques - draws inspiration from a number of sources. Most similar is the way Figma and Hex describe their collaboration platforms; they likewise support complex apps by composing simple, easy-to-reason-about pieces. Relative to those platforms, I incorporate more academic CRDT designs, enabling more flexible behavior and server-free operation.\n\nThe specific CRDTs I describe are based on Shapiro et al. 2011 unless noted otherwise. Note that they abbreviate “Unique Set” to “U-Set”. For composition techniques, a concept analogous to CRDT Objects appears in BloomL; CRDT-Valued Maps appear in Riak and BloomL; and the Collections of CRDTs are inspired by how Yjs’s Y.Array and Y.Map handle nested CRDTs.\n\nSimilar to how I build everything on top of a Unique Set CRDT, Mergeable Replicated Data Types are all built on top of a (non-unique) set with a 3-way merge function, but in a quite different way.\n\nOther systems that allow arbitrary nesting of CRDTs include Riak, Automerge, Yjs, and OWebSync.\n# Acknowledgments\n\nI thank Heather Miller, Ria Pradeep, and Benito Geordie for numerous CRDT design discussions that led to these ideas. Jonathan Aldrich, Justine Sherry, and Pratik Fegade reviewed a version of this post that appears on the CMU CSD PhD Blog. I am funded by an NDSEG Fellowship sponsored by the US Office of Naval Research.\n# Appendix: What’s Missing?\n\nThe CRDT design techniques I describe above are not sufficient to reproduce all published CRDT designs - or more generally, all possible Strong Eventual Consistency data structures. This is deliberate: I want to restrict to (what I consider) reasonable semantics and simple implementations.\n\nIn this section, I briefly discuss some classes of CRDTs that aren’t covered by the above design techniques.\n# Optimized Implementations\n\nGiven a CRDT designed using the above techniques, you can often find an alternative implementation that has the same semantics (user-visible behavior) but is more efficient.\n\nFor example:\n\n Suppose you are counting clicks by all users. According to the above techniques, you should use a Unique Set CRDT and add a new element to the set for each click (Principle 1), then use the size of the set as the number of clicks. But there is a much more efficient implementation: merely store the number of clicks, and each time a user clicks, send a message instructing everyone to increment their number. This is the classic Counter CRDT.\n Peritext is a rich-text CRDT that allows formatting operations to also affect concurrently inserted characters, like our example above. Instead of using concurrent+causal for-each operations, they store formatting info at the start and end of the range, then do some magic to make sure that everything works correctly. This is much more efficient than applying formatting to every affected character like in our example, especially for memory usage.\n\nMy advice is to start with an implementation using the techniques in this blog post. That way, you can pin down the semantics and get a proof-of-concept running quickly. Later, if needed, you can make an alternate, optimized implementation that has the exact same user-visible behavior as the original (enforced by mathematical proofs, unit tests, or both).\n\nDoing things in this order - above techniques, then optimize - should help you avoid some of the difficulties of traditional, from-scratch CRDT design. It also ensures that your resulting CRDT is both correct and reasonable. In other words: beware premature optimization!\n\n 3 out of 4 Peritext authors mention that it was difficult to get working: here, here, and here.\n\n\nOne way to optimize is with a complete rewrite at the CRDT level. For example, relative to the rich text CRDT that we sketched above (enhanced with concurrent+causal for-each operations), Peritext looks like a complete rewrite. (In reality, Peritext came first.)\n\nAnother option is to “compress” the CRDT’s state/messages in some way that is easy to map back to the original CRDT. That is, in your mind (and in the code comments), you are still using the CRDT derived from this blog post, but the actual code operates on some optimized representation of the same state/messages.\n\nFor example, in the rich text CRDT sketched above, if storing separate formatting registers for each character uses too much memory, you could compress the state by deduplicating the identical formatting entries that result when a user formats a range of text. Then the next time you receive an operation, you decompress the state, apply that operation, and recompress. Likewise, if formatting a range of characters individually generates too much network traffic (since there is one CRDT message per character), you could instead send a single message that describes the whole formatting operation, then have recipients decompress it to yield the original messages.\n# Optimized Semantics\n\nSome existing CRDTs deliberately choose behavior that may look odd to users, but has efficiency benefits. The techniques in this blog post don’t always allow you to construct those CRDTs.\n\nThe example that comes to my mind concerns what to do when one user deletes a CRDT from a CRDT collection, while concurrently, another user makes changes to that CRDT. E.g., one user deletes a presentation slide while someone else is editing the slide. There are a few possible behaviors:\n\n “Deleting” semantics: The deletion wins, and concurrent edits to the deleted CRDT are lost. This is the semantics we adopt for the Collections of CRDTs above; I attribute it to Yjs. It is memory-efficient (deleted CRDTs are not kept around forever), but can lose data.\n “Archiving” semantics: CRDTs are never actually deleted, only archived. Concurrent edits to an archived CRDT apply to that CRDT as usual, and if the new content is interesting, users can choose to un-archive. We described how to do this using the Add-Wins Set above. This is the nicest semantics for users, but it means that once created, a CRDT stays in memory forever.\n “Resetting” semantics: A delete operation “resets” its target CRDT, undoing the effect of all (causally) prior operations. Concurrent edits to the deleted CRDT are applied to this reset state. E.g., if a user increments a counter concurrent to its deletion, then the resulting counter value will be 1, regardless of what its state was before deletion.\n This semantics is adopted by the Riak Map and a JSON CRDT paper, but it is not possible using the techniques in this blog post. It is memory-efficient (deleted CRDTs are not kept around forever) and does not lose data, but has weird behavior. E.g., if you add some text to a slide concurrent to its deletion, then the result is a slide that has only the text you just entered. This is also the cause of the above map anomaly.\n\nI am okay with not supporting odd semantics because user experience seems like a first priority. If your desired semantics results in poor performance (e.g. “archiving” semantics leading to unbounded memory usage), you can work around it once it becomes a bottleneck, e.g., by persisting some state to disk.\n# Hard Semantics\n\nSome CRDTs seem useful and not prematurely optimized, but I don’t know how to implement them using the techniques in this blog post. Two examples:\n\n A Tree CRDT with a “move” operation, suitable for modeling a filesystem in which you can cut-and-paste files and folders. The tricky part is that two users might concurrently move folders inside of each other, creating a cycle, and you have to somehow resolve this (e.g., pick one move and reject the other). Papers: Kleppmann et al., Nair et al..\n A CRDT for managing group membership, in which users can add or remove other users. The tricky part is that one user might remove another, concurrent to that user taking some action, and then you have to decide whether to allow it or not. This is an area of active research, but there have been some proposed CRDTs, none of which appear to fit into this blog post.\n\n Aside. There is a sense in which the Unique Set CRDT (hence this blog post) is “CRDT-complete”, i.e., it can be used to implement any CRDT semantics: you use a Unique Set to store the complete operation history together with causal ordering info, then compute the state as a function of this history, like in pure op-based CRDTs. However, this violates the spirit of the blog post, which is to give you guidance on how to design your CRDT.\n\n# Beyond CRDTs\n\nCRDTs, and more broadly Strong Eventual Consistency, are not everything. Some systems, including some collaborative apps, really need Strong Consistency: the guarantee that events happen in a serial order, agreed upon by everyone. E.g., monetary transactions. So you may need to mix CRDTs with strongly consistent data structures; there are a number of papers about such “Mixed Consistency” systems, e.g., RedBlue consistency.\n\nHome • Matthew Weidner • PhD student at CMU CSD • mweidner037 [at] gmail.com • @MatthewWeidner3 • LinkedIn • GitHub\n\n"}},"token":"2FrN6DWGbVILfFMMiPg/YdNYUIw6BcO99Z5M/XTIU74=","login":null}