We present a reference architecture for a transactional cloud datastore where data is replicated at multiple datacenters. While we consider Google’s Megastore as our motivating example, we define general abstractions for each of the key components. Therefore, our solution is extensible to any system that satisfies the properties specified by the abstractions. We present a transaction management and replication protocol based on the Paxos algorithm, and we formally prove the correctness of this protocol within our reference architecture. We also show that the Paxos protocol, as it is implemented in Megastore, acts as a concurrency prevention mechanism rather than a concurrency control mechanism. We then present an enhanced protocol that we call Paxos with Combination and Promotion (Paxos-CP). Paxos-CP provides true transaction concurrency and requires the same per instance message complexity as the original Paxos protocol. Finally, we compare the performance of Paxos and Paxos-CP using a prototype implementation of our reference architecture.