现网压测系统设计

发表于 2022-09-21 分类于后台开发知识，系统设计阅读次数： Valine：
本文字数： 2.3k 阅读时长 ≈ 2 分钟

Q: 为什么需要线上压测？
Q: 全链路压测和接口压测的区别？
Q: 业务系统如何区分压测流量？即判断哪些是压测的请求，哪些是正常的请求？
Q: 这个压测打标的改造和适配要中间所有服务参与吗？改造成本会不会有点大？
Q: 识别到压测标记后，如何保证往下游发请求时，仍然是压测标记的形式？
Q: 如果我不在同一个线程中处理和发请求，怎么办？
Q: 如果我的压测链路中包含了外部服务的接口怎么办？例如第三方支付、第三方短信等。
Q: 会对数据库产生影响的压测请求怎么办？
Q: redis、kafka等中间件对压测有什么特殊处理？
Q: 压测结束时，如何避免对数据库继续产生影响？
Q: 压测数据怎么构造？一个个手动拼数据参数，然后让测试同学发送吗？
Q: 怎么完整设计这个压测系统的架构？包含哪些角色
Q: 怎么模拟实际用户的请求发送？因为实际场景应该是多个不同ip的用户访问进来才对。

[toc]

Q: 为什么需要线上压测？#

A:

需要在某些活动、大促前，评估机器扩容数量，验证系统能否有效支撑流量峰值。
线下测试环境的机器资源有限，无法完全模拟现网。同时很多配置可能配置不相同，如果没对上导致机器数量估计错误，可能引发重大故事。所以必须要在线上做压测。

Q: 全链路压测和接口压测的区别？#

A:
在特定的业务场景下，将相关的链路完整地串联起来同时施压，尽可能模拟出真实的用户行为。
接口A做接口压测，可能是1w/s的QPS，但是A和B同时压测，可能因为数据库连接等共享资源，导致实际QPS下降。

Q: 业务系统如何区分压测流量？即判断哪些是压测的请求，哪些是正常的请求？#

A:

url上加上打标参数，例如 http://xx?st=true
hearder中打标

Q: 这个压测打标的改造和适配要中间所有服务参与吗？改造成本会不会有点大？#

A:
不需要全部参与。

如果设计过链路跟踪系统，则每个服务都有中间件团队提供的拦截器，因此直接通过公共拦截器来做压测标记的识别。

Q: 识别到压测标记后，如何保证往下游发请求时，仍然是压测标记的形式？#

即发请求的时候已经不是同一段拦截器的代码了。但是也要保证尽可能不改动原有的业务逻辑代码。

A:
如果处理请求和发下游请求是在一个线程中完成的，那么可以使用threadLocal。
即拦截到请求时，将压测标记set进threadLocal中。
发送下游请求的代码中，如果能从threadLocal中拿到压测标记，则改造url，设置进往下发的请求中

Q: 如果我不在同一个线程中处理和发请求，怎么办？#

即我的业务代码中做了new Thread或者ExectorPool.submit提交异步请求，这时候业务逻辑里肯定不会涉及到threadLocal的代码，而此时压测标记就会丢失了。

threadLocal可以用 InheriableThreadLocal，这样如果在线程中new新的线程，则标记可以被传递下来。
如果是线程池创建异步请求，可以用阿里的TransmittableThreadLocal。

Q: 如果我的压测链路中包含了外部服务的接口怎么办？例如第三方支付、第三方短信等。#

A:
链路跟踪系统中发请求的filter中，新增MockFilter，如果判断是压测请求，则直接返回mock逻辑（不建议部署mock服务，因为部署mock服务的话，服务器成本又得考虑，不如直接封装到mockFilter代码中）

Q: 会对数据库产生影响的压测请求怎么办？#

如果直接落库，可能会影响正常用户的请求访问，也可能污染线上数据。
A:
为每个生产库生成一个影子库，专门用来存储压测数据。

然后做过分库分表的话，肯定有数据库的proxy，在proxy里都往压测库插入和读写。
如果没有，就扩展Spring的AbstactRoutngDataSource类，实现一个动态的数据源，让里面可以根据压测标记进行切换。

Q: redis、kafka等中间件对压测有什么特殊处理？#

A:
除了添加统一特点的压测标记（中间件和业务不是强相关，所以可以进行特定改造）
还要注意缓存的存活时间要设置短一点。

Q: 压测结束时，如何避免对数据库继续产生影响？#

A:
注意不要触发数据源的init-method方法，当真正执行压测的时候再建议会话连接。
各种超期时间也要注意设置，尽快接触压测对组件的影响。

Q: 压测数据怎么构造？一个个手动拼数据参数，然后让测试同学发送吗？#

A:
不行，如果业务有改动，参数很容易对不上，同时组装过程耗时也会非常久。

建议从线上直接dump最近的请求数据，这样可保证参数没有变化。
同时做一些脱敏和修正处理。

Q: 怎么完整设计这个压测系统的架构？包含哪些角色#

A:

压测manager服务，提供给压测控制者查看和使用的。可以读取mysql数据库获取压测结果情况，或者进行调度指令的下发等。
taskService服务，用于处理调度指令，执行定时调度、即时调度等行为。
Agent 压测请求发送客户端。根据taskService的指令进行发送
DataFactoy，给agent提供脱敏、修改后的压测数据。
MQ，接收agent压测请求的结果，堆积到队列里提供给DataCollect消费。
DataCollect，压测结果消费者，将结果写入到数据库MYSQL。
注册中心，用于管理和注册上面这些服务。
Detecotr，流量检测和干预器，可以根据情况即时调整agent的发送速率。

Q: 怎么模拟实际用户的请求发送？因为实际场景应该是多个不同ip的用户访问进来才对。#

A:

apache HttpComponents的httpclient包
Java11的异步httpclient，支持HTTP/2，支持用reactive stream。

高并发/高压场景处理设计

发表于 2022-09-21 分类于后台开发知识，系统设计阅读次数： Valine：
本文字数： 3.9k 阅读时长 ≈ 4 分钟

Q: 吞吐量（TPS）是什么
Q: QPS是什么
Q: QPS和TPS的区别？
Q: TP是什么？
Q: 接口访问量过大会发生什么？
Q: 应对高并发、大流量有哪些常见手段？
Q: 什么是流量的漏斗模型？
Q: 如何做接口限流？
Q: 如何设计一个限时抢购的功能
Q: 如何在产品设计上进行削峰？
Q: 如何避免高并发写的场景下的数据库超卖问题
Q: 如果库存充足，无论多少的写请求都一次性打给数据库吗？（和限时抢购不同，不考虑写失败）
Q: WATCH的原理是什么？
Q: redis写成功，那什么时候同步到数据库呢？
秒杀系统设计题

[toc]

Q: 吞吐量（TPS）是什么#

A:
TPS：Transactions Per Second（每秒传输的事物处理个数），即服务器每秒处理的事务数。
TPS包括一条消息入和一条消息出，加上一次用户数据库访问。（业务TPS = CAPS × 每个呼叫平均TPS）

对于无并发的应用系统而言，吞吐量与响应时间成严格的反比关系，实际上此时吞吐量就是响应时间的倒数
对于并发系统而言，有你n个用户使用时，每个用户看到的响应时间通常并不是n×t，而往往比n×t小很多（因为并发执行，很多资源是交叉使用的）
吞吐量是一个比较通用的指标，两个具有不同用户数和用户使用模式的系统，如果其最大吞吐量基本一致，则可以判断两个系统的处理能力基本一致

Q: QPS是什么#

A:
(Query Per Second)
每秒查询率QPS是对一个特定的查询服务器在规定时间内所处理流量多少的衡量标准
在因特网上，作为域名系统服务器的机器的性能经常用每秒查询率来衡量。对应fetches/sec，即每秒的响应请求数，也即是最大吞吐能力。（看来是类似于TPS，只是应用于特定场景的吞吐量）

Q: QPS和TPS的区别？#

A:
QPS是最大吞吐能力。
TPS是针对单个请求的简单事务处理能力判断。更多是针对单个接口而言。

Q: TP是什么？#

A:
响应时间是指系统对请求作出响应的时间。是用户感知的时间，响应时间小于100毫秒应该是不错的，响应时间在1秒左右可能属于勉强可以接受，如果响应时间达到3秒就完全难以接受了。

Q: 接口访问量过大会发生什么？#

A:
服务器可能会崩溃。
服务器对于请求都是排队的，负载不大的时候感觉不到，因为都是1秒内处理了。
当请求数量上去后，就开始有感觉了。继续增大的话，队列会占满了，服务器开始丢弃部分请求
继续增大网络请求，操作系统的TCP协议栈也开始丢弃请求，对外表现为服务器网络也连不上了。
继续增大的话，网卡硬件部分开始满速运行，然后就看操作系统驱动和硬件质量了。
另一种说法：

