Discussed herein is a technique for replication of keys across regions of a cloud infrastructure. A first vault is created in a first region. The first vault stores a plurality of records, each of which is associated with a key and corresponding metadata. A second region, different from the first region, is selected where replication of the plurality of records is desired. A second vault is created in the second region. The plurality of records are relayed from the first vault to the second vault, so that each of the plurality of records is replicated in the second vault based on an entropy value of the record. A mutation operation executed with respect to the first vault is stored as a new record in the first vault. The new record is transmitted to the second vault, which is updated to reflect the mutation operation performed on the first vault.