A system and method for a distributed database that is consistent but non-blocking. This distributed database, also referred to as a datastore, has a number of desirable features. Without wishing to be limited by a closed list, these features include but are not limited to: providing strong, ANSI SQL-compatible consistency guarantees; being distributable across multiple computers, data centers and even geographical locations; having a resilient, fault-tolerant architecture, where even failures of multiple different data centers can allow the operation of the datastore to continue seamlessly, depending on the configuration.