当访问量大的时候，后端发送给数据库的请求多，数据库并发读取或写入，受系统io影响，服务器磁盘io是固定的，一般受硬盘硬件读写影响，读写越多，io越高，到达上线就会等待，出现io等待，CPU就会等待，内存也会占用不释放，然后越来越多的请求阻塞，恶性循环，系统资源耗尽，系统崩溃，这也是为什么要提高性能，各种做缓存，从cdn到业务层缓存，代码编译缓存，数据库缓存

Q: 应对高并发、大流量有哪些常见手段？#

A:

扩容——提升集群并行处理能力
静态化——静态数据由cdn返回
限流
缓存
队列——当上下游处理能力存在差距时，通过队列形成漏斗，等下游有处理能力时自己来消费。

Q: 什么是流量的漏斗模型？#

A:
即流量要经过的系统如同漏斗一样，访问db应当是最少也最后才到达的地方

Q: 如何做接口限流？#

A:

对客户端、前端限速，复杂业务操作例如验证码等，或者短时间内限制频繁操作次数上限。
如果自己这个接口是基础接口，被内部调用，则也要限制内部服务的并发，单纯增加服务A和B的数量，基础服务没跟上，会造成雪崩效应。
使用漏桶算法

不管服务调用多么不稳定，我们只固定进行服务输出，比如每10毫秒接受一次服务调用。既然是一个桶，那就肯定有容量，由于调用的消费速率已经固定，那么当桶的容量堆满了，则只能丢弃了
实现方面，可以先准备一个队列，当做桶的容量，另外通过一个计划线程池（ScheduledExecutorService）来定期从队列中获取并执行请求调用，当然，我们没有限定一次性只能从队里中拿取一个请求，比如可以一次性拿100个请求，然后并发执行
缺点：严格限制的吞吐量，无法响应瞬发性的高峰流量。

使用令牌桶算法

生成令牌的速度是恒定的，而请求去拿令牌是没有速度限制的。这意味，面对瞬时大流量，该算法可以在短时间内请求拿到大量令牌，而且拿令牌的过程并不是消耗很大的事情。
令牌桶源码解读
计数器算法
在单位时间内，有一个专门的计数器进行计数，每请求一次计数器就+1，。单位时间内如果到达阈值，则后续请求进行限流处理。只有时间临界点到达后，才会重置，新的请求才能访问。

单位时间计数器可以用redis的setnx实现
要在 10 秒内限定 20 个请求，那么可以在 setnx 的时候设置过期时间 10，当请求的 setnx 数量达到 20 的时候即达到了限流效果。
Redis Setnx（SET if Not eXists）命令在指定的 key 不存在时，为 key 设置指定的值。

也可以用redis的zset实现
将请求打造成一个zset数组，当每一次请求进来的时候，value保持唯一，可以用UUID生成，而score可以用当前时间戳表示，因为score我们可以用来计算当前时间戳之内有多少的请求数量。而zset数据结构也提供了range方法让我们可以很轻易的获取到2个时间戳内有多少请求

Q: 如何设计一个限时抢购的功能#

例如每个商品都有特定的可抢购次数例如10w，但是如果同时打进来可能直接导致数据库出现较大的负载压力。

A:
应用层代码里用简单的时间片算法，某一时间内阈值是1000，时间到了后就拒绝后面用户的抢购，时间点到了后再允许接收。
同时开发一个接口，支持动态修改其中的各个参数。

另外如果商品数量过多，每个商品都有阈值，可能总量会超出，所以要根据商品总量动态调整每个商品的阈值上限。

Q: 如何在产品设计上进行削峰？#

A:

高流量活动分时段进行，例如抢购5000个商品，分5个时间段，每个时间段开放1000个。
答题验证，验证码

Q: 如何避免高并发写的场景下的数据库超卖问题#

A:
在Innodb中使用乐观锁来实现写入。
每次写入前先查出商品剩余量和version
调用update的时候加上where version条件，如果version发生变化，自然就会update失败，于是进行重试。

虽然还是会占行锁，但是不会造成请求线程阻塞。

Q: 如果库存充足，无论多少的写请求都一次性打给数据库吗？（和限时抢购不同，不考虑写失败）#

A:
可以使用redis缓存做库存扣减。

客户端调用WATCH + （商品id）这个命令
调用MULTI命令标记事务块的开始
输入写命令。
调用EXEC进行事务提交
如果商品的缓存值在WATCH后被修改了，则EXEC会失败， redis之后再重试即可。

Q: WATCH的原理是什么？#

A:
redis服务端会维持一个监听key的客户端链表
当key发生变化之后，这个key对应的客户端会被标记成REDIS_DIRTY_CAS状态
当接收到后面这个客户端的EXEC请求时，就返回执行失败。

Q: redis写成功，那什么时候同步到数据库呢？#

A:
将写成功的消息写入雕铣队列，通过消息队列来实现削峰，确保写入数据库时的流量可控。

秒杀系统设计题#

秒杀系统，库存只有一份，所有人会在集中的时间读和写这些数据，多个人读一个数据

Q: 设计一个秒杀系统大概要在哪些层面设计？#

A:
首先考虑重要优化点：

将请求尽可能拦截在上游。因为实际上写操作不会有那么多。
充分利用缓存。因为大部分失败的人都是读操作。
那么基于这2点，设计下面的架构：
浏览器端，最上层，会执行到一些JS代码
站点层，这一层会访问后端数据，拼html页面返回给浏览器(即和浏览器直接交互的）
服务层，向上游屏蔽底层数据细节，提供数据访问（即直接提供数据查询的服务，这里数据实际读取和返回前台响应分成了2个服务）
数据层，最终的库存是存在这里的，mysql是一个典型（当然还有会缓存）

各部分优化措施如下：

浏览器和APP：做限速
站点层：按照uid做限速，做页面缓存
服务层：按照业务做写请求队列控制流量，做数据缓存
数据层：闲庭信步

Q: 浏览器层可以怎么拦截？#

A:
验证码、短时间内访问次数限制。分段销售

Q: 站点层怎么防护？#

A:
站点层根据用户id做请求计数， uid只能5秒通过一次。这样可以避免恶意用户频繁用一个uid绕过客户端限制去下单。
同时补充页面缓存。

Q: 10w个不同的uid同时打入，站点层缓存拦不住了，到服务层了，怎么办？#

A:
服务层设计一个请求队列，每次只透有限的写请求去数据层
读请求怎么办？用数据缓存。cache缓存动态扩容。热点发现

Q: 写队列满了怎么办？#

A:
最坏的情况下，缓存了若干请求之后，后续请求都直接返回“无票”（队列里已经有100w请求了，都等着，再接受请求也没有意义了）

Q: 秒杀后未支付，怎么办？#

A:
数据库里一个状态，未支付。如果超过时间，例如45分钟，库存会重新会恢复（大家熟知的“回仓”）

Q: 系统做了主从读写分离时，怎么保证写之后能马上读到新数据？#

A:
用切面的方式做注解
通过注解判断哪些请求走主库，哪些请求走从库
例如有些场景写之后马上就读的概率很高，那就走主库
如果有些场景对读的实时性要求不高，那就从走从库
或者用一些mycat中间件。

动态规划

发表于 2022-09-20 更新于 2022-09-21 分类于编程，算法大全，其他阅读次数： Valine：
本文字数： 3.6k 阅读时长 ≈ 3 分钟

1+4的思考套路
- 简单例子
- 进阶版，二维的动态规划
其他类似题目练习

[toc]

以后不定期更新一些算法方便自己的思考和总结。

平时练习算法题学习算法知识时，经常会发现题解里写着“动态规划”，里面一上来就是一个复杂的dp公式，对于新人来说除了说声

剩下就是疑惑，他是怎么想到这个公式的？我能想到吗？这玩意工作中有用吗？
加上“动态规划”这高端的名字，然后就劝退了不少试图去理解他的人。

动态规划听起来太吓人，可以换个说法

我在内心更喜欢叫他“状态缓存”
如果是服务开发，相信很熟悉这个词语，利用缓存来加快一些重复的请求的响应速度。
而这个缓存的特点是 和其他缓存有所关联。

比如我们的服务要计算7天内的某金钱总和，计算后要缓存一下。
后来又收到一个请求，要计算8天内的金钱总和
那我们只需要取之前算过的7天内的金钱综合，加上第8天的金钱就行了。

1+4的思考套路#

自己针对动态规划总结了一个自己的思考套路，我叫他1组例子4个问题，就叫1+4好了，通过这5个过程，可以站在普通人的角度（就是非acm大佬那种的角度），去理解动态规划是如何被思考出来的

在超时的思路上写出一组计算过程的例子
在超时例子的基础上，有哪些重复、浪费的地方？
如何定义dp数组
状态的变化方向是什么，是怎么变化的
边界状态是什么

简单例子#

以一道简单题为例：
爬楼梯：
https://leetcode-cn.com/problems/climbing-stairs/

这时候就要静下心，观察这个解法的例子中是否有重复经历的场景，而这个重复经历的场景就叫状态。
我处理动态规划的题目时，都会问自己3个问题，一般就能顺利地解决。

①在超时的思路上写出一组计算过程的例子#

如果我们考虑最简单的解法，就是从起点开始，每次选择走1步或者走2步，看下能否走到终点，能走到则方法数+1。
但这种方法注定超时（O（n^2)）
但我还是照着这个过程模拟了一下，随便列了几个
1 ->2-> 3-> 4-> 5
1 ->2 ->3-> 5
1->3->4->5
1->3->5

