Design and implementation of timer

The application of timer

Application scenario 1 ：keep alive The survival mechanism （ The heartbeat detection ）

Thousands of clients connect to the server , However, some clients may never send data after connecting to the server , In order to allocate the best resources to effective connections , Each client needs to send heartbeat packets to the server regularly , If the server fails to detect heartbeat packets for a period of time , Then the connection will be automatically disconnected .

Application scenario II ： Specific operations to be performed at regular intervals

1. Game skill cooling
2. Map monster refresh
3. count down

The design of timer

When designing the data structure of the timer, the following requirements should be met ：

1. Orderly structure , And the addition and deletion operations do not affect the order of the structure ;
2. Can quickly find the smallest node ;

To sum up, the timer can be designed in the following ways ： Red and black trees 、 The smallest pile 、 Single level time wheel 、 Multi level time wheel ,
Next, I will analyze the advantages and disadvantages of these implementation methods from the perspective of algorithm .

The algorithm name	Increase node time complexity	Find node time complexity	Delete node time complexity	The time complexity of deleting the smallest node
Red and black trees	lg(n)	lg(n)	lg(n)	That is, the node at the bottom left corner lg(n)
The smallest pile	lg(n)	lg(n)	n	The top node O(1)
Single level time wheel	O(1)	O(1)	O(1)	O(1)
Multi level time wheel	O(1)	O(1)	O(1)	O(1)

It can be seen that in many algorithms , The time wheel algorithm is the best .

The realization of timer

Red black number and minimum heap

#include <stdio.h>
#include <sys/epoll.h>
#include "mh-timer.h"
void hello_world(timer_entry_t *te) {
    
    printf("hello world time = %u\n", te->time);
}
int main() {
    
    init_timer();

    add_timer(3000, hello_world);// Add time event 

    int epfd = epoll_create(1);
    struct epoll_event events[512];

    for (;;) {
    
        int nearest = find_nearest_expire_timer(); // Get the arrival time of the latest event 
        int n = epoll_wait(epfd, events, 512, nearest);// Set up epoll_wait Block until the next time event arrives 
        for (int i=0; i < n; i++) {
    
            //  Deal with time events 
        }
        expire_timer();// Delete the timeout event 
    }
    return 0;
}

The two are implemented in a similar way , Only the underlying data structure changes .

Both are stored in the form of key value ,key It's due time ,alue Is the callback function executed .

Single level time wheel

principle

The data structure of a single-layer time wheel is actually a linked list , The circle in the middle is the time chain , Outside is the linked list of scheduled tasks , The pointer tick Will rotate around the time wheel , Every time you add a time event , Put the event into (tick+delay) % MAX_TIME_WHEEL_SIZE At the end of the linked list , Every time tick Go to the appropriate time scale , Take out the time event and execute .

defects

1. The timing length and accuracy depend on the scale of the time axis , This is also the limitation of single-layer time axis .

Solution

1. increase round( Rounds ) attribute ： It's like running , Add... To each task round The counter of , When the pointer turns around ,round Counter minus 1, So just take it out round=0 Tasks that need to be triggered .

advantage ： It can reduce the waste of space caused by too large time grid

shortcoming ： Each time, you need to traverse all the task lists in the corresponding grid , Especially when the scale granularity of the time wheel is very small , The task list is extremely long , Time will be greatly increased .

2. Adopt hierarchical time wheel ： Like a clock , There's a clock 、 Minutes and seconds . The hierarchical time wheel can be further extended to the sky wheel 、 Moon rings and even annual rings .

Code implementation

#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>

#if defined(__APPLE__)
#include <AvailabilityMacros.h>
#include <sys/time.h>
#include <mach/task.h>
#include <mach/mach.h>
#else
#include <time.h>
#endif

#define MAX_TIMER ((1<<17)-1)
#define MAX_CONN ((1<<16)-1)

typedef struct conn_node {
    
    uint8_t used; //  quote   This is the number of heartbeat packets sent during this period 
    int id;  // fd
} conn_node_t;

