一、海量数据

1.1 处理海量数据

在需要对海量数据进行处理时，常常会有时间上的需求、内存空间不足等问题，

• 时间上：加快处理速度

  时间上可以通过算法 & 数据结构来提高处理速度，如哈希、Trie树等

• 空间上：打破内存限制

  采用分而治之的思想，分批处理

一般提高海量数据系统性能（时间、空间）的框架为：

1.2 分而治之：解决分割数据问题

一般解决的场景是，比如海量日志查找、海量数据求TopK、海量数据频次统计、大文件排序存储等问题。

一般这种问题有大差不差的解决思路（分而治之），即将数据分割成小块，然后分别处理，最后合并结果。

• 分：hash映射
• 各分块处理：hash-map统计、排序、求TopK
  • 统计频次：hash-map统计
  • 各块单独排序：堆/快排/归并
  • TopK：从各块中选取每个模块的TopK
• 合并：归并

1.2.1 怎么分？- 哈希计算

一般对于海量数据排序、求频次tok等问题，内存无法一次性装入所有数据进行处理，所以我们选择将数据分成N部分，保证每一部分都可以单独在内存中处理。

由于数据是无序的，所以如果采用简单的分割，可能会导致相同的数据不在同一部分，从而导致分块数据的统计结果并不正确

举个例子，我们要对海量数据求TopK，如果我们采用简单的分割，从各个部分中求TopK，最后合并求最终实际的TopK，可能会导致当前这部分数据的非TopK数据跟其他部分的数据合并后可以成为TopK数据的情况，从而导致统计结果不正确。

所以我们需要哈希计算，将相同的数据哈希到同一部分，这样就可以保证相同的数据在同一部分，从而保证统计结果的正确性。

分布式负载均衡

在分布式系统中，我们需要将数据分布到不同的服务器上，这样可以保证每台服务器的负载均衡，提高系统的性能。

一般在实现分布式负载均衡时，我们首选会采用一致性哈希算法，这样可以保证当服务器数量发生变化时，数据的分布变化较小，从而保证系统的稳定性。（避免缓存雪崩现象）

哈希计算

哈希计算是将数据映射到一个固定的范围内，这样可以保证相同的数据映射到同一部分，从而保证数据的正确性。

哈希碰撞

因为哈希结果是有值域范围（有限的），所以哈希碰撞是不可避免的，但是我们可以通过哈希冲突解决的方法来解决这个问题。

解决哈希碰撞的方法一般有两种：

• 开放地址法--不常用：当哈希值发生冲突时，会继续寻找下一个空位置，直到找到空位置为止

• 拉链法：将哈希值相同的数据放在同一个链表中，这样可以保证相同的数据在同一部分

  拉链法如下所示：

  

哈希查找的时间复杂度

a. 普通哈希计算hash(data)%N

哈希计算的特点是相同的数据哈希值相同，所以当我们进行hash(data)时，相同的数据会有相同的计算结果，我们再确保这些相同计算结果的数据都放在同一部分即可。

之后怎么进行数据划分呢？

如果我们有N台服务器/需要将数据分出N部分，普通哈希计算会将哈希值通过取模（求对N的余数）分布在0-N之间，余数为n的数据就放在第n部分，这样通过哈希计算保证相同的数据取余后结果相同，也就是在同一部分。

b. 一致性哈希hash(data)%(2^32)

按照普通哈希计算，如果我们有N台服务器，当服务器数量发生变化时，数据的分布会发生变化，所有数据都要重新计算哈希值，然后进行数据迁移。

而解决这个问题的最好方法就是一致性哈希

1）实现-哈希环

一致性哈希将数据hash(data)、服务器hash(IP or Mac)都映射到一个哈希环上，通过对2^32取模，将数据映射到特定哈希环上。

通过顺时针查找，找到第一个大于等于该数据data哈希值的服务器，将数据放在这台服务器上。也就是环中某个区间的数据存在于某台服务器上。

当服务器数量发生变化时，只需要对部分数据进行迁移，而不是全部数据。

如当删除一台服务器时，只需要将该服务器的数据迁移到下一台服务器即可，不需要进行大量数据的迁移。

2）实现-虚拟节点

在前面的一致性哈希中还存在一个问题，即数据分布不均匀，因为服务器的数量有限，如果两个服务器的哈希值在环中很靠近，那么会有一台服务器的数据很多，另一台服务器的数据很少，导致数据分布不均匀。

一致性哈希的实现中，为了保证数据的均匀分布，我们会采用虚拟节点的方式，将每台服务器映射到多个虚拟节点上，这样可以保证数据的均匀分布。

1.2.2 各分块怎么处理？

根据不同需求，我们可以采用不同的处理方式，如求频次->排序->求TopK、海量数据去重等。

求频次：hash-map统计

求频次的问题，我们可以采用hash-map的方式，将数据映射到哈希表(key:data,value:count)中，然后统计频次。

时间复杂度：

有序hash-map的底层实现是红黑树，时间复杂度为n*O(logn)

无序hash-map、set的底层实现是拉链法，时间复杂度为O(1)、O(n)

