Redis(三). Redis数据类型
在上面的两个章节中，介绍了Redis内部的数据结构的底层实现；这两类实现构成了Redis对外支持的数据结构；Redis的机制是在使用内存较少的时候使用内存的数据结构，当数据量到达一定量的时候，就是演变成第一章使用的数据结构；
1. 对象处理机制
特定命令针对特定的数据结构，LPUSH 和 LLEN 只能用于List， SADD 和 SRANDMEMBER 只能用于Set
Redis 必须让每个键都带有类型信息，使得程序可以检查键的类型，并为它选择合适的处理方式；
Redis 的一个键的数据类型，可能有不同的底层实现，Redis 内存称之为编码encoding,所以说，Redis在处理键的时候，会根据键的编码方式，执行不同的方法；
Redis 构建了自己的类型系统，这个系统的主要功能包括
? redisObject 对象。
? 基于 redisObject 对象的类型检查。
? 基于 redisObject 对象的显式多态函数。
? 对 redisObject 进行分配、共享和销毁的机制。
1.1 redisObject (最新版)
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;
/* The actual Redis Object */
#define OBJ_STRING 0 /* String object. */
#define OBJ_LIST 1 /* List object. */
#define OBJ_SET 2 /* Set object. */
#define OBJ_ZSET 3 /* Sorted set object. */
#define OBJ_HASH 4 /* Hash object. */
/* Objects encoding. Some kind of objects like Strings and Hashes can be
* internally represented in multiple ways. The 'encoding' field of the object
* is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0 /* Raw representation */
#define OBJ_ENCODING_INT 1 /* Encoded as integer */
#define OBJ_ENCODING_HT 2 /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3 /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6 /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
#define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */
ptr 是一个指针，指向实际保存值的数据结构，这个数据结构由 type 属性和 encoding 属性决
定。
Redis 各种数据类型，以及它们的数据结构（编码方式）
1.2 命令的类型检查和多态
当执行一个处理数据类型的命令时，Redis 执行以下步骤：
- 根据给定 key ，在数据库字典中查找和它像对应的 redisObject ，如果没找到，就返回NULL 。
- 检查 redisObject 的 type 属性和执行命令所需的类型是否相符，如果不相符，返回类型错误。
- 根据 redisObject 的 encoding 属性所指定的编码，选择合适的操作函数来处理底层的数据结构。
- 返回数据结构的操作结果作为命令的返回值。
1.3 对象共享
一些对象在 Redis 中非常常见，比如命令的返回值 OK 、ERROR 、WRONGTYPE 等字符，另外，一些小范围的整数，比如个位、十位、百位的整数(参考Java Integer) ，Redis 在内部使用了一个 Flyweight 模式 ,多个数据结构之间共享这些对象
共享对象只能被字典和双端链表这类能带有指针（可以指向字面量）的数据结构使用；像整数集合和压缩列表这些只能保存字符串、整数等字面值的内存数据结构，就不能使用共享对象(因为保存的本身就是字面量)；
1.4 引用计数以及对象的销毁
redisObject 中字段refcount 表示被引用多少次，创建时为1，共享时+1，取消共享-1 ，0时 释放；
1.5 总结
- 一种 Redis 类型的键可以有多种底层实现。
2. 字符串 REDIS_STRING
2.1 字符串编码
字符串类型分别使用 REDIS_ENCODING_INT 和 REDIS_ENCODING_RAW 两种编码：
-
REDIS_ENCODING_INT 使用 long 类型来保存 long 类型值。
-
REDIS_ENCODING_RAW 则使用 sdshdr 结构来保存 sds （也即是 char* )、long long 、double 和 long double 类型值。
在 Redis 中，只有能表示为 long 类型的值，才会以整数的形式保存，其他类型的整数、小数和字符串，都是用 sdshdr 结构来保存
2.2 编码选择
创建的时候使用REDIS_ENCODING_RAW ，尝试将字符串转为 REDIS_ENCODING_INT 编码。
3. 哈希表 REDIS_HASH
3.1 哈希表编码
REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_HT 两种编码方式
3.2 字典编码的哈希表
当哈希表使用字典编码时，程序将哈希表的键（key）保存为字典的键，将哈希表的值（value）保存为字典的值。
3.3 压缩列表编码的哈希表
键和值一同推入压缩列表，从而形成保存哈希表所需的键 -值对结构
3.4 编码的选择
默认使用 REDIS_ENCODING_ZIPLIST 编码，下面条件之一就切换REDIS_ENCODING_HT
- 某个键或某个值的长度大于 server.hash_max_ziplist_value （默认值为 64）
- 压缩列表中的节点数量大于 server.hash_max_ziplist_entries （默认值为 512 ）
4. 列表 REDIS_LIST
4.1 列表的编码
REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_LINKEDLIST 两种方式编码
4.2 编码的选择
默认使用 REDIS_ENCODING_ZIPLIST 编码，当以下任意一个条件被满足时，列表会被转换成 REDIS_ENCODING_LINKEDLIST 编码
-
添加一个字符串到列表，字符串超过server.list_max_ziplist_value （默认值为 64 ）。
-
ziplist 包含的节点超过 server.list_max_ziplist_entries （默认值为 512 ）。
4.3 列表命令的实现
命令几乎就是通过一对一地映射到底层数据结构的操作来实现的；
但是呢，List 有几个阻塞的命令 下面看看是如何实现的；
4.3 阻塞命令
BLPOP 、BRPOP 和 BRPOPLPUSH 三个命令都可能造成客户端被阻塞，以下将这些命令统称为列表的阻塞原语，命令执行机制
- 列表为空
- 不为空的话 执行无阻塞版本的 LPOP 、RPOP 或 RPOPLPUSH 命令。
4.4 阻塞
阻塞时 ，也就是列表为空
1.客户端标记为 阻塞中 ，记录客户端的阻塞键，和最timeout；
2.信息记录到 server.db[i]->blocking_keys 中 （i是选择的数据库）； key1~n 是被阻塞的客户端，key1 阻塞的客户端有多个
3.维持连接，不发数据，保持阻塞；
4.5 脱离阻塞
脱离阻塞状态有以下三种方法
- 被动脱离：有其他客户端为造成阻塞的键推入了新元素
- 主动脱离：到达执行阻塞原语时设定的最大阻塞时间 timeout
- 强制脱离：客户端强制终止和服务器的连接，或者服务器停机
插入数据
实例 阻塞blocking_keys 如下
这个时候 PUSH key3 value,将 readyList 添加到服务器 ,新元素 value 添加到键 key3
解除阻塞
- server.ready_keys 不为空，那么弹出该链表的表头元素，并取出元素中的readyList 值
- readyList 值所保存的 key 和 db ，在 server.blocking_keys 中查找所有因为 key而被阻塞的客户端（以链表的形式保存）
- 如果 key 不为空，那么从 key 中弹出一个元素，并弹出客户端链表的第一个客户端，然后将被弹出元素返回给被弹出客户端作为阻塞原语的返回值
- readyList 结构的属性，删除 server.blocking_keys 中相应的客户端数据，取消客户端的阻塞状态。
- 继续执行步骤 3 和 4 ，直到 key 没有元素可弹出，或者所有因为 key 而阻塞的客户端都取消阻塞为止
- 继续执行步骤 1 ，直到 ready_keys 链表里的所有 readyList 结构都被处理完为止；
4.6 先阻塞先服务
上图中的key3 后面阻塞了三个客户端，keys 添加了三个value 的时候，一定是client3 ,client34，client6 按照先后顺序来解除阻塞状态；
4.7 timeout 取消阻塞
Redis 服务器常规操作函数（server cron job）执行时；检查阻塞状态的客户端，判断是否超过了timeout ，如果是，给客户端空白回复；取消阻塞；
5. 集合 REDIS_SET
5.1 集合的编码
REDIS_ENCODING_INTSET 和 REDIS_ENCODING_HT 两种方式编码
5.2 编码的选择
添加到集合的元素，决定了创建集合时所使用的编码
-
如果第一个元素可以表示为 long long 类型值（也即是，它是一个整数），那么集合的初始编码为 REDIS_ENCODING_INTSET 。
-
否则，集合的初始编码为 REDIS_ENCODING_HT 。
5.3编码的切换
REDIS_ENCODING_INTSET 切换为REDIS_ENCODING_HT
- 个数超过 server.set_max_intset_entries （默认值为 512 ）
- 添加一个新元素，并且这个元素不能被表示为 long long 类型
5.4 使用字典编码的集合
REDIS_ENCODING_HT 编码时，集合将元素保存到字典的键里面，而字典的值则统一设为 NULL，(类似于JavaHashSet利用 HashMap的key来实现 )
6.有序集 REDIS_ZSET
6.1 编码方式
REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_SKIPLIST 两种方式编码
6.2 编码的选择
依据第一的元素来做初始化的类型 条件之一符合 创建 REDIS_ENCODING_ZIPLIST 编码的有序集
- 服务器属性 server.zset_max_ziplist_entries 的值大于 0 （默认为 128 ）。
- 元素的 member 长度小于服务器属性 server.zset_max_ziplist_value 的值（默认为 64）
6.3 编码的切换
REDIS_ENCODING_ZIPLIST 编码的有序集，只要满足以下任一条件，就将它转换为REDIS_ENCODING_SKIPLIST 编码
- ziplist 所保存的元素数量超过服务器属性 server.zset_max_ziplist_entries 的值（默认值为 128 ）
- 新添加元素的 member 的长度大于服务器属性 server.zset_max_ziplist_value 的值（默认值为 64 ）
6.4 ZIPLIST的有序集
6.5 SKIPLIST 编码的有序集
zset 同时使用字典和跳跃表两个数据结构来保存有序集元素。 (数据双写)
通过使用字典结构，并将 member 作为键，score 作为值，有序集可以在 O(1) 复杂度内：
-
检查给定 member 是否存在于有序集（被很多底层函数使用）；
-
取出 member 对应的 score 值（实现 ZSCORE 命令）。另一方面，
通过使用跳跃表，可以让有序集支持以下两种操作：
-
在 O(log N) 期望时间、O(N) 最坏时间内根据 score 对 member 进行定位（被很多底层函数使用）；
-
范围性查找和处理操作，这是（高效地）实现 ZRANGE 、ZRANK 和 ZINTERSTORE等命令的关键。
