导图社区 Redis数据结构知识框架学习
- 22
- 0
- 0
- 举报
Redis数据结构知识框架学习
因为redis数据类型有很多,不同的数据类型有相同的元数据要记录,所以redis会用一个RedisObject结构体来统一记录这些元数据 当保存Long类型的时候,RedisObject的指针就直接赋值为整数.
编辑于2022-11-14 13:53:00 广东- redis
- redis数据…
- 相似推荐
- 大纲
Redis数据结构知识框架学习
缓存一致性问题
先更新数据库,再删除缓存
（1）缓存刚好失效 （2）请求A查询数据库，得一个旧值 （3）请求B将新值写入数据库 （4）请求B删除缓存 （5）请求A将查到的旧值写入缓存
以上会发生脏数据
但是只有2,3中 3比2 快, B才会发生先删除缓存,A 用旧值写缓存
实际上 写库操作远远低于读操作,所以避免慢 SQL.
先删缓存再写数据库
（1）先淘汰缓存 （2）再写数据库（这两步和原来一样） （3）休眠1秒，再次淘汰缓存
使用异步双删除
基本操作
常见操作
查看个数,长度
是否存在,包含,追加,对该key 或key下的某一域增减
删除,删除指定位置,删除并获取
自由主题
数据类型
Key
删除,是否存在,查看,按模式匹配(大集合会有性能问题),
Scan迭代所有的key,
对List,set进行排序
从一个redis实例迁移到另一个redis实例
设置,取消过期时间, 获取key的剩余过期时间
Redis如何淘汰过期的keys Redis keys过期有两种方式：被动和主动方式。 当一些客户端尝试访问它时，key会被发现并主动的过期。 当然，这样是不够的，因为有些过期的keys，永远不会访问他们。 无论如何，这些keys应该过期，所以定时随机测试设置keys的过期时间。所有这些过期的keys将会从密钥空间删除。 具体就是Redis每秒10次做的事情： 测试随机的20个keys进行相关过期检测。 删除所有已经过期的keys。 如果有多于25%的keys过期，重复步奏1. 这是一个平凡的概率算法，基本上的假设是，我们的样本是这个密钥控件，并且我们不断重复过期检测，直到过期的keys的百分百低于25%,这意味着，在任何给定的时刻，最多会清除1/4的过期keys。
Set
Sdiff 获取集合不存在的元素 SDiff a b 相当于a-b
Sdiff Store 将差集存储到一个key中
求几个集合的并集, 可存储到一个key 中
SInter 取交集 SInterStore 将交集写入到一个key中
List
BLOCK 操作,从队列头尾阻塞的取出一个值
可指定从若干个队列中获取值
当队列为空,给client 会被阻塞,直到有写入,可指定超时时间,超时后返回 nil
阻塞操作可以保证公平性
redis 2.4 2.6 不同,同时写入多个值时如 a,b,c ,因该key被阻塞的client在2.4下,会 收到a, 2.6会收到c
当从server端删除该值后,假如client在该值被 处理之前挂掉了,那么该值也就丢了,rabbitmq的消息确认机制可以解决这个问题
可以使用List的阻塞操作结合其他数据类型在同一个事务中的原子操作,为客户端提供阻塞行为
是否可实现公平的分布式锁
类似于Java中List提供的操作,新增了LTrim, 截取某一个范围的值
删除列表最后一个元素,将其放到另一个列表
自由主题
有序集合
可以对几个有序集合并集 reduce操作,支持SUM,MIN,MAX
返回有序集合中某key的排名
可以获取有序集合的某一范围的值; 也可以指定分数的最小最大值分页查询该范围的集合
迭代集合
Transaction
watch
WATCH命令可以监控一个或多个键，一旦其中有一个键被修改（或删除），之后的事务就不会执行。监控一直持续到EXEC命令,只要在exec执行之前,该值被修改,该事务就不会被执行,相当于exec时,redis作了检查
由于WATCH命令的作用只是当被监控的键值被修改后阻止之后一个事务的执行，而不能保证其他客户端不修改这一键值，所以在一般的情况下我们需要在EXEC执行失败后重新执行整个函数。用循环保证
执行EXEC命令后会取消对所有键的监控，如果不想执行事务中的命令也可以使用UNWATCH命令来取消监控。在某些业务场景中,watch 之后,我们不一定执行事务操作,
Watch命令是一种乐观锁技术,只要是这个键值被修改,那么后边有效修改都不会生效,通常也可以使用该方式,较少竞态条件,当exec返回空集合时,认为该次操作失败
Exec实际执行事务中的所有指令,会清空watch 命令
Exec命令回复是一个数组,和 命令的执行顺序一致
即使事务中有某条/某些命令执行失败了， 事务队列中的其他命令仍然会继续执行 —— Redis 不会停止执行事务中的命令。
事务在执行 EXEC 之前，入队的命令可能会出错。比如说，命令可能会产生语法错误（参数数量错误，参数名错误，等等 这种情况下,客户端会停止执行这个事务
从Mutil命令开始到exec 命令中执行的命令都会被入到事务队列
Hash
是否存在,添加,删除,获取所有key,value, 迭代hash集合
递增hash 某key的值 如果 该key不存在就设置其为0+ incre value
自由主题
数据结构坑点
当字符串大小需要扩容时,小于1M,都是扩大一倍.大于1M,每次只扩容1M. 最大长度512 M
自增值超过最大值,会报错
对于容器型数据结构,如果容器不存在就创建,如果元素没有了,就删除容器
分布式锁
单节点方案(非红锁)
获取锁
hash 到一个 cluster 节点
如果不存在,设置 lock path.设置过期时间
加锁是 value 设置 client id
设置看门狗 watch dog ,定期更新锁. 可使用延迟队列实现.
没有获取到锁,可考虑阻塞似等待获取
解锁
如果不设置过期时间.会导致出现死锁问题
a) 一旦redis发生主从切换，可能会丢失一些锁，
和zk 比较
Zookeeper实现的分布式锁其实存在一个缺点，那就是性能上可能并没有缓存服务那么高。因为每次在创建锁和释放锁的过程中，都要动态创建、销毁瞬时节点来实现锁功能。ZK中创建和删除节点只能通过Leader服务器来执行，然后将数据同不到所有的Follower机器上。 并发问题，可能存在网络抖动，客户端和ZK集群的session连接断了，zk集群以为客户端挂了，就会删除临时节点，这时候其他客户端就可以获取到分布式锁了
Redis很难实现公平性
redlock
在算法的分布式版本中，我们假设我们有N个Redis主机。这些节点完全独立，因此我们不使用复制或任何其他隐式协调系统。我们已经描述了如何在单个实例中安全地获取和释放锁。我们理所当然地认为算法将使用此方法在单个实例中获取和释放锁。在我们的示例中，我们设置N = 5，这是一个合理的值，因此我们需要在不同的计算机或虚拟机上运行5个Redis主服务器，以确保它们以大多数独立的方式失败。 为了获取锁，客户端执行以下操作： 1. 它以毫秒为单位获取当前时间。 2. 它尝试按顺序获取所有N个实例中的锁，在所有实例中使用相同的键名和随机值。在步骤2期间，当在每个实例中设置锁定时，客户端使用与总锁定自动释放时间相比较小的超时以获取它。例如，如果自动释放时间是10秒，则超时可以在~5-50毫秒范围内。这可以防止客户端长时间保持阻塞状态，试图与Redis节点通话失败：如果实例不可用，我们应该尝试尽快与下一个实例通话。 3. 客户端通过从当前时间中减去在步骤1中获得的时间戳来计算获取锁定所需的时间。当且仅当客户端能够在大多数实例中获取锁定时（至少3个）并且获取锁定所经过的总时间小于锁定有效时间，认为锁定被获取。 4. 如果获得了锁，则其有效时间被认为是初始有效时间减去经过的时间，如步骤3中计算的。 5. 如果客户端由于某种原因（无法锁定N / 2 + 1实例或有效时间为负）未能获取锁定，它将尝试解锁所有实例（即使它认为不是能够锁定）。
当挂掉一个节点后,不会导致锁被抢占的风险
缓存
失效
失效时间设置随机值,避免集体失效
数据结构的实现
应用场景
zset
记录用户帖子id 列表.快速显示
记录热榜帖子 ID列表.总热榜,分类热榜
用于记录一对多,且多的一方严格不能重复
记录某个集合,该集合可能是和用户相关,也可能是与总的系统相关
hash
记录帖子点赞数,评论数,点击数.
记录帖子标题,摘要,作者,封面信息等.
缓存近期的热贴内容.(帖子内容非常大,不适合从db取)
list
记录帖子的相关文章列表.根据内容推荐相关帖子
bitmap
用于作为bool数组,或者自定义位数组,主要是为了节省内存
HyperLogLog
用于粗略计算去重之后的统计值.
例如网站 UV,需要过滤重复访问
只能添加和获取总数,不能获取某个值是否存在,或者全部元素
布隆过滤器
用于去重.获取某个元素是否存在于列表中
如果存在,不一定真的存在 如果不存在,那一定不存在
考虑一定给用户推荐未访问过得资源
考虑不重复多次使用资源.
要容忍一定的失败率,即资源可能未被访问,但是被当成已被访问过
使用多个 Hash算法,分别叫key 映射的bit置1.
不存在一定不存在!!!!
只有add和 exist(可查多个)命令
可使用初始参数,设置过滤器,error_rate 是错误率,越低容量越大. initial_size 预估总量,要针对实际的场景,设置总量
Redis-cell
项目不大的，维护成本不高的话，可以采用 直接使用 redsi-cell ，否则可以考虑细粒度的控制到每个服务节点去限流，配合相应的负载均衡策略去实现
利用zset，score圈出时间窗口，统计时间窗口内同一个用户同一个行为出现的次数,如果限流次数太大.可能不适用,例如1s 1000次
CL.THROTTLE test 100 400 60 3
test key 容量100(最大并发) 60s内最多400次. 本次申请3个容量
1： 是否成功，0：成功，1：拒绝 2： 令牌桶的容量，大小为初始值+1 3： 当前令牌桶中可用的令牌 4： 若请求被拒绝，这个值表示多久后才漏斗桶中会重新添加令牌，单位：秒，可以作为重试时间 5： 表示多久后令牌桶中的令牌会存满
漏斗算法
特殊的数据结构
压缩链表
由一个个压缩链表即数组组成,为了避免普通链表的额外内存开销.
为了尽可能节约内存设计出来的双向链表
存储字符串或整数
在细节上节省内存，对于值的存储采用了变长的编码方式
每一项会有单独的位数标记该项的数据长度和类型
hash、list、zset底层数据结构实现
特点
1) 内部表现为数据紧凑排列的一块连续内存数组。
2) 可以模拟双向链表结构，以O(1)时间复杂度入队和出队。
3) 新增删除操作涉及内存重新分配或释放，加大了操作的复杂性。
4) 读写操作涉及复杂的指针移动，最坏时间复杂度为O(n2)。
5) 适合存储小对象和长度有限的数据。
1）针对性能要求较高的场景使用ziplist，建议长度不要超过1000，每个元素大小控制在512字节以内
跳跃表
跳表平均支持 O(logN)，最坏O(N)复杂度的查找
为什么不用树,平衡树代替跳跃表?
跳跃表的实现很简单就能达到 O(logN)的级别
快速链表
压缩链表使用 指针链接起来,变成一个linkedlist
每一个ziplist 默认是8k.(可配)
运维
监控
2）命令平均耗时使用info Commandstats命令获取，包含每个命令调用次数 ，总耗时，平均耗时，单位微秒。
主从
Redis的复制功能分为同步（sync）和命令传播（command propagate）两个操作：
同步操作用于将从服务器的数据库状态 更新至主服务器当前所处的数据库状态；
命令传播操作则用于在主服务器的数据库状态被修改， 导致主从服务器的数据库状态出现不一致时，让主从 服务器的数据库重新回到一致状态。
读写分离
读写分离适合大访问（大到单台redis感觉很慢了），并且写操作远小于读操作的情况。
如果读请求数量远超写请求，导致集群数据copy成本远小于读请求成本。 同时能一定程度上接受数据的不一致性，那可以做读写分离的。
redis cluster
特性
1、所有的redis节点彼此互联(PING-PONG机制),内部使用二进制协议优化传输速度和带宽。
2、节点的fail是通过集群中超过半数的节点检测失效时才生效。
3、客户端与redis节点直连,不需要中间proxy层.客户端不需要连接集群所有节点,连接集群中任何一个可用节点即可。
4、redis-cluster把所有的物理节点映射到[0-16383]slot上（不一定是平均分配）,cluster 负责维护node<->slot<->value。
每个Redis 节点都需要执行命令,声明自己负责的 slot
cluster addslots {slot_index1} {slot_index 2} {slot_index 3}
5、Redis集群预分好16384个桶，当需要在 Redis 集群中放置一个 key-value 时，根据 CRC16(key) mod 16384的值，决定将一个key放到哪个桶中。
每个Redis实例都知道其他节点的存在
无法保证强一致性
1、你的客户端写给主服务器节点 B 2、主服务器节点B向您的客户端回复确认。 3、主服务器节点B将写入传播到它的从服务器B1，B2和B3。
如果在 2步之后, 没有发送从服务器,此时B 挂掉了,那么key将丢失(故障期间一定会有key 丢失)
容错
选举过程是集群中所有master参与,如果半数以上master节点与故障节点通信超过(cluster-node-timeout),认为该节点故障，自动触发故障转移操作.
(2):什么时候整个集群不可用(cluster_state:fail)? a:如果集群任意master挂掉,且当前master没有slave.集群进入fail状态,也可以理解成集群的slot映射[0-16383]不完成时进入fail状态. b:如果集群超过半数以上master挂掉，无论是否有slave集群进入fail状态.
当集群不可用时,所有对集群的操作做都不可用，收到((error) CLUSTERDOWN The cluster is down)错误
故障转移
1. 下线的主节点的所有从节点里面，会进行选举，选举出一个新的主节点。 2. 被选中的从节点会执行 slave no one命令，成为新的主节点。 3. 新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽指派给自己。 4. 新的主节点向集群广播一条pong消息，这条pong消息可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点，并且这个主节点已经接管了原本由已下线节点处理的槽。 5.新的主节点开始接受和自己负责处理的槽有关的命令请求，故障转移操作完成。
主从选举
1. 当从节点发现自己复制的主节点进入已下线时，从节点（这里发出请求的从节点可能会有多个）会向集群广播一条cluster_type_failover_auth_request的消息，要求有投票权（负责处理槽）的主节点向这个节点进行投票。 2.收到cluster_type_failover_auth_request消息的主节点，根据自身条件（发起投票节点的current epoch不低于投票节点的current epoch）判断是否赞成该从节点成为新的主节点，若赞成则返回一条cluster_type_failover_auth_ack消息。 3. 从节点接收到cluster_type_failover_auth_ack消息，会将选票数加1。 4.如果某个从节点的选票大于等于集群中主节点的一半时（大于等于N/2 + 1），这个节点就会成为新的主节点。 如果在一个配置周期内，没有一个从节点获得足够多的选票，那么集群中会进入新的配置周期，并在此进行选举，知道选出新的主节点为止。
所有从节点都可能征求意见,自己是否可以成为主(投票的人只投给自己大的节点),超过半数即可(n+1)/2
可能选不出来
局限
1.目前只支持同一个槽上的key的批量操作； 2.目前只支持同一个槽上的key事务； 3.只能使用数据库0(每个redis实例有16个数据库，可通过select {index}命令来切换)； 4.不能将一个大的key(如hash、list)映射到不同的节点上； 5.目前集群主从复制只支持一层，不支持嵌套树状架构；
扩容时
步骤
1.对目标节点发送 cluster setslot {slot_index} importing {source_node_id} 2.对源节点发送 cluster setslot {slot_index} migrating {target_node_id} 3.源节点循环执行 cluster getkeysinslot {slot_index} {count(key个数)} 4.源节点执行，把key通过流水线(pipeline)迁移到目标节点 migrate {target_ip} {target_port} "" 0 {timeout} keys {key1} {key2} {key3} 5.重复3、4步骤 6.向集群中所有主节点发送通知 cluster setslot {slot_index} node {target_nodeid}
每个节点都知道每个槽对应的 cluster node .
节点在接到命令请求时,查询是否自己处理,如果是则处理,如果不是,返回 move 错误, moved错误携带正确的节点ip和端口号返回给客户端指引其转向执行，而且客户端以后的每一次关于该key都会去moved错误提供的节点去执行。
Codis
访问层:访问方式可以是vip或者是通过java代码调用jodis,然后连接调用不同的codis-proxy地址来实现高可用的LVS和HA功能.
代理层:然后中间层由codis-proxy和zookeeper处理数据走向和分配,通过crc32算法,把key平均分配在不同redis的某一个slot中.实现类似raid0的条带化,在旧版本的codis中,slot需要手工分配,在codis3.2之后,slot会自动分配,相当方便.
数据层:最后codis-proxy把数据存进真实的redis-server主服务器上,由于codis的作者黄东旭相当注重数据一致性,不允许有数据延时造成的数据不一致,所以架构从一开始就没考虑主从读写分离.从服务器仅仅是作为故障切换的冗余架构,由zookeeper调用redis-sentinel实现故障切换功能.
在Codis中，Codis会把所有的key分成1024个槽，这1024个槽对应着的就是Redis的集群，这个在Codis中是会在内存中维护着这1024个槽与Redis实例的映射关系。这个槽是可以配置，可以设置成 2048 或者是4096个。看你的Redis的节点数量有多少，偏多的话，可以设置槽多一些。
当Codis的Codis Dashbord 改变槽位的信息的时候，其他的Codis节点会监听到ZooKeeper的槽位变化，会及时同步过来。如图：
zk负责同步槽位信息.
优先级队列
sorted set
list
使用多个队列实现.优先级队列.不同的优先级任务进入到不同的队列
同时消费者从队列中取数据时,支持从多个队列中取数据,其中有优先级顺序.
阻塞似
启动多个消费者就是启动多个 client取数据
消息队列
pubsub
使用
订阅者可订阅一个,多个,匹配的订阅 topic
发布者发布某一个主题,和 value
发布主题会被立即转发到订阅该主题的消费者,如果没有消费者该消息会被丢弃
风险
会存在丢消息的风险(当宕机,断网,或者网络闪断丢失报文时)
由于该种特性,导致简单的 pubsub 会存在丢失响应的风险.
数据可靠性的无法保障
无法保证至少一次
扩展不灵活，没法通过多加consumer来加快消费的进度
可以使用多个 channel,监听多次.
list
list
1、当给定列表内没有任何元素可供弹出的时候，连接将被 BRPOP 命令阻塞，直到等待超时或发现可弹出元素为止。 2、当给定多个key参数时，按参数 key 的先后顺序依次检查各个列表，弹出第一个非空列表的尾部元素。 另外，BRPOP 除了弹出元素的位置和 BLPOP 不同之外，其他表现一致。
如果list中没有任务时， 该连接将会被阻塞 连接的阻塞有一个超时时间 ， 当超时时间设置为0时 ， 即可无线等待， 直到弹出消息
使用 pubsub 也可以通知消费者可以去 list中消费了
适用于 A-B 之间两个业务之间的订阅发布等,当多个业务线意味着不同的消费者时,比较困难
ack实现
维护两个队列： pending队列和doing表（hash表）。
workers定义为ThreadPool。 由pending队列出队后，workers分配一个线程（单个worker）去处理消息——给目标消息append一个当前时间戳和当前线程名称，将其写入doing表，然后该worker去消费消息，完成后自行在doing表擦除信息。
启用一个定时任务，每隔一段时间去扫描doing队列，检查每隔元素的时间戳，如果超时，则由worker的ThreadPoolExecutor去检查线程是否存在，如果存在则取消当前任务执行，并把事务rollback。最后把该任务从doing队列中pop出，再重新push进pending队列。
可以使用zset 作排序.
避免过度使用 Redis.只用 Redis作最擅长的事情,做不擅长的事情,越做越发现 坑点越多,最后欲罢不能.前期错误的设计导致后期故障率高.稳定性差, 改造成本高.等 rabbitmq 并不是很复杂.运维也很简单,可以和业务系统混部