Redis的数据类型

作者: Haalo | 来源:发表于2020-02-13 18:53 被阅读0次

关系型数据库和非关系型数据库

在绝大部分时候，我们都会首先考虑用关系型数据库来存储我们的数据，比如 SQLServer，Oracle，MySQL 等等。

关系型数据库

关系型数据库的特点:

它以表格的形式，基于行存储数据，是一个二维的模式。
它存储的是结构化的数据，数据存储有固定的模式(schema)，数据需要适应
表结构。
表与表之间存在关联。
大部分关系型数据库都支持 SQL(结构化查询语言)的操作，支持复杂的关联查
询。
通过支持事务(ACID 酸)来提供严格或者实时的数据一致性。

关系型数据库也存在一些限制:

要实现扩容的话，只能向上(垂直)扩展，比如磁盘限制了数据的存储，就要扩大磁盘容量，通过堆硬件的方式，不支持动态的扩缩容。水平扩容需要复杂的技术来实现，比如分库分表。
表结构修改困难，因此存储的数据格式也受到限制。
在高并发和高数据量的情况下，我们的关系型数据库通常会把数据持久化到磁盘，基于磁盘的读写压力比较大。

ACID，是指数据库管理系统（DBMS）在写入或更新资料的过程中，为保证事务（transaction）是正确可靠的，所必须具备的四个特性：原子性（atomicity，或称不可分割性）、一致性（consistency）、隔离性（isolation，又称独立性）、持久性（durability）。

非关系型数据库

为了规避关系型数据库的一系列问题，我们就有了非关系型的数据库，我们一般把它叫做“non-relational”或者“Not Only SQL”。NoSQL 最开始是不提供 SQL 的数据库的意思，但是后来意思慢慢地发生了变化。

非关系型数据库的特点:

存储非结构化的数据，比如文本、图片、音频、视频。
表与表之间没有关联，可扩展性强。
保证数据的最终一致性。遵循 BASE(碱)理论。 Basically Available(基本
可用); Soft-state(软状态); Eventually Consistent(最终一致性)。
支持海量数据的存储和高并发的高效读写。
支持分布式，能够对数据进行分片存储，扩缩容简单。

BASE理论：BASE是对CAP中一致性和可用性权衡的结果，其来源于对大规模互联网分布式系统实践的总结，是基于CAP定律逐步演化而来。其核心思想是即使无法做到强一致性，但每个应用都可以根据自身业务特点，才用适当的方式来使系统打到最终一致性。

Redis的数据类型

String
Hash
Set
Zset
List
Hyperloglog
Geo
Streams

Redis的存储结构

Redis 是 KV 的数据库，它是通过 hashtable 实现的(我们把这个叫做外层的哈希)。所以每个键值对都会有一个 dictEntry。里面指向了 key 和 value 的指针。next 指向下一个 dictEntry。

dictEntry

typedef struct dictEntry {
    void *key; /* key 关键字定义 */ 
    void *val;/* value 定义 */
    struct dictEntry *next;/* 指向下一个键值对节点 */
} dictEntry;

在每个dictEntry中，key 是以SDS存储，val则是以redisObject形式存储的。而redisObject存储实际值也是通过SDS存储的。

redisObject

typedef struct redisObject {
    unsigned type:4;/*类型*/
    unsigned encoding:4;/*编码*/
    // 对象最后一次被访问的时间(用于进行LRU算法)
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;/*引用计数 当 refcount 为 0 的时候，表示该对象已经不被任何对象引用，则可以进行垃圾回收了*/
    void *ptr;/*指向实际值的指针*/
} robj;

SDS是真正存储数据的结构，使用字符数组 char[]实现。
SDS的特点：

不用担心内存溢出问题，如果需要会对 SDS 进行扩容。
sdsMakeRoomFor()方法则可以对已有的sds进行扩容。
获取字符串长度时间复杂度为 O(1)，因为定义了 len 属性。
判断是否结束的标志是 len 属性。
通过“空间预分配”( sdsMakeRoomFor)和“惰性空间释放”，防止多次重分配内存。

SDS

