Redis5种数据结构的运用及实现

2018-07-03  本文已影响0人  Sponge1128

1.数据结构

1.1字符串

       字符串类型的值实际可以是字符串、数字(整数，浮点数)，甚至是二进制(图片、视频)，但是值不能超过512MB。
1）常用命令

2)不常用命令：

3)内部编码：int 8字节长整形；embstr (基于SDS实现)小于等于39个字节的字符串；raw(基于SDS实现) 大于39个字节的字符串

4)典型使用场景：缓存数据，计数，共享Session，限速；

1.2哈希

键指向一个映射关系field-value；
1)命令

  1. 内部编码
    　　Ziplist(压缩列表)：当哈希类型元素个数小于hash-max-ziplist-entries配置(默认512)、同时所有值都小于hash-max-ziplist-value配置(默认64字节)时，使用ziplist作为哈希的内部实现，以紧凑结构实现多个元素的连续存储，所有在节省内存方面比hashtable好。
    　　Hashtable(哈希表)：当哈希类型无法满足ziplist条件时，Redis会使用hashtable作为哈希的内部实现，因为ziplist此时读写效率会下降，而hashtable读写效率时O(1)的，但会消耗更多内存。

1.3列表

列表中的元素是有序的，可以通过索引下标获取某个元素或者某个范围内的元素列表；列表中的元素可以是重复的；最多可以存储232-1个元素；可以对列表两端插入和弹出。
1）命令

a)添加操作

b)查找

c)删除

d)修改

e)阻塞操作O(1)
　　blpop key [key …] timeout
　　brpop key [key …] timeout
　　blpop/brpop是lpop和rpop的阻塞版本，其中key [key …]代表多个列表的键；timeout代表阻塞时间。若列表为空，timeout=0则一直阻塞或者等待timeout时间后返回；若列表不为空，客户端立即返回，
　　需要注意的是：1.如果是多个键，brpop会从左至右依次遍历键，一旦有一个键能弹出元素，客户端立即返回；2.如果多个客户端对用一个键指向brpop，那么最先执行的客户端可以获取到弹出的值；

2）内部编码
　　ziplist，同哈希，元素个数小于list-max-ziplist-entries配置，且每个元素值小于list-max-ziplist-value配置，采用压缩列表作为内部实现来减少内存使用；
　　linkedlist(链表)，无法满足ziplist条件时，采用linkedlist；

1.4集合

集合用于保存多个字符串元素，但集合不允许有重复元素，且元素无序，不能通过下标获取元素；Redis除了支持集合内部从增删改查，还支持多个集合的交、并、差。
1）命令

a)集合内操作

b)集合间操作

2）内部编码
　　intset(整数集合)，当集合中元素都是整数且元素个数小于set-max-inset-entries配置时采用，可以减少内存使用；
　　hashtable(哈希表)，无法满足intset条件时采用

1.5 有序集合

有序集保留了集合不能有重复成员的特性，同时对有序集合中的元素进行了排序。
1）命令

a)集合内

2）内部编码
　　ziplist(压缩列表)：当有序集合的元素个数小于zset-max-ziplist-entries配置(默认128)，同时每个元素的值都小于zset-max-ziplist-value配置，会采用ziplist来减少内存使用；
　　skiplist(跳跃表)：当ziplist条件不满足时采用；

1.6 键管理

1)单个键管理

2）遍历键
全量遍历键 keys pattern，
渐进式遍历 scan cursor [match pattern] [count number]
为解决keys命令存在的问题，采用渐进式遍历的方式来解决keys命令可能带来的阻塞问题，每次scan命令的时间复杂度为O(1)
cursor 是必须参数,是一个游标，每次遍历完会返回当前游标的值，从0开始，直到游标值为0遍历结束
match 是可选参数，作用是进行模式匹配
count number 是可选参数，作用是表明每次要遍历的键的个数，默认值为10，可适当增大；
即执行一次scan默认返回10个键和下一次scan需要的cursor，当返回的cursor=0，则所有的键均已经被遍历.

3）数据库管理

2.数据结构实现

2.1 简单字符串(simple dynamic string,SDS)

       Redis没有直接采用C语言传统的字符串表示，而是自己构造了简单动态字符串(SDS)的抽象类型作为默认字符串表示，embstr和raw都是基于此实现。每个sds.h/sdshdr结构表示一个SDS值：

 struct sdshde {
     //记录buf数组中已使用字节的数量
     //等于SDS所保存字符串的长度
    int len;
     //记录buf数组中未使用字节的数量
    int free;
     //字符串数组，用于保存字符串数组
    char buf[];
};

       SDS遵循C字符串以空字符'\0'结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性内，并且为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等都是SDS函数自动完成的。
SDS与C字符串的区别

2.2 链表

       当一个列表键包含过多元素/包含的元素较长时，Redis采用链表作为列表键的底层实现。 除了链表键外，发布与订阅、慢查询、监视器等也用到了链表，服务器本身还使用链表来保存多个客户端的状态信息。

typedef struct listnode{
       //前置节点
       struct listNode *prev;
       //后置节点
       struct listNode *next;
       //节点的值
       void *value;
};

       虽然仅仅使用多个listNode结构就可以组成链表，但使用adlist.h/list来持有链表更方便：

typedef struct list{
       //表头
       listNode *head;
       //表尾
       listNode *tail;
       //链表所包含的节点数
        unsigned long len;
       //节点复制函数
       void *(*dup)(void *ptr)
       //节点值释放函数
       void (*free)(void *ptr);
       //节点值对比函数
       void (*match) (void *ptr,void *key);
   }

