How to design a counting time window

Time window, usually for some real-time information display used more, such as to maintain a five-minute transaction details time window, it is necessary to record the current time, to five minutes before all the transaction details, and five minutes before the data, then throw away

A simple implementation is to use a queue where new data is added at the head; At the same time, a thread is continuously asked whether the data at the end of the queue is expired, and if it is, it is discarded

Another scenario needs to make use of the data in this time window for calculation, such as calculating the total inflow and outflow of funds in the five-minute transaction. If the above method is still used, what problems will there be?

• If the time window is large, a large amount of detailed data needs to be stored
• Our main concern is the inflow and outflow of funds; It is not worth saving these detailed data
• Calculate the inflow and outflow consumption performance in real time every time you add or delete expired data

Is there a trick to this particular scenario?

I. Program design

1. Queue-based polling deletion mode

The time window is divided into time slices. Each time slice records the total inflow and outflow of funds, and then the total inflow and outflow is the sum of inflow and outflow of all time slices

New data:

• If not, the value of the queue header is updated
• If across time slices, add a queue header

Delete data:

• Poll the task to determine whether the tail of the queue is expired
• If the end of the queue expires, the end of the queue is deleted. If the data of the head of the queue is not added to the calculation, the end of the queue is also added to the calculation

2. The queue-based deletion mode for adding new data

Compared with the previous polling method, the application scenario of this method is different. Only when new data is added, the accuracy of data can be ensured. There is no need for polling tasks to delete expired data

Simply put, in some scenarios (such as ensuring that data does not come in intermittently, i.e., each time slice has at least one data coming in), I want my time window data to be driven and updated by new data

New data:

• If no time slice is crossed, the queue header value is updated
• Across time slices, a new one is inserted and the old data is deleted

II. Time window implementation based on array

In view of the above the second, a simple implementation is given based on array, this paper mainly gives a basic way of the design and implementation of a time window, of course also needs to have the advanced case, such as the above cash inflow and outflow, I need to calculate 5 min, 10 min, 30 min, 1 h, 3 h, 6 h, 12 h, 24 h time window, How do you do that? Can a single queue satisfy all time Windows? I’ll leave that to the next article

1. Time wheel calculator

The queue is easier to understand, but why do we use an array?

• Fixed length to avoid frequent addition and deletion of objects
• Easy to locate and update data

The first is to implement a time wheel calculator that retrieves expired data that needs to be deleted based on the time passed in

@Data
public class TimeWheelCalculate {
    private static final long START = 0;

    private int period;
    private int length;

    /** * Number of time slices */
    private int cellNum;

    private void check(a) {
        if(length % period ! =0) {
            throw new IllegalArgumentException(
                    "length % period should be zero but not! now length: " + length + " period: "+ period); }}public TimeWheelCalculate(int period, int length) {
        this.period = period;
        this.length = length;

        check();

        this.cellNum = length / period;
    }

    public int calculateIndex(long time) {
        return (int) ((time - START) % length / period);
    }

    /** * gets all expired time slice indexes **@paramLastInsertTime Timestamp of the last update to the time wheel *@paramNowInsertTime Indicates the timestamp of the update time wheel *@return* /
    public List<Integer> getExpireIndexes(long lastInsertTime, long nowInsertTime) {
        if (nowInsertTime - lastInsertTime >= length) {
            // After a round, all the past data is discarded
            return null;
        }

        List<Integer> removeIndexList = new ArrayList<>();
        int lastIndex = calculateIndex(lastInsertTime);
        int nowIndex = calculateIndex(nowInsertTime);
        if (lastIndex == nowIndex) {
            // If the time slice has not been crossed, there is no need to delete the expired data
            return Collections.emptyList();
        } else if (lastIndex < nowIndex) {
            for (inttmp = lastIndex; tmp < nowIndex; tmp++) { removeIndexList.add(tmp); }}else {
            for (int tmp = lastIndex; tmp < cellNum; tmp++) {
                removeIndexList.add(tmp);
            }

            for (int tmp = 0; tmp < nowIndex; tmp++) { removeIndexList.add(tmp); }}returnremoveIndexList; }}Copy the code

The implementation of this calculator is relatively simple, the first is to specify the length of the time window (length), time slice (period), which mainly provides two methods

• calculateIndexDetermines the index of expired data in the array based on the current time
• getExpireIndexesBased on the last insert time and the current insert time, calculates all expired data indexes between the two insert times

2. Time Wheel container

The data under the time window stored in the container, including real-time data and the array of the past N time slices, its main core is the need to judge when adding data

• If it is across time slices, delete expired data, update real-time data, and update the total number
• If not, update real-time data directly

@Data
public class TimeWheelContainer {
    private TimeWheelCalculate calculate;

    /** * Historical time slice counts, each time slice corresponds to one of its elements */
    private int[] counts;

