键值存储是一种NoSQL数据库，它使用简单的键值方法来存储数据。数据库中的每个项目都以属性名称（或“键”）及其值一起存储。本页面重点介绍如何设计和实现一个分布式键值存储，专门用于缓存搜索引擎查询结果。
有关一般NoSQL数据库概念，请参阅数据库。有关键值存储之外的缓存策略，请参阅缓存。
搜索引擎的键值存储缓存查询结果，以改善响应时间并减少后端服务的负载。热门的搜索可以直接从缓存中提供，而不是从头开始处理每个搜索查询。
图：带键值缓存的搜索引擎查询流程
来源：solutions/system_design/query_cache/README.md61-69 solutions/system_design/query_cache/README.md81-91
对于搜索引擎查询缓存，我们需要考虑：
来源：solutions/system_design/query_cache/README.md24-33
键值存储实现了最近最少使用（LRU）缓存，以有效地管理有限的内存资源。当达到内存限制时，此淘汰策略可确保从缓存中移除很少访问的查询。
图：LRU缓存实现组件
来源：solutions/system_design/query_cache/query_cache_snippets.py25-90 solutions/system_design/query_cache/README.md92-152
LRU缓存实现的关键组件有：
该缓存使用哈希表进行O(1)查找，并使用双向链表管理LRU淘汰策略。当缓存达到容量时，最近最少使用的项目（位于链表尾部）将被移除。
QueryApi类处理查询并与缓存交互。
图：查询处理流程
来源：solutions/system_design/query_cache/query_cache_snippets.py4-22 solutions/system_design/query_cache/README.md67-91
缓存实现了两个主要操作：
Cache.get(query):
1. Look up the query in the hash table
2. If found, move the node to the front of the linked list (mark as recently used)
3. Return the associated results or None if not found
Cache.set(query, results):
1. If the query exists in the cache, update its results and move to front of list
2. If the query is new:
a. If cache is at capacity, remove the least recently used item (from tail)
b. Create a new node with the query and results
c. Add the node to the front of the linked list
d. Add the query-node mapping to the hash table
来源：solutions/system_design/query_cache/query_cache_snippets.py56-90 solutions/system_design/query_cache/README.md152-196
当底层数据发生变化时，缓存需要刷新。常见的更新策略包括：
| 策略 | 描述 | 优点 | 缺点 |
|---|---|---|---|
| 生存时间（TTL） | 缓存条目在设定时间后过期 | 易于实现 | 可能在过期前返回陈旧数据 |
| 旁路缓存（Cache-aside） | 当数据更改时，应用程序更新缓存 | 应用程序控制新鲜度 | 应用程序逻辑更复杂 |
| 直写式缓存（Write-through） | 数据库更新时缓存也更新 | 保证数据一致性 | 写操作较慢 |
| 回写式缓存（Write-behind） | 更新排队并异步处理 | 更好的写入性能 | 临时数据不一致 |
来源：solutions/system_design/query_cache/README.md199-209
对于处理数百万查询的分布式搜索引擎，单机缓存是不足的。键值存储必须分布在多台机器上。
图：分布式键值存储架构
来源：solutions/system_design/query_cache/README.md215-242
有三种主要方法可以跨多台机器扩展键值缓存：
对于分片缓存，常用方法是使用一致性哈希来确定哪台机器存储特定键
machine = hash(query) % num_machines
这种方法将缓存条目均匀地分布到所有可用机器上，同时在添加或移除机器时最大限度地减少重新分配。
来源：solutions/system_design/query_cache/README.md237-242
任何键值存储的核心都是哈希表实现。一个简单的哈希表可以实现如下：
图：哈希表实现
来源：solutions/object_oriented_design/hash_table/hash_map.py1-38
哈希表使用链式寻址来解决冲突——当多个键哈希到同一索引时，它们被存储在该索引处的链表中。此实现提供：
在实现搜索引擎的键值存储时，会涉及几个相关的系统设计概念：