For the past week, I have felt a wave of relief that we shipped Kiln Harmony, the first DVCS-agnostic source control system. Kiln Harmony’s translation engine ruled my life for the better part of a year, and, as the technical blog series is revealing, probably took some of my sanity with it. But we’ve received nearly universally positive feedback, and built a product that I myself love to use, so I can’t help but feel the project was an incredible success.
A success that started with me half-screaming “that’s impossible” across a table.
That’s impossible!
I like to think of myself as fairly open-minded, but I found those words flying out of my mouth almost before I’d had a chance to think about them.
Joel and I were sitting in his office in January 2012, discussing adding Git support to Kiln. As much as I loved Mercurial, and as happy as we both were that Kiln had been built on top of it, we both also agreed that the time had come to add Git support as well. The support I wanted to build was simple and straightforward: just like every other service that offers both Git and Mercurial, we’d make you pick one of the two at repository creation. To make it easy to change your mind later, I also proposed a one-click method to switch a repository to the alternative DVCS, but any given repository would ultimately be either Git or Mercurial—not both.
Joel’s idea was fundamentally different: he wanted anyone to be able to use either system on any repository at any time. And that’s why I found myself screaming “that’s impossible.”
Developers expect that pushing data to Kiln and cloning it back out again gives them the same repository. To do that, we’d have to round-trip a steady state between Mercurial and Git. No conversion tool at the time could do that, and for a very good reason: while Mercurial and Git are nearly isomorphic, they have some fundamental differences under the hood that were intractable. There are concepts that exist only in one of the two systems, and therefore cannot possibly be translated in a meaningful fashion into the other. Unless you’re the magic data fairy, you’re going to lose that information while round-tripping. In addition, since some of these data are tightly tied to their tool’s preferred workflow, you’re also going to severely hamper day-to-day DVCS operations in the process.
In other words, if we tried to build what Joel wanted, we’d end up with the world’s first lossy version control system, supporting only the narrow band of functionality common between Git and Mercurial. Talk about products that are dead on arrival. I wanted no part.
I ended up going back to my office after that meeting incredibly annoyed. Joel just didn’t understand the internals of the two tools well enough. If he did, he’d agree with me. I’d therefore draft up a paper explaining exactly why you could not possibly build a tool like what he was proposing.
That’s improbable!
Except I ended up doing quite the opposite.
Over and over, I’d pick a topic that I knew was fundamentally intractable—say, handling Git- and Mercurial-style tags at the same time—and bang out a few paragraphs going into the technical minutiae of why it was impossible. Then I’d read back over my paragraph, and realize there were gaps in my logic. So I’d fill gap after gap, until, finally, I’d written a detailed how-to manual for handling exactly the thing that I originally said you couldn’t.
The impossible things fell down one by one. I designed a scheme for Mercurial named branches that involved non-fast-forward merges on the Git side for lossless preservation.[1] I proposed extending Mercurial’s pushkey system in a way to handle annotated tags. I developed a workflow that could handle the competing branching strategies with minimal user confusion. I ended up going home at nearly 8 PM, only to keep writing.
The next morning, I came into the office not with a document explaining why we couldn’t make Kiln repositories simultaneously Git and Mercurial, but rather, a document explaining exactly how to do so.
That’s very unlikely!
At the time, I was still serving as Kiln’s shit-umbrella more than a developer, so I asked Kevin, one of the Kiln team’s best developers, to write me a prototype based on the white paper, thus freeing me up for the vastly more sexy task of merging 15,000 SQL Server databases into one so our backup strategy would finally be viable. (Hey, I was a good shit umbrella.) He put together a surprisingly robust prototype using ideas from the white-paper, extending them nicely in the process, thus indicating pretty strongly that my ideas weren’t all that bad.
Based on Kevin’s prototype, I proposed a new strategy: we would, indeed, make a version of Kiln that had Git and Mercurial “either/or” support, and we’d still aim to have that project shippable by summer on roughly the original schedule. That would be our safety option. Meanwhile, a parallel effort, dubbed “Doublespeak,” would launch to make repositories DVCS-agnostic. If Doublespeak ended in failure, we’d still have a new Kiln version to show in summer with Git support. If, on the other hand, it were promising, we’d delay the launch long enough to ship the more ambitious vision of Kiln with Doublespeak.
By a stroke of luck, things worked out such that I could swap my team-lead duties for developer duties just as Doublespeak development kicked off in earnest, and that’s how I ended up as the lead engineer on the translation engine.
The first thing I did was throw out the prototype. Dogma or no, I realized in my first day of hacking that the original design, by definition, would not perform as well as we needed it to. Its architecture would also have required me to spend a considerable amount of time modifying Git’s internals, which was not appealing to me.[2]
I opted for a new design that would directly leverage Mercurial’s code base and a Python Git implementation called Dulwich. I reimplemented the prototype in a day or two. Then I began the long sledge through gnarly parts of the white-paper: managing ref/bookmark translation and movement. Handling tags. Handling octopus merges. Handling Mercurial’s concepts of filenode parents and linkrevs. As the Kiln “either/or” project wrapped up, more developers started joining me on the translation layer to fill in the increasingly esoteric gaps.
But it’ll still never actually fly!
It wasn’t long before we had a nearly complete solution that was ready for dogfooding. Unfortunately, almost as soon as we began using the new magic, we hit two major problems that threatened to scuttle the project.
The first was that the entire engine was just too slow, limited almost entirely by how much disk I/O Doublespeak had to do to get its job done. This was already brutal on Fog Creek’s private Kiln instance; our ops team was having nightmares about what the disk damage would look like on Kiln On Demand. Thus began months of work to try to get our disk access as minimal as possible. The general mantra was to read any given revision at most once when converting—and, whenever possible, not at all. We introduced caches, memoization, and more. At the beginning, I was landing order-of-magnitude performance improvements daily. By the end, we’d optimized the code base so much that dinky little 2% performance improvements were frequently the result of days of work. But we had the system performing at a level we could actually use.
The second problem we hit was that, while we had lots of experience with how Mercurial repositories were supposed to look, and how Git data was supposed to look, we grossly underestimated how much real-world variation there’d be in Mercurial and Git repositories. The Kiln team spent weeks adding more and more “corrupt” data preservation logic to Doublespeak before it could handle real-world repositories like Mercurial itself. But we ultimately got to a place where nearly every repository we threw at the thing losslessly round-tripped.[3]
But we tackled both of these challenges. And soon, dogfooding became alpha, alpha became beta, the Doublespeak code-name became the much less Orwellian “Kiln Harmony,” and, last Tuesday, Kiln Harmony shipped.
That was supposed to be impossible!
I don’t think Joel was prescient and knew Kiln Harmony was doable, and I certainly don’t think he knew how to do everything the white-paper explained before I wrote it. But I definitely believe he knew that pushing me as hard as he did would force me to find a way if there were one to be found.
In case it’s not clear, I’m very glad he did.
This strategy ended up being too clever by half, so we dropped it for a less-perfect but less-surprising solution, but I was very excited to realize it was possible at all. ↩︎
I honestly couldn’t care less whether you like Mercurial or Git at the end of the day, but I think it’s objectively obvious that Mercurial is far easier to hack and extend than Git. Its code base is DRY, orthogonal, written in Python, and (in the sense of executable count) monolithic. Therefore, solutions where the hacking could be more in Mercurial, and less in Git, were highly attractive. ↩︎
Annoyingly, we somehow spaced ever checking the Linux kernel, so of course that was one of the first repositories someone fed Kiln Harmony on launch day, and it crashed the translation engine. Thankfully, while there’s lots of user features headlining Kiln Harmony, one of the features the developers are most excited about is that we are finally in a place where Kiln can be continuously deployed. Open-source may make all bugs shallow, but continuous deployment makes all bugs short-lived. ↩︎
Want to comment on this post? Join the discussion! Email my public inbox.