排序：堆/快排/归并

排序的问题，我们可以采用堆排序、快排、归并等方式时间复杂度较小的算法，将数据进行排序。

一般采用堆排序维护一个大小为K的小根堆，然后将数据插入堆中，当堆的大小超过K时，将堆顶元素删除，这样可以保证堆中的元素是TopK。

时间复杂度：

求TopK：从各块中选取TopK

对于最经典的从海量数据中求TopK的问题，我们可以从各分块中排序后先分别求TopK，最后合并求最终的TopK。

海量数据去重

海量数据去重主要有两种方法：

• hash-set
  • 将数据映射到哈希表中，经计算后只有唯一值
  • 可以快速定位数据是否存在，时间复杂度为O(1)
  • 缺点是需要额外的空间来存储数据（空间换时间）
• Trie树
  • 将数据映射到Trie树中，相同前缀的数据只存储一次，通过共享前缀来节省空间
  • 定位时需要遍历Trie树，时间复杂度为max(O(n*len),O(n*lgk))（len为字符串长度，k为需要求的最频繁前k位）
  • 缺点是空间复杂度较高，但是可以压缩存储，节省空间

1.2.3 怎么合并？- 归并

合并还有个问题，就是如果大文件本身就不能一次性读入内存，那么对于多个分块的数据肯定也不能一次性读入内存。这里还是采用归并的方法，但是在进行两两归并时，我们需要将内存划分成3个缓冲区来动态实现归并。

• 将内存分为3块，2块用来存放需要归并的分块的数据，1块用来存放合并后的数据
• 从分块中读取数据，然后归并到合并块中
• 当合并块满时，将数据写入磁盘，然后继续读取数据
• 当分块空时，继续读取分块下一部分的数据

1.2.4 举例

1）有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节内存限制大小是1M。返回频数最高的100个词

由于内存限制，我们依然无法直接将大文件的所有词一次读到内存中。因此，同样可以采用分治策略，把一个大文件分解成多个小文件，保证每个文件的大小小于 1MB（需要分成大约5000个），求各个小文件的Top100，进而直接将单个小文件读取到内存中进行处理。

• 分：分而治之/hash映射
  • 顺序读取文件，对于每个词x，取hash(x)%5000
  • 然后把该值存到5000个小文件(记为x0,x1…...x4999)中。这样每个文件大概是200k左右。
  • 如果其中有的小文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。
• 处理：hash_map统计
  • 对每个小文件，采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
  • 堆/归并排序
  • 取出出现频率最大的100个词(可以用含100个结点的最小堆)后
  • 再把100个词及相应的频率存入文件，这样又得到了5000个文件
• 合：归并
  • 最后就是把这5000个文件进行归并(类似于归并排序)的过程了

2）海量日志数据，提取出某日访问百度次数最多的那个IP

百度作为国内第一大搜索引擎，每天访问它的IP数量巨大，如果想一次性把所有IP数据装进内存处理，则内存容量明显不够，故针对数据太大，内存受限的情况，可以把大文件转化成(取模映射)小文件，从而大而化小，逐个处理。 换言之，先映射，而后统计，最后排序。

• 分：分而治之/hash映射
  • 首先把这一天访问百度日志的所有IP提取出来
  • 然后逐个写入到一个大文件中
  • 接着采用映射的方法，比如%1000，把整个大文件映射为1000个小文件
• 处理：hash_map统计
  • 当大文件转化成了小文件，那么我们便可以采用hash_map(ip, value)来分别对1000个小文件中的IP进行频率统计，再找出每个小文件中出现频率最大的IP
  • 堆/快速排序
  • 找出那个频率最大的IP
• 合：归并
  • 最后，再对这1000个频率最大的IP进行归并排序，找出那个频率最大的IP

Hash取模是一种等价映射，不会存在同一个元素分散到不同小文件中去的情况，即这里采用的是%1000算法，那么同一个IP在hash后，只可能落在同一个文件中，不可能被分散的。

3）给定a、b两个文件，各存放50亿个ur，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的ur?

可以估计每个文件大小为5Gx64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

• 分：分而治之/hash映射
  • 遍历文件a，对每个url求取 hash(URL)% 1000，然后根据所取得的值将url分别存储到1000个小文件(记为a1-a999)中。这样每个小文件的大约为300M
  • 遍历文件b，同样对每个url求取 hash(URL)% 1000，然后根据所取得的值将url分别存储到1000个小文件(记为b1-b999)中
  • 这样处理后，所有可能相同的url都在对应的小文件(即a1 对应 b1，a2 对应b2..，a999 对应 b999)中，不对应的小文件不可能有相同的url
• 处理+合并：hash_map统计
  • 首先对A的小文件在hash_set中进行去重操作
  • 然后查找B的小文件是否有url在刚才构建的hash_set中
  • 如果是，那么就是共同的url，存到文件里面就可以了

参考：何为一致性哈希

二、高并发分布式系统设计基础

面对高并发场景，我们通常有两种大解决方向：

