本文主要是介绍Redis之数据结构原理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、Redis是单线程的吗？（面试题）

　　1.Redis是单线程的，Redis是指处理用户请求的线程是单线程，请求过程：获取 (socket 读)、解析、执行、内容返回 (socket 写)。

　　2.Redis还有后台任务线程，例如定时删除过期key线程、AOF持久化策略刷盘、异步删除大key（unlink命令）的内存清理等。

　　3.多个db之间也是共享的单线程（db之间是相互影响的）。

 

二、Redis的数据结构

String
String 是 Redis 的基础数据类型，redis 没有 int Float ，Boolean 等数据类型的概念，所有的基本类型在Redis 都可以通过String 体现
String的 常用命令

• set 为一个 key 设置 value，可以配合 ex/px 参数指定key 的有效期，通过nx/xx 参数对key 是否存在的情况进行区别操作，时间复杂度为 O(1)
• get 获取 key 对应的 value 时间复杂度为 O(1)
• getset 为一个key 设置value 并返回key 的原 value ，时间复杂度为 O(1)
• mset 为 多个 key 设置 value ，时间复杂度为 O(n)
• msetnx 同 mset ，如果指定的key 中有任意一个已经存在，则不进行任何操作，时间复杂度为 O(n)

List
redis 的 list 是链表型的数据结构，可以使用 lpush、rpush、lpop、rpop 等命令在List 的两端执行插入和移除元素操作， List 而已支持在特定的 index 上插入和读取元素的功能，但是其时间复杂度就比较高里的，谨慎使用。

• lpush 向指定 List 的左侧（也就是头部）插入一个或者多个元素，返回插入一户list 的长度，时间复杂度为 O(n),n 为插入元素的数量
• rpush 向 List 的的右侧，也就是尾部，插入一个或者多个元素
• lpop 是从 List 的头部移除一个元素，就是取最后面添加的元素，并返回该元素，时间复杂度为 O(1)
• rpop 从 List 的尾部移除一个元素并返回
• lpushx、rpushx 和 lpush rpush 类似，区别就是，如果 操作的 key 不存在，则不会进行任务号的操作
• llen 是返回 指定list 的长度，时间复杂度为 O(1)
• lrange 返回指定 list 中 指定范围的元素，时间复杂度为 O(n), 这个命令要控制获取 list 元素的个数，太大会导致 redis 延迟响应，另外对于不可预知长度的list 禁止 lrange key 0 -1 这样的遍历操作。
• 注意 谨慎使用 命令 lindex 返回指定的下标的元素，如果下标越界 返回 nil， index 数值是回环的，也就是说 -1 代表最后一个位置，-2 代表倒数第二个位置，该命令的时间复杂度为 O(n) ; lset 命令将指定 list 指定 index 的元素设置为 value ,如果下标越界，则返回错误，其时间复杂度为 O(n),操作 首尾的话 复杂度为 O(1); linsert 向指定 List 中指定元素之前或者之后添加一个新元素，并返回操作后的list长度，如果指定的元素不存在，返回 -1，如果指定的 key 不存在，则不进行任何操作 ，时间复杂度也为 O(n)

Hash
哈希表，redis 的hash 和传统的 hash 一样，是一种 field-value 的数据结构，Hash 适合用于表现对象类型的数据， hash 中的 field 对应 对象的 field 即可。
Hash 的优点包括

1. 可以实现二元查询
2. 比起将整个对象序列化后作为String 存储，hash 能够有效的减少网络传输的消耗
3. 当使用 hash 维护一个集合的时候，提供了比 List 效率更高的随机访问命令

与Hash 相关常用的命令

• hset 将key 对应的 Hash 中的 field 设置为 value ，如果该 hash 不存在，则会自动创建一个 时间复杂度为 O(1)
• hget 返回指定Hash 中 field 字段的值，时间复杂度为 O(1)
• hmset/hmget 和 hset 和 hget 类似，可以批量操作同一个key 下的多个 field，jedis 中你可以 使用一个key 存储一个 map对象进去，其时间复杂度是 O(n),n为一次操作的 field 的数量
• hsetnx 通 hset 如果 field 存在，则不会进行任何的操作，O(1) 复杂度
• hexists 是否存在 field，存在返回 -1 ，不存在返回0  O(1)复杂度
• hdel 删除指定 hash 中的 field （一个或者 多个），时间复杂度为O(n),n为操作的 field 数量
• hincrby 同 incrby ，对指定Hash 中的 field 进行 incrby 操作，O(1) 复杂度
  需要谨慎使用的命令
