crdt

tags

peer-to-peer ,Alternative Internet , Local First Software , Distributed Systems

FAQ

Relationships

CRDT vs OT

• algorithm - Differences between OT and CRDT - Stack Overflow 

CRDT vs Cloudflare Durable Objects

• https://sunilpai.dev/posts/the-future-of-serverless/
• https://blog.cloudflare.com/durable-objects-alarms/
• https://www.gitlip.com/blog/multiplayer-filesystem-in-durable-objects
• https://blog.cloudflare.com/introducing-workers-durable-objects/

• Core Relationship

  • DOs are foundational: They provide strongly consistent, stateful serverless units with storage. Think of them as a single source of truth or a coordination point.
  • CRDTs are a pattern for data: They are special data structures designed for multi-user collaboration, automatically merging concurrent edits to reach eventual consistency without central locking during the edits.
  • DOs can host CRDTs: You can use a DO to store the state of a CRDT, manage its updates, and coordinate clients.
  • DOs are not limited to CRDTs: For many tasks, using a DO as the single authoritative state manager is simpler and sufficient, avoiding CRDT complexity.

• Pragmatic Points & Considerations

  • Use Case Dictates Choice:
    • Need simple coordination/state? Use a standard Durable Object.
    • Need real-time, multi-user simultaneous editing (like Google Docs)? Consider building with CRDTs, potentially using DOs for persistence and coordination.
  • CRDT Complexity:
    • Implementing CRDTs correctly is hard.
    • Not all data types easily map to CRDTs.
    • Specific CRDT libraries (like Yjs) might have APIs that clash with DO’s asynchronous nature or present challenges for complex multi-document scenarios.
  • DO Integration Challenges (when using CRDTs):
    • Storage Limits: DOs have storage size limits (e.g., 128KB per value). CRDT updates might need chunking or merging before saving.
    • Performance: Optimize how you write CRDT updates to DO storage (e.g., batching/debouncing) to manage costs and latency.
    • Feature Interaction: You may need to adapt CRDT features (like presence detection) to work well with DO features (like Hibernation).

CRDT and Synchronization

I recommend learning about CRDTs. Not because a sync system should be built on CRDTs (it probably shouldn’t unless you’re building a truly decentralized, peer-to-peer system), but because everyone’s talking about them and it’s useful to understand their limitations (and strengths). Also the literature contains many concepts that are helpful even if you don’t need costly decentralization because can rely on a centralized server. - pesterhazy

What’s relationship between CRDT and Eventual Consistency ?

• crdt give strong Eventual Consistency

How is WebRTC(Realtime) related to CRDT?

• See WebRTC
• You don’t really need webrtc to collaborative tech as you’ll anyway need a signaling server.
• You might aswell use a centralized sync server with something  like WebSockets .

When do you need to use CRDT?

• You might not need a CRDT | Hacker News 
• You don’t need a CRDT to build a collaborative experience | Hacker News 

What’s the crux of the problem?

Often the challenge was less technical, and centered around what a conflicted state means in the absence of a human discussion, i.e. how would you resolve a git merge conflict without human intervention, or if two people reschedule the meeting simultaneously one of them is likely to miss it unless they talk it out

What?

Assumptions and context

• CRDT’s assume that you can model and automate conflict resolution for your data-model. Depending on your needs this may be easy or difficult. If you can’t do that modeling for some reason then you can’t really use CRDT.

Different definitions

• CRDTs are a family of generic data structures that can withstand network partitions without conflicts
• CRDTs are a buzzname for lattices storing state. Whats needed is to think latticewise (monotonically) about how you use state, not just store it.
• Keep CALM and CRDT on  : Paper explores a richer API than that of CRDTs, which guarantees both update and query are meaningful

CRDT and Text editing

Resources

• Text Editor: Data Structures | Hacker News 
• Lies I was told about collab editing, Part 1: Algorithms for offline editing | Hacker News 
• Collaborative text editing with Eg-Walker: Better, faster, smaller | Hacker News 
• Building Document-Centric, CRDT-Native Editors | Hacker News 

Tools

Primitives

• position-strings - npm 

Frameworks/Libraries

• Traditional CRDT libraries (Yjs, Automerge, Collabs  ) give you a data structure
• The data structure also controls the state of the whole list/text (or possibly your whole app).

Toy Implementations

• https://github.com/39aldo39/DecSync/tree/master
• https://github.com/siliconjungle/tiny-merge-legacy
• https://github.com/ergl/crdt-ml/tree/master
• https://github.com/siliconjungle/crdt-tutorials/blob/main/examples/min-store.js