关系型数据库和非关系型数据库
在绝大部分时候，我们都会首先考虑用关系型数据库来存储我们的数据，比如 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[];/* 字符串真正的值 */
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存放到一块连续的内存空间中去了。
因此与 raw 相比，embstr 的好处在于创建时少分配一次空间，删除时少释放一次 空间，以及对象的所有数据连在一起，寻找方便。
而 embstr 的坏处也很明显，如果字符串的长度增加需要重新分配内存时，整个RedisObject 和 SDS 都需要重新分配空间，因此 Redis 中的 embstr 实现为只读。
Hash
存储类型
Hash 本身也是一个 KV 的结构,外层的哈希(Redis KV 的实现)只用到了 hashtable。当存储 hash 数据类型时， 我们把它叫做内层的哈希。内层的哈希底层可以使用两种数据结构实现：ziplist 和 hashTable。
ziplist 压缩列表
Ziplist 是为了尽可能地节约内存而设计的特殊编码双端链表。它不存储指向上一个链表节点和指向下一 个链表节点的指针，而是存储上一个节点长度和当前节点长度，通过牺牲部分读写性能， 来换取高效的内存空间利用率，是一种时间换空间的思想。只用在字段个数少，字段值小的场景里面。ziplist在内存中是连续存储的，利用内存的连续性可以方便查找下一个节点，不需要和链表一样存储下一个节点的属性。
ziplist结构
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;
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;
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 在原链表中不存在。
在这个查找过程中，由于新增加的指针，我们不再需要与链表中每个节点逐个进行
比较了。需要比较的节点数大概只有原来的一半。这就是跳跃表。