• hgetall 返回指定hash中所有的 field-value，返回结果是数组，数组中field 和value 交替出现，O(n) 复杂度
• hkeys/hvals 返回指定 Hash 中 所有的 field/value O(n) 复杂度。
  上面 3 个命令都会将 hahs 整个遍历，尽量使用 hscan 进行游标式遍历。

Set
redis set 是无序的，不可重复的String 集合
与 set 相关常用命令

• sadd 向指定的 set 中添加一个或者多个 member ，如果指定的set 不存在，自会自动创建一个，时间复杂度为 O(n),n 为添加的个数
• srem 从指定的 set 移除 1 个或者多个 member，时间复杂度为O(n), n为返回的member个数
• srandmember 从指定的set 随机返回 1 个或者多个 member ，时间复杂度为 O(n), n为返回的member 的个数
• spop 从指定的set 移除并返回 n个 member 时间复杂度为 O(n)，n为移除的member的个数
• scard 返回指定 set 中 member的格式 ，时间复杂度为O(1)
• sismember 判断指定的 value 是否存在于指定的 set 中，时间复杂度为O(1)
• smove 将指定的member 从一个 set 移动到另外的 set

　慎用的set 命令

　　smembers 返回指定 hash 中所有的 member ，O(n)
　　sunion / sunionstore 计算多个 set 的并集并返回/存储到另外一个 set 中，O(n)
　　sinter/sinterstore 计算多个set 的交集并返回/ 存储至另外一个set 中，O(n)
　　sdiff / sdiffstore 计算 1 个 set 与 1 个或者多个 set 的并集并返回存储到另外的 set 中，O(n)

　上面的几个命令计算量大，特别是在 set 尺寸不可知的情况下，避免使用，可以考虑 sscan 命令遍历获取相关的 set 的全部 member 。

其他命令

 exists 　　　　　　判断是否存在某个 key  存在 返回 1，不存在 返回 0  O(1)
 del 　　　　　　　　　　删除指定 key 及其对应的  value ，时间复杂度为 O(n) , n 为删除 key 的数量
 expire/pexpire 　　　　为一个 key 设置有效期，单位为 秒 或者 毫秒，时间复杂度为 O(1)
 TTL/PTTL  　　　　　　  返回一个 key 的有效时间，单位为秒或者毫秒。O(1)
 rename / renamenx 　　将 key 重命名为 newkey，使用 rename 时候，如果 newkey 已经
 　　　　　　　　　　　　　　存在其值会被覆盖 ，使用 renamenx 时，如果 newkey 已经存在，则不会进行任何的操作。O(1)
 type 　　　　　　　 返回 key 的类型，O(1)
 config get  　　  获得 redis 某配置项当前的值，可以使用 * 通配符 O(1)
 config set 　　　 为 redis 某配置项设置新值，时间复杂度为 O(1)
 config rewrite 　让 redis 重新加载 redis.conf 的配置 
 

　　

三、分布式缓存写缓写步骤/失效步骤

　　写缓存：先查询缓存是否存在，再决定是否需要写入缓存

 

 

　　失效缓存：写缓存的时候指定失效时间；删/改-删除缓存

 

 

四、常见的缓存问题

》缓存穿透：指缓存和数据库中都没有的数据，而用户不断发起请求，造成数据库压力过大（攻击手段）

 

　解决办法1-缓存空值：针对数据库不存在值也缓存

　　优点：简单 缺点：攻击者可以短时间不断更换查询id，把Redis内存占满。

　解决办法2-布隆过滤器：一种用于“检索一个元素是否在一个集合中”高效的占用空间小的数据结构 特点：存在一定的错误率（返回true不一定存在，但返回false一定不存在）

　　优点：有效 缺点：麻烦，适用场景上要求数据不得删除

　解决办法3：（推荐）两者一起使用，先通过“布隆过滤器”，再针对返回false的查询，缓存空。

 

》缓存击穿：缓存中没有但数据库中有的数据（一般是缓存时间到期），这时由于并发用户特别多，同时读缓存没读到数据，又同时去数据库去取数据，引起数据库压力瞬间增大，造成过大压力。

 

 

　解决方案1：热点数据永不过期

　解决方案2：写缓存时加锁，同一时间只能有一个线程查询数据库更新缓存，其他线程阻塞等待(Spring Cache支持)

 

 

》缓存雪崩：由于原有缓存失效（缓存集中失效、Redis宕机等种种原因），所有原本应该访问缓存的请求都去查询数据库了，而对数据库CPU和内存造成巨大压力，严重的会造成数据库宕机。从而形成一系列连锁反应，造成整个系统崩溃。 特点：缓存击穿是针对某一条缓存，缓存雪崩是针对缓存整体；缓存雪崩主要体现在连锁反映上

　

