当前位置: 首页 > redis, 分布式系统 > 正文

Redis核心解读–类型系统解构

关键字:
1 星2 星3 星4 星5 星 (1 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

Redis的db中每个key都对应一个对象,而对象有五种类型:string,list,set,zest,hash。而list、set、zest、hash类型存储的都是string类型。

1
2
3
4
5
6
/* Object types */
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4

在这里,我称呼它们为“逻辑类型”,它是对Redis使用用户可见的,但是Redis在内存中存储某种类型对象时却可能采用不同的物理存储编码方式。

Redis中的“object”

在介绍物理存储结构之前,先介绍下在Redis源码中“object”的概念。

1
2
3
4
5
6
7
8
9
/* A redis object, that is a type able to hold a string / list / set */
typedef struct redisObject {
    unsigned type:4;
    unsigned notused:2;     /* Not used */
    unsigned encoding:4;
    unsigned lru:22;        /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

robj是真正存储redis逻辑类型的结构,4位的`type`表示逻辑类型,如REDIS_STRING,`encoding`表示该逻辑类型的物理存储编码方式(如下文介绍的),`lru`用于LRU算法用于当内存超限时清除内存中的对象。`refcount`是对象的计数持有。如果在OO思想中,robj应该是五种逻辑类型的父类,string、list、set、zset、hash从robj继承,但是因为在C中,所以Redis采用robj这种结构来统一不同的逻辑类型,使得所有value值都能用robj在函数间传递,而不需要用具体的类型结构。

从Redis服务器端接受到客户端请求后,解析请求包的参数,就会将所有参数转换为string类型的robj对象,robj在层层解析中传递,最终通过逻辑类型的实现进行相应的处理

Redis类型物理存储解构

1
2
3
4
5
6
7
8
#define REDIS_ENCODING_RAW 0     /* Raw representation */
#define REDIS_ENCODING_INT 1     /* Encoded as integer */
#define REDIS_ENCODING_HT 2      /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6  /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */

Redis内部物理表示类型的编码方式目前有8种:

string类型: REDIS_ENCODING_RAW, REDIS_ENCODING_INT

list类型: REDIS_ENCODING_ZIPLIST, REDIS_ENCODING_LINKEDLIST

set类型: REDIS_ENCODING_HT, REDIS_ENCODING_INTSET

zset类型: REDIS_ENCODING_ZIPLIST, REDIS_ENCODING_SKIPLIST

hash类型: REDIS_ENCODING_ZIPLIST, REDIS_ENCODING_HT

string类型的值包括原始字符串编码和整数编码,string类型在Redis可能是DB中的key或者value或者其他逻辑类型中的值,如list中的元素,set中的元素,hash类型中的键或者值。在作为DB中的key时,是将string类型的实际字符串作为key,而不是robj对象(下文详细介绍关于DB的kv存储方式)。除此之外,如果string类型代表的值是一个整数的话,可以转换编码方式为REDIS_ENCODING_INT节约空间存储,这样robj的ptr指针是void *,可以直接将ptr=(void *)long_obj,这样做的好处就是代表整数的string不用额外的内存保存值,因为long跟指针的占用字节数不管32位还是64位系统都是一样的。

list类型有zip list和linked list两种物理存储编码方式,当时使用linked list时,通常list中元素较多,可以直接将接受到的robj对象(也就是string类型的robj对象)插入,而使用zip list方式时,是将robj对象的ptr指针指向的字符串复制到zip list的存储字节序列内。list物理存储编码方式通过下面这个函数转换不同的编码,当增加元素时,如果值长度大于配置中设置的list-max-ziplist-value时,或者list长度大于list-max-ziplist-entries时,list类型会从非常节约空间的REDIS_ENCODING_ZIPLIST转为REDIS_ENCODING_LINKEDLIST.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void listTypeTryConversion(robj *subject, robj *value) {
    if (subject->encoding != REDIS_ENCODING_ZIPLIST) return;
    if (value->encoding == REDIS_ENCODING_RAW &&
        sdslen(value->ptr) > server.list_max_ziplist_value)
            listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
}
void listTypePush(robj *subject, robj *value, int where) {
    /* Check if we need to convert the ziplist */
    listTypeTryConversion(subject,value);
    if (subject->encoding == REDIS_ENCODING_ZIPLIST &&
        ziplistLen(subject->ptr) >= server.list_max_ziplist_entries)
            listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
    …….
}

set类型分为两种情况,如果set里的值全为整数,并且set的元素数量小于配置中的set-max-inset-entries,那么编码为针对整数优化空间利用的REDIS_ENCODING_INTSET,否则是REDIS_ENCODING_HT。REDIS_ENCODING_INTSET是将encoding为REDIS_ENCODING_INT的robj的ptr值复制到intset的字节序列内,而REDIS_ENCODING_HT是直接将指向robj对象的指针作为key和value插入到dict结构。

zset类型跟list类型一样,如果zset中的元素数量小于配置中的zset-max-ziplist-entries并且元素值长度都小于zset-max-ziplist-value,那么zest编码为REDIS_ENCODING_ZIPLIST,否则为REDIS_ENCODING_SKIPLIST。

hash类型跟zset类型一样,如果hash中元素数量小于配置中的hash-max-ziplist-entries并且值长度都小于hash-max-ziplist-value,那么编码为REDIS_ENCODING_ZIPLIST,否则为REDIS_ENCODING_HT。

每个DB其实就是一个物理存储编码方式为REDIS_ENCODING_HT的DB逻辑类型,跟REDIS_HASH逻辑类型不同的是,DB的key值不是robj对象,是sds字符串(在Redis有一个sds结构,是一个char *的包装,带有长度,空闲长度等信息)。而value值是robj对象

Redis类型实现过程

t_string.c t_list.c t_set.c t_zset.c t_hash.c

这五个文件实现了redis的类型接口,当redis服务器端接收到都某个类型的增删改查命令时,都通过调用这五个文件提供的接口,类型的接口实现一般会解析需要修改的类型对象的编码方式,然后调用特定的数据结构API对内存中特定编码对象的访问。

如命令 hset myhash f “asdf” :

首先,服务器接受到客户端的命令后,会解析第一个参数,得知是hset后,调用t_hash.c中的hsetCommand(),检测是否myhash对象是否需要创建,然后检测该myhash对象是否需要转换编码方式,如从linked_list转为skiplist,然后调用hashTypeSet接口执行真正set操作,set操作会根据具体的编码来执行对应的操作方式。

1
2
3
4
5
6
7
8
9
10
11
12
void hsetCommand(redisClient *c) {
    int update;
    robj *o;
 
    if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
    hashTypeTryConversion(o,c->argv,2,3);
    hashTypeTryObjectEncoding(o,&c->argv[2], &c->argv[3]);
    update = hashTypeSet(o,c->argv[2],c->argv[3]);
    addReply(c, update ? shared.czero : shared.cone);
    signalModifiedKey(c->db,c->argv[1]);
    server.dirty++;
}

小结

Redis在数据结构实现和用户可见类型做了一个映射,Redis动态的改变用户可见类型的内存结构,Redis逻辑类型决定了使用底层数据结构的方式,object的使用就非常复杂,比如REDIS_HASH类型,如果是ziplist编码,key,value object需要去掉object结构,只将o->ptr的内容放入,但如果使用dict结构,那么,key、value实际上是robj的指针。另外,每个db实际上是一个dict结构,也可以看成是db类型,db同样是基于dict结构,但是key不能是object,而value是object。

本文固定链接: http://www.chepoo.com/redis-analysis-data-structure.html | IT技术精华网

Redis核心解读–类型系统解构:等您坐沙发呢!

发表评论