286. Delayed Retry Scheduling for Failed Events

Delayed Retry Scheduling for Failed Events

Design an in-memory data structure that schedules failed events for retry at specific timestamps and efficiently retrieves retries that are ready to run.

Retry Rules

Each event is identified by a unique eventId.
An event must not be returned before its scheduled execution timestamp.
Scheduling an already pending eventId replaces its previous execution timestamp.
Retrieving ready events removes them from the pending retry data structure.
Events are returned in ascending order of their scheduled timestamps.
Events with the same scheduled timestamp are returned in ascending lexicographical order of eventId.

Methods

Schedule a Retry

public void scheduleRetry(String eventId, long executeAtTimestamp)

Schedules the given event to be retried at executeAtTimestamp. If the event is already pending, its existing schedule is replaced.

Parameters

eventId: The unique identifier of the failed event.
executeAtTimestamp: The timestamp at which the event becomes ready for execution.

Get Ready Events

public List<String> getEventsToExecuteNow(long currentTimestamp)

Returns and removes every pending event whose scheduled execution timestamp is less than or equal to currentTimestamp.

Parameters

currentTimestamp: The timestamp used to determine which retries are ready.

Returns

A list containing the ready event IDs, ordered first by scheduled timestamp and then lexicographically by event ID. An empty list is returned when no event is ready.

Design Requirements

Explain the data structures used to store and retrieve pending retries.
Scheduling or rescheduling an event should be efficient.
Retrieving ready events should avoid scanning every pending event.
Include the time and space complexity of both methods.

Constraints

1 ≤ eventId.length() ≤ 100
eventId contains letters, digits, hyphens, and underscores.
0 ≤ executeAtTimestamp ≤ 1,000,000,000,000,000,000
0 ≤ currentTimestamp ≤ 1,000,000,000,000,000,000
At most 100,000 method calls will be made.
Parameter values are always valid and never null.

Examples

Example 1

scheduleRetry(eventId = "payment-42", executeAtTimestamp = 5,000)

scheduleRetry(eventId = "webhook-17", executeAtTimestamp = 9,000)

getEventsToExecuteNow(currentTimestamp = 6,000)

Output: ["payment-42"]

Only "payment-42" is ready. It is removed from the pending retries, while "webhook-17" remains scheduled.

Example 2

scheduleRetry(eventId = "callback-b", executeAtTimestamp = 15,000)

scheduleRetry(eventId = "callback-a", executeAtTimestamp = 15,000)

scheduleRetry(eventId = "callback-c", executeAtTimestamp = 12,000)

getEventsToExecuteNow(currentTimestamp = 15,000)

Output: ["callback-c", "callback-a", "callback-b"]

"callback-c" has the earliest timestamp. The other two events have the same timestamp, so they are ordered lexicographically.

Example 3

scheduleRetry(eventId = "order-sync", executeAtTimestamp = 30,000)

scheduleRetry(eventId = "order-sync", executeAtTimestamp = 20,000)

getEventsToExecuteNow(currentTimestamp = 25,000)

Output: ["order-sync"]

The second scheduling call replaces the original timestamp of 30,000.

Example 4

scheduleRetry(eventId = "invoice-update", executeAtTimestamp = 40,000)

getEventsToExecuteNow(currentTimestamp = 35,000)

Output: []

The event is not ready because its scheduled timestamp is greater than the current timestamp.