Eventual consistency - following the Middle Path

One of the features of Amazon's SimpleDB is that a write to the database may not be immediately reflected to all readers, and that the user of the interface needs to be aware of this and work with it accordingly.

For those of us used to working with relational databases, which generally provide support for full read consistency, this is a somewhat revolutionary thought. But Werner Vogels, CTO of Amazon.com, explains in his blog that in scalable systems where data must be shared across machines, consistency inherently limits availability, particularly in larger systems where network partitioning is common:

Eric [Brewer] presented the CAP theorem, which states that of three properties of shared-data systems; data consistency, system availability and tolerance to network partition one can only achieve two at any given time. A more formal confirmation can be found in a paper by Gilbert and Lynch.

A system that is not tolerant to network partitions can achieve data consistency and availability, and often does so by using transaction protocols. To make this work, client and storage systems are part of the same environment and they fail as a whole under certain scenarios and as such clients cannot observe partitions. An important observation is that in larger distributed scale systems, network partitions are a given and as such consistency and availability cannot be achieved at the same time. This means that one has two choices on what to drop; relaxing consistency will allow the system to remain highly available under the partitionable conditions and prioritizing consistency means that under certain conditions the system will not be available.

Both require the client developer to be aware of what the system is offering. If the system emphasizes consistency, the developer has to deal with the fact that system may not be available to take for example a write. If this write fails because of system unavailability the developer will have to deal with what to do with the data to be written. If the system emphasizes availability, it may always accept the write but under certain conditions a read will not reflect the result of a recently completed write. The developer then has to make a decision about whether the client requires access to the absolute latest update all the time. There is a range of applications that can handle slightly stale data and they are served well under this model.

He then goes on to describe one form of consistency, called eventual consistency, where there is a time lag between an update and the ability of all clients to read that update.

Eventual consistency. The storage system guarantees that if no new updates are made to the object eventually (after the inconsistency window closes) all accesses will return the last updated value. The most popular system that implements eventual consistency is DNS, the domain name system. Updates to a name are distributed according to a configured pattern and in combination with time controlled caches, eventually of client will see the update.

I love this -- eventual consistency. I think this is the way things actually work on the large scale in the real world. And when you design a system this way, it allows you to, in a sense, breathe, and you end up with something that is much more tolerant and scalable.

It reminds me of the story of the Buddha. He was trying to find God, and he was so strict and severe in his austerities that he was practically starving. He was feeling lost, wondering why all this effort wasn't leading him to God. Then he overheard a man instructing a student how to tune a stringed instrument: "don't tune the string too loose, or it will make no sound. Don't tune it too tight, or the string will break." And Buddha saw this as a message to him to follow the Middle Path, to relax and breathe while still following a healthy discipline.

In a way, requiring strict consistency is like tuning the string too tight. The constraints are so severe that the system is brittle and easily breaks.

So, Grasshopper, when building scalable systems, may we follow the Middle Path of Eventual Consistency.

Interesting stuff from LinkedIn - Project Voldemort

Although the name is a bit odd, Project Voldemort itself looks interesting.

The folks at LinkedIn have open sourced a distributed cache/storage engine under the Apache 2.0 license. The interface looks a lot like memcached: get(key), put(key, value), delete(key). The key (haha) difference is that it is not just a cache - it's also provides persistent storage.

I recommend taking a look at their design page. Here are some things

No structure, no queries

Project Voldemort explicitly eliminates the structured form of relational databases and queries, just like memcached. This means if you want to do things like queries, joins, etc., then you need to do it yourself.

It appears that one way they solve this is by building pre-built "answers" to queries by running Hadoop queries and then putting the result back into the storage engine en masse. Much more efficient than trying to run the queries against your "live" store.


Eventual Consistency and Ordering of Versions

They also seem to be following the principles laid out by Werner Vogels and the Amazon team around providing eventual consistency.

I also particularly liked how they do versioning (a version is defined by a tuple of server numbers and version numbers) and how they handle conflicts and fix consistency issues: they go ahead and write whenever you want to write, and then when someone does a read, they look at the various versions and make a decision who wins (or decide there is a conflict and mark it as such so that the problem can be resolved manually).


But Does It Work?

Being a long-term database guy, I always wonder what key functionality you are giving up when you go for the simple key/value way of doing things. I know it scales, and I know it is fast, and I know it avoids issues with network partitioning. But what requirements does it place on the client as a result? They mention, for instance, that this solution separates business logic from data storage, and that's a good thing. It's funny, because in my Sybase days, placing business logic close to data storage was considered the right way to go - function shipping instead of data shipping.

Anyway, it looks like another distributed key-value store has hit the streets. I have some time right now, maybe I'll take a closer look. And I'll be doing the same thing with SimpleDB and CouchDB while I'm at it...

The exponential cost of contention

I enjoy Nati Shalom's blog, although it always has that taste of having the agenda of pushing Gigaspace's solutions. But putting that aside his posts are always well thought-out and well written.

I think his latest blog on the Economies of Non-Scale really drive some points home about scalability, or more to the point, the cost of non-linear scalability.

If 90% of our application is free of contention, and only 10% is spent on a shared resources, we will need to grow our compute resources by a factor of 100 to scale by a factor of 10! Another important thing to note is that 10x, in this case, is the limit of our ability to scale, even if more resources are added.

...

