Time keeps on slippin’, slippin’, slippin’ into the future.
This blog is about the Stig project, and eventual concurrency is Stig’s central idea. This is a twist on the more common NoSQL notion of eventual consistency, and it gets us out of jams.
In a Stig database, each user’s view is always consistent. Things behave as the programmer expects and Stig always responds promptly to the user. In other words, Stig is transactionally consistent, available to users planet-wide, and tolerant of hardware and network faults. This combination of properties is well known to be impossible (CAP forbids), so you can bet something has to give somewhere.
With Stig, each user acts in his or her private universe. Within each universe, time flows consistently forward (that is, the way your natural intuition says it should) and all operations are consistent. Change a value and it stays changed. Read a value twice and be assured of getting the same answer both times. This works for everyone, everywhere, all the time.
It’s in the spaces between the private universes that Stig is free to monkey with time and meaning. It propagates each user’s changes asynchronously, in the background, knitting them together into a consensus that everyone can see. Stig decides the consensus such that it won’t violate anyone’s preexisting ideas of how the universe is, but might fill in a lot of information about which they were previously unaware. It’s like having the time-travel equivalent of a crumple zone: whatever might be inconsistent, Stig rearranges so as to preserve meaning and avoid conflict.
This consensus takes Stig some time to decide, but it’s time outside of the flow of events within each private universe. Users generally don’t have to wait for consensus, so the lag—often only a few milliseconds of real time—vanishes completely. Interstitial time appears to be a gap in CAP.
Of course, it really isn’t. In strict CAP terms, Stig is sacrificing availability. It limits each user’s ability to see the latest changes made by someone else. But it does so in way that, for most applications, isn’t important and is easily hidden.
If one doesn’t interact with another user directly, there’s no possible frame of reference in which to notice the gap in update availability. And while users of a real-time chat program might notice the gap, it would only be problematic if it were lengthy. Stig’s performance is such that the chat room would have to involve thousands of people before the consensus became time-consuming to form.
Of course, what the large print giveth, the small print taketh away. There are limitations. There are situations in which Stig can’t please every user and someone’s private universe is going to suffer. You may need to think about how to handle trade-offs in concurrency, but Stig provides a powerful and expressive set of tools to help you. Our guiding principle: if Stig can’t make the problem go away, it should at least bring the problem into sharper focus.
I’m biased, of course, but I think Stig’s programming model of strict consistency blended with eventual concurrency is beautiful. It also has the virtue of being as simple as possible but no simpler. Perhaps that phrase makes you wary. If so, good; programmers should be wary.
But I hope it also makes you curious enough to Stig with me for a while.
(Ugh, I can’t believe I ended on a pun. Oh wait, I didn’t.)
Jason Lucas April 1st, 2014
Posted In: Uncategorized
One should never, never doubt what nobody is sure about.
CAP theorem has pried up a lot of things we thought were nailed down. I think it’s comparable to what Einstein did to Newton: just a minor change in the way we look at things that compacts all prior ideas, serviceable as they were, into a single, trivial case of a far weirder world.
The current generation of database servers has felt the reality of CAP. These are projects marked by explosive creativity and a giddy willingness to smash things up. Definitions have been particularly prized targets for dismemberment. The ACID properties, long held by experts to be the bedrock of database, have given way to BASE. Experts can’t even agree on what that acronym stands for.
All this tumult has gone under the banner of the NoSQL movement. Calling it a movement is, I think, fair, in the social and political senses of the term. It is a groundswell, motivated by immediate needs as well as by a shared, passionate intuition about what’s right. It’s also a big tent, full of people who are eager for change and leery about empowering a new regime too hastily.
Nevertheless, some concepts are firming up, some wandering camps are becoming entrenched positions. There are variations within the themes, of course, and people applying spins. The alignments are sometimes hard to see.
Observers often categorize each NoSQL project by how it faces the fundamental tradeoffs of CAP: consistency, availability, and partition tolerance. In essence, we ask each project, ‘Whom shall we screw?’
If we sacrifice consistency, we’re screwing our programmers. Programming in a world where constants aren’t and variables won’t is a lot more fun to joke about than to do. Programs either become dominated by error-handling code or are riddled with semantic gaps. As is often the case in situations of inherent complexity and uncertainty, the people who aren’t going to pieces are usually the ones who haven’t grasped their predicament.
Sacrifice availability, and the screwee is the user. The system is consistent and perfect and can’t be bothered to accept a connection. Calls time out or otherwise fail with a regularity that programmers find reassuring and users find deadly. Although it might pass its unit tests and be verified against its spec, the system probably falls short of solving the real-world problem it was aiming for.
But if we refuse to screw either the programmer or the user, we’re forced to screw the world. If we can’t accept partition tolerance, we will simply never scale to the levels necessary to serve the whole planet. In the far-reaching internet ocean, not every wave will arrive in an orderly fashion. If we insist otherwise, we’re confined to the shallows.
This is bleak heart of CAP. It is unavoidable, proven beyond argument. No matter how clever we are, no matter how much hardware we throw at the problem, somebody—the programmer, the user, or the world-wide audience—is going to take one for the team. More often than not, we programmers, noble beings that we are, throw ourselves on the grenade and sacrifice consistency.
As with so many of the ugly realities of life, we wrap this idea up in a euphemism. We use the term eventual consistency, which I think has a lovely, hopeful ring to it. It seems to say that, maybe not today, but someday, this goddamn program will be right.
We also carefully pace off the perimeter of the safety zone, the part of the program where we know we can be consistent. Often this means we can reliably update only one object at a time. (Or row or whatever your machine’s basic unit might be.) If we have to coordinate updates between two or more objects, well… maybe eventually it’ll be ok.
Let me come clean about this. The whole idea of eventual consistency makes my feet itch. It runs contrary to my intuition about what a database is meant to be. I also think that single-object consistency is like kissing one’s sibling: it’s nice, but doesn’t promise any thrilling possibilities.
Keeping things consistent for a single user surely isn’t a problem. We only run into trouble when we need to be consistent across a large number of users. (And by a large number, I mean everyone on Earth.) To me that suggests not eventual consistency, but eventual concurrency.
I’ll talk more about eventual concurrency eventually. Ok, immediately. As in, the very next post.
Jason Lucas March 24th, 2014
Posted In: Uncategorized
Moderation is a fatal thing… Nothing succeeds like excess.
But I’m sure most people know Stig as a database system, distributed runtime environment, and programming language that simplifies the development of massively scalable web and mobile applications.
Well, maybe they don’t know Stig yet, but I’m here to introduce you. Let’s start with our tag line:
Stig powers innovation at planetary scale.
Ok, that’s a bold claim. How can I possibly back that up? I’ll start with a line of pseudo-math on which to hang some definitions:
Innovation = Insight × Confidence × Iteration Rate ÷ Cost of Failure
Therefore, Stig must:
This is what our project charter amounted to when we started, four years ago, at Tagged in San Francisco. Since then, our team has grown a little and our code base has grown a lot. But there’s still so much more to be done.
That’s why Tagged, the Stig team, and I think it’s time to open the project to all of you. We hope the open source community will adopt Stig, benefit from it, and help us to make it better.
And who wouldn’t love a compiler that thinks it’s a database that thinks it’s a distributed operating system?
Jason Lucas March 19th, 2014
Posted In: Uncategorized