My understanding of how it all fits together, please correct if wrong: the default datastore is (strongly!) consistent and partition tolerant but sacrifices availability. The new HRD gives you availability and partition tolerance at the cost, potentially, of consistency. You can get an intermediate state by wrapping writes in taskqueue tasks, which I do for writes that can wait but must not fail on the standard datastore.
To clarify: the HRD sacrifies some consistency, but the sacrifice is limited. It still maintains consistency within an "entity group", using the Paxos algorithm for distributed consensus. Consistency is sacrificed only for queries that span entity groups. Retrieving individual records, or queries within an entity group, are strongly consistent even in HRD. The primary tradeoffs for HRD really are cost (because you're maintaining more replicas of your data), and write latency (because you're updating multiple locations). For those not familiar with App Engine terminology, each database is partitioned, by the developer, into shards called Entity Groups -- see http://code.google.com/appengine/docs/python/datastore/entit... for details.
How is consistency sacrificed with HRD? Do you mean that, with HRD, you could potentially see the effects of some write W to entity group A, write some value dependent on that write to entity group B, then immediately look at entity group A and see a pre-W value?
No, the scenario you describe could not occur -- it would involve a consistency violation within entity group A. Once you see the effects of write W to entity group A, all operations on entity group A (across all servers) are guaranteed to see W.
The reduced consistency guarantees in HRD involve indexes, because indexes span entity groups. An example: suppose that you set name=foo in record A1, which is part of entity group A. If you then retrieve record A1, that's an operation on entity group A, so you're guaranteed to see name=foo. But if you perform a global query for all records with name == foo, that's an operation on an index, which is outside the entity group and so is not mediated by the entity group's Paxos log. Therefore, your query might not return A1. The index is "eventually" consistent -- it's guaranteed that, eventually, all indexes will be updated. But AFAIK there's no guaranteed upper bound on "eventually". In practice, it should usually be very quick, but only usually.
snewman's comments have addressed most of this. (hey steve!) i'll just add that HRD has more predictable read and write latency, which most developers like a lot, but its writes are also slower on average, since they incur at least one Paxos round across datacenters.
