几个有意思的分布式系统设计模式

分布式系统有它特有的设计模式，无论意识到还是没有意识到，我们都会接触很多，网上这方面的材料不少，比如《Catalog of Patterns of Distributed Systems》，还有《Cloud Design Patterns》等等。这里简单谈谈几个我接触过的，也觉得比较有意思的模式。

LSM Tree

对于这个话题，基本上第一个在我脑海里蹦出来的就是 LSM 树（Log Structured Merge Tree）。其实，LSM 树本来只是指一种数据结构，这种数据结构对于大吞吐量的写入做了性能上的优化（比如日志写入），同时对于根据 key 的读取也有不错的性能。换言之，对于读写性能的平衡，大幅优化了写入，而小幅牺牲了读取，现在它也不再被局限于数据结构本身，而是泛化为能够提供这样特性的一种机制。

整个写入过程分为两个部分，为了追求极致的写入速度，写入方式都被设计成追加的：

C0：这一层其实就是内存中写入的 buffer，它的实现可以用 RBTree，或者是 SkipList，这种树状有序的结构，它的写入和范围查询都很快。在 Bigtable 的设计中，它被称为 Memtable。
C1：这一层则主要待在磁盘上了，它可以由若干个文件组成，每一个文件都是有序的数据，这样拿着一个 key 去文件查询对应的数据，根据 indexed keys 可以用二分法来查找。在 Bigtable 的设计中，它就是 SSTable。

所以，为了追求写性能，数据写入会直接插入到 C0 中，一旦 C0 达到一定大小，就会建立一个新的 C0’ 来替代旧的，而原有的 C0 会被异步持久化成 C1 中的一个新文件（其实就是做 snapshot）；C1 中的文件全都是有序的，它们会不断地被异步 merge，小文件不断被合并成大文件（下图来自维基百科）。极端情况下，同一个 key 可以有若干次更新，并且更新能同时存在于 C0 和 C1 所有的文件中。

对于根据 key 的查询，需要先去 C0 中找，如果找到了最好，没找到的话需要去 C1 中找，最坏的情况下需要找每个文件。如果数据存在于多个地方，数据采用的优先级是，C0> 新的 C1 文件> 旧的 C1 文件。

对于不存在 C0 中的数据查询，为了尽量避免去每一个 C1 的文件中查询，Bigtable 会使用 bloom filter 来做第一步的存在性判断（校验用的数据全量加载在内存中），根据结果，如果这一步判断通过，这意味着数据可能存在于目标文件；如果没通过，这意味着数据肯定不存在于目标文件。

Write-Ahead Log

顺着 LSM Tree 的话题，说到 WAL。WAL 适用于解决这样一个问题：一个系统对于写请求有较苛刻的延迟或者吞吐量的要求，同时又要严格保证 durability（数据不丢）。

因此直观上，WAL 包含三步：

首先要求 append 日志，日志是持久化的，并且可以根据一致性的要求持久化到不止一个存储中
接着就是把数据更新到内存的某个数据结构中（比如上面的 LSM Tree 在内存中的结构 C0），这时候同步的请求响应就可以发回客户端了
C0 的数据会异步 merge 压缩到持久性存储 C1 中（LSM Tree 部分的操作）

基本上思路就是把能延迟的操作全延迟了，如果服务端挂掉了，根据持久性存储+日志就可以完全恢复到挂掉之前的状态，因此数据不会丢。

于此，有一系列相关的 pattern，比如：

Low-Water Mark，低水位线：指的是这条线以前的数据全部都以常规方式持久化了（C1），因此如果节点挂掉的话，只需要根据现有的文件+低水位线以上的日志就可以完全还原挂掉之前的状态，也就是说，理论上低水位线以前的日志可以删掉了；
High-Water Mark，高水位线：日志是持久化的，但是这个持久化需要在多个节点上发生，这条线就指向了最新一条已经成功持久化到 “大多数” 节点上的日志（这个大多数其实就是 Majority Quorum 模式）。
Hinted Handoff，提示性移交，它和 WAL 有一定类似性，因此经常被放在一起比较：如果一个节点挂掉了，那么更新会跑到另外一个（随机的）节点上面去，等到挂掉的节点恢复的时候，这些数据会被重新写入那个恢复的节点，执行 replay 从而恢复一致性。

Clock Bound Request Batch

Request Batch 太常见不过了，请求可以批量发送，减少 overhead，从而减少资源（网络带宽、序列化开销等等）的消耗。通常的 batch 是根据大小或者数量来划分批次的，但是修饰词 Clock Bound 指的是，这样的分批还要依据时间，就是说，系统可以等待一段时间，这一段时间内的请求都可能打包成一个 batch，但是这样的打包还要有时间限制，到了这个时间，无论当前的 batch 有多小，都必须要发送出去了。

Kafka 客户端就有这样的一个机制，message 可以被 group，但是：

batch.size 这个参数指定 batch 最大有多少；
linger.ms 这个参数指定了最多等多久。

