Delayed message delivery

Design a delayed/scheduled message service that lets producers enqueue a message to be delivered at an arbitrary future timestamp (from seconds to 1 year out). Scale: 500M scheduled messages in flight, 50K new schedules/sec, delivery accuracy within ±1s of the target time, at-least-once delivery to downstream consumers. Schedules can be cancelled or rescheduled before they fire.