9.t_string——redis可见数据结构

介绍完Redis的底层数据结构之后， 介绍我们平时使用Redis的时候可以直接看到的数据结构：

  • 字符串
  • 哈希
  • 链表
  • 集合和有序集合。

字符串的实现

上一章说过，字符串有3种编码形式

类型 编码 描述
REDIS_STRING REDIS_ENCODING_INT 使用整数值实现的字符串对象
REDIS_STRING REDIS_ENCODING_EMBSTR 使用 embstr 编码的简单动态字符串实现的字符串对象
REDIS_STRING REDIS_ENCODING_RAW 使用简单动态字符串实现的字符串对象。

这三种类型分别对应的底层数据结构为int，embstr, sds。

编码的选择

字符串具体用哪种方法实现呢？

  • REDIS_ENCODING_INT：如果字符串存的是整数，就用整数形式保存
  • REDIS_ENCODING_RAW：如果字符串对象保存的是一个字符串值， 并且这个字符串值的长度大于44字节， 那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值， 并将对象的编码设置为 raw
  • REDIS_ENCODING_EMBSTR：如果字符串对象保存的是一个字符串值， 并且这个字符串值的长度小于等于 44 字节， 那么字符串对象将使用 embstr 编码的方式来保存这个字符串值。

embstr是啥

embstr 编码是专门用于保存短字符串的一种优化编码方式， 这种编码和 raw 编码一样， 都使用 redisObject 结构和 sdshdr 结构来表示字符串对象， 但 raw 编码会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构， 而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间， 空间中依次包含 redisObject 和 sdshdr 两个结构

编码的转换

int转为RAW
对于 int 编码的字符串对象来说， 如果我们向对象执行了一些命令， 使得这个对象保存的不再是整数值， 而是一个字符串值， 比如在最开始的数字类型后边执行了一个append的操作，加上了一串字符串，那么字符串对象的编码将从 int 变为 raw
embstr编码转换为raw编码
因为 Redis 没有为 embstr 编码的字符串对象编写任何相应的修改程序 （只有 int 编码的字符串对象和 raw 编码的字符串对象有这些程序）， 所以 embstr 编码的字符串对象实际上是只读的： 当我们对 embstr 编码的字符串对象执行任何修改命令时， 程序会先将对象的编码从 embstr 转换成 raw ， 然后再执行修改命令； 因为这个原因， embstr 编码的字符串对象在执行修改命令之后， 总会变成一个 raw 编码的字符串对象。

字符串的命令

字符串支持的命令如下：

命令 命令描述
SET key value [ex 秒数][px 毫秒数][nx/xx] 设置指定key的值
GET key 获取指定key的值
APPEND key value 将value追加到指定key的值末尾
INCRBY key increment 将指定key的值加上增量increment
DECRBY key decrement 将指定key的值减去增量decrement
STRLEN key 返回指定key的值长度
SETRANGE key offset value 将value覆写到指定key的值上，从offset位开始
GETRANGE key start end 获取指定key中字符串的子串[start,end]
MSET key value [key value …] 一次设定多个key的值
MGET key1 [key2..] 一次获取多个key的值

SET 命令的实现

set命令是调用setCommand实现的，命令格式如下

set key value [ex 秒数] [px 毫秒数] [nx/xx]

其中，各个选项的含义如下:

  • ex 设置指定的到期时间，单位为秒
  • px 设置指定的到期时间，单位为毫秒
  • nx 只有在key不存在的时候，才设置key的值
  • xx 只有key存在时，才对key进行设置操作
void setCommand(client *c) {
    robj *expire = NULL;
    int unit = UNIT_SECONDS;
    int flags = OBJ_NO_FLAGS;

    if (parseExtendedStringArgumentsOrReply(c,&flags,&unit,&expire,COMMAND_SET) != C_OK) {
        return;
    }

    c->argv[2] = tryObjectEncoding(c->argv[2]);
    setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}

parseExtendedStringArgumentsOrReply()函数是解析参数用的,设置对应的flag
tryObjectEncoding() 尝试将字符串编码成整数或者EMB，流流程如下：

