A relational database replication system includes a client, at least one primary database, a plurality of secondary databases and replication agents which coordinate database transactions. The system provides a high level of performance, reliability, and scalability with an end result of efficient and accurate duplication of transactions between the primary and secondary databases. In one implementation, the client transmits sets of database update statements to the primary database and primary agent in parallel; the primary agent replicates the statements to at least one secondary agent. A transaction prepare and commit process is coordinated between the primary database and the primary agent, which in turn coordinates with the at least one secondary agent. Databases can be partitioned into individual smaller databases, called shards, and the system can operate in a linearly scalable manner, adding clients, databases and replication agents without requiring central coordination or components that cause bottlenecks.