我被技术问题所吸引。突然间，一个朋友问我，
如果你要构建一个内存缓存，你会怎么做？
它应该有良好的性能并能存储大量条目。读取操作比写入操作更频繁。我已经知道我应该怎么做，但我想听听你的方案。
我无法不接受这个挑战。
在回答这个问题和编写代码的过程中，我发现自己的思维方式发生了许多变化，这是经验带来的结果。这些变化使得软件工程变得更加容易，也是在我经验不足时从未考虑过的。
我开始写一篇长篇大论的文章，但觉得它没有完全达到预期的效果，因此这是个简化的版本。如果时间允许，我可能会在单独的文章中更详细、更简洁地探讨其中一些实践。
实践
以下是我在构建快速、简单内存缓存过程中采用的八种方法。
1. 使用现成解决方案
我们对这个问题的第一反应应当是“我们可以使用 Redis 吗？”
只要组件不是非常昂贵或复杂，或者说不是创造核心价值的部分，我们应该倾向于选择现成的方案。之前我已撰文论述过为何要建设昂贵复杂的架构（https://entropicthoughts.com/build-vs-buy.html）。
2. 成本和可靠性超过功能
如果我们发现不能使用现成的方案，我们就需要开发一种便宜且可靠的方案。通常这意味着不需要具备所有附加功能，不过这也是一个值得权衡的选择。我最喜欢的一句话是，
对于可靠型软件而言，添加新特性容易得多；相比而言，在复杂的功能型软件里增加可靠性却困难得多。
此外，人们很容易错误地认为自己需要那些实际并不存在的需求。
我并不是特别支持设计阶段。有时候确实需要，但是如果需要预先设计软件架构的话，这会增加开发成本，并拖延完成时间。另一方面，有时一点点提前分析可以帮助我们在编写任何代码之前排除掉大部分的设计方案。
在处理这个缓存时，我们可以询问有关条目持久性要求、请求率、大小、逐出条件等问题。通过这种分析，我们会发现可以只需一个线程来访问一个单一的数据结构，并且不需要主动进行逐出处理 — 这是一个巨大的胜利！简化了设计。
3. 快速实现想法至生产
上一实践的一部分原因在于轻易认为所需的功能其实并不必要。那么，如何判断哪些功能才是真正需要的呢？一般来说，最廉价且最为可靠的方法是在生产环境中验证出来。
如果我们部署最少必要的特性集，我们可以迅速了解哪些额外的特性需求最高，并且这往往是与我们预想的不同。即使相同，也会发现它们通常具有其他事先未曾考虑到的要求。
这一做法与前面所述强烈相关：使用分析来减少到最小要求，再编写最小代码以满足这些条件，并尽快将其投入生产环境以更好地了解我们试图解决的问题。
4. 简单数据结构
尽管复杂数据结构往往颇具吸引力。尤其是在存在第三方库时可以帮助我们处理这一切。然而，复杂数据结构的问题是由于了解欠缺而容易滥用，导致性能瓶颈和错误。
就该具体缓存而言，需要存储的条目数量（我们可以通过排队论从ttl和写入速率推算出这个数值）仅需19.9位信息便已足够 — 换句话说，我们可以直接利用数组来存储各项，并对键值（key）进行哈希映射以获得地址。1 我们早已确认无需逐出过期项。如果真的需要处理，那么可以使用最小堆来维护快要过期项目列表以节省成本且简化任务。这比全排序方式更为高效简便。除了独立的过程之外，我们还可以依赖高请求频率触发删除操作，从而以少许延迟换取避免并发设计工作。另一个变体是提供单独API接口以触发过期条目逐出功能，赋予调用方决定要花费多少时间在这上面的灵活性。这样一来，调用方可灵活调节该时间以进行动态延迟性能折中。
5. 早期预留资源
在为我设计的缓存做出的另一个可能引起争议的决策是其在一开始就分配完整索引数组。这看起来很浪费，但从初步计算可知，连续操作期间其实需要大多数这个空间，因而推迟分配并不会节省什么资源。
早期分配的好处是在系统启动时即可确定是否具备所需资源，这样如果资源不足可以立即崩溃，而不会等到夜里工程师睡觉时才收到 PagerDuty 的报警电话。这对于容量规划和性能预测也更加有利。
新来的读者注意啦，生产环境下易于运行是我非常看重的一件事，我会尽可能经常发表关于这个话题的文章。您应该订阅我的电子邮件列表以获取每周更新的文章摘要：https://buttondown.email/entropicthoughts
如果您不喜欢可以随时退订。
6. 设定上限
对于解决哈希冲突时定位对象所采用的基于线性探测开放寻址法，我选择了粗糙的方式，虽然这种方法简单并且通常情况下性能很好（同样只需要基本算术即可得出特定应用场景下的结论），但是在最坏情形下表现却很差：每遇到一次缓存未命中就可能遍历整个数组。
鉴于完美召回并非必须2 这再一次表明询问需求的重要性！设置一个最大迭代限制，例如500步，以确保最坏情况离平均情况相差不远，为此需要牺牲一些缓存命中情况。500步是否最优？不是。我不知道如何在事先计算这个问题，所以生产经验将指导未来对步数上限的调整。
最关键的是要有 某个 上限，而不是完全没有，这样我们才不会因为一些意外的长时间处理过程。
鉴于静态分配需求，我们还应设定缓存可以容纳数据量上限，以防夜半三更因意外超出内存限额而苦恼。总的来说，限制所有可以量度的事务！如果有人对限制不满，则修订限制—不要取消它。
7. 使测试变得容易
为了避免回归问题并确保期望行为，我让缓存程序可以从标准输入接收命令。这意味着我们可以在终端窗口中启动缓存并键入 write hello world 来将字符串 "world" 保存至键 "hello" 下。
这也意味着我们可以将一系列命令放入文件中，然后通过管道将其送到缓存程序。如果同时给缓存添加一条命令，用来确保上次读取的值是否特定3，那么我们就可以在纯文本文件中编写一整套测试脚本，然后将其传递给该程序以验证其功能。输入文件可能如下所示：
# 缓存为空，查找应无效。
read abc
assert undef
# 写入随后立即读回相同内容。
write abc 123
read abc
assert 123
# 不同键应无响应。
read xyz
assert undef
# 写入不同值后再次读取应匹配。
write abc 567
read abc
assert 567
# 写入新键，abc仍应在位置不变。
write xyz 444
read abc
assert 567
单个步骤均相对简单（接受命令行输入、允许断言读取内容）但是其结合现有工具（shell 输入重定向）后可以显著加快迭代周期，从而造就更为可靠的软件。
8. 集成性能计数器
最后，我们需要了解程序的时间分配情况。这可以通过剖析工具或日志中推断得出，但最简便的做法是嵌入性能计数器。计数器可以统计各种事项，比如
- 花费多少时间读取键？
- 花费多少时间写入键值对？
- 花费多少时间在 I/O 处理上？
- 发生了多少次缓存未命中？
- 需要线性搜索多少个键？
- 达到500步最大迭代次数的次数有多少次？
注意，所有这些都是累积的，所以我们不问“当前分配了多少存储空间？”，而是问以下两个问题
- 从启动到现在，我们总共分配了多少存储空间？
- 从启动到现在，我们总共释放了多少存储空间？
通过将测量结果分解为两个随时间变化的总数，我们可以更多地了解系统的行为。
这些数字随时间的变化也是一个有用的指标。例如，“我们必须线性搜索多少个键？”的值可能会稳步增加（表明哈希冲突分布相对均匀）或者有时会大幅上升（表明突然出现大量冲突）。能够区分这些情况是非常有用的。结合“迭代限制被达到的次数”来看，这可以告诉我们系统所承受的压力很大。
其他实践
肯定还有许多其他从多年软件工程实践中获得的洞察，但这些都是我在本次练习中想到的。我很乐意听听你所想到的其他见解！无论如何，我希望这能教会我成为一名更好的软件工程师。