Neo's Blog

服务的处理能力是有客观上限的。当请求速度超过服务的处理速度时，服务就会过载。

如果服务持续过载，会导致越来越多的请求积压，最终所有的请求都必须等待较长时间才能被处理，从而使整个服务处于瘫痪状态。

与之相对的，如果直接拒绝掉一部分请求，反而能够让服务能够”及时”处理更多的请求。 我们称这种做法为限流。限流是过载保护的手段之一，目的在于保护系统不被超过服务吞吐能力的流量（或突发）打死。

常见的限流手段有固定窗口、滑动窗口、令牌桶、漏桶、BBR、brpc自适应限流等。

下面挨个介绍每一种限流算法的原理以及优缺点。

传统的基于配置的单机限流算法

第一，固定窗口

原理：维护一个窗口的两个信息：窗口开始时间、经过窗口的请求数。如果窗口内超出限制数则拒绝。如果已经进入新的窗口，则reset计数。

不足：存在临界点（窗口reset前后的瞬时）的qps会飙高，从而打死系统。

第二，滑动窗口

原理：将总的时间窗口划分为N个小格，并单独维护每一个小格的计数。通过这种方式，可以把过去一段时间内的计数信息也用上，从而让限流的统计更精确一些。

不足：窗口不可能无限划分

第三，漏桶

原理：漏桶具有固定容量，出水速率是固定常量（流出请求）如果桶是空的，则不需流出水滴。可以以任意速率流入水滴到漏桶（流入请求）如果流入水滴超出了桶的容量，则流入的水滴溢出（新请求被拒绝）

不足：无法应对突发流量

第四，令牌桶

原理：假如用户配置的平均发送速率为r，则每隔1/r秒一个令牌被加入到桶中。假设桶最多可以存发b个令牌。如果令牌到达时令牌桶已经满了，那么这个令牌会被丢弃。当一个n个字节的数据包到达时，就从令牌桶中删除n个令牌，并且数据包被发送到网络。如果令牌桶中少于n个令牌，那么不会删除令牌，并且认为这个数据包在流量限制之外。

算法允许最长b个字节的突发，但从长期运行结果看，数据包的速率被限制成常量r。

自适应限流

上面的几种算法，一定程度上确实能够保护系统不被拖垮, 但不管漏斗桶还是令牌桶, 其防护思路都是设定一个指标, 当超过该指标后就阻止或减少流量的继续进入，当系统负载降低到某一水平后则恢复流量的进入。但其通常都是被动的，其实际效果取决于限流阈值设置是否合理，但往往设置合理不是一件容易的事情。具体有如下几个弊端：

1. 集群增加机器或者减少机器限流阈值是否要重新设置?
2. 设置限流阈值的依据是什么?
3. 人力运维成本是否过高?
4. 只针对局部服务端的限流，无法掌控全局资源，
5. 当调用方反馈限流错误时, 这个时候重新设置限流, 其实流量高峰已经过了。重新评估限流是否有意义？

第五，B站BBR限流

底层原理：并发 = qps * latency

自适应限流能动态调整服务的最大并发，在保证服务不过载的前提下，让服务尽可能多的处理请求。

具体逻辑：如果cpu > 800 && inflight > rt * max_qps，则启用限流

为什么要用 CPU\IOPS 作为启发值呢？

因为自适应限流与 TCP 拥塞控制还存在不同之处，TCP 中客户端可以控制发送率，从而探测到 maxPass，但是 RPC 线上无法控制流量的速率，所以必须以 CPU 作为标准，当 CPU 快满载的时候再开启，这时我们认为之前探测到的 maxPass 已经接近了系统的瓶颈，乘以 minRtt 就可以得到 InFlight

第六，BRPC自适应限流

• peek_qps 峰值qps
• nodelay_latency 系统无负载或者低负载的响应时间，理论值无法计算
• Min_latency 用来替代nodelay_latency
• max_cocurrent = max_qps * ((2+alpha) * min_latency - latency)

名词及解释
concurrency(并发度): 同时处理的请求数，又被称为“并发度”。

max_concurrency:
设置的最大并发度。超过并发的请求会被拒绝（返回ELIMIT错误），在集群层面，client应重试到另一台server上去。

best_max_concurrency:
并发的物理含义是任务处理槽位，天然存在上限，这个上限就是best_max_concurrency，也就是最佳的最大并发度，一般推荐设置最大并发为该值，若max_concurrency设置的过大，则concurrency可能大于best_max_concurrency，任务将无法被及时处理而暂存在各种队列中排队，系统也会进入拥塞状态。若max_concurrency设置的过小，则concurrency总是会小于best_max_concurrency，限制系统达到本可以达到的更高吞吐。

noload_latency:
单纯处理任务的延时，不包括排队时间。另一种解释是低负载的延时。由于正确处理任务得经历必要的环节，其中会耗费cpu或等待下游返回，noload_latency是一个服务固有的属性，但可能随时间逐渐改变（由于内存碎片，压力变化，业务数据变化等因素）。

