[大数据]Redis常用数据结构底层实现与验证-String

前言

在比较老的版本中，Redis支持的数据结构一共有五种，分别是：String、Sets、Sorted Sets、Lists 、Hashes ；这五种数据结构也是我们在日常工作中目前使用最多的结构，满足了我们大部分的业务场景，在最新版的Redis版本中，又新增了Bitmaps、Bitfields、HyperLogLog、Geospatial indexes 、Streams 这样的五种数据结构，更加多样化的满足我们日常的使用场景。我们当前主要是来了解一下我们常用的五种数据结构在Redis实现过程中底层所采用的存储结构，并对不同场景进行必要的验证，这样的对我们在日常工作中更为合理的设计提供了必要的帮助，同时可以让我们以更加低的成本，更加快速的方式实现我们所需要的效果，今天我们来看一下我们最常用的String结构的底层实现方案，通过一些简单的方法来验证一下我们探究的东西，这样对我们以后进一步的使用它提供实践基础

Redis Object

Redis中的不同数据结构在存储的时候都是存在一个叫redisObject的结构体中，对应的C语言代码如下：

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; 
    int refcount;
    void *ptr;
} robj;

对于不同的数据结构，只需要分配不同的存储空间大小，然后调整不同的type类型和encoding编码格式，就可以有效的实现这些常用存储结构，同时通过ptr这个指针，可以根据type的不同指向不同的存储结构中，即保证了上层结构的统一性，又保证了底层实现的多样性。有了对这个结构体的简单的了解，我们再来梳理下面的内容

Redis中String的底层数据结构

在了解String类型数据结构前，我们先来看一下Redis中为了性能更加优秀而自定义的一种字符串类型：SDS (Simple Dynamic String)，该自定义字符串类型主要的特点如下：

• 获取字符串长度的时间复杂度是O(1),因为该结构体中的len字段保存了当前字符串的长度
• 支持安全的二进制数据存储，字符串的结束不再依赖于’\0’来表示，可以通过len的长度来确定实际的字符串的长度啦
• 动态扩容机制，在没有达到最大扩容限制之前，每次动态扩容会是原来的内存空间的2倍，有效降低扩容的次数
• 字符串的长度不再依赖于字节数组的长度的判断，这样就可以预分配一些数组长度，来减少内存分配的次数，提高效率
• 惰性释放内存空间，当字符串修改时并不会马上对对应的内存空间进行释放，而是留着这些内存空间供后续的该字符串的变更来使用，如果存储空间触发了某些条件，才会真正的对这些空闲内存进行释放，避免内存泄漏

SDS （简单动态字符串）

typedef char *sds;

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
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[];
};

Redis中不同数据结构中的Key的底层存储方案

Redis中不同的数据结构我们主要是针对于存储的Value来说的，所以我们有的时候很少会去关注Redis中的Key的具体存储方案，在Redis中，不管是String类型数据结构，还是List类型的数据结构，他们的存储的Key都是按照SDS字符串来进行处理的，不管你存储的时候的Key是一个整数、或者是一个字符串、或者是一个小数，底层都会按照SDS来处理方式来进行存储

Redis中String类型数据的处理方案

在Redis中，针对String类型的KV结构的存储，针对于存储的Value的内容的不同，具体的存储的方式也是不同的，下面就来看一下：

• 如果字符串中保存的是一个整数，并且该整数可以用long类型的整数表示，Redis会将键值转化为long型来进行存储，对应 OBJ_ENCODING_INT 编码类型，通过 object encoding 命令查看的话返回值是 int，该种类型直接将改该值保存在redisObject结构体中的ptr属性中，将void的类型转换为long类型，对应的代码如下：

robj *createStringObjectFromLongLongWithOptions(long long value, int valueobj) {
    robj *o;

    if (server.maxmemory == 0 ||
        !(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS))
    {
        /* If the maxmemory policy permits, we can still return shared integers
         * even if valueobj is true. */
        valueobj = 0;
    }

    if (value >= 0 && value < OBJ_SHARED_INTEGERS && valueobj == 0) {
        incrRefCount(shared.integers[value]);
        o = shared.integers[value];
    } else {
        if (value >= LONG_MIN && value <= LONG_MAX) {
            o = createObject(OBJ_STRING, NULL);
            o->encoding = OBJ_ENCODING_INT;
            o->ptr = (void*)((long)value);
        } else {
            o = createObject(OBJ_STRING,sdsfromlonglong(value));
        }
    }
    return o;
}

• 如果字符串中保存的是一个整数，并且该整数大于long类型的整数的最大值，Redis会将值转化为embstr型来进行存储，对应 OBJ_ENCODING_EMBSTR 编码类型，通过 object encoding 命令查看的话返回值是 ebmstr，该种类型将改该值保存在一个sdshdr结构体中，embstr编码类型只调用一次内存分配，在一块连续的空间上同时包含redisObject结构和sdshdr结构，对应的代码如下：

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会将值转化为embstr型来进行存储，对应 OBJ_ENCODING_EMBSTR 编码类型，通过 object encoding 命令查看的话返回值是 ebmstr，该种类型将改该值保存在一个sdshdr结构体中，embstr编码类型只调用一次内存分配，在一块连续的空间上同时包含redisObject结构和sdshdr结构，对应的代码如下：

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}

