27

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?

11
  • I'm a little confused by the question. The distribution of jobs over the interval is not actually relevant to the question right? You are solely asking how to find the exact starting instant of the next interval correct?
    – Zwander
    Aug 7, 2015 at 3:49
  • @Zwander That's correct. Once I have the starting point, I can apply the distribution. I just wanted to indicate my end goal.
    – Savior
    Aug 7, 2015 at 4:52
  • In your example, is the interval 4 logical days, or 345,600 seconds? In other words, is it a Period or a Duration? Aug 7, 2015 at 5:13
  • @namshub Ideally it would be both, but let's say it's a duration.
    – Savior
    Aug 7, 2015 at 5:28
  • 2
    @Pillar Period and Duration represent different concepts. If your locale observes daylight savings time, four days can be as few as 342,000 seconds or as much as 349,200 seconds. Aug 7, 2015 at 6:17

5 Answers 5

13
+200

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?

1
  • Yes, startNext should be startCurrent. This saves an equation or two, that's good.
    – Savior
    Aug 11, 2015 at 2:45
5

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).)

2
  • Is there an easy way to reconcile periods and durations? For example, if I want to do a day and three hours, I'd like to consider the day as a day rather than 86400 seconds and append the three hours at the end.
    – Savior
    Aug 7, 2015 at 14:44
  • @Pillar: Well you can create a period of "1 day and 3 hours" easily enough - but all the code for dealing with it in your use case becomes much more complicated at that point. You'd also need to consider that you'd sometimes have 28 hours and sometimes have 26 hours over which to distribute the work, for example... as well as specifying the time zone, which is currently irrelevant. I would strongly urge you to stick to regular durations if you possibly can.
    – Jon Skeet
    Aug 7, 2015 at 14:57
5

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);
}
3
  • Looking at just your java.time code (which can be reduced to long values), is what you propose any different than what I already have? (Other than removing intermediate variables.)
    – Savior
    Aug 13, 2015 at 3:16
  • @Pillar my code doesn't know about startNext or distributionStrategy, only origin and hashCode. Also, the first version in my answer is about the smallest amount of code I can think of to get the job done (and I personally favour "less code" solutions)
    – Bohemian
    Aug 13, 2015 at 4:24
  • That's what he meant with removing intermediate variables. In your last snippet, mostRecentIntervalStart is equivalent to startNext (which should be startCurrent) and hashCode is equivalent to distributionStrategy. Aug 14, 2015 at 0:23
2

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

2
  • I would have to keep (or recreate) multiple trees (for each job) with potentially thousands of nodes, depending on the interval size and origin date. Also, where does the tree end? Does it end at now? Is this really better than the math?
    – Savior
    Aug 7, 2015 at 15:34
  • It is possible to buikd out a stream of intervals.. only generating enough to find the current iteration. Maybe only holding onto the last iteration where the last job instance was fired? Perhaps also putting users into a group, calculating the trigger time for that group and applying gor the users within that group?
    – EdH
    Aug 8, 2015 at 3:19
2

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);
}

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.