系统设计面试题精选

1 . 目 录 致谢 介绍 系统设计考察的是什么？ 分布式ID生成器 短网址的长度 短网址系统(TinyURL) 信息流(News Feed) 定时任务调度器 API限速 线程安全的HashMap 最近一个小时内访问频率最高的10个IP 负载均衡 Key-Value存储引擎 网络爬虫 PageRank 搜索引擎 大数据 数据流采样 基数估计 频率估计 Top K 频繁项 范围查询 成员查询 附录 跳表(Skip List) Raft 本文档使用 书栈(BookStack.CN) 构建 - 1 - 

2 .致谢 致谢 当前文档 《系统设计面试题精选》 由 进击的皇虫 使用 书栈(BookStack.CN) 进行构建， 生成于 2018-04-16。 书栈(BookStack.CN) 仅提供文档编写、整理、归类等功能，以及对文档内容的生成和导出工 具。 文档内容由网友们编写和整理，书栈(BookStack.CN) 难以确认文档内容知识点是否错漏。如 果您在阅读文档获取知识的时候，发现文档内容有不恰当的地方，请向我们反馈，让我们共同携手， 将知识准确、高效且有效地传递给每一个人。 同时，如果您在日常生活、工作和学习中遇到有价值有营养的知识文档，欢迎分享到 书栈 (BookStack.CN) ，为知识的传承献上您的一份力量！ 如果当前文档生成时间太久，请到 书栈(BookStack.CN) 获取最新的文档，以跟上知识更新换 代的步伐。 文档地址：http://www.bookstack.cn/books/system-design 书栈官网：http://www.bookstack.cn 书栈开源：https://github.com/TruthHun 分享，让知识传承更久远！ 感谢知识的创造者，感谢知识的分享者，也感谢每一位阅读到此处的 读者，因为我们都将成为知识的传承者。 本文档使用 书栈(BookStack.CN) 构建 - 2 - 

3 .介绍 介绍 系统设计面试题精选 在线阅读 系统设计面试题精选 在线阅读 Community License 来源(书栈小编注) 系统设计面试题精选 本书精选了一些经典的系统设计题，也是各大公司常考的，进行详细深入的讲解，帮助读者举一反 三，各个击破。 在线阅读 https://www.gitbook.com/book/soulmachine/system-design/ 系统设计面试题精选 本书精选了一些经典的系统设计题，也是各大公司常考的，进行详细深入的讲解，帮助读者举一反 三，各个击破。 在线阅读 https://www.gitbook.com/book/soulmachine/system-design/ Community Github: https://www.github.com/soulmachine/system-design 微博： @灵魂机器 小密圈： 本文档使用 书栈(BookStack.CN) 构建 - 3 - 

4 .介绍 License Book License: CC BY-SA 3.0 License 来源(书栈小编注) https://github.com/soulmachine/system-design 本文档使用 书栈(BookStack.CN) 构建 - 4 - 

5 .介绍 本文档使用 书栈(BookStack.CN) 构建 - 5 - 

6 .系统设计考察的是什么？ 系统设计考察的是什么？ 系统设计考察的是什么？ 设计容量 系统设计考察的是什么？ 系统设计这个面试环节，首先当然是考察候选人的对系统(System)底层的了解，然后考察的是候选 人的架构(Architect)能力，在各种工具和方案中组合出最合适的。最后，大部分系统设计题是开放 型的题目，这时候沟通(Communication)很重要，要多问面试官，理解题意，给出一个能自圆其说 的结论。 设计容量 搭建一个服务，跟建造一个房子一样，是有开发成本的。不同容量的系统，需要的人月数完全不一 样，成本差别巨大。拿到一个题目，首先要问面试者，希望抗住多少流量，多大的QPS或者多少在线 用户等。 这个题目我一直在考虑要不要写，因为有一天也许我们彼此会坐在一方小桌的两端，聊聊系统设计， 而我这么做有泄题兜底之嫌。不过，考虑到不是所有的读者都会来 TubiTV 这座小庙面试，而这个 方面的确是很多朋友的弱项，我就略说几句。 请听题：一个使用 rail（或者 django，或者 express，…）和 MySQL 做的 API 系统，最近流 量从 6,000 RPM 激增至 20,000 RPM，整个系统的压力骤升，现在需要在应用层设计一套缓存方 案来降低整个系统的负荷。要求是：缓存方案不能在 web 层（包括 proxy）做，也不能使用 framework 自带的，或者第三方的缓存模块。 大部分的面试者一看，这问题简单啊，使用 redis（或者 memcached），加在应用服务器和数据库 服务器之间，读取数据的时候如果没有命中缓存，则读取数据库并写入缓存，下次再读相同的数据时 就能命中缓存，大大减轻数据库的压力了。 这回答对么？不好说。也许对，也许不对。但你要这么快抢答的话基本上就会被面试官毙了。 系统设计的面试重在讨论和交流，厘清一切限制条件，然后在这些限制条件下面找到一个比较合理的 解决方案。它不是编程题或者算法题，弄清楚题目的要求就可以写开始答案的。 好的面试者应该主动发问，来尽量找全限制条件，而不是直接假设。拿上述回答来说，面试者还没开 始认真分析问题所在，就想当然认为压力在数据库一侧（是的，流量激增之后 90% 的可能性都是数 据库先扛不住压力，但这是假设，不能化作前提），从可能错误的前提出发，必然会得出一个很可能 错误的解决方案。 本文档使用 书栈(BookStack.CN) 构建 - 6 - 