min_latency:
实际测定的latency中的较小值的ema，当concurrency不大于best_max_concurrency时，min_latency和noload_latency接近(可能轻微上升）。

peak_qps: 服务处理qps的上限。注意是处理或回复的qps而不是接收的qps。值取决于best_max_concurrency /
noload_latency，这两个量都是服务的固有属性，故peak_qps也是服务的固有属性，和拥塞状况无关，但可能随时间逐渐改变。

max_qps: 实际测定的qps中的较大值。由于qps具有上限，max_qps总是会小于peak_qps，不论拥塞与否。

• Little’s Law

在服务处于稳定状态时: concurrency = latency * qps。 这是自适应限流的理论基础。

服务的noload_latency并非是一成不变的，自适应限流必须能够正确的探测noload_latency的变化。当noload_latency下降时，是很容感知到的，因为这个时候latency也会下降。难点在于当latency上涨时，需要能够正确的辨别到底是服务过载了，还是noload_latency上涨了。

参考：
https://blog.csdn.net/qq_42936727/article/details/134548409

参考：

BRPC开发手册

B站在微服务治理中如何探索与实践

高性能

SendFile、zero copy

索引设计

Kafka为了卸载MQ本身的复杂性，为了其真正无状态的设计，它将状态维护机制这口锅完全甩给了消费者，因此取消息的问题就转化成了消费者拿着一个offset索引来Kafka存储器里取消息的问题，这就涉及到了性能。But 如何能查的更快？How？

但实际上，

1. partition并不是一个文件，而是一个目录
2. 目录下面存了很多逻辑上的segment，每一个segment物理上包括两个文件：索引文件、日志文件（每次都append)

文件的命名相当于查找的稀疏索引，省去索引文件

每个segment索引又是一个稀疏索引减少索引文件的大小

在 Kafka 中，生产者写入消息、消费者读取消息的操作都是与 leader 副本进行交互的，从而实现的是一种主写主读的生产消费模型。

cosume group

通过cosume group，巧妙的解决了广播问题。

16.为什么Kafka不支持读写分离？

Kafka 并不支持主写从读，因为主写从读有 2 个很明 显的缺点:

(1)数据一致性问题。数据从主节点转到从节点必然会有一个延时的时间窗口，这个时间 窗口会导致主从节点之间的数据不一致。某一时刻，在主节点和从节点中 A 数据的值都为 X， 之后将主节点中 A 的值修改为 Y，那么在这个变更通知到从节点之前，应用读取从节点中的 A 数据的值并不为最新的 Y，由此便产生了数据不一致的问题。

(2)延时问题。类似 Redis 这种组件，数据从写入主节点到同步至从节点中的过程需要经 历网络→主节点内存→网络→从节点内存这几个阶段，整个过程会耗费一定的时间。而在 Kafka 中，主从同步会比 Redis 更加耗时，它需要经历网络→主节点内存→主节点磁盘→网络→从节 点内存→从节点磁盘这几个阶段。对延时敏感的应用而言，主写从读的功能并不太适用。

replication

2.1 消息备份

Kafka允许同个Partition存在多个消息副本(Replica)，每个Partition的副本通常由1个Leader及0个以上的Follower组成，产者将消息直接发往对应Partition的Leader，Follower会周期地向Leader发送同步请求，Kafka的Leader机制在保障数据致性地同时降低了消息备份的复杂度。同Partition的Replica应存储在同一个Broker上，因为一旦该Broker宕机，对应Partition的所有Replica都无法作，这就达不到高可用的效果。为做好负载均衡并提容错能，Kafka会尽将所有的Partition以及各Partition的副本均匀地分配到整个集群上。举个例，当集群中部署3台Broker，TopicA共有4个Partition，每个Partition均有3个Replica时下图就是种合理的分布方式。

ISR:In-Sync Replicas 副本同步队列

ISR(In-Sync Replicas)指的是个Partition中与Leader“保持同步”的Replica列表(实际存储的是副本所在Broker的BrokerId)，这的 保持同步是指与Leader数据保持完全一致，只需在replica.lag.time.max.ms时间内与Leader保持有效连接，官方解释如下If a follower hasn’t sent any fetch requests or hasn’t consumed up to the leaders log end offset for at least this time, the leader will remove the follower from isr,( default value =10000 )Follower周期性地向Leader发送FetchRequest请求(数据结构见下)，发送时间间隔配置在replica.fetch.wait.max.ms中，默认值为 500。

AR:Assigned Replicas 所有副本

ISR是由leader维护，follower从leader同步数据有一些延迟（包括延迟时间replica.lag.time.max.ms和延迟条数replica.lag.max.messages两个维度, 当前最新的版本0.10.x中只支持replica.lag.time.max.ms这个维度），任意一个超过阈值都会把follower剔除出ISR, 存入OSR（Outof-Sync Replicas）列表，新加入的follower也会先存放在OSR中。AR=ISR+OSR。

ISR数据同步、ACK选项（全部ack、只有一个ack）

Kafka的复制机制既不是完全的同步复制，也不是单纯的异步复制。

完全同步复制要求All Alive Follower都复制完，这条消息才会被认为commit，这种复制方式极大的影响了吞吐率。