typedef struct timer_node {
    
    struct timer_node *next; //  next 
    struct conn_node *node; //  In itself 
    uint32_t idx;
} timer_node_t;

static timer_node_t timer_nodes[MAX_TIMER] = {
    0};
static conn_node_t conn_nodes[MAX_CONN] = {
    0};
static uint32_t t_iter = 0;
static uint32_t c_iter = 0;

timer_node_t * get_timer_node() {
     //  Be careful ： The number of scheduled tasks not detected exceeds  MAX_TIMER  The situation of 
    t_iter++;
    while (timer_nodes[t_iter & MAX_TIMER].idx > 0) {
    
        t_iter++;
    }
    timer_nodes[t_iter].idx = t_iter;
    return &timer_nodes[t_iter];
}

conn_node_t * get_conn_node() {
     //  Be careful ： The number of connections not detected exceeds  MAX_CONN  The situation of 
    c_iter++;
    while (conn_nodes[c_iter & MAX_CONN].used > 0) {
    
        c_iter++;
    }
    return &conn_nodes[c_iter];
}

#define TW_SIZE 16
#define EXPIRE 10
#define TW_MASK (TW_SIZE - 1)
static uint32_t tick = 0;

typedef struct link_list {
    
    timer_node_t head; //  Easy to traverse 
    timer_node_t *tail; //  Easy to add 
}link_list_t;

void add_conn(link_list_t *tw, conn_node_t *cnode, int delay) {
    
    link_list_t *list = &tw[(tick+EXPIRE+delay) & TW_MASK];
    timer_node_t * tnode = get_timer_node();
    cnode->used++;
    tnode->node = cnode;
    list->tail->next = tnode;
    list->tail = tnode;
    tnode->next = NULL;
}

void link_clear(link_list_t *list) {
    
    list->head.next = NULL;
    list->tail = &(list->head);
}

void check_conn(link_list_t *tw) {
    
    int32_t itick = tick;
    tick++;
    link_list_t *list = &tw[itick & TW_MASK];
    timer_node_t *current = list->head.next;
    while (current) {
    
        timer_node_t * temp = current;
        current = current->next;
        conn_node_t *cn = temp->node;
        cn->used--;
        temp->idx = 0;
        if (cn->used == 0) {
    
            printf("fd:%d kill down\n", cn->id);
            temp->next = NULL;
            continue;
        }
        printf("fd:%d used:%d\n", cn->id, cn->used);
    }
    link_clear(list);
}

static time_t
current_time() {
    
    time_t t;
#if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
    struct timespec ti;
    clock_gettime(CLOCK_MONOTONIC, &ti);
    t = (time_t)ti.tv_sec;
#else
    struct timeval tv;
    gettimeofday(&tv, NULL);
    t = (time_t)tv.tv_sec;
#endif
    return t;
}

int main() {
    
    memset(timer_nodes, 0, MAX_TIMER * sizeof(timer_node_t));
    memset(conn_nodes, 0, MAX_CONN * sizeof(conn_node_t));

    // init link list
    link_list_t tw[TW_SIZE];
    memset(tw, 0, TW_SIZE * sizeof(link_list_t));
    for (int i = 0; i < TW_SIZE; i++) {
    
        link_clear(&tw[i]);
    }

    //  The test starts at 0 second , therefore  delay  Cannot add more than 10 Number of numbers .
    {
    
        conn_node_t *node = get_conn_node();
        node->id = 10001;
        add_conn(tw, node, 0);
        add_conn(tw, node, 5);
    }

    {
    
        conn_node_t *node = get_conn_node();
        node->id = 10002;
        add_conn(tw, node, 0);
    }

    {
    
        conn_node_t *node = get_conn_node();
        node->id = 10003;
        add_conn(tw, node, 3);
    }

    time_t start = current_time();
    for (;;) {
    
        time_t now = current_time();
        if (now - start > 0) {
     //
            for (int i=0; i<now-start; i++)
                check_conn(tw);
            start = now;
            printf("check conn tick:%d\n", tick);
        }
        // 1.  Why?  usleep 20ms  And the time precision is  1s 50 individual  20ms
        // check_conn  It takes time , With the operation , The accuracy of time is getting worse 
        //
        usleep(20000); // 1 second  1000000 1s 1000ms 20ms
    }
    return 0;
}

