系统设计笔记

Published: June 03, 2021 by Daltao

• Categories:
• techonology 15

• Tags:

• 一般步骤
  • 澄清需求边界
  • 定义系统接口
  • 粗略估计
  • 确定数据模型
  • 高层设计
  • 细节设计
  • 识别和分解瓶颈
  • 摘要
• 数据库选择
  • 读写
  • 索引
  • 分区
  • 事务
    • 更新丢失
• 分布式系统
  • 检测节点失效
  • 时钟
  • 分布式锁
• 一致性
  • 线性化
  • 因果关系
  • 全序关系广播
  • 共识算法
    • 两阶段提交
• 批处理系统
  • MapReduce
    • 分组和Join
    • 热点数据
• 流处理系统
• 参考资料

一般步骤

澄清需求边界

由于系统设计问题是开放的，没有固定的标准答案，因此必须澄清其中比较容易出现歧义的部分。我们需要在回答问题之前，确定需要设计实现哪些功能，哪些不需要实现。而这些需求会决定我们最终设计的样貌。

比如设计一个推特系统，你需要确认下面需求边界：

• 我们的用户是否由能力发布推特以及跟随他人
• 是否应该创建并展示用户的时间线
• 推特内容是否包含图片和视频
• 我们只需要关注后端还是需要同时关注前端
• 推特是否支持搜索功能
• 是否需要展示热门话题
• 是否需要向用户推送新（或重要）的推特

定义系统接口

确定系统需要哪些接口。比如推特系统的接口可能如下。

postTweet(user_id, tweet_data, tweet_location, user_location, timestamp, …)
generateTimeline(user_id, current_time, user_location, …)
markTweetFavorite(user_id, tweet_id, timestamp, …) 

粗略估计

提前估计系统的规模是一个好主意，这会在之后我们关注扩容、分片、负载均衡和缓存的时候提供支持。

• 系统的规模是多大（新推特的数量，用户的数量）
• 我们需要多大的存储？如果推特中可以包含图片和视频，我们则需要更大的存储。
• 我们期望多大的网络带宽使用量。我们需要依据这条管理网络传输和服务器之间的负载均衡。

确定数据模型

提前定义数据模型，有助于澄清数据是如何在系统的不同模块之间流转的。之后它会指导我们数据分片和管理。候选人应该要有能力识别系统中的不同实体，以及它们之间的交互，以及不同层面的数据管理，比如存储，传输，加密等。下面是推特系统中的一些实体。

User: UserID, Name, Email, DoB, CreationData, LastLogin, etc.
Tweet: TweetID, Content, TweetLocation, NumberOfLikes, TimeStamp, etc.
UserFollowo: UserdID1, UserID2
FavoriteTweets: UserID, TweetID, TimeStamp

要使用哪个数据库系统？使用NoSQL还是传统的SQL数据库，应该如何存储图片和视频数据。

高层设计

绘制一个方形图标，其中放置5到6个盒子，表示我们系统的核心模块。我们要确定足够的模块，通过端到端解决我们实际问题。

对于推特，我们需要多个应用服务器来服务所有的读写请求，在它们前置负载均衡，来分配流量。如果我们假定读流量较多（相较于写流量），我们可以用不同的服务器来处理这样的场景。对于后端，我们需要一个高效的数据库，能够存储所有的推特数据，并且能承担巨量的读请求。我们还需要一个分布式文件存储系统来存储图片和视频。

细节设计

深入挖掘其中的两个到三个模块；面试官的回馈应该引导我们知道系统的哪些部分还需要深入讨论。我们应该提供多种途径，以及它们的优点和缺点，并且解释为什么我们会选择其中的一种途径。答案并不唯一，唯一重要的就是在考虑不同选项的得失的时候将系统约束牢记于心。

