[大数据]redis——基础数据结构

前言

redis中每个键值对都是由对象组成，其中：

1. 数据库Key总是一个字符串对象
2. 数据库Value的值对应有五种基本数据结构，分别为：String(字符串)、list(列表)、hash(字典)、set(集合)，zset(有序集合)

1、键和值用什么结构组织？

1. redis使用哈希表来存储所有的键值对对数据，因为值的结构有多种，所以哈希桶中的元素保存的不是值本身，而是指向具体值的指针。

2. 在上图redis使用哈希表来存储数据，那么当写入数据多了，产生Hash冲突了，怎么解决？

redis会采用拉链法解决hash冲突，同一个哈希桶中的多个元素通过指针链接起来。

3. 但是这种随着数据写入的增多会导致冲突链过长，导致某个链上的元素查找耗时变长，怎么解决？

一般会对原Hash表进行扩容，再进行数据搬迁如hashMap，但是这个过程涉及到大量数据的拷贝，如果一次性把全部数据迁移完成，会造成redis线程的阻塞，无法服务其他请求。所以redis采用了渐进式rehash，这个后续讲hash结构会对实现进行分析。

2、值对应的基本数据类型

值对应有五种基本数据结构，分别为：String(字符串)、list(列表)、hash(字典)、set(集合)，zset(有序集合)

2.1、String(字符串)

String内部表示就是一个字符数组，它是自己构建一种名为SDS(简单动态字符串)的抽象类型，内部结构类似Java的ArrayList，采用预分配空间来减少内存的频繁分配，当字符串小于1MB时，扩容都是扩容2倍，当字符串长度超过1MB，扩容至多只会扩容1MB，字符串的最大长度为512MB

优点：

• sds结构体中存在一个属性记录长度，所以可以O(1)复杂度获取字符长度，因为有字段记录长度，还可以杜绝缓冲区溢出，redis可以根据剩余空间判断是否满足传入的大小，不满足则进行扩容。
• 通过空间预分配机制和惰性释放，可以避免在字符串长度变更的时候频繁的进行内存的申请。
• 二进制安全，因为有len属性的值来判断字符串是否结束，而不是\0

2.2、list(列表)

redis的列表相当于Java中的LinkedList，采用双向链表实现，每个元素都适用双向指针串起来。

1. 但是链表实现的列表虽然元素的插入和删除是O(1),但是查找元素的时间复杂度是O(n)，这个怎么解决？

在列表元素较少的情况下，会使用一块连续的内存存储，这个接口就是zipList(压缩列表)，这个时候所有元素存储在一起，分配的是一块连续的内存，当数据量比较多的时候才会改成quickList。

2. 压缩列表结构

压缩列表类似一个数组，数组中的每个元素对应的一个数据，和数组不同的是压缩列表在数组头部有三个字段zlbytes、zltail和zllen，表示列表长度、列表尾的偏移量和列表中entry个数，尾部还有一个zlend表示列表结束。zipList默认大小8KB

优点：元素紧凑，节省内存，不需要维护额外的两个指针prev和next
缺点：

1. 因为ziplist是紧凑存储的，没有冗余空间，所以插入一个元素就需要调用realloc扩展内存，可能会重新分配新的内存空间，如果ziplist占据内存过大，重新分配内存和拷贝内存就会有很大开销，所以ziplist不适合存储太多字符串，存储的元素不宜过多。
2. 在上面每个entry元素会有一个prevlen字段存储前一个entry的长度，如果内容小于254字节，prevlen就用1字节存储，否则用5字节，如果其中一个entry发生修改了从253字节变成254字节，那么它下个entry的prevlen字段就要更新，从1字节扩展到5字节，如果下个entry加了4字节也超过了254字节，那么就会级联下去。或者删除其中某个entry就会导致需要级联修改prevlen。

3.快速链表结构

这里优化了原有的双向链表，而是采用数组+链表的结合体，把linkedList按段切开，每一段使用zipList存储，多个zipList使用双向指针链接起来。

2.3、hash(字典)

redis中的hash表相当于java中的HashMap，使用数组+链表的结构存储，当出现hash冲突的时候，采用拉链法解决冲突。

