redis学习--基础数据类型一(sds)

发表于 | 分类于

前沿

redis作为目前高性能Nosql数据库，应用在大量的互联网应用基础库中；作为能支持高并发的应用基础函数库，它一定存在特殊的优势，特别在大量高频使用的基础数据类型，通过学习它，可以更深入了解如何写高并发的代码

sds字符串优势

c字符串 sds  
  获取字符串长度的复杂度为O(N) O(1)
  api不安全，可能缓冲区溢出 api安全
  修改字符串长度N次必然执行N次内存重分配 至多执行N次重分配
  只能保留文本数据 文本或二进制数据
  没有额外的管理内存开销 每个sds都需要一个header

sds结构

len alloc flag buff end
buf数组实际使用字节数量 总长度-1 类型 ‘\0’  

sds几种不同的子类型

type header size 数据储量  
  sdshdr5 1 byte <2^5=31
  sdshdr8 3 byte 2^5~2^8
  sdshdr16 5 byte 2^8~2^16
  sdshdr32 9 byte 2^16~2^32
  sdshdr64 17 byte >2^32

本篇主要内容

  • 学习redis中如何对字符串，及一系列同步的使用的核心函数：申请、扩容、字符串分割等

代码学习

redis对字符串的封装

redis对string的封装根据字符串长度不同，有5种数据类型；根据结构体中flag类型来确定某一字符串是属于哪一种；而flag占8位，5种类型只需要3位即可表示，还有高5位未使用

/* 通过 __attribute__ ((__packed__)) 关闭了自动对齐，此时的header内的各个部分都是紧紧挨在一起的，没有多余空间 */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 低3位存header类型，高5位保存字符串长度 */
    char buf[]; //字符最长为2^5=31，因此sdshdr5没有alloc
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; //已使用的数组长度不包括零结束标志
    uint8_t alloc; //总长度不包括零结束标志
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 
struct __attribute__ ((__packed__)) sdshdr32 
struct __attribute__ ((__packed__)) sdshdr64

sds基本函数

/* 通过sds类型，sds地址，新建它对应的结构体指针 */
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
/* 通过sds类型，sds地址返回它的结构体指针 */
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
/* 计算sds5类型的字符串长度 */
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
/* 计算sds字符串长度通用函数，不同子类型计算方式大同小异 */
static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

/* 计算sds字符串得到剩余的空间
 * 1. sds5类型没有预留空间
 * 2. 其余类型则为alloc-len
 */
static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0;/* 计算sds5类型的字符串没有预留空间，剩余空间为0 */
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

/* 其余类似函数 */
//设置一个新长度
static inline void sdssetlen(sds s, size_t newlen)
//长度增加：添加字符串后，长度增加
static inline void sdsinclen(sds s, size_t inc)
//获取总空间大小
static inline size_t sdsalloc(const sds s)
//设置总空间大小
static inline size_t sdssetalloc(sds s, size_t newlen)

sds字符串初始化

/*
 * 根据传入参数 init，initlen创建新sds字符串;返回sds buf部分起始地址
 * 1. 根据initlen确定sds数据类型
 * 2. 根据类型计算所需的总内存 sizeof(header)+initlen+1
 * 3. 申请内存，初始化管理结构体
 */
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
	/* 根据initlen确定创建的sds类型
	 * 1. 0<initlen<2^5 ===>SDS_TYPE5
	 * 2. 2^5<initlen<2^8 ===>SDS_TYPE8
	 * 3. 2^8<initlen<2^16 ===>SDS_TYPE16
	 * 4. 2^16<initlen<2^32 ===>SDS_TYPE32
	 * 其余的为SDS_TYPE64 */
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
	/* 返回sds管理结构体大小，用于确定申请内存大小 */
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
	/* 真实申请的内存大小：sds管理结构体大小+用户需求大小+'\0' */
    sh = s_malloc(hdrlen+initlen+1);
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    s = (char*)sh+hdrlen;
	/* 计算flag的内存地址 */
    fp = ((unsigned char*)s)-1;
	/* 根据不同类型，初始化结构体数据 */
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

参考资料

sds简单动态字符串