redis4.0_intset源码剖析

1.intset概述

intset(整数集合)可以用于保存类型为int16_t, int32_t, int64_t的整数值,并且保证intset中不会出现重复元素。

2.intst结构体

  • 表示intset的结构体定义如下:

    1
    2
    3
    4
    5
    6
    7
    8
    typedef struct intset {
    //intset的编码方式:int*_t
    uint32_t encoding;
    //intset中元素的数量
    uint32_t length;
    //用于保存元素的数组(0长度数组的妙用)
    int8_t contents[];
    } intset;
  • intset对应的图示如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    |----------|
    | encoding |
    |----------|
    | length |
    |----------|
    |int*_t v0 |
    |----------|
    |int*_t v1 |
    |----------|
    |int*_t |
    |vlength-1 |
    |----------|

redis4.0_ziplist源码剖析

1.ziplist

1.1.ziplist概述

The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers(integer内存表示) instead of a series of characters(ASCII码). It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.

1.2.ziplist整体内存布局

1
2
3
4
5
6
7
|-----------|----------|---------|---------|---------|----|----------|---------|
| <zlbytes> | <zltail> | <zllen> | <entry0>| <entry1>| ...| <entryn> | <zlend> |
|-----------|----------|---------|---------|---------|----|----------|---------|
|低地址 <---------------------------- 高地址 |
NOTE: all fields are stored in little endian(即:低位在地地址,高位在高地址), if not specified otherwise.
  • The general layout of the ziplist is as follows:
    • 用于记录整个ziplist占用的内存字节数;
    • 用于记录最后一个节点(the last entry)的首地址距离ziplist首地址的偏移量;
    • 用于记录ziplist中节点(entry)数量;
    • 用于表示ziplist的结尾,为定制 0xFF;
1.2.ziplist中entry内存布局
1
2
3
4
5
6
7
|--------|----------|---------|
| prelen | encoding | content |
|--------|----------|---------|
|低地址 <---------- 高地址 |
NOTE:a complete entry is stored like above(content长度可能为0,即一个entry可能只有prelen和encoding字段,没有content字段).
1.2.1 entry每个字段的含义:
  • prevlen字段用于记录前一个ziplist节点(entry)的长度,该字段以字节为单位。
    • 如果前一个节点的长度小于255个字节,则prelen属性的长度为1bytes,该字节用于保存前一个节点的长度;
    • 如果前一个节点的长度大于或等于255个字节,则prelen字段的长度为5bytes,其中第一个bytes为定制0xFF,之后的四个bytes用于保存前一个节点的长度;
1.2.2 encoding字段的含义:
  • encoding字段用于表示content字段所保存的数据的类型(string or int)以及content的长度。
  • encoding表示string类型及长度:
    • 当encoding表示string类型时,encoding长度可能为1bytes,2bytes,5bytes,其中最低地址的头两个bits为非11(即(?? & 11) < 11)
    • 当encoding编码为 00bb bbbb(二进制) 时,encoding字段的长度为1bytes,content的长度小于等于0x3F的字节数组;
    • 当encoding编码为 01bb bbbb bbbb bbbb(二进制) 时,encoding字段的长度为2bytes(其中encoding中bb bbbb bbbb bbbb表示string的长度,即content的长度,采用big endian表示),content的长度为小于等于0x3FFF的字节数组;
    • 当encoding编码为10 __ aaaa aaaa bbbb bbbb cccc cccc dddd dddd (二进制)时,encoding字段的长度为5bytes(其中encoding中aaaaaaaa bbbbbbbb cccccccc dddddddd表示string的长度,采用big endian表示),content的长度为小于等于0xFFFFFFFF的字节数组;
  • encoding表示int*_t类型及长度:
    • 当encoding表示integer类型时,encoding字段的长度为1bytes,最低地址的头两个bits为11(即encoding为(11?? ????));
    • 当encoding的编码为 1100 0000(二进制)时,content的长度与2bytes,即表示int16_t类型
    • 当encoding的编码为 1101 0000(二进制)时,content的长度与4bytes,即表示int32_t类型
    • 当encoding的编码为 1110 0000(二进制)时,content的长度与8bytes,即表示int64_t类型
    • 当encoding的编码为 1110 0000(二进制)时,content的长度与3bytes,即表示int24_t类型
    • 当encoding的编码为 1111 1110(二进制)时,content的长度与1bytes,即表示int8_t类型
    • 当encoding的编码为 1100 xxxx(二进制)时,content的长度与0bytes,即表示immediate 4 bit integer,其中xxxx 4bits表示0,12;
    • |11111111| - End of ziplist special entry.