• 垂直方向：提升单机能力
  • 这种方式主要是通过硬件升级，如购买多核高频机器，大内存，大容量磁盘等
  • 软件优化，如多线程、异步、缓存等
  • 但是这种方式有瓶颈，即硬件成本高，以及当硬件达到一定程度时，提升单机性能的效果会递减。
• 水平方向：分布式集群
  • 这种方式主要是通过多台机器，通过微服务解耦将数据分布到不同的机器上，从而提升系统的性能
    • 架构层次分层
    • 业务服务划分
  • 这种方式成本低，可扩展性强，但是复杂度高，需要考虑数据一致性、负载均衡等问题

当前最常见的高并发系统设计是分布式系统设计，即将数据分布到不同的机器上，通过负载均衡、一致性哈希等技术来提升系统的性能。因此后面我们主要讲的就是水平方向分布式场景下的设计理念和框架。

一般我们在分布式系统设计中，主要关注以下几个方面：

• 池化技术：内存池、线程池、连接池
• 负载均衡：保证用户分流
• 缓存：提高响应速度
  • 分布式锁
• 数据库存储
  • 分布式事务
• 消息队列
• 限流：控制并发访问量，避免过载
• 熔断
• 降级：保证核心功能

整体并发架构如下：

2.1 分布式CAP理论

CAP理论是分布式系统设计中的一个重要理论，它指出在分布式系统中，一致性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance）三者不可兼得，只能同时满足其中两个。

• 一致性C 所有节点在同一时间的数据是一致的，即等同于所有节点访问同一份最新的数据副本
• 可用性A 客户的每个请求都能够得到非错响应，但是但是不保证获取的数据为最新数据
• 分区容错性P
  • 系统能够容忍网络分区
  • 针对一致性的容错性：当不要求保证一致性时，每个节点使用本地数据，在同一时间内可能出现全局不一致，但是一段时间后最终一致
  • 针对可用性的容错性：必须保证一致性，但是不保证可用性，即允许部分服务停止，直到网络分区解决

1）CA系统：单点集群

对于业务扩展性不强、并发性要求不高的系统，我们可以采用单点集群的方式同时保证一致性和可用性

场景：银行系统、图书馆管理系统

2）CP系统：放弃高可用性（高性能）

对于对一致性要求较高的系统，我们可以采用放弃可用性的方式来保证一致性

一旦遇到分区故障，就要允许放弃一部分业务，通常性能不高

场景：火车票售票系统、redis

3）AP系统：最终一致性

某些场景下对一致性要求不高，我们可以采用最终一致性的方式来保证绝对可用性

通常很多分布式系统都是采用AP来实现的（买票时看到有几张余票，但是买的时候告诉你没有了，当再次刷新发现确实没票）

场景：电商系统、社交系统（博客，微博）、搜索引擎

2.2 系统并发指标

• TPS：一台服务器每秒能处理的事务数
  • 一个客户端请求就是一个事务
• QPS：一台服务器每秒能响应的查询次数
  • 一个客户端请求可能有多个查询，所以QPS是TPS的倍数，QPS>=TPS

• 并发数：系统同时承载的并发用户数

• 响应时间：系统响应一个请求的时间

2.3 分布式负载均衡

负载均衡是为了满足多台服务器情况下的高可用需求，通过负载均衡（）可以将请求分发到不同的服务器实例上，从而提高系统的性能。

负载均衡通过不断向后端服务器发送心跳检测，来检测服务器的健康状态，从而保证负载均衡的准确性。

负载均衡有硬件负载均衡和软件负载均衡两种方式：

• 硬件负载均衡性能好，但是可扩展性差，成本高
• 软件负载均衡性能一般，但是可扩展性强，成本低

目前常见的三种软件负载均衡：

• 基于DNS负载均衡：通过地理位置or加权，根据IP映射到不同服务器
• 基于网络层负载均衡：基于IP地址和端口号来分发流量
• 基于应用层负载均衡：解包HTTP请求的特性（如请求头、URL、主机名等）来分发不同业务请求到不同后端服务器

一般大型服务器系统中，会同时包含这三种均衡方式

2.3.1 DNS负载均衡

DNS对某个域名进行IP映射，DNS负载均衡通过DNS解析将域名解析到多个不同的IP地址，然后将解析后的IP地址返回给客户端，从而实现负载均衡。能够对网站加载进行加速

做为第一层的负载均衡，它能根据不同地理位置的用户返回离用户最近的服务器，减少中间的网络传输延迟和丢包率

但是由于DNS解析是有缓存的（包括本地DNS缓存、客户端缓存等），所以DNS负载均衡无法确保各地服务器负载均匀

DNS负载均衡的实现策略

1）轮询策略

DNS服务器中维护一个服务器列表，每次请求时按照轮询的方式返回服务器列表中的下一个服务器IP，也就是N台服务器的IP按照顺序返回给不同的客户端

缺点：无法根据各个服务器的负载情况和地理位置来返回服务器IP

2）地理位置策略

DNS服务器通过解析判断客户端请求的来源IP地址，然后将请求解析到地理位置最近的或者网络延迟最低的服务器

