三次给你讲清楚 Redis 之 Redis 是个啥
摘要:Redis 是一款基于键值对的 NoSQL 数据库,它的值支持多种数据结构:字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)等。
本文分享自华为云社区《三次给你聊清楚Redis》之Redis是个啥》,原文作者:兔老大。
一、入门
Redis 是一款基于键值对的 NoSQL 数据库,它的值支持多种数据结构:字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)等。
• Redis 将所有的数据都存放在内存中,所以它的读写性能十分惊人,用作数据库,缓存和消息代理。
• Redis 具有内置的复制,Lua 脚本,LRU 逐出,事务和不同级别的磁盘持久性,并通过 Redis Sentinel 和 Redis Cluster 自动分区提供了高可用性。
• Redis 典型的应用场景包括:缓存、排行榜、计数器、社交网络、消息队列等
1.1NoSql 入门概述 1)
1)单机 Mysql 的美好时代
瓶颈:
数据库总大小一台机器硬盘内存放不下;
数据的索引(B + tree)一个机器的运行内存放不下;
访问量(读写混合)一个实例不能承受;
2)Memcached(缓存)+ MySql + 垂直拆分
通过缓存来缓解数据库的压力,优化数据库的结构和索引。
垂直拆分指的是:分成多个数据库存储数据(如:卖家库与买家库)。
3)MySql 主从复制读写分离
主从复制:主库来一条数据,从库立刻插入一条;
读写分离:读取(从库 Master),写(主库 Slave);
4)分表分库+水平拆分+MySql 集群
主库的写压力出现瓶颈(行锁 InnoDB 取代表锁 MyISAM);
分库:根据业务相关紧耦合在同一个库,对不同的数据读写进行分库(如注册信息等不常改动的冷库与购物信息等热门库分开);
分表:切割表数据(例如 90W 条数据,id 1-30W 的放在 A 库,30W-60W 的放在 B 库,60W-90W 的放在 C 库);
MySql 扩展的瓶颈
大数据下 IO 压力大
表结构更改困难
常用的 Nosql
Redis
memcache
Mongdb 以
上几种 Nosql 请到各自的官网上下载并参考使用
Nosql 的核心功能点
KV(存储)
Cache(缓存)
Persistence(持久化)
……
1.2redis 的介绍和特点:
问题:
传统数据库:持久化存储数据。
solr 索引库:大量的数据的检索。
在实际开发中,高并发环境下,不同的用户会需要相同的数据。
因为每次请求,在后台我们都会创建一个线程来处理,这样造成,同样的数据从数据库中查询了 N 次。
而数据库的查询本身是IO操作,效率低,频率高也不好。
总而言之,一个网站总归是有大量的数据是用户共享的,但是如果每个用户都去数据库查询,效率就太低了。
解决:
将用户共享数据缓存到服务器的内存中。
特点:
1、基于键值对
2、非关系型(redis)关系型数据库:
存储了数据以及数据之间的关系,oracle,mysql
非关系型数据库:存储了数据,redis,mdb.
3、数据存储在内存中,服务器关闭后,持久化到硬盘中
4、支持主从同步
实现了缓存数据和项目的解耦。
redis 存储的数据特点:
大量数据
用户共享数据数据不经常修改。
查询数据
redis 的应用场景:
网站高并发的主页数据
网站数据的排名
消息订阅
1.3redis——数据结构和对象的使用介绍
redis 官网
我们下载第一个,然后基本一路默认就行了。
安装后,服务自动启动,以后也不用自动启动。
出现这个表示我们连接上了。
1.3.1 String
数据结构
常见操作
应用场景
String 是最常用的一种数据类型,普通的 key/value 存储都可以归为此类,value 其实不仅是 String,也可以是数字:比如想知道什么时候封锁一个 IP 地址(访问超过几次)。INCRBY 命令让这些变得很容易,通过原子递增保持计数。
1.3.2 LIST
数据结构
常见操作
应用场景
Redis list 的应用场景非常多,也是 Redis 最重要的数据结构之一。我们可以轻松地实现最新消息排行等功能。Lists 的另一个应用就是消息队列,可以利用 Lists 的 PUSH 操作,将任务存在 Lists 中,然后工作线程再用 POP 操作将任务取出进行执行。
1.3.3 HASH
数据结构
dictht 是一个散列表结构,使用拉链法保存哈希冲突的 dictEntry。
Redis 的字典 dict 中包含两个哈希表 dictht,这是为了方便进行 rehash 操作。在扩容时,将其中一个 dictht 上的键值对 rehash 到另一个 dictht 上面,完成之后释放空间并交换两个 dictht 的角色。
rehash 操作并不是一次性完成、而是采用渐进式方式,目的是为了避免一次性执行过多的 rehash 操作给服务器带来负担。
渐进式 rehash 通过记录 dict 的 rehashidx 完成,它从 0 开始,然后没执行一次 rehash 例如在一次 rehash 中,要把 dict[0] rehash 到 dict[1],这一次会把 dict[0] 上 table[rehashidx] 的键值对 rehash 到 dict[1] 上,dict[0] 的 table[rehashidx] 指向 null,并令 rehashidx++。
在 rehash 期间,每次对字典执行添加、删除、查找或者更新操作时,都会执行一次渐进式 rehash。
采用渐进式 rehash 会导致字典中的数据分散在两个 dictht 中,因此对字典的操作也会在两个哈希表上进行。例如查找时,先从 ht[0]查找,没有再查找 ht[1],添加时直接添加到 ht[1]中。
常见操作
1.3.4 SET
常见操作
应用场景
Redis 为集合提供了求交集、并集、差集等操作,故可以用来求共同好友等操作。
1.3.5 ZSET
数据结构
typedef struct zskiplistNode{//后退指针 struct zskiplistNode *backward;//分值 double score;//成员对象 robj *obj;//层 struct zskiplistLever{//前进指针 struct zskiplistNode *forward;//跨度 unsigned int span;}lever[];}
跳跃表,基于多指针有序链实现,可以看作多个有序链表。
与红黑树等平衡树相比,跳跃表具有以下优点:
插入速度非常快速,因为不需要进行旋转等操作来维持平衡性。
更容易实现。
支持无锁操作。
常见操作
应用场景
以某个条件为权重,比如按顶的次数排序。ZREVRANGE 命令可以用来按照得分来获取前 100 名的用户,ZRANK 可以用来获取用户排名,非常直接而且操作容易。
Redis sorted set 的使用场景与 set 类似,区别是 set 不是自动有序的,而 sorted set 可以通过用户额外提供一个优先级(score)的参数来为成员排序,并且是插入有序的,即自动排序。
1.4 Spring 整合 Redis
引入依赖
- spring-boot-starter-data-redis
配置 Redis
- 配置数据库参数
- 编写配置类,构造 RedisTemplate
这个 springboot 已经帮我们配了,但是默认 object,我想改成 string
import org.springframework.context.annotation.Bean;import org.springframework.context.annotation.Configuration;import org.springframework.data.redis.connection.RedisConnectionFactory;import org.springframework.data.redis.core.RedisTemplate;import org.springframework.data.redis.serializer.RedisSerializer;
@Configurationpublic class RedisConfig {
}
访问 Redis
- redisTemplate.opsForValue()
- redisTemplate.opsForHash()
- redisTemplate.opsForList()
- redisTemplate.opsForSet()
- redisTemplate.opsForZSet()
@RunWith(SpringRunner.class)@SpringBootTest@ContextConfiguration(classes = CommunityApplication.class)public class RedisTests {
}
这样还是稍微有点麻烦,我们其实可以绑定 key
二、数据结构原理总结
这部分在我看来是最有意思的,我们有必要了解底层数据结构的实现,这也是我最感兴趣的。比如,
你知道 redis 中的字符串怎么实现的吗?为什么这么实现?
你知道 redis 压缩列表是什么算法吗?
你知道 redis 为什么抛弃了红黑树反而采用了跳表这种新的数据结构吗?
你知道 hyperloglog 为什么用如此小的空间就可以有这么好的统计性能和准确性吗?
你知道布隆过滤器为什么这么有效吗?有没有数学证明过?
你是否还能很快写出来快排?或者不断优化性能的排序?
是不是只会调库了甚至库函数怎么实现的都不知道?真的就是快排?
包括数据库,持久化,处理事件、客户端服务端、事务的实现、发布和订阅等功能的实现,也需要了解。
2.1 数据结构和对象的实现
1) 字符串
redis 并未使用传统的 c 语言字符串表示,它自己构建了一种简单的动态字符串抽象类型。
在 redis 里,c 语言字符串只会作为字符串字面量出现,用在无需修改的地方。
当需要一个可以被修改的字符串时,redis 就会使用自己实现的 SDS(simple dynamic string)。比如在 redis 数据库里,包含字符串的键值对底层都是 SDS 实现的,不止如此,SDS 还被用作缓冲区(buffer):比如 AOF 模块中的 AOF 缓冲区以及客户端状态中的输入缓冲区。
下面来具体看一下 sds 的实现:
sds 遵循 c 中字符串以'\0'结尾的惯例,这一字节的空间不算在 len 之内。这样的好处是,我们可以直接重用 c 中的一部分函数。比如 printf;
sds 相对 c 的改进
获取长度:c 字符串并不记录自身长度,所以获取长度只能遍历一遍字符串,redis 直接读取 len 即可。
缓冲区安全:c 字符串容易造成缓冲区溢出,比如:程序员没有分配足够的空间就执行拼接操作。而 redis 会先检查 sds 的空间是否满足所需要求,如果不满足会自动扩充。
内存分配:由于 c 不记录字符串长度,对于包含了 n 个字符的字符串,底层总是一个长度 n+1 的数组,每一次长度变化,总是要对这个数组进行一次内存重新分配的操作。因为内存分配涉及复杂算法并且可能需要执行系统调用,所以它通常是比较耗时的操作。
redis 内存分配:
1、空间预分配:如果修改后大小小于 1MB,程序分配和 len 大小一样的未使用空间,如果修改后大于 1MB,程序分配 1MB 的未使用空间。修改长度时检查,够的话就直接使用未使用空间,不用再分配。
2、惰性空间释放:字符串缩短时不需要释放空间,用 free 记录即可,留作以后使用。
二进制安全
c 字符串除了末尾外,不能包含空字符,否则程序读到空字符会误以为是结尾,这就限制了 c 字符串只能保存文本,二进制文件就不能保存了。
而 redis 字符串都是二进制安全的,因为有 len 来记录长度。
2) 链表
作为一种常用数据结构,链表内置在很多高级语言中,因为 c 并没有,所以 redis 实现了自己的链表。
链表在 redis 也有一定的应用,比如列表键的底层实现之一就是链表。(当列表键包含大量元素或者元素都是很长的字符串时)发布与订阅、慢查询、监视器等功能也用到了链表。
具体实现:
总结一下 redis 链表特性:
双端、无环、带长度记录
多态:使用 void* 指针来保存节点值, 可以通过 dup 、 free 、 match 为节点值设置类型特定函数, 可以保存不同类型的值。
3)字典
其实字典这种数据结构也内置在很多高级语言中,但是 c 语言没有,所以 redis 自己实现了。应用也比较广泛,比如 redis 的数据库就是字典实现的。不仅如此,当一个哈希键包含的键值对比较多,或者都是很长的字符串,redis 就会用字典作为哈希键的底层实现。
来看看具体是实现:
table 是一个数组, 数组中的每个元素都是一个指向 dictEntry 结构的指针, 每个 dictEntry 结构保存着一个键值对
图为一个大小为 4 的空哈希表。我们接着就来看 dictEntry 的实现:
(v 可以是一个指针, 或者是一个 uint64_t 整数, 又或者是一个 int64_t 整数。)
next 就是解决键冲突问题的,冲突了就挂后面,这个学过数据结构的应该都知道吧,不说了。
下面我们来说字典是怎么实现的了。
type 和 privdata 是对不同类型的键值对, 为创建多态字典而设置的:
type 指向 dictType , 每个 dictType 保存了用于操作特定类型键值对的函数, 可以为用途不同的字典设置不同的类型特定函数。
而 privdata 属性则保存了需要传给那些类型特定函数的可选参数。
dictType 就暂时不展示了,不重要而且字有点多。。。还是讲有意思的东西吧
rehash(重新散列)
随着我们不断的操作,哈希表保存的键值可能会增多或者减少,为了让哈希表的负载因子维持在合理的范围内,有时需要对哈希表进行合理的扩展或者收缩。 一般情况下, 字典只使用 ht[0] 哈希表, ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。
redis 字典哈希 rehash 的步骤如下:
1)为 ht[1]分配合理空间:如果是扩展操作,大小为第一个大于等于 ht[0]used2 的,2 的 n 次幂。
如果是收缩操作,大小为第一个大于等于 ht[0]*used 的,2 的 n 次幂。
2)将 ht[0]中的数据 rehash 到 ht[1]上。
3)释放 ht[0],将 ht[1]设置为 ht[0],ht[1]创建空表,为下次做准备。
渐进 rehash
数据量特别大时,rehash 可能对服务器造成影响。为了避免,服务器不是一次性 rehash 的,而是分多次。
我们维持一个变量 rehashidx,设置为 0,代表 rehash 开始,然后开始 rehash,在这期间,每个对字典的操作,程序都会把索引 rehashidx 上的数据移动到 ht[1]。
随着操作不断执行,最终我们会完成 rehash,设置 rehashidx 为-1.
需要注意:rehash 过程中,每一次增删改查也是在两个表进行的。
4)整数集合
整数集合(intset)是 Redis 用于保存整数值的集合抽象数据结构, 可以保存 int16_t 、 int32_t 、 int64_t 的整数值, 并且保证集合中不会出现重复元素。
实现较为简单:
各个项在数组中从小到大有序地排列, 并且数组中不包含任何重复项。
虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组, 但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值:
如果 encoding 属性的值为 INTSET_ENC_INT16 , 那么 contents 就是一个 int16_t 类型的数组, 数组里的每个项都是一个 int16_t 类型的整数值 (最小值为 -32,768 ,最大值为 32,767 )。
如果 encoding 属性的值为 INTSET_ENC_INT32 , 那么 contents 就是一个 int32_t 类型的数组, 数组里的每个项都是一个 int32_t 类型的整数值 (最小值为 -2,147,483,648 ,最大值为 2,147,483,647 )。
如果 encoding 属性的值为 INTSET_ENC_INT64 , 那么 contents 就是一个 int64_t 类型的数组, 数组里的每个项都是一个 int64_t 类型的整数值 (最小值为 -9,223,372,036,854,775,808 ,最大值为 9,223,372,036,854,775,807 )。
升级
c 语言是静态类型语言,不允许不同类型保存在一个数组。这样第一,灵活性较差,第二,有时会用掉不必要的内存。
比如用 long long 储存 1
为了提高整数集合的灵活性和节约内存,我们引入升级策略。
当我们要将一个新元素添加到集合里, 并且新元素类型比集合现有元素的类型都要长时, 集合需要先进行升级。
分为三步进行:
根据新元素的类型, 扩展整数集合底层数组的空间大小, 并为新元素分配空间。
将底层数组现有的所有元素都转换成与新元素相同的类型, 并将类型转换后的元素放置到正确的位上
将新元素添加到底层数组里面。
因为每次添加新元素都可能会引起升级, 每次升级都要对已有元素类型转换, 所以添加新元素的时间复杂度为 O(N) 。
因为引发升级的新元素比原数据都长,所以要么他是最大的,要么他是最小的。我们把它放在开头或结尾即可。
降级
略略略,不管你们信不信,整数集合不支持降级操作。。我也不知道为啥
5)压缩
列表压缩列表是列表键和哈希键的底层实现之一。
当一个列表键只包含少量列表项,并且列表项都是小整数或者短字符串,redis 就会用压缩列表做列表键底层实现。
压缩列表是 Redis 为了节约内存而开发的, 由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。
一个压缩列表可以包含任意多个节点(entry), 每个节点可以保存一个字节数组或者一个整数值。
具体实现:
具体说一下 entry:
由三个部分组成:
1、previous_entry_length:记录上一个节点的长度,这样我们就可以从最后一路遍历到开头。
2、encoding:记录了 content 所保存的数据类型和长度。(具体编码不写了,不重要)
3、content:保存节点值,可以是字节数组或整数。(具体怎么压缩的等我搞明白再补)
连锁更新
前面说过, 每个节点的 previous_entry_length 属性都记录了前一个节点的长度:
如果前一节点的长度< 254 KB, 那么 previous_entry_length 需要用 1 字节长的空间
如果前一节点的长度>=254 KB, 那么 previous_entry_length 需要用 5 字节长的空间
现在, 考虑这样一种情况: 在一个压缩列表中, 有多个连续的、长度介于 250 字节到 253 字节之间的节点 ,这时, 如果我们将一个长度大于等于 254 字节的新节点 new 设置为压缩列表的表头节点。。。。
然后脑补一下,就会导致连锁扩大每个节点的空间对吧?e(i)因为 e(i-1)的扩大而扩大,i+1 也是如此,以此类推... ...
删除节点同样会导致连锁更新。
这个事情只是想说明一个问题:插入删除操作的最坏时间复杂度其实是 o(n*n),因为每更新一个节点都要 o(n)。
但是,也不用太过担心,因为这种特殊情况并不多见,这些命令的平均复杂度依旧是 o(n)。
版权声明: 本文为 InfoQ 作者【华为云开发者社区】的原创文章。
原文链接:【http://xie.infoq.cn/article/9ccbd47401e3e60a926bbd6bb】。文章转载请联系作者。
评论