The goal is to build an interoperable multi-user system that allows co-editing of documents and does so without a server authoritative model which allows offline edits and background sync.
Interoperability comes nearly free with ATProto because of 2 things:
- 1.
PDS as a "social filesystem" means that any application can read and write data from the PDS
- 2.
Lexicons / Lexicon Publishing and PDS schema enforcement allow any client to discover the schema to read / write data
For CRDTs we need one additional piece - A CRDT can effectively be modeled as a pure function over ops f(ops) which given the same two sets of ops produces the same document. To be truly interoperable that function needs to be open sourced, documented, and feature extensive test suites in the form of (ops) -> document pairings.
Given these three things.
- 1.
Ops stored in the PDS
- 2.
Ops storage documented via a published lexicon
- 3.
f(Ops) documented with extensive tests
Any implementation of a CRDT editor system will be interoperable. As we consider different architectures we we maintain these 3 invariants the question will be what the difficulty of interoperability will be.
The simplest version of this involves your client writing ops to your PDS, reading ops both from your PDS and from other PDS' while in turn your PDS is read by other clients. If we start by building this system other systems can layer on-top of this.
What Ops to write?
There are two types of Ops when we're thinking about a system like this.
- 1.
Pending Ops - ops that haven't been committed to the document on other clients
- 2.
Committed Ops - ops that have been committed to the document on other clients
Because we want the pool of clients to be fluid and not centrally managed we can simplify these two cases into the following groups
- 1.
Ops that originate from your client
- 2.
Ops that originate from another client
Ops that originate from your client must be written to your PDS by your client. Ops that originate from another client can be written to your pds.
Should I write your Ops to My PDS?
Maybe? – The reason to write your ops to my PDS is because I don't trust that your PDS (or another source) will make them available in the future – either because you're offline or because you've decided you don't want to provide those ops any more, and I want to see them in the future. Just reading a document you've written I shouldn't feel the need to replicate your ops, but if you're contributing to a doc I've written I may want to write those contributions to my PDS.
Of course in the end it doesn't matter, if I have two ops OP1 and OP2 that are structurally identical then F(OP1, OP2) = F(OP1) = F(OP2)
So if I choose to duplicate your ops then any client will continue to resolve the correct document from the combined op log. This means that we can leave the choice of if and when to replicate Ops from the network.
Here's a slightly different network topology – In practice it works the same as the one above but now a Document Server which acts as an App View sits between the PDS and the Clients. This has the role of collecting the Ops from the independent Ops logs and pulling them together into a single op log that any client can read. It can also be responsible for replicating and storing these ops allowing each individual PDS to be offline in order to still construct the whole OP log.
Live Editing
In many cases the above network topology is enough – however if you want live (per-character) editing then relying on the firehose to stream ops from a PDS to your client isn't fast enough. The solution in this case is to stream your ops to a relay that can distribute them to multiple connected clients - this is an entirely optional.
In practice we can collapse any of these boxes together. For instance a web based editor may take directory to a single server that acts as both a relay, document server, and writes back to the PDS. But the fundamental aspect - writing your own ops to your PDS allows anyone on the network to re-create the OP log and bring any of these pieces they want.
Lexicons
When designing a Lexicon for the op log we can start with the very simple design
{
"lexicon": 1,
"id": "com.example.oplog",
"defs": {
"main": {
"type": "record",
"key": "tid",
"record": {
"type": "object",
"required": ["ops"],
"properties": {
"ops": {
"type": "array",
"items": {
"type": "union",
"refs": []
}
}
}
}
}
}
}We can pressure test this design with a few questions.
- 1.
Can I reasonably only pull "new" ops? - Yes. Assuming that the records are read only it's possible to remember the last TID for each PDS and only pull new records. Even if records are edited we can find newly committed records based on PDS subscriptions
- 2.
Can I reasonably only pull "relevant" ops? - No, the TID based keys don't let me sort for "ops that apply to X" which means at a minimum we'd need to read some data out of each record
{
"lexicon": 1,
"id": "com.example.document",
"defs": {
"main": {
"type": "record",
"key": "any", // document ID
"record": {
"type": "object",
"required": ["ops"],
"properties": {
"ops": {
"type": "array",
"items": {
"type": "union",
"refs": []
}
}
}
}
}
}
}With the model inverted we find the opposite problem. It's easy for me to find ops relevant to X but you need to read ops you make have already seen.
If only we could create composite RKeys? Of course we can but we lose support in the lexicon... Unless we wait for private data.
Bridge the Gap till Private Data Lands
Ultimately private data is the right abstraction for CRDT documents - after all even for a publicly readable document you don't want public contributions. However until private data lands we can bridge the gap with a composite key by using tid + document id. We want to put tid first since it will allow us to sort by time then document, that means that looking at "updates since the last time I checked" will require a check on a limited number of records.
Op Compaction
The structure of our OP log gives us 2 types of compaction.
- 1.
Record Compaction - As we create lots of sporatic operations we'll have lots of small records, we can go in and move operations from older records to newer records (remember duplicated ops in the op log are not an issue). Afterwards we can delete the old records.
- 2.
Op Compaction - If we have 3 ops such that F(OP1, OP2) = F(OP3) we can replace OP1 and OP2 with OP3. This has a few real limitations.
- 1.
OP3 must have the same op id as OP2
- 2.
No additional ops may depend on OP
Because PDS records are mutable we can leverage both of these compaction methods with our network topologies. However for OP compaction we have to fundamentally introduce an edit horizon which will limit how far back an operations is allowed to occur.
The Proposed Lexicon
{
"lexicon": 1,
"id": "com.example.oplog",
"defs": {
"main": {
"type": "record",
"key": "any",
"description": "An append-only operation log for a single document. The record key is a TID followed by the document's GUID, in the form
`<tid>-<docId>` (TID first so records for a doc sort chronologically). Authorship is attested via the badge.blue convention: signatures live in the
`signatures` array, while the transient `$sig` container is injected only during CID computation and is never persisted.",
"record": {
"type": "object",
"required": ["docId", "createdOn", "ops"],
"properties": {
"docId": {
"type": "string",
"description": "The GUID of the document this log belongs to. Matches the docId portion of the record key."
},
"createdOn": {
"type": "string",
"format": "datetime",
"description": "When this oplog record was created."
},
"ops": {
"type": "array",
"description": "The operations recorded in this entry.",
"items": {
"type": "union",
"refs": []
}
},
"signatures": {
"type": "array",
"description": "Attestations over the record, attributing its ops to one or more authors. Stripped before CID computation so the signing
payload is stable. Each entry is either an inline attestation or a strongRef to a remote proof record.",
"items": {
"type": "union",
"refs": ["#inlineSig", "com.atproto.repo.strongRef"]
}
}
}
}
},
"inlineSig": {
"type": "object",
"description": "An inline attestation embedded directly in the record.",
"required": ["key", "cid", "signature"],
"properties": {
"key": {
"type": "string",
"description": "Public-key reference identifying the signer."
},
"cid": {
"type": "string",
"format": "cid",
"description": "The computed attestation CID."
},
"signature": {
"type": "bytes",
"description": "The normalized signature bytes over the record CID."
}
}
}
}
}The inclusion of the signature allows the oplog record to be replicated to multiple PDS while still being cryptographically attributed to the original author.
In addition to the OP log we can create a document record to hold the fully hydrated document to a specific point
{
"lexicon": 1,
"id": "com.example.doc",
"defs": {
"main": {
"type": "record",
"key": "any",
"description": "A document. The record key is the document's GUID, matching the `docId` field. The document body schema is not yet defined;
for now it is carried as an opaque value. A compressed snapshot of the document's operation log travels alongside it as a zipped JSON blob.",
"record": {
"type": "object",
"required": ["docId", "oplog", "lastOpId"],
"properties": {
"docId": {
"type": "string",
"description": "The GUID of this document. Matches the record key."
},
"body": {
"type": "unknown",
"description": "The document body. Schema is not defined yet; treated as an opaque object for now."
},
"oplog": {
"type": "blob",
"description": "The document's operation log as a ZIP-compressed JSON file.",
"accept": ["application/zip"]
},
"lastOpId": {
"type": "unknown",
"description": "Identifier of the most recent operation reflected in this document state. Acts as a logical timestamp/version marker for
the document. Schema is opaque for now."
}
}
}
}
}
}This record is entirely optional however it makes it much easier for someone to pick up editing a document by giving a fully realized starting point. Of note is the oplog included here as a blob reference to a zip file. This is the complete operation log from all the records that have been processed, compressed into a zip file so they can easily be read into a client.