而异步复制方式下，Follower异步的从Leader复制数据，数据只要被Leader写入log就被认为已经commit，这种情况下，如果leader挂掉，会丢失数据。

kafka使用ISR的方式很好的均衡了确保数据不丢失以及吞吐率。Follower可以批量的从Leader复制数据，而且Leader充分利用磁盘顺序读以及send file(zero copy)机制，这样极大的提高复制性能，内部批量写磁盘，大幅减少了Follower与Leader的消息量差。

leader会维护一个与其基本保持同步的Replica列表，该列表称为ISR(in-sync Replica)，每个Partition都会有一个ISR，而且是由leader动态维护 ，如果一个follower比一个leader落后太多，或者超过一定时间未发起数据复制请求，则leader将其重ISR中移除

Log End Offset

当前broker收到的最新offset

HighWatermark

已经同步到其他slave中的offset

HW是High Watermark的缩写，俗称高水位，它标识了一个特定的消息偏移量（offset）​，消费者只能拉取到这个offset之前的消息。

LEO是Log End Offset的缩写，它标识当前日志文件中下一条待写入消息的offset，图1-4中offset为9的位置即为当前日志文件的LEO，LEO的大小相当于当前日志分区中最后一条消息的offset值加1。
分区ISR集合中的每个副本都会维护自身的LEO，而ISR集合中最小的LEO即为分区的HW，对消费者而言只能消费HW之前的消息。

Leader epoch

由于follower的HW的更新，需要一轮额外的消息拉取，如果folloer很多的话，就需要多轮拉取Leader 副本高水位更新和 Follower 副本高水位更新在时间上是存在错配的，会导致数据的
不一致，所以Leader epoch登场。

Epoch，一个单调增加的版本号。每当leader发生变更时，都会增加该版本号。小版本号的Leader 被认为是过期 Leader，不能再行使 Leader权力。

起始位移，Leader 副本在该 Epoch 值上写入的首条消息的位移类似于zookeper的leader机制，通过leader epoch的单调递增，以此避免副本宕机重启导致的消息同步错乱

epoch相关：
https://www.jianshu.com/p/469ec6dcdc02

参考：
https://blog.csdn.net/dog250/article/details/79588437

常见面试题：
https://blog.csdn.net/qq_28900249/article/details/90346599

可能的一些作用：

1. 非核心逻辑异步化，追求高性能
2. 解除耦合，Event Driven 事件驱动设计
3. 实现广播
4. 削峰填谷，把峰值流量缓冲下来，后面慢慢处理

具体可以用于：

1. 分布式事务，单方生产，多个消费业务逻辑
2. 数据复制：通过消息队列，将数据复制到多个目的地（多维度数据表、ES、Hadoop、搜索等）
3. 日志同步：多个app生产日志并放入队列，然后消费队列完成日志的离线与实时处理
4. 延迟队列：可靠的延迟队列，分布式环境定时器
5. 广播通知：Cache失效通知

消息队列的缺点

系统可用性降低：系统引入的外部依赖越多，越容易挂掉，本来你就是A系统调用BCD三个系统的接口就好了，人ABCD四个系统好好的，没啥问题，你偏加个MQ进来，万一MQ挂了咋整？MQ挂了，整套系统崩溃了，你不就完了么。

系统复杂性提高：硬生生加个MQ进来，你怎么保证消息没有重复消费？怎么处理消息丢失的情况？怎么保证消息传递的顺序性？头大头大，问题一大堆，痛苦不已

一致性问题：A系统处理完了直接返回成功了，人都以为你这个请求就成功了；但是问题是，要是BCD三个系统那里，BD两个系统写库成功了，结果C系统写库失败了，咋整？你这数据就不一致了。

主流消息队列对比

Master/Slave概念差异
Kafka：Master/Slave 是个逻辑概念，1 台机器同时是 Master 和 Slave。
RocketMQ：Master/Slave 是个物理概念，1 台机器只能是 Master 或者 Slave。

参考：https://blog.csdn.net/wdj_yyds/article/details/123534023

https://cloud.tencent.com/developer/article/2442460
https://news.sohu.com/a/739423661_411876
https://mp.weixin.qq.com/s?__biz=MzU0OTE4MzYzMw==&mid=2247561232&idx=2&sn=52bcba1f40c1fd054ad316d9b32e9f2f&chksm=fbb079eeccc7f0f8cf8f9c0d751a91ad71db53c7f6e0b68e534560fe84a8fa4f5c2e1a120a49&scene=27

分布式消息队列评价指标

可靠

分布式消息队列提供更好的可靠性，主要体现在：

1. 消息会被持久化到分布式存储中。这样避免了单台机器存储的消息由于机器问题导致消息的丢失；
2. 不佳的网络环境中，保证只有当消息的接收者确实收到消息时才从队列中删除消息。

可扩展

可扩展性体现在访问量和数据量两个方面：

访问量：分布式消息队列服务，会随着访问量的增减而自动增减逻辑处理服务器；

数据量：当数据量扩大时，后端分布式存储会自动扩容。

