Delayed job queue

Design a delayed/scheduled job queue that lets services enqueue work to run at a specific future time, from seconds (retry-with-backoff) to months out (a subscription-renewal reminder), at ~20k scheduled jobs/sec enqueue rate with tens of millions of pending jobs. Requirements: a job fires within a few seconds of its scheduled time, a due job is never lost or fired twice, and you can cancel or reschedule before it fires. Walk through the storage and dispatch.