Multi level time wheel

A multi-level time wheel is actually a collection of multiple single-level time wheels , Just like our clock , The second hand goes round , Take a minute , The minute hand goes round , Go one space clockwise , The design idea is the same , Design multiple linked lists , The precision represented by each linked list is different , Put them into different linked lists according to the set time , Let variables tick++, Where to add to facilitate the linked list , Perform corresponding tasks .

Visible from above , Except that the first time wheel is the exact time , A time range is stored from the second level to the fifth level , As long as the tasks falling within this time range exist in this linked list , wait until tick Traversing 2-5 Node of layer , Just take these nodes out , Do another insert operation , In this way, they will all become the nodes of the first layer .

Code implementation

The mutual exclusion between threads adopts spin lock , Because mutually exclusive resources are pure computing classes , System calls are not involved , So mutexes consume more resources than spinlocks .

#ifndef _SPINLOCK_H
#define _SPINLOCK_H

struct spinlock {
    
	int lock;
};

static void spinlock_init(struct spinlock *lock) {
    
	lock->lock = 0;
}

static void spinlock_lock(struct spinlock *lock) {
    
	while (__sync_lock_test_and_set(&lock->lock, 1)) {
    }
}

static int spinlock_trylock(struct spinlock *lock) {
    
	return __sync_lock_test_and_set(&lock->lock, 1) == 0;
}

static void spinlock_unlock(struct spinlock *lock) {
    
	__sync_lock_release(&lock->lock);
}

static void spinlock_destroy(struct spinlock *lock) {
    
	(void) lock;
}

#endif

#ifndef TIMEWHEEL_H
#define TIMEWHEEL_H
#include<pthread.h>
#include<iostream>
#include<list>
#include<string.h>
#include"spinlock.h"
using namespace  std;

#define TIME_NEAR_SHIFT 8
#define TIME_NEAR (1 << TIME_NEAR_SHIFT)
#define TIME_LEVEL_SHIFT 6
#define TIME_LEVEL (1 << TIME_LEVEL_SHIFT)
#define TIME_NEAR_MASK (TIME_NEAR-1)
#define TIME_LEVEL_MASK (TIME_LEVEL-1)
typedef void (*handler_pt) (struct timeNode *node);


struct timeNode;
// This structure is the node of each layer 
struct link_list {
    
    list<timeNode *> head;
};
// Time wheel class , Use the singleton mode 
class timeWheel
{
    
public:
    // Add scheduled tasks 
    timeNode* add_timer(int time, handler_pt func, int threadid);
    static timeWheel* GetInstance();
    // Detect expired tasks 
    void timer_update();
    void del_timer(timeNode *node);
    void clear_timer();
private:
    timeWheel();
    // Get the current time 
    uint64_t gettime();
    void expire_timer();
    void add_node(timeNode *node);
    void move_list(int level, int idx);
    void link(link_list *list, timeNode *node);
    void timer_shift();
    void dispatch_list(list<timeNode *> *current);
    void timer_execute();
    list<timeNode *> link_clear(link_list *list);
private:
	
    static timeWheel *m_Instance;
    //0 Layer time wheel ,255 grid 
    link_list m_near[TIME_NEAR];
    //1-4 Layer time wheel  64 grid 
    link_list m_t[4][TIME_LEVEL];
    struct spinlock m_lock;
    uint32_t m_time;
    uint64_t m_current;
    uint64_t m_current_point;
};

struct timeNode
{
    
    uint32_t m_expire;  // Timeout time 
    handler_pt m_callback; // Callback function 
    uint8_t m_cancel; // Whether to cancel 
    int id;
};

#endif // TIMEWHEEL_H