安全

安全体现在以下两个方面：

1. 同时使用消息队列的业务之间不会互相干扰。如果有多个业务同时在使用消息队列，对于单机的消息队列服务，一个业务的消息操作可能会影响其他业务的正常运行。比如，一个业务的消息操作特别频繁，占据了消息队列的绝大部分服务时间，也占据了这台服务器的绝大部分网络IO，导致其他业务无法正常地与消息队列通信。而且甚至可能由于服务控制不当，导致机器崩溃，服务停止，业务也跟着停止。分布式消息队列则不会出现这个问题：
   （1）监控措施完善，系统性能指数会控制在一定范围之内，而且有任何异常也会报警；
   （2）当访问量和数据量增大时，分布式消息队列服务可以自动扩展。

2. 各业务的消息内容是安全存储的，其他业务不能访问到非自身业务的数据。
   一方面是业务需要密钥来访问消息队列；另一方面，消息是被加密存储的。

简单实用

简单实用体现在：

1. 透明：接收者和发送者无需知道具体的消息队列的服务器地址，服务器的增减对接收者和发送者透明。
2. 实用：对于两个服务之间不能通信的网络情况，消息队列为他们提供了恰到好处的桥梁。

如何保证消息不丢

生产端不丢消息

生产端如何保证不丢消息呢？确保生产的消息能到达存储端。

如果是RocketMQ消息中间件，Producer生产者提供了三种发送消息的方式，分别是：

• 同步发送
• 异步发送
• 单向发送

生产者要想发消息时保证消息不丢失，可以：

• 采用同步方式发送，send消息方法返回成功状态，就表示消息正常到达了存储端Broker。
• 如果send消息异常或者返回非成功状态，可以重试。
• 可以使用事务消息，RocketMQ的事务消息机制就是为了保证零丢失来设计的

存储端不丢消息

如何保证存储端的消息不丢失呢？ 确保消息持久化到磁盘。大家很容易想到就是刷盘机制。

刷盘机制分同步刷盘和异步刷盘：
生产者消息发过来时，只有持久化到磁盘，RocketMQ的存储端Broker才返回一个成功的ACK响应，这就是同步刷盘。它保证消息不丢失，但是影响了性能。
异步刷盘的话，只要消息写入PageCache缓存，就返回一个成功的ACK响应。这样提高了MQ的性能，但是如果这时候机器断电了，就会丢失消息。

Broker一般是集群部署的，有master主节点和slave从节点。消息到Broker存储端，只有主节点和从节点都写入成功，才反馈成功的ack给生产者。这就是同步复制，它保证了消息不丢失，但是降低了系统的吞吐量。与之对应的就是异步复制，只要消息写入主节点成功，就返回成功的ack，它速度快，但是会有性能问题。

消费阶段不丢消息

如何保证消息顺序

消费者执行完业务逻辑，再反馈会Broker说消费成功，这样才可以保证消费阶段不丢消息。

消息队列保证顺序性整体思路就是这样啦。比如Kafka的全局有序消息，就是这种思想的体现: 就是生产者发消息时，1个Topic只能对应1个Partition，一个 Consumer，内部单线程消费。

但是这样吞吐量太低，一般保证消息局部有序即可。在发消息的时候指定Partition Key，Kafka对其进行Hash计算，根据计算结果决定放入哪个Partition。这样Partition Key相同的消息会放在同一个Partition。然后多消费者单线程消费指定的Partition。

如何实现消息事务

下面是RabbitMQ/RocketMQ消息事务的实现机制

1. 生产者产生消息，发送一条半事务消息到MQ服务器
2. MQ收到消息后，将消息持久化到存储系统，这条消息的状态是待发送状态。
3. MQ服务器返回ACK确认到生产者，此时MQ不会触发消息推送事件
4. 生产者执行本地事务
5. 如果本地事务执行成功，即commit执行结果到MQ服务器；如果执行失败，发送rollback。
6. 如果是正常的commit，MQ服务器更新消息状态为可发送；如果是rollback，即删除消息。
7. 如果消息状态更新为可发送，则MQ服务器会push消息给消费者。消费者消费完就回ACK。
8. 如果MQ服务器长时间没有收到生产者的commit或者rollback，它会反查生产者，然后根据查询到的结果执行最终状态。

集成：在服务提供端或者调用端，如何集成注册中心？应用内 OR 应用外

测活：服务注册之后，如何对服务进行测活以保证服务的可用性

负载均衡：当存在多个服务提供者时，如何均衡各个提供者的负载？

运行时依赖：引入注册中心之后，对应用的运行时环境有何影响？

可用性：如何保证注册中心本身的可用性，特别是消除单点故障？

状态获取：（1）主动探测（2）心跳上报

一些可能问题：

• 保护机制：如果短时间内摘除的节点数量超过集群的40%，则停止摘除节点
• 通知风暴问题（准备更多的注册中心节点；精简通知内容）

目前比较流行的解决方案包括：

Eureka还有一种自我保护机制，如果在15分钟内超过85%的节点都没有正常的心跳，那么Eureka就认为客户端与注册中心出现了网络故障，此时会出现以下几种情况：