• 由于将会存储超大规模的数据，我们如何将数据分片为多个数据库，我们是否应该将单个用户的所有数据都存储在同一个数据库中。它会带来什么问题。
• 我们如何处理那种发很多推特或者跟随很多人的热点用户。
• 由于用户的时间线会包含最近的推特，我们是否应该组织我们的数据，以优化最近推特的扫描。
• 我们应该在哪些层次引入缓存来加速。
• 哪些组件需要更好的负载均衡。

识别和分解瓶颈

讨论尽可能多的瓶颈，以及用不同的途径来缓解。

• 系统是否存在单点故障问题，我们如何缓解。
• 数据是否有足够多的副本，允许我们在失去少量的服务器后我们依旧可以向用户提供服务。
• 服务是否有足够多的副本，在部分服务下线的情况时不会导致整个系统宕机。
• 我们如何监控服务的性能，在重要的组件下线或者性能下降后，是否会收到报警。

摘要

简单来说，提前准备和面试期间有组织地描述是系统设计环节面试成功的关键。上面提到的方法可以让你保持在正轨上，并且在系统设计的时候覆盖所有不同的层次。

数据库选择

读写

数据库一般提供的主要是读写两方面。

大部分情况下都是读多写少的场景，我们可以直接用缓存和读写分离来加速。

小部分情况下是写多读少（或相近）的场景。分情况讨论：

• 如果允许数据丢失，可以用缓冲区进行加速。
• 如果读仅要求顺序读，可以使用WAL的技术，将数据写入到日志文件尾部。
• 如果要求支持随机读写，我们可以用基于LSM算法的数据结构，比如HBase和LevelDB。这时候读性能为$O((\log_2n)^2)$，而写性能为$O(\log_2n)$，我们牺牲读性能换取写性能。

索引

对于整数类型的多列索引，我们可以合为一列。比如说我们要支持两类查找，一种是查找最新的数据，一种是查找某条指定的数据。那么我们可以把主键格式设计为时间戳+递增序列号的形式，这样我们能同时支持两类查找，且只需要建立一个索引，优化了写性能。

分区

分区的目的是提供水平扩展，一个分区只能分配给一个结点，而一个结点上可以配置多个分区。分区的方案有很多。

• 随机分区，但是这样二次查找的时候由于不确定数据在哪个分区上，需要遍历所有分区。
• 范围分区，优点是做范围查询的时候可以非常快的完成。但是可能会存在热点问题。
• 哈希分区，优点是分区均匀，减轻热点问题，且能很快定位数据所在的分区。但是做范围查询的时候需要遍历所有的分区。

在对多列排序的时候，我们可以在第一列上做哈希分区，后面几列上做索引。这样第一列是固定的时候，我们可以很快的在某个分片上做范围查询。

哈希分区同样无法避免热点问题，一种解决方案是对于热点数据，我们在其关键字之后再加一个随机数，这样热点数据就被再次分片到所有机器上（类似随机分区），大大降低了写的压力。但是缺点是读取热点数据的时候需要去所有分片上读取并做合并（也可以全写+任意读，这样可以减轻读压力，但是会增大写压力），我们还需要能够识别热点数据。

在分区上实现的索引有两类：

• 本地索引：每个分区维护自己的索引信息。优点是数据都落在某个分区中的时候会非常快。缺点是数据不指定关键字的时候，需要遍历所有的分区查询需要的结果，之后做合并。
• 全局索引：我们在业务上维护一个全局索引，出于性能考虑，我们需要对全局索引做范围分区。优点是我们只需要查询存在数据的分区即可，读速度加快。缺点是写数据的时候要同时更新全局索引，速度会变慢。在实践中，对全局索引的更新一般都是异步的。

事务

事务提供了ACID安全保证：

• A，原子性：指事务的操作要么全部成功，要么全部失败，主要用于数据库宕机重启需要丢弃那些未提交的事务以及它们所做的操作。
• C，一致性：一致性表示的是因果上的一致，比如借贷平衡。数据库提供像唯一索引、外键等功能来保证一致性，但是一致性实际上是需要应用层来保证的。
• I，隔离性：数据库需要保证每个事务执行的结果，和串行化的时候是一样的。
• D，持久性：持久性保证事务提交成功后，即使存在硬件故障或数据库崩溃，事务写入的数据都不会丢失。

