redis-源码学习-基础数据类型

Redis构建了自己的类型系统

• redisObject 对象
• 基于 redisObject 对象的类型检查
• 基于 redisObject 对象的显式多态函数
• 对 redisObject 进行分配、共享和销毁的机制

RedisObject 编码结构

redisObject 是 Redis 类型系统的核心，数据库中的每个键、值，以及 Redis 本身处理的参数，都表示为这种数据类型。

/*
 * Redis 对象
 */
 typedef struct redisObject {
     // 类型
     unsigned type:4;
     // 编码
     unsigned encoding:4;
     // 对象最后一次被访问的时间
     unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
     // 引用计数
     int refcount;
     // 指向实际值的指针
     void *ptr;
} robj;

说明：type 、 encoding 和 ptr 是最重要的三个属性

• type（类型）
  • REDIS_STRING 0 // 字符串
  • REDIS_LIST 1 // 列表
  • REDIS_SET 2 // 集合
  • REDIS_ZSET 3 // 有序集
  • REDIS_HASH 4 // 哈希表
• encoding（编码）
  • REDIS_ENCODING_RAW 0 // 编码为字符串
  • REDIS_ENCODING_INT 1 // 编码为整数
  • REDIS_ENCODING_HT 2 // 编码为字典
  • REDIS_ENCODING_ZIPMAP 3 // 编码为 zipmap
  • REDIS_ENCODING_LINKEDLIST 4 // 编码为双端链表
  • REDIS_ENCODING_ZIPLIST 5 // 编码为压缩列表
  • REDIS_ENCODING_INTSET 6 // 编码为整数集合
  • REDIS_ENCODING_SKIPLIST 7 // 编码为跳跃表
• ptr
  • 指向实际保存值得数据结构
    • 这个数据结构由type属性 和encoding 属性决定
  • 例子
    • redisObject 的 type属性为REDIS_LIST，encoding属性为REDIS_ENCODING_LINKEDLIST
    • 那么这个对象就是一个Redis列表，它的值保存在一个双端链表内，而ptr指针就指向这个双端链表

命令的类型检查和多态

当执行一个处理数据类型的命令时，Redis执行以下步骤：

• 根据给定 key ，在数据库字典中查找和它像对应的 redisObject ，如果没找到，就返回NULL 。
• 检查 redisObject 的 type 属性和执行命令所需的类型是否相符，如果不相符，返回类型错误。
• 根据 redisObject 的 encoding 属性所指定的编码，选择合适的操作函数来处理底层的数据结构。
• 返回数据结构的操作结果作为命令的返回值

REDIS_ENCODING_INT

如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构 的ptr属性里面（将void* 转换成long），并将字符串对象的编码设置为int。

REDIS_ENCODING_RAW

如果字符串对象保存的是一个字符串字符串值， 并且这个字符串值的长度大于32字节，那么字符串对象将使用一个简单动态字符串（SDS） 来保存这个字符串值，并将 对象的编码设置为raw。

REDIS_ENCODING_EMBSTR

如果字符串对象保存的是一个字符串值，并且这个字符串值的长度小于等于32字节，那么字符串对象将使用embstr编码的方式来保存这个字符串值。

• embstr 编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次。
• 释放embstr编码的字符串对象只需要调用一次内存释放函数，而释放raw编码的字符串对象需要调用两次内存释放函数。
• 因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比起raw编码的字符串对象能够 更好地利用缓存带来的优势。

REDIS_ENCODING_ZIPLIST

当列表对想可以同时满足以下两个条件时，列表对象使用ziplist编码：

• 列表对象保存的所有字符串元素的长度都小于64字节
• 列表对象保存的元素数量小于512个，不能满足这两个条件的列表对象需要使用linkedlist编码

当哈希对象可以同时满足以下两个条件时，哈希对象使用ziplist编码

• 哈希对象保存所有键值对的键和值的字符串长度都小于64字节
• 哈希对象保存的键值对梳理小于512个，不能满足这两个条件的哈希对象需要使用hashtable编码

REDIS_ENCODING_LINKEDLIST

REDIS_ENCODING_HT

REDIS_ENCODING_SKIPLIST

REDIS_ENCODING_INTSET

当集合对象可以同事满足以下两个条件时，对象使用intset编码：

• 集合对象保存的所有元素都是整数值
• 集合对象保存的元素数量不超过512个

不满足这两个条件的集合对象需要使用hashtable编码

/*
 *对象类型
 */
#define REDIS_STRING 0  // 字符串
#define REDIS_LIST   1  // 列表
#define REDIS_SET    2  // 集合
#define REDIS_ZSET   3  // 有序集
#define REDIS_HASH   4  // 哈希表
/*
 * 对象编码
 */
#define REDIS_ENCODING_RAW          0   // 编码为字符串
#define REDIS_ENCODING_INT          1   // 编码为整数
#define REDIS_ENCODING_HT           2   // 编码为哈希表
#define REDIS_ENCODING_ZIPMAP       3   // 编码为 zipmap
#define REDIS_ENCODING_LINKEDLIST   4   // 编码为双端链表
#define REDIS_ENCODING_ZIPLIST      5   // 编码为压缩列表
#define REDIS_ENCODING_INTSET       6   // 编码为整数集合
#define REDIS_ENCODING_SKIPLIST     7   // 编码为跳跃表
#define REDIS_ENCODING_EMBSTR       8   // 编码为内嵌的sds字符串类型

