设计一个 kv 内存缓存系统，保存最近 web 的查询

1. 准备和计算

面试官一般会提供一些假设和约束，比如用户量，数据量等，我们需要粗略做个计算。

假设这题有以下假设和约束：

  • 用户数 1000w
  • 每月查询量 100 亿
  • 内存有限
  • 要求低延时
  • 服务高可用

我们可以做出如下粗略盘点：

  • 假设每个查询 50 个 bytes，根据查询解析出的 key 算它 20 bytes，value 是一个快照 snippet 算它 200 bytes，那么一次查询共 270 bytes.

  • 每条查询 270 byte ，每月 100 亿查询，如果每次查询都是唯一的话，需要存储 2.7T 数据。

  • 每月 100 亿查询，每月 250万 秒，平均每秒 4000 次

1
2
3
4
5
1G ≈ 1000M ≈ 1000000K(100万k) ≈ 1000000000b(10亿byte)

1T ≈ 10000亿byte

30 天 = 24 * 30 h = 24 * 30 * 3600 s ≈ 250万 s

2. 抽象设计

各个组件

3. 核心组件设计

常见的缓存查询做法，通常使用 redis 或者 memcached 来降低延时。
从内存顺序读取1 MB 大约需要 250 微秒，从 SSD 读取数据需要 4 倍时间，而从磁盘读取需要 80 倍时间

因为内存有限，这里使用 LRU 缓存，过滤到常使用的缓存。

  1. client 端发送一个请求到 web server，通常是一个反向代理服务。

  2. web server 将请求转发到 query api server。

  3. query api server 执行以下操作

  • 解析请求
  • 检查内存里是否有内容匹配此查询
    • 如果有
      • 更新缓存到 LRU 头部
      • 返回该值
    • 如果没有
      • 使用反向索引服务，查询匹配查询的文档
        • 反向索引服务会对查询结果排序，并返回最前面的结果
      • 使用文档服务返回查询标题和快照内容
      • 更新内存，并将内容放到 LRU 头部

缓存实现：使用一个双向链表，新的内容会添加到头部，老的会被移除，同时使用一个 hash table 来快速查找内容。

具体代码可以参考之前面试对象设计之设计一个LruCache.

4. 扩展服务设计

服务扩展性有很多放面可以做，选取一个基线，做假设，再讨论。

以下一些 topic 几乎每个系统设计都会提到，这里不做扩展，可以自行研究。

  • DNS (域名解析)
  • Load Balancer (负载均衡)
  • Horizontal scaling (水平扩展)
  • Web Server (反向代理)
  • Api Server (应该服务)
  • cache (缓存)
  • Consistency patterns (一致性原则)
  • Availability patterns (可用性原则)

为了应对大量请求负载，以及大量的内存，需要水平扩展机器，有三种主要的方法。

  • 每台机器在集群里保存各自的缓存。（简单，但查找会延时）
  • 每台机器在集群里都保存同一份缓存副本。 （简单，但浪费机器内存）
  • 缓存分片，集群里每台机器保存一定hash范围内的缓存。（复杂，理论上最好）

5. 进一步讨论

取决于问题领域和剩余时间。

SQL (读写分离，分库分表，分片，sql 调优)

NoSql (kv 存储，document 存储，宽表存储，图形数据库)

缓存 (client，cdn，web server，database)

消息队列，微服务，服务发现

其他方面的权衡取舍

6. 其他

持续对系统进行基准测试和监控，发现瓶颈，并解决它，服务扩展时一个持续的过程。