  In this paper, we present STAR, a new distributed in-memory database with
asymmetric replication. By employing a single-node non-partitioned architecture
for some replicas and a partitioned architecture for other replicas, STAR is
able to efficiently run both highly partitionable workloads and workloads that
involve cross-partition transactions. The key idea is a new phase-switching
algorithm where the execution of single-partition and cross-partition
transactions is separated. In the partitioned phase, single-partition
transactions are run on multiple machines in parallel to exploit more
concurrency. In the single-master phase, mastership for the entire database is
switched to a single designated master node, which can execute these
transactions without the use of expensive coordination protocols like two-phase
commit. Because the master node has a full copy of the database, this
phase-switching can be done at negligible cost. Our experiments on two popular
benchmarks (YCSB and TPC-C) show that high availability via replication can
coexist with fast serializable transaction execution in distributed in-memory
databases, with STAR outperforming systems that employ conventional concurrency
control and replication algorithms by up to one order of magnitude.