3）权重策略

每个服务器IP都有一个权重值，根据权重值来返回服务器IP

权重值可以根据服务器负载情况、地理位置等来设置

4）智能DNS

DNS可以通过：

• 心跳监测服务器是否故障（定期向注册的服务器发送探测请求HTTP、TCP、ICMP等）
• 通过服务器监测工具定期收集注册服务器的性能数据
• 根据性能数据来动态调整服务器的权重值
• 结合地理位置和动态权重值返回最优服务器IP

2.3.2 网络层&应用层负载均衡：Nginx

Nginx具有web服务器、负载均衡、反向代理等功能，是一个高性能的HTTP和反向代理服务器。

Nginx是一种基于应用层的软件负载均衡，通常根据解析的URL来反向代理转发请求

Nginx的负载均衡有轮询、加权轮询、IP哈希、最少连接等策略

1）IP哈希

根据客户端IP地址的哈希值来分配请求，这样可以保证同一个IP的请求始终分配到同一个服务器上

2）最少连接

将请求分配到连接数最少的服务器上，这样可以保证负载均衡，但是性能可能会受到影响

2.4 分布式缓存

在高并发场景下，缓存机制可以有效缓解实例服务器和数据库压力、提高网页访问速度

2.4.1 本地客户端缓存

常用于缓存实时性不敏感、静态网页，如在大促期间提前将一些js/css/image文件缓存至本地，避免在大促期间再次请求

本地客户端缓存可以通过HTTP缓存机制来实现

• 强制缓存
  • Expires字段：绝对时间
  • Cache-Control字段：倒计时时间
• 协商缓存
  • Last-Modified字段：当前缓存对应的最后修改时间
  • E-tag字段：当前缓存资源的哈希值
• 混合缓存

2.4.2 CDN-内容分发网络

CDN是由专门的机构在世界各地建立边缘服务器，用户通过DNS域名解析获取最近的CDN服务器，从该CDN服务器上获取资源而不是直接从实例服务器获取，大大加快了请求响应速度。

同时由于CDN替实例服务器分流了，所以还可以大大减少带宽（虽然还需要向CDN服务商付费）

CDN中的缓存内容：

• 静态网页资源
• 动态网页API接口

CDN缓存机制主要有两种：

• 主动推送（push）：服务器主动将缓存push给CDN
• 拉去机制（pull）：客户端首次访问CDN中不存在的资源，CDN主动从源服务器中获取数据并存储在CDN节点上

2.4.3 反向代理缓存

反向代理服务器如Nginx除了上面提到的负载均衡外，还可以通过配置具有缓存功能，也是存储静态资源，返回给用户时从缓存中拿，不再向源服务器请求

2.4.4 redis缓存

Redis缓存是指分散存储在服务器上，在内存中进行计算的缓存，相比磁盘中的数据库具有更快的响应速度

Redis是一种高性能的键值key-value存储系统，用其快速的读写能力和一致性哈希算法实现数据分片和负载均衡（通过一致性哈希算法分配给集群中的某个缓存）

redis集群缓存带来的问题

1）缓存穿透

问题：

• 请求缓存和数据库都没有的数据 都去访问数据库 -> 数据库崩溃、服务器宕机

解决：

• 布隆过滤器：将数据库中的数据映射到布隆过滤器中，当请求来临时，先通过布隆过滤器判断是否存在，不存在则直接返回
• 空值缓存：将数据库中不存在的数据也存入缓存(设为空值)

2）缓存击穿

问题：

• 单个热点key失效 都去访问数据库 -> 数据库崩溃、服务器宕机

解决：

• 热点数据永不过期：将热点数据设置为永不过期，当失效时，立即更新
• 互斥锁：当热点数据失效时，通过互斥锁来保证只有一个线程去访问数据库，其他线程等待
• 多级缓存

3）缓存雪崩

问题：

• 大量key同时失效 都去访问数据库 -> 数据库崩溃、服务器宕机
• 服务器宕机： 采用普通哈希算法导致所有Key同时失效 -> 都去访问数据库 -> 数据库崩溃

解决：

• 缓存失效时间随机：将缓存失效时间设置为随机时间，避免同时失效
• 多级缓存

4）数据一致性

缓存一致性指的是缓存与DB之间的数据一致性

需要保证始终一直或最终一致

常用的解决方法是

• 缓存的分布式锁
• DB数据库的分布式事务

数据一致性的两种方法将在后面详细介绍

2.5 分布式消息队列

在高并发场景下，同步的请求处理方式往往会导致系统响应时间变长和资源消耗增加。

因此我们可以采用异步的方式，将耗时的操作或复杂的业务逻辑异步化处理，并将结果通过消息队列传递，可以实现解耦和异步化处理，在只需要最终一致性的场景下，很适合用来配合做流控。

分布式缓存在读多写少的场景性能优异，对于写操作较多的场景可以采用消息队列集群，它可以很好地做写请求异步化处理，实现削峰填谷的效果。

业界有很多著名的消息中间件，比如ZeroMQ，rabbitMQ，kafka等。

2.5.1 消息队列的优点

