A response to this article on Redis: http://aphyr.com/posts/283-call-me-maybe-redis
A great alternative to thinking about things in terms of CAP that Justin brings up is harvest-yield, where yield is the probability of completing a request and harvest is the fraction of your data that the response actually represents. Here's the paper: http://lab.mscs.mu.edu/Dist2012/lectures/HarvestYield.pdf