complex scheduler solution ideas please

What is a scalable solution for running lambda at specific times in the future?

We are building a SaaS platform, in which our users can request a task to happen according a recurring schedule (simple parameter of {"frequency": "NNN minutes"}. They can also edit/delete this schedule, to affect that future events. There will be K's of users, requesting M's of tasks over time (from 1 min to 1 year). The tasks will not be created in the order they should execute. I need high integrity on completion.

I've discounted just using sqs. I've looked at cloudwatch events, but have concerns about scaling. I've considered putting the tasks into a DB table then polling. Is there something else I should look at?