← Courses Catalogue

#设计一个键-值缓存来存储最近 web 服务查询的结果

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

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

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

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

#用例

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

#限制条件与假设

#提出假设

#计算用量

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

便利换算指南：

#第二步：概要设计

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

Imgur

#第三步：设计核心组件

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

#用例：用户发送了一次请求，命中了缓存

常用的查询可以由例如 Redis 或者 Memcached 之类的内存缓存提供支持，以减少数据读取延迟，并且避免反向索引服务以及文档服务的过载。从内存读取 1 MB 连续数据大约要花 250 微秒，而从 SSD 读取同样大小的数据要花费 4 倍的时间，从机械硬盘读取需要花费 80 倍以上的时间。1

由于缓存容量有限，我们将使用 LRU（近期最少使用算法）来控制缓存的过期。

#缓存的实现

缓存可以使用双向链表实现：新元素将会在头结点加入，过期的元素将会在尾节点被删除。我们使用哈希表以便能够快速查找每个链表节点。

向你的面试官告知你准备写多少代码。

实现查询 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):
        ...

实现缓存：

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

#何时更新缓存

缓存将会在以下几种情况更新：

解决这些问题的最直接的方法，就是为缓存记录设置一个它在被更新前能留在缓存中的最长时间，这个时间简称为存活时间（TTL）。

参考 「何时更新缓存」来了解其权衡取舍及替代方案。以上方法在缓存模式一章中详细地进行了描述。

#第四步：架构扩展

根据限制条件，找到并解决瓶颈。

Imgur

重要提示：不要从最初设计直接跳到最终设计中！

现在你要 1) 基准测试、负载测试。2) 分析、描述性能瓶颈。3) 在解决瓶颈问题的同时，评估替代方案、权衡利弊。4) 重复以上步骤。请阅读「设计一个系统，并将其扩大到为数以百万计的 AWS 用户服务」 来了解如何逐步扩大初始设计。

讨论初始设计可能遇到的瓶颈及相关解决方案是很重要的。例如加上一个配置多台 Web 服务器的负载均衡器是否能够解决问题？CDN呢？主从复制呢？它们各自的替代方案和需要权衡的利弊又有什么呢？

我们将会介绍一些组件来完成设计，并解决架构扩张问题。内置的负载均衡器将不做讨论以节省篇幅。

为了避免重复讨论，请参考系统设计主题索引相关部分来了解其要点、方案的权衡取舍以及可选的替代方案。

#将内存缓存扩大到多台机器

为了解决庞大的请求负载以及巨大的内存需求，我们将要对架构进行水平拓展。如何在我们的内存缓存集群中存储数据呢？我们有以下三个主要可选方案：

#其它要点

是否深入这些额外的主题，取决于你的问题范围和剩下的时间。

#SQL 缩放模式

#NoSQL

#缓存

#异步与微服务

#通信

#安全性

请参阅「安全」一章。

#延迟数值

请参阅「每个程序员都应该知道的延迟数」。

#持续探讨