How to remove expired records from a large database?

Hello,

I am exploring the various methods to remove expired records from a large database (millions of records) running on an internet-scale service. I thought of the following approaches so far:

1. run a dedicated clean-up service that scans the entire table and removes the expired during non-peak hours. This is not optimal
2. lazy removal by returning an error to the user when the user requests for an expired record and removing the expired record on demand. This is not optimal either
3. run a dedicated cleanup service against the replica of the database. The dedicated service gathers the primary key of all the expired records. The expired records are removed from the primary database during non-peak hours. This approach avoids a full table scan
4. Remove records from the replica database. Copy the new records to the replica database that was inserted in the meantime and redirect traffic making the replica the new primary DB.

Please share your thoughts on alternative approaches!