1）异步

如果我们按照同步的处理方式来设计，比如设计一个用户注册功能，会经过用户注册->短信通知->增加积分三个串行同步步骤，这种方式的话，总耗时是三个步骤的总和。

总耗时：10ms+100ms+100ms=210ms

而如果在中间加上一层消息队列实现异步并行处理，那么总耗时将只剩下用户注册这一步，因为通过异步方式，用户注册后消息队列就可以返回，后面的两个耗时步骤直接与消息队列通信拉取信息。用户不需要阻塞在那等待耗时步骤完成。

总耗时：10ms

2）业务解耦

业务解耦是在异步的基础上实现的，如果是同步的话，用户注册和短信通知是紧耦合的，如果短信通知出现问题，那么用户注册也会受到影响。

而使用了消息队列实现异步后，消息发送方和接收方不直接联系，各个业务之间也相对独立，不会因为某个业务的宕机影响到其他业务

3）削峰填谷

举个例子，在高并发场景下，假设1min内有30W个请求（30W/min），而后端业务服务器只能处理1W/min，那么超量的请求可能会导致服务器宕机。

加入我们在请求和处理方中间加上一层消息队列，消息队列只做简单的数据接收任务，能处理100W/min，此时由后端服务器主动向消息队列拉去任务就可以控制后端服务器不过载，达到控制流量的作用。

2.5.2 消息队列优化设计

根据简陋版本消息队列的各种问题，可以进行优化来提高可用性及性能

根据Kafka的设计理念来剖析优化方向

1）MQ数据堆积

MQ中数据堆积本质是消费者消费能力差，可以通过增加消费者线程，也就是多消费者模式，同理也可以添加多生产者提高吞吐量

2）多生产者和多消费者竞争MQ

分Topic

将消息队列根据不同主题Topic分为多个MQ减少冲突等待

Topic的Partition分区

单个Topic中还可以再细分成多个Partition分区，每个消费者对应一个Partition分区，从而降低多线程竞争

3）高性能

将多个Partition分布在不同机器上，每个机器称为broker

4）高可用

单个broker如果宕机了，该部分的功能将无法继续进行，因此可以设计leader-follower的集群方式

leader负责读写数据，follower负责复制数据，当leader宕机时可以从follower中选举出新的leader

5）持久化

数据放在内存中有宕机丢失的风险，因此数据还应该具备持久化到磁盘的能力

同时为了防止磁盘溢出，还应该设置过期时间

根据不同的优化策略，形成了不同的消息队列中间件，可以根据需求和中间件的优缺点选择合适的方案：

2.5.3 RabbitMQ设计

RabbitMQ中主要涉及的模块元素有：

• Producer生产者：负责生产和发送消息，一般是直接与交换机连接
• Connection连接：生产者与Broker的连接、Broker与消费者的连接
• virtual Host虚拟机：一个Broker可以有多个虚拟机，每个虚拟机实现一种业务，虚拟机之间数据互相隔离
• Exchange交换机：生产者将消息发送到交换机，交换机根据路由规则将消息发送到某个队列
• Queue队列：存储消息的缓冲区
• Comsumer消费者：负责接收和处理消息
  • 多个消费者绑定同一个队列可以通过消息轮询的方式进行分发

1）消息丢失

RabbitMQ的消息丢失主要有三种情况：

• 生产者丢失：发送者发送失败，可能是网络原因
  • 通过消息确认机制Comfirm接收ACK或NACK以及重传来实现，确保消息投递到了queue中
• Broker丢失：消息未发送存储到queue中可能就出现Broker宕机等原因丢失
  • 通过持久化来实现
• 消费者丢失：消息接收也可能因为网络或者处理失败等原因丢失
  • 通过ACK事务机制来实现。消费者成功处理完后才会发送ACK告知Broker可以删除该条消息

2）消息重复

消息可能出现重复消费的原因：

• 生产者重复推送
• Broker收到ACK后还未删除就宕机：重启后会再次发送该消息给消费者
• 消费者处理完后未发送ACK就宕机：重启后MQ超时没收到ACK会重新推送该条消息给消费者处理

解决方法：

插入去重表：消费去重表可以是MySQL存储，也可以是Redis存储

• 收到消息后先查询去重表，如果存在则不处理，否则将该消息插入去重表再进行处理
• 处理完再将该消息状态更改为已处理

3）消息顺序

除非采用单线程消费，否则消息顺序无法保证，但是可以尽量保证消息顺序

• 同一个queue中的消息是顺序的
• Exchange路由器指定分发同样的key到某个queue中
• queue中增加一些机制，只有某个操作收到ACK后才分发下一个

2.5.4 Kafka设计

Kafkade的设计架构在前面优化部分已经有大致提及了

所以接下来还是将重心放在Kafka怎么解决消息丢失、消息重复、消息顺序三大问题

1）消息丢失

• 生产者丢失：发送者发送失败，可能是网络原因
  • 通过消息确认机制Comfirm接收ACK或NACK以及回调重传来实现，确保消息投递到了queue中