隔离性的解决方案：

• 读未提交：存在脏读和脏写的问题
• 读已提交：通过行锁保证同时最多有一个事务修改解决脏写的问题，但是脏读一般不会用锁来解决，否则会影响许多只读事务的运行，脏读一般通过多版本控制来解决（具体就是对每条记录维护两个版本，一个是旧快照，一个是修改后的版本）。但是读已提交存在不可重复读的问题。
• 可重复读：大部分数据库是指快照级别隔离。
• 可串行化隔离：允许并发执行事务，但是要求结果必须与串行执行的结果相同。

一般数据库会通过多版本并发控制来避免加读锁。具体的方案就是为每个事务维护一个递增的事务ID，之后对于修改操作，会标记原记录的删除事务为当前事务，并插入一条修改后的记录，其创建事务为当前事务。在事务创建的时候同时会维护有哪些运行中（未提交）的事务池，而当前事务只能看到事务号小于自己，且不出现在未提交事务池中的那些记录。这样会导致同一条记录产生很多数据版本，需要数据库的垃圾回收进程去删除那些不再被引用的过期版本。

更新丢失

一般使用事务的时候，我们不会选择串行化隔离级别，而会选择其它级别。这时候会出现更新丢失的情况。比如有一个计数器，我们有两个事务要分别扣减它，如果计数器值为$0$，则业务失败。但是由于我们使用多版本控制而非加读锁的方式，因此可能两个事务都读到$1$，之后同时发生扣减，导致计数器变成了负数，使得一致性被破坏。

要解决更新丢失，一般的方案有下面几种：

• 乐观锁：通过CAS原子操作，每次替换值之前做一次比较操作。这个方案一般性能最好，但是需要数据库的支持。
• 悲观锁：在读数据的时候加上写锁（或共享锁），这样可以保证在修改数据之前，数据不会被其它事务修改。
• 自动检测：一些数据库在快照隔离级别（可重复读）可以自动检测更新丢失的情况，并终止违规的事务。但是MySQL/InnoDB不支持。

更新丢失是由同时更新同一条记录导致的。而写倾斜类似于更新丢失，它源于更新不同的记录，但是导致一致性受到破坏。比如要求值班的人至少有一人，目前有两人负责值班，并且都提交了请假的请求。这时候由于发现剩余人数为两人，因此二人的请求全部提交成功，并标志它们为请假中。但是这破坏了一致性的要求。一般写倾斜是很难自动检测的，需要通过乐观锁或悲观锁检测。

但是仅通过加锁也未必能解决所有写倾斜的场景。比如说，同时只能允许一个人请假，由于二人在查询当前请假人数的时候都是$0$，那么之后同时插入请假人信息就会破坏一致性。由于这里前提是无法查到数据，因此自然也不可能对之后插入的数据加锁。这种一个事务的写入改变另外一个事务查询结果的现象称为幻读。而快照级别隔离是无法解决幻读问题的。

幻读的解决方案有如下几种：

• 实体化冲突：我们可以额外创建一些记录，表示当前请假人数，之后对这些记录进行加锁。
• 谓词锁：谓词锁锁定的是满足条件的所有记录，包括将来插入的记录。所有写操作都需要与之前的谓语做比较。在MySQL中的间隙锁和临键锁就是谓词锁。
• 串行化：终极方案

还有一种方案是通过2PL（两阶段加锁）来解决所有的并发修改问题。具体就是读数据的时候加读锁，写数据的时候加写锁。但是这很容易产生死锁问题。

分布式系统

检测节点失效

由于分布式系统中不同节点只能通过网络进行通信，要检测一个节点失效，需要通过心跳超时机制。

