Originally posted as an answer to this StackOverflow question:

The Google App Engine documentation contains this paragraph:

Note: If your application receives an exception when committing a transaction, it does not always mean that the transaction failed. You can receive DatastoreTimeoutException, ConcurrentModificationException, or DatastoreFailureException exceptions in cases where transactions have been committed and eventually will be applied successfully. Whenever possible, make your Datastore transactions idempotent so that if you repeat a transaction, the end result will be the same.

Wait, what? It seems like there’s a very important class of transactions that just simply cannot be made idempotent because they depend on current datastore state. For example, a simple counter, as in a like button. The transaction needs to read the current count, increment it, and write out the count again. If the transaction appears to “fail” but doesn’t REALLY fail, and there’s no way for me to tell that on the client side, then I need to try again, which will result in one click generating two “likes.” Surely there is some way to prevent this with GAE?

Dan Wilkerson, Simon Goldsmith, et al. designed a thorough global transaction system on top of App Engine‘s local (per entity group) transactions. At a high level, it uses techniques similar to the GUID one you describe. Dan dealt with “submarine writes,” the transactions you describe that report failure but later surface as succeeded, as well as many other theoretical and practical details of the datastore. Erick Armbrust implemented Dan’s design in tapioca-orm.

I don’t necessarily recommend that you implement his design or use tapioca-orm, but you’d definitely be interested in the research.

In response to your questions: plenty of people implement GAE apps that use the datastore without idempotency. It’s only important when you need transactions with certain kinds of guarantees like the ones you describe. It’s definitely important to understand when you do need them, but you often don’t.

The datastore is implemented on top of Megastore, which is described in depth in this paper. In short, it uses multi-version concurrency control within each entity group and Paxos for replication across datacenters, both of which can contribute to submarine writes. I don’t know if there are public numbers on submarine write frequency in the datastore, but if there are, searches with these terms and on the datastore mailing lists should find them.

Amazon’s S3 isn’t really a comparable system; it’s more of a CDN than a distributed database. Amazon’s SimpleDB is comparable. It originally only provided eventual consistency, and eventually added a very limited kind of transactions they call conditional writes, but it doesn’t have true transactions. Other NoSQL databases (Redis, Mongo, CouchDB, etc.) have different variations on transactions and consistency.

Basically, there’s always a tradeoff in distributed databases between scale, transaction breadth, and strength of consistency guarantees. This is best known by Eric Brewer’s CAP theorem, which says the three axes of the tradeoff are consistency, availability, and partition tolerance. More details in my Transactions Across Datacenters talk.