redis 数据结构

实验版本：4.0 version


1. string[int, embstr, raw]

字符串的编码可以是int，raw或者embstr。

（1）int

当value是一个整数，并且可以使用long类型（8字节）来表示时，那么会属于int编码，ptr直接存储数值。


127.0.0.1:6379> set string_int 123
OK
127.0.0.1:6379> OBJECT encoding string_int
"int"

（2）普通的字符串有两种，embstr和raw。embstr对象用于存储较短的字符串，如果字符串对象的长度小于44字节，就用embstr对象。大于 44 字节  ，用的raw对象。



127.0.0.1:6379> set string_str bf2hwfh
OK
127.0.0.1:6379> OBJECT encoding string_str
"embstr"
127.0.0.1:6379> set string_str2 9hbff29fbiwhowi0fyqinf0w9flj0wejkbwufi2nfjosh80fn2kbv09wrjobsu9vbjwbf8wrkwh89tjobu9vwjfhisnflmsdngi0whkofbdsi9fh2ib80whfko2b8fbwjovh82rowd8v2nkfn80wnvkownv80wnfkohw0fnlksdhv80wnfkp
OK
127.0.0.1:6379> OBJECT encoding string_str2
"raw"
127.0.0.1:6379>

int

int 编码是用来保存整数值，raw编码是用来保存长字符串，而embstr是用来保存短字符串。其实 embstr 编码是专门用来保存短字符串的一种优化编码，

embstr和raw 编码

两种存储方式下，都RedisObject和SDS结构(简单动态字符串)来存储字符串，区别在于，embstr对象用于存储较短的字符串，embstr编码中RedisObject结构与ptr指向的SDS结构在内存中是连续的，内存分配次数和内存释放次数均是一次，而raw编码会分别调用两次内存分配函数来分别创建RedisObject结构和SDS结构。

2.set 无序集合[inset->hashtable]

Set是一个无序的，不重复的字符串集合，底层编码有inset和hashtable两种。


（1）inset
当元素都为整数，且元素个数较少时会使用inset作为底层编码，inset结构中的有一个contents属性，content是是一个整数数组，从小到大保存了所有元素。

Redis 的 intset 是一个紧凑的整数数组结构，它用于存放元素都是整数的并且元素个数较少的 set 集合。

如果整数可以用 uint16 表示，那么 intset 的元素就是 16 位的数组，如果新加入的整数超过了 uint16 的表示范围，那么就使用 uint32 表示，如果新加入的元素超过了 uint32 的表示范围，那么就使用 uint64 表示，Redis 支持 set 集合动态从 uint16 升级到 uint32，再升级到 uint64。