但是多久超时呢，如果超时时间太久，意味着需要等待很久的时间才能宣判某个节点死亡，而较短的时间虽然能帮助我们快速发现失效节点，但是可能会错误的将一些繁忙的节点判定为失效节点。

如果网络最大传输时间为$d$，而请求处理时间为$r$，那么$2d+r$作为超时时间是个合理的选择。但是由于异步网络并不能保证最大传输时间，因此$d$可能无穷大。

更好的方式是不断对网络响应时间进行采样，从而估算出实时网络状况下$d$的值，并根据这个值判断超时。

还有一种思路是类似于电话网络拨打电话的方式，在一条线路上分配固定带宽的通信链路，该链路直到连接断开后才被释放。这样的好处是能保证数据传输的效率和延迟，我们可以通过这种方式很容易计算出超时时间。但是这种方式成本很高，真实的网络是通过抢占的方式获取带宽的，后抵达交换机的报文会参与排队，而溢出的报文会被丢弃，这样可以最大限度的利用带宽资源，节省成本。

时钟

每台机器都有自己的时钟硬件设备，通常是石英晶体振荡器。换言之，每台机器都维护了一个本地时间，不同机器之间的本地时间未必相同。

可以在一定程度上同步机器之间的时钟，最常用的就是网络时间协议（NTP），它根据一组专门的时间服务器来调整本地时间，而时间服务器则从更高精度的时间源获取高精度时间。

上面提到的获取时间的时钟称为墙上时钟。墙上时钟由于会通过NTP协议与时间服务器同步时间，因此可能会发生回跳的情况。

我们也不能使用第三方服务器上的时间，因为得到的时间是服务器响应我们的时候的时间，中间存在网络延迟，因此我们收到时间时已经滞后了。

一般机器还会提供一个单调时钟，它们能保证递增的性质，比如System.nanoTime()。单调时钟适合用来测量持续的时间段，比如超时和计时，但是它的具体值是没有意义的，因为每次机器重启后可能都会重置单调时钟。同时单调时钟的精度要比墙上时钟更高，其一般是微妙级的，而墙上时钟则是毫秒级的。

如果非要使用墙上时钟的话，一般时间API返回一个置信区间是个不错的选择。[L,R]表示当前时间落在该区间中，区间的大小取决于上一次NTP同步的时间。

分布式锁

分布式锁存在一个非常常见的问题，就是网络抖动导致锁被释放，或者持有锁的进程长时间没有被调度，再次被调度的时候锁已经过期却无法感知。我们无法在做每一次操作之前都去检查锁是否有效，因为这不仅会导致性能极度下降，同时由于CPU调度的不确定性，依旧可能存在检查完成后被调度的风险。

一种解决方案是使用fencing令牌。每次我们锁服务授予锁的时候同时返回一个fencing令牌，该令牌每授予一次就会递增。让后客户端每次向资源服务器发送请求的时候，需要带上已经持有的fencing令牌信息。由资源服务器来判别锁是否有效，如果有效才做修改操作。资源服务器可以直接对某个资源上锁的信息记录到该资源的元数据上，这样每次请求都只需要比较一下资源当前锁是否比上一次加锁的序列号大即可。

一致性

线性化

线性化是指，表现的就好像只有一个数据副本，且其上的所有操作都是原子的。

因果关系

最简单的线性化实现就是使用串行化的方式，但是它的存在严重的性能问题。保证线性化需要牺牲性能，而大部分时候我们都可以选择性能更好的因果关系来替代线性化要求。因果关系允许并行执行那些没有关联的请求，从而提高性能。

因果关系为操作赋予了偏序关系，而线性化为操作赋予了全序关系。

如果两个操作没有因果关系，则我们可以并发执行，提高性能。CPU的指令重排就满足了因果关系。

在数据库中可以通过版本号来保持因果关系，我们可以通过将先前读到的行的版本号传回数据库，而数据库则需要检查这些行是否是最新的。因此数据库需要跟踪事务读取了哪些版本的数据。但是事务可能会读取大批的数据，但是可能仅关注其中少量记录的版本号，显式跟踪是一个不小的成本。