Redis的链表实现特性：

2.3 字典

       字典用于保存键值对的抽象数据结构，同时字典也是哈希键的底层实现之一。Redis的字典采用哈希表作为底层实现，一个哈希表里面包含多个哈希表节点，一个哈希表节点代表一个键值对。
哈希表

typedef struct dictht {
    //哈希表数组,数组中元素指向一个dictEntry结构的指针,每个dictEntry结构保存一个键值对  
    dictEntry **table;
    //哈希表大小,即table数组的大小
    unsigned long size;
    //哈希表大小掩码,用于计算索引值 sizemask = size - 1;
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
}

哈希表节点

typedef struct dictEntry{
    // 键
    void *key;
    // 值,可以使一个指针、uint64_t整数或者int64_t整数
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    } v;
    // 指向下个哈希表节点，形成链表，将多个哈希值相同的键值对链接在一起，解决键冲突
    struct disEntry *next;
} dictEntry;

字典

typedef struct dict{
    //类型特定函数,指向dictType的指针,dictType结构保存了一簇用于操作特定类型键值对的函数  
    dictType *type;  
    //私有数据,保存了需要传给特定函数的可选参数  
    void *privdate;
    //哈希表,ht[0]即为哈希表,ht[1]只在rehash时使用
    dictht ht [2];
    //rehash索引,记录rehash目前的进度,当rehash不在进行时,值为-1;
    int rehashidx;
} dict;

typedef struct dictType{
    //计算哈希值
    unsigned int (*hashFunction) (const void *key);
    //复制键函数
    void *(*keyDup) (void *privdate, const void *key);
    //复制值的函数
    void *(*valDup) (void *privdate,const void *obj);
    //对比键的函数
   int (*keyCompare) (void *privdate,const void *key1, const void *key2);
    //销毁键的函数  
    void (*keyDestructor) (void *privdate,void *key);
    //销毁值的函数
    void (*valDestructor) (void *privdate,void *obj);
}

哈希算法
       根据键计算出哈希值和索引值，再根据索引值将包含键值对的哈希表节点放置到哈希表数组的指定索引上。
使用字典设置的哈希函数，计算键key的哈希值
hash = dict -> type -> hashFunction(key);
使用哈希表的sizemask属性和哈希值，计算出索引值

index = hash & dict->ht[x].sizemask

键冲突
       当有两个或以上数量的键被分配到哈希数组同一个索引上面时，键发生冲突；Redis哈希表采用拉链法解决键冲突。
渐进式rehash
       随着键值对的增多和减少，为维持负载因子(已保存节点数/哈希表大小)，需要对哈希表大小进行相应的扩展和收缩，如果直接将ht[0]的键值对rehash到ht[1]由于数据量过大可能对服务器性能造成影响。所以通过渐进式rehash分多次，将rehash键值对所需的工作平摊到字典的每个增删改查操作上，避免了集中式rehash带来的庞大计算量，步骤如下：

2.4 跳跃表

       跳跃表是一种有序数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。支持平均O(logN)，最坏O(N)的查找。跳跃表只在有序集合和集群节点内部数据结构中被用到， 通由跳跃表节点zskiplistNode和保存跳跃表节点信息的zskiplist两个结构定义。

zskiplist结构包含以下属性：

zskiplistNode结构包含以下属性：

2.5 整数集合

       整数集合(intset)是Redis用于保存整数值的集合抽象数据结构，保存类型为int16_t、int32_t和int64_t的整数值。

typedef struct intset {
    //编码方式
    uint32_t encoding;
    //集合包含的元素个数
    uint32_t length;
    //保存元素的数组,类型由encoding属性的值确定,元素从小到大排列，无重复元素
    int8_t contents[];
}

升级
       当添加新元素，且新元素类型比现有元素类型都长时，集合需要先进行升级：

       所以向整数集合添加新元素的时间复杂度为O(N),同时采用升级还能提升整数集合的灵活性，可以随意添加不同类型的整数而不用担心出现类型错误，也尽可能的节约了内存，升级操作只会在需要的时候进行，而不是一开始就预先分配大量的空间。
降级
       整数集合不支持降级，一旦对数组进行了升级，编码会一直保持升级后的状态。

2.6 压缩列表

       压缩列表是Redis为了节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型数据结构。

属性 类型 长度 用途
zlbytes uint32_t 4字节 记录整个压缩列表占用的内存字节数:内存重分配和计算zlend位置是使用
zltail uint32_t 4字节 记录压缩列表表尾阶段距离压缩列表起始地址有多少个字节
zllen uint16-t 2字节 记录压缩列表包含的节点数：如果大于65535则需要遍历计算
entryX 列表节点 不定 压缩列表包含的各个节点，节点长度由节点保存的内容决定
zlend uint8_t 1字节 特殊值0xFF，用于标记压缩列表的末端

压缩列表节点由previous_entry_length、encoding、content三部分组成：

连锁更新
       由于previous_entry_length属性都记录了前一个节点的长度，长度小于254字节用1字节空间记录否则用5字节空间，那么当一个压缩列表中有多个连续且长度介于250-253字节的节点，添加一个大于等于254字节的节点到头节点时，导致后续节点都需要空间重分配，扩展出4个字节构成5字节来记录前一节点的长度，进而自身超出254字节，引起了后续节点的连锁更新；在删除节点时也可能会导致连锁更新。

上一篇下一篇

猜你喜欢

热点阅读