libco Timer core data structure: array + linked list, a bit like hash table, changing time through space. libco timer is also called time wheel. Let's see how this "wheel" turns.
Article source: [libco] libco timer (time wheel)
1. General
libco timer core data structure: array + bidirectional linked list (left figure).
The array is in milliseconds. The default size is 60 * 1000. It mainly stores event data that expires within one minute. Events with the same expiration time will be saved in the two-way linked list. When the time expires, the linked list of expiration events will be taken out together.
Of course, expiration events that exceed one minute also support saving. Through the module taking route, it may be coupled with the data that expires within one minute. After taking them out together, check them again, and write back those that do not expire.
In general application scenarios, the timeout event is within 1 minute. Although the processing scheme for events beyond this time is a little stupid, the cost of code maintenance is relatively small.
libco timer is also called time wheel (right figure): because of the array data structure, the subscript is in milliseconds, and the current time subscript is stTimeout_t.llStartIdx, along this subscript, reads and writes data clockwise over time.
Image source: processon
2. Timer source code analysis
- Data structure.
struct stCoEpoll_t {
...
struct stTimeout_t *pTimeout; /* Timer. */
...
};
/* Timer. */
struct stTimeout_t {
stTimeoutItemLink_t *pItems; /* Array. */
int iItemSize; /* Array size. */
unsigned long long ullStart; /* The time when the expiration event was last obtained. */
long long llStartIdx; /* Last get the array subscript of the expiration event. */
};
/* Two way linked list of expiration events. */
struct stTimeoutItemLink_t {
stTimeoutItem_t *head;
stTimeoutItem_t *tail;
};
- Initialize timer data structure, array size 60000. In general application scenarios, scheduled tasks are within 1 minute (60000 milliseconds), so what about more than one minute? See the source code implementation of AddTimeout below.
stCoEpoll_t *AllocEpoll() {
...
ctx->pTimeout = AllocTimeout(60 * 1000);
...
}
stTimeout_t *AllocTimeout(int iSize) {
stTimeout_t *lp = (stTimeout_t *)calloc(1, sizeof(stTimeout_t));
lp->iItemSize = iSize;
lp->pItems = (stTimeoutItemLink_t *)calloc(1, sizeof(stTimeoutItemLink_t) * lp->iItemSize);
lp->ullStart = GetTickMS();
lp->llStartIdx = 0;
return lp;
}
- Add an expiration event.
int AddTimeout(stTimeout_t *apTimeout, stTimeoutItem_t *apItem, unsigned long long allNow) {
...
unsigned long long diff = apItem->ullExpireTime - apTimeout->ullStart;
if (diff >= (unsigned long long)apTimeout->iItemSize) {
/* Events exceeding one minute should be arranged at the end of the wheel and checked last,
* Because the wheel is "round", the tail is the previous subscript of the current array subscript (llStartIdx).
* (It's a little windy here...) */
diff = apTimeout->iItemSize - 1;
...
}
/* By taking the module, the timer events are stored in the bidirectional linked list corresponding to the array. */
AddTail(apTimeout->pItems + (apTimeout->llStartIdx + diff) % apTimeout->iItemSize, apItem);
return 0;
}
- Gets the expiration event.
/* Gets the expiration event. */
inline void TakeAllTimeout(stTimeout_t *apTimeout, unsigned long long allNow, stTimeoutItemLink_t *apResult) {
...
/* Process time events that expire between the current time and the last processing time. */
int cnt = allNow - apTimeout->ullStart + 1;
if (cnt > apTimeout->iItemSize) {
cnt = apTimeout->iItemSize;
}
...
for (int i = 0; i < cnt; i++) {
int idx = (apTimeout->llStartIdx + i) % apTimeout->iItemSize;
Join<stTimeoutItem_t, stTimeoutItemLink_t>(apResult, apTimeout->pItems + idx);
}
/* Refresh the current data. */
apTimeout->ullStart = allNow;
apTimeout->llStartIdx += cnt - 1;
}
/* Event loop to handle events. */
void co_eventloop(stCoEpoll_t *ctx, pfn_co_eventloop_t pfn, void *arg) {
...
for (;;) {
int ret = co_epoll_wait(ctx->iEpollFd, result, stCoEpoll_t::_EPOLL_SIZE, 1);
...
/* Retrieve the current time expiration event. */
unsigned long long now = GetTickMS();
TakeAllTimeout(ctx->pTimeout, now, timeout);
...
/* Identify that this time is an expiration event because fd event and time event are coupled (! ^ ^). */
stTimeoutItem_t *lp = timeout->head;
while (lp) {
lp->bTimeout = true;
lp = lp->pNext;
}
Join<stTimeoutItem_t, stTimeoutItemLink_t>(active, timeout);
lp = active->head;
while (lp) {
/* Traversal handles active events. (fd event, expiration event.) */
PopHead<stTimeoutItem_t, stTimeoutItemLink_t>(active);
/* Processing time: those expired will be processed first, and those not expired will be added back. */
if (lp->bTimeout && now < lp->ullExpireTime) {
/* Because the time wheel array has only 60000 subscripts, it generally stores expiration events within 1 minute,
* However, events that expire more than 1 minute can also be stored, which may be modeled,
* The expiration events within 1 minute are stored in the same two-way linked list and taken out,
* So these unexpired events should be saved back. */
int ret = AddTimeout(ctx->pTimeout, lp, now);
if (!ret) {
lp->bTimeout = false;
lp = active->head;
continue;
}
}
...
lp = active->head;
}
}
}
3. Disadvantages
- The default size of the time wheel array is 60 * 1000. In milliseconds, the maximum time interval is one minute. However, if the expiration event exceeds one minute, the processing efficiency will be reduced. For example, the expiration time of session often exceeds one minute.
- libco's timer is mainly designed for its internal process switching. After adding a timing event, it is difficult to delete the specified time event by searching. Only when the event is triggered, the event will be deleted from the two-way linked list.
- Timers are not friendly to external use. It seems that they can only create a coroutine, which is implemented through poll inside the coroutine processing function. Moreover, the cost of implementing a timer through a collaborative process is too high. A collaborative process structure has a few K of memory space 😔， So I had to build a lightweight timer wheel to deal with the problem of session Expiration: Timer based on stl map.
- Based on the above problems, it is also easy to analyze why some open sources maintain timers through a small heap, such as libev.
4. Summary
libco's timer design is very excellent and very efficient within a certain range. Although there are some small shortcomings, they do not hide their shortcomings.