7 .系统设计考察的是什么？ 所以比较对路的思考过程是： 现有系统的架构是什么样子？ 作为一个已有系统的优化项目，不了解现有系统的架构，历史（演变的过程和演变的原因，当然，在 面试中这个可以省去）而立刻上手设计都是在耍流氓。 web 服务器，应用服务器，数据库服务器等之间的关系以及数量？ 现在有没有使用类似于 redis / memcached 的缓存服务器？如果有，它们用来处理什么任务？ （如果有人问道这个，会有大大的加分） 目前哪个部分在系统中压力最大？ 这个问题非常重要，你得需要先知道问题在哪再考虑优化。如果问题出在应用服务器，那么，可能需 要做页面级的缓存；如果问题出在数据库服务器上，可以做数据级或者页面级的缓存。 我们希望达到一个什么样的 capacity？ 很多有多年一线工作经验的面试者在这样一个系统设计中竟然不去考虑究竟需要一个什么样的 capacity，就进入到具体的解决方案，这样是不妥的。capacity 因问题而异，在这例子中，起码 要考虑 1) 缓存系统每秒的处理能力 2) 缓存系统的容量。对于一个 20k PRM 的请求数量，缓存 系统应该能承受 50k，100k，甚至 200k PRM 的请求。至于容量，应该考虑假设所有不同的请求 都被缓存（worst case），需要多大的容量，在限定的软硬件条件下，是否能达到这个容量，达不 到的话，什么样的上限比较合理。 有了这样一个目标后，你还需要对你要使用的工具有个谱。有一个面试者说用 redis 做缓存，因为 redis 很快。「很快」是个很虚的概念，我于是问这个面试者你觉得 redis 对于 1k 大小的 value，在 commodity hardware 上做 GET 操作每秒钟的 QPS 是多少？对此，面试者一点概 念也没有，我让他猜，他竟然给了个 3-5k QPS 的估值。我自己印象中 redis benchmark GET 操作大概是 100k 这个数量级，当然，每次返回 1k 大小的数据会拖累这个结果，但绝不会差出来 两个数量级。 有了设计容量的概念后，我们需要知道要缓存数据的大小，这其中，median size，average size，max size 都需要了解一下，起码知道是什么量级。返回 2k 大小的数据和 200k 大小的数 据的处理方式可能是完全不同的，假设你的缓存系统的容量是 1M，2k 数据大小的缓存直接占用的内 存是 2G，而 200k 则是 200G，后者显然不能使用内存来做缓存，只能用文件系统缓存。 讲到文件系统，多说两句。用文件系统做缓存则需要注意 unix 的目录实际上是一个记录文件名和 inode 对应关系的 map（你可以 ls -ai1 . 查看）。单个目录下的文件越多，这个 map 越大， 需要的读取次数就越多（一般系统调用会每次读 32k 或者类似的量级），所以当一个目录下的文件 特别多时，访问效率会急剧下降。这是为什么常见的文件缓存系统都是用两级甚至多级目录，1M 个 文件，一级目录使用两个字母或数字，可以有 (26 + 10) 平方个二级目录，也就是 1296 个目 录，每个目录名两个字节，加上 inode 和其他一些消耗， 10-20 字节完全够用，一次读取就能获 得所有二级目录，而二级目录平均是 772 个文件，一次读取也能完成，总共两次读取，找到缓存文 本文档使用 书栈(BookStack.CN) 构建 - 7 - 

8 .系统设计考察的是什么？ 件，而如果把 1M 个文件放在一个目录下，如果每个记录 32 字节，需要 1000 次读取。这种分级 缓存的思路在很多系统中都能见到，比如 TLB（不过多级 TLB 主要是为了节省内存）。 设计是否有优化的地方？ 如今，内存，硬盘已经非常便宜，很多时候我们做系统设计，已经不需要一个比特或者一个字节地去 扣细节，但这并不意味着更好的，更省内存，更快运行的方案就没有价值。我曾在一个面试中和面试 者讨论一个系统设计的优化，那个面试者对我「逼」着他优化算法很不理解，他认为 computation 这么便宜，钱不是问题，多加几台机器并行运算就可以了。这是一种错误的做事态度。 永远不要忘了设计应该是面向未来的，如果通过更换更好的算法，能节省数十倍的内存（bitmap vs hashmap），或者数十倍的运算（bloom filter pre-filter vs raw computation），那么 你省下的不仅仅是当下的资源（或者金钱），还有未来的时间 —— 因为，当你的应用有10倍的流量 时，你还能够应对自如。 此外，优化可能会从量变转化为质变。一个 analytics 应用如果每五分钟才能完成一次分析，一小 时仅能进行 12 次分析；如果将其优化成 30 秒完成，一个小时就可能完成 120 次，用户可以更 快地掌握趋势。 一个认为资源不是问题，钱不是问题的设计者，只能是一个平庸的设计者。 每个认真的程序员应该这样看待自己：In me the tiger sniffs the rose. https://zhuanlan.zhihu.com/p/20578447 本文档使用 书栈(BookStack.CN) 构建 - 8 - 

