Techniques are described herein for performing key rotation and key replacement. In an embodiment, a request is received that specifies key names. A first set of messages is generated, where each message identifies a table that is associated with the encrypted-data locations, and stored in a queue for processing by a first plurality of worker processes. Each worker process retrieves a message from the queue and generates a second message that identifies a subset of encrypted data records from the table. Each second message is stored in a distinct queue which is assigned to a worker process of a second plurality of worker processes. Each worker process retrieves the message from the assigned queue, decrypts the subset of encrypted data records, re-encrypts the decrypted data records using a new encryption key that corresponds to a new key name, and stores the re-encrypted data records in a database.