还有一些流处理系统也采用这种方式，比如 Spark 的 micro batching。

Singular Update Queue

Singular Update Queue 非常有用，queue 本身就是用来处理异步的事件，可以有若干个 producer 产生消息到队列里面，有若干个 consumer 来处理它们。这种场景下这个 queue 为核心的机制扮演了至少这样几个角色：

缓冲，平滑请求的波峰；
流控，保护下游系统不被负载冲垮；
校验，能写入 queue 的数据一定是符合格式的，从 queue 读取的数据也一定是符合格式的；
解耦，对于 MxN 的调用关联关系，所有的 producer 只和 queue 打交道（写入），而所有的 consumer 也之和 queue 打交道（读取），这样，复杂度就变成了 M+N。

对于写请求，我们需要保证这些事件处理不会有并发的问题，通过采用 Singlar Update Queue，对特定的 topic，我们可以设计一个良好的 sharding 规则，加上对于每一个 sharding（在 Kafka 等系统里面我们叫做 partition），设置为只有一个 consumer 线程，这样的话就保证了不会有并发问题，因为只有一个线程来处理所有这个 sharding 的消息，这种方式可以简化系统，不需要引入第三方锁系统就可以处理同一个 sharding 之间存在并发冲突的消息。

我想起另外一个相关的话题，monolith（单体应用）还是 microservices（微服务），一直是一个争论。早些时候，在微服务概念刚提出的时候，它受到了追捧，但是现在出现了越来越多批评的声音。一个突出的微服务的问题就是各个微服务之间像蜘蛛网一样复杂调用依赖的问题。而这样的问题，其中一个解决办法就是引入这样的 queue 在中间解耦。

有些时候，queue 里面未必存放全部完成 update 所需的数据，而是只放很少的内容，比如只有一个 key，consumer 拿到这个 key 以后去别的 service 获取完成任务需要的信息，因此这个 queue 就起到一个通知的作用。这其实就是 Claim Check 模式了。

Asynchronous Request-Reply

Asynchronous Request-Reply 本身是一个简单而且常用的机制，就是请求发起以后，服务端响应说，请求任务正在处理中，并返回给 client 一个 token。后续 client 拿着这个 token 就可以来（可以是另外一个单独的用于状态查询和结果获取的服务）查询请求的处理状态（poll），同时，服务端也可能会通知（push）客户端情况。

不过，既然上面谈到了 Singular Update Queue，它们俩有时是有关联的。

在使用 Singular Update Queue 的时候，如果 consumer 处理一个消息需要花很长的时间，那么它就可能成为整个系统吞吐量的瓶颈。很多时候，这个 consumer 花很长时间来处理往往不是因为有复杂的 CPU 计算，而是等待，比如等待一个远程调用结束，等待一个文件写入结束等等。

对于这样的问题，有两种解决思路：

一种是划分出更多的 partition，这样就可以设置更多的 consumer 线程来处理，但是这种方法带来的代价是更高的 overhead。
第二种是把处理流程变成异步执行的，而把它变成异步的就意味着系统没法直接妥善处理异步处理结果（它可能成功，也可能失败），因此对于这样一个子问题，有两个进一步解决的思路：
1. 触发处理流程之后，预约下一个 “回访”，也就是采用这里提到的 Asynchronous Request-Reply 这样的机制，但是这个回访需要在一定时间后发生，并且一定要发生，因此这需要一个高可用的定时任务的服务（需要支持重试策略和失败处理），或者是封装一个 delay queue，即里面的消息需要过一段时间才能被 poll 到，因此这个机制有可能会比较复杂。
2. 还有一个思路则是让 consumer 来集成 Coroutine，这样一个 consumer 线程可以被分享同时处理若干个消息，这些消息都来自同一个 partition（有一些开源库就专干这个事儿），于是这样多个消息就可以被同一个线程以非阻塞的方式并行处理。这个方法的一个局限性是，这些消息在 Coroutine 框架内处理时，不能存在并发冲突的问题。

Rate Limiting & Throttling

最后比较一下 Rate Limiting 和 Throttling。我也是不久前才区分清楚，以前我基本是把它们混在一起使用的。它们都是用来限流的，并且有多重不同的方式，可以是基于 fixed window，sliding window 等等。

但是它们的区别，本质上是它们工作的角度不同。Rate Limiting 是从 client 的角度来管理资源的，比如说，规定某一个/每个用户对于资源的访问不能超过一定的限度，因为资源不能让一个客户端全占了，这样其他人才可以有访问资源的权利；而 Throttling 则是从 service 的角度来管理资源的，比如说，规定某个/每一个 API 的访问 throughput 上限是多少，一道超过这个限度，请求就会被拒掉，从而保护服务。

和这两个可以放在一起的，其实还有一个 Circuit Breaker，不过 Circuit Breaker 的功能和这两个有较大区别，不太容易弄混，因此就不赘述了。

文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接《四火的唠叨》