logo
System Design Case Studies

设计 Key-Value 存储

Key-Value 存储 System Design

注意：这个文档中的链接会直接指向System Design 主题索引中的有关部分，以避免重复的内容。你可以参考链接的相关内容，来了解其总的要点、方案的权衡取舍以及可选的替代方案。

第一步：简述用例与约束条件

搜集需求与问题的范围。 提出问题来明确用例与约束条件。 讨论假设。

我们将在没有面试官明确说明问题的情况下，自己定义一些用例以及限制条件。

用例

我们将把问题限定在仅处理以下用例的范围中

  • 用户发送一个搜索请求，命中 cache
  • 用户发送一个搜索请求，未命中 cache
  • 服务有着高 availability

限制条件与假设

提出假设

  • 网络流量不是均匀分布的
    • 经常被查询的内容应该一直存于 cache 中
    • 需要确定 cache 过期、cache 刷新规则
  • cache 查询速度要快
  • 机器间 latency 较低
  • cache 有内存限制
    • 需要决定 cache 什么、移除什么
    • 需要 cache 百万级 queries
  • 1000 万用户
  • 每月 100 亿次查询

计算用量

如果你需要进行粗略的用量计算，请向你的面试官说明。

  • cache 存储键值对有序表，键是 query，值是 results
    • query - 50 bytes
    • title - 20 bytes
    • snippet - 200 bytes
    • 总计 270 bytes
  • 假设 100 亿次查询都不同且全部存储，则每月需要 2.7 TB cache 空间
  • 每秒 4,000 次请求

便利换算指南：

  • 每月约 250 万秒
  • 每秒 1 个请求 = 每月 250 万次请求
  • 每秒 40 个请求 = 每月 1 亿次请求
  • 每秒 400 个请求 = 每月 10 亿次请求

第二步：概要设计

列出所有重要组件以规划概要设计。

Imgur

第三步：设计核心组件

深入每个核心组件的细节。

用例：用户发送请求，命中 cache

常用查询可由 内存 cache（如 Redis / Memcached）提供，降低读取 latency，并避免 反向索引服务 与 文档服务 过载。从内存读取 1 MB 连续数据约 250 微秒，而从 SSD 读取需 4 倍、机械硬盘需 80 倍以上。<a href=https://github.com/donnemartin/system-design-primer/blob/master/README-zh-Hans.md#每个程序员都应该知道的latency数>1

由于 cache 容量有限，使用 LRU 控制过期。

  • 客户端向运行 reverse proxy 的 Web 服务器发送请求
  • Web 服务器转发给 查询 API 服务
  • 查询 API 处理：
    • 解析 query：清理文本、分词、拼写修正、大小写归一、布尔化
    • 查 内存 cache：
      • 命中：移动到 LRU 头部并返回结果
      • 未命中：
        • 调用 反向索引服务 搜索并排名
        • 调用 文档服务 返回标题/片段
        • 写入 cache 并移动到 LRU 头部

cache 的实现

用双向链表 + 哈希表：链表维护 LRU 顺序，哈希表 O(1) 定位节点。

向面试官说明你准备写多少代码。

实现 查询 API 服务：

class QueryApi(object):

    def __init__(self, memory_cache, reverse_index_service):
        self.memory_cache = memory_cache
        self.reverse_index_service = reverse_index_service

    def parse_query(self, query):
        """移除多余内容，将文本分割成词组，修复拼写错误，
        规范化字母大小写，转换布尔运算。
        """
        ...

    def process_query(self, query):
        query = self.parse_query(query)
        results = self.memory_cache.get(query)
        if results is None:
            results = self.reverse_index_service.process_search(query)
            self.memory_cache.set(query, results)
        return results

实现 节点：

class Node(object):

    def __init__(self, query, results):
        self.query = query
        self.results = results

实现 链表：

class LinkedList(object):

    def __init__(self):
        self.head = None
        self.tail = None

    def move_to_front(self, node):
        ...

    def append_to_front(self, node):
        ...

    def remove_from_tail(self):
        ...

实现 cache：

class Cache(object):

    def __init__(self, MAX_SIZE):
        self.MAX_SIZE = MAX_SIZE
        self.size = 0
        self.lookup = {}  # key: query, value: node
        self.linked_list = LinkedList()

    def get(self, query)
        """从缓存取得存储的内容

        将入口节点位置更新为 LRU 链表的头部。
        """
        node = self.lookup[query]
        if node is None:
            return None
        self.linked_list.move_to_front(node)
        return node.results

    def set(self, results, query):
        """将所给查询键的结果存在缓存中。

        当更新缓存记录的时候，将它的位置指向 LRU 链表的头部。
        如果这个记录是新的记录，并且缓存空间已满，应该在加入新记录前
        删除最老的记录。
        """
        node = self.lookup[query]
        if node is not None:
            # 键存在于缓存中，更新它对应的值
            node.results = results
            self.linked_list.move_to_front(node)
        else:
            # 键不存在于缓存中
            if self.size == self.MAX_SIZE:
                # 在链表中查找并删除最老的记录
                self.lookup.pop(self.linked_list.tail.query, None)
                self.linked_list.remove_from_tail()
            else:
                self.size += 1
            # 添加新的键值对
            new_node = Node(query, results)
            self.linked_list.append_to_front(new_node)
            self.lookup[query] = new_node

相关练习题

设计 Key-Value 存储

暂无相关练习题