②在超时例子的基础上，有哪些重复、浪费的地方？#

在上面，我发现了重复的地方

也就是说
从3到5总共就2种路线，已经在1->2之后计算过了，我后面从1走到3再往后走时，没必要再去算了。
换言之，当我走到3的时候，其实早就可以知道后面还剩下多少种走法。
发现重复的地方后，就可以开始建立dp公式了。

③如何定义dp数组？#

定义dp数组，也就是定义上面提到的重复的地方。重新看下之前的那句话
当我走到3的时候，其实早就可以知道后面还剩下多少种走法。
所以dp[3]代表的就是从3往后，有多少种可走的方法。

④状态的变化方向是什么，是怎么变化的#

首先思考状态的变化方向
重新看这句话：

当我走到3的时候，其实早就可以知道后面还剩下多少种走法

说明结果取决于往后面的状态
因此我们要先计算后面的状态, 即从后往前算

接着思考这个后面的状态和当前的状态有什么联系，是怎么变化的

这个一般都包含在题目条件中
根据题意，要么走2步，要么走1步，因此每当我走到一层时，下一次就2种状态可以变化。
那么对于第3层而言，他后续有2种走法，走1步或者走2步
那么他的情况就是dp[3] = dp[3+1] + dp{3+2}
如果层数设为i，那么这个变化情况就是
dp[i] = dp[i+1] + dp[i+2]

⑤边界状态是什么？#

边界状态就是不需要依赖后面的状态了，直接可以得到结果的状态。
在这里肯定就是最后一层dp[n]，最后一层默认是一种走法。 dp[n]=1

实现#

根据上面的过程，自己便定义了这个状态和变化

定义：dp[i] : 代表从第i层往后，有多少种走法
方向和变化：dp[i] = dp[i+1] + dp[i+2];
边界: dp[n] = 1
根据这个写代码就很容易了
代码：

    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[n] = 1;
        dp[n-1] = 1;
        for(int i = n-2; i >=0;i--) {
            dp[i] = dp[i+1] + dp[i+2];
        }
        return dp[0];
    }

进阶版，二维的动态规划#

https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/

①在超时的思路上写出一组计算过程的例子#

超时的思路肯定是像搜索一样模拟所有的行走过程。
先假设1个steps=5, arrlen=3的情况
随便先列几个。模拟一下不断走的位置。数字指的是当前位置。
0->1->2->1->0->0
0->1->2->1->1->0
0->1->1->1->1->0
0->1->1->1->0->0
0->0->1->1->1->0
……

②在超时例子的基础上，有哪些重复、浪费的地方？#

0->1->2->1->0->0
0->1->2->1->1->0
0->1->1->1->1->0
0->1->1->1->0->0
0->0->1->1->1->0
0->0->1->1->0->0
我发现这部分标粗的部分重复了，
换句话说
当我还剩2步且当前位置为1的时候，后面还有多少种走法，其实早就知道了。

③如何定义dp数组？#

重新看这句话：

当我还剩2步且当前位置为1的时候，后面还有多少种走法，其实早就知道了。

涉及了2个关键因素: 剩余步数和当前值，所以得用二维数组
因此
dp[realstep][index]
就代表了剩余步数为step且位置为index时，后续还剩多少种走法。

④状态的变化方向是什么，是怎么变化的#

先思考变化方向
“当我还剩2步且当前位置为1的时候，后面还有多少种走法，其实早就知道了。”

这个后面是指啥，后面会怎么变?
后面肯定是步数越来越少的情况，并且位置会根据规律变化。所以变化方向是步数变少，位置则按照规定去变。
那么这个固定越来越少的这个“剩余步数”，就是核心的变化方向
我们计算时，可以先计算小的剩余步数的状态，再去算大的剩余步数。

如何变化
根据题意和方向，剩余步数肯定-1，然后位置有3种选择（减1，不变，加1），那么方法就是3种选择的相加
dp[step][index] = dp[step-1][index-1] + dp[step-1][index] + dp[step-1][index+1]

⑤边界状态是什么？#

剩余步数为0时，只有当前位置为0才是我们最终想要的方案，把值设为1并提供给后面用，其他位置且步数为0时都认为是0。
dp[0][0] = 1；
dp[0][index] = 0；（index>0)

实现#

那么最终出来了

定义：dp{realstep][index]: 剩余步数为step且位置为index时，后续还剩多少种走法。
方向和变化：dp[step][index] = dp[step-1][index-1] + dp[step-1][index] + dp[step-1][index+1]
边界: dp[0][0] = 1；

内存溢出处理#

不过这题因为是困难题，所以给上面这个公式设立了一个小难度：

数组长度非常大，导致如果index的范围我们选择为0~arrLen-1, 那么最大情况dp[500][10^6]注定超时内存范围。
这时候就要去思考index设那么大是不是没必要
一般我们可以自己列这种情况的小例子，例如
step=2, arr=10
然后看下index有没有必要设成0~9，随便走几步
0->1->0
0->1->0
0->0->0
嗯？我发现就3种情况，arr后面那么长不用啦？
于是发现规律：
剩余的步数，必须支撑他返回原点！
也就是说，其实index的最大范围最多就是step/2，不能再多了，再多肯定回不去了。
于是问题解决。

其他类似题目练习#

https://leetcode-cn.com/problems/minimum-cost-for-tickets/

状态压缩的位dp，尽量从0往上更新，往后面看而不是往前面看

698. 划分为k个相等的子集 - 力扣（LeetCode）

微服务心跳管理机制设计

发表于 2022-09-19 分类于后台开发知识，系统设计阅读次数： Valine：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

基于LRU实现百万级别的心跳监控服务
另一个方式：时间轮
- Q: java的DelayQueue类原理知道吗？
- Q: 时间轮和 java的delayQueue）有什么区别？

[toc]

笔记来源：
实战：单机如何实现管理百万主机的心跳服务

基于LRU实现百万级别的心跳监控服务#

1. Q: 百万级别节点，如何快速找到离线的节点？（非数据库存储模式）#

全部遍历找超时，O(n)，百万级别节点消耗非常大，遍历时可能会因为涉及更新的同步问题，导致此时无法插入。
如果用单线程，这个过程慢的话会造成阻塞。

实现方式1： LRU+链表+哈希表
① 所有心跳放进一个LRU队列中，保证最新的心跳包在队尾，最老的心跳包在队头。
② 如果某节点有新的心跳包进来，利用哈希表找到这个节点的链点位置，删除掉，再将新包插入到队尾。
③ 每次心跳检查时，只要查询队头，不断将超时的心跳包出队，直到队头的心跳包不超时即可。

实现方式2：时间轮，时间轮的做法见最后

2. Q: 如何保证心跳服务的可靠性？#

上面提到的心跳检查都在内存中，心跳检查节点如果只有1个的话不可靠，而且量级也会很大。
但又不能落盘，这会导致数据库的并发查询压力很大，且数据库自身的可靠性又会成了问题。

解决方式：
分布式处理。
心跳入口网关根据节点的ip或者节点id做哈希，确保相同节点的心跳包发往同一个节点。
如果网关发现某个节点挂了，利用哈希一致算法更新发送的节点即可。

3. Q: 如何提升单个心跳服务节点的心跳接收性能？#

收到心跳后，涉及心跳的解包，LRU+哈希更新，需要提升处理性能。

① 多线程处理，同样利用上面的方法做哈希，分配到特定的心跳处理线程，不同线程之间处理的节点信息不会互相干扰。

注意点：缓存队列放到各自的工作线程中。即push而非pull的方式，尽可能避免N之间的竞争，即只做1+1的竞争。

队列锁采用自旋锁，避免工作线程频繁出现上下文切换（即保证工作线程一直在跑，这个用于高并发场景，高并发场景不能让他停下来的）

② 心跳包资源池减少内存释放频率
如果只有10w个节点，那么每次收到心跳请求时，不要反复new新的心跳对象，而是从心跳资源池里取出构造好的对象，把最新时间set进去后再扔给分发线程。

4. 心跳包选用TCP还是UDP？#

满足以下条件的话选择UDP:

心跳包报文长度内容信息量很少，基本小于MTU，不需要利用TCP自带的分包机制。
超时判断时间允许偶然一次的不可靠丢包（即偶尔丢一次并不影响）

这种情况用UDP在网内发到心跳服务即可。
不需要TCP那样的高消耗。

另一个方式：时间轮#

参考自TimingWheel 时间轮详解

时间轮本质：