• 如果字符串中保存的是字符并且长度大于44的话，Redis会将值转化为raw型来进行存储，对应 OBJ_ENCODING_RAW 编码类型，通过 object encoding 命令查看的话返回值是 raw，该种类型将改该值保存在一个sdshdr结构体中，在一块连续的redisObject结构体通过ptr指针指向sdshdr结构体，所以该创建过程需要进行两次内存分配，对应的代码如下：

robj *createRawStringObject(const char *ptr, size_t len) {
    return createObject(OBJ_STRING, sdsnewlen(ptr,len));
}

robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    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. */
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    return o;
}

功能验证

在Long类型范围内的整数保存为 OBJ_ENCODING_INT 编码类型

public static void main(String[] args) {
        try(Jedis jedis = new Jedis("127.0.0.1", 6379)) {

            Long l = Long.MAX_VALUE;
            jedis.del("l");

            jedis.set("l", l.toString());
            System.out.println("byte: " + Arrays.toString(l.toString().getBytes(StandardCharsets.UTF_8)));
            System.out.println("l size: " + l.toString().getBytes(StandardCharsets.UTF_8).length);
            System.out.println("objectEncoding:" + jedis.objectEncoding("l"));

            
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

运行结果：

byte: [57, 50, 50, 51, 51, 55, 50, 48, 51, 54, 56, 53, 52, 55, 55, 53, 56, 48, 55]
l size: 19
objectEncoding:int

大于Long类型范围的整数或小于等于44个字节的字符串保存为 OBJ_ENCODING_EMBSTR 编码类型

public static void main(String[] args) {
        try(Jedis jedis = new Jedis("127.0.0.1", 6379)) {

            BigDecimal b = BigDecimal.valueOf(Long.MAX_VALUE).add(BigDecimal.valueOf(1000));

            jedis.set("b", b.toString());
            System.out.println("b byte: " + Arrays.toString(b.toString().getBytes(StandardCharsets.UTF_8)));
            System.out.println("b size: " + b.toString().getBytes(StandardCharsets.UTF_8).length);
            System.out.println("objectEncoding:" + jedis.objectEncoding("b"));

            String embStr = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqr";
            jedis.del("embStr");

            jedis.set("embStr", embStr);
            System.out.println("embStr byte: " + Arrays.toString(embStr.getBytes(StandardCharsets.UTF_8)));
            System.out.println("embStr size: " + embStr.getBytes(StandardCharsets.UTF_8).length);
            System.out.println("objectEncoding:" + jedis.objectEncoding("embStr"));

        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

运行结果：

b byte: [57, 50, 50, 51, 51, 55, 50, 48, 51, 54, 56, 53, 52, 55, 55, 54, 56, 48, 55]
b size: 19
objectEncoding:embstr

embStr byte: [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114]
embStr size: 44
objectEncoding:embstr

大于44个字节的字符串保存为 OBJ_ENCODING_RAW 编码类型

public static void main(String[] args) {
        try(Jedis jedis = new Jedis("127.0.0.1", 6379)) {

            String raw = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqr1";
            jedis.del("raw");

            jedis.set("raw", raw);
            System.out.println("raw byte: " + Arrays.toString(raw.getBytes(StandardCharsets.UTF_8)));
            System.out.println("raw size: " + raw.getBytes(StandardCharsets.UTF_8).length);
            System.out.println("objectEncoding:" + jedis.objectEncoding("raw"));
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

运行结果：

raw byte: [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 49]
raw size: 45
objectEncoding:raw

结论

通过上面的分析和验证，其实整体的结论及日常使用需要注意的点已经非常清晰啦，主要总结以下几点：

• 从空间占用的角度来说，我们存储的value尽量用数字来表示，这样就不需要单独的创建一个结构体来保存这些信息啦，直接通过redisObject就可以搞定了，很多时候人们保存字符串可能是为了更加容易理解，其实很多时候有一个清晰明了的注释可能比一些自定义的字符串更加容易让使用者理解；如果一定需要使用字符串的话，尽量小于44个字符，这样空间占用也是比更长的字符串要小的，因为如果字符串更长的话，就需要更大的sdshdr来进行保存的

• 从创建效率的角度来说的话，int类型的效率是最高的，因为只需要创建一个redisObject结构体，并且将值赋值给 ptr 即可；embstr的效率次之，虽然创建的是两个结构体，但是只需要分配一次内存即可；raw类型的最慢，需要创建两个结构体并且分配两次内存空间

• 从查询效率的角度来说，int类型的数据找到对应的redisObject即可；embstr类型的值需要找到redisObject并且进行一次内存空间偏移即可找到对应的值；而raw类型的话需要找到redisObject并且再通过指针才能找到真正的数据

所以不管是从哪个角度来说，都是 int > embstr > raw的，不过具体情况还要看具体的业务环境，我们在设计的时候需要考虑一下这样的几个区别，尽可能的向效率最高成本最低的方案去进行设计

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系