redis4.0_t_string源码剖析

1.字符串对象介绍

  • encoding为REDIS_ENCODING_INT

    • 字符串的内容为“123456”,对应的redisObject内存布局如下:
      encoding_int
  • encoding为REDIS_ENCODING_EMBSTR内存布局
    encoding_embstr

  • encoding为REDIS_ENCODING_RAW内存布局
    encoding_raw

redis4.0_object源码剖析

1.redisObject介绍

  • Redis使用对象来表示数据库中的key和value,每次在redis中创建一个新的键值对时,至少需要创建两个对象对象:键对象和值对象。
  • Redis中的每个对象都由一个redisObject结构体表示。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    typedef struct redisObject {
    //对象的类型
    unsigned type:4;
    //对象采用的编码方式
    unsigned encoding:4;
    //对象最后一次被命令程序访问的时间
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
    * LFU data (least significant 8 bits frequency
    * and most significant 16 bits decreas time). */
    //对象引用计数
    int refcount;
    //指向底层数据结构的指针
    void *ptr;
    } robj;
  • redisObject结构体中type表示对象的类型,type的取值如下:

1
2
3
4
5
6
7
8
/* A redis object, that is a type able to hold a string / list / set */
/* The actual Redis Object */
#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4
  • redisObject结构体中encoding表示type类型的对象采用哪种数据结构作为底层实现,encoding的取值如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* Objects encoding. Some kind of objects like Strings and Hashes can be
* internally represented in multiple ways. The 'encoding' field of the object
* is set to one of this fields for this object. */
//sds
#define OBJ_ENCODING_RAW 0 /* Raw representation */
//"1234"存储为数字1234,即ptr=(void*)1234;
#define OBJ_ENCODING_INT 1 /* Encoded as integer */
#define OBJ_ENCODING_HT 2 /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3 /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6 /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */

2.object.c源码分析

  • 创建一个redisObject对象

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //创建一个redisObject对象
    robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    //sds
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    //引用计数
    o->refcount = 1;
    /* Set the LRU to the current lruclock (minutes resolution), or
    * alternatively the LFU counter. */
    //lru字段用于记录对象最后一次被命令程序访问的时间
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
    o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
    o->lru = LRU_CLOCK();
    }
    return o;
    }
  • redisObject对象refcount字段减1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void decrRefCount(robj *o) {
if (o->refcount == 1) {
switch(o->type) {
case OBJ_STRING: freeStringObject(o); break;
case OBJ_LIST: freeListObject(o); break;
case OBJ_SET: freeSetObject(o); break;
case OBJ_ZSET: freeZsetObject(o); break;
case OBJ_HASH: freeHashObject(o); break;
case OBJ_MODULE: freeModuleObject(o); break;
default: serverPanic("Unknown object type"); break;
}
zfree(o);
} else {
if (o->refcount <= 0) serverPanic("decrRefCount against refcount <= 0");
if (o->refcount != OBJ_SHARED_REFCOUNT) o->refcount--;
}
}

4.参考文献

  1. 《Redis设计与实现》
  2. redis_reading

redis4.0_adlist源码剖析

1.adlist介绍

adlist:双向非循环链表,如图:
adlist

2.adlist.h源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* Node, List, and Iterator are the only data structures used currently. */
//链表Node,双向非循环链表
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
//迭代器
typedef struct listIter {
listNode *next;
int direction;
} listIter;
typedef struct list {
//指向list中第一个listnode节点
listNode *head;
//指向list中最后一个listnode节点
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);//用于释放Node中value字段
int (*match)(void *ptr, void *key);
unsigned long len;//链表的长度
} list;

redis4.0_skiplist源码剖析

1.skiplist概述

  • skiplist(跳跃表)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点指针,从而达到快速访问节点的目的。
  • skiplist支持平均O(logN),最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。
  • This skiplist implementation is almost a C translation of the original algorithm described by William Pugh in “Skip Lists: A Probabilistic Alternative to Balanced Trees”, modified in three ways:
    • a) this implementation allows for repeated scores.
    • b) the comparison is not just by key (our ‘score’) but by satellite data.
    • c) there is a back pointer, so it’s a doubly linked list with the back pointers being only at “level 1”. This allows to traverse the list from tail to head, useful for ZREVRANGE. */