1. Eureka不再从注册列表中移除因为长时间没收到心跳而应该过期的服务
2. Eureka仍然能够接受新服务的注册和查询请求，但是不会被同步到其它节点上(即保证当前节点依然可用)
3. 当网络稳定时，当前实例新的注册信息会被同步到其它节点中

因此， Eureka可以很好的应对因网络故障导致部分节点失去联系的情况，而不会像zookeeper那样使整个注册服务瘫痪。

参考：
http://www.360doc.com/content/21/0221/16/73848659_963189895.shtml

单体到微服务

为什么要转向微服务架构（收益）

1. 系统扩展性不足（例如，因为DB连接问题导致无法持续扩容）
2. 迭代效率低。如果是预估到业务在飞速增长，那就别犹豫，一定要提前考虑微服务的拆分。
3. 系统编译、部署成本高
4. 如果在设计架构的时候，发现需要很多异构的技术栈，那也要考虑下微服务。

转向微服务架构需要克服什么困难（成本）

1. 技术基础设施要求比较高（如果公司技术基础设施非常完备，对应的业务起初就设计的非常复杂，那么也别犹豫，起手就上微服务。）
2. 工程拆分挑战比较大，实现时容易为了拆分而拆分。

拆分原则

从单体到微服务，也许可以有一个过度：工程的拆分

微服务拆分的大原则

1. 单一服务内的高内聚、低耦合，单一职责
2. 拆分粒度：先粗拆，后细拆（伴随业务复杂度的变多，或者对业务的理解程度加深）
3. 拆分过程中，要避免影响业务的日常功能迭代—按照依赖顺序，挨个拆分
4. 确保服务接口定义有可扩展性
5. 避免环形依赖问题（通过分层，例如业务层、数据访问层）

业务优先，组织结构，质量维度

SRP Single Responsibilty 单一指责原则
CCP Common Closure Principle 共同闭包原则，包中包含的所有类应该是同类的变化的一个集合，也就是说，如果对包作出修改，需要调整的类应该都在这个包之内。

你的团队成员结构是什么样的，你的架构就会长成啥样。

团队按照业务边界来拆分；确保团队不要太大

因为微服务就是为了减少研发成本，而包括沟通成本。

服务拆分带来的问题

1. 接口调用耗时增加
2. 如何知道调用哪个服务？服务注册中心
3. 服务治理体系：熔断、限流、降级、超时控制等
4. 问题排查困难（分布式链路追踪）

微服务组件

API网关

入口网关：隔离客户端与微服务，协议转换、安全策略、认证、限流、熔断等

出口网关：调用外部API，统一认证，授权、授权、访问控制等

性能：IO多路复用、异步非阻塞、线程池

设计要点：性能、扩展性（责任链模式）

隔离性：针对接口对线程池进行分类

服务注册与发现

zookeeper, consul, euraker

负载均衡

RoundRobin, Hash, Weight

熔断、限流

配置实时下发

客户端

配置项的读取-变更推送如何实现：

1. 轮询 + 摘要 （简单，实时性略差）
2. 长轮询 + 版本号（复杂，实时性好一些）

client的高性能实现逻辑：

1. DoubleBufferedData， 数据分前台和后台
2. 读拿到自己所在线程的thread-local读写锁，执行查询逻辑后释放锁。
3. 同时只有一个写：修改后台数据，切换前后台，挨个获得所有thread-local锁并立刻释放，结束后再改一遍新后台（老前台）。

一个小原则：配置系统的旁路化，不要因为配置系统挂了，你的程序启动不了；
可以做两层缓存：内存缓存、文件保存

服务端

不同的配置类型：节点类型 》机房类型 》 全局配置

配置项的存储-配置系统的高可用

核心指标在于可用性！！！5个9？

对接调用链追踪 （Jager)

trace_id + span_id来标识链路的调用关系。

对trace_id采样，而不要随机采样。

span 基本工作单元，一次链路调用（可以是RPC，DB等没有特定的限制）创建一个span，通过一个64位ID标识它，uuid较为方便，span中还有其他的数据，例如描述信息，时间戳，key-value对的（Annotation）tag信息，parent_id(基于parent_span_id来维护树形结构）等,其中parent-id可以表示span调用链路来源。

trace_id 类似于 树结构的Span集合，表示一次完整的跟踪，从请求到服务器开始，服务器返回response结束，跟踪每次rpc调用的耗时，存在唯一标识trace_id。比如：你运行的分布式大数据存储一次Trace就由你的一次请求组成。

Annotation 注解，用来记录请求特定事件相关信息（例如时间），一个span中会有多个annotation注解描述。通常包含四个注解信息：

监控系统

方案：普罗米修斯、Graphna

APM：端到端的监控体系

如何防止消息被篡改：对消息体 + 消息头 进行加密，生成一个签名
如何对数据进行加密：

使用非对称加密的公钥对 “对称加密的私钥-OriginPrivate“ 进行加密，得到SecretPrivate
然后服务端利用非对称加密的私钥，对 SecretPrivate进行解密，得到OriginPrivate

然后再使用OriginPrivate对加密之后的消息体（SecretContext)进行解密，得到Contenxt

