CodingTour —
ARTS #33

Algorithm

本周选择的算法题是：Valid Parentheses

规则如下：

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solution

我实现的方案：

Runtime：24 ms，快过 89.65%。

Memory：12.6 MB，低于100%。

class Solution:
    def isValid(self, s: str) -> bool:
        mapping = {'(':')', '[':']', '{':'}'}
        stack = []
        for char in s:
            closing = mapping.get(char)
            if closing:
                stack.append(closing)
            elif not (stack and stack.pop() == char):
                return False
        
        return not stack

Review

用 MERLin 实现 iOS 下的事件驱动

架构类的文章不少了，有些观点还是可以看一看

Tip

这周完善了 Monorepo 的工具链：

  • 开发了一个 CocoaPods 插件，将 Pod 数据源进行了扩展，以便可以识别同仓库下的组件

Share

部署升级策略

服务部署的模式一般有：

  • 停机部署 - 把现有的服务停机，然后部署成新的版本
  • 蓝绿部署 - 部署好新版本后，把流量从老服务那边切过来
  • 滚动部署 - 一点一点地升级现有的服务
  • 灰度部署 - 把一部分用户切到新版本上来，然后看一下有没有问题，如果没有就扩大升级
  • A/B 测试 - 同时上线两个版本，然后做相关的比较

对于灰度发布或者 A/B 测试可以使用下面的方案来选择用户：

  • 浏览器 Cookie
  • 查询参数
  • 地理位置
  • 技术支持，如浏览器版本、屏幕尺寸、操作系统等
  • 客户端语言

缓存

数据库的读操作是最容易出现性能问题的地方，一方面，select 会有很多像 join、group、order、like 这类丰富的语义，另一方面大多数应用都是读多写少，加剧了慢查询的问题。

常见的缓存更新模式：

  • Cache Aside
    • 失效 - 先取 Cache，Cache 没有再从数据库中取，取完后放入 Cache
    • 命中 - 从 Cache 中取数据并返回
    • 更新 - 先更新数据库，再让缓存失效
  • Read/Write Through
    • Read Through - 由 Cache 代理数据库
    • Write Through - 由 Cache 代理数据库（同步更新）
  • Write Behind Cache
    • 更新 - 直接更新内容，不立即落盘（异步）

缓存设计的重点：

  • 需要一个第三方的缓存集群，让服务没有状态
  • 缓存要支持数据分片，这样才可以不断地 scale 下去
  • 缓存的好坏要看命中率，一般到 80% 以上就算很高了
  • 确定缓存是否适合业务，能接受数据更新的延迟？
  • 缓存数据的时间周期需要好好设计
  • 对于 LRU 的缓存系统来说，更新 LRU 需要加锁，这会导致更慢的缓存存取时间
  • 小心爬虫，需要一个保护机制或者引导这些人使用提供的外部 API

异步处理

异步通讯设计模式的好处：

  • 提高系统的稳定性

  • 提高容错能力

  • 系统可以统一高度

异步处理的设计：

  • 推模型 Push
  • 拉模型 Pull

异步处理+事件溯源的方式可以很好地让我们的整个系统进行任务的统筹安排、批量处理，可以让整体处理过程达到性能和资源的最大化利用。

异步处理的分布式事务设计要点：

  • 凭证需要非常好地保存起来，不然会导致事务做不下去
  • 凭证处理的幂等性问题，不然在重试时就会出现多次交易的情况
  • 如果事务完成不了，需要做补偿事务处理

异步处理的设计要点：

  • 需要有状态回传告诉发起方
  • 需要对账
  • 需要补偿
  • 考虑业务是否可以用异步的方式
  • 考虑扩容或者限流
  • 本质是对任务进行高度和统筹管理

数据库扩展

数据库扩展的方式：

  • 读写分离
  • 分库分表

读写分离也有两种方式：

  • 一写多读：
    • 比较容易实现
    • 可以很好的隔离业务
    • 可以很好地分担数据的读负载
    • 写库有单点故障的问题
    • 数据库同步不及时
  • CQRS（Command and Query Responsibility Segregation） - 命令与查询职责分离：
    • Query 做数据的整合，返回结果数据，但不会修改数据，没有副作用
    • Command 做业务逻辑，不会返回结果数据，只会返回执行状态
    • 分工明确，可以负责不同的部分
    • 逻辑清晰，能够看到系统中哪些行为或操作导致了状态变化
    • 可以从数据驱动转到任务驱动以及事件驱动

数据库里的数据越来越多也会影响我们的数据操作，数据库最好也可以拆分开。

分库分表：

  • 考虑分库的策略 - 比如按地理位置、或是日期、或是按某个范围分
  • 数据访问层 - 用来做数据路由

数据访问层不容易做好，可以采用一些分片策略来规避：

  • 按多租户的方式
  • 按数据的种类
  • 通过范围来分
  • 通过哈希算法来分

数据库扩展的设计重点：

  • 数据库与服务一同拆开，一个服务一个库
  • 做完服务化拆分后，再做数据分片：
    • 垂直分片 - 区分变化频率不一致的数据
    • 水平分片：
      • 考虑周期性地调整平衡性
      • 可以做一个索引表来快速索引数据位置
      • 支持从各个分片上提取数据
      • 考虑数据一致性以及评估是否采用两阶段提交的方式
      • 做好测试任务

秒杀

秒杀的流程：

  • 需要一个倒计时
  • 倒计时的时间到了则可以继续操作
  • 防止机器来抢

即：

  • 前端需要不停地轮询，以校准时间
  • 后端在合适的时机返回一个 URL 供前端使用
  • 抢到了库存则继续后面的流程

秒杀的技术挑战：

  • 需要扛住大量 TPS
  • 由于是单条的热点数据，无论怎么分库分表、分布式数据库都无济于事

秒杀的解决方案：

  • 可以在 CND 上部署一个小服务，用于统计用户
  • 在秒杀快要开始前，后端下发一个概率值
  • CDN 通过概率值用户过滤
  • 后端仅为过滤后的用户服务

这种玩法有一定的适用性，但不适用于12306和双11这种业务。双11的业务需要尽可能地多卖商品，需要认认真真地用高并发架构来应对。