The Amazon model is the “design for failure” model. Under the “design for failure” model, combinations of your software and management tools take responsibility for application availability. The actual infrastructure availability is entirely irrelevant to your application availability. 100% uptime should be achievable even when your cloud provider has a massive, data-center-wide outage.

…from The AWS Outage: The Cloud’s Shining Moment, O’Reilly, April 2011

Back in the golden days of my youth, my father worked as a technical writer, producing brochure copy for computer companies. I can’t have been much more than ten when I read some of his work: a brochure advertising the benefits of a computer architecture (I forget which one, but it might have been Tandem NonStop that could continue operating in the event of any single, and some multiple, component failures by having redundant links between redundant storage and processor units.

This looked rather fun, but it was only much later, when I learnt about computer networks, that I began to realise you didn’t need special hardware to do this. Although the special hardware is built to be more reliable than commodity equipment, the magic is all in the software that fails over responsibilities to other hardware when part of it breaks. With a little more work, those software techniques can be applied to off-the-shelf hardware joined together by a network.

Back to square one?

But designing software for failure requires new skills. Some parts are easy; any software component that doesn’t hold state is easily replicated to a bunch of servers, as the loss of one merely means losing the state of an in-progress operation. Ideally, protocols like HTTP would do more to help us; perhaps Web browsers that find multiple servers for the same Web site should keep trying if the first one they try doesn’t work, rather than just giving up (there’s a standard for this already: SRV records) so that we do not need tricks like anycast DNS and front-end load balancers to provide decent failover of front-end application servers.

Designing software for failure is an extra barrier to overcome, but isn’t too hard, and it certainly pays off. Largely, it boils down to making sure that operations do not leave the system in an unstable state if they are aborted partway through for some reason. This is mainly a challenge for the frameworks and infrastructure upon which applications are built; with the infrastructure for retrying failed operations built into the system, application developers only really need to worry about the areas where the system can’t automate recovery from failure (such as operations that trigger real-world actions).

Porting legacy applications

But there’s a lot of legacy software out there, that hasn’t been designed for failure. What do we do about that? A lot of cloud users are trying to migrate their existing systems “into the cloud”, and they are the ones who will suffer worse quality of service because of it. Cloud servers and links have a high failure rate. An application that can take advantage of the fact that the cloud offers easy access to a large number of unreliable nodes, and very rapid provisioning of new ones can provide uptimes that put expensive mainframe hardware to shame; but applications written to expect expensive mainframe hardware will not fare well.

But you shouldn’t need to rewrite an application to make it failure-tolerant. Web applications, by their largely stateless nature, are often structured in ways that make building in failure-tolerance quite practical; the code that handles HTTP requests, nine times out of ten, will only have two effects – writing into a database and generating a response. A suitably smart load balancer can wait until a complete response is generated before sending it back to the client, and retry on another server if the response aborts partway through. If there is no storage of state other than in the database (and I’m looking at you, Java servlet session storage…), then the problem really boils down to:

• A fault-tolerant place to store your data.
• Managing a pool of stateless Web servers with request failover via load balancers.

But database fault tolerance is pretty tricky. The market is starting to swell with databases claiming to offer fault tolerance, but most of them merely survive server failures. What if the link between datacentres fails, splitting your system into a European cluster and a US cluster? Few databases can operate in a partitioned environment; and most of those are exotic NoSQL databases that your app will need rewriting to use.

As usual, there’s no silver bullet

Of course, at this point, you’d expect me to say “…except GenieDB!”, but there’s often more to the problem than just the database. You still need to audit the app to make sure it’s not squirreling data away anywhere else, and work out how to manage that “pool of Web servers with request failover via load balancers”.

Rolling out updates to the application becomes more of a challenge and all these new servers need monitoring. Fault tolerant systems are built to hide failures from normal users and, with GenieDB being extremely tolerant of almost complete system failure, measures need to be taken to make sure somebody is alerted before you’ve only got a single server left!

The audit process is quite simple, though. We recently audited WordPress, and found only one issue: it puts uploaded images into the filesystem. We fixed this by writing a WordPress plugin that, whenever an image or other media file is uploaded into a post, copies it to all the other servers, and a mechanism for servers to catch up with uploads they missed during an outage.

We’ve put a lot of work into helping migrate legacy apps into fault-tolerant environments, by finding ways to support the kinds of behaviour they expect from a single-node database, in a distributed environment. Porting WordPress to run on a NoSQL database would be a huge amount of work!

Conclusion

So I think we will see many exciting new things happening as application developers figure out how to take advantage of cloud systems. Applications will start to appear that are fault-tolerant from the start. New tools to help build these applications, with support for failure tolerance built in and that help applications to be fault tolerant, will continue to appear. New tips and tricks and techniques to handle common problems are all out there, waiting to be rediscovered…

There’s been even more discussion about CAP lately. The good news is, there’s now becoming more and more articles explaining the common misconceptions that arose in earlier discussions; and even Eric Brewer himself has recommended Coda Hale’s “You Can’t Sacrifice Partition Tolerance”.

In particular, it draws attention to a different way of categorising the failure semantics of distributed systems, by examining the tradeoff between “yield” (the fraction of queries which are rejected outright) and “harvest” (the fraction of the eligible rows returned by a query).

Non-fault-tolerant systems respond to failure by dropping the yield to zero; the system is shut down.

Fully replicated systems respond to faults by preserving yield and harvest, but reducing capacity; less nodes means less reads per second – but that might cause a loss of yield if the system is then over capacity and has to start rejecting queries. However, if the replication is performed asynchronously, then the system doesn’t actually provide 100% harvest even in the best case – as it may return out-of-date (and, therefore, incorrect) records. Whether you count an out-of-date record as totally worthless, or as having some fraction of the worth of the latest data, and the average fraction of records returned by queries that are actually out of date, affect exactly what this harvest will be.

Fully partitioned systems respond to faults by dropping harvest, as some fraction of the data becomes unreachable when the servers hosting it become unreachable.

Whether harvest or yield is more important, and how much potentially old replicas count towards your harvest, are business decisions, and vary between applications.

So where does GenieDB fit in this model?

Well, our central persistent store is a asynchronously fully replicated. The presence of full replication means we maintain 100% yield (except in REALLY catastrophic situations). Meanwhile, our consistency buffering algorithm means we provide a 100% harvest when there are no faults. But when there are faults, because the consistency buffer is fully partitioned, we return potentially out-of-date data for some fraction of the records. However, we mark those records with a flag indicating that they’re potentially outdated, so the application can choose whether to discard them (making them have a zero contribution towards the harvest), use them with the knowledge that they may be outdated, or just to use them anyway, (and, therefore, having some contribution towards the effective harvest, as they’re better than no records).

An application that is very fussy about data quality, so would rather trade off yield than harvest, can even reject the entire results of the query if any of the records are potentially outdated – thereby trading off harvest for yield.

And this is our corporate ethos – our database aims to provide developers with the flexibility to build different kinds of applications. And more importantly, to build applications that have different requirements in different parts of the system. GenieDB’s architecture makes it cheap for our database to provide the application with the best data it can, along with the information required for the application to choose its own tradeoff between harvest and yield – on a per-query basis.

We’re gearing up to release v0.5 of GenieDB right now, and the biggest new feature in v0.5 is the generic indexing framework.

Originally, GenieDB provided indices on fields of records. As we do not mandate a per-table schema, each record in a table could have totally different fields; so when an index is created on the field “foo” of the table “bar”, we index any record in “bar” that has a “foo” field under that value in the index. If the record did not have a “foo” field, then it doesn’t appear in the index at all (whereas records with a NULL value for “foo” are indexed under NULL, of course).

However, expecting future interesting developments, we made sure this part of the code – figuring out how a given record should appear in a given index – would be easy to extend in future. In general, there could be any function from records to zero or more index entries.

For v0.5 we filled in some more of that infrastructure; we’ve not brought it to its logical conclusion yet. But to start with, we’ve extended the type system with a compound type, which basically represents a sequence of typed component values. This means that any field of a record might be a compound of other values – which, in turn, might be compounds; arbitrary tree structures can therefore be stored.

Our next trick was to extend the indexing system to support compound indices. These refer to a list of fields in their specification, and the indexed value is then a compound made by assembling the values of the named fields from the records. Since each element in the compound has to be associated with a particular field, we have to “stuff” missing fields in the record with NULLs.

The consequence of this is that we can have compound indices, as found in SQL. Which is useful, as we’ve used this facility to extend our MySQL interface to support compound indices in MySQL using it.

However, here at GenieDB, we don’t like to do things by half! Rather than tinkering with how indices work in the low-level indexing engine, we’ve just extended the function that extracts a record’s “index image” to create compound values, which are then indexed. In future, we can add new kinds of indexing function. How about one that splits a string field into words, stems them, maps them to synonym root words with a thesaurus, removes any words found in a stoplist, and then indexes the record under that list of words? That would mean that a record with the indexed field containing “GenieDB developers work too hard!” would appear in the index under “geniedb”, “developer”, “work”, “too”, and “hard”. We could expose this type of index as a free-text index under MySQL, and then support free-text queries with relatively little work. Or how about an index that maps two numeric fields representing latitude and longitude (with an optional third for altitude?) into a three-dimensional Cartesian coordinate relative to the center of the planet, and then combines those three numbers into a Z-order curve and indexes the record under the resulting integer? We’ll then have a geospatial index. How about an index that applies the Double Metaphone algorithm to the words of a string field and indexes the record under the metaphone codes as well as the actual words, with different prefix characters to distinguish them? That’ll give us a fuzzy index that we can search for a word by searching for the literal word (with the appropriate prefix character) as well as for the Double Metaphone codes of the word (with the other prefix character), meaning we will find direct matches as well as approximate sounds-like matches.

But adding more and more index-generation functions into the core isn’t what we want to do. That way lies bloat! What will be much more useful is to embed a suitably sandboxed and lightweight embedded language, so that users can provide their own indexing function that does delightful application-specific things. Things like free-text indices will need special support in the MySQL plugin to appear as MySQL free-text indices, but any type of index might be exposed as a virtual read-only column to be searched on to work around MySQL’s limited view of what an index can do; MySQL doesn’t allow indices on general expressions, but we can provide that functionality directly when we interface with databases that do.