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

Well, as has already been stated, finding the containing Duration interval as you are already doing or using millis directly is sufficient for this use case, and the math involved is straightforward. However, if you did have a use case which warranted a Period interval involving hours, here's how it could be handled:

1. Translate the Period into an approximate duration of hours and use that to estimate how many intervals away the target is from the origin.
2. Scale the Period by your estimate. Treat aggregations of 24 hours as additional days.
3. Move the origin interval by the scaled period. If the moved interval contains your target, you're done. If not, re-estimate based on the amount you missed by.

An important thing to note when finding the containing interval is that all Period addition must take place from the origin directly and not from intermediate intervals for consistency. For example, if you have a Period of one month with an origin of January 31st, the intervals immediately after the origin interval should begin on February 28th and March 31st. Adding two months to January 31st will correctly yield March 31st, but adding one month to February 28th would incorrectly yield March 28th.

The following is the code for the above approach. Note that there are plenty of anomalous situations for this kind of thing, and I only tested a few of them, so don't consider this code as rigorously tested.

public static final int NUM_HOURS_IN_DAY = 24;
public static final int NUM_HOURS_IN_MONTH = 730;  // approximate

public ZonedDateTime startOfContainingInterval(ZonedDateTime origin, Period period, int hours, ZonedDateTime target) {
    return intervalStart(origin, period, hours, containingIntervalNum(origin, period, hours, target));
}

public int containingIntervalNum(ZonedDateTime origin, Period period, int hours, ZonedDateTime target) {
    int intervalNum = 0;
    ZonedDateTime intervalStart = origin, intervalFinish;
    long approximatePeriodHours = period.toTotalMonths() * NUM_HOURS_IN_MONTH + period.getDays() * NUM_HOURS_IN_DAY + hours;
    do {
        long gap = ChronoUnit.HOURS.between(intervalStart, target);
        long estimatedIntervalsAway = Math.floorDiv(gap, approximatePeriodHours);
        intervalNum += estimatedIntervalsAway;
        intervalStart = intervalStart(origin, period, hours, intervalNum);
        intervalFinish = intervalStart(origin, period, hours, intervalNum + 1);
    } while (!(target.isAfter(intervalStart) && target.isBefore(intervalFinish) || target.equals(intervalStart)));
    return intervalNum;
}

public ZonedDateTime intervalStart(ZonedDateTime origin, Period period, int hours, int intervalNum) {
    Period scaledPeriod = period.multipliedBy(intervalNum).plusDays(hours * intervalNum / NUM_HOURS_IN_DAY);
    long leftoverHours = hours * intervalNum % NUM_HOURS_IN_DAY;
    return origin.plus(scaledPeriod).plusHours(leftoverHours);
}

Answer 2

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 3

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 4

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 5

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