robj *tryObjectEncoding(robj *o) {
    long value;
    sds s = o->ptr;
    size_t len;
    // 确认是字符串类型
    serverAssertWithInfo(NULL,o,o->type == OBJ_STRING);
    
    // 如果已经是INT编码就无需再编码了
    // #define sdsEncodedObject(objptr) (objptr->encoding == OBJ_ENCODING_RAW || objptr->encoding == OBJ_ENCODING_EMBSTR)
    if (!sdsEncodedObject(o)) return o;
    // 只对引用计数为1的进行编码，共享的不编码
     if (o->refcount > 1) return o;

    /****************************
    如果长度小于20就尝试编码成long
    这里说是长度小于20能编码成long，大于不行
    #define ULLONG_MAX 18446744073709551615ULL
    20位，大于20位肯定不行
    ****************************/
    len = sdslen(s);
    if (len <= 20 && string2l(s,len,&value)) {   // string2l()尝试把s转化成long存在value
        /*
          [1]这里的if是判断是否使用共享对象,标记为1,后面细说
        */
        if ((server.maxmemory == 0 ||
            !(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) &&
            value >= 0 &&
            value < OBJ_SHARED_INTEGERS)
        {
            decrRefCount(o);
            incrRefCount(shared.integers[value]);
            return shared.integers[value];
        } else {
            /* 如果原先是RAW形式，成功用整数编码string，更换o的编码形式 ，并把ptr指向value */
            if (o->encoding == OBJ_ENCODING_RAW) {
                sdsfree(o->ptr);
                o->encoding = OBJ_ENCODING_INT;
                o->ptr = (void*) value;
                return o;
            /* 如果原先是EMBSTR形式，把o直接释放掉，重新创建一个robj */
            /* createStringObjectFromLongLongForValue(long) 根据数字创建一个robj */
            } else if (o->encoding == OBJ_ENCODING_EMBSTR) {
                decrRefCount(o);
                return createStringObjectFromLongLongForValue(value);
            }
        }
    }

    //************************ 整数编码失败，如果长度小于39，开始编码成EMB形式***********
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) {
        robj *emb;

        if (o->encoding == OBJ_ENCODING_EMBSTR) return o;
        //【2】标记一下，稍后详解一下emb
        emb = createEmbeddedStringObject(s,sdslen(s));
        decrRefCount(o);
        return emb;
    }
  /*********************************************编码EMB也失败了，就尝试删除sds的多余空间
  // 
    trimStringObjectIfNeeded(o);
    return o;
}

[1]共享对象

[2]emb编码

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


image.png

创建emb的函数如下

robj *createEmbeddedStringObject(const char *ptr, size_t len) {
    robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);
    struct sdshdr8 *sh = (void*)(o+1);

    o->type = OBJ_STRING;
    o->encoding = OBJ_ENCODING_EMBSTR;
    o->ptr = sh+1;
    o->refcount = 1;
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }

    sh->len = len;
    sh->alloc = len;
    sh->flags = SDS_TYPE_8;
    if (ptr == SDS_NOINIT)
        sh->buf[len] = '\0';
    else if (ptr) {
        memcpy(sh->buf,ptr,len);
        sh->buf[len] = '\0';
    } else {
        memset(sh->buf,0,len+1);
    }
    return o;
}

为什么是44？

redis用jemalloc分配内存，一次分配64b，减去各种头，剩下的就是44

下面看执行SET命令的函数

setGenericCommand()函数是以下命令: SET, SETEX, PSETEX, SETNX.的最底层实现

  • SET:普通设定
  • SETEX:设定定时删除,如果 key 已经存在， SETEX 命令将会替换旧的值
redis 127.0.0.1:6379> SETEX KEY_NAME TIMEOUT VALUE
#example
redis 127.0.0.1:6379> SETEX mykey 60 redis
OK
redis 127.0.0.1:6379> TTL mykey
60
redis 127.0.0.1:6379> GET mykey
"redis
  • PSETEX:以毫秒为单位设置 key 的生存时间。
redis 127.0.0.1:6379> PSETEX key1 EXPIRY_IN_MILLISECONDS value1 
redis 127.0.0.1:6379> PSETEX mykey 1000 "Hello"
OK
redis 127.0.0.1:6379> PTTL mykey
999
redis 127.0.0.1:6379> GET mykey
1) "Hello"
  • SETNX: （SET if Not eXists） 命令在指定的 key 不存在时，为 key 设置指定的值。
//setGenericCommand()函数是以下命令: SET, SETEX, PSETEX, SETNX.的最底层实现
//flags 可以是NX或XX，由上面的宏提供
//expire 定义key的过期时间，格式由unit指定
//ok_reply和abort_reply保存着回复client的内容，NX和XX也会改变回复
//如果ok_reply为空，则使用 "+OK"
//如果abort_reply为空，则使用 "$-1"
void setGenericCommand(client *c, int flags, robj *key, robj *val, robj *expire, int unit, robj *ok_reply, robj *abort_reply) {
    long long milliseconds = 0; /* initialized to avoid any harmness warning */ //初始化，避免错误

    //如果定义了key的过期时间
    if (expire) {
        //从expire对象中取出值，保存在milliseconds中，如果出错发送默认的信息给client
        if (getLongLongFromObjectOrReply(c, expire, &milliseconds, NULL) != C_OK)
            return;
        // 如果过期时间小于等于0，则发送错误信息给client
        if (milliseconds <= 0) {
            addReplyErrorFormat(c,"invalid expire time in %s",c->cmd->name);
            return;
        }
        //如果unit的单位是秒，则需要转换为毫秒保存
        if (unit == UNIT_SECONDS) milliseconds *= 1000;
    }

    //lookupKeyWrite函数是为执行写操作而取出key的值对象
    //如果设置了NX(不存在)，并且在数据库中 找到 该key，或者
    //设置了XX(存在)，并且在数据库中 没有找到 该key
    //回复abort_reply给client
    if ((flags & OBJ_SET_NX && lookupKeyWrite(c->db,key) != NULL) ||
        (flags & OBJ_SET_XX && lookupKeyWrite(c->db,key) == NULL))
    {
        addReply(c, abort_reply ? abort_reply : shared.nullbulk);
        return;
    }
    //在当前db设置键为key的值为val
    setKey(c->db,key,val);

    //设置数据库为脏(dirty)，服务器每次修改一个key后，都会对脏键(dirty)增1
    server.dirty++;

    //设置key的过期时间
    //mstime()返回毫秒为单位的格林威治时间
    if (expire) setExpire(c->db,key,mstime()+milliseconds);

    //发送"set"事件的通知，用于发布订阅模式，通知客户端接受发生的事件
    notifyKeyspaceEvent(NOTIFY_STRING,"set",key,c->db->id);

    //发送"expire"事件通知
    if (expire) notifyKeyspaceEvent(NOTIFY_GENERIC,
        "expire",key,c->db->id);

    //设置成功，则向客户端发送ok_reply
    addReply(c, ok_reply ? ok_reply : shared.ok);
}