127.0.0.1:6379> sadd set_int 1 2 34 5 5
(integer) 4
127.0.0.1:6379> OBJECT encoding set_int
"intset"


 (2）hashtable
当元素个数较多时，Set使用hashtable来保存元素，元素的值作为key，value都是NULL。

127.0.0.1:6379> sadd set_str 135 2 53 f 6 t5 6y
(integer) 7
127.0.0.1:6379> OBJECT encoding set_str
"hashtable"
 

当集合同时满足以下两个条件时，使用 intset 编码：

1、集合对象中所有元素都是整数

2、集合对象所有元素数量不超过512

不能满足这两个条件的就使用 hashtable 编码。第二个条件可以通过配置文件的 set-max-intset-entries 进行配置。

3.list[quicklist]


Redis 早期版本存储 list 列表数据结构使用的是压缩列表 ziplist 和普通的双向链表 linkedlist，

也就是元素少时用 ziplist，元素多时用 linkedlist。


考虑到链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。
后续版本对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。


list的内部实现quicklist正是一个双向链表。在quicklist.c的文件头部注释中，是这样描述quicklist的：
它确实是一个双向链表，而且是一个ziplist的双向链表。

quicklist的每个节点都是一个ziplist。

quicklist 内部默认单个 ziplist 长度为 8k 字节，超出了这个字节数，就会新起一个 ziplist。
ziplist 的长度由配置参数list-max-ziplist-size决定。



127.0.0.1:6379> rpush list_test 1 2 3
(integer) 3
127.0.0.1:6379> OBJECT encoding list_test
"quicklist"
127.0.0.1:6379> rpush list_test 1 2 n3 o wfnkow
(integer) 8
127.0.0.1:6379> OBJECT encoding list_test
"quicklist"
127.0.0.1:6379>


4.zset[ziplist->skiplist]

有序集合对象的编码可以是ziplist或者skiplist。同时满足以下条件时使用ziplist编码：

(1)元素数量小于128个
(2)所有member的长度都小于64字节
以上两个条件的上限值可通过
zset-max-ziplist-entries
zset-max-ziplist-value
来修改。

ziplist编码的有序集合使用紧挨在一起的压缩列表节点来保存，第一个节点保存member，第二个保存score。ziplist内的集合元素按score从小到大排序，score较小的排在表头位置。


skiplist编码的有序集合底层是一个命名为zset的结构体，而一个zset结构同时包含一个字典和一个跳跃表。

 较少的时候是ziplist, 数量大的时候 是skiplist


127.0.0.1:6379> zadd zset_str 1 mysql
(integer) 1
127.0.0.1:6379> zadd zset_str 2 redis
(integer) 1
127.0.0.1:6379> zadd zset_str 3 es
(integer) 1
127.0.0.1:6379> OBJECT encoding zset_str
"ziplist"


127.0.0.1:6379> zadd zset_str 8 bjvbwjidbjiwobnwonwbcodwcowonononoknonkonkonoknkobojwdbcjbwcojwbcobdwjobwjbvjosbvokjwbvjkbhvwbifh92bfu9hbfjbfu92bfjb29ubfjowdbu2g39uh297ry9qubf92egfbe29ufgbe2ofg9e2ub9u2hf2fnw0gh2nfh02ini0hfo2kioty7384hnfh9hbfw9hf2nfi02i0
(integer) 1
127.0.0.1:6379> OBJECT encoding zset_str
"skiplist"

P:跳跃列表是根据score的值来进行快速查找的，但是我们一般得查询是通过key来进行查询的，那么zset是如何通过key来找到它多对应的score的呢？

有说是2个数据结构吗，查找是根据hash直接定位的，跳跃表使用的情况是按范围查找和算rank

当有序集合对象同时满足以下两个条件时，对象使用 ziplist 编码：

1、保存的元素数量小于128；

2、保存的所有元素长度都小于64字节。

不能满足上面两个条件的使用 skiplist 编码。以上两个条件也可以通过Redis配置文件zset-max-ziplist-entries 选项和 zset-max-ziplist-value 进行修改。

5.hash[ziplist->hasntable]


hash是Redis中可以用来存储一个对象结构的比较理想的数据类型。一个对象的各个属性，正好对应一个hash结构的各个field。


实际上，hash随着数据的增大，其底层数据结构的实现是会发生变化的，当然存储效率也就不同。
在field比较少，各个value值也比较小的时候，hash采用ziplist来实现；
而随着field增多和value值增大，hash可能会变成hashtable来实现。

当hash底层变成hashtable来实现的时候，它的存储效率就没法跟那些序列化方式相比了。

ziplist是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，相对于字典数据结构，压缩列表用于元素个数少、元素长度小的场景。其优势在于集中存储，节省空间。

当随着数据的插入，hash底层的这个ziplist就可能会转成dict。那么到底插入多少才会转呢？
hash-max-ziplist-entries 512
hash-max-ziplist-value 64


Redis的hash之所以这样设计，是因为当ziplist变得很大的时候，它有如下几个缺点：

a.每次插入或修改引发的realloc操作会有更大的概率造成内存拷贝，从而降低性能。
b.一旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更大的一块数据。
c.当ziplist数据项过多的时候，在它上面查找指定的数据项就会性能变得很低，因为ziplist上的查找需要进行遍历。


P:hash比string要节省内存吗？
我们在网上很容易找到这样一些技术文章，它们会说存储一个对象，使用hash比string要节省内存。
实际上这么说是有前提的，具体取决于对象怎么来存储。如果你把对象的多个属性存储到多个key上（各个属性值存成string），当然占的内存要多。
但如果你采用一些序列化方法，先把对象序列化为字节数组，然后再存入到Redis的string中，那么跟hash相比，哪一种更省内存，就不一定了。


（1）ziplist

元素保存的字符串长度较短且元素个数较少时(小于64字节，个数小于512)，出于节约内存的考虑，hash表会使用ziplist作为的底层实现，ziplist是一块连续的内存，里面每一个节点保存了对应的key和value，然后每个节点很紧凑地存储在一起，优点是没有冗余空间，缺点插入新元素需要调用realloc扩展内存。（可能会进行内存重分配，将内容拷贝过去，也可能在原有地址上扩展）。


（2）hashtable

元素比较多时就会使用hashtable编码来作为底层实现，这个时候RedisObject的ptr指针会指向一个dict结构，dict结构中的ht数组保存了ht[0]和ht[1]两个元素，通常使用ht[0]保存键值对，ht[1]只在渐进式rehash时使用。hashtable是通过链地址法来解决冲突的，table数组存储的是链表的头结点（添加新元素，首先根据键计算出hash值，然后与数组长度取模之后得到数组下标，将元素添加到数组下标对应的链表中去）



127.0.0.1:6379> OBJECT encoding hash_test
"ziplist"
127.0.0.1:6379> HmSET hash_test name uuu age 11 score 131
OK
127.0.0.1:6379> OBJECT encoding hash_test
"ziplist"



127.0.0.1:6379> HmSET hash_test name uuu age 11 score 131 mark gf8gbfg82bcwbfwb9bjdwfjh92hfjowdhf982hvh2hfh29hfowhf92hofh29ufnu2h0fnwh02nh2i0fni0n0ih2i0vn2i0hnfi02n0in0invini0vnwodnv0wnv0wnvnw0invowbv0nwi0fnwkonvinvoh2hkoe2hth2i0nf02en20nfw0nfiowhvnsi0n2kvi0wu0jni0nvi0nw
OK
127.0.0.1:6379> OBJECT encoding hash_test
"hashtable"

127.0.0.1:6379>

参考资料：《Redis设计与实现》