弄一个数组（看起来是一个环，实际上是数组）
数组中中每个节点又存了一个双向链表，用于存放实际的任务（用链表是为了方便插入）
任务具体放数组中的哪个位置？根据超期时间取余决定他的实际存放位置。
如果数组的节点中有任务，会把本身的超期时间带着一起扔进一个队列中
队列每次取队头数据，如果时间没到队头节点指定的延迟时间，就阻塞，直到时间到达，取出里面的任务逐个执行。
如果任务的定时时间超过整个环的时间？则新增一个时间轮，时间比这个更长，因此队列里可能会多插入一个节点，节点中会标识我是小时间轮还是大时间轮的。

其他的延时队列怎么做的?
延时队列实现的几种姿势

Q: java的DelayQueue类原理知道吗？#

A:

有一个优先队列，放入的任务会根据是否快要超期进行排序，马上就要超期的会放在队头。
当使用take方法取数据时，看一下队头任务，如果时间到了就返回。
如果时间还没到

首先看一下是否已经有线程在等待这个任务了，如果是的话，使用锁的condition机制做await等待。
如果没有线程正在等待，就计算还差多少时间，然后用 LockSupport.parkNanos()让这个调用take方法的线程等待特定时间。

注意等待期间，会释放锁，因此这期间可以正常offer和take。
当时间到了后，这个线程肯定能取走数据了。取完后，顺便看一下队列里还有没有数据，如果有，调用condition.signal()，通知那堆正在等待的线程，你们可以试着竞争一下取数据了。
另外每当有新的任务offer时，如果发现最新入队的数据就是马上要超期的数据，也会立刻通知等待的各位马上苏醒竞争（因为之前等待的线程认为自己还要睡一会才会有数据）

Java阻塞延迟队列DelayQueue原理及使用

Q: 时间轮和 java的delayQueue）有什么区别？#

A:
java的delayQueue本质上是用堆（优先队列）实现的。
接收任务后，直接把任务放进优先队列中，按照超期时间确定堆位置。每次poll时如果发现堆顶没到时间就阻塞，直到时间到了再poll。
取出来检查后，再加上时间扔回队列。

坏处：插入和删除的复杂度是O(logn)。

而时间轮并不会把任务扔进 queue中，而是把时间轮的槽扔进queue中。因此整个延迟队列实际上时针对槽的，不需要堆，按先入先出取数据和插槽即可，O(1)的复杂度。而后面扔进来的任务，都是往槽里的双向链表塞进去而已。

服务缓存设计

发表于 2022-09-19 分类于后台开发知识，系统设计阅读次数： Valine：
本文字数： 4.8k 阅读时长 ≈ 4 分钟

本地缓存
分布式缓存
缓存热点
数据一致性

[toc]

本地缓存#

Q: 什么是本地缓存？#

A:
即在客户端、应用端进行本地缓存，或在jvm中缓存或在程序的堆外缓存。中间没有跨网络的开销

Q: 有哪些本地缓存产品？#

A:

Ehcache(Hibernate的二级缓存就用的这个）
GuavaCache（轻量，易用，有丰富的被动更新机制）
MapDb(支持堆外内存）

Q: 本地缓存有什么缺点？#

A:

本地缓存会占用jvm有限的内存资源
高潮gc次数过快可能会导致贤者时间（stopworld）的延长。
只在本地缓存，容易引发数据不同步。

Q: 本地缓存有哪些更新方式？#

A:

被动更新
通过自己设置的超时时间，超期后就自动进行更新，更新就是去重新发请求获取。。
主动更新
数据发生变更，主动通过消息队列的方式同步给订阅的应用（适用于内部服务配置订阅），应用进行更新。

Q: 被动更新本地缓存有什么要注意的地方？#

A:
如果同时失效的缓存很多，需要控制更新时的线程必须只有1个，如果支持同时触发多个线程进行请求更新，可能导致大量请求打到分布式缓存上引发雪崩。
两种方式：

expireAfterWrite，各超期的缓存起线程准备发请求时，需要先抢到锁，抢到了才能发，否则就阻塞（对性能要求不高可以选这个）
refreshAfterWrite，也是抢锁，区别是如果抢不到，就返回旧值，等下次超期再抢。（数据实时性要求不高的情况下可以选择这个）

Q: 什么是off-heap技术？有什么好处#

A:
堆外内存技术，将数据存在jvm外的操作系统内存上，避免和原jvm进程互相干扰，因此也不会参与垃圾收集器gc。
好处：

减少gc次数
扩展和使用更大的内存空间
省去了物理内存和heap进程内存之间的数据复制步骤，类似于零拷贝了。

Q: 怎么使用off-heap？#

A:

NIO有个ByteBuffer.allocateDirect(int capacity)方法，可以生成一个DirectByteBuffer实例
根据参数capacity的值，它会在物理内存中分配一块固定大小的直接字节缓冲区。
本质上是调用sum.misc.unsafe里实现的native方法进行内存分配操作。
可用-XX：MaxDirectMemorySize限制总的最大堆外申请大小，避免申请过多。

Q: directByteBuffer的内存什么时候会被释放？需要自己写C++代码释放吗？#

A:
不需要。 directByteBuffer在jvm中仍然是段引用，只不过buffer数据存到堆外了。当这个buffer引用被回收了，那么buffer背后的堆外内存也会被回收。

分布式缓存#

Q: 一致性哈希是做什么的？#

A:
https://blog.csdn.net/qq_42046105/article/details/92802476
普通的哈希表算法一般都是计算出哈希值后，通过取余操作将 key 值映射到不同的服务器上
但是当服务器数量发生变化时，取余操作的除数发生变化，所有 key 所映射的服务器几乎都会改变，这对分布式缓存系统来说是不可以接收的。
一致性哈希算法能尽可能减少了服务器数量变化所导致的缓存迁移。

以分布式缓存场景为例，分析一下一致性哈希算法环的原理。
首先将缓存服务器（ ip + 端口号）进行哈希，映射成环上的一个节点，计算出缓存数据 key 值的 hash key，同样映射到环上，并顺时针选取最近的一个服务器节点作为该缓存应该存储的服务器。具体实现见后续的章节。

服务器 B 宕机下线，服务器 B 中存储的缓存数据要进行迁移，但由于一致性哈希环的存在，只需要迁移key 值为1的数据，其他的数据的存储服务器不会发生变化。这也是一致性哈希算法比取余映射算法出色的地方。

现实情况下，服务器在一致性哈希环上的位置不可能分布的这么均匀，导致了每个节点实际占据环上的区间大小不一。

这种情况下，可以增加虚节点来解决。通过增加虚节点（即A节点实际对应好几个虚节点），使得每个节点在环上所“管辖”的区域更加均匀。

这样就既保证了在节点变化时，尽可能小的影响数据分布的变化，而同时又保证了数据分布的均匀。

Q: 分槽算法是什么？#

A:
在redis官方给出的集群方案中，数据的分配是按照槽位来进行分配的，每一个数据的键被哈希函数映射到一个槽位，redis-3.0.0规定一共有16384个槽位，当然这个可以根据用户的喜好进行配置。当用户put或者是get一个数据的时候，首先会查找这个数据对应的槽位是多少，然后查找对应的节点，然后才把数据放入这个节点。这样就做到了把数据均匀的分配到集群中的每一个节点上，从而做到了每一个节点的负载均衡，充分发挥了集群的威力。

Redis 集群有16384个哈希槽,每个key通过CRC16校验后对16384取模来决定放置哪个槽.集群的每个节点负责一部分hash槽

当需要增加节点时，只需要把其他节点的某些哈希槽挪到新节点就可以了；
当需要移除节点时，只需要把移除节点上的哈希槽挪到其他节点就行了；

一致性哈希和分槽算法

Q: 缓存穿透是什么?解决方式是？#

A:
大量不存在的请求攻入，反复去查询数据库
对于不存在的数据，可以用布隆过滤器（对1个值做多个不同的哈希，放入不同的位图位置里，后面计算的时候，看下是否有1个位置没满足，没满足就一定不存在）

Q: 缓存中的布隆过滤器是什么？

A:

回答1
回答2

Q: 要是分布式缓存发生雪崩了怎么办，要怎么防止发生#

A:
缓存雪崩可能是因为数据未加载到缓存中，或者一大堆缓存在同一时间大面积的失效过期，从而导致所有请求都去查数据库，导致数据库CPU和内存负载过高，甚至宕机。

解决方式：

缓存失效可以通过加锁或队列来控制读取数据库的访问的线程数量，比如对某个key值运行一个线程访问数据库，其他线程等待
不同的key，设置不同的过期时间，让失效的时间点尽量均匀或者随机，避免一下子大面积失效。
做二级缓存，a1失效时候，访问a2，a1失效的时间设置为短期，a2为长期

Q: 几十万的用户同时访问某个数据，但这个数据正好缓存里没有，导致十几万的请求打到数据库上，这种情况叫做什么？怎么解决？#

A:
这种情况叫做 ”缓存击穿“。

延长热点数据的缓存超期时间。提前预置热点缓存。
接口限流、降级、队列。

Q: 缓存过多时，如何进行筛选和淘汰？#

A:

没啥人用的数据占用了很多内存，叫缓存污染

Redis共支持八种淘汰策略。

第一类：不淘汰

noeviction
如果满了，新的写请求就报错

第二类：淘汰部分过期数据
当缓存满却收到新的写请求时，从会过期数据中选一个淘汰。

volatile-random 随机删除过期数据中的某一个
volatile-ttl：越早过期的数据，越优先被删除
volatile-lru：局部最近最少使用（即过期数据中一直没被用过的，优先删）。
特点是会从集合中随机选N个，从N个里选一个LRU最小的删除。
好处：Redis不用维护一个巨大的链表，也不用操作链表，进而提升性能
volatile-lfu：
增加了访问次数
先在过期集合中判断访问次数，再判断LRU时间、

第三类：全部数据可能都被淘汰

allkeys-lru
allkeys-random
allkeys-lfu
和volatile的处理一样，区别是 ”所有缓存“ 而非”部分过期缓存“

缓存热点#

Q: 什么是热点Key问题？#

A:
热点问题产生的原因大致有以下两种：

用户消费的数据远大于生产的数据（热卖商品、热点新闻、热点评论、明星直播）。
在日常工作生活中一些突发的的事件，被大量刊发、浏览的热点新闻、热点评论、明星直播等，这些典型的读多写少的场景会产生热点问题。
危害：

请求分片集中，超过单Server的性能极限。
在服务端读数据进行访问时，往往会对数据进行分片切分，此过程中会在某一主机Server上对相应的Key进行访问，当访问超过Server极限时，就会导致热点Key问题的产生。
流量集中，达到物理网卡上限。
请求过多，缓存分片服务被打垮。
DB击穿，引起业务雪崩。

Q: 如何发现热点？#

最简单的方式，是提前配置热点key，需要运营人员提供相关数据。
或者搭建有自身业务特点的热点自动发现平台，通过分析日志得到热点key，及时更新热点保护。
client->Proxy->redis的proxy层做收集上报，其实类似于上面的自动发现收集。
发现动态热点数据
 秒杀系统之发现动态热点数据
redis自身有个monitor命令，可以抓取收到的命令，收集上报热点key。

Q: 如何解决热点问题？#

识别到热点后就是处理策略了。

升级为本地缓存，也就是redis前置服务增加jvm内部缓存，只针对部分热点key。
紧急扩容redis缓存（但是扩容需要过程，还涉及预热同步主节点数据问题）
拆分key分散到更多其它缓存节点避免单节点瓶颈**（redis单节点一般10w qps）**，即单独对这个热点key添加新的分片算法，分到其他本不属于的redis上。

换句话说，根本解决方式就是及时进行缓存的扩容。有种办法是重写redis的访问机制，将slave节点也用上，实现读写分离。
redis有个客户端lettuce，可以开启cluster模式下的读写分离，水平扩容slave节点来无限延申系统容量。
热点Key问题的发现与解决

Q: 如何删除热点？#

A:
然后就是删除的问题，，保证最终一致性即可，如果是本地缓存可以用MQ广播消息+超时过期的策略，当然还有些极端情况的不一致可以考虑延迟双删和binlog异步刷新

Q: 如何利用redis 实现秒杀系统？#

A:
使用Redis搭建电商秒杀系统

数据一致性#

Q: 当需要删除数据时，如果我先删缓存，再删数据库，可能会有什么问题？#

A:
删完缓存，业务代码准备去删数据库时，另一个请求打到redis这，发现不存在，于是另一个处理线程去数据库中取出了数据，并加载到了缓存中。
这导致了缓存删除了个寂寞。

核心原因是因为业务代码的删库和读-加载操作是支持并发执行的。

因此应该先删数据库，再删缓存，这样能确保不会把脏数据重新加载到内存中

Q: 网络通信正常、命令正常的情况下，先删库，再删缓存，还是有可能造成脏数据，知道为什么么？#

A:
这种情况一般是”读缓存过期“导致的。

即正好某个key的读缓存过期，被删除。
然后查询请求过来，决定查库并加载到缓存中。
此时又正好发来一个删除请求，删库+删缓存，然后又被上面的请求给重新加载了。

但是一般不考虑，因为正好过期+ 正好删除请求 + ”先删库->查询缓存->删缓存->加载缓存的顺序“ 这种概率是非常低的。

Q: 如果删了库之后，再删缓存的途中，网络临时不通怎么办？那缓存也有可能一直脏着了。#

A:
失败的话，放入一个消息队列。搞一个定时线程定期取消息队列中的消息进行处理。
为了减少业务代码耦合，弄一个独立的缓存更新程序，专门从binlog中拿更新消息进行同步。

分布式存储和事务

发表于 2022-09-19 分类于后台开发知识，系统设计阅读次数： Valine：
本文字数： 5.7k 阅读时长 ≈ 5 分钟

Q: CAP分别指什么？
Q: 为什么说CAP无法同时满足？能讲清楚3种情况吗？
Q: BASE解决方案是什么？
Q: 分布式事务种的2PC是什么？
Q: 3PC又是什么？
Q: TCC又是什么？
Q:数据库主从复制的延时问题如何解决？
Q：讲一下分布式锁的实现？
Q: 详细讲讲如何用数据库实现锁？
Q: redis的红锁是什么？解决什么问题的？
Q: 如何实现分布式的负载均衡？
Q: 主备数据库如何实现主备切换？
Q：如何防止上面的主备切换过程中的新数据丢失？
Q: 如何防止主备切换时的数据不同步？和上面的数据丢失不同，这里指的是master节点已经收到数据，但是还没有往备节点同步时就挂掉了
Q: 如何生成分布式ID？

[toc]

Q: CAP分别指什么？#

A:

C 一致性Consistency —— 多台节点之间数据一致（响应准确度）
A 可用性Availability —— 能快速响应结果，没有延迟或者等待（响应速度，不需要等待）
P 分区容错性PartitionTolerance—— 如果有一部分节点挂了，其他区节点还能提供服务（时刻能响应，不会挂）

Q: 为什么说CAP无法同时满足？能讲清楚3种情况吗？#

A:

CA 无P :
不支持分区处理请求，则仅1个节点，或者全部是时刻联通， 1个挂了，则认为系统不可用。
意味着分布式系统的意义不存在。无法扩展。违背初衷
传统的关系型数据库RDBMS：Oracle、MySQL就是CA。
CP 无A：
没有可用性。
意味着我会尽可能保证数据同步，不同步的话我就不返回。
如果有节点挂了，就用另外正在同步的节点做。
例子： redis、hbase 这类和业务实时性强相关较弱的分布式数据库
他们要保证一致性，但不一定要马上能返回结果，
AP 无C
缺失一致性。
就是因为节点同步延迟，你看到的可能和别人的页面不一样，但是至少会马上给你结果。
一般用于不重要的广告、网页推送、推荐之类的功能。

举个例子：

以这个图为例
如果必须满足P
则当DB1和DB0的网络通信断开（需要1分钟才能恢复）
N2仍旧要能够返回结果。
这时候一致性和可用性无法同时满足
如果要求有一致性，则必须等待1分钟才会恢复，则无法立刻响应结果
如果要求可用性，则必须立刻返回结果，那么无法保证DB0和DB1是一致的。

Q: BASE解决方案是什么？#

A:
BASE就是为了解决关系数据库强一致性引起的问题而引起的可用性降低而提出的解决方案。

基本可用（Basically Available）
指系统故障时，能保障核心功能可用，接口性能适当降低
软状态（Soft state）
允许存在中间状态，例如支付中、同步中，也就是允许数据延时
最终一致（Eventually Consistent）
经过一段时间后，所有节点数据都将会达到一致。如订单的"支付中"状态，最终会变为“支付成功”或者"支付失败"，使订单状态与实际交易结果达成一致，但需要一定时间的延迟、等待。

Q: 分布式事务种的2PC是什么？#

A:
2PC（ two-phase commit protocol）
两阶段提交

第一阶段：请求/表决阶段（点击放大）
问一下这些参与节点"这件事你们能不能处理成功了"，参与者节点打开本地数据库事务，完成后并不会立马提交数据库本地事务，而是先向Coordinator报告说：“我这边可以处理了/我这边不能处理”
第二阶段：提交/执行阶段（正常流程）
所有参与者节点都向协调者报告说“我这边可以处理”，协调者向所有参与者节点发送“全局提交确认通知（global_commit）”，参与者节点就会完成自身本地数据库事务的提交，并最终将提交结果回复“ack”消息给Coordinator，然后Coordinator就会向调用方返回分布式事务处理完成的结果。
第二阶段：提交/执行阶段（异常流程）
参与者节点向协调者节点反馈“Vote_Abort”的消息。此时分布式事务协调者节点就会向所有的参与者节点发起事务回滚的消息（“global_rollback”），此时各个参与者节点就会回滚本地事务，释放资源，并且向协调者节点发送“ack”确认消息，协调者节点就会向调用方返回分布式事务处理失败的结果。
缺点：性能（阻塞等待）、协调者故障、

Q: 3PC又是什么？#

A:
在两阶段提交的基础上增加了CanCommit阶段并引入了超时机制，一旦事务参与者迟迟没有收到协调者的Commit请求，就会自动进行本地commit，这样相对有效地解决了协调者单点故障的问题。

第一阶段：CanCommit阶段（确认、检查各节点状态）
第二阶段：PreCommit阶段（事务预提交，有执行节点的超时机制）
第三阶段：DoCommit阶段（同样引入超时）

Q: TCC又是什么？#

A:

补偿事务TCC协议（Try-Confirm-Cancel）
有3个阶段 Try、confirm、cancel

Try阶段：主要是对业务系统做检测及资源预留。
Confirm阶段：确认执行业务操作。
Cancel阶段：取消执行业务操作。

2PC通常都是在跨库的DB层面，而TCC本质上就是一个应用层面的2PC，需要通过业务逻辑来实现。这种分布式事务的实现方式的优势在于，可以让应用自己定义数据库操作的粒度，使得降低锁冲突、提高吞吐量成为可能。

TCC的不足之处则在于对应用的侵入性非常强，业务逻辑的每个分支都需要实现try、confirm、cancel三个操作。此外，其实现难度也比较大，需要按照网络状态、系统故障等不同的失败原因实现不同的回滚策略。

Q:数据库主从复制的延时问题如何解决？#

A:
分情况讨论

如果是写操作太多，导致binlog过多，以至于主库写和从库写都很慢——那么可以通过水平扩容的方式，打散写请求。或者用高版本mysql支持并行binlog复制
过大的事务，导致主从延时——拆分大事务语句到若干小事务中，这样能够进行及时提交，减小主从复制延时
对大表进行alter table操作，导致了表会重新生成并进行迁移。——避免业务高峰执行表修改操作，尽量安排在业务低峰期执行
从库机器规格、配置和主库不一致。 ——从库有时候规格应该比主库配置要高。
数据库的表缺少主键或者合适索引，导致更新时的主从复制延时。 —— 去检查表结构，保证每个表都有显式自增主键，并协助用户建立合适索引
从库的查询请求过多，导致性能下降——增加从库数量，打散从库的查询请求。

https://zhuanlan.zhihu.com/p/92077345

Q：讲一下分布式锁的实现？#

A:
分布式锁实现

https://blog.csdn.net/wuzhiwei549/article/details/80692278

从理解的难易程度角度（从低到高）

数据库（最简单） > 缓存 > Zookeeper

从实现的复杂性角度（从低到高）

Zookeeper >= 缓存 > 数据库

从性能角度（从高到低）

缓存（最快） > Zookeeper >= 数据库

从可靠性角度（从高到低）

Zookeeper（最可靠） > 缓存（怕主节点突然挂了，导致锁失效） > 数据库（无失效时间，挂了就gg）

Q: 详细讲讲如何用数据库实现锁？#

A:
有个locker表
分别有4个字典

锁名
持有锁的机器id
version
超时时间

先查出这个锁名所在的行数据
判断这个锁的id是否为空。
如果不为空，且机器id也不是自己，说明被人持有了，返回false。
如果为空，则会尝试去更新，使用 update 机器id where lockname=‘xxx’ and version = 刚才拿到的version+1
如果update返回的结果不为0，说明更新成功，返回true，持有锁成功。
如果update结果为0，说明抢锁失败，因为version被人改了，导致where条件不成立，没更新任何一条

抢到锁的人完成自己的事务操作后，释放锁，即把锁id清理即可。
没抢到的人自己选择等一段时间再获取，或者频繁查询。

利用的行锁和MVCC的特性实现。
图片如下：

Q: redis的红锁是什么？解决什么问题的？#

A:
解决的问题：
Redis的master节点上拿到了锁，但是这个加锁的key还没有同步到slave节点；master故障，发生故障转移，slave节点升级为master节点，导致锁丢失。

如何解决：

获取当前时间（单位是毫秒）。
轮流用相同的key和随机值在N个节点上请求锁，在这一步里，客户端在每个master上请求锁时，会有一个和总的锁释放时间相比小的多的超时时间。比如如果锁自动释放时间是10秒钟，那每个节点锁请求的超时时间可能是5-50毫秒的范围，这个可以防止一个客户端在某个宕掉的master节点上阻塞过长时间，如果一个master节点不可用了，我们应该尽快尝试下一个master节点。
客户端计算第二步中获取锁所花的时间，只有当客户端在大多数master节点上成功获取了锁（在这里是3个），而且总共消耗的时间不超过锁释放时间，这个锁就认为是获取成功了。
如果锁获取成功了，那现在锁自动释放时间就是最初的锁释放时间减去之前获取锁所消耗的时间。
如果锁获取失败了，不管是因为获取成功的锁不超过一半（N/2+1)还是因为总消耗时间超过了锁释放时间，客户端都会到每个master节点上释放锁，即便是那些他认为没有获取成功的锁。

Q: 如何实现分布式的负载均衡？#

A:

nginx的负载均衡方式
反向代理，作为代理服务器进行请求转发。
轮询：指定1个服务器ip列表，依次按顺序分配
weight权重：根据指定权重，分配的概率会变高（和服务器不同性能相关）
ip哈希算法：让特定ip都导向同一个服务器（避免不同服务器频繁获取某个用户信息）
fair响应时间算法：根据响应时间，动态调整分配优先级
url哈希：类似ip哈希，根据url哈希，一般是某个服务器会做特定接口缓存的情况。

Q: 主备数据库如何实现主备切换？#

A:
两种方式

配置中心实现。当监控系统发现异常后，运维人员手动修改配置中心的数据源信息。 shark支持了基于zk的配置中心客户端。
给主备节点部署keepalive程序。需要主备机器配置虚拟ip（类似于浮动ip),支持机器进行ip切换。
运行过程中， master和slave机器上的keepalived程序会互相发心跳，确认对方是否存货。一旦master实例出现异常，主节点的keeplive会自杀，同时slave节点开始接管这个虚拟ip。