监控哪些东西：网络卡顿率、做某件事情的失败率等

考虑暂存 + retry来应对网络状况不佳的情况

自动化全链路压测系统

压测的原则-尽量模拟真实情况；压测的注意点：
（1）使用线上数据与线上数据
（2）使用线上流量（流量拷贝）
（3）流量应该从尽量靠近用户的CDN发起

如何搭建：
（1）流量的隔离（区分压测流量与正式流量）
（2）风险控制（尽量避免压测对正常用户的影响）

压测数据的产生：
拷贝真实流量（可以从访问日志、可以抓取某个端口的数据等）
打上压测标签
放在合适的机房（尽量接近用户）
数据隔离：
针对读请求，针对某些不能压测（例如推荐、数据分析等）的组件进行mock
对于写请求，把流量产生的数据写入影子库（数据库-拷贝一份库表和数据；缓存-加压测前缀；ES-多搞一份索引）
压力测试的实施
持续放大，做好系统过载的识别（例如超时率、resp time等）

熔断简单说明

在分布式系统中，一次完整的请求可能需要经过多个服务模块的调用，请求在多个服务中传递，服务对服务的调用会产生新的请求，这些请求共同组成了这次请求的调用链。当调用链中的某个环节，特别是下游服务不可用时，将会导致上游服务调用方不可用，最终将这种不可用的影响扩大到整个系统，导致整个分布式的不可用，引起服务雪崩现象。

为了避免这种情况，在下游服务不可用时，保护上游服务的可用性显得极其重要。对此我们可以通过熔断的方式，通过及时熔断服务调用方和服务提供方的调用链，保护服务调用方资源，防止服务雪崩现象的出现。

使用服务熔断，能够有效地保护服务调用方的稳定性，它能够避免服务调用者频繁调用可能失败的服务提供者，防止服务调用者浪费cpu、线程和IO资源等，提高服务整体的可用性。

所以，熔断设计的目的是在服务提供方不可用时保护服务调用方的资源，减少服务调用中无用的远程调用。

常见熔断策略

google SRE 自适应熔断

基于失败率

drop_ratio = $max(0, （requests - K * accepts） / (requests + 1))$

算法参数：

• requests：窗口时间内的请求总数
• accepts：正常请求数量
• K：敏感度，K 越小越容易丢请求，一般推荐 1.5-2 之间

算法解释：

• 正常情况下 requests=accepts，所以概率是 0。
• 随着正常请求数量减少，当达到 requests == K* accepts 继续请求时，概率 P 会逐渐比 0 大开始按照概率逐渐丢弃一些请求，如果故障严重则丢包会越来越多，假如窗口时间内 accepts==0 则完全熔断。
• 当应用逐渐恢复正常时，accepts、requests 同时都在增加，但是 K*accepts 会比 requests 增加的更快，所以概率很快就会归 0，关闭熔断。

brpc熔断策略

在开启了熔断之后，CircuitBreaker会记录每一个请求的处理结果，并维护一个累计出错时长，记为acc_error_cost，当acc_error_cost > max_error_cost时，熔断该节点。

两个小技巧：

1. 利用EMA（移动平均值）策略计算接口的平均响应时间;
2. 利用双时间窗口统计来平衡短期抖动与长期错误率过高;

可选的熔断由CircuitBreaker实现，在开启了熔断之后，CircuitBreaker会记录每一个请求的处理结果，并维护一个累计出错时长，记为acc_error_cost，当acc_error_cost > max_error_cost时，熔断该节点。

每次请求返回成功之后，更新max_error_cost:

首先需要更新latency的EMA值，记为ema_latency: ema_latency = ema_latency alpha + (1 - alpha) latency。
之后根据ema_latency更新max_error_cost: max_error_cost = window_size max_error_rate ema_latency。
上面的window_size和max_error_rate均为gflag所指定的常量, alpha则是一个略小于1的常量，其值由window_size和下面提到的circuit_breaker_epsilon_value决定。latency则指该次请求的耗时。

每次请求返回之后，都会更新acc_error_cost：

如果请求处理成功，则令 acc_error_cost = alpha acc_error_cost
如果请求处理失败，则令 acc_error_cost = acc_error_cost + min(latency, ema_latency 2)
上面的alpha与计算max_error_cost所用到的alpha为同一个值。考虑到出现超时等错误时，latency往往会远远大于ema_latency。所以在计算acc_error_cost时对失败请求的latency进行了修正，使其值不超过ema_latency的两倍。这个倍率同样可以通过gflag配置。

具体见：
CircuitBreaker

netflix 断路器

三种断路器状态：关闭、打开、半开

关闭 —> 打开：当故障率等于或大于可配置的阈值时，CircuitBreaker 的状态将从“关闭”更改为“打开”。