1. The cost of non-linearly scalable applications grows exponentially with the demand for more scale.

2. Non-linearly scalable applications have an absolute limit of scalability. According to Amdhal's Law, with 10% contention, the maximum scaling limit is 10. With 40% contention, our maximum scaling limit is 2.5 - no matter how many hardware resources we will throw at the problem

That's something to chew on. These are real costs, both to your business, to your users, and to the environment. Even if you only have a teeny 10% contention in your system, that 10% will nail you faster than you can say ACID semantics. And as has become very clear to me the final breaking point, the final point of contention in any traditional web application architecture, is the database. Get rid of that and you're home free.

How do you do that? Well, there are a lot of people trying to solve this problem with things like space-based architectures, eventual consistency, distributed map/reduce and Stonebraker's H-Store architecture. Anything to let each instance stand on its own and not have to serialize with the rest of the system at any point, in any form.

Some people argue that scalability is so hard that you shouldn't think about it until you need to. But I really believe that if you do enough to educate yourself and make some wise choices, you will be very glad you did.

What I'd like to see is the industry coalescing around some best practices, an open source "scale stack" ala LAMP, tools, community, and hosting environments like Amazon, that allow developers to easily build applications that will scale from the get go. That's where I want to see things go. That way you don't have to throw your hands up and hope for the best. Because as you can see, the costs can be deadly.

Something to think about...

Design principle: question your assumptions

A lot about good software engineering and design is about listening - listening to that little voice in your head that's telling you you're pushing it, forcing a design or an implementation onto a problem that's not a good fit.

It's very hard for me to listen to this voice when I've got a particular solution in mind, and I'm plugging away implementing this solution, and if I can just get past this next hurdle, it will work, dammit!

Yesterday I finally noticed I was banging my head against a problem.  I thought about what the struggle was, and I realized that most of my pain was in trying to coordinate two separate threads of control through the system - one doing updates and one posting those updates to listeners.

So I decided to apply a common principle for me: question your assumptions.  Did they really have to be coordinated?  I contacted some other members of the team and our product manager and asked what they thought.  It turns out there was much more flexibility than I thought was possible.  If I tried to stop having absolute control, as it were, relaxed a bit, and let things be a little loosy-goosy, then my overall design became much less coupled and thus much simpler.  Ahhh....

It reminds me of the beauty of eventual consistency - if you let go some of your tight constraints, it's amazing how it opens things up and brings new possibilities into the solution.

Dooth Booty at MySQL Conference next week

Off to the MySQL conference next week. I still have to remind myself that MySQL is now part of Sun - it's so easy to think of "them" as a separate company that we're just partnering with. It really is something that takes a while to get your head around.

I'll be doing a ton of dooth booty, um booth duty, on Tuesday and Wednesday. Come to the NetBeans booth in the morning and I'll be there, and maybe I can get you a T-Shirt. XXXL of course :)

We'll be showing off what you can do with NetBeans and MySQL, and I also would love to talk to folks about what you want for database tooling in an IDE (and what you don't want).

I'm looking forward to hearing from Mårten Mickos and Jonathan Schwårtz. It should be very interesting to see where these guys see MySQL going next. And then there is Werner Vogels, my "hero" of eventual consistency. Should be good.

I also hope to meet a number of my colleagues from MySQL as well as dear old friends from the Java DB, PostgreSQL and HADB teams (which are now part of the New Database Team).

It should be a time of good information, good friends, and good cheer.

Why not just put the whole friggin' thing in memory?

When I was at Sun, I worked on the design for a replicated in-memory data store. One of the principles was, scale and throughput demands are increasing, and memory is getting cheaper, so why not put it all in memory, and use disk/database only as a backing store. We provided durability not through writing to disk but through replication, and then writing back to disk (e.g. to a traditional relational database) in the background. Even if there were a node failure, we would recover from the replica, not from the database.

We couldn't get this project funded for various reasons. It's been frustrating because I knew we were on to something but couldn't make it happen - and now, as many of us predicted, the industry is moving in that direction - a growing belief in denormalization, caching, and eventual consistency. But still, many applications write to the database as part of the cycle of a transaction.

But this article at HighScalability hit the nail on the head - you evolve your application from database-centric to cache-centric to memory-centric. Money quote:

As scaling and performance requirements for complicated operations increase, leaving the entire system in memory starts to make a great deal of sense. Why use cache at all? Why shouldn't your system be all in memory from the start?

Well, that sounds awfully familiar. And it's true. If you are replicating anyway, your risk of data loss is pretty minimal, and as Pat Helland, Amazon ex-architect says, computer suck, and you should just plan to apologize sometimes. If you batch your changes every N minutes, then you have an N minute window where some changes may be lost. But for many applications, that's OK. And the wins you get in terms of throughput are significant.

Latency was slashed because logic was separated out of the HTTP request/response loop into a separate process and database persistence is done offline.

It looks like the way they implemented an all-memory solution was using Gigaspaces, which, by the way, has a solution that deploys and scales automatically on the Amazon EC2 fabric. And the result: near linear scalability and 1 billion events a day[1]. Yeah, that's the ticket.

[1] I think actually this statement is misleading. Reading the article more carefully, they are claiming they can get to 1 billion events a day. This hasn't actually been tested, so take it with a grain of salt.

Posted via email from David Van Couvering's Posterous