更好的方式是为每个操作分配一个序列号，因的序列号一定要小于果的序列号。这样我们就能确定因果关系。

• 如果是单master，那么我们可以由单master负责生成递增的序列号。这种方案存在性能。
• 如果是多master，我们可以将同一个事务的序列号全部路由到一个master上生成序列号。这个方案存在热点问题。

更好方案是使用“Lamport时间戳”。我们为每个节点维护一个计数器，并且分配一个节点id，而我们生成的序列号是一个二元组(计数器值,节点id)，以计数器值为第一关键字，节点id为第二关键字排序。这个算法的关键点在于每次去请求序列号的时候要带上我们现在获得的最大计数器值。当序列号生成服务受到请求时，如果发现请求中的计数器值大于本地的，则将当前计数器值设置请求中的计数器值。之后自增得到新的计数器值。

全序关系广播

但是即使我们为每个操作分配了序列号，对于很多并发场景依旧会有问题。比如多个客户端要获得分布式锁，当节点收到请求后，节点并不能直接判断请求是否成功，因为它们不知道是否有其它抢锁的请求有更小的时间戳。为了获得这些信息，系统必须检查所有的节点，询问它们在做什么，而如果这时候一个节点出了故障，那么这个方法就没法失效了。

最简单的就是使用主从模型，但是会遇到单点写入瓶颈。

全序关系广播是指节点之间交换信息的某种协议，它需要满足下面两个性质：

• 可靠发送，没有消息丢失
• 严格有序，消息总以相同顺序发送给每个节点

如果中间发生了网络故障，那么全序关系广播必须通过不断重试，在故障修复后将消息分发给所有其它节点。

全序关系广播与线性化的区别：

• 全序关系广播是基于异步模型，仅保证消息的可靠发送和有序性，不保证消息具体什么时候发送
• 可线性化强调就近性，读取时保证能看到最新的写入值。

如果还需要持久化存储，那么我们可以通过日志复制的方式实现全序关系广播。

比如在我们的分布式锁场景：

1. 节点在日志中首先追加一条消息，指明获取的是哪把锁。
2. 将日志广播给所有节点，并等待它们的响应
3. 如果某个节点声称锁已经被获取了，且时间戳最小的是当前节点的回应，则提交操作，否则中止操作。

我们上面解决的是写操作的顺序一致性，其仅保证写入是顺序的，但是不能保证读操作能读到最新的值，因此并不能保证线性一致性。一种简单的解决方案是将读操作也广播给所有节点，最后根据所有节点的回复合并得到结果返回给客户端，这样就能保证线性一致性了。

共识算法

FLP结论表明在不使用时钟或超时机制的情况下，如果节点可能崩溃，那么不存在总是能达成共识的算法。

但是在允许使用时钟和超时机制检测崩溃节点的情况下，还是存在不少共识算法的。

共识算法一般原理就是选主，之后由主节点发起投票，其余节点进行投票。可能因为网络原因，出现多个主节点，所有节点只认同最后一个它投票支持的主节点，拒绝其余主节点的投票。而每次投票赞成的人数必须达到半数以上（法定人数），投票才通过。

两阶段提交

一般单一节点的数据库事务可以由存储引擎实现，其原理就是通过记录日志的方式将事务操作记录持久化到磁盘上，一旦中间发生宕机重启，则可以根据事务是否提交来选择是否撤销事务的操作。

而跨节点的事务并不能通过对所有节点提交事务实现。因为可能会出现部分事务提交成功，而一些事务提交失败（如无法获得锁，违反约束，节点崩溃，网络断开等）的情况。这时候由于无法撤销已经提交的事务，因此存在不一致的状态，事务的原子性无法得到保证。

这种情况下，需要用另外一个事务抵消掉已经提交的事务，这种事务称为补偿性事务，补偿性事务是由应用层发起的。