1. hash表元素过多的时候，在进行rehash的时候就会非常耗时，需要新申请一个数组，然后做元素的迁移，而redis又是一个单线程的，那么redis怎么避免在rehash的时候阻塞主线程？

redis采用渐进式rehash，来避免全量迁移阻塞住线程。

2. 渐进式rehash实现原理

字典结构内部包含两个hashtable，在不做rehash的时候只有ht[0]是有值的，在字典扩容的时候，需要分配新的hashtable，这个时候就会存在两个hashtable，然后慢慢进行渐进式搬迁。
搬迁流程：

1. 后续对hash表操作的指令(如hset,hdet指令)则在执行指令的时候会执行搬迁操作
2. 为了防止客户端后续可能不会执行指令，redis还会有一个定时任务，100ms执行一次，会对hash表进行主动搬迁。
3. 在rehash的时候会维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在 rehashidx索引(table[rehashidx]桶上的链表)上的所有键值对rehash到ht[1]上，当rehash工作完成之后，将rehashidx属性的值增一，表示下一次要迁移链表所在桶的位置。

3. 如果现在处于rehash过程中，这个时候的查询命令应该怎么执行?

这里如果是新增数据的话那么可以直接新增到ht[1]中，但是如果是查询或者删除语句的话，那么就不知道数据存在ht[1]还是ht[1]中，所以在查找的时候会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找。

4. hash表扩容和缩容条件?

1.扩容条件： 当hash表中的元素的个数等于第一维数组的长度时，就会开始扩容，扩容的新数组是原数组大小的2倍，如果redis正在做bgSave，那么为了防止迁移导致内存页的过多拷贝(CopyOnWrite)，redis尽量不回去扩容，但如果元素个数已经达到了数组长度的5倍，会强制进行扩容。
2. 缩容条件：当元素个数低于数组长度的10%，则会进行缩容量，缩容不会考虑是否在做bgsave，这里为什么不需要考虑bgsave，可能因为由于申请的内存比较小，同时会释放掉一些已经使用的内存，不会增大系统的压力。因此不用考虑是否在进行 BGSAVE 操作。而且缩减的过程不用重新申请内存，内存已经是使用过的，而且指针原来指向的二维链表部分，可以直接置空，后续交给系统进行回收。

2.4、set(字典)

redis里面的set实现也是通过字典结构实现的，所有的value是NULL，这个和java中的HashSet一致。

2.5、zset(字典)

zset是一个复合结构，一方面它需要一个hash结构来维护value和score的对应关系，另一方面需要提供按照score排序的功能，还需要根据score的范围来获取value列表，这个有序结构可以使用红黑树或者跳表，redis使用跳表来进行实现

1. 跳表结构剖析

因为字典上述已经讲过了，所以这里具体讲解skipList的实现原理
我们知道存储score，一定会使用一个有序结构来存储，如果使用数组存储，那么在进行删除或者增加元素的时候时间复杂度就是O(n)了，如果使用链表结构存储，那么就不能像有序数组在查找的时候可以进行二分。而跳表可以做到查找和添加删除的复杂度都是O(lg(n))，具体是在链表之上构建多级索引来实现的。

这里不再赘述跳表的查询和删除流程，想看点如下链接。
跳表原理分析

2. 跳表的随机层数

跳表在每次插入新元素的时候都要通过随机算法分配一个合理的层数，这样是为了避免查找退化成O(n)，如果插入元素不更新索引，那么就会导致索引结构不均匀，存在偏差，在元素插入多的情况下，索引就不起效果了。所以能维持logN的复杂度，随机函数也至关重要
对新节点来说，存在50%的概率被分配到l1,25%的概率被分配到l2,12.5%的概率分配到l3…,2^-63概率被分到最顶层(reids跳表的层数一共有64层)

3. 如果zset中的值的score值都一样，查找性能会退化成O(n)么？

zset排序元素时不只看score值，如果score值相同的话则会再比较vlaue值(字符串字典序比较)

总结

redis内部设计了多种数据结构，且针对不同大小的对象使用不同的数据结构存储，把内存和性能利用到了极致。大家有时间也可以看下下面这篇文章，看微博针对自己的业务场景设计不同的数据结构，来最大化利用内存和性能。
微博redis实践场景