　解决方案1：缓存不集中失效（一般情况下天然打散）

　解决方案2：缓存预热，针对可预先知道的查询数据进行预热，定时刷新缓存（例如秒杀商品）

　解决办法3：提前预案-缓存降级，（1）两台Redis热备；（2）降级为本地缓存

 

五、分布式锁

  分布式锁：保证在分布式系统中对于同一共享资源，同时只有一个线程在操作。

  Redis实现分布式锁的方式：

　　方案1： setnx + expire

　　　　获取锁：set ${lockKey} ${lockValue} setnx：

　　　　　　setnx指令，SET if Not eXists，如果不存在则设置成功；

　　　　　　expire：设置超时时间

　　　　释放锁：del ${lockKey}

　　　　缺点：

　　　　　　 获取锁：setnx与expire不是原子的，setnx后程序宕机，那么此锁永远得不到释放。

　　　　　　释放锁：直接del操作，有可能释放了不属于当前线程的锁，造成更多的问题。（线程1获取锁成功，但是运行超时，锁已过期；线程2抢占成功；线程1运行完成之后，本不该释放锁，直接del把线程2的锁给释放掉了）

 

　　方案2：与方案1类似，只是lockValue为过期的时间戳，解决了“setnx与expire“非原子操作的问题

　　　　获取锁：setnx之前先get锁的值，发现时间已经过期，再setnx。

　　　　释放锁：del之前，先get值获取锁的值，是否和lockValue一致，一致则释放。【缺点：先读再del的方式不是原子的】

 

　　方案3： set + lua脚本【Redis简单分布式锁实现的正确姿势】

　　　　获取锁： SET ${lockKey} ${lockValue} ${过期时间} NX （Redis 2.6.12 +）

　　　　释放锁：使用lua脚本保证原子性，执行过程中不会被打断

　　

 

 

六、string的底层数据结构

Redis的string底层数据结构-SDS（Simple Dynamic String，动态字符串）

特点：

 　　1.记录了字符串长度，获取长度的时间复杂度为O(1)。

　　 2. 具有动态增加空间的能力，扩容不需要使用者关心。

　　 3.空间预分配，减少字符串修改时内存分配次数。

　　　　扩容：当字符串长度小于 1M 时，扩容都是加倍修改后的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。(字符串最大长度为 512M)。

　　　　缩容：不会释放，修改len与free，供下次使用　　

 

对于Redis的key-value中value的结构体如下：

　　   

 

 

其中，type：类型，记录了对外的类型（例如string、hash、set、zset等） （可以根据此判断是否能够执行某指令）

　　　encoding：编码，记录了内部使用存储“值”的数据结构（可以根据此判断是否能够执行某指令）

　　　*ptr：指针，指向“值”

 

当我们的type=string时，有三种encoding，分别是：

　　1.int：整型（string的值为数字时，使用此编码）

　　2.embstr：使用embstr编码的SDS（string的值为非数字时，且长度小于等于44个字节，使用此编码）

　　3.raw：SDS（string的值为非数字时，且长度大于44个字节，使用此编码）

embstr与raw的区别：embstr是一种保存短字符串的优化手段，查询与释放更快
　　raw格式的RedisObject与SDS的内存分配是2次，是不连续的
　　embstr格式的RedisObject与SDS的内存分配是1次，是连续的

同一个key的embstr与raw转换可逆

　　

 

浮点型的string存储也是使用raw或embstr的SDS，操作运算的时候转换为浮点型，存储的时候再转换回SDS

　　

 

 

 

 

 

 

 小结-Redis底层数据结构概述　　

Redis基本数据结构[RedisObject的type] （string、list、hash、set、zset）

Redis底层数据结构[RedisObject的encoding]

　　int：整型

　　embstr：embstr格式的SDS，简单动态字符串

　　raw：SDS，简单动态字符串

　　quicklist：快速列表

　　hashtable ：字典

　　zskiplist：跳跃表

　　intset：整数集合

　　ziplist：压缩列表

底层对应关系：

 

 

 

 

七、list的底层数据结构

list的底层数据结构用到了快速列表quicklist和压缩表ziplist（在Redis3.2版本之后一律采用quicklist数据结构）

 

如何快速？

　quicklist表面是一个普通的链表，快速体现在data区域，quicklist的data指针指向的不是数据，而是ziplist，ziplist存储了数据。

　ziplist(压缩列表)是一个Redis为节省内存而开发的连续内存组成的顺序型数据结构。

　quicklist是一个采用链表分段存储，每段采用ziplist紧凑存储的数据结构

 

下图是ziplist的结构：

 

 

 

 其中，entry的结构如下：

 