struct __attribute__ ((__packed__)) sdshdr8 {
   uint8_t len; /* 获取字段长度 */
   uint8_t alloc;/*当前字符数组总共分配的内存大小 */
   unsigned char flags;/* 当前字符数组的属性、用来标识到底是 sdshdr8 还是 sdshdr16 等 */
   char buf[];/* 字符串真正的值 */

redis 存储结构

String

存储类型

可以用来存储字符串、整数、浮点数。

存储(实现)原理

字符串类型的内部编码有三种:
1、int，存储 8 个字节的长整型(long，2^63-1)。
2、embstr, 代表 embstr 格式的 SDS(Simple Dynamic String 简单动态字符串)，
存储小于 44 个字节的字符串。
3、raw，存储大于 44 个字节的字符串。

embstr和raw的区别

embstr 的使用只分配一次内存空间(因为 RedisObject 和 SDS 是连续的)，而 raw 需要分配两次内存空间(分别为 RedisObject 和 SDS 分配空间)。

embstr和raw 底层都是sdshdr结构体，但是在创建的时候只调用了一次zmalloc，而RAW编码则会调用两次。因此，EMBSTR是将redisObject和sdshdr存放到一块连续的内存空间中去了。

createRawStringObject

createEmbstriStringObject

因此与 raw 相比，embstr 的好处在于创建时少分配一次空间，删除时少释放一次空间，以及对象的所有数据连在一起，寻找方便。
而 embstr 的坏处也很明显，如果字符串的长度增加需要重新分配内存时，整个RedisObject 和 SDS 都需要重新分配空间，因此 Redis 中的 embstr 实现为只读。

Hash

存储类型

Hash 本身也是一个 KV 的结构,外层的哈希(Redis KV 的实现)只用到了 hashtable。当存储 hash 数据类型时，我们把它叫做内层的哈希。内层的哈希底层可以使用两种数据结构实现：ziplist 和 hashTable。

ziplist 压缩列表

Ziplist 是为了尽可能地节约内存而设计的特殊编码双端链表。它不存储指向上一个链表节点和指向下一个链表节点的指针，而是存储上一个节点长度和当前节点长度，通过牺牲部分读写性能，来换取高效的内存空间利用率，是一种时间换空间的思想。只用在字段个数少，字段值小的场景里面。ziplist在内存中是连续存储的，利用内存的连续性可以方便查找下一个节点，不需要和链表一样存储下一个节点的属性。

ziplist结构

ziplist

ziplist2

zlbytes ：是一个无符号整数，保存着 ziplist 使用的内存数量，通过这个值，程序可以直接对 ziplist 的内存大小进行调整。
zltail：保存着到达列表中最后一个节点的偏移量,这个偏移量使得对表尾的 pop 操作可以在无须遍历整个列表的情况下进行。
zllen: 保存着列表中的节点数量。

typedef struct zlentry {
unsigned int prevrawlensize; /* 上一个链表节点占用的长度 */
unsigned int prevrawlen;/* 存储上一个链表节点的长度数值所需要的字节数 */ 
unsigned int lensize; /* 存储当前链表节点长度数值所需要的字节数 */
unsigned int len;/* 当前链表节点占用的长度 */
unsigned int headersize;  /* 当前链表节点的头部大小(prevrawlensize + lensize)，即非数据域的大小 */ 
unsigned char encoding; /* 编码方式 */
unsigned char *p;/* 压缩链表以字符串的形式保存，该指针指向当前节点起始位置 */
} zlentry;

每个 ziplist 节点都包含两部分信息：

前置节点的长度，在程序从后向前遍历时使用。
当前节点所保存的值的类型和长度。

Hashtable结构(dict)

在 Redis 中，hashtable 被称为字典(dictionary)，它是一个数组+链表的结构。
Redis 的 KV 结构是通过一个 dictEntry 来实现的，而hashtable 是对这个dictEntry进行多层的封装。

dict--dictht--dictEntry

typedef struct dictEntry {
    void *key; /* key 关键字定义 */ 
    void *val;/* value 定义 */
    struct dictEntry *next;/* 指向下一个键值对节点 */
} dictEntry;

typedef struct dictht {
    dictEntry **table;/*哈希表数组*/
    unsigned long size;// 哈希表大小
    unsigned long sizemask; //哈希表大小掩码，用于计算索引值
    unsigned long used; // 该哈希表已有节点的数量

} dictht;

typedef struct dict {
    dictType *type; /* 字典类型 */
    void *privdata; /* 私有数据 */
    dictht ht[2]; /* 一个字典有两个哈希表 */
    long rehashidx; /* rehash 索引 */
    unsigned long iterators; /* 当前正在使用的迭代器数量 */
} dict;

Hashtable

dictht 后面是 NULL 说明第二个 ht 还没用到。dictEntry*后面是 NULL 说明没有 hash 到这个地址。dictEntry 后面是 NULL 说明没有发生哈希冲突。

为什么dict字典中有两个dictht结构呢？

redis 的 hash 默认使用的是 ht[0]，ht[1]不会初始化和分配空间。
哈希表 dictht 是用链地址法来解决碰撞问题的。在这种情况下，哈希表的性能取决于它的大小(size 属性)和它所保存的节点的数量(used 属性)之间的比率:

比率在 1:1 时(一个哈希表 ht 只存储一个节点 entry)，哈希表的性能最好;
如果节点数量比哈希表的大小要大很多的话(这个比例用 ratio 表示，5 表示平均
一个 ht 存储 5 个 entry)，那么哈希表就会退化成多个链表，哈希表本身的性能
优势就不再存在。
在这种情况下需要扩容。Redis 里面的这种操作叫做 rehash。
rehash 的步骤:

为字符 ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以
及 ht[0]当前包含的键值对的数量。
扩展:ht[1]的大小为第一个大于等于 ht[0].used*2。
将所有的 ht[0]上的节点 rehash 到 ht[1]上，重新计算 hash 值和索引，然后放
入指定的位置。
当 ht[0]全部迁移到了 ht[1]之后，释放 ht[0]的空间，将 ht[1]设置为 ht[0]表，
并创建新的 ht[1]，为下次 rehash 做准备。
什么时候触发扩容?:
负载因子ratio = used / size，已使用节点与字典大小的比例
dict_can_resize 为 1 并且 dict_force_resize_ratio 已使用节点数和字典大小之间的比率超过 1:5，触发扩容。

List

存储(实现)原理

quicklist

quicklist(快速列表)是 ziplist 和 linkedlist 的结合体。

typedef struct quicklist {
    quicklistNode *head; /* 指向双向列表的表头 */ 
    quicklistNode *tail; /* 指向双向列表的表尾 */
    unsigned long count;/* 所有的 ziplist 中一共存了多少个元素 */
    unsigned long len; /* 双向链表的长度，node 的数量 */
    int fill : 16;/* fill factor for individual nodes */
    unsigned int compress : 16; /* 压缩深度，0:不压缩; */
} quicklist;

quicklistNode 中的*zl 指向一个 ziplist，一个 ziplist 可以存放多个元素。

typedef struct quicklistNode {
struct quicklistNode *prev; /* 前一个节点 */
struct quicklistNode *next; /* 后一个节点 */
unsigned char *zl; /* 指向实际的 ziplist */
unsigned int sz; /* 当前 ziplist 占用多少字节 */
unsignedintcount:16;/* 当前ziplist中存储了多少个元素，占16bit(下同)，最大65536个*/ unsigned int   encoding : 2; /* 是否采用了 LZF 压缩算法压缩节点，1:RAW 2:LZF */
unsigned int   container : 2; /* 2:ziplist，未来可能支持其他结构存储 */
unsigned int   recompress : 1; /* 当前 ziplist 是不是已经被解压出来作临时使用 */
unsigned int   attempted_compress : 1; /* 测试用 */
unsigned int   extra : 10; /* 预留给未来使用 */
} quicklistNode;

list

Set

存储类型

String 类型的无序集合，最大存储数量 2^32-1(40 亿左右)。

存储(实现)原理

Redis 用 intset 或 hashtable 存储 set。如果元素都是整数类型，就用 inset 存储。如果不是整数类型，就用 hashtable(数组+链表的存来储结构)。

typedef struct intset {
    uint32_t encoding; // 编码方式
    uint32_t length; //集合包含的元素数量
    int8_t contents[];// 保存元素的数组
} intset;

ZSet 有序集合

存储类型

sorted set，有序的 set，每个元素有个 score。 score 相同时，按照 key 的 ASCII 码排序。

存储原理

同时满足以下条件时使用 ziplist 编码:

元素数量小于 128 个。
所有 member 的长度都小于 64 字节。
在 ziplist 的内部，按照 score 排序递增来存储。插入的时候要移动之后的数据。
超过阈值之后，使用 skiplist+dict 存储。
什么是 skiplist
skiplist.png
现在当我们想查找数据的时候，可以先沿着这个新链表进行查找。当碰到比待查数据大的节点时，再回到原来的链表中的下一层进行查找。比如，我们想查找 23，查找的路径是先从最上层进行查找。

23首先和7比较，再和19比较，比它们都大，继续向后比较。
但23和26比较的时候，比26要小，因此回到下面的链表(原链表)，与22
比较。
23比22要大，沿下面的指针继续向后和26比较。23比26小，说明待查数
据 23 在原链表中不存在。
在这个查找过程中，由于新增加的指针，我们不再需要与链表中每个节点逐个进行
比较了。需要比较的节点数大概只有原来的一半。这就是跳跃表。

Redis的数据类型

关系型数据库和非关系型数据库

关系型数据库

关系型数据库的特点:

关系型数据库也存在一些限制:

非关系型数据库

非关系型数据库的特点:

Redis的数据类型

Redis的存储结构

dictEntry

redisObject

SDS

String

存储类型

存储(实现)原理

embstr和raw的区别

Hash

存储类型

ziplist 压缩列表

ziplist结构

Hashtable结构(dict)

dict--dictht--dictEntry

为什么dict字典中有两个dictht结构呢？

List

存储(实现)原理

quicklist

Set

存储类型

存储(实现)原理

ZSet 有序集合

存储类型

存储原理

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Redis专题