原文：http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html

缓存是提升性能的通用方法，现在大多数的缓存实现都使用了经典的技术。这篇文章中，我们会发掘 Caffeine 中的现代的实现方法。Caffeine 是一个开源的 Java 缓存库，它能提供高命中率和出色的并发能力。期望读者们能被这些想法激发，进而将它们应用到任何你喜欢的编程语言中。

驱逐策略

缓存的驱逐策略是为了预测哪些数据在短期内最可能被再次用到，从而提升缓存的命中率。由于简洁的实现、高效的运行时表现以及在常规的使用场景下有不错的命中率，LRU（Least Recently Used）策略或许是最流行的驱逐策略。但 LRU 通过历史数据来预测未来是局限的，它会认为最后到来的数据是最可能被再次访问的，从而给与它最高的优先级。

现代缓存扩展了对历史数据的使用，结合就近程度（recency）和访问频次（frequency）来更好的预测数据。其中一种保留历史信息的方式是使用 popularity sketch（一种压缩、概率性的数据结构）来从一大堆访问事件中定位频繁的访问者。可以参考 CountMin Sketch 算法，它由计数矩阵和多个哈希方法实现。发生一次读取时，矩阵中每行对应的计数器增加计数，估算频率时，取数据对应是所有行中计数的最小值。这个方法让我们从空间、效率、以及适配矩阵的长宽引起的哈希碰撞的错误率上做权衡。

Window TinyLFU（W-TinyLFU）算法将 sketch 作为过滤器，当新来的数据比要驱逐的数据高频时，这个数据才会被缓存接纳。这个许可窗口给予每个数据项积累热度的机会，而不是立即过滤掉。这避免了持续的未命中，特别是在突然流量暴涨的的场景中，一些短暂的重复流量就不会被长期保留。为了刷新历史数据，一个时间衰减进程被周期性或增量的执行，给所有计数器减半。

对于长期保留的数据，W-TinyLFU 使用了分段 LRU（Segmented LRU，缩写 SLRU）策略。起初，一个数据项存储被存储在试用段（probationary segment）中，在后续被访问到时，它会被提升到保护段（protected segment）中（保护段占总容量的 80%）。保护段满后，有的数据会被淘汰回试用段，这也可能级联的触发试用段的淘汰。这套机制确保了访问间隔小的热数据被保存下来，而被重复访问少的冷数据则被回收。

如图中数据库和搜索场景的结果展示，通过考虑就近程度和频率能大大提升 LRU 的表现。一些高级的策略，像 ARC，LIRS 和 W-TinyLFU 都提供了接近最理想的命中率。想看更多的场景测试，请查看相应的论文，也可以在使用 simulator 来测试自己的场景。

过期策略

过期的实现里，往往每个数据项拥有不同的过期时间。因为容量的限制，过期后数据需要被懒淘汰，否则这些已过期的脏数据会污染到整个缓存。一般缓存中会启用专有的清扫线程周期性的遍历清理缓存。这个策略相比在每次读写操作时按照过期时间排序的优先队列来清理过期缓存要好，因为后台线程隐藏了的过期数据清除的时间开销。

鉴于大多数场景里不同数据项使用的都是固定的过期时长，Caffien 采用了统一过期时间的方式。这个限制让用 O（1）的有序队列组织数据成为可能。针对数据的写后过期，维护了一个写入顺序队列，针对读后过期，维护了一个读取顺序队列。缓存能复用驱逐策略下的队列以及下面将要介绍的并发机制，让过期的数据项在缓存的维护阶段被抛弃掉。

并发

由于在大多数的缓存策略中，数据的读取都会伴随对缓存状态的写操作，并发的缓存读取被视为一个难点问题。传统的解决方式是用同步锁。这可以通过将缓存的数据划成多个分区来进行锁拆分优化。不幸的是热点数据所持有的锁会比其他数据更常的被占有，在这种场景下锁拆分的性能提升也就没那么好了。当单个锁的竞争成为瓶颈后，接下来的经典的优化方式是只更新单个数据的元数据信息，以及使用随机采样、基于 FIFO 的驱逐策略来减少数据操作。这些策略会带来高性能的读和低性能的写，同时在选择驱逐对象时也比较困难。

另一种可行方案来自于数据库理论，通过提交日志的方式来扩展写的性能。写入操作先记入日志中，随后异步的批量执行，而不是立即写入到数据结构中。这种思想可以应用到缓存中，执行哈希表的操作，将操作记录到缓冲区，然后在合适的时机执行缓冲区中的内容。这个策略依然需要同步锁或者 tryLock，不同的是把对锁的竞争转移到对缓冲区的追加写上。

