Algorithm
本周选择的算法题是：Pascal’s Triangle
规则如下：
Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
Solution
我实现的方案：
Runtime：24 ms，快过 87.56%。
Memory：12.7 MB，低于 100%。
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows == 0: return []
if numRows == 1: return [[1]]
result = [[1]]
for row in range(1, numRows):
result.append([1])
for col in range(1, row):
result[row].append(result[row-1][col-1] + result[row-1][col])
result[row].append(1)
return result
Review
Can You Answer This Simple Swift Question Correctly?
这个问题确实容易掉入陷阱，主要的误区在于：
Block 的参数传递语法:
xxx in {}Block 的方括号捕获语法:
[xxx] in {}
至于文章后段提到的值类型和引用类型就是老生常谈的话题了，略过。
Tip
关于分页的 API 设计，IETF 专门做了一个 link 域，不过比较少见，目前看来 GitHub 实践的很好：
Share
弹力设计的几点思考
补偿事务
传统的关系型数据库特点：
- Atomicity - 原子性，要么全部成功要么全部不成功
- Consistency - 一致性，开始前和结束后，数据库的完整性没有被破坏
- Isolation - 隔离性，两个事务是互不干扰和可见的
- Durability - 持久性，事务完成之后，该事务对数据库的修改将永久保存
但在分布式系统中，ACID 很难达到高性能的要求，CAP 定理：
- Consistency - 一致性，同一时刻有同样的值
- Availability - 可用性，一部分节点挂掉后，系统还能提供服务
- Partition tolerance - 分区容忍性，子节点遇到网络分区时，需要在 C 和 A 之间进行取舍
由于 CAP 不能被同时满足，为了提高性能，出现了 Base：
- Basic Availability - 基本可用，系统可以暂时出现不可用，后面会恢复
- Soft-state - 软状态，为了性能，可以让服务暂时保存一些状态或数据
- Eventual Consistency - 最终一致性，系统在一个短暂的时间段时不一致的，但最终整个系统看到的数据是一致的
要实现 BASE，需要在系统内引入业务补偿机制，即：
- 系统需要努力地通过一系列的操作达到一个我们想要的状态
- 如果达不到，就需要通过补偿机制回滚到之前的状态
设计重点：
- 服务方需要支持幂等性，并且在上游有重试机制
- 需要有一个高可用和稳定的工作流引擎，用来持有一个业务流程中的状态
- 在设计正向业务流程时，也要设计业务的反向补偿流程
- 业务补偿是强业务相关的，很难做得通用
- 下层的业务方最好要有短期的资源预留机制
重试设计
重试的前提是：这个故障是暂时的，而不是永久的，所以，我们会去重试。
可重试的场景：
- 调用超时
- 被调用方返回了某种可以重试的错误（如繁忙中、流控中、维护中、资源不足等）
有些错误是没必要的重试的：
- 业务级的错误（如没有权限、或是非法娄持等）
- 技术上的错误（如 HTTP 的 503），重试下去没有意义
Spring 下的常见重试策略：
- NeverRetryPolicy - 不允许重试
- AlwaysRetryPolicy - 无限重试，直到成功
- SimpleRetryPolicy - 固定次数的重试策略
- TimeoutRetryPolicy - 超时时间重试策略，在指定的超时时间内允许重试
- CircuitBreakerRetryPolicy - 带有熔断功能的重试策略
- CompositeRetryPolicy - 组合重试策略，有两种组合方式：
- 乐观 - 只要有一个策略允许重试就重试
- 悲观 - 只要有一个策略不允许重试就不能重试
Backoff 策略：
- NoBackOffPolicy - 无退避算法
- FixedBackOffPolicy - 固定时间的退避策略
- UniformRandomBackOffPolicy - 随机时间退避策略
- ExponentialBackOffPolicy - 指数退避策略
- ExponentialRandomBackOffPolicy - 随机指数退避策略，引入随机乘数
重试设计的重点：
- 什么错误下可以重试
- 重试的时间和重试的次数
- 被调用方是否有幂等设计
熔断设计
熔断设计的目的：可以防止应用程序不断地尝试执行可能会失败的操作，使得应用程序继续执行而不用等待修正错误，或者浪费 CPU 时间去等待长时间的超时产生。熔断器模式也可以使应用程序能够诊断错误是否已经修正。如果已经修正，应用程序会再交尝试调用操作。
熔断设计的三个状态：
- 闭合（Closed）状态 - 需要一个调用失败的计数器，如果最近失败的次数超过了一定的阀值，则切换到断开状态，此时开启一个超时时钟，如果该时钟超过了该时间，则切换到半开状态
- 断开（Open）状态 - 在该状态下应用程序立即返回错误或者缓存的数据
- 半开（Half-Open）状态 - 在该状态允许一定数量的请求去调用服务，如果调用成功，则切换到闭合状态，否则切换到断开状态
熔断设计的重点：
- 错误的类型 - 需要对错误进行识别，一些错误先走重试，重试几次后再打开熔断，还有一些错误不必走重试
- 日志监控 - 能够记录所有失败的请求，以及一些可能会尝试成功的请求，使得管理员能够监控使用熔断器保护服务的执行情况
- 测试服务是否可用
- 手动重置 - 系统恢复时间很难确定，提供一个手动重置功能能够使得管理员可以手动地强制将熔断器切换到闭合状态
- 并发问题 - 对调用结果进行统计可能涉及到对共享数据结果的操作，最好使用一些无锁的数据结构，或是 atomic 的原子操作，尽量提高性能
- 资源分区 - 资源可能分布在不同的分区上，熔断器需要只对有问题的分区进行熔断，而不是整体
- 重试错误的请求 - 有时候，错误和请求的数据和参数有关系，记录下出错的请求，在半开状态下重试能够准确地知道服务是否真的恢复，这需要被调用方支持幂等调用
实现熔断器模式可以使得系统更加稳定和有弹性，在系统从错误中恢复的时候提供稳定性，并且减少了错误对系统性能的影响。
限流设计
限流的目的：
- 为了向用户承诺 SLA。保证系统在某个速度下的响应时间以及可用性
- 防止在多租户下，某一用户把资源耗尽而让所有的用户都无法访问
- 为了应对突发的流量
- 节约成本。不会为了一个不常见的峰尖来把系统扩容到最大的尺寸，而是在有限的资源下能够承受比较高的流量
简而言之，限流就是保护系统不会在过载的情况下出现问题。
限流的策略：
- 拒绝服务。反多出来的请求拒绝掉。
- 服务降级。关闭或是把后端的服务做降级处理，把资源留给更重要的功能。
- 特权请求。把有限的资源分给重要的用户。
- 延时处理。用一个队列来缓冲大量的请求，一般用于短暂的峰刺请求。
- 弹性伸缩。对服务做自动化的伸缩。
常见的实现方式：
- 队列算法
- 均速队列
- 有优先级的队列
- 权重队列
- 漏斗算法 - 当请求过多时，队列就开始积压任务，如果队列满了就会开始拒绝请求，漏斗算法其实就是在队列请求中加上一个限流器，让 Processor 以一个均匀的速度处理请求。
- 令牌桶算法 - 有一个中间人在一个桶内以一定的速率放入一些 token，然后处理程序要处理请求时，需要拿到 token 才能处理请求；相对于漏斗算法，令牌桶算法在流量少时“攒钱”，流量大时可以快速处理。
上面这些算法都需要一个确定的限流值。也可以基于响应时间做动态限流：
- 需要计算一定时间内的 P90 或 P99
- 需要像 TCP 流控那样，需要一个当前的 QPS，然后动态调整它