• Broker丢失：消息未发送存储到queue中可能就出现Broker宕机等原因丢失
  • 通过持久化来实现
  • Kafka对每个Partition提供了leader-follower的副本机制方式，当leader宕机时可以从follower中选举出新的leader
• 消费者丢失：消息接收也可能因为网络或者处理失败等原因丢失
  • 通过ACK事务机制来实现。消费者成功处理完后才会发送ACK告知Broker可以删除该条消息

2）消息重复

Kafka的消息队列中通过offset来标记消息的位置，消费者消费完后会自动提交offset来避免重复消费，但是依然这也导致了如果消费者宕机，重启后消息队列可能触发了超时重传导致重复消费。

在这个背景下，避免消息重复处理的方式跟RabbitMQ一样，可以通过插入去重表来实现：

解决方法：

插入去重表：消费去重表可以是MySQL存储，也可以是Redis存储

• 收到消息后先查询去重表，如果存在则不处理，否则将该消息插入去重表再进行处理
• 处理完再将该消息状态更改为已处理

3）消息顺序

为什么会出现消息顺序问题呢？

Kafka的消息队列中，同一个Partition中的消息是有序的，但是不同Partition中的消息是无序的，因此如果同一个业务的消息被路由分发到不同Partition中，那么就会出现消息消费顺序不是消息发送顺序的问题。

解决方法：

基于这个背景，可以采用自定义路由的方式，将同一个业务（指定的key）的消息路由到同一个Partition中，再指定某个消费者线程去定向取某个Patition分区的消息，从而保证消息的顺序性。

• 自定义路由：通过自定义路由将同一个业务（按照key取模）的消息路由到同一个Partition中
• 指定消费者：指定某个消费者线程去定向取某个Patition分区的消息

6）主从数据一致性

前面提到Kafka会通过leader-follower的副本机制来减少数据丢失，这里的数据存储涉及MySQL或Redis数据库

• MySQL下的数据一致性：通过Follower节点拉取Leader的binlog日志，然后同步到Follower节点
• Redis下的数据一致性：主-从-从方式，主节点写入数据后，从节点同步数据，再从从节点同步到其他从节点

5）leader-follower下的选举问题：ISR

Kafka中的leader-follower机制是指leader负责读写数据，follower负责复制数据，当leader宕机时可以从follower中选举出新的leader

但是在leader-follower机制下，follower可能会出现数据同步滞后的问题，导致数据不一致。

为了解决这个问题，Kafka中引入了ISR机制，在ISR中维护一个集合，该集合是代表存储最新数据离leader最近的follower，只有ISR中的follower才能被选举为leader

因此采用ISR的好处主要有两个：

• 提高宕机后重选leader的效率：只有ISR中的follower才能被选举为leader，提高了选举效率
• 避免数据丢失：因为ISR中节点的数据和leader节点的数据是最接近的

2.6 分布式数据库

传统的数据库系统是单机数据库，在高并发场景下，单机数据库可能会出现性能瓶颈，面对这种需求，我们一般有纵向扩展和横向扩展两种方式。

• 纵向扩展：提高单机数据库的性能，如增加CPU、增加内存、增加硬盘等
  • 成本过高，不适合现在海量数据的场景
• 横向扩展：通过分布式数据库来实现，将数据分布在多个节点上，从而提高系统的性能
  • 适合海量数据的场景，需要考虑数据库容灾、数据一致性等问题

这里主要讨论怎么解决数据库容灾问题

数据库容灾是指在数据库宕机或数据丢失时，能够快速恢复数据，保证系统的高可用性

一般出现故障的原因主要有三大类：

• 服务器主机故障：服务器过载宕机、网络故障等
• 机房故障：机房电力系统出现问题、火灾等
• 地域故障：发生地震、火灾等

出现这些问题最需要解决的就是系统恢复、保证数据不丢失

1）主从数据库备份

通过主从复制技术、binglog等技术实现同步

2）数据分片

将数据根据业务需求，通过分片键如用户ID、订单ID等决定哪个数据库集群存储特定数据

3）数据一致性

通过分布式事务、分布式锁等技术来保证数据一致性

4）防止过载

通过前面讲到的负载均衡、限流等技术来保证系统不会因为过载而宕机

5）读写分离

应用中的读操作远远多于写操作，可以通过读写分离来减轻数据库的压力

写操作：主数据库

读操作：从数据库

2.7 分布式事务和分布式锁

这两种方式都是为了保证MySQL和Redis数据一致性的

服务器在响应读数据请求时，会先从Redis中读取数据，如果Redis中没有数据，再从MySQL中读取数据，然后将数据返回给客户端。

而对于写数据则有多种更新方式（建议采用删除Redis而不是更新修改Redis）：

• 先更新Redis再更新MySQL：如果先更新Redis，那么如果MySQL更新失败回滚，还要再次回滚Redis

• 先更新MySQL再更新Redis：如果先更新MySQL，那么当线程1被最新的线程2抢占CPU资源后，会出现线程2的数据先写入缓存，线程2的数据后写入数据库，导致缓存存的不是最新数据

