Structure of timer
The underlying structure of the timer is generally
1. Red black tree
2. Time wheel
3. Skip table
4. Minimum heap
Function of timer
1. Timeout control
2. Timed task
What are the characteristics of the data structure to implement a timer?
When inserting data, the speed of searching and inserting must be fast (time complexity)
At the same time, we should ensure the order of the structure
Skip table implementation timer
The zset type in redis is implemented with a skip table when the number of inserted elements exceeds 128.
So how does redis implement the timer? Redis implements the timer with an unordered double ended linked list.
But the author said that the time complexity of this disordered double ended linked list is O(N). It can be realized by jumping the table.
The complexity of the addition, deletion, modification and query events of the jump table tends to O(logN).
Now let's use the jump table to realize the function of a timer.
Internal timer:
1) Insert, delete (any node and head node) O (logN)
2) The expiration time only needs to be compared with the first node (the score of the node stores the timestamp)
The external timer needs to provide the following interfaces:
1. Initialize
2. Add timer
3. Delete timer
4. Timer expiration function
We can also use some structures of the jump table in the redis source code.
skiplist.h
#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */
typedef struct zskiplistNode zskiplistNode;
typedef void (*handler_pt) (zskiplistNode *node);
struct zskiplistNode {
// sds ele;
// double score;
unsigned long score; // time stamp
handler_pt handler;
/* struct zskiplistNode *backward; Used when traversing from back to forward*/
struct zskiplistLevel {
struct zskiplistNode *forward;
/* unsigned long span; The number of nodes between the stored level s is not required in the timer*/
} level[];
};
typedef struct zskiplist {
// Add a free function
struct zskiplistNode *header/*, *tail You don't need to know the last node*/;
int length;
int level;
} zskiplist;
zskiplist *zslCreate(void);
void zslFree(zskiplist *zsl);
zskiplistNode *zslInsert(zskiplist *zsl, unsigned long score, handler_pt func);
zskiplistNode* zslMin(zskiplist *zsl);
void zslDeleteHead(zskiplist *zsl);
void zslDelete(zskiplist *zsl, zskiplistNode* zn);
void zslPrint(zskiplist *zsl);
skiplist.c
#include <stdlib.h>
#include <stdio.h>
#include "skiplist.h"
void defaultHandler(zskiplistNode *node) {
}
/* Create a skiplist node with the specified number of levels. */
zskiplistNode *zslCreateNode(int level, unsigned long score, handler_pt func) {
zskiplistNode *zn =
malloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->handler = func;
return zn;
}
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
zsl = malloc(sizeof(*zsl));
zsl->level = 1;
zsl->length = 0;
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,defaultHandler);
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
}
return zsl;
}
/* Free a whole skiplist. */
void zslFree(zskiplist *zsl) {
zskiplistNode *node = zsl->header->level[0].forward, *next;
free(zsl->header);
while(node) {
next = node->level[0].forward;
free(node);
node = next;
}
free(zsl);
}
int zslRandomLevel(void) {
int level = 1;
while ((arc4random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
zskiplistNode *zslInsert(zskiplist *zsl, unsigned long score, handler_pt func) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
int i, level;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
x->level[i].forward->score < score)
{
x = x->level[i].forward;
}
update[i] = x;
}
level = zslRandomLevel();
printf("zskiplist add node level = %d\n", level);
if (level > zsl->level) {
for (i = zsl->level; i < level; i++) {
update[i] = zsl->header;
}
zsl->level = level;
}
x = zslCreateNode(level,score,func);
for (i = 0; i < level; i++) {
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
}
zsl->length++;
return x;
}
zskiplistNode* zslMin(zskiplist *zsl) {
zskiplistNode *x;
x = zsl->header;
return x->level[0].forward;
}
void zslDeleteHead(zskiplist *zsl) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
zskiplistNode *x = zslMin(zsl);
if (!x) return;
int i;
for (i = zsl->level-1; i >= 0; i--) {
if (zsl->header->level[i].forward == x) {
zsl->header->level[i].forward = x->level[i].forward;
}
}
while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level--;
zsl->length--;
}
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
int i;
for (i = 0; i < zsl->level; i++) {
if (update[i]->level[i].forward == x) {
update[i]->level[i].forward = x->level[i].forward;
}
}
while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level--;
zsl->length--;
}
void zslDelete(zskiplist *zsl, zskiplistNode* zn) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
x->level[i].forward->score < zn->score)
{
x = x->level[i].forward;
}
update[i] = x;
}
x = x->level[0].forward;
if (x && zn->score == x->score) {
zslDeleteNode(zsl, x, update);
free(x);
}
}
void zslPrint(zskiplist *zsl) {
zskiplistNode *x;
x = zsl->header;
x = x->level[0].forward;
printf("start print skiplist level = %d\n", zsl->level);
int i;
for (i = 0; i < zsl->length; i++) {
printf("skiplist ele %d: score = %lu\n", i+1, x->score);
x = x->level[0].forward;
}
}
Red black tree implementation timer
Binary tree may degenerate into single linked list due to the insertion of some data. In order to balance, there is AVL. The height difference between the left and right subtrees of the AVL tree is 1, but the AVL balance operation is too severe.
The red black tree maintains a consistent black height to solve the problem that the balance operation is too severe
Find expiration timer,
You need to find the leftmost node, which is less efficient
If the data is large enough, find the leftmost node and find a lot.
There is the implementation of red black tree in nginx.
Follow the in nginx framework, rbtree c, rbtree. H file. To implement the timer
#include <stdio.h>
#include <stdint.h>
#include <unistd.h>
#include <stdlib.h>
#include <stddef.h>
#include <time.h>
#if defined(__APPLE__)
#include <AvailabilityMacros.h>
#include <sys/time.h>
#include <mach/task.h>
#include <mach/mach.h>
#endif
#include "rbtree.h"
ngx_rbtree_t timer;
static ngx_rbtree_node_t sentinel;
typedef struct timer_entry_s timer_entry_t;
typedef void (*timer_handler_pt)(timer_entry_t *ev);
struct timer_entry_s {
ngx_rbtree_node_t timer;
timer_handler_pt handler;
};
static uint32_t
current_time() {
uint32_t t;
#if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
struct timespec ti;
clock_gettime(CLOCK_MONOTONIC, &ti);
t = (uint32_t)ti.tv_sec * 1000;
t += ti.tv_nsec / 1000000;
#else
struct timeval tv;
gettimeofday(&tv, NULL);
t = (uint32_t)tv.tv_sec * 1000;
t += tv.tv_usec / 1000;
#endif
return t;
}
// When map and set are inserted, they are updated
int init_timer() {
// If the time stamps and key s are the same, the insert operation becomes a modify operation.
ngx_rbtree_init(&timer, &sentinel, ngx_rbtree_insert_timer_value);
return 0;
}
void add_timer(timer_entry_t *te, uint32_t msec) {
msec += current_time();
printf("add_timer expire at msec = %u\n", msec);
te->timer.key = msec;
ngx_rbtree_insert(&timer, &te->timer);
}
void del_timer(timer_entry_t *te) {
ngx_rbtree_delete(&timer, &te->timer);
}
void expire_timer() {
timer_entry_t *te;
ngx_rbtree_node_t *sentinel, *root, *node;
sentinel = timer.sentinel;
uint32_t now = current_time();
for (;;) {
root = timer.root;
if (root == sentinel) break;
node = ngx_rbtree_min(root, sentinel);
if (node->key > now) break;
printf("touch timer expire time=%u, now = %u\n", node->key, now);
te = (timer_entry_t *) ((char *) node - offsetof(timer_entry_t, timer));
te->handler(te);
ngx_rbtree_delete(&timer, &te->timer);
free(te);
}
}
void print_hello(timer_entry_t *te) {
printf("hello world time = %u\n", te->timer.key);
}
int main()
{
init_timer();
timer_entry_t *te = malloc(sizeof(timer_entry_t));
memset(te, 0, sizeof(timer_entry_t));
te->handler = print_hello;
add_timer(te, 3000);
for (;;) {
expire_timer();
usleep(10000);
}
return 0;
}
Ask me, how should I lock a red black tree and a table hopping multi-threaded environment?
Global locking
Simple time wheel timer scheme
Suppose the connection timeout is detected. According to the heartbeat packet, if it is not received for 10s, disconnect the connection.
General practice:
Map < FD, connect * > poll every S to check whether all connections have timed out.
Record the time stamp after receiving the heartbeat packet, and then check whether it times out.
Very poor efficiency O (N)
If a connection has just been received or a heartbeat packet has just been received, it is not necessary to detect it
Divide and Conquer:
Only detect connections that are about to expire, not just
Array + linked list hash array size should be set to 10 or 16?
Why is it set to 16
Why not set 8?
Why is redis hash 2 to the nth power?
When the data is fetched, the speed is the fastest when it is set to the nth power of 2.
Development experience value, set to 16
redis hash 16 10000 15 & 1111
Remainder of 16
That is, the number & 1111
#include <unistd.h>
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class CTimerNode {
public:
CTimerNode(int fd) : id(fd), ref(0) {}
void Offline() {
this->ref = 0;
}
bool TryKill() {
if (this->ref == 0) return true;
DecrRef();
if (this->ref == 0) {
cout << id << " is killed down" << endl;
return true;
}
cout << id << " ref is " << ref << endl;
return false;
}
void IncrRef() {
this->ref++;
}
protected:
void DecrRef() {
this->ref--;
}
private:
int ref;
int id;
};
const int TW_SIZE = 16;
const int EXPIRE = 10;
const int TW_MASK = TW_SIZE - 1;
static size_t iRealTick = 0;
typedef list<CTimerNode*> TimeList;
typedef TimeList::iterator TimeListIter;
typedef vector<TimeList> TimeWheel;
void AddTimeout(TimeWheel &tw, CTimerNode *p) {
if (p) {
p->IncrRef();
TimeList &le = tw[(iRealTick+EXPIRE) & TW_MASK];
le.push_back(p);
}
}
// Used to indicate delay time and call AddTimeout.
void AddTimeoutDelay(TimeWheel &tw, CTimerNode *p, size_t delay) {
if (p) {
p->IncrRef();
TimeList &le = tw[(iRealTick+EXPIRE+delay) & TW_MASK];
le.push_back(p);
}
}
void TimerShift(TimeWheel &tw)
{
size_t tick = iRealTick;
iRealTick++;
TimeList &le = tw[tick & TW_MASK];
TimeListIter iter = le.begin();
for (; iter != le.end();iter++) {
CTimerNode *p = *iter;
if (p && p->TryKill()) {
delete p;
}
}
le.clear();
}
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 ()
{
TimeWheel tw(TW_SIZE);
CTimerNode *p = new CTimerNode(10001);
AddTimeout(tw, p);
AddTimeoutDelay(tw, p, 5);
time_t start = current_time();
for (;;) {
time_t now = current_time();
if (now - start > 0) {
for (int i=0; i<now-start; i++)
TimerShift(tw);
start = now;
cout << "check timer shift " << iRealTick << endl;
}
usleep(2500);
}
return 0;
}