2.skiplist结构体

单击图片进行放大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;//跨度:用于记录与forward指向节点的距离
} level[]; //0长度数组的妙用
} zskiplistNode;
typedef struct zskiplist {
//指向skiplist中表头节点和表尾节点
struct zskiplistNode *header, *tail;
//skiplist中节点的数量(不包括表头节点)
unsigned long length;
//skiplist中层数最高的节点的层数
int level;
} zskiplist;

redis4.0_sds源码剖析

1.sds介绍

  1. sds:Simple Dynamic String即简单动态字符串,为redis的默认字符串表示。

2.sds.h源码分析

  1. sds结构体的内存布局

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    /* 0长度数组的妙用
    * ----------------
    * | len |
    * |——————————————|
    * | alloc |
    * |——————————————|
    * | flags |
    * |——————————————|<----buf
    * | buf[0~n] |
    * | . |
    * | . |
    | . |
    * |——————————————|
    */
  2. sds结构体的定义

  3. sds结构体定义在src/sds.h,其中根据buf[]中字符串的长度来选择不同的sds结构体
    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
    typedef char *sds;
    /* Note: sdshdr5 is never used, we just access the flags byte directly.
    * However is here to document the layout of type 5 SDS strings. */
    //sdshdr5与其他sds结构体的区别是:没有alloc字段,即无法获得free=alloc-len
    //sdshdr5中flags字段的低3bits表示sds类型,高5bits位buf的length字段
    struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];//等价于char buf[0];
    };
    struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    //0长度数组 char buf[]等价于char buf[0]
    char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    //sdsnhdr的类型
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
    };

redis4.0_dict源码剖析

1.dict概述

  • dict(字典):又称为符号表(symbol table),关联数组(associative array)或者映射(map),是一种用于保存键值对(key-value pair)的抽象数据结构。字典中每个键都是独一无二的,程序可以在字典中根据键查找与之关联的值,或者根据键来删除整个键值对。

2.dict结构体

  • hash table结构体
    ht

    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
    /* Unused arguments generate annoying warnings... */
    #define DICT_NOTUSED(V) ((void) V)
    //hash table节点
    typedef struct dictEntry {
    //键
    void *key;
    //值
    union {
    void *val;
    uint64_t u64;
    int64_t s64;
    double d;
    } v;
    //指向下一个hash table节点
    struct dictEntry *next;
    } dictEntry;
    /* This is our hash table structure. Every dictionary has two of this as we
    * implement incremental rehashing, for the old to the new table. */
    //hash table
    typedef struct dictht {
    //hash table数组[动态二维数组内存布局](http://chinchao.xyz/2016/04/07/cpp-model-2/)
    dictEntry **table;
    //hash table数组的大小,size=2^n
    unsigned long size;
    //sizemash=size-1,hash table掩码,用于计算索引值
    unsigned long sizemask;
    //hash table中节点(dictEntry)的数量
    unsigned long used;
    } dictht;
  • dict结构体

ht

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//字典
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
//rehashidx=-1表示没有进行rehash,否则rehashidx表示hash table数组中当前待rehash的元素的索引
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
//安全迭代器的数量
unsigned long iterators; /* number of iterators currently running */
} dict;
//类型特定函数
typedef struct dictType {
uint64_t (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(*valDup)(void *privdata, const void *obj);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
void (*keyDestructor)(void *privdata, void *key);
void (*valDestructor)(void *privdata, void *obj);
} dictType;

APUE中文第三版勘误

本博客根据自己对APUE中文第三版的阅读理解,列出其中自己认为翻译错误或者翻译有歧义的部分。

1,page81

中文:其中,如果测试文件是否已经存在,mode就为F_OK;否则mode是图4-7中所列常量的按位或。
英文(page102):The mode is either the value F_OK to test if a file exists, or the bitwise OR of any of the flags shown in Figure 4.7.

2,page89

中文:对于符号链接,文件长度是在文件名中的实际字节数。
英文(page111):For a symbolic link, the file size is the numberof bytes in the filename.