CodingTour —
ARTS #30

Algorithm

本周选择的算法题是：Combination Sum

规则如下：

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Solution

我实现的方案：

Runtime：48 ms，快过 96.74%。

Memory：12.9 MB，低于 100%。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        dp = [[[]]] + [[] for length in range(target)]
        for candidate in candidates:
            for index in range(candidate, target + 1):
                position = index - candidate
                dp[index] += [combination + [candidate] for combination in dp[position]]
        return dp[target]

这是在 IDE 里反复调试并优化后的版本，最初的版本如下：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        self.dp(candidates, 0, [], target, result)
        return result
    
    def dp(self, 
           nums: List[int], 
           sum: int, 
           list_to_sum: List[int], 
           target: int, 
           result: List[List[int]]):
        if len(nums) == 0: return

        num = nums[0]
        if sum + num == target:
            result.append(list_to_sum + [num])
            return
        elif sum + num > target:
            return
        
        self.dp(nums, sum + num, list_to_sum + [num], target, result)
        self.dp(nums[1:], sum + num, list_to_sum + [num], target, result)
        self.dp(nums[1:], sum, list_to_sum, target, result)

性能上大打折扣：

  • 过多的重复计算
  • 需要对结果去重

Review

These four “clean code” tips will dramatically improve your engineering team’s productivity

作者在文章提到了一些想法：

  • “如果它没有经过测试，那它就是坏的” - 做大量测试，特别是单元测试，否则你会后悔
  • 选择有意义的名称 - 使用简短、精确的变量名、类名和方法名
  • 类和方法要足够小到符合单一职责 - 它们应该只做一件事
  • 方法应该没有副作用 - 不能修改入参、满足幂等设计

基本的概念就跳过了，看看这段代码：

function getUserByEmailAndPassword(email, password) {                    
  let user = UserService.getByEmailAndPassword(email, password);
  if (user) {
    LoginService.loginUser(user);  // Log user in, add cookie (Side effect!!!!)
  }
  return user;
}

有几个问题：

  1. 有副作用。通过方法名能猜到这是一个查询用户的接口，除此之外这个方法还做了登录并写入 cookie，这个逻辑有可能会写在文档里，但是对现代的 IDE 来说，代码提示已经很智能了，程序员并不一定会先读文档再写代码，这是一个潜在的风险
  2. 不容易测试。在单元测试中你需要构建依赖，我们希望依赖越少越好，这样测试的效率才高，由于该方法内部需要走网络请求，你不得不在测试“根据邮箱和密码返回用户”时构建一个 HTTP 请求或者 mocking。
  3. 耦合。第2点谈到了可测试性，依赖多了耦合就多了，查找用户和登录用户应该是两个功能，这是没必要的耦合，而且这个耦合很可能会在未来被解掉，所以这个方法并不安全 - it’s not “future proof”。

Tip

本周正式接入了自动化测试。为了提高测试效率，我们引入了自动化更新、部署，主要是采用 git + watchdog 的方式实现。

为了改善 UAT(User Acceptance Test) 效率，我们在平台接入了自研的极速 UAT 方案，后续的性能瓶颈可能会集中到服务器。

Share

一个完整的 PaaS 平台包括：

  • 调度层 - PaaS 的自动化和分布式对高可用、高性能的管理
  • 能力服务层 - PaaS 对外提供的服务和能力
  • 流量调度 - 流量调度相关的东西，含对高并发的管理
  • 运营管理 - 软件资源库、软件接入、认证和开放平台门户
  • 运维管理 - DevOps 相关的东西

弹力设计

要提高系统的可用性，需要在系统中引入弹力设计。弹力设计又叫容错设计，容错能力包括：

  • 服务治理 - 服务隔离、异步调用、请求幂等性
  • 可伸缩性 - 有/无 状态的服务
  • 一致性 - 补偿事务、重试
  • 应对大流量的能力 - 熔断、降级

弹力设计以提高系统的可用性为保障的重点。

可用性计算公式为：

Availability = MTTF / (MTTF + MTTR)

MTTF - Mean Time To Failure，平均故障前的时间

MTTR - Mean Time To Recovery，平均修复故障的时间

要提高可用性，要么提高 MTTF，要么降低 MTTR。

分布式系统故障发生是常态，一般有以下几种原因的故障：

  • 网络问题。带宽拥塞、链接不稳定等
  • 性能问题。数据库慢 SQL，Java Full GC，硬盘 IO 过大，CPU 使用率过高，内存不足等
  • 安全问题。被网络攻击，如 DDoS 等
  • 运维问题。系统总是在被更新和修改，架构也在不断地被调整，监控问题等
  • 管理问题。没有梳理出关键服务以及服务依赖、调用的“地图”，运行信息没有和控制系统同步等
  • 硬件问题。硬盘损坏，网卡出问题，交换机出问题，机房问题等