在 Caffeine 中，有一组缓冲区被用来记录读写。一次访问首先会被因线程而异的哈希到 stripped ring buffer 上，当检测到竞争时，缓冲区会自动扩容。一个 ring buffer 容量满载后，会触发异步的执行操作，而后续的对该 ring buffer 的写入会被丢弃，直到这个 ring buffer 可被使用。虽然因为 ring buffer 容量满而无法被记录该访问，但缓存值依然会返回给调用方。这种策略信息的丢失不会带来大的影响，因为 W-TinyLFU 能识别出我们希望保存的热点数据。通过使用因线程而异的哈希算法替代在数据项的键上做哈希，缓存避免了瞬时的热点 key 的竞争问题。

写数据时，采用更传统的并发队列，每次变更会引起一次立即的执行。虽然数据的损失是不可接受的，但我们仍然有很多方法可以来优化写缓冲区。所有类型的缓冲区都被多个的线程写入，但却通过单个线程来执行。这种多生产者/单个消费者的模式允许了更简单、高效的算法来实现。

缓冲区和细粒度的写带来了单个数据项的操作乱序的竞态条件。插入、读取、更新、删除都可能被各种顺序的重放，如果这个策略控制的不合适，则可能引起悬垂索引。解决方案是通过状态机来定义单个数据项的生命周期。

在基准测试中，缓冲区随着哈希表的增长而增长，它的的使用相对更节省资源。读的性能随着 CPU 的核数线性增长，是哈希表吞吐量的 33%。写入有 10%的性能损耗，这是因为更新哈希表时的竞争是最主要的开销。

结论

还有许多实用的话题没有被覆盖到。包括最小化内存的技巧，当复杂度上升时保证质量的测试技术以及确定优化是否值得的性能分析方法。这些都是缓存的实践者需要关注的点，因为一旦这些被忽视，就很难重拾掌控缓存带来的复杂度的信心。

Caffeine 的设计实现来自于大量的洞见和许多贡献者的共同努力。它这些年的演化离不开一些人的帮助：Charles Fry, Adam Zell, Gil Einziger, Roy Friedman, Kevin Bourrillion, Bob Lee, Doug Lea, Josh Bloch, Bob Lane, Nitsan Wakart, Thomas Müeller, Dominic Tootell, Louis Wasserman, and Vladimir Blagojevic. Thanks to Nitsan Wakart, Adam Zell, Roy Friedman, and Will Chu for their feedback on drafts of this article.

 原文地址：http://biaobiaoqi.github.io/blog/2017/03/19/design-of-a-modern-cache/
 版权声明：自由转载-非商用-非衍生-保持署名| Creative Commons BY-NC-ND 3.0

背景

邮件服务系列博文中，前两篇介绍了邮件系统的基本功能和安全体系，本文记录了搭建邮箱服务器的实践。

Sendmail 是一种多用途、支援多种协定的跨网络电子邮件传送代理软件，于 1983 年随着 BSD 4.1c 首次发行，2001 年时的调查，互联网上的邮件服务器有 42%使用 Sendmail，但之后由于多次被发现重大的安全性漏洞，且其设定档过于复杂造成较高的学习门槛等因素，导致市占率下滑。

Postfix 被 Wietse Zweitze Venema 创造出来以取代 Sendmail。本次实践即使用 Postfix 为域名 biaobiaoqi.me 搭建邮箱服务器，服务器是 Linode 上的 VPS，Ubuntu 12.04LTS，DNS 服务器使用 DNSPod。

背景

邮件服务系列博文中第一篇博客介绍了邮件服务的基本知识，了解了邮件是如何从发件人的邮件客户端经过不同的传输协议传送到收件人的邮件客户端的。这只是邮件的基本功能实现，但如果发生如下情况，整个邮件系统的生态环境将被扰乱：

• 被不法分子利用邮箱服务器发送垃圾邮件
• 被其他人伪造域名邮箱发送邮件
• 被中间人窃取账号密码、甚至重要邮件信息（中间人攻击）
• 即使自己拥有邮箱服务器的权限，无限制的滥用这个权利给其他邮箱发送邮件也是不好的

为了防止以上的种种情况，电子邮箱体系引入了更多的协议和机制。本文对此做浅显的总结，如有出错，还请指出和补充。

背景

电子邮件出现在 1960s 晚期，比打开浏览器就要使用的 HTTP 协议早了 20 年左右,是二十世纪人类最伟大的发明之一。这个古老、经典的框架在网络中运行了五十多年，现今仍然是网络中主要的流量类型之一。

不得不提的是，wiki 上关于中国的第一封电子邮件的记载：1987 年 9 月 14 日 [1]中国第一封电子邮件是由“德国互联网之父”维纳·措恩与王运丰在北京的计算机应用技术研究所发往德国卡尔斯鲁厄大学的，其内容为英文，大意如下：

Across the Great Wall we can reach every corner in the world.

真的是很有远见呢-,-