Q：如何防止上面的主备切换过程中的新数据丢失？#

A:
数据优先插入到缓存服务，再通过消息队列插入到数据库，如果主节点挂了，可以通过failover机制重发，当切换成功后，就能插入到更新后的master节点上了（前提是failover的总时间大于主备切换的时间）

Q: 如何防止主备切换时的数据不同步？和上面的数据丢失不同，这里指的是master节点已经收到数据，但是还没有往备节点同步时就挂掉了#

A:

方法1：如果要求数据强一致，可以开启半同步复制模式，即事务提交到master时，master会先发binlog给slave，当slave响应成功后，master才会完成这个事务。（TPS较高场景不适合该模式）
方法2：就是上面提到的缓存机制，先缓存，再落库。然后再依靠 GTID（全局事务id）来保证主备数据的最终一致性。

GTID即全局事务ID (global transaction identifier), 其保证为每一个在主上提交的事务在复制集群中可以生成一个唯一的ID。GTID最初由google实现，官方MySQL在5.6才加入该功能。mysql主从结构在一主一从情况下对于GTID来说就没有优势了，而对于2台主以上的结构优势异常明显，可以在数据不丢失的情况下切换新主

如图, Server1(Master)崩溃，根据从上show slave status获得Master_log_File/Read_Master_Log_Pos的值，Server2(Slave)已经跟上了主，Server3(Slave)没有跟上主。这时要是把Server2提升为主，Server3变成Server2的从。这时在Server3上执行change的时候需要做一些计算。

这个问题在5.6的GTID出现后，就显得非常的简单。由于同一事务的GTID在所有节点上的值一致，那么根据Server3当前停止点的GTID就能定位到Server2上的GTID。甚至由于MASTER_AUTO_POSITION功能的出现，我们都不需要知道GTID的具体值，直接使用CHANGE MASTER TO MASTER_HOST=‘xxx’, MASTER_AUTO_POSITION命令就可以直接完成failover的工作。

Q: 如何生成分布式ID？#

A:

UUID
UUID.randomUUID()
UUID有5个版本，第一个版本比较好理解
基于时间戳、随机数、机器MAC地址（java中改成ip地址）生成UUID
随机性过强，不连续
数据库自增ID
需要一个单独的MySQL实例用来生成ID，给id字段加上auto_increment关键字，自动id，只不过可能会不连续（可能挂掉）
数据库多主模式
设置两个Mysql实例都能单独的生产自增ID
2个实例的自增大小相同，但是起始值不同，就能保证隔开了
不方便扩容
号段模式
从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如 (1,1000] 代表1000个ID，具体的业务服务将本号段，生成1~1000的自增ID并加载到内存
多业务端可能同时操作，所以采用版本号version乐观锁方式更新，这种分布式ID生成方式不强依赖于数据库，不会频繁的访问数据库，对数据库的压力小很多。
主流
Redis
利用redis的 incr命令实现ID的原子性自增
RDB备份可能导致id重复
AOF备份可能导致重启时间过长
雪花算法Snowflake
Snowflake ID组成结构：正数位（占1比特）+ 时间戳（占41比特）+ 机器ID（占5比特）+ 数据中心（占5比特）+ 自增值（占12比特），总共64比特组成的一个Long类型
序列号部分（12bit），自增值支持同一毫秒内同一个节点可以生成4096个ID

