Techniques are disclosed for adding a key column to a table to be replicated, where the key column stores key values for use in replication. In one embodiment, a request is received to add a table to a replication domain, such that the table is replicated from a first database server to at least a second database server. Key values are generated for both existing records and new records subsequently requested to be inserted into the table, respectively. Each generated key value is unique across the replication domain. Further, the key column may be added to the table without requiring exclusive access to the table.