netty - TimerWheel

netty - TimerWheel

1.什么时间启动 workerThread?

2.workerThread 工作流程?

3.HashedWheelBucket 如何处理过期任务

4.Queue timeouts 队列作用？

5.Queue cancelledTimeouts 队列作用?

Queue timeouts 队列作用？

@Override
    public Timeout newTimeout(TimerTask task, long delay, TimeUnit unit, String argv) {
        if (task == null) {
            throw new NullPointerException("task");
        }
        if (unit == null) {
            throw new NullPointerException("unit");
        }
        start();

        // Add the timeout to the timeout queue which will be processed on the next tick.
        // During processing all the queued HashedWheelTimeouts will be added to the correct HashedWheelBucket.
        long deadline = System.nanoTime() + unit.toNanos(delay) - startTime;
        HashedWheelTimeout timeout = new HashedWheelTimeout(this, task, deadline, argv);
        timeouts.add(timeout);
        return timeout;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这里做了两件事:

• 启动 worker 线程 , 调用 start() 方法
• 计算 任务过期时间，并加入到 timeouts 队列中

1.首先看 timeouts 是在什么时候加入数据的？

在向时间轮添加任务的时候，会把 task 加入到timeouts 队列中，而不是 直接加入到 HashedWheelBucket 槽中

2.那什么时候处理 timeouts队列中的数据?

private void transferTimeoutsToBuckets() {
    // transfer only max. 100000 timeouts per tick to prevent a thread to stale the workerThread when it just
    // adds new timeouts in a loop.
    for (int i = 0; i < 100000; i++) {
        HashedWheelTimeout timeout = timeouts.poll();
        if (timeout == null) {
            // all processed
            break;
        }
        if (timeout.state() == HashedWheelTimeout.ST_CANCELLED) {
            // Was cancelled in the meantime.
            continue;
        }

        //计算过期时间总槽数
        long calculated = timeout.deadline / tickDuration;
        //计算剩余圈数
        timeout.remainingRounds = (calculated - tick) / wheel.length;

        // tick 当前 计数总数
        final long ticks = Math.max(calculated, tick); // Ensure we don't schedule for past.
        int stopIndex = (int) (ticks & mask);

        HashedWheelBucket bucket = wheel[stopIndex];
        bucket.addTimeout(timeout);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

• 每次从 timeouts队列中转移 100000个到 HashedWheelBucket 槽中
• 如果为空，则break
• 如果 task 任务是 cancel 则跳过
• 计算过期时间总槽数 和 计算剩余圈数
• 计算落在哪个 HashedWheelBucket 中
• 将 任务 放入对应 的 HashedWheelBucket 中

那 transferTimeoutsToBuckets() 方法在什么时候被调用呢？ 在 workerThread 中的 run() 方法

workerThread 工作流程?

private final class Worker implements Runnable {
    private final Set<Timeout> unprocessedTimeouts = new HashSet<Timeout>();

    private long tick;

    @Override
    public void run() {
        // Initialize the startTime.
        startTime = System.nanoTime();
        if (startTime == 0) {
            // We use 0 as an indicator for the uninitialized value here, so make sure it's not 0 when initialized.
            startTime = 1;
        }

        // Notify the other threads waiting for the initialization at start().
        startTimeInitialized.countDown();

        do {
            //计算下个卡槽失效时间
            final long deadline = waitForNextTick();
            if (deadline > 0) {
                //计算下一个卡槽 idx
                int idx = (int) (tick & mask);
                //处理 cancle 状态的 任务
                processCancelledTasks();
                HashedWheelBucket bucket =
                    wheel[idx];
                //将任务转移到 对应的 HashedWheelBucket， 每次取最多 10_0000个
                transferTimeoutsToBuckets();
                //当前失效卡槽设置过期时间
                bucket.expireTimeouts(deadline);
                //下一个卡槽
                tick++;
            }
        } while (WORKER_STATE_UPDATER.get(TimerWheel.this) == WORKER_STATE_STARTED);

        // Fill the unprocessedTimeouts so we can return them from stop() method.
        for (HashedWheelBucket bucket: wheel) {
            bucket.clearTimeouts(unprocessedTimeouts);
        }
        for (;;) {
            HashedWheelTimeout timeout = timeouts.poll();
            if (timeout == null) {
                break;
            }
            if (!timeout.isCancelled()) {
                unprocessedTimeouts.add(timeout);
            }
        }
        processCancelledTasks();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

流程:

• 等待线程启动
• 计算下个卡槽失效时间
• 如果 deadline 大于 0：
  • 计算下一个卡槽 idx
  • 处理 cancle 状态的 任务
  • 将任务转移到 对应的 HashedWheelBucket， 每次取最多 10_0000个
  • 当前失效卡槽设置过期时间
  • 下一个卡槽
• 如果时间轮停止，取消所有未处理的任务

1.waitForNextTick() 方法

private long waitForNextTick() {
    //下一个槽
    long deadline = tickDuration * (tick + 1);

    for (;;) {
        final long currentTime = System.nanoTime() - startTime;
        //sleep 1 毫秒
        long sleepTimeMs = (deadline - currentTime + 999999) / 1000000;

        if (sleepTimeMs <= 0) {
            if (currentTime == Long.MIN_VALUE) {
                return -Long.MAX_VALUE;
            } else {
                return currentTime;
            }
        }

        // Check if we run on windows, as if thats the case we will need
        // to round the sleepTime as workaround for a bug that only affect
        // the JVM if it runs on windows.
        //
        // See https://github.com/netty/netty/issues/356
        if (PlatformDependent.isWindows()) {
            sleepTimeMs = sleepTimeMs / 10 * 10;
        }

        try {
            Thread.sleep(sleepTimeMs);
        } catch (InterruptedException ignored) {
            if (WORKER_STATE_UPDATER.get(TimerWheel.this) == WORKER_STATE_SHUTDOWN) {
                return Long.MIN_VALUE;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

• 计算下一个槽时间
• 如果没有到下个卡槽时间，则进行 sleep
• 如果过期时间到了，则返回睡的时间

2.processCancelledTasks()

private void processCancelledTasks() {
    for (;;) {
        HashedWheelTimeout timeout = cancelledTimeouts.poll();
        if (timeout == null) {
            // all processed
            break;
        }
        try {
            timeout.remove();
        } catch (Throwable t) {
            if (logger.isWarnEnabled()) {
                logger.warn("An exception was thrown while process a cancellation task", t);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这个简单，直接 cancelledTimeouts 队列 中取出，然后删除就行，那 cancelledTimeouts 是什么时间加入数据的？

private static final class HashedWheelTimeout implements Timeout   
	@Override
    public boolean cancel() {
        // only update the state it will be removed from HashedWheelBucket on next tick.
        if (!compareAndSetState(ST_INIT, ST_CANCELLED)) {
            return false;
        }
        // If a task should be canceled we put this to another queue which will be processed on each tick.
        // So this means that we will have a GC latency of max. 1 tick duration which is good enough. This way
        // we can make again use of our MpscLinkedQueue and so minimize the locking / overhead as much as possible.
        timer.cancelledTimeouts.add(this);
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

在调用 HashedWheelTimeout 的 cancle 方法

3.transferTimeoutsToBuckets()

从 timeouts 队列中的 HashedWheelTimeout 任务放入对应的 HashedWheelBucket 槽 中

4.[HashedWheelBucket ]bucket.expireTimeouts()

public void expireTimeouts(long deadline) {
    HashedWheelTimeout timeout = head;

    // process all timeouts
    while (timeout != null) {
        boolean remove = false;
        if (timeout.remainingRounds <= 0) {
            if (timeout.deadline <= deadline) {
                timeout.expire();
            } else {
                // The timeout was placed into a wrong slot. This should never happen.
                throw new IllegalStateException(String.format(
                    "timeout.deadline (%d) > deadline (%d)", timeout.deadline, deadline));
            }
            remove = true;
        } else if (timeout.isCancelled()) {
            remove = true;
        } else {
            timeout.remainingRounds --;
        }
        // store reference to next as we may null out timeout.next in the remove block.
        HashedWheelTimeout next = timeout.next;
        if (remove) {
            remove(timeout);
        }
        timeout = next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• 从头遍历 HashedWheelBucket 双向链接
• 需要删除的过期的任务
  • remainingRounds 剩余圈数小于0
    • 如果 deadline 小于当前要过期的 deadline ,则过期
  • 任务被取消了
  • 其他 情况 下 该任务 的 remainingRounds 减一
• 从 HashedWheelBucket 删除 这些节点

从以上可以看出，主要 做两件事:

• 删除 HashedWheelBucket 中过期的 任务
• 如果当前任务 deadline 到期，执行 任务的 expire 方法

其中 任务 HashedWheelTimeout的 expire 方法很简单 :

public void expire() {
    if (!compareAndSetState(ST_INIT, ST_EXPIRED)) {
        return;
    }

    try {
        task.run(this, argv);
    } catch (Throwable t) {
        if (logger.isWarnEnabled()) {
            logger.warn("An exception was thrown by " + TimerTask.class.getSimpleName() + '.', t);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

直接执行这个任务的 具体内容