redis data struct - yaokun123/php-wiki GitHub Wiki
redis的5种基本数据结构
Redis 有 5 种基础数据结构，它们分别是：string(字符串)、list(列表)、hash(字典)、set(集合) 和 zset(有序集合)。这 5 种是 Redis 相关知识中最基础、最重要的部分，下面我们结合源码以及一些实践来给大家分别讲解一下。
redis中所有的key最终都会被redis转换为string。
一、字符串 string
Redis 是用 C 语言开发完成的，但在 Redis 字符串中，并没有使用 C 语言中的字符串，而是用一种称为 SDS（Simple Dynamic String）的结构体来保存字符串。
SDS 与 C 字符串的区别:
- 1、常数时间内获得字符串长度
C 字符串本身不记录长度信息，每次获取长度信息都需要遍历整个字符串，复杂度为 O(n)；C 字符串遍历时遇到 '\0' 时结束。
SDS 中 len 字段保存着字符串的长度，所以总能在常数时间内获取字符串长度，复杂度是 O(1)。
- 2、避免缓冲区溢出
假设在内存中有两个紧挨着的两个字符串，s1=“xxxxx”和 s2=“yyyyy”。
由于在内存上紧紧相连，当我们对 s1 进行扩充的时候，将 s1=“xxxxxzzzzz”后，
由于没有进行相应的内存重新分配，导致 s1 把 s2 覆盖掉，导致 s2 被莫名其妙的修改。
但 SDS 的 API 对 zfc 修改时首先会检查空间是否足够，若不充足则会分配新空间，避免了缓冲区溢出问题。
- 3、减少字符串修改时带来的内存重新分配的次数
在 C 中，当我们频繁的对一个字符串进行修改（append 或 trim）操作的时候，需要频繁的进行内存重新分配的操作，十分影响性能。
如果不小心忘记，有可能会导致内存溢出或内存泄漏，对于 Redis 来说，本身就会很频繁的修改字符串，所以使用 C 字符串并不合适。
而 SDS 实现了空间预分配和惰性空间释放两种优化策略：
空间预分配：
当 SDS 的 API 对一个 SDS 修改后，并且对 SDS 空间扩充时，程序不仅会为 SDS 分配所需要的必须空间，还会分配额外的未使用空间。
分配规则如下：如果对 SDS 修改后，len 的长度小于 1M，那么程序将分配和 len 相同长度的未使用空间。
举个例子，如果 len=10，重新分配后，buf 的实际长度会变为 10(已使用空间)+10(额外空间)+1(空字符)=21。
如果对 SDS 修改后 len 长度大于 1M，那么程序将分配 1M 的未使用空间。
惰性空间释放：
当对 SDS 进行缩短操作时，程序并不会回收多余的内存空间，而是使用 free 字段将这些字节数量记录下来不释放，
后面如果需要 append 操作，则直接使用 free 中未使用的空间，减少了内存的分配。
- 4、二进制安全
在 Redis 中不仅可以存储 String 类型的数据，也可能存储一些二进制数据。
二进制数据并不是规则的字符串格式，其中会包含一些特殊的字符如 '\0'，在 C 中遇到 '\0' 则表示字符串的结束，
但在 SDS 中，标志字符串结束的是 len 属性。
string的定义如下：
sds.h
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 { //0 - 2^5 - 1
unsigned char flags; /* 3 lsb of type, and 5 msb of string length 前三个bit保存类型，后5个bit保存长度*/
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 { // 2^5 - 2^8 - 1
uint8_t len; /* used 用于记录 buf 中已使用空间的长度*/
uint8_t alloc; /* excluding the header and null terminator buf 中空闲空间的长度*/
unsigned char flags; /* 3 lsb of type, 5 unused bits 存储实际内容*/
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
//redis的value被封装如下
typedef struct redisObject {
unsigned type:4; //4 bit string,list,set,zset,hash
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 decreas time). */
int refcount;
void *ptr;//真实值的指针，当范围可用long long表示时候，就是真实的数据int
} robj
Redis 为了对内存做极致的优化，不同长度的字符串使用不同的结构体来表示。字符串的内部编码，Redis会根据当前值的类型和长度决定使用内部编码实现。
例如：执行命令 set key value，key 和 value 都是一个 SDS 类型的结构存储在内存中。
字符串类型的内部编码有3种：
int：8个字节的长整型。//节省内存，减少一次内存io
embstr：小于等于44个字节的字符串。cache line 64byte - redisObject:16byte = 48byte(sdshdr8(4bit) + data(44byte))
raw：大于44个字节的字符串。
注：Redis 规定了字符串的长度不得超过 512 MB。
二、列表 list
redis采用quicklist（双端链表）和ziplist作为list的底层实现。
可以通过设置每个ziplist的最大容量，quicklist的数据压缩范围，提升数据存取效率
list-max-ziplist-size -2 //单个ziplist节点最大能存储8kb，超过则进行分裂，将数据存储在新的ziplist节点上
list-compress-depth 1 //0代表所有节点，都不进行压缩，1代表从头节点往后走一个，尾节点往前走一个不用压缩，
//其他全部压缩，2，3，4，...以此类推
如果直接使用双向链表则需要使用两个指针prev,next占用16byte。如果元素比较多，这样的开销还是比较大的。
三、字典 hash
Hash数据结构的底层实现为一个字典(dict)，也是redisDb用来存储K-V的数据结构，当数据结构比较小，或者单个元素比较小时，底层用ziplist存储，数据大小和元素数量阀值可以通过如下参数设置
hash-max-ziplist-entries 512 //ziplist元素个数超过512，将改为hashtable编码
hash-max-ziplist-value 64 //单个元素大小超过64byte，将改为hashtable编码
四、集合 set
Set为无序的，自动去重的集合数据类型，Set数据结构的底层实现为一个value为null的字典(dict)，当数据可以用整型表示时，Set集合将被编码为intset数据结构，以下两个条件任意一个满足时Set将用hashtable存储数据
1、元素的个数大于set-max-intset-entries 512
2、元素无法用整形表示
set-max-intset-entries 512
intset能存储的最大元素个数，超过则用hashtableb编码
注意：intset是有序的，是整形数组。判断是否存在时候使用二分查找。
五、有序列表 zset
zset为有序的，自动去重的集合数据类型，zset数据结构底层实现为字典(dict)+跳表(skiplist)，当数据比较少时，用ziplist编码结构存储。
zset-max-ziplist-entries 128 //元素个数超过128，将用skiplist编码
zset-max-ziplist-value 64 //单个元素大小超过64byte，将用skiplist