打开 —> 半开：当 CircuitBreaker 打开时，它会拒绝带有 CallNotPermittedException 的调用。经过一段等待时间后，CircuitBreaker 状态从 OPEN 变为 HALF_OPEN，并允许可配置数量的服务调用是否仍然不可用或再次变为可用。用 CallNotPermittedException 拒绝其他调用，直到所有允许的调用完成。如果故障率或慢呼叫率等于或大于配置的阈值，则状态会变回 OPEN。

半开 —> 关闭：如果故障率和慢呼叫率低于阈值，则状态将变回“已关闭”。

DISABLED：始终允许调用。

FORCED_OPEN：始终拒绝调用

最近一段时间内的错误率 = 错误数 / 总数

最近一段时间内的错误数与总数，通过滑动窗口来实现，而滑动窗口又通过环形队列来实现。

错误率超过多少，则进入打开状态，持续一段时间。

持续一段时间后，进入半开状态，允许定量的请求通过，如果成功的比例足够大，则进入关闭状态，否则重新加入打开状态。

并行排序（并行归并排序、并行快速排序）

并行查找（并行的散列表，随机分为K份）

并行字符串匹配（任何算法都可以，只是分割后，需要补上2m个char）

并行搜索（对于BFS，使用两个队列，循环使用）

多线程问题的本质：有序性，可见性，原子性

我们处理线程安全可以有几个层次：

1. 能否做成无状态的不变对象。无状态是最安全的。
2. 能否线程封闭
   （1）栈封闭，多采用局部变量
   （2）线程局部存储（用空间换性能）
   （3）程序控制线程封闭（Hash，将同一hash val的的请求丢给同一个线程去处理）
3. 采用何种同步技术

多线程同步的方式

线程同步

多个线程间的一种协作机制。谈到线程我们经常想到的是线程间的竞争，比如去争夺锁，但这并不是故事的全部，线程间也会有协作机制。就是在一个线程进行了规定操作后，就进入等待状态， 等待其他线程执行完他们的指定代码过后 再将其唤醒;
（在有多个线程进行等待时， 如果需要，可以使用 notifyAll()来唤醒所有的等待线程。）

(1) 信号量 semphore

(2) 共享内存 shared_memory

(3) 读写锁 rw_lock

(4) 条件变量 condition

线程间存在依赖

(5) 互斥量 mutex

互斥锁

对于互斥锁，如果资源已经被占用，资源申请者只能进入睡眠状态。

1. 临界区：通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。
2. 互斥量：为协调共同对一个共享资源的单独访问而设计的。
3. 信号量：为控制一个具有有限数量用户资源而设计。
4. 读写锁

自旋锁

但是自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁。如果等待的时间比较短，适合使用自旋锁，占用大量的CPU资源

锁的实现机制

在硬件层面，CPU提供了原子操作、关中断、锁内存总线的机制。

禁中断

既然只有中断才能把上锁过程打断，造成多线程操作失败。我先关中断不就得了，在加锁操作完成后再开中断。

普通的原子指令

上面这个手段太笨重了，能不能硬件做一种加锁的原子操作呢？能，大名鼎鼎的“test and set”指令就是做这个事情的。

锁内存总线 + 原子指令

通过上面的手段，单核环境下，锁的实现问题得到了圆满的解决。

那么多核环境呢？简单嘛，还是“test and set”不就得了，这是一条指令，原子的，不会有问题的。

真的吗，单独一条指令能够保证该指令在单个核上执行过程中不会被中断打断，但是两个核同时执行这个指令呢？。。。

我再想想，硬件执行时还是得从内存中读取lock，判断并设置状态到内存，貌似这个过程也不是那么原子嘛。对，多个核执行确实会存在这个问题。怎么办呢？首先我们得明白这个地方的关键点，关键点是两个核会并行操作内存而且从操作内存这个调度来看“test and set”不是原子的，需要先读内存然后再写内存，如果我们保证这个内存操作是原子的，就能保证锁的正确性了。

确实，硬件提供了锁内存总线的机制，我们在锁内存总线的状态下执行test and set操作，就能保证同时只有一个核来test and set，从而避免了多核下发生的问题。

无锁

1. 无锁算法的底层实现 — CAS
2. 借助内存访问WORD的原子性

参考：

https://xie.infoq.cn/article/c7045d48ccb28872277445ff8

http://jm.taobao.org/2011/12/07/1347/

https://blog.csdn.net/heiyeshuwu/article/details/9722443

https://www.cnblogs.com/jing99/p/11984966.html

https://www.qbitai.com/2019/12/9895.html
https://www.jianshu.com/p/d585b3938dea

https://blog.csdn.net/ITer_ZC/article/details/40392787

高速缓存

思想：索引思想、折中思想

• 直接映射ByHash

主存中的一个块只能映射到Cache的某一特定块中去。例如，主存的第0块、第16块、……、第2032块，只能映射到Cache的第0块；而主存的第1块、第17块、……、第2033块，只能映射到Cache的第1块……

直接映射是最简单的地址映射方式，它的硬件简单，成本低，地址变换速度快，而且不涉及替换算法问题。

但是这种方式不够灵活，Cache的存储空间得不到充分利用，每个主存块只有一个固定位置可存放，容易产生冲突，使Cache效率下降，