两阶段提交（2PC）算法引入了一个新的组件：事务管理器，而其余数据库节点称为资源管理器。两阶段提交的第一阶段如下：

1. 事务管理器发送prepare请求到所有资源管理器，要求它们预留事务需要的资源。
2. 事务管理者收到所有资源管理器的回复。

两阶段提交的第二阶段：

1. 如果第一阶段所有资源管理器全部回复成功，则事务管理器发送commit请求到所有资源管理器，提交本地事务。
2. 否则第一阶段至少有一个资源管理器回复失败，则事务管理器发送rollback请求到所有资源管理器，回滚本地事务。

这里实际上可以发现即使是两阶段提交，也可能会遇到网络或节点崩溃的问题。

先考虑资源管理器节点崩溃。发生在第一阶段，这时候事务并没有真的提交，并且事务管理器会决定回滚事务，因此不会带来影响。如果发生在第二阶段，那么要求事务管理器根据资源管理器的回复，做出提交还是回滚的判断，并将决定持久化。之后事务管理器需要发送决定给其它节点，如果这时候遇到故障，则事务管理器必须不断重试直到成功（如果节点崩溃，那么需要等待节点恢复后继续执行），开弓没有回头箭。

再考虑事务管理器节点崩溃。那么但凡接受了prepare操作的节点，就不能因为超时原因释放prepare操作锁定的资源，它们必须等待事务管理器节点恢复后做出决定。事务管理器节点恢复后，根据本地日志决定是否提交事务（如果之前写入了决定，就是用这个决定，否则回滚）。但是这里实际上有一个故障点，就是协调者存在单点问题，一旦协调者的磁盘损坏，那么将会出现悬而未决的事务始终持有着资源的情况，这种时候一般需要人工介入，或者将协调者做主从。

目前X/Open XA(eXtended Architecture)是异构数据库下实现两阶段提交的一个工业标准。目前，许多关系数据库和消息队列都支持XA。

XA并不是一个网络协议，而是一个与事务协调者进行通信的C API，当然它也支持其它语言的API绑定，比如在java中就有JTA（Java Transaction API）。事务协调者需要实现XA API，一般情况下，协调者也是一个API库，它与产生事务的应用程序运行在相同进程中，这些API会负责跟踪事务中的所有参与者，协调它们进行prepare工作，之后根据参与者的投票，在本地磁盘的日志文件中记录事务的最终决定。

批处理系统

除了我们日常见到的在线服务外，还有一种专门处理大批量数据的批处理系统。前者以响应时间作为主要衡量指标，后者的衡量指标则是吞吐量。

MapReduce

UNIX系统使用了管道的概念，允许我们组合现成的工具处理大批量的数据。但是这种方式只能处理单机的数据，要处理多机的数据，需要使用到像MapReduce这种批处理框架。类似于UNIX系统中的命令，MapReduce保证只读输入文件，因此多次执行MapReduce不会带来副作用。

1. 读取一组输入文件，将其分解为记录。
2. 调用mapper，从输入记录中提取一个键值对。
3. 将所有键值对按照关键字进行排序。
4. 调用reducer函数遍历排序的键值对，进行合并操作。

mapper和reducer的代码需要用户自己编写。

MapReduce的输入文件一般几百兆，只要资源充足，MapReduce调度器会尝试在持有输入文件副本的机器上运行mapper任务。这样可以避免文件通过网络传输带来的网络负载。调度决定的机器上可能没有mapper的代码，调度器会自动复制代码（JAR文件）过去，之后启动map任务。

Map和Reduce任务为了能水平扩展，需要对任务进行切片处理。Map的切片是基于文件块进行切片的，同一个文件块仅由同一个Map任务处理。而Reduce则会根据Map得到的键值对，按照关键字的哈希值进行切片，这样可以保证相同关键字的键值对由同一个Reduce任务处理。

实现上Map会先根据mapper产生的键值对进行分区，之后对各个分区进行排序，得到排序后的分区文件。之后MapReduce调度器会通知reducer开始从mapper中获取输出文件。

