How do you divide a time period into equal intervals and find the current one?

Question

I need to schedule a periodic job for lots of users. This job will run at a fixed rate, the interval. I want to distribute the execution of the job for each user uniformly over that interval. For example, if the interval is 4 days, I'd use a consistent hashing function with an identifier for each user to schedule the job at the same time, eg. every 4 days, on the 3rd day.

The interval is relative to an origin instant that is the same for all users. Given such an origin instant, like Instant#EPOCH or some other constant value, how do I find the start date of the current interval?

I can do

Instant now = Instant.now();
Instant origin = Instant.EPOCH;
Duration interval = Duration.ofDays(4);

Duration duration = Duration.between(origin, now);
long sinceOrigin = duration.toMillis();
long millisPerInterval = interval.toMillis();

long intervalsSince = sinceOrigin / millisPerInterval;
Instant startNext = origin.plus(interval.multipliedBy(intervalsSince));

int cursor = distributionStrategy.distribute(hashCode, millisPerInterval);

I can then use the cursor to schedule the job at an Instant relative to the start of the current interval.

There's a lot of math here and I'm not sure the transformation to milliseconds everywhere will uphold actual dates. Is there a more precise way of dividing the time between two instants and finding the one (the subdivision) we are in currently?

Answer 1

If you only want to reduce the math here, you can use remainder instead of a division and multiplication.

long millisSinceIntervalStart = sinceOrigin % millisPerInterval;
Instant startNext = now.minusMillis(millisSinceIntervalStart);

Here you don't have to calculate the number of intervals passed since origin. Just get the time passed since intervalStart and subtract it from current time.

Also, your startNext seems to indicate the start of current interval, not the next interval. Correct?

Answer 2

Assuming you're actually interested in instants and durations (i.e. nothing to do with periods, dates, time zones etc) then your code should be fine. I'd actually go into milliseconds earlier in this case... the maths is all simple here.

Interval getInterval(Instant epoch, Duration duration, Instant now) {
    long epochMillis = epoch.getMillis();
    long durationMillis = duration.getMillis();

    long millisSinceEpoch = now.getMillis() - epochMillis;        
    long periodNumber = millisSinceEpoch / durationMillis;
    long start = epochMillis + periodNumber * durationMillis;
    return new Interval(start, start + durationMillis);
}

This assumes you don't need to worry about now being before epoch - at which point you'd have to do a bit of work as you want the floor of the division operation, rather than truncation towards 0.

(If you only want the start, you could just return new Instant(start).)

Answer 3

I think you're over-complicating things. You don't need to know nearly as much as your code suggests.

You only need to answer "when should this object next run?", such that the answer is statistically evenly distributed over the interval and consistent (not dependant on "now", except that the next run is always after "now").

This method does that:

public static long nextRun(long origin, long interval, Object obj) {
    long nextRunTime = origin + (System.currentTimeMillis() - origin)
       / interval * interval + Math.abs(obj.hashCode() % interval);
    return nextRunTime > System.currentTimeMillis() ? nextRunTime : nextRunTime + interval;
}

This method returns the next time the object should run using its hashCode() to determine where within the duration it should be scheduled, and then returns the next actual time that will happen.

Small implementation note: Math.abs(obj.hashCode() % interval) is used instead of Math.abs(obj.hashCode()) % interval to guard against the hashCode() returning Integer.MIN_VALUE and knowing that Math.abs(Integer.MIN_VALUE) == Integer.MIN_VALUE

---

If you require that java.time classes be used in your API, here's the same code but with java.time parameters and return type:

public static Instant nextRun(Instant origin, Duration interval, Object target) {
    long start = origin.toEpochMilli();
    long width = interval.toMillis();
    long nextRunTime = start + (System.currentTimeMillis() - start)
       / width * width + Math.abs(target.hashCode() % width);
    nextRunTime = nextRunTime > System.currentTimeMillis() ? nextRunTime : nextRunTime + width;
    return Instant.ofEpochMilli(nextRunTime);
}

---

To help understand the math, here's a longer version with the component calculations broken down and assigned to meaningful variable names:

public static Instant nextRun(Instant origin, Duration duration, Object target) {
    long now = System.currentTimeMillis();
    long start = origin.toEpochMilli();
    long intervalWidth = duration.toMillis();
    long ageSinceOrigin = now - start;
    long totalCompleteDurations = ageSinceOrigin / intervalWidth * intervalWidth;
    long mostRecentIntervalStart = start + totalCompleteDurations;
    long offsetInDuration = Math.abs(target.hashCode() % intervalWidth);
    long nextRun = mostRecentIntervalStart + offsetInDuration;
    // schedule for next duration if this duration's time has already passed
    if (nextRun < now) { 
        nextRun += intervalWidth;
    }
    return Instant.ofEpochMilli(nextRun);
}

Answer 4

I would try to define each time period as an object with a start and end date. Then use an RB Tree to store the Period objects. Then you can navigate the tree for a specific date:

if the date is within the first period, you've found it. if the date is before the start date of the period, navigate to the left node and check that period if the date is after the end date of the period, navigate to the right node and check that period