• 先删除Redis再更新MySQL：也会有数据不一致问题（通过延迟双删来解决）

• 先更新MySQL再删除Redis：目前比较有效的方式

而由于分布式数据库有读写分离的设计，所以会有概率出现从数据库还没来得及更新，就被请求读取了，导致缓存与数据库数据不一致的问题

这里的解决办法是加上一层消息队列保证顺序性。

2.7.1 分布式锁

传统的同步锁是单机锁，只能保证在单机下多线程的同步

而在分布式场景下，多个服务器之间的同步就需要分布式锁来实现，否则还会出现类似超卖现象

主流分布式锁有：

• Redis：通过setnx设置键值对，如果返回1则表示加锁成功，否则设置失败
  • 要记得加上锁过期时间，避免造成死锁
  • 过期时业务还没执行完怎么办？---添加一个线程每n秒判断服务器是否在线、给锁加一个唯一ID（UUID）
  • 以上设计方式实际上可以通过Redisson来一步实现(lua脚本)
• Zookeeper：通过临时节点来实现分布式锁
  • 通过创建临时节点来实现分布式锁，如果创建成功则表示加锁成功，否则加锁失败
  • 通过监听节点来实现锁释放，当节点被删除时，其他节点可以重新加锁

2.7.2 分布式事务

事务是为了保证一组操作要么全部成功，要么全部失败，保证数据的原子性、一致性、隔离性和持久性

而在分布式场景下，多个不同业务是异步的，怎么保证一个业务失败后，其它业务也回滚呢？

1）两阶段提交2PC

事务参与者：多种业务的事务执行者

事务协调者：负责协调各个事务参与者的事务执行

2PC两个阶段是由事务协调者来协调的：

• 准备阶段：
  • 事务协调者向所有事务参与者发送prepare准备请求
  • 各个事务参与者执行事务操作
  • 如果事务参与者执行成功，则返回ACK，否则返回NACK
• 提交阶段：
  • 若正常收到所有事务参与者的ACK，则事务协调者向所有事务参与者发送commit提交请求
  • 某个事务迟迟没有返回ACK，则事务协调者会回滚所有事务参与者的事务

缺点：造成所有事务参与者阻塞，性能较差

2）三阶段提交3PC

相比2PC，3PC在准备阶段前多了一个可否提交询问CanCommit阶段，也就是先判断事务服务器是否存活，避免资源浪费

• 可否提交询问CanCommit：
  • 事务协调者向所有事务参与者发送CanCommit询问请求
  • 事务参与者执行事务操作
  • 如果事务参与者执行成功，则返回ACK，否则返回NACK
• 准备阶段
• 提交阶段

缺点：依然存在事务进行时的全局阻塞

2.8 分布式限流

在秒杀等超高并发场景下，为了保证系统的稳定性，需要适当降低用户体验来平衡系统的压力

一般可以通过拒绝服务、服务降级、特权VIP处理、限流等方式来实现

经典的限流算法有4种：计数器方式、滑动窗口、漏桶、令牌桶

2.8.1 计数器方式

计数器方式是最简单的限流算法，通过固定一个计数器阈值来记录单位时间内允许的请求次数

当在这段时间内某一刻总请求次数超过阈值时，则后面这段时间内将就拒绝服务

缺点：在两个相隔时间段内可能瞬间请求次数过多，导致瞬间流量过大

2.8.2 滑动窗口

在计数器方式的基础上，将大时间段再细分为小时间段，通过滑动窗口来动态累计请求次数

2.8.3 漏桶

漏桶算法是一种固定容量的漏桶缓存消息，消费者对桶的消费速率相对固定，而生产者的生产速率不固定，但是有容量限制，当桶满时，生产者将拒绝请求，从而实现限流

2.8.4 令牌桶

令牌桶的容量不固定，而是通过中间人按照一定速率往桶中放入令牌token，有点类似于空闲时段攒钱，在繁忙时段可以花钱，所以相比漏桶算法，在面对大流量时可以快速处理

当请求来临时，先从桶中取出令牌，如果有令牌则处理请求，否则拒绝请求

2.9 分布式熔断和降级

熔断与降级的区别：熔断可能会调用降级机制，但是降级不会调用熔断机制

2.9.1 熔断

在某些情况下，系统大量下游节点出现异常，那么会影响整个系统的稳定性

而熔断（Circuit Breaking）是面向不稳定服务场景设计的，它能最大限度避免下游服务不稳定对上游服务带来的影响。

当某个下游业务不稳定时，可以通过熔断机制先把不稳定的服务熔断，然后降级处理

熔断判断方法：

• 异常率：当异常率超过一定阈值时，就会触发熔断
• 响应超时率：当响应超时率超过一定阈值时，就会触发熔断

2.9.2 降级

降级是为了解决资源不足和访问量过大的问题，通过降低牺牲一些业务（停某些业务）或流程（强一致性变最终一致）来保证系统的稳定性

降级的方式有：

• 停止某些业务：比如在秒杀高并发场景下，可以停止注册业务
• 强一致性变最终一致性：比如在秒杀高并发场景下，可以降级为最终一致性

