ri/blog

Recently, an old project of mine came up in the Apache Wave mailing list. CTree, for those not aware, is a competitor to OT (Operational Transform), the algorithm that makes up the heart of Wave. Unfortunately, I haven’t worked on CTree in a long time, so obviously CTree is a dead project, and DEJE is the future, right?

No. I have big plans for CTree. I may not be actively working on it, but it isn’t dead, it’s dormant. And I’m finally putting those plans into a blog post I can give people when they ask me about it.

What is CTree?

Like OT, but less terrible.

Okay, well let’s hear about that first

OT is a system for real-time, asynchronous exchange of information deltas (changes) that provides eventual consistency (given enough time, the data will look the same to everyone) based on operations composed of simple, reversible instructions.

It has a lot of advantages, and is one of the popular synchronization systems for text data, used as the foundation of Wave, Gobby, Etherpad, and more. It’s also an infernal bitch to scale in multiple ways.

There are serious performance problems you run headfirst into, that are inherent because you have to track the state of everyone you’re connected to (this is why Wave performed so poorly).

There are no formal instruction specifications, so you can have subtle implementation differences between OT apps - perfectly fine until they need to communicate. Then you have the two processes blindly and naively talking in slightly different dialects, which tends to work for ten minutes and then suddenly glitch horribly. Wave was always intended to federate, but it picked one of the least friendly sync engines in terms of federation, which is why it took so long to get ports to other languages and such.

And CTree solves those issues?

Yes.

While ConcurrenTree was originally a very close fork of OT in spirit, over time it became agressively different. However, it still uses some of the same terminology - transactional operations composed of atomic instructions.

CTree has always been designed with a specific use case in mind: distributed realtime collaboration, with an obvious correct implementation (no crazy dialects) and no need to care about anyone else’s state. It is less efficient than OT, as it imposes a structure onto the content that OT does not, but it is much easier and more consistent/reliable to use, because it does not impose any structure on operation or peer state tracking (the most egregious problems of OT implementations).

It gets most of its unique benefits and downsides because operations are portable and idempotent, but irreversible. You can apply an operation once, twice, twenty times, and it’ll always result in the same data. But operations can overlap (performing the same idempotent operations), which makes it impossible to reverse an operation, and be sure that you’re only reversing that operation.

Orchard

Orchard was an alternative to Wave based on CTree instead of OT. It used Socket.IO to talk to the browser client, and trade CTree deltas over a protocol called BCP (Basic CTree Protocol).

It had a few intentions that were never completely realized:

  • Communicate between multiple servers via MCP (Multiplexed CTree Protocol)
  • Provide full graphical management and editing of CTree data
  • Use self-describing metadata as part of documents, to control permissions

The last part was what made it futile. Eventual consistency was ultimately incompatible with a strong, data-central versioning necessary for self-describing permissions controls. How do you enforce those kinds of controls when you’re intentionally using a lazy sync algorithm?

It was this problem, that eventually led to the birth of DEJE.

DEJE

DEJE was another sync engine designed to make self-describing permissions possible. It is founded on the idea that there is a single, central correct version of the content, but it is still managed by a distributed group of trusted peers. It is loosely inspired by Bitcoin, which works the same way at high level - using a blockchain to maintain a central versioned dataset policed by everyone who uses it.

The weak point of DEJE is that it’s really crap at realtime delta transfer. Every change has to be confirmed by a customizable consensus of verification by humans or algorithms. This makes it perfect for DJDNS, a DNS server system that stores all registry data in DEJE. It makes it crap for Wave-like communications.

The future

So what are we going to do about Orchard? If neither DEJE nor CTree is a sufficient choice for replacing federated OT, what do we have? We’re certainly not inventing yet another sync engine, right?

Of course not. We’re making a sandwich.

Sandwich?

DEJE is the bread, CTree is the stuff inside. DEJE provides everything that CTree needs to be self-sufficient - an environment with strongly verified, versioned central metadata. And CTree provides what DEJE is missing - realtime communication at high speed, using portable operations.

When DEJE is mature enough, I’ll be developing tech to embed CTree data into DEJE documents, allowing CTree to piggyback on those documents. This gives us everything we need for any kind of distributed collaborative app, including Orchard.

So what happens to Orchard and CTree in the future?

Mostly, trimming. I’m getting rid of the CTree protocols (BCP and MCP), such that CTree no longer cares about the network side at all. It leaves it up to the code using the library to validate and feed in the operation data.

Orchard will be getting lots of gut rewriting, so that it uses DEJE as a base and CTree as the realtime running on top of it. This will be a big change, but a good one, and DEJE should be pretty mature by then.

And of course, all of this is on hold until DEJE is mature, and DJDNS (which is a higher-priority project) is well-established. Until DEJE is stable, reliable, and supports CTree embedding, I won’t be making any major changes to CTree or Orchard.

I’m here from the mailing list. Is this tech a viable replacement for Wave/OT?

No, but it definitely will be, if I can get the necessary development hours into it. I have no doubt that Project Sandwich will be an easier, more portable foundation for Wavelike tech than OT ever can be, and I would be tickled pink if it was ultimately adopted to replace OT in Wave, though I would be surprised if those folks would be willing to completely throw out OT after existing time and code investments.

But of course, this all blocks on DEJE, and getting DJDNS off the ground. I recommend checking out both projects on Github, and working on sponsored issues. Even if you don’t need the money, I use sponsorship to differentiate between issues that are ready for third-party work, and issues that aren’t (usually either blocked by another issue or on my personal todo list).

General notes

I’ll be working primarily on maintaining and updating my Linode machines over the next few days, while I order my replacement desktop from System76 (yes, supercalculator is acting up again, the little scamp). So it may be awhile before I can properly hack on the projects listed in this blog post, but I don’t intend to lie around while I wait for the 21st century commerce infrastructure to deploy a miracle of engineering to my doorstep.

Happy hacking, and thanks for reading this gigantic wall of text.