pbailis

For a fixed amount of throughput, if I want consistent reads, I pay x dollars. If I'm okay with eventual consistency, I can pay x/2 dollars and get the same throughput.

Conflating resource usage, pricing, and consistency using a single metric (here, price) seems confusing, especially without the right metrics to guide devs.

Right; you need some notion of a total order or commutativity in your update functions. f(A,B) = f(B,A). "Last writer wins" is one example of commutativity, but that isn't often what you want.

What you want is something like a "Commutative Replicated Data Type" [1], where you define a commutative function specific to your application. Libraries like StateBox allow you to build CRDTs [2]. In fact, your example of document editing was one of the areas where these ideas first came up.

There's also a theorem saying that if your program is "logically monotonic"--that is, if your data only "grows" in size, and facts never change from True to False or vice versa--then your program will work under eventual consistency without modification [3].

Finally, bank accounts have to employ eventual consistency. Banks demand availability from their ATMs and give up consistency to handle partition tolerance: your ATM will still work even if you sever its network connection. However, banks, unlike a lot of software, have well-defined compensation protocols for handling inconsistency. For example, they'll charge you for negative balances left in your account via overdraft fees.

[1] http://arxiv.org/pdf/0710.1784.pdf

[2] http://labs.mochimedia.com/archive/2011/05/08/statebox/

[3] http://databeta.wordpress.com/2010/10/28/the-calm-conjecture...

You make a good point. Without additional safeguards/depending on implementation, W=1 can indeed mean "durability of one".

This also depends on your failure model. If your node crashed (RAM cleared) and your durable storage broke, you're in trouble. If the data was durably persisted and you just have to restart the node, it's a better situation.

Shameless plug:

Interactive Demo: http://bailis.org/projects/pbs/#demo

PBS for Cassandra: https://github.com/pbailis/cassandra-pbs

This depends. Even with W=R=1, you still send each read/write to every replica. If the replica that acknowledged the write fails, the other two replicas should eventually receive the write.

But--what happens if the write messages to the other two replicas drop? Well, typically the coordinator will hand the write off to replacement replicas (hinted handoff/sloppy quorums). Alternatively, when you detect the message loss via a timeout you could retry. But what happens if the coordinator dies and can't retry? Then you'd better replicate your coordinator. That gets hairy, so hinted handoff and sloppy quorums are easier. However, whichever way you go, it's definitely possible to handle an arbitrary (still fixed) number of node failures without data loss.

In general, though, sloppy quorums/hinted handoff solve this problem. I haven't heard any data loss complaints with Riak/Cassandra/Voldemort due to replication, but I'm very interested to hear if you have.

You can definitely extend PBS to node failure cases/sloppy quorums/hinted handoff. The main reason we didn't was because we don't have good failure data. There's nothing stopping you, and, as we point out in the paper/backup slides, you can potentially hide this in the tail (e.g. the .01% of stale cases) provided your DB "does the right thing".

Eventual consistency isn't about "losing writes". It's about how long it will take for all of your replicas to agree on/observe the last written versions and, in the meantime, you'll read potentially stale data.

Certain data structures inherently tolerate staleness or message reordering: look at your Twitter feed, any kind of log, or other "commutative data structures". If you can't handle staleness, you should probably use stronger consistency.

However, if you can find out about staleness after the fact (an asynchronous callback, for instance), you can run some sort of compensatory routine (e.g., overdraft charges for your bank). Then you have an optimization problem: (cost of compensation)*(number of times you have to run compensation) vs. the benefit you get from weak consistency (latency, availability, whatever).

There's an awesome paper by Pat Helland about the problem you mention regarding building real-world systems on top of inherently unreliable components. It's called "Building on Quicksand": http://arxiv.org/pdf/0909.1788.pdf

The Berkeley EECS NFS mount is chugging, so I've mirrored the site at: http://cs.harvard.edu/~pbailis/pbs-mirror/#demo