如果要通过MapReduce实现UNIX的管道的效果，需要将第二个MapReduce的输入和第一个MapReduce的输出目录配置为同一个，并在结束了第一个MapReduce任务后再启动第二个MapReduce任务。

分组和Join

考虑这样一个场景，我们要处理用户行为日志，分析每个行为在各个年龄段受欢迎程度。但是日志中仅记录了用户的ID。

有两种方案：

• 将年龄段记录到日志中，这样会浪费很多存储空间，并且还需要提前预判到有这样的需求。
• 在处理日志的时候，拿ID去数据库查找。这会导致大量的数据库查询操作，拖慢性能。

一种更好的办法是通过MapReduce合并数据。先将数据库副本拷贝到日志所在的分布式文件系统中。之后分别对日志和数据库副本中的用户数据调用Map操作，它们都根据用户ID进行哈希。这样就能保证reducer执行的时候，用户的数据库记录和操作日志紧密排列，避免了查询数据库的消耗。

而分组操作也比较场景，比如上面的案例中，我们后面还需要根据年龄段进行分组，统计各个年龄段的点击次数。我们可以在Map阶段将分组作为关键字即可。

热点数据

如果存在热点key，那么某个reducer的执行时间就会变得很长。解决方案如下

1. 第一次MapReduce，将每个key后面加个不大的随机数（如果是Join操作需要把Join用到的数据复制多份）。
2. 在第一次MapReduce的结果，执行通用的MapReduce操作。

流处理系统

批处理系统正常运行需要保证输入是有界的。对于实时生成的数据，批处理系统必须将数据按照时间分块，并计算之前时间块的数据。比如今天只能看到昨天的数据报表。

在批处理系统中，文件被写入一次，被多个作业读取。流处理系统中也类似，事件由生产者生成一次，然后由多个消费者消费。

由于事件生产的时间不确定，因此不适合使用拉模式来消费消息，而应该用推模式来主动向消费者推送事件。推送新事件的常见方式是使用消息系统。

传统数据库不适合用于实现消息系统，而消息队列则很适合用来实现消息系统。

在有多个消费者的时候，消息的消费方式有两种：

• 负载均衡式：每一条消息只能传递给一个消费者。
• 扇出式：每一条消息都传递给所有消费者。

消费者可能在消费消息的过程中崩溃，为了确保消息不丢失，消息队列应该使用确认机制。只有客户端处理完消息后显式告诉消息队列，消息队列才允许将消息从队列移除，超时或网络断开等不确定情况下，消息队列应该保守认为消息未消费并重新投递。

日志是一类磁盘上支持追加操作的序列，我们可以使用相同的结构来实现消息队列。生产者将消息追加到日志的末尾来发送消息，消费者则通过依次读取日志来接收消息。

为了突破单机的瓶颈，可以对日志进行分区。将分区分布到不同的节点上，并将拥有相同类型数据的分区组称为主题。在每个分区中，代理为每个消息都分配一个单调递增的序列号或偏移量。由于分区只能追加，因此同一个分区的消息的写入一定是有序的，不同分区则没有保证。

如果我们不删除日志，那么多个消费者可以独立读取日志而不互相影响，这样就很自然的支持扇出式消费消息。为了支持负载均衡式的消费消息，消息队列可以将整个分区分配给消费者组中的节点。这样不同的消费者组消费的分区是不相交的，就保证一条消息仅由一个组中的所有消费者消费。

顺序读取一个分区可以避免判断那些消息被消费过。

如果我们都不做删除操作，那么最终磁盘必定会被耗尽。一种是解决方案是将日志文件（一个分区）分割为若干个段，并且定期归档或删除最老的段。这意味着如果消费者的消费能力不足，那么它势必会失去消费一些消息的机会。

参考资料

• Grokking the System Design Interview
• 《数据密集型应用系统设计》
• 如何验证线性一致性