#include "timewheel.h"
timeWheel* timeWheel::m_Instance = NULL;
timeWheel::timeWheel()
{
    
    for(int i=0;i<TIME_NEAR;i++)
    {
    
        m_near->head.clear();
    }
    for(int i=0;i<4;i++)
    {
    
        for(int j=0;j<TIME_LEVEL;j++)
        {
    
            m_t[i][j].head.clear();
        }
    }
    spinlock_init(&m_lock);
    m_time = 0;
    m_current = 0;
    m_current_point = gettime();
}
timeWheel* timeWheel::GetInstance()
{
    
     if (m_Instance == NULL) // Determine whether the first call 
         m_Instance = new timeWheel();
     return m_Instance;
}

timeNode* timeWheel::add_timer(int time, handler_pt func, int threadid)
{
    
    timeNode *node = (timeNode *)malloc(sizeof(*node));
    spinlock_lock(&m_lock);
    node->m_expire = time+m_time;
    node->m_callback = func;
    node->id = threadid;
    if (time <= 0) {
    
        node->m_callback(node);
        spinlock_unlock(&m_lock);
        free(node);
        return NULL;
    }
    add_node(node);
    spinlock_unlock(&m_lock);
    return node;
}

void timeWheel::timer_update()
{
    
    spinlock_lock(&m_lock);
    timer_execute();// Here twice timer_execute（） Because 
    timer_shift(); //  May appear tick In the second floor 2 Complete the execution of timer_shift() after 
    timer_execute();// Time tasks are mapped to the first layer 2 It's about , If there is no second time, a time task will be lost 
    spinlock_unlock(&m_lock);
}
void timeWheel::del_timer(timeNode *node)
{
    
    node->m_cancel=1;
}
uint64_t timeWheel::gettime()
{
    
    uint64_t t;
#if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
    struct timespec ti;
    clock_gettime(CLOCK_MONOTONIC, &ti);
    t = (uint64_t)ti.tv_sec * 100;
    t += ti.tv_nsec / 10000000;
#else
    struct timeval tv;
    gettimeofday(&tv, NULL);
    t = (uint64_t)tv.tv_sec * 100;
    t += tv.tv_usec / 10000;
#endif
    return t;
}
void timeWheel::expire_timer()
{
    
    uint64_t cp = gettime();
    if (cp != m_current_point) {
    
        int diff = (uint32_t)(cp - m_current_point);
        m_current_point = cp;
        int i;
        for (i=0; i<diff; i++) {
    
            timer_update();
        }
    }
}
void timeWheel::clear_timer()
{
    
    for(int i=0;i<TIME_NEAR;i++)
    {
    
        m_near->head.clear();
    }
    for(int i=0;i<4;i++)
    {
    
        for(int j=0;j<TIME_LEVEL;j++)
        {
    
            m_t[i][j].head.clear();
        }
    }
}
void timeWheel::link(link_list *list, timeNode *node)
{
    
    list->head.push_back(node);
}
void timeWheel::add_node(timeNode *node)
{
    
    uint32_t time=node->m_expire;
    uint32_t current_time=m_time;
    uint32_t msec = time - current_time;
    if (msec < TIME_NEAR) {
     //[0, 0x100)  discharge 0 layer 
        link(&m_near[time&TIME_NEAR_MASK],node);
    } else if (msec < (1 << (TIME_NEAR_SHIFT+TIME_LEVEL_SHIFT))) {
    //[0x100, 0x4000)  discharge 1 layer 
        link(&m_t[0][((time>>TIME_NEAR_SHIFT) & TIME_LEVEL_MASK)],node);
    } else if (msec < (1 << (TIME_NEAR_SHIFT+2*TIME_LEVEL_SHIFT))) {
    //[0x4000, 0x100000)  discharge 2 layer 
        link(&m_t[1][((time>>(TIME_NEAR_SHIFT + TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK)],node);
    } else if (msec < (1 << (TIME_NEAR_SHIFT+3*TIME_LEVEL_SHIFT))) {
    //[0x100000, 0x4000000)  discharge 3 layer 
        link(&m_t[2][((time>>(TIME_NEAR_SHIFT + 2*TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK)],node);
    } else {
    //[0x4000000, 0xffffffff]  discharge 4 layer 
        link(&m_t[3][((time>>(TIME_NEAR_SHIFT + 3*TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK)],node);
    }
}
void timeWheel::move_list(int level, int idx)
{
    
    list<timeNode *> *current = &m_t[level][idx].head;
    while (!current->empty()) {
    
        timeNode *temp=current->front();
        current->pop_front();
        add_node(temp);
    }
    current->clear();
}
void timeWheel::timer_shift()
{
    
    int mask = TIME_NEAR;
    uint32_t ct = ++m_time;
    if (ct == 0) {
      // Because there will be tick = 2^32-1 , delay = 3 This overflow int32 Data types 
        move_list(3, 0); // Time round m_t[3][0] What is stored here is beyond 2^32*20ms -->(2^32+255*64*64*64)*20ms Delay situation 
    } else {
    
        // ct / 256
        uint32_t time = ct >> TIME_NEAR_SHIFT; // /256
        int i=0;
        // ct % 256 == 0
        while ((ct & (mask-1))==0) {
    //%256
            int idx=time & TIME_LEVEL_MASK;//%64
            if (idx!=0) {
    
                move_list(i, idx);
                break;
            }
            mask <<= TIME_LEVEL_SHIFT; // *64
            time >>= TIME_LEVEL_SHIFT; // /64
            ++i;
        }
    }
}


void timeWheel::dispatch_list(list<timeNode *> *current)
{
    
    while (!current->empty())
    {
    
        timeNode * temp = current->front();
        current->pop_front();
        if (temp->m_cancel == 0)
            temp->m_callback(temp);
        free(temp);
    }
}
// Perform all tasks in the linked list 
void timeWheel::timer_execute()
{
    
    int idx = m_time & TIME_NEAR_MASK; //%256
    while (!m_near[idx].head.empty())
    {
    
        list<timeNode *> *current = &m_near[idx].head;
        spinlock_unlock(&m_lock);
        dispatch_list(current);
        current->clear();
        spinlock_lock(&m_lock);
    }
}
list<timeNode *> timeWheel::link_clear(link_list *list)
{
    
    std::list<timeNode *> head=list->head;
    list->head.clear();
    return head;
}

Test code ：

#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <time.h>
#include <stdlib.h>
#include "timewheel.h"
struct context {
    
    int quit;
    int thread;
};

struct thread_param {
    
    struct context *ctx;
    timeWheel *tw;
    int id;
};

static struct context ctx = {
    0};

void do_timer(timeNode *node) {
    
    printf("timer expired:%d - thread-id:%d\n", node->m_expire, node->id);
}

void* thread_worker(void *p) {
    
    struct thread_param *tp = (struct thread_param *)p;
    int id = tp->id;
    struct context *ctx = tp->ctx;
    while (!ctx->quit) {
    
        int expire = rand() % 200;
        tp->tw->add_timer(expire, do_timer, id);
        usleep(expire*(10-1)*1000);
    }
    printf("thread_worker:%d exit!\n", id);
    return NULL;
}

void do_quit(timeNode * node) {
    
    ctx.quit = 1;
}

int main() {
    
    timeWheel *tw=timeWheel::GetInstance();
    srand(time(NULL));
    ctx.thread = 8;
    pthread_t pid[ctx.thread];

    tw->add_timer(600, do_quit, 100);
    struct thread_param task_thread_p[ctx.thread];
    int i;
    for (i = 0; i < ctx.thread; i++) {
    
        task_thread_p[i].id = i;
        task_thread_p[i].ctx = &ctx;
        task_thread_p[i].tw = tw;
        if (pthread_create(&pid[i], NULL, thread_worker, &task_thread_p[i])) {
    
            fprintf(stderr, "create thread failed\n");
            exit(1);
        }
    }

    while (!ctx.quit) {
    
        tw->expire_timer();
        usleep(2500);
    }
    tw->clear_timer();
    for (i = 0; i < ctx.thread; i++) {
    
        pthread_join(pid[i], NULL);
    }
    printf("all thread is closed\n");
    return 0;
}

// gcc tw-timer.c timewheel.c -o tw -I./ -lpthread

Run the renderings

There are deficiencies 、 If you have any questions, please leave a message