Table of contents

DONE

CRDTs: The Hard Parts

video

%3 cluster_f629005c_c7fb_4aff_93be_c348071ef7e3 CRDTs: The Hard Parts cluster_c1723a57_8d48_4e2e_ac5a_ede2a09c5f9a Notes cluster_dc7848a2_4acf_4ef7_92e3_d6f6ebe1092b CRDTs cluster_a9fa5a85_2f8d_486c_b621_67fb111f66bb Moving/Reordering list items cluster_1e51fc0c_adf5_49f0_84ce_a5c4f3cf02fe Concurrent moving of subtrees _fc57e4ca_e8c8_40cd_8260_3e5eae486d39 References _7b20659e_322d_4049_82fa_525e08d6d840 Reducing metadata overhead _a6d4a8a9_5030_4880_bf75_58884e061fda Data structures _f3110f13_22ea_4cf4_9de2_612c6d46e6ea How to define a new operation? _14fb44d2_375a_4bfd_a575_e3dca029eb2b Open problem _c1c25b6e_50b4_4439_8bad_4a7d66662d56 Interleaving _5809f26b_8911_484e_bdc7_4076c6231fff IDs _c885caa6_2762_4a69_bb9c_187ce34a30fb OTs _c97d95cc_d787_4951_8beb_aa9d5279f6e9 CRDT: Conflict-free Replicated Data Type _dfc6c787_8803_4a50_84ba_5c8fe0d46ded Operational transformations _dfc6c787_8803_4a50_84ba_5c8fe0d46ded->_c97d95cc_d787_4951_8beb_aa9d5279f6e9 _9bd30dc2_c082_449d_b968_044ba2026fc0 CRDTs and the Quest for Distributed Consistency _9bd30dc2_c082_449d_b968_044ba2026fc0->_c97d95cc_d787_4951_8beb_aa9d5279f6e9 _9bd30dc2_c082_449d_b968_044ba2026fc0->__0:cluster_f629005c_c7fb_4aff_93be_c348071ef7e3 __1:cluster_f629005c_c7fb_4aff_93be_c348071ef7e3->_c97d95cc_d787_4951_8beb_aa9d5279f6e9 __2:cluster_f629005c_c7fb_4aff_93be_c348071ef7e3->_dfc6c787_8803_4a50_84ba_5c8fe0d46ded

Notes

  • Base sample

    Collaborative text editing

  • At the "beggining" all users have the same document

  • Concurrent actions make all users converge on the same state

  • Alternatives

    • OT

      Operational Transformation

      • Google Docs, MS Office Online

    • CRDTs

      Conflict-Free Replicated Data Types

      • Riak, TomTom GPS, Atom's Teletype

OTs

  • Requires

    A central server (YT)

  • "How changes are made to a document"

  • Indexes of the positions where some operations happens have to be transformed when operations happen concurrently

CRDTs

  • Looks for convergence

  • Two nodes that see the same set of operations (but maybe in a different order) will converge in the same final state.

Interleaving

  • What happens if several people concurrently introduce text in the same position?

IDs

  • Gives each character in the document a (unique, stable) identifier by which is referred

  • The way to define this IDs is what makes the CRDTs differ on how they merge (so, how they interleave)

    • Some represent the text as a tree of characters (Treedoc, Logoot, RGA, Causal Trees, ...)

    • Maybe nodeID + counter

Moving/Reordering list items

  • For example, for TO-DO lists

  • Text CRDTs don't support move, only adding and deleting

  • Delete-and-reinsert in new position might duplicate the element in the new position

How to define a new operation?

  • CRDTs provide a stable way to reference an element in a list

    • Take it's unique identifiers to use in the new operation

  • We define the operation with Last-Writer-Wins semantic (any stable one is OK)

  • A new (state) register is constructed for the elements going in this operation.

    • Each node will add a new element (pair) to the set

Open problem

Concurrent moving of subtrees

  • Moving one subtree to (concurrently) two different ones at the same time

  • Instead of duplication, a Last-Writer-Wins behavior is expected

  • Apply the operations in timestamp order, and skip the operations that will produce and incorrect state

    • This means that some of the nodes will have to undo the skipped operations

    • Even more, operations will have to be undone and redone to thread received operations in timestamp-order

    • See

      https://youtu.be/x7drE24geUw?t=2704

Data structures

  • Each move operation has

    • time

      Timestamp (Globally unique, eg. Lamport timestamp)

    • parent

      NodeId (Destination of move)

    • meta

      Metadata (eg. filename within parent, etc)

    • child

      NodeId (Subtree being moved)

  • Each log entry (for undo/redo) has

    • time

      Timestamp

    • oldParent

      NodeId? (null if not previously on tree, happened in remote nodes)

    • oldMeta

      Metadata?

    • newParent

      NodeId

    • newMeta

      Metadata

    • child

      NodeId

Reducing metadata overhead

  • If we give every character a unique identifier and some metadata, each char will go from 1 byte to ~100 bytes for metadata&ID