因此只适合大容量Cache采用。

例如，如果一个程序需要重复引用主存中第0块与第16块，最好将主存第0块与第16块同时复制到Cache中，但由于它们都只能复制到Cache的第0块中去，即使Cache中别的存储空间空着也不能占用，因此这两个块会不断地交替装入Cache中，导致命中率降低

• 全相连映射ByAll

图3-15 是全相联映射的Cache组织，主存中任何一块都可以映射到Cache中的任何一块位置上

全相联映射方式比较灵活，主存的各块可以映射到Cache的任一块中，Cache的利用率高，块冲突概率低，只要淘汰Cache中的某一块，即可调入主存的任一块。

但是，由于Cache比较电路的设计和实现比较困难，这种方式只适合于小容量Cache采用。

• 组相连映射ByGroup

组间直接相连，组内全相连

组相联映射实际上是直接映射和全相联映射的折中方案，其组织结构如图3-16所示。主存和Cache都分组，主存中一个组内的块数与Cache中的分组数相同，组间采用直接映射，组内采用全相联映射。也就是说，将Cache分成u组，每组v块，主存块存放到哪个组是固定的，至于存到该组哪一块则是灵活的。例如，主存分为256组，每组8块，Cache分为8组，每组2块。

主存中的各块与Cache的组号之间有固定的映射关系，但可自由映射到对应Cache组中的任何一块。例如，主存中的第0块、第8块……均映射于Cache的第0组，但可映射到Cache第0组中的第0块或第1块；主存的第1块、第9块……均映射于Cache的第1组，但可映射到Cache第1组中的第2块或第3块。

常采用的组相联结构Cache，每组内有2、4、8、16块，称为2路、4路、8路、16路组相联Cache。

组相联结构Cache是前两种方法的折中方案，适度兼顾二者的优点，尽量避免二者的缺点，因而得到普遍采用。

具体参考：https://blog.csdn.net/weixin_34319111/article/details/92562285

一致性协议

MESI 缓存一致性协议

Modified、Exclusive、Shared、Invalid

我们知道linux采用了分页机制，通常采用四级页表，页全局目录(PGD)，页上级目录(PUD)，页中间目录(PMD)，页表(PTE)。如下：

1. 从CR3寄存器中读取页目录所在物理页面的基址(即所谓的页目录基址)，从线性地址的第一部分获取页目录项的索引，两者相加得到页目录项的物理地址。
2. 第一次读取内存得到pgd_t结构的目录项，从中取出物理页基址取出，即页上级页目录的物理基地址。
3. 从线性地址的第二部分中取出页上级目录项的索引，与页上级目录基地址相加得到页上级目录项的物理地址。
4. 第二次读取内存得到pud_t结构的目录项，从中取出页中间目录的物理基地址。
5. 从线性地址的第三部分中取出页中间目录项的索引，与页中间目录基址相加得到页中间目录项的物理地址。
6. 第三次读取内存得到pmd_t结构的目录项，从中取出页表的物理基地址。
7. 从线性地址的第四部分中取出页表项的索引，与页表基址相加得到页表项的物理地址。
8. 第四次读取内存得到pte_t结构的目录项，从中取出物理页的基地址。
9. 从线性地址的第五部分中取出物理页内偏移量，与物理页基址相加得到最终的物理地址。
10. 第五次读取内存得到最终要访问的数据。

整个过程是比较机械的，每次转换先获取物理页基地址，再从线性地址中获取索引，合成物理地址后再访问内存。不管是页表还是要访问的数据都是以页为单位存放在主存中的，因此每次访问内存时都要先获得基址，再通过索引(或偏移)在页内访问数据，因此可以将线性地址看作是若干个索引的集合。

虚拟内存管理

Linux通过红黑树管理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

struct task_struct {

    struct mm_struct *mm;

}

struct vm_area_struct {
    struct mm_struct * vm_mm;    /* 所属的内存描述符 */
    unsigned long vm_start;    /* vma的起始地址 */
    unsigned long vm_end;        /* vma的结束地址 */
 
    /* 该vma的在一个进程的vma链表中的前驱vma和后驱vma指针，链表中的vma都是按地址来排序的*/
    struct vm_area_struct *vm_next, *vm_prev;
 
    pgprot_t vm_page_prot;        /* vma的访问权限 */
    unsigned long vm_flags;    /* 标识集 */
 
    struct rb_node vm_rb;      /* 红黑树中对应的节点 */
}

该结构体是一段虚拟内存，从vm_start到vm_end，他们拥有相同的权限；
vm_prev 、vm_next 是双向链表的next与pre；
vm_rb 是红黑树节点

1
2
3
4
5

struct mm_struct {
        struct vm_area_struct * mmap;       /* list of VMAs */
        struct rb_root mm_rb;/*又是红黑树的根节点*/
        struct vm_area_struct * mmap_cache;      /* last find_vma result */
}

mmap是双向链表；按照地址大小来顺序管理所有的area

mm_rb是红黑树的根节点

红黑树的Key-Value: 虚拟地址区间 => 对应的area.