9 .分布式ID生成器 分布式ID生成器 应用场景(Scenario) 需求(Needs) UUID 多台MySQL服务器 Twitter Snowflake 参考资料 如何设计一个分布式ID生成器(Distributed ID Generator)，并保证ID按时间粗略有序？ 应用场景(Scenario) 现实中很多业务都有生成唯一ID的需求，例如： 用户ID 微博ID 聊天消息ID 帖子ID 订单ID 需求(Needs) 这个ID往往会作为数据库主键，所以需要保证全局唯一。数据库会在这个字段上建立聚集索引 (Clustered Index，参考 MySQL InnoDB)，即该字段会影响各条数据再物理存储上的顺序。 ID还要尽可能短，节省内存，让数据库索引效率更高。基本上64位整数能够满足绝大多数的场景，但 是如果能做到比64位更短那就更好了。需要根据具体业务进行分析，预估出ID的最大值，这个最大值 通常比64位整数的上限小很多，于是我们可以用更少的bit表示这个ID。 查询的时候，往往有分页或者排序的需求，所以需要给每条数据添加一个时间字段，并在其上建立普 通索引(Secondary Index)。但是普通索引的访问效率比聚集索引慢，如果能够让ID按照时间粗略 有序，则可以省去这个时间字段。为什么不是按照时间精确有序呢？因为按照时间精确有序是做不到 的，除非用一个单机算法，在分布式场景下做到精确有序性能一般很差。 这就引出了ID生成的三大核心需求： 全局唯一(unique) 按照时间粗略有序(sortable by time) 尽可能短 下面介绍一些常用的生成ID的方法。 本文档使用 书栈(BookStack.CN) 构建 - 9 - 

10 .分布式ID生成器 UUID 用过MongoDB的人会知道，MongoDB会自动给每一条数据赋予一个唯一的ObjectId,保证不会重复， 这是怎么做到的呢？实际上它用的是一种UUID算法，生成的ObjectId占12个字节，由以下几个部分 组成， 4个字节表示的Unix timestamp, 3个字节表示的机器的ID 2个字节表示的进程ID 3个字节表示的计数器 UUID是一类算法的统称，具体有不同的实现。UUID的有点是每台机器可以独立产生ID，理论上保证 不会重复，所以天然是分布式的，缺点是生成的ID太长，不仅占用内存，而且索引查询效率低。 多台MySQL服务器 既然MySQL可以产生自增ID，那么用多台MySQL服务器，能否组成一个高性能的分布式发号器呢？ 显然可以。 假设用8台MySQL服务器协同工作，第一台MySQL初始值是1，每次自增8，第二台MySQL初始值是2， 每次自增8，依次类推。前面用一个 round-robin load balancer 挡着，每来一个请求，由 round-robin balancer 随机地将请求发给8台MySQL中的任意一个，然后返回一个ID。 Flickr就是这么做的，仅仅使用了两台MySQL服务器。可见这个方法虽然简单无脑，但是性能足够 好。不过要注意，在MySQL中，不需要把所有ID都存下来，每台机器只需要存一个MAX_ID就可以 了。这需要用到MySQL的一个REPLACE INTO特性。 这个方法跟单台数据库比，缺点是ID是不是严格递增的，只是粗略递增的。不过这个问题不大，我们 的目标是粗略有序，不需要严格递增。 Twitter Snowflake 比如 Twitter 有个成熟的开源项目，就是专门生成ID的，Twitter Snowflake 。Snowflake的 核心算法如下： 本文档使用 书栈(BookStack.CN) 构建 - 10 - 

11 .分布式ID生成器 最高位不用，永远为0，其余三组bit占位均可浮动，看具体的业务需求而定。默认情况下41bit的时 间戳可以支持该算法使用到2082年，10bit的工作机器id可以支持1023台机器，序列号支持1毫秒产 生4095个自增序列id。 Instagram用了类似的方案，41位表示时间戳，13位表示shard Id(一个shard Id对应一台 PostgreSQL机器),最低10位表示自增ID，怎么样，跟Snowflake的设计非常类似吧。这个方案用 一个PostgreSQL集群代替了Twitter Snowflake 集群，优点是利用了现成的PostgreSQL，容易 懂，维护方便。 有的面试官会问，如何让ID可以粗略的按照时间排序？上面的这种格式的ID，含有时间戳，且在高 位，恰好满足要求。如果面试官又问，如何保证ID严格有序呢？在分布式这个场景下，是做不到的， 要想高性能，只能做到粗略有序，无法保证严格有序。 参考资料 Sharding & IDs at Instagram Ticket Servers: Distributed Unique Primary Keys on the Cheap Twitter Snowflake 细聊分布式ID生成方法 - 沈剑 服务化框架－分布式Unique ID的生成方法一览 - 江南白衣 生成全局唯一ID的3个思路，来自一个资深架构师的总结 本文档使用 书栈(BookStack.CN) 构建 - 11 - 

12 .短网址的长度 短网址的长度 短网址的长度 参考资料 如何设计一个文件系统缓存？ 在 Linux 操作系统中，当应用程序需要读取文件中的数据时，操作系统先分配一些内存，将数据从 磁盘读入到这些内存中，然后再将数据传给应用程序；当需要往文件中写数据时，操作系统先分配内 存接收用户数据，然后再将数据从内存写到磁盘上。文件 Cache 管理指的就是对这些由操作系统分 配，并用来存储文件数据的内存的管理。 短网址的长度 参考资料 Linux 内核的文件 Cache 管理机制介绍-IBM Ticket Servers: Distributed Unique Primary Keys on the Cheap Twitter Snowflake 短 URL 系统是怎么设计的？ 本文档使用 书栈(BookStack.CN) 构建 - 12 - 