2.10 UUID-雪花算法

UUID是由32个16进制数字，也就是16³²⁼²128128位组成的，一般是全球唯一，是通过雪花算法（生成分布式全局唯一ID的算法）生成的

UUID的产生一般与时间戳、网卡MAC地址、随机数等有关

优点：全球唯一、不重复

缺点：无序、存储空间大、字符串存储，查询效率低

参考：架构设计之道：高并发架构设计

参考：分布式之CAP原则详解

参考：面试场景题积累汇总

参考：高并发架构设计（三大利器：缓存、限流和降级）

参考：深入消息队列MQ，看这篇就够了！

三、常见的分布式系统设计场景

3.1 秒杀系统设计

整体架构主要包括Redis预扣库存、Kafka异步下单、MySQL扣除实际库存、前端跳转支付等步骤，一般的流程为请求->限流组件->Redis预扣->库存服务

具体流程如下：

3.1.1 限流

限流一般是在接入系统前进行的预处理，一般由专门的限流组件在网关端实现，通过令牌桶、漏桶等算法来实现

当请求超过一定阈值时，就会触发限流，返回请求太多的提示来拒绝请求服务

3.1.2 Redis预扣库存

Redis预扣库存主要有以下的步骤：

• 预扣库存（管理订单名额）+限额：用户请求到达后，先从Redis中预扣库存，如果库存不足则返回库存不足的提示
• LUA保证原子性：通过LUA脚本来保证预扣库存的原子性，避免超卖的问题
• 状态记录逻辑：secNum（uuid）做为key来存储状态信息

3.1.3 Kafka异步下单

Redis预扣除后，怎么把实际的订单消息传给MySQL进行实际订单生成和库存扣除呢？

1）直接打到MySQL

由于Redis已经进行预扣除，只有拿到入场券的订单才能交给MySQL，如果此时商品秒杀库存总额只有几百或者几千，那么直接打到MySQL也是可以的

但是如果商品秒杀库存总额有几十万、几百万，那么直接打到MySQL就会导致MySQL的压力过大，因此需要异步下单

2）Kafka异步下单

Kafka中存储订单消息交给MySQL消费，通过同一商品在同一分区中，保证订单生成的顺序性

消费队列的数据主要包括：订单ID、用户ID、商品ID、商品数量、商品价格等信息

3.1.4 MySQL扣除实际库存

1）扣除库存

MySQL中的商品库存是实际库存，通过商品ID来扣除库存

2）订单生成

通过订单ID、用户ID、商品ID、商品数量、商品价格等信息来生成订单

3）订单状态

订单生成后，需要更新订单状态，比如已支付、未支付等状态

3.1.5 前端跳转支付

订单生成后，需要跳转支付，通过支付宝、微信等支付方式来完成支付

支付完成后，需要更新订单状态为已支付，同时扣除用户余额等操作

3.1.6 更新Redis库存

支付完成后，需要更新Redis库存，将预扣库存更新为实际库存

3.2 扫码登录设计

3.2.1 token

token是指令牌，是一种身份验证的方式，通过token来验证用户身份，保护用户隐私

我们通常在网页中登陆一次后，下次访问不需要再次登陆，就是通过token来实现的：

• token生成：通过用户ID、时间戳、密钥等信息生成token
• token验证：
  • 通过token来验证用户身份，如果token过期或者不正确则需要重新登陆
  • 由于token中的value包含设备信息，所以就算被窃取也很难保证设备信息一致

3.2.2 扫码登录设计思路

• 获取二维码
  • PC端：携带设备信息->请求后端二维码ID
  • 后端Redis：产生二维码ID（状态为：待扫码）->关联二维码ID和设备信息->返回二维码ID
• 显示二维码
  • PC端：前端展示二维码
  • PC端：开始不断轮询后端二维码ID状态
• 登录扫码
  • 移动端：扫码获得二维码ID->发起扫码请求
  • 后端Redis：根据二维码ID关联用户ID（状态改为：待确认）->生成临时token->返回临时token
  • PC端：轮询到状态改变，显示用户对应头像（等待移动端确认）
• 确认登录
  • 移动端：确认登录->携带临时token->请求后端
  • 后端Redis：删除临时token->根据用户ID生成token->二维码关联用户ID（状态改为：已激活）
  • PC端：轮询到状态改变，获取token并登录

3.2.3 扫码登录设计

3.2.3.1 数据结构

采用Redis做为存储，为了保证原子性，需要通过Lua来操作

以key-value的形式存储数据：

1
2
3
4
5
6
7
8
9
10
11
12
13

{
    //qrID
    "qrIDxxx":{
        "accountID":"dsfsd1231321f",
        "deviceInfo":{
            "deviceID":"sdfsfaldfhfshlfhds",
            "deviceType":"mac",
            "position":"shenzhen"
        },
        "status": 3,//激活
        "pcToken":"xxxxxxxx"
    }
}

3.2.3.1 临时token作用（安全性）

临时token是为了绑定扫码的移动端设备，这样就算token被截获，也无法登录，因为token是绑定设备的