GET命令

类似于set命令，get命令也是最终调用一个getGenericcommand的函数实现：

//GET 命令的底层实现
int getGenericCommand(client *c) {
    robj *o;

    //lookupKeyReadOrReply函数是为执行读操作而返回key的值对象，找到返回该对象，找不到会发送信息给client
    //如果key不存在直接，返回0表示GET命令执行成功
    if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.nullbulk)) == NULL)
        return C_OK;

    //如果key的值的编码类型不是字符串对象
    if (o->type != OBJ_STRING) {
        addReply(c,shared.wrongtypeerr);    //返回类型错误的信息给client，返回-1表示GET命令执行失败
        return C_ERR;
    } else {
        addReplyBulk(c,o);  //返回之前找到的对象作为回复给client，返回0表示GET命令执行成功
        return C_OK;
    }
}

参考

https://harleylau.github.io/2018/05/redis%E6%BA%90%E7%A0%81%E5%89%96%E6%9E%90%E5%AD%97%E7%AC%A6%E4%B8%B2t_string%E5%AE%9E%E7%8E%B0/

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • redis 内部数据结构(1.7)-对象
    Redis 使用对象来表示数据库中的键和值， 每次当我们在 Redis 的数据库中新创建一个键值对时， 我们至少会...
    颜灏_2181阅读 1,486评论 0赞 0
  • redis string底层数据结构
    系列 redis数据淘汰原理redis过期数据删除策略redis server事件模型redis cluster ...
    晴天哥_王志阅读 22,378评论 4赞 14
  • Redis底层数据结构之string
    我们都知道，Redis是由C语言编写的。在C语言中，字符串标准形式是以空字符\0作为结束符的，但是Redis里面的...
    天明code阅读 3,523评论 0赞 0
  • 表情管理
    表情是什么，我认为表情就是表现出来的情绪。表情可以传达很多信息。高兴了当然就笑了，难过就哭了。两者是相互影响密不可...
    Persistenc_6aea阅读 127,505评论 2赞 7
  • 2019-11-28 173
    16宿命：用概率思维提高你的胜算 以前的我是风险厌恶者，不喜欢去冒险，但是人生放弃了冒险，也就放弃了无数的可能。 ...
    yichen大刀阅读 11,304评论 0赞 4

友情链接更多精彩内容