background
Made a set of information platform for a mall project of the company, that is This goods , this message is not a message such as SMS or email notification, but a message in the message queue. The platform can dynamically create consumers and producers, process asynchronous messages, and provide a variety of visual means to manage the whole life cycle of the message processing process. Interested partners can learn about it. End of advertising time:), the following is the text
The platform has a small function, which can configure scheduled tasks and execute some programs regularly. It is easy to use at the beginning ScheduledThreadPoolExecutor When implemented, you can implement periodic tasks. Later, you need to implement such non fixed periodic tasks as one day in a month. This needs to be introduced cron expressions , it's not difficult to find a framework that supports cron expressions. spring boot itself supports it and quartz supports it, but considering
- Timing is not a core function. We do not want to introduce too many dependencies for a non core function
- cron expression has only five variables, which is relatively simple to parse
- Self made wheels are highly controllable
There are two reasons why the cron expression function of spring boot is not used (and no new dependencies are introduced)
- The system and spring boot are decoupled in architecture, that is, the system core does not rely on spring boot. Spring boot only realizes the function of web api, but timing belongs to the function of the system itself, not the function of web api
- The cron of spring boot does not support dynamic creation and needs to be determined at startup
This article does not use any knowledge of compilation principles (in fact, I won't). It is completely hard parsing. You can eat it at ease to ensure that everyone can understand:)
cron expressions
Cron expression is an expression language that can describe periodic tasks. A cron expression contains five parts, each separated by a space. For example, the following expression represents the execution at 20:12 every day
12 20 * * *
The meaning of each part of the cron expression is as follows
- minute
- hour
- day
- month
- week
Each section allows the following operators
- *All numbers in the value range
- /How many numbers do you pass
- -From X to Z
- , hash number
example
Example 1: execute every 1 minute * * * * * Example 2: execute at the 3rd and 15th minute of every hour 3,15 * * * * Example 3: execute at the 3rd and 15th minutes from 8 a.m. to 11 a.m 3,15 8-11 * * * Example 4: every two days from 8 a.m. to 11 a.m. in the 3rd and 15th minutes 3,15 8-11 */2 * * Example 5: every Monday from 8 a.m. to 11 a.m. in the 3rd and 15th minutes 3,15 8-11 * * 1 Example 6: 21 per night:30 restart smb 30 21 * * * Example 7: 4 on the 1st, 10th and 22nd of each month : 45 restart smb 45 4 1,10,22 * * Example 8: 1 every Saturday and Sunday : 10 restart smb 10 1 * * 6,0 Example 9: 18 per day : 00 To 23 : 00 Restart every 30 minutes between smb 0,30 18-23 * * * Every Saturday night: 11 : 00 pm restart smb 0 23 * * 6 Example 11: restart every hour smb 0 */1 * * *
Realization idea
To complete a program similar to quartz, it needs the cooperation of two core components. Basically, all timing class frameworks follow this idea
- For a thread with a fixed cycle (actually Thread.sleep), the cycle depends on the accuracy supported by the timing. If the thread regularly (such as 5s) checks whether there are tasks to be executed, a program needs to tell it whether to execute or not
- Judge whether to execute the task in this execution cycle according to the expression + last execution time. This is what the parser needs to do and our task today
The first component is relatively simple and is beyond the scope of this discussion. This time, we mainly discuss how to implement the second component. We divide the parser into two parts
- data structure
- algorithm
Data structure refers to how to store cron data (not a simple string). Selecting an appropriate data structure can get twice the result with half the effort. Algorithm refers to how to judge whether the cycle hits after parsing and storing it in the specified data structure. We will talk about it separately.
data structure
Through observation, it can be found that each part can be divided into two categories
- Periodic execution class (such as every five minutes)
- Fixed time (e.g. 20:12)
No matter what kind, we can abstract it into a range. For example, the default range of minutes is 1-59. Neither periodicity nor fixed time can escape from this range. For example
- /5 *: range 1-59. Because you don't know the minutes of the last execution, it is possible to take values in the whole range
- 12 20 *: range [12], only 12 can be taken
- 12,13: Scope [12-13]
- 12-15: Scope [12-15]
Because the range can cover all the grammars we support, there is also a small problem. Minutes, hours and months can be determined, but days cannot be determined. Days are determined according to months and are affected by years (leap years). cron also supports weeks. Weeks do not correspond to specific concepts. How to deal with weeks? In further abstraction, we define the range by merging the year, month and day. There are at most 366 options in this range, and the processing of weeks is also very simple. For example, if Tuesday is specified in cron, we can remove the non Tuesday dates in the year, month and day range. In this way, we can unify and synthesize the above. We define the following ranges
- branch
- Time
- Year, month and day (in fact, there is no need to define the year, because there is no upper limit for the year and it can be added all the time)
What data structure should be used to store the month and day merging? Because the minutes and hours are int type and the hours increase, it is best to keep consistent. Considering that the month < = 12 and the day < = 31, two numbers can be merged into one number by bit operation
/**
* Combines the month and day into an int integer
* @param month
* @param day
* @return
*/
public int encodeMonthday(int month, int day) {
return (day & 0x000000FF) | (month << 8 & 0x0000FF00);
}
/**
* Decoding month
* @param monthDay
* @return
*/
public int decodeMonth(int monthDay) {
return (monthDay & 0x0000FF00) >> 8;
}
/**
* Decoding day
* @param monthDay
* @return
*/
public int decodeDay(int monthDay) {
return (monthDay & 0x000000FF);
}algorithm
This part is the most troublesome. I try to make it as clear as possible. We may better understand the problem by abstracting it. We convert the problem into the following description
There are three combinations of ABC, A value [A1-AN], B value [B1-BN], C value [C1-CN]. Given A DEF, find the next minimum value of DEF in ABC
Is it a bit like doing ACM topics in the University, but it's like this in the abstract. My idea is like this (not necessarily the best, ha, I dreamed of entering the ACM team in the University, but I didn't even enter the primary election,:), so if you have a better solution, please leave a message in the comment area
- Judging from big to small
- First judge whether F is in C. if it is, continue to judge E
- Judge whether E is in B or not, if continue to judge D
- Judge whether D is in A or not. If it is, just calculate min ([A1-an] > d)
- If D is not in A, return to E and calculate min ([b1-bn] > E)
- and so on
Of course, there are still some small problems to deal with, such as cross year problems. The detailed algorithm can be seen in the code, and the language expression ability is limited to this
realization
The whole parser is implemented with no more than 200 lines of code, so it is not very difficult to read. The complete code is posted as follows
package com.definesys.mc.core.cron;
import java.util.Calendar;
import java.util.Date;
import java.util.Set;
import static java.util.Calendar.DATE;
import static java.util.Calendar.DAY_OF_YEAR;
/**
* @Description:
* @author: jianfeng.zheng
* @since: 2021/12/30 3:50 afternoon
* @history: 1.2021/12/30 created by jianfeng.zheng
*/
public class CronParser {
private String cronExp;
public CronParser(String exp) {
this.cronExp = exp;
}
public Date nextDate(Date start) {
Calendar lastCal = Calendar.getInstance();
lastCal.setTime(start);
//Last execution time field
int lastYear = lastCal.get(Calendar.YEAR);
int lastMonth = lastCal.get(Calendar.MONTH) + 1;
int lastDay = lastCal.get(Calendar.DAY_OF_MONTH);
int lastMonthDay = this.encodeMonthday(lastMonth, lastDay);
int lastHour = lastCal.get(Calendar.HOUR_OF_DAY);
int lastMinute = lastCal.get(Calendar.MINUTE);
int lastSecond = lastCal.get(Calendar.SECOND);
//Next execution time field
Integer newMonthDay = null;
Integer newHour = null;
Integer newMinute = null;
Integer newYear = lastYear;
//Parse cron expression
String[] exps = cronExp.split("\\s+");
CronRange minute = parseRange(exps[0], 0, 59);
CronRange hour = parseRange(exps[1], 0, 23);
CronRange day = parseRange(exps[2], 1, 31);
CronRange month = parseRange(exps[3], 1, 12);
CronRange week = parseRange(exps[4], 1, 7);
CronRange monthDay = this.calMonthDay(month, day, week);
if (monthDay.isEmpty()) {
return null;
}
boolean isNotFound = false;
if (monthDay.inRange(lastMonthDay)) {
if (hour.inRange(lastHour)) {
if (minute.inRange(lastMinute)) {
newMinute = minute.getNextValue(lastMinute);
}
if (newMinute == null) {
//If the minutes cannot be found, the hours need to be incremented
newHour = hour.getNextValue(lastHour);
isNotFound = newHour == null;
newMinute = minute.getMin();
} else {
newHour = lastHour;
}
}
if (newHour == null) {
if (isNotFound) {
//If the hour cannot be found, the number of days needs to be incremented
if (monthDay.isAll()) {
Calendar c = Calendar.getInstance();
c.setTime(start);
c.add(DATE, 1);
newMonthDay = this.encodeMonthday(c.get(Calendar.MONTH) + 1, c.get(Calendar.DAY_OF_MONTH));
} else {
//If you cross the new year, you can't find it
newMonthDay = monthDay.getNextValue(lastMonthDay);
}
} else {
newMonthDay = lastMonthDay;
}
newHour = hour.getMin();
newMinute = minute.getMin();
} else {
newMonthDay = lastMonthDay;
}
} else {
//If the days are not in the range, you need to increment the days
newMonthDay = monthDay.getNextValue(lastMonthDay);
newHour = hour.getMin();
newMinute = minute.getMin();
}
if (newMonthDay == null) {
//straddle old and new years
newYear = newYear + 1;
if (monthDay.isAll()) {
//January 1st
newMonthDay = 0x0101;
} else {
newMonthDay = monthDay.getMin();
}
newHour = hour.getMin();
newMinute = minute.getMin();
}
Calendar newCal = Calendar.getInstance();
newCal.set(Calendar.MONTH, this.decodeMonth(newMonthDay) - 1);
newCal.set(Calendar.DAY_OF_MONTH, decodeDay(newMonthDay));
newCal.set(Calendar.HOUR_OF_DAY, newHour);
newCal.set(Calendar.MINUTE, newMinute);
newCal.set(Calendar.SECOND, lastSecond);
newCal.set(Calendar.YEAR, newYear);
return newCal.getTime();
}
/**
* Combines the month and day into an int integer
* @param month
* @param day
* @return
*/
public int encodeMonthday(int month, int day) {
return (day & 0x000000FF) | (month << 8 & 0x0000FF00);
}
/**
* Decoding month
* @param monthDay
* @return
*/
public int decodeMonth(int monthDay) {
return (monthDay & 0x0000FF00) >> 8;
}
/**
* Decoding day
* @param monthDay
* @return
*/
public int decodeDay(int monthDay) {
return (monthDay & 0x000000FF);
}
private CronRange calMonthDay(CronRange month, CronRange day, CronRange week) {
CronRange monthDay = new CronRange();
if (month.isAll() && day.isAll() && week.isAll()) {
//If they are all in the full range, they will not be calculated
monthDay.setReturnAll(true);
return monthDay;
}
int[] monthDays = {31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
//If it's a leap year, it's 29 days
monthDays[1] = Calendar.getInstance().getActualMaximum(DAY_OF_YEAR) > 365 ? 29 : 28;
Set<Integer> rangeMonth = month.getRange();
for (Integer m : rangeMonth) {
for (int d = 1; d <= monthDays[m - 1]; ++d) {
if (day.inRange(d)) {
//Logic of judging week
if (!week.isAll()) {
Calendar cal = Calendar.getInstance();
cal.set(Calendar.MONTH, m - 1);
cal.set(Calendar.DAY_OF_MONTH, d);
int w = cal.get(Calendar.DAY_OF_WEEK) - 1;
//Sunday Saturday = = > 1-7
w = w == 0 ? 7 : w;
if (!week.inRange(w)) {
continue;
}
}
monthDay.addRange(this.encodeMonthday(m, d));
}
}
}
return monthDay;
}
/**
* Value range and cycle period of analytical expression
*
* @param exp
* @param start
* @param end
* @return
*/
public CronRange parseRange(String exp, int start, int end) {
String[] exps = exp.trim().split("/");
CronRange range = new CronRange();
if (exps.length > 1) {
range.setCycle(Integer.parseInt(exps[1]));
}
if (exps[0].trim().length() == 0) {
range.range(start, end);
} else if ("*".equals(exps[0])) {
range.range(start, end);
range.setReturnAll(exps.length == 1);
} else if (exps[0].contains("-")) {
String[] ss = exps[0].split("-");
range.range(Integer.parseInt(ss[0]), Integer.parseInt(ss[1]));
} else if (exps[0].contains(",")) {
String[] ss = exps[0].split(",");
for (String s : ss) {
range.addRange(Integer.parseInt(s));
}
} else {
range.addRange(Integer.parseInt(exps[0]));
}
return range;
}
}
class CronRange {
private Set<Integer> range = new TreeSet<>();
private Integer cycle;
private Integer max = null;
private Integer min = null;
private Boolean returnAll = false;
public CronRange range(int start, int end) {
for (int i = start; i <= end; ++i) {
this.addRange(i);
}
return this;
}
public CronRange addRange(int value) {
max = (max == null || value > max) ? value : max;
min = (min == null || value < min) ? value : min;
this.range.add(value);
return this;
}
public Set<Integer> getRange() {
return range;
}
public void setCycle(Integer cycle) {
this.cycle = cycle;
}
public boolean inRange(int value) {
return returnAll ? true : range.contains(value);
}
public boolean isEmpty() {
return !returnAll && range.isEmpty();
}
public Integer getNextValue(int lastValue) {
Integer value = null;
if (this.cycle != null) {
value = this.cycle + lastValue;
while (!inRange(value)) {
value = value + this.cycle;
if (value > max) {
value = null;
break;
}
}
} else {
value = this.getNextMin(lastValue);
}
return value;
}
private Integer getNextMin(int value) {
Integer[] integers = range.toArray(new Integer[range.size()]);
Integer minValue = null;
for (int i = 0; i < integers.length; ++i) {
if (integers[i] > value) {
minValue = integers[i];
break;
}
}
return minValue;
}
public Boolean isAll() {
return returnAll;
}
public void setReturnAll(Boolean returnAll) {
this.returnAll = returnAll;
}
public Integer getMin() {
return min;
}
}test
I wrote several expressions and tested them. They all meet the expected results
public static void main(String[] cmd) throws ParseException {
String cronExp = "* * * * *";
CronParser parser = new CronParser(cronExp);
String lastExecuteDateStr = "2022-1-3 22:23:22";
SimpleDateFormat fmt = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
Date lastExecuteDate = fmt.parse(lastExecuteDateStr);
for (int i = 0; i < 10; ++i) {
lastExecuteDate = parser.nextDate(lastExecuteDate);
if (lastExecuteDate == null) {
return;
}
System.out.println(fmt.format(lastExecuteDate));
}
}output
2022-01-03 22:24:22 2022-01-03 22:25:22 2022-01-03 22:26:22 2022-01-03 22:27:22 2022-01-03 22:28:22
Other examples
# Every five minutes */5 * * * * 2022-01-03 22:28:22 2022-01-03 22:33:22 2022-01-03 22:38:22 2022-01-03 22:43:22 2022-01-03 22:48:22 #Every five minutes at 12:00 */5 12 * * * 2022-01-03 12:00:22 2022-01-03 12:05:22 2022-01-03 12:10:22 2022-01-03 12:15:22 2022-01-03 12:20:22 #At 12:00 on February 3, every five minutes */5 12 3 2 * 2022-02-03 12:00:22 2022-02-03 12:05:22 2022-02-03 12:10:22 2022-02-03 12:15:22 2022-02-03 12:20:22
Conclusion
In actual projects, we may also encounter a slightly complex business development like this. When facing this development, we must not code immediately. If we code rashly without clarifying the data structure and algorithm, there must be a problem. This parser is neither simple nor complex, But the data structure and algorithm also took me a day to deliberate on the notebook. It is suggested that programmers should have a notebook to write their ideas clearly on paper. Writing code is just to realize the things on paper in code (in fact, coding + debugging takes less than an hour), and attach notes that are so ugly that only I and God can understand