9种分布式ID生成方式

消息队列设计

发表于 2022-09-19 分类于后台开发知识，系统设计阅读次数： Valine：
本文字数： 2.7k 阅读时长 ≈ 2 分钟

Q: 消息队列的作用是什么？
Q: 消息队列都有什么缺点？
Q: Kafka、activeMQ、RibbitMQ、RocketMQ都有什么优缺点？
Q: 如何保证消息队列的高可用？不会因为1台消息队列服务挂掉导致服务失灵？
Q: 怎么知道leader掉线？
Q: 如何保证消息不会被重复消费？
Q: 是如何保证消息消费时一定是幂等的？
Q: 消息队列 mq 怎么保证顺序消费？
Q: 如何保证消息的可靠性传输，不会丢失？
Q:消息队列满了, 发生阻塞积压怎么办？例如突然流量峰值，几百万消息持续积压？
Q: 如果让你写一个消息队列，该如何进行架构设计，说一下你的思路？

[toc]

Q: 消息队列的作用是什么？#

A:

解耦：
通过一个MQ，发布和订阅模型（Pub/Sub模型），系统A就和其它系统彻底解耦。
需要考虑一下负责的系统中，是否有类似的场景，就是一个系统或者一个模块，调用了多个系统，互相之间的调用很复杂，维护起来很麻烦。（新增、删除接口都是要两边互相适配）
但是其实这个调用是不需要同步调用接口的（不需要等待返回），如果用MQ给他异步化解耦，也是可以的，这个时候可以考虑在自己的项目中，是不是可以运用这个MQ来进行系统的解耦。
异步：
加快接口的返回。
削峰
就是大量的请求过来，然后MQ将其消化掉了，然后通过其它系统从MQ中取消息，在逐步进行消费，保证系统的有序运行。一般高峰期不会持续太长，在一段时间后，就会被下游系统消化掉。

Q: 消息队列都有什么缺点？#

A:

系统可用性降低： MQ挂掉的话很危险
系统复杂性提高：要考虑消息没有重复消费？怎么处理消息丢失的情况？怎么保证消息传递的顺序性
一致性问题：存在关联的消息，被不同消费者消费，如果另一个消费者执行失败，如何感知和回退？

Q: Kafka、activeMQ、RibbitMQ、RocketMQ都有什么优缺点？#

A:
列出一个表格

简单记忆rabitMq和kafka的区别

kafka高吞吐，适合大数据量的实时计算、日志采集。但rabitMq的时延更小。
rabitMq基于主从， kafka则支持分布式（多副本）
rabitQq基于erlang开发， kafka用scala开发。

Q: 如何保证消息队列的高可用？不会因为1台消息队列服务挂掉导致服务失灵？#

A:
只讲一下kafka的

每个partition属于多台机器。
有一个是leader节点
leader会把数据同步到另外2台机器。
如果leader挂了，则消费者选择读取这个partition的另外2台机器

假设其中的一个leader宕机了，但是因为每个leader下还有多个follower，并且每个follower都进行了数据的备份，因此kafka会自动感知leader已经宕机，同时将其它的follower给选举出来，作为新的leader，并向外提供服务支持。

Q: 怎么知道leader掉线？#

A:
对于Kafka而言，定义一个Broker是否“活着”包含两个条件：

一是它必须维护与ZooKeeper的session（这个通过ZooKeeper的Heartbeat机制来实现）。
二是Follower必须能够及时将Leader的消息复制过来，不能“落后太多”。
Leader会跟踪与其保持同步的Replica列表，该列表称为ISR（即in-sync Replica）。如果一个Follower宕机，或者落后太多，Leader将把它从ISR中移除

更详细的解释，包括如何感知掉线（ack、zk-session）、如何选举
Kafka学习之路（三）Kafka的高可用

Q: 如何保证消息不会被重复消费？#

A: 需要消息消费者保证幂等性，同样的消息，消费2次，结果是一样的。

幂等性是什么？通俗点说：幂等性就是一个数据，或者一个请求，以相同的内容和方式给你执行多次，得保证对应的数据不会改变，并且不能出错，这就是幂等性。（这样才能做到发送者搞重试或者多发问题）

Q: 是如何保证消息消费时一定是幂等的？#

A:
需要应用服务器消费消息时是幂等的，注意消息队列不保证幂等。
消费中如果是insert相关，且只会insert1次的，通过主键判断，避免重插（消费端）
消费端业可以加一个redis，以缓存消费过的记录，重复消费可以通过redis识别，并且redis是临时缓存，不会占用太多资源。

Q: 消息队列 mq 怎么保证顺序消费？#

A:
abbitmq 中，每个消费者对应一个队列
kafka中，每个消费者对应一个 partition。 partion中是有序的。

即kafka能保证塞入partion时是有序的
因此你要求有序的那堆请求，要有相同的key映射到同一个partion

同时消费者处理的时候，也要按照核心key在内存中分配给不同的线程（内存线程使用加锁队列去获取消息），避免多线程处理的时候出现混乱

Q: 如何保证消息的可靠性传输，不会丢失？#

A:
生产者发送到 MQ的时候丢了：生产者使用ack机制，如果超时没收到，就回调nack接口做重发

MQ没发给消费者：消息持久化，如果MQ挂了，还可以从磁盘中恢复重发。（ack应该在存盘后再发给生产者）

消费端没收到数据或者消费者挂了：
关闭MQ的自动ack，在消费者的代码逻辑里自己实现ack机制，保证是自己处理完成后才发ack，而不是收到了就发ack。
对于kafka来说，消费者的ack其实就是offset。 offset不能自动发，要自己实现。

Q:消息队列满了, 发生阻塞积压怎么办？例如突然流量峰值，几百万消息持续积压？#

A:
运维根据告警信息，对queue资源和consumer资源都临时进行紧急进行人工扩容。

Q: 如果让你写一个消息队列，该如何进行架构设计，说一下你的思路？#

A:

首先MQ得支持可伸缩性
那就需要快速扩容，就可以增加吞吐量和容量，可以设计一个分布式的系统，参考kafka的设计理念，broker - > topic -> partition，每个partition放一台机器，那就存一部分数据，如果现在资源不够了，可以给topic增加partition，然后做数据迁移，增加机器，不就可以存放更多的数据，提高更高的吞吐量
其次得考虑一下这个MQ的数据要不要落地磁盘？也就是需不需要保证消息持久化，因为这样可以保证数据的不丢失，那落地盘的时候怎么落？顺序写，这样没有磁盘随机读写的寻址开销，磁盘顺序读的性能是很高的，这就是kafka的思路。
其次需要考虑MQ的可用性？这个可以具体到我们上面提到的消息队列保证高可用，提出了多副本，leader 和follower模式，当一个leader宕机的时候，马上选取一个follower作为新的leader对外提供服务。
需不需要支持数据0丢失？可以参考kafka零丢失方案

第311场周赛-104名-4题

发表于 2022-09-18 更新于 2022-09-19 分类于编程，力扣周赛记录阅读次数： Valine：
本文字数： 2.6k 阅读时长 ≈ 2 分钟

6180. 最小偶倍数 - 力扣（LeetCode）

sb题目

class Solution {
    public int smallestEvenMultiple(int n) {
        return n%2==0?n:n*2;
    }
}

6181. 最长的字母序连续子字符串的长度 - 力扣（LeetCode）

单指针直接遍历计数就好了

class Solution {
    public int longestContinuousSubstring(String s) {
        char lastC = 0;
        int len = 0;
        int res = 0;
        for (int i = 0; i < s.length();i++) {
            char c = s.charAt(i);
            if (c != lastC + 1) {
                res = Math.max(len, res);
                len = 1;
            } else {
                len++;   
            }
            lastC = c;
        }
        res = Math.max(len, res);

        return res;
    }
}

6182. 反转二叉树的奇数层 - 力扣（LeetCode）

先后序dfs记录每个点在哪个层，放进一个list

然后按层遍历哪些list，把他们的值返回来重新存放即可

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        Map<Integer, List<TreeNode>> nodes = new HashMap<>();
        dfs(root, 0, nodes);
        for (Map.Entry<Integer, List<TreeNode>> entry : nodes.entrySet()) {
            if (entry.getKey() % 2 == 0) {
                continue;
            }    
            List<TreeNode> list = entry.getValue();
            List<Integer> valus = list.stream().map(tn -> tn.val).collect(Collectors.toList());
            Collections.reverse(valus);
            for (int i = 0; i < list.size();i++) {
                list.get(i).val = valus.get(i);
            }
        }
        return root;
    }
    
    void dfs(TreeNode node, int level, Map<Integer, List<TreeNode>> map) {
        if( node == null) {
            return ;
        }
        dfs(node.left, level+1, map);
        dfs(node.right, level+1, map);
        if (!map.containsKey(level)) {
            map.put(level, new ArrayList<>());
        }
        map.get(level).add(node);
    }
}