Redis 数据结构和常见数据结构的实现对比

	分类（常见算法）	Redis（实现算法）	是否有序	运行元素重复
字符串	字符串	String——(整数，动态字符串)	*	*
列表	列表——（数组/链表）	List——（双向链表，压缩列表）	是	是
集合	集合——（基于字典)	Set ——（基于字典，数组）	否	否
有序集合——（二叉树）	Zset——（跳跃表，压缩列表）	是
字典	字典——（哈希表）	Hash——（哈希表，压缩列表）	否	key不能重复
有序字典——（二叉树）	*	是

数据结构

simple dynamic string(SDS)

/*
 * 保存字符串对象的结构，之前的版本2.9
 */
struct sdshdr {
     
    // buf 中已占用空间的长度
    int len;
    // buf 中剩余可用空间的长度
    int free;
    // 数据空间
    char buf[];
};

//3.2.4版本
/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
//3.2.4版本
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 */
    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 */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

压缩列表-ziplist

/*
 * 虚拟 ziplist 结构，实际上无该结构
 */
typedef struct ziplist{
     uint32_t zlbytes;      /*整个压缩列表占用内存字节数*/
     uint32_t zltail;       /*尾部距离列表起始位置有多少字节*/
     uint16_t zllen;        /*存储节点个数*/
     unsigned char* entryList[]; /*列表节点*/
     unit8_t char zlend;    /*尾部标识,特殊标识0XFF(十进制255)*/
}ziplist;
  
/*
 * 保存 ziplist 节点信息的结构
 */
typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;  /*前置节点的长度,
                                                编码prevrawlen所需的字节大小*/
    unsigned int lensize, len;  /*当前节点值的长度, 编码 len 所需的字节大小*/
    unsigned int headersize;    /*当前节点 header 的大小
                                  值 = prevrawlensize + lensize*/
    unsigned char encoding;     /*当前节点值所使用的编码类型*/
    unsigned char *p;           /*指向当前节点的指针*/
}zlentry;

双端链表-list

/*
 * 双端链表结构
 */
typedef struct list {
    listNode *head;     /* 表头节点  */
    listNode *tail;     /* 表尾节点  */
    void *(*dup)(void *ptr);  /* 节点值复制函数  */
    void (*free)(void *ptr);  /* 节点值释放函数  */
    int (*match)(void *ptr, void *key);   /* 节点值对比函数 */
    unsigned long len;    /* 链表所包含的节点数量 */
} list;
  
/*
 * 双端链表节点
 */
typedef struct listNode {
    struct listNode *prev;   /* 前置节点 */
    struct listNode *next;   /* 后置节点 */
    void *value;             /* 节点的值 */
} listNode;

字典-DICT

/*
 * 字典
 */
typedef struct dict {
    dictType *type;     /* 类型特定函数 */
    void *privdata;     /* 私有数据 */
    dictht ht[2];       /* 哈希表 */
    int rehashidx;      /* rehash 索引,当 rehash 不在进行时，值为 -1 */
    int iterators;      /* 目前正在运行的安全迭代器的数量*/
} dict;
  
/*
 * 哈希表
 * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
 */
typedef struct dictht {
    dictEntry **table;      /* 哈希表数组 */
    unsigned long size;     /* 哈希表大小 */
    unsigned long sizemask; /* 哈希表大小掩码，用于计算索引值，
                            总是等于 size - 1*/
    unsigned long used;     /* 该哈希表已有节点的数量 */
} dictht;
  
/*
 * 哈希表节点
 */
typedef struct dictEntry {
    void *key;      /* 键 */
    union {         /* 值 */
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;  /* 指向下个哈希表节点，形成链表*/
} dictEntry;

整数集合-intset

/*
*  整数集合
*/
typedef struct intset {
    uint32_t encoding;  /* 编码方式 */
    uint32_t length;    /* 集合包含的元素数量 */
    int8_t contents[];  /* 保存元素的数组 */
} intset;
 
/*
 * intset 的编码方式
 */
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

跳跃表-skiplist

  
/*
 * 有序集合
 */
typedef struct zset {
    // 字典，键为成员，值为分值
    // 用于支持 O(1) 复杂度的按成员取分值操作
    dict *dict;
    // 跳跃表，按分值排序成员
    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
    // 以及范围操作
    zskiplist *zsl;
} zset;
  
/*
 * 跳跃表
 */
typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;
 
  
/*
 * zset使用一个特殊版本的跳跃表
 */
typedef struct zskiplistNode {
    // 成员对象
    robj *obj;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;
  
  
  
/* Returns a random level for the new skiplist node we are going to create.
 *
 * 返回一个随机值，用作新跳跃表节点的层数。
 *
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned.
 *
 * 返回值介乎 1 和 ZSKIPLIST_MAXLEVEL 之间（包含 ZSKIPLIST_MAXLEVEL），
 * 根据随机算法所使用的幂次定律，越大的值生成的几率越小。
 *
 * T = O(N)
 */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        //这里取小于0xffff的数，有0.25的概率level+1，因此level有1/4概率为2, 1/16的概率为3等等
 
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}