　previous_entry_length：表示前一个entry的字节长度，占1个或者5个字节

　　 前一个元素长度小于254个字节，则previous_entry_length=1个字节

　　 前一个元素长度大于等于254个字节，则previous_entry_length=5个字节

　encoding：表示当前元素的编码

　content：存储的数据

 

ziplist的反向遍历：通过ziplist的zltail和entryN的previous_entry_length完成从后往前的遍历

 

ziplist紧凑的代价-连锁更新

　案例：

　　1.在一个压缩列表中， 有多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN。

　　因为 e1 至 eN 的所有节点的长度都小于 254 字节， 所以记录这些节点的长度只需要 1 字节长的 previous_entry_length 属性

　　2.将一个长度大于等于 254 字节的新节点 new 设置为压缩列表的表头节点， 那么 new 将成为 e1 的前置节点

 　　e1 的 previous_entry_length 属性需要从原来的 1 字节长扩展为 5 字节长。

　

　　3.e2、e3直到eN都要更新

 　

 

 

 

八、hash的底层数据结构

两种底层实现的数据结构：ziplist（压缩列表）与hashtable（字典）

 

使用ziplist时的存储结构：K占一个entry，V也占一个entry，如下图：

 

 

使用hashtable的存储结构：C语言没有字典，Redis自己实现了一个，类似于Java的HashMap

　　需要解决的问题与HashMap是相同的，原理也类似：hash碰撞、rehash、负载因子

　　区别：rehash过程是渐进式的，不是一次性完成的，若都在一个hset请求中进行rehash，可能会阻塞其他指令

 

两种底层数据结构转换的临界点：

　　k-v的长度小于64个字节 且 k数量小于512个：ziplist

　　其他：hashtable

 

 

 

 

九、set的底层数据结构

底层数据结构：

　intset：整型集合，内存连续的数组存储

　hashtable（类似与Java的HashSet的底层是HashMap，只不过Value为NULL）

 

两种底层数据结构转换的临界点：

　成员长度是整数值 且 成员数量小于512：intset

　其他：hashtable

 

 

十、zset的底层数据结构

底层数据结构：

　ziplist：压缩列表

　skiplist：跳跃表

 

两种底层数据结构转换的临界点：

　　 成员长度大小均小于64字节 且 成员数量小于128：ziplist

　　其他：skiplist

 

skiplist：跳跃表，一种有序的数据结构，通过在每个节点中维护多个指向其他节点的指针，从而能快速访问。

如何跳跃的逻辑如下图所示：

　　1.一个普通的有序链表

　

　　　2.每个节点增加指针，建立索引

　

　　　3.再加一级索引，称为L2

　

 

跳跃表：一个加了多级索引的链表

Redis的跳跃表有2个结构组成：

　skiplist：用于保存跳跃表节点的相关信息，比如节点的数量,以及指向表头节点和表尾节点的指针等等。

　skiplistNode：用于表示跳跃表节点

 

其中BW是回退指针，插入/删除/查找：平均O(logN)，最坏O(N)。

 

 ————面试题————

 

问法1：mysql为什么不使用跳跃表做为索引的数据结构？（一般这么问）

问法2：redis为什么不使用B+树做为zset的数据结构？

　　

分析：redis的zset与mysql都面临一个问题，根据条件查询范围内的数据

　　mysql：select * from table where a >= 1.0 and a <= 2.0

　　redis： zrangebyscore ${key} 1.0 2.0

 

数据结构的差异：

 

 

B+树更适合于数据存储在硬盘的场景：每次查找基本代表了一次i/o，B+树的查询i/o次数稳定为O(logN)，跳跃表最差为O(n)。

跳跃表更适合数据存储在内存的场景：数据结构较为简单，占用的空间页也较少。

 

 

十、scan

SCAN：一个基于游标的迭代器。这意味着命令每次被调用都需要使用上一次这个调用返回的游标作为该次调用的游标参数，以此来延续之前的迭代过程。

　　SCAN 命令用于迭代当前数据库中的数据库键，替代keys

　　SSCAN 命令用于迭代集合键中的元素，替代smembers

　　HSCAN 命令用于迭代哈希键中的键值对，替代hgetall

　　ZSCAN 命令用于迭代有序集合中的元素（包括元素成员和元素分值）

 

SCAN通用语法：[H/S/Z]SCAN [KEY] ${cursor} [MATCH pattern] [COUNT count]

 

使用方法： 第一次遍历时，cursor 值为 0 将返回结果中第一个整数值作为下一次遍历的 cursor 一直遍历到返回的 cursor 值为 0 时结束，如下图：

　　

 

这篇关于Redis之数据结构原理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！