分布式下不要尝试去避免故障，要将故障的处理逻辑当成正常的功能做在架构里：

  • 故障是正常的，而且是常见的
  • 故障是不可预测突发的，而且相当难缠

好的弹力设计就是想尽一切办法降低 MTTR。

服务隔离

服务隔离就是将系统分离开，有两种分离方式：

  • 按服务分离 - 每个服务的域名、服务器、数据库独有，服务间完全隔离
  • 按用户分离 - 将用户分成不同的组，组与组隔离，即多租户模式

多租户按隔离程度有三种方式：

  • 完全独立 - 每个租户都有自己完全独立的服务和数据
  • 独立的数据分区，共享的服务 - 服务间共享，数据分开隔离
  • 共享的数据，共享的服务 - 每个租户的数据和服务都是共享的

隔离设计的重点和考量：

  • 需要清楚地定义隔离业务的大小和粒度
  • 需要结合系统的复杂度、成本、性能、资源使用的情况，找出一个合适的均衡方案，不存在什么都满足的系统
  • 需要搭配一些高可用、重试、异步、消息中间件，流控、熔断等设计模式
  • 需要结合自动化运维的管理工具，驾驭复杂度
  • 需要一个服务“地图”，能监控完整的服务状态、依赖

异步调用

异步调用可以让服务间的解耦更彻底，同时可以起到削峰的作用。

同步调用会带来的问题：

  • 整个调用链的性能由最慢的那个服务决定
  • 调用链的参与方会有相同的等待时间，消耗资源
  • 同步调用很难做到一对多
  • 同步调用容易产生多米诺骨牌效应

异步通讯相对于同步来说，除了可以提高系统的吞吐量，最大的一个好处是可以让服务间的解耦更为彻底，调用方和被调用方可以按照自己的速率而不是步调一致，让系统更有弹力。

异步通讯的三种方式：

  • 请求响应式：
    • 发送方时不时轮询一下
    • 调用多将回调地址给被调用方
  • 订阅的方式 - 观察者的形式
  • 通过 Broker 的方式 - 由 Broker 中间件解耦订阅的双方，事件驱动的最佳实践

事件驱动的好处：

  • 服务间的依赖没有了
  • 开发、测试、运维、故障处理都是高度隔离的
  • 服务间通过事件关联，不会相互 block
  • 服务间容易增加一些 Adapter（如日志、认证、版本、限流、降级、熔断等）
  • 各服务可以按照自己的速率来处理事件

异步通讯的开发注意事项：

  • Broker 成了关键，需要设计成高可用不丢消息的
  • 流程不直观，需要有相应的跟踪机制
  • 需要有一个总控方管理状态
  • 需要考虑像 TCP 那样的 send 和 ACK 机制，服务的幂等性

请求幂等性

幂等性的定义是一次或多次调用具有相同的副作用。以 HTTP 请求 Method 来说：

  • GET - 虽然请求的返回数据可能不一样，但没有产生副作用，所以是幂等的
  • HEAD - 和 GET 一样，但是仅返回头信息，所以也是幂等的
  • OPTIONS - 获取请求 URL 支持的全部 Method，幂等
  • DELETE - 有副作用，但是是幂等的
  • POST - 每次调用会创建资源，所以不是幂等的
  • PUT - 每次更新同一个资源，有副作用，但是是幂等的

除此之外要做到幂等性，还需要有全局唯一的 ID，特别是在分布式的场景下，可以参考 Twitter 的 Snowflake 算法：

  • 它是一个分布式 ID 的生成算法
  • 产生的是一个 Long 型的 ID
    • 1bit，总是为 0
    • 41bits 作为毫秒数，大概可以用 69.7 年
    • 10bits 作为机器编号（5bits 是数据中心，5bits 是机器 ID），支持 1024 个实例
    • 12bits 作为毫秒内的序列号，一毫秒可以生成 4096 个序号

服务的状态

可伸缩的系统对服务的状态管理要求比较高，无状态的服务特点是没有副作用，可轻松扩展和运维。因此无状态的服务被当作分布式服务设计的最佳实践。

为了做出无状态的服务，我们需要将服务的状态存储到其他地方，比如 Redis、MySQL、ZooKeeper/Etcd

等第三方存储服务中，这些服务必须也做成高可用和高拓展，同时为了减少网络开销，无状态的服务需要增加缓存机制。

无论服务是否带有状态，底层的分布式数据库或分布式文件系统都是系统的关键组成部分，它可以：

  • 减少服务启动或恢复的时间，变相提高系统的可用性
  • 减少节点间的通讯开销
  • 数据持久化，避免状态丢失