前几天梳理了电子邮箱相关的协议和框架组件，准备整理成文。一共三篇，本文是基本知识总结，第二篇介绍安全认证和防垃圾邮件的规范，第三篇记录了邮件服务器的搭建实践。

本文主要参考自《深入理解 Java 虚拟机》。这本书是国人写的难得的不是照搬代码注释的且不是废话连篇的技术书，内容涵盖了 Java 从源码到字节码到执行的整个过程，包括了 JVM（Java Virtual Machine）的架构，垃圾收集的介绍等。这里摘录出关于配置 JVM 基本参数来调优 Eclipse 启动的过程，比较初级，供初学者参考。

ZJU 的校网论坛 CC98 比较活跃。论坛只对校内网开放，而且账号跟学生绑定，每个学生注册的账号数量有限。『十大』是 CC98 的经典页面：基于关注的人数（回帖的用户数而不是回帖的数量）用算法求出 24 小时内最火爆的十个发帖。很多同学都会浏览十大，关注论坛动态。

故事就是从十大引出的。有的社团在宣传活动时，为了扩大宣传面，会发动成员的小马甲顶贴上十大。这种违背社区自然发展轨迹的手段，强奸了关注十大贴的用户的意愿，阻碍了信息的自由流动。

于是萌生了完成一个批量发帖的机器，以其人之道还治其人之身的想法。在下次十大被宣传贴攻占时，能有反击的工具。

工具的用途很简单：使用不同的用户身份模拟真人论坛回帖，增加帖子关注度，以抵抗宣传贴。流程如下：提前收集各路亲朋好友的用户信息作为『预备水军』，『灌水』时，在评论内容文件中输入自定义的评论内容，在命令行参数中制定目标贴，即可实现随机顺序的用户自动顶贴。鉴于现在的功能是顶贴竞争十大，而十大排名是根据关注人数也就是独立用户评论数量做排序的，这里设计的顶贴策略是一个马甲发一条评论。以后可以考虑增加灵活的配置方案，实现更多功能。

项目 Github 地址：https://github.com/biaobiaoqi/CC98PostMachine/

介于这个工具本身的罪恶的攻击属性，在此强调，工程仅供学习交流和对抗宣传贴。

Web 服务开发的心灵鸡汤

周末去上海陪妹子的两天在路途上看完了这本《大规模 Web 服务开发技术》。

《大规模 Web 服务开发技术》是日本的 Hetena 团队以夏天举办的实习活动的课程讲义为基础整理的开发、运营大规模服务的入门书。书中更多的偏重了 Hetena 技术团队发展过程中的实践经验总结，将一个系统从无到有的发展过程有条理的展现了出来。读完全书，觉得它更像是一本 Web 服务开发的心灵鸡汤，有许多靠谱的总结，但相对零散，刚接触的人很难掌握。当然，心灵鸡汤并不是贬义，只是有不同的针对性。

《黑客：计算机革命的英雄》不是一本新书，创作于上世纪 80 年代。

这本书我断断续续花了几个月才看完。大量的传奇黑客人物穿插其中，说实话容量略大，到头来也没记住几个名字，不过这不是重点。全书将对整个计算机发展史有深刻影响的黑客文化分三个阶段的娓娓道来，让我重新审视对黑客的看法认识。下面是我对全书的笔记摘要。

不要在意那些细节

这是一本关于计算机世界的科普读物。豆瓣链接：请戳。

非常推荐刚接触计算机的朋友花上三五小时将全书通读一遍，没有技术细节，没有公式证明，它会告诉作者挑选出的九大算法出现的缘由和发展的过程。这些不关乎实现细节的思想概括，更能体现算法在整个领域中的存在的原因。它们不再是冷冰冰的算法过程，这是阅读大多数的书籍、教材所难以获得的。

至于我的推荐原因，如下全文。

今晚是阿里巴巴 2013 校园招聘的杭州站笔试。下午匆忙看了两张历年试卷，去现场打了瓶酱油。

题目总体考察点偏基础，倒数第二题（Java 附加题）比较有趣，考察了 Java 初始化机制的细节，在此摘录出来。

题目

求如下 java 代码的输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class T  implements Cloneable{
  public static int k = 0;
  public static T t1 = new T("t1");
  public static T t2 = new T("t2");
  public static int i = print("i");
  public static int n = 99;
  
  public int j = print("j");
  {
      print("构造快");
  }
  
  static {
      print("静态块");
  }
  
  public T(String str) {
      System.out.println((++k) + ":" + str + "    i=" + i + "  n=" + n);
      ++n; ++ i;
  }
  
  public static int print(String str){
      System.out.println((++k) +":" + str + "   i=" + i + "   n=" + n);
      ++n;
      return ++ i;
  }
  
  public static void main(String[] args){
      T t = new T("init");
  }
}