6183. 字符串的前缀分数和 - 力扣（LeetCode）

字段树，只有1000的范围，不会超，直接构建完树后直接遍历

class Solution {
    static class Node {
        int count = 0;
        Node[] nextNodes = new Node[26];
    }
    public int[] sumPrefixScores(String[] words) {
        Node root = new Node();
        for (String word : words) {
            Node node = root;
            for (char c : word.toCharArray()) {
                if (node.nextNodes[c-'a'] == null) {
                    node.nextNodes[c-'a'] = new Node();

                }
                node.nextNodes[c-'a'].count++;
                node = node.nextNodes[c-'a'];
            }
        }
        int[] res = new int[words.length];
        int i = 0;
        for (String word : words) {
            Node node = root;
            int sum = 0;
            for (char c : word.toCharArray()) {
                if (node.nextNodes[c-'a'] != null) {
                    sum += node.nextNodes[c - 'a'].count;
                }
                node = node.nextNodes[c-'a'];
            }
            res[i++] = sum;
        }
        return res;
    }
}

扫描线（叠加区间问题）

发表于 2022-09-17 分类于编程，算法大全，数学阅读次数： Valine：
本文字数： 366 阅读时长 ≈ 1 分钟

扫描线概念
步骤
相关题目

[toc]

扫描线概念#

多个连续区间，计算叠加部分要去掉或者叠加某个价值，这种题常见于那种任务流

区间的坐标很大（一般是10^9）导致无法遍历坐标值，但你可以遍历起点和终点坐标。

则可以将这些起点和终点作为纳入扫描点，逐个按从左到右的顺序扫描,并更新所谓的“高度""，每次做宽度乘高度的计算

步骤#

将终点和起点都放入数组排序，并注意保留是起点还是终点的信息（有可能起点和终点相同，如果没保留这个标志可能导致出错）
从左到右扫描各点
扫描到某点时，先不着急更新高度，而是先计算"当前高度乘上（当前位置减去上一个位置）"。注意这个过程不需要区分是起点还是终点，都可以直接算。
计算完成后，根据是起点还是终点，来更新所谓的高度
更新上一个位置

解答错误#

排查一：数值溢出#

排查是否存在数值溢出， int要改成用long，或者根据题意在某个可能溢出的部分没有mod(10^9+7)

排查二：二分法寻找关键用例#

如果给出了用例，但是用例里的值或者数组特别多，也不存在溢出问题，说明是题意理解有错，且肯定和某个关键值有关（如果不是某个关键值，那么简单用例就该出错了）

例如：

则你应对不断二分删除里面的数据，对比结果，直到缩小用例范围，便可以调试或者打印信息来确认问题原因了。

上面这边最后可以定位到这样小的范围：

1	[[166,0,166,808],[441,0,644,435]]

从而发现是[166,0,166,808]这个数据，明明题目说是矩形，却可以允许x1和x2相等。。

Q: 为什么需要线上压测？#

Q: 全链路压测和接口压测的区别？#

Q: 业务系统如何区分压测流量？即判断哪些是压测的请求，哪些是正常的请求？#

Q: 这个压测打标的改造和适配要中间所有服务参与吗？ 改造成本会不会有点大？#

Q: 识别到压测标记后， 如何保证往下游发请求时，仍然是压测标记的形式？#

Q: 如果我不在同一个线程中处理和发请求， 怎么办？#

Q: 如果我的压测链路中 包含了外部服务的接口怎么办？ 例如第三方支付、第三方短信等。#

Q: 会对数据库产生影响的压测请求怎么办？#

Q: redis、kafka等中间件对压测有什么特殊处理？#

Q: 压测结束时，如何避免对数据库继续产生影响？#

Q: 压测数据怎么构造？一个个手动拼数据参数，然后让测试同学发送吗？#

Q: 怎么完整设计这个压测系统的架构？包含哪些角色#

Q: 怎么模拟实际用户的请求发送？ 因为实际场景应该是多个不同ip的用户访问进来才对。#

Q: 吞吐量（TPS）是什么#

Q: QPS是什么#

Q: QPS和TPS的区别？#

Q: TP是什么？#

Q: 接口访问量过大会发生什么？#

Q: 应对高并发、大流量有哪些常见手段？#

Q: 什么是流量的漏斗模型？#

Q: 如何做接口限流？#

Q: 如何设计一个限时抢购的功能#

Q: 如何在 产品设计上进行削峰？#

Q: 如何避免高并发写的场景下的数据库超卖问题#

Q: 如果库存充足， 无论多少的写请求都一次性打给数据库吗？（和限时抢购不同，不考虑写失败）#

Q: WATCH的原理是什么？#

Q: redis写成功，那什么时候同步到数据库呢？#

秒杀系统设计题#

Q: 设计一个秒杀系统大概要在哪些层面设计？#

Q: 浏览器层可以怎么拦截？#

Q: 站点层怎么防护？#

Q: 10w个不同的uid同时打入，站点层缓存拦不住了，到服务层了，怎么办？#

Q: 写队列满了怎么办？#

Q: 秒杀后未支付，怎么办？#

Q: 系统做了主从读写分离时， 怎么保证写之后能马上读到新数据？#

1+4的思考套路#

简单例子#

①在超时的思路上写出一组计算过程的例子#

②在超时例子的基础上，有哪些重复、浪费的地方？#

③如何定义dp数组？#

④状态的变化方向是什么，是怎么变化的#

⑤边界状态是什么？#

实现#

进阶版，二维的动态规划#

①在超时的思路上写出一组计算过程的例子#

②在超时例子的基础上，有哪些重复、浪费的地方？#

③如何定义dp数组？#

④状态的变化方向是什么，是怎么变化的#

⑤边界状态是什么？#

实现#

内存溢出处理#

其他类似题目练习#

基于LRU实现百万级别的心跳监控服务#

1. Q: 百万级别节点，如何快速找到离线的节点？（非数据库存储模式）#

2. Q: 如何保证心跳服务的可靠性？#

3. Q: 如何提升单个心跳服务节点的心跳接收性能？#

4. 心跳包选用TCP还是UDP？#

另一个方式：时间轮#

Q: java的DelayQueue类原理知道吗？#

Q: 时间轮和 java的delayQueue）有什么区别？#

本地缓存#

Q: 什么是本地缓存？#

Q: 有哪些本地缓存产品？#

Q: 本地缓存有什么缺点？#

Q: 本地缓存有哪些更新方式？#

Q: 被动更新本地缓存有什么要注意的地方？#

Q: 什么是off-heap技术？有什么好处#

Q: 怎么使用off-heap？#

Q: directByteBuffer的内存什么时候会被释放？ 需要自己写C++代码释放吗？#

分布式缓存#

Q: 一致性哈希是做什么的？#

Q: 分槽算法是什么？#

Q: 缓存穿透是什么?解决方式是？#

Q: 要是分布式缓存发生雪崩了怎么办，要怎么防止发生#

Q: 几十万的用户同时访问某个数据，但这个数据正好缓存里没有，导致十几万的请求打到数据库上，这种情况叫做什么？怎么解决？#

Q: 缓存过多时，如何进行筛选和淘汰？#

缓存热点#

Q: 什么是热点Key问题？#

Q: 如何发现热点？#

Q: 如何解决热点问题？#

Q: 这个压测打标的改造和适配要中间所有服务参与吗？改造成本会不会有点大？#

Q: 识别到压测标记后，如何保证往下游发请求时，仍然是压测标记的形式？#

Q: 如果我不在同一个线程中处理和发请求，怎么办？#

Q: 如果我的压测链路中包含了外部服务的接口怎么办？例如第三方支付、第三方短信等。#

Q: 怎么模拟实际用户的请求发送？因为实际场景应该是多个不同ip的用户访问进来才对。#

Q: 如何在产品设计上进行削峰？#

Q: 如果库存充足，无论多少的写请求都一次性打给数据库吗？（和限时抢购不同，不考虑写失败）#

Q: 系统做了主从读写分离时，怎么保证写之后能马上读到新数据？#

Q: directByteBuffer的内存什么时候会被释放？需要自己写C++代码释放吗？#

Q: 当需要删除数据时，如果我先删缓存，再删数据库，可能会有什么问题？#

Q: 网络通信正常、命令正常的情况下，先删库，再删缓存，还是有可能造成脏数据，知道为什么么？#

Q: 如果删了库之后，再删缓存的途中，网络临时不通怎么办？那缓存也有可能一直脏着了。#

Q: 为什么说CAP无法同时满足？能讲清楚3种情况吗？#

Q：如何防止上面的主备切换过程中的新数据丢失？#

Q: 如何防止主备切换时的数据不同步？和上面的数据丢失不同，这里指的是master节点已经收到数据，但是还没有往备节点同步时就挂掉了#

Q:消息队列满了, 发生阻塞积压怎么办？例如突然流量峰值，几百万消息持续积压？#

排查二：二分法寻找关键用例#