13 .短网址系统(TinyURL) 短网址系统(TinyURL) 使用场景(Scenario) 需求(Needs) 短网址的长度 一对一还是一对多映射？ 如何计算短网址 如何存储 301还是302重定向 预防攻击 参考资料 如何设计一个短网址服务(TinyURL)？ 使用场景(Scenario) 微博和Twitter都有140字数的限制，如果分享一个长网址，很容易就超出限制，发布出去。短网址 服务可以把一个长网址变成短网址，方便在社交网络上传播。 需求(Needs) 很显然，要尽可能的短。长度设计为多少才合适呢？ 短网址的长度 当前互联网上的网页总数大概是 45亿(参考 http://www.worldwidewebsize.com)，45亿超过 了 2^{32}=4294967296 ，但远远小于64位整数的上限值，那么用一个64位整数足够了。 微博的短网址服务用的是长度为7的字符串，这个字符串可以看做是62进制的数，那么最大能表示 {62}^7=3521614606208 个网址，远远大于45亿。所以长度为7就足够了。 一个64位整数如何转化为字符串呢？，假设我们只是用大小写字母加数字，那么可以看做是62进制 数， log_{62} {(2^{64}-1)}=10.7 ，即字符串最长11就足够了。 实际生产中，还可以再短一点，比如新浪微博采用的长度就是7，因为 62^7=3521614606208 ，这 个量级远远超过互联网上的URL总数了，绝对够用了。 现代的web服务器（例如Apache, Nginx）大部分都区分URL里的大小写了，所以用大小写字母来区 分不同的URL是没问题的。 因此，正确答案：长度不超过7的字符串，由大小写字母加数字共62个字母组成 本文档使用 书栈(BookStack.CN) 构建 - 13 - 

14 .短网址系统(TinyURL) 一对一还是一对多映射？ 一个长网址，对应一个短网址，还是可以对应多个短网址？ 这也是个重大选择问题 一般而言，一个长网址，在不同的地点，不同的用户等情况下，生成的短网址应该不一样，这样，在 后端数据库中，可以更好的进行数据分析。如果一个长网址与一个短网址一一对应，那么在数据库 中，仅有一行数据，无法区分不同的来源，就无法做数据分析了。 以这个7位长度的短网址作为唯一ID，这个ID下可以挂各种信息，比如生成该网址的用户名，所在网 站，HTTP头部的 User Agent等信息，收集了这些信息，才有可能在后面做大数据分析，挖掘数据 的价值。短网址服务商的一大盈利来源就是这些数据。 正确答案：一对多 如何计算短网址 现在我们设定了短网址是一个长度为7的字符串，如何计算得到这个短网址呢？ 最容易想到的办法是哈希，先hash得到一个64位整数，将它转化为62进制整，截取低7位即可。但是 哈希算法会有冲突，如何处理冲突呢，又是一个麻烦。这个方法只是转移了矛盾，没有解决矛盾，抛 弃。 正确答案：分布式发号器(Distributed ID Generator) 如何存储 如果存储短网址和长网址的对应关系？以短网址为 primary key, 长网址为value, 可以用传统的 关系数据库存起来，例如MySQL, PostgreSQL，也可以用任意一个分布式KV数据库，例如Redis, LevelDB。 如果你手痒想要手工设计这个存储，那就是另一个话题了，你需要完整地造一个KV存储引擎轮子。当 前流行的KV存储引擎有LevelDB何RockDB，去读它们的源码吧 :D 301还是302重定向 这也是一个有意思的问题。这个问题主要是考察你对301和302的理解，以及浏览器缓存机制的理解。 301是永久重定向，302是临时重定向。短地址一经生成就不会变化，所以用301是符合http语义 的。但是如果用了301， Google，百度等搜索引擎，搜索的时候会直接展示真实地址，那我们就无 法统计到短地址被点击的次数了，也无法收集用户的Cookie, User Agent 等信息，这些信息可以 用来做很多有意思的大数据分析，也是短网址服务商的主要盈利来源。 所以，正确答案是302重定向。 本文档使用 书栈(BookStack.CN) 构建 - 14 - 

15 .短网址系统(TinyURL) 可以抓包看看新浪微博的短网址是怎么做的，使用 Chrome 浏览器，访问这个URL http://t.cn/RX2VxjI，是我事先发微博自动生成的短网址。来抓包看看返回的结果是啥， 可见新浪微博用的就是302临时重定向。 预防攻击 如果一些别有用心的黑客，短时间内向TinyURL服务器发送大量的请求，会迅速耗光ID，怎么办呢？ 首先，限制IP的单日请求总数，超过阈值则直接拒绝服务。 光限制IP的请求数还不够，因为黑客一般手里有上百万台肉鸡的，IP地址大大的有，所以光限制IP作 用不大。 可以用一台Redis作为缓存服务器，存储的不是 ID->长网址，而是 长网址->ID，仅存储一天以内 的数据，用LRU机制进行淘汰。这样，如果黑客大量发同一个长网址过来，直接从缓存服务器里返回 短网址即可，他就无法耗光我们的ID了。 参考资料 Sharding & IDs at Instagram Ticket Servers: Distributed Unique Primary Keys on the Cheap Twitter Snowflake 短 URL 系统是怎么设计的？ 本文档使用 书栈(BookStack.CN) 构建 - 15 - 

16 .信息流(News Feed) 信息流(News Feed) 请设计一个信息流(news feed)。例如Facebook用户首页的信息流，微博用户的信息流，等等。 本文档使用 书栈(BookStack.CN) 构建 - 16 - 

17 .定时任务调度器 定时任务调度器 方案1: PriorityBlockingQueue + Polling 方案2: PriorityBlockingQueue + 时间差 方案3: DelayQueue Task对象 生产者 消费者 定时任务调度器 方案4: 时间轮(HashedWheelTimer) 参考资料 请实现一个定时任务调度器，有很多任务，每个任务都有一个时间戳，任务会在该时间点开始执行。 定时执行任务是一个很常见的需求，例如Uber打车48小时后自动好评，淘宝购物15天后默认好评， 等等。 方案1: PriorityBlockingQueue + Polling 我们很快可以想到第一个办法： 用一个 java.util.concurrent.PriorityBlockingQueue 来作为优先队列。因为我们需要一个优先队 列，又需要线程安全，用 PriorityBlockingQueue 再合适不过了。你也可以手工实现一个自己 的 PriorityBlockingQueue ，用 java.util.PriorityQueue + ReentrantLock ，用一把锁把这个队列 保护起来，就是线程安全的啦 对于生产者，可以用一个 while(true) ，造一些随机任务塞进去 对于消费者，起一个线程，在 while(true) 里每隔几秒检查一下队列，如果有任务，则取出来执 行。 这个方案的确可行，总结起来就是轮询(polling)。轮询通常有个很大的缺点，就是时间间隔不好设 置，间隔太长，任务无法及时处理，间隔太短，会很耗CPU。 方案2: PriorityBlockingQueue + 时间差 可以把方案1改进一下， while(true) 里的逻辑变成： 偷看一下堆顶的元素，但并不取出来，如果该任务过期了，则取出来 如果没过期，则计算一下时间差，然后 sleep()该时间差 不再是 sleep() 一个固定间隔了，消除了轮询的缺点。 稍等！这个方案其实有个致命的缺陷，导致它比 PiorityBlockingQueue + Polling 更加不可用，这 个缺点是什么呢？。。。假设当前堆顶的任务在100秒后执行，消费者线程peek()偷看到了后，开始 本文档使用 书栈(BookStack.CN) 构建 - 17 - 

18 .定时任务调度器 sleep 100秒，这时候一个新的任务插了进来，该任务在10秒后应该执行，但是由于消费者线程要睡 眠100秒，这个新任务无法及时处理。 方案3: DelayQueue 方案2虽然已经不错了，但是还可以优化一下，Java里有一个DelayQueue，完全符合题目的要求。 DelayQueue 设计得非常巧妙，可以看做是一个特化版的 PriorityBlockingQueue ，它把计算时间差 并让消费者等待该时间差的功能集成进了队列，消费者不需要关心时间差的事情了，直接 在 while(true) 里不断 take() 就行了。 DelayQueue的实现原理见下面的代码。 1. import java.util.PriorityQueue; 2. import java.util.concurrent.Delayed; 3. import java.util.concurrent.locks.Condition; 4. import java.util.concurrent.locks.ReentrantLock; 5. 6. import static java.util.concurrent.TimeUnit.NANOSECONDS; 7. 8. public class DelayQueue<E extends Delayed> { 9. private final transient ReentrantLock lock = new ReentrantLock(); 10. private final PriorityQueue<E> q = new PriorityQueue<E>(); 11. private final Condition available = lock.newCondition(); 12. private Thread leader = null; 13. 14. public DelayQueue() {} 15. 16. /** 17. * Inserts the specified element into this delay queue. 18. * 19. * @param e the element to add 20. * @return {@code true} 21. * @throws NullPointerException if the specified element is null 22. */ 23. public boolean put(E e) { 24. final ReentrantLock lock = this.lock; 25. lock.lock(); 26. try { 27. q.offer(e); 28. if (q.peek() == e) { 29. leader = null; 30. available.signal(); 31. } 32. return true; 33. } finally { 34. lock.unlock(); 本文档使用 书栈(BookStack.CN) 构建 - 18 - 

19 .定时任务调度器 35. } 36. } 37. 38. /** 39. * Retrieves and removes the head of this queue, waiting if necessary 40. * until an element with an expired delay is available on this queue. 41. * 42. * @return the head of this queue 43. * @throws InterruptedException {@inheritDoc} 44. */ 45. public E take() throws InterruptedException { 46. final ReentrantLock lock = this.lock; 47. lock.lockInterruptibly(); 48. try { 49. for (;;) { 50. E first = q.peek(); 51. if (first == null) 52. available.await(); 53. else { 54. long delay = first.getDelay(NANOSECONDS); 55. if (delay <= 0) 56. return q.poll(); 57. first = null; // don't retain ref while waiting 58. if (leader != null) 59. available.await(); 60. else { 61. Thread thisThread = Thread.currentThread(); 62. leader = thisThread; 63. try { 64. available.awaitNanos(delay); 65. } finally { 66. if (leader == thisThread) 67. leader = null; 68. } 69. } 70. } 71. } 72. } finally { 73. if (leader == null && q.peek() != null) 74. available.signal(); 75. lock.unlock(); 76. } 77. } 78. } 这个代码中有几个要点要注意一下。 1. put()方法 本文档使用 书栈(BookStack.CN) 构建 - 19 - 

20 .定时任务调度器 1. if (q.peek() == e) { 2. leader = null; 3. available.signal(); 4. } 如果第一个元素等于刚刚插入进去的元素，说明刚才队列是空的。现在队列里有了一个任务，那么就 应该唤醒所有在等待的消费者线程，避免了方案2的缺点。将 leader 重置为null，这些消费者之间 互相竞争，自然有一个会被选为leader。 2. 线程leader的作用 leader 这个成员有啥作用？DelayQueue的设计其实是一个Leader/Follower模式， leader 就 是指向Leader线程的。该模式可以减少不必要的等待时间，当一个线程是Leader时，它只需要一个 时间差；其他Follower线程则无限等待。比如头节点任务还有5秒就要开始了，那么Leader线程会 sleep 5秒，不需要傻傻地等待固定时间间隔。 想象一下有个多个消费者线程用take方法去取任务,内部先加锁,然后每个线程都去peek头节点。如 果leader不为空说明已经有线程在取了，让当前消费者无限等待。 1. if (leader != null) 2. available.await(); 如果为空说明没有其他消费者去取任务,设置leader为当前消费者，并让改消费者等待指定的时间， 1. else { 2. Thread thisThread = Thread.currentThread(); 3. leader = thisThread; 4. try { 5. available.awaitNanos(delay); 6. } finally { 7. if (leader == thisThread) 8. leader = null; 9. } 10. } 下次循环会走如下分支，取到任务结束， 1. if (delay <= 0) 2. return q.poll(); 3. take()方法中为什么释放first 1. first = null; // don't retain ref while waiting 本文档使用 书栈(BookStack.CN) 构建 - 20 - 

21 .定时任务调度器 我们可以看到 Doug Lea 后面写的注释，那么这行代码有什么用呢？ 如果删除这行代码，会发生什么呢？假设现在有3个消费者线程， 线程A进来获取first,然后进入 else 的 else ,设置了leader为当前线程A，并让A等待一段 时间 线程B进来获取first, 进入else的阻塞操作,然后无限期等待，这时线程B是持有first引用的 线程A等待指定时间后被唤醒，获取对象成功，出队，这个对象理应被GC回收，但是它还被线程B 持有着，GC链可达，所以不能回收这个first 只要线程B无限期的睡眠，那么这个本该被回收的对象就不能被GC销毁掉，那么就会造成内存泄 露 Task对象 1. import java.util.concurrent.Delayed; 2. import java.util.concurrent.TimeUnit; 3. 4. public class Task implements Delayed { 5. private String name; 6. private long startTime; // milliseconds 7. 8. public Task(String name, long delay) { 9. this.name = name; 10. this.startTime = System.currentTimeMillis() + delay; 11. } 12. 13. @Override 14. public long getDelay(TimeUnit unit) { 15. long diff = startTime - System.currentTimeMillis(); 16. return unit.convert(diff, TimeUnit.MILLISECONDS); 17. } 18. 19. @Override 20. public int compareTo(Delayed o) { 21. return (int)(this.startTime - ((Task) o).startTime); 22. } 23. 24. @Override 25. public String toString() { 26. return "task " + name + " at " + startTime; 27. } 28. } JDK中有一个接口 java.util.concurrent.Delayed ，可以用于表示具有过期时间的元素，刚好可以拿来 表示任务这个概念。 本文档使用 书栈(BookStack.CN) 构建 - 21 - 

22 .定时任务调度器 生产者 1. import java.util.Random; 2. import java.util.UUID; 3. 4. public class TaskProducer implements Runnable { 5. private final Random random = new Random(); 6. private DelayQueue<Task> q; 7. 8. public TaskProducer(DelayQueue<Task> q) { 9. this.q = q; 10. } 11. 12. @Override 13. public void run() { 14. while (true) { 15. try { 16. int delay = random.nextInt(10000); 17. Task task = new Task(UUID.randomUUID().toString(), delay); 18. System.out.println("Put " + task); 19. q.put(task); 20. Thread.sleep(3000); 21. } catch (InterruptedException e) { 22. e.printStackTrace(); 23. } 24. } 25. } 26. } 生产者很简单，就是一个死循环，不断地产生一些是时间随机的任务。 消费者 1. public class TaskConsumer implements Runnable { 2. private DelayQueue<Task> q; 3. 4. public TaskConsumer(DelayQueue<Task> q) { 5. this.q = q; 6. } 7. 8. @Override 9. public void run() { 10. while (true) { 11. try { 12. Task task = q.take(); 13. System.out.println("Take " + task); 本文档使用 书栈(BookStack.CN) 构建 - 22 - 

23 .定时任务调度器 14. } catch (InterruptedException e) { 15. e.printStackTrace(); 16. } 17. } 18. } 19. } 当 DelayQueue 里没有任务时， TaskConsumer 会无限等待，直到被唤醒，因此它不会消耗CPU。 定时任务调度器 1. public class TaskScheduler { 2. public static void main(String[] args) { 3. DelayQueue<Task> queue = new DelayQueue<>(); 4. new Thread(new TaskProducer(queue), "Producer Thread").start(); 5. new Thread(new TaskConsumer(queue), "Consumer Thread").start(); 6. } 7. } DelayQueue这个方案，每个消费者线程只需要等待所需要的时间差，因此响应速度更快。它内部用 了一个优先队列，所以插入和删除的时间复杂度都是 \log n 。 JDK里还有一个ScheduledThreadPoolExecutor，原理跟DelayQueue类似，封装的更完善，平 时工作中可以用它，不过面试中，还是拿DelayQueue来讲吧，它封装得比较薄，容易讲清楚原理。 方案4: 时间轮(HashedWheelTimer) 时间轮(HashedWheelTimer)其实很简单，就是一个循环队列，如下图所示， 上图是一个长度为8的循环队列，假设该时间轮精度为秒，即每秒走一格，像手表那样，走完一圈就是 8秒。每个格子指向一个任务集合，时间轮无限循环，每转到一个格子，就扫描该格子下面的所有任 本文档使用 书栈(BookStack.CN) 构建 - 23 - 

24 .定时任务调度器 务，把时间到期的任务取出来执行。 举个例子，假设指针当前正指向格子0，来了一个任务需要4秒后执行，那么这个任务就会放在格子4 下面，如果来了一个任务需要20秒后执行怎么？由于这个循环队列转一圈只需要8秒，这个任务需要 多转2圈，所以这个任务的位置虽然依旧在格子4(20%8+0=4)下面，不过需要多转2圈后才执行。因 此每个任务需要有一个字段记录需圈数，每转一圈就减1，减到0则立刻取出来执行。 怎么实现时间轮呢？Netty中已经有了一个时间轮的实现, HashedWheelTimer.java，可以参考它 的源代码。 时间轮的优点是性能高，插入和删除的时间复杂度都是O(1)。Linux 内核中的定时器采用的就是这 个方案。 Follow up: 如何设计一个分布式的定时任务调度器呢？ 答: Redis ZSet, RabbitMQ等 参考资料 java.util.concurrent.DelayQueue HashedWheelTimer.java - Github delayQueue原理理解之源码解析 - 简书 细说延时任务的处理 - 简书 延迟任务的实现总结 - nick hao - 博客园 定时器（Timer）的实现 java.util.concurrent.DelayQueue Example HashedWheelTimer 原理 - ZimZz - 博客园 Hash算法系列-具体算法（HashedWheelTimer） - CSDN java Disruptor工作原理，谁能用一个比喻形容下? - 知乎 1分钟实现“延迟消息”功能 - 58沈剑 Linux 下定时器的实现方式分析 - IBM 1分钟了解Leader-Follower线程模型 - 58沈剑 本文档使用 书栈(BookStack.CN) 构建 - 24 - 

25 .API限速 API限速 参考资料 给定一个公共API，限制每个用户每秒只能调用1000次，如何实现？ 这个一个经典的API限速问题(API rate limiting)。 参考资料 Google Interview API rate limiting - CareerCup 本文档使用 书栈(BookStack.CN) 构建 - 25 - 

26 .线程安全的HashMap 线程安全的HashMap 方案1: JDK7版本，锁分离 方案2: JDK8版本，锁分离+CAS+红黑树 参考资料 请设计一个线程安全的HashMap。 先回顾一下普通的哈希表(HashMap)是怎么写出来的，再讨论如何做到线程安全。HashMap的核心在 于如何解决哈希冲突，主流思路有两种， 开地址法(Open addressing). 即所有元素在一个一维数组里，遇到冲突则按照一定规则向后 跳，假设元素x原本在位置 hash(x)%m （m表示数组长度），那么第i次冲突时位置变为 Hi = [hash(x) + di] % m ，其中 di 表示第i次冲突时人为加上去的偏移量。偏移量 di 一般有如下 3种计算方法， i. 线性探测法(Linear Probing)。非常简单，发现位子已经被占了，则向后移动1位， 即 d_i = i , i=1,2,3,… 该算法最大的优点在于计算速度快，对CPU高速缓存友好；其缺点也非常明显，假设3个元素 x1，x2，x3的哈希值都相同，记为p, x1先来，查看位置p，是空，则x1被映射到位置p， x2后到达，查看位置p，发生第一次冲突，向后探测一下，即p+1，该位置为空，于是x2映 射到p+1, 同理，计算x3的位置需要探测位置p, p+1, p+2，也就是说对于发生冲突的所有 元素，在探测过程中会扎堆，导致效率低下，这种现象被称为clustering。 ii. 二次探测法(Quadratic Probing)。 d_i=ai^2+bi+c , 其中a,b,c为系数， d_i 是i 的二次函数，所以称为二次探测法。该算法的性能介于线性探测和双哈希之间。 iii. 双哈希法(Double Hashing)。偏移量di由另一个哈希函数计算而来，设为 hash2(x) ， 则 di=(hash2(x) % (m-1) + 1) * i 拉链法(Chaining)。开一个定长数组，每个格子指向一个桶(Bucket, 可以用单链表或双向链 表表示)，对每个元素计算出哈希并取模，找到对应的桶，并插入该桶。发生冲突的元素会处于同 一个桶中。 JDK7和JDK8里 java.util.HashMap 采取了拉链法。 如何将基于拉链法的HashMap改造为线程安全的呢？有以下几个思路， 将所有public方法都加上synchronized. 相当于设置了一把全局锁，所有操作都需要先获取 锁， java.util.HashTable 就是这么做的，性能很低 由于每个桶在逻辑上是相互独立的，将每个桶都加一把锁，如果两个线程各自访问不同的桶，就 不需要争抢同一把锁了。这个方案的并发性比单个全局锁的性能要好，不过锁的个数太多，也有 很大的开销。 本文档使用 书栈(BookStack.CN) 构建 - 26 - 

27 .线程安全的HashMap 锁分离(Lock Stripping)技术。第2个方法把锁的压力分散到了多个桶，理论上是可行的的， 但是假设有1万个桶，就要新建1万个 ReentrantLock 实例，开销很大。可以将所有的桶均匀的划 分为16个部分，每一部分成为一个段(Segment)，每个段上有一把锁，这样锁的数量就降低到了 16个。JDK 7里的 java.util.concurrent.ConcurrentHashMap 就是这个思路。 在JDK8里，ConcurrentHashMap的实现又有了很大变化，它在锁分离的基础上，大量利用了了 CAS指令。并且底层存储有一个小优化，当链表长度太长（默认超过8）时，链表就转换为红黑 树。链表太长时，增删查改的效率比较低，改为红黑树可以提高性能。JDK8里的 ConcurrentHashMap有6000多行代码，JDK7才1500多行。 方案1: JDK7版本，锁分离 TODO 方案2: JDK8版本，锁分离+CAS+红黑树 TODO 参考资料 ConcurrentHashMap.java - JDK8 ConcurrentHashMap.java - JDK7 Java 8系列之重新认识HashMap - 美团点评技术团队 JDK1.8源码分析之HashMap（一） - 博客园 ConcurrentHashMap - 博客园 探索jdk8之ConcurrentHashMap 的实现机制 - 博客园 《Java源码分析》：ConcurrentHashMap JDK1.8 - CSDN ConcurrentHashMap源码解读(put/transfer/get)-jdk8 ConcurrentHashMap源码分析（JDK8版本） ConcurrentHashMap源码分析—Java8 聊聊并发（四）——深入分析ConcurrentHashMap - InfoQ 探索 ConcurrentHashMap 高并发性的实现机制 - IBM ConcurrentHashMap源码解析 - Github 并发与并行的区别？ - 知乎 深入理解Java内存模型（一） - 基础 深入理解Java内存模型（二） - 重排序 深入理解Java内存模型（三） - 顺序一致性 深入理解Java内存模型（四） - volatile 深入理解Java内存模型（五） - 锁 深入理解Java内存模型（六） - final 深入理解Java内存模型（七） - 总结 本文档使用 书栈(BookStack.CN) 构建 - 27 - 

28 .线程安全的HashMap 本文档使用 书栈(BookStack.CN) 构建 - 28 - 

29 .最近一个小时内访问频率最高的10个IP 最近一个小时内访问频率最高的10个IP 实时输出最近一个小时内访问频率最高的10个IP，要求： 实时输出 从当前时间向前数的1个小时 QPS可能会达到10W/s 这道题乍一看很像Top K 频繁项，是不是需要 Lossy Count 或 Count-Min Sketch 之类的算 法呢？ 其实杀鸡焉用牛刀，这道题用不着上述算法，请听我仔细分析。 1. QPS是 10万/秒，即一秒内最高有 10万个请求，那么一个小时内就有 100000*3600=360000000≈$$2^{28.4}$$，向上取整，大概是 $$2^{29}$$个请求，也不 是很大。我们在内存中建立3600个 HashMap<Int,Int> ，放在一个数组里，每秒对应一个 HashMap，IP地址为key, 出现次数作为value。这样，一个小时内最多有$$2^{29}$$个 pair，每个pair占8字节，总内存大概是 $$2^{29} \times 8=2^{32}$$字节，即4GB，单 机完全可以存下。 2. 同时还要新建一个固定大小为10的小根堆，用于存放当前出现次数最大的10个IP。堆顶是10个 IP里频率最小的IP。 3. 每次来一个请求，就把该秒对应的HashMap里对应的IP计数器增1，并查询该IP是否已经在堆中 存在， 如果不存在，则把该IP在3600个HashMap的计数器加起来，与堆顶IP的出现次数进行比 较，如果大于堆顶元素，则替换掉堆顶元素，如果小于，则什么也不做 如果已经存在，则把堆中该IP的计数器也增1，并调整堆 4. 需要有一个后台常驻线程，每过一秒，把最旧的那个HashMap销毁，并为当前这一秒新建一个 HashMap，这样维持一个一小时的窗口。 5. 每次查询top 10的IP地址时，把堆里10个IP地址返回来即可。 以上就是该方案的全部内容。 有的人问，可不可以用”IP + 时间”作为key, 把所有pair放在单个HashMap里？如果把所有数据放 在一个HashMap里，有两个巨大的缺点， 第4步里，怎么淘汰掉一个小时前的pair呢？这时候后台线程只能每隔一秒，全量扫描这个 HashMap里的所有pair,把过期数据删除，这是线性时间复杂度，很慢。 这时候HashMap里的key存放的是”IP + 时间”组合成的字符串，占用内存远远大于一个int。 而前面的方案，不用存真正的时间，只需要开一个3600长度的数组来表示一个小时时间窗口。 本文档使用 书栈(BookStack.CN) 构建 - 29 -