    /** * Real time slice count */
    private int realTimeCount;

    /** * count the entire time round */
    private int timeWheelCount;

    private Long lastInsertTime;


    public TimeWheelContainer(TimeWheelCalculate calculate) {
        this.counts = new int[calculate.getCellNum()];
        this.calculate = calculate;
        this.realTimeCount = 0;
        this.timeWheelCount = 0;
        this.lastInsertTime = null;
    }

    public void add(long now, int amount) {
        if (lastInsertTime == null) {
            realTimeCount = amount;
            lastInsertTime = now;
            return;
        }


        List<Integer> removeIndex = calculate.getExpireIndexes(lastInsertTime, now);
        if (removeIndex == null) {
            // If the interval is longer than one round, the count is cleared
            realTimeCount = amount;
            lastInsertTime = now;
            timeWheelCount = 0;
            clear();
            return;
        }

        if (removeIndex.isEmpty()) {
            // If no time slice is crossed, only the real-time count is updated
            realTimeCount += amount;
            lastInsertTime = now;
            return;
        }

        // If the time slice is crossed, the expired data needs to be deleted from the total and new data needs to be appended
        for (int index : removeIndex) {
            timeWheelCount -= counts[index];
            counts[index] = 0;
        }
        timeWheelCount += realTimeCount;
        counts[calculate.calculateIndex(lastInsertTime)] = realTimeCount;
        lastInsertTime = now;
        realTimeCount = amount;
    }

    private void clear(a) {
        for (int i = 0; i < counts.length; i++) {
            counts[i] = 0; }}}Copy the code

3. The test

The main thing is to verify that there are no obvious problems with the above implementation. Why are there obvious problems?

• Deep bug in the actual use, more easily exposed

public class CountTimeWindow {

    public static void main(String[] args) {
        TimeWheelContainer timeWheelContainer = new TimeWheelContainer(new TimeWheelCalculate(2.20));

        timeWheelContainer.add(0.1);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 0."first");

        timeWheelContainer.add(1.1);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 0."first");

        timeWheelContainer.add(2.1);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 2."second");
        Assert.isTrue(timeWheelContainer.getCounts()[0] = =2."second");

        for (int i = 3; i < 20; i++) {
            timeWheelContainer.add(i, 1);
            System.out.println("add index: " + i + " count: " + timeWheelContainer.getTimeWheelCount());
        }

        // Just one round

        timeWheelContainer.add(20.3);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 20."third");
        timeWheelContainer.add(21.3);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 20."third");


        // Subtract the expired data
        timeWheelContainer.add(22.3);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 26 - 2."fourth");
        Assert.isTrue(timeWheelContainer.getCounts()[0] = =6."fourth");


        timeWheelContainer.add(26.3);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 24 - 2 - 2 + 3."fifth");
        System.out.println(Arrays.toString(timeWheelContainer.getCounts()));


        timeWheelContainer.add(43.3);
        System.out.println(Arrays.toString(timeWheelContainer.getCounts()));
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 6."six"); }}Copy the code

III. The other

1. A gray Blog: https://liuyueyi.github.io/hexblog.

A gray personal blog, recording all the study and work in the blog, welcome everyone to go to stroll

2. Statement

As far as the letter is not as good as, has been the content, purely one’s own words, because of the limited personal ability, it is hard to avoid omissions and mistakes, such as finding bugs or better suggestions, welcome criticism and correction, not grudging gratitude

• Micro Blog address: Small Gray Blog
• QQ: a gray /3302797840

3. Scan attention