透明多级分流系统（架构扫盲贴）

技术分享 2年前 (2023-02-25) 0 999+

关注

引子

现代互联网系统，架构设计时避不开的一点就是流量规划、负载均衡。期望做到透明、多级的分流系统。“多级”就是在各个层面的技术组件来分流，“透明”就是业务无感知（甚至是技术无感知）。本文期望能够给各位架构师作为扫盲贴使用。

两条普适性原则：

1.尽最大限度减少到达单点部件的流量。引导请求分流至最合适的组件中，避免绝大多数流量汇集到单点部件（如数据库），同时依然能够在绝大多数时候保证处理结果的准确性，使单点系统在出现故障时自动而迅速地实施补救措施，这便是系统架构中多级分流的意义。
2.奥卡姆剃刀原则。作为一名架构设计者，应对多级分流的手段有全面的理解与充分的准备，同时清晰地意识到这些设施并不是越多越好。在能满足需求的前提下，最简单的系统就是最好的系统。

作为架构师，想一想应对大流量互联网系统，我们有哪些可以优化的地方？扩带宽？服务器/组件横向扩容？做缓存？基本思路如下图所示：

一、客户端缓存

客户端缓存（Client Cache）：HTTP 协议的无状态性决定了它必须依靠客户端缓存来解决网络传输效率上的缺陷。包含三种缓存机制：“状态缓存”、“强制缓存”（“强缓存”）和“协商缓存”。

1.1 状态缓存

是指不经过服务器，客户端直接根据缓存信息对目标网站的状态判断。例如：301/Moved Permanently（永久重定向）

1.2 强制缓存

客户端可以无须经过任何请求，在指定时点前一直持有和使用该资源的本地缓存副本。

Expires

Expires 是 HTTP/1.0 协议中开始提供的 Header，后面跟随一个截至时间参数。当服务器返回某个资源时带有该 Header 的话，意味着服务器承诺截止时间之前资源不会发生变动，浏览器可直接缓存该数据，不再重新发请求，示例：

HTTP/1.1 200 OK Expires: Wed, 8 Apr 2020 07:28:00 GMT

缺点：

受限于客户端的本地时间。

无法处理涉及到用户身份的私有资源。

无法描述“不缓存”的语义。

Cache-Control是 HTTP/1.1 协议中定义的强制缓存 Header，它的语义比起 Expires 来说就丰富了很多，如果 Cache-Control 和 Expires 同时存在，并且语义存在冲突（譬如 Expires 与 max-age / s-maxage 冲突）的话，规定必须以 Cache-Control 为准。Cache-Control 的使用示例如下：

HTTP/1.1 200 OK Cache-Control: max-age=600

1.3 协商缓存

基于检测的缓存机制，通常被称为“协商缓存”。协商缓存有两种变动检查机制，分别是根据资源的修改时间进行检查，以及根据资源唯一标识是否发生变化来进行检查，它们都是靠一组成对出现的请求、响应 Header 来实现的：

Last-Modified 和 If-Modified-Since：Last-Modified 是服务器的响应 Header，用于告诉客户端这个资源的最后修改时间。对于带有这个 Header 的资源，当客户端需要再次请求时，会通过 If-Modified-Since 把之前收到的资源最后修改时间发送回服务端。

如果此时服务端发现资源在该时间后没有被修改过，就只要返回一个 304/Not Modified 的响应即可，无须附带消息体，达到节省流量的目的，如下所示：

HTTP/1.1 304 Not Modified Cache-Control: public, max-age=600 Last-Modified: Wed, 8 Apr 2020 15:31:30 GMT

如果此时服务端发现资源在该时间之后有变动，就会返回 200/OK 的完整响应，在消息体中包含最新的资源，如下所示：

HTTP/1.1 200 OK Cache-Control: public, max-age=600 Last-Modified: Wed, 8 Apr 2020 15:31:30 GMT  Content

Etag 和 If-None-Match：Etag 是服务器的响应 Header，用于告诉客户端这个资源的唯一标识。HTTP 服务器可以根据自己的意愿来选择如何生成这个标识，譬如 Apache 服务器的 Etag 值默认是对文件的索引节点（INode），大小和最后修改时间进行哈希计算后得到的。对于带有这个 Header 的资源，当客户端需要再次请求时，会通过 If-None-Match 把之前收到的资源唯一标识发送回服务端。

如果此时服务端计算后发现资源的唯一标识与上传回来的一致，说明资源没有被修改过，就只要返回一个 304/Not Modified 的响应即可，无须附带消息体，达到节省流量的目的，如下所示：

HTTP/1.1 304 Not Modified Cache-Control: public, max-age=600 ETag: "28c3f612-ceb0-4ddc-ae35-791ca840c5fa"

如果此时服务端发现资源的唯一标识有变动，就会返回 200/OK 的完整响应，在消息体中包含最新的资源，如下所示：

HTTP/1.1 200 OK Cache-Control: public, max-age=600 ETag: "28c3f612-ceb0-4ddc-ae35-791ca840c5fa"  Content

Etag是 HTTP 中一致性最强的缓存机制,又是 HTTP 中性能最差的缓存机制。

二、域名解析

2.1 概念

域名缓存（DNS Lookup）：DNS 也许是全世界最大、使用最频繁的信息查询系统，如果没有适当的分流机制，DNS 将会成为整个网络的瓶颈。DNS的核心作用就是把域名解析成IP地址。典型的DNS域名解析流程如下图：

2.2 缺点

DNS 系统多级分流的设计本生没啥问题，但在极限情况（各级服务器均无缓存）下，性能很差。--->专门有一种被称为“DNS 预取”（DNS Prefetching）的前端优化手段用来避免这类问题。
DNS 的分级查询意味着每一级都有可能受到中间人攻击的威胁，流量被劫持。--->解决方案：最近几年出现了另一种新的 DNS 工作模式：HTTPDNS（也称为 DNS over HTTPS，DoH）。它将原本的 DNS 解析服务开放为一个基于 HTTPS 协议的查询服务，替代基于 UDP 传输协议的 DNS 域名解析。

三、传输链路

流量从客户端往服务器传输，这个过程就是“传输链路”。程序发出的请求能否与应用层、传输层协议提倡的方式相匹配，对传输的效率也会有极大影响。由于HTTP 协议还在持续发展，从 20 世纪 90 年代的 HTTP/1.0 和 HTTP/1.1，到 2015 年发布的 HTTP/2，再到 2019 年的 HTTP/3，由于 HTTP 协议本身的变化，使得“适合 HTTP 传输的请求”的特征也在不断变化。变化如下图：

3.1 连接数优化

HTTP（ HTTP/3 以前）是以 TCP 为传输层的应用层协议。减少请求数量和扩大并发请求数成为了优化的主流思想。

HTTP/1.0持久连接（Persistent Connection），也称为连接Keep-Alive 机制。

原理是让客户端对同一个域名长期持有一个或多个不会用完即断的 TCP 连接。
典型做法是在客户端维护一个 FIFO 队列，每次取完数据之后一段时间内不自动断开连接，以便获取下一个资源时直接复用，避免创建 TCP 连接的成本。

HTTP/2 的最重要的技术特征一，被称为 HTTP/2 多路复用（HTTP/2 Multiplexing）技术。如下图所示：

核心：

流（Stream）作为数据通道。
帧（Frame）作为最小信息单位，且附带一个流 ID 以标识这个帧属于哪个流。
传输时按照帧打散数据到不同流上传输。接收时根据ID，将不同流中的数据段重组。
在 HTTP/2 中 Header 压缩的原理是基于字典编码的信息复用，是单域名单连接的机制（对每个域名只维持一个 TCP 连接（One Connection Per Origin）来以任意顺序传输任意数量的资源），更适合小文件传输。

3.2 传输压缩

“静态预压缩”（Static Precompression）：在网络时代的早期，服务器处理能力还很薄弱，为了启用压缩，把静态资源先预先压缩为.gz 文件的形式存放起来，当客户端可以接受压缩版本的资源时（请求的 Header 中包含 Accept-Encoding: gzip）就返回压缩后的版本（响应的 Header 中包含 Content-Encoding: gzip），否则就返回未压缩的原版。
“即时压缩”（On-The-Fly Compression）：现代服务器处理能力大幅提升，废弃预压缩，使用即时压缩。整个压缩过程全部在内存的数据流中完成，不必等资源压缩完成再返回响应，这样可以显著提高“首字节时间”（Time To First Byte，TTFB），改善 Web 性能体验。缺点是不知道压缩后资源的确切大小（Content-Length 这个响应 Header）。

3.3 快速 UDP 网络连接

“快速 UDP 网络连接”（Quick UDP Internet Connections，QUIC）：以 UDP 协议为基础，由自己来实现可靠传输能力，并专门支持移动设备的网络切换场景。QUIC 提出了连接标识符的概念，该标识符可以唯一地标识客户端与服务器之间的连接，而无须依靠 IP 地址。这样，切换网络后，只需向服务端发送一个包含此标识符的数据包即可重用既有的连接。2018 年末，IETF 正式批准了 HTTP over QUIC 使用 HTTP/3 的版本号，将其确立为最新一代的互联网标准。

截止到2023.2.21，根据W3Techs的数据显示，全球网站中，支持HTTP/2 协议占 39.8%，HTTP/3协议占25.2%。

四、内容分发网络

内容分发网络（Content Distribution Network），即CDN是一种十分古老而又十分透明，没什么存在感的分流系统，许多人都说听过它，但真正了解过它的人却很少。一个运作良好的内容分发网络，能为互联网系统解决跨运营商、跨地域物理距离所导致的时延问题，能为网站流量带宽起到分流、减负的作用。举个例子，如果不是有遍布全国乃至全世界的阿里云CDN网络支持，哪怕把整个杭州所有市民上网的权力都剥夺了，把带宽全部让给淘宝的机房，恐怕也撑不住全国乃至全球用户在双十一期间的疯狂“围殴”。内容分发网络的工作过程，主要涉及路由解析、内容分发、负载均衡和所能支持的 CDN 应用内容四个方面，我们来逐一了解。

4.1 路由解析

前面第二节讲解了DNS的路由解析，这里扩展一下有CDN参与的过程，核心就是生成了CNAME（Canonical Name规范名）记录。实际上有2条记录：

一条是A记录，代表Address，域名->IP映射关系。
一条是CNAME记录，代表别名->域名映射关系。

如下图：

CDN 路由解析的具体工作过程是：

架设好“hello.com”的服务器后，将服务器的 IP 地址在CDN服务商上注册为“源站”，注册后你会得到一个 CNAME（Canonical Name规范名），DNS 服务商会注册一条 CNAME 记录。
当第一位用户来访你的站点时，将首先发生一次未命中缓存的 DNS 查询，域名服务商解析出 CNAME（“hello.cdn.com”）后，返回给本地 DNS。
本地 DNS 查询 CNAME 时，由于能解析该 CNAME 的权威服务器只有 CDN 服务商所架设的权威 DNS，这个 DNS 服务将根据一定的均衡策略和参数，如拓扑结构、容量、时延等，在全国的 CDN 缓存节点中挑选一个最适合的，将 IP 给本地 DNS。
浏览器从本地 DNS 拿到 IP 地址，访问CDN服务器。有缓存直接返回，没缓存访问源站再缓存返回。

4.2 内容分发

CDN 获取源站资源的过程被称为“内容分发”，这是 CDN 的核心价值。目前主要有以下两种主流的内容分发方式：

主动分发（Push）：分发由源站主动发起，将内容从源站或者其他资源库推送到用户边缘的各个 CDN 缓存节点上。一般用于网站要预载大量资源的场景。譬如双十一之前一段时间内，淘宝、京东等各个网络商城就会开始把未来活动中所需用到的资源推送到 CDN 缓存节点中，特别常用的资源甚至会直接缓存到你的手机 APP 的存储空间或者浏览器的localStorage上。
被动回源（Pull）：被动回源由用户访问所触发全自动、双向透明的资源缓存过程。CDN 缓存节点发现没有该资源，就会实时从源站中获取（源站->CDN->用户）。不适合应用于数据量较大的资源。但使用起来非常方便。这种分发方式是小型站点使用 CDN 服务的主流选择，如果不是自建 CDN，而是购买阿里云、腾讯云的 CDN 服务的站点，多数采用的就是这种方式。

4.3 CDN 应用

内容分发网络最初是为了快速分发静态资源而设计的，但今天的 CDN 所能做的事情已经远远超越了开始建设时的目标，列举如下：

加速静态资源：这是 CDN 本职工作。
安全防御：CDN 在广义上可以视作网站的堡垒机，源站只对 CDN 提供服务，由 CDN 来对外界其他用户服务，这样恶意攻击者就不容易直接威胁源站。CDN 对某些攻击手段的防御，如对DDoS 攻击的防御尤其有效。但需注意，将安全都寄托在 CDN 上本身是不安全的，一旦源站真实 IP 被泄漏，就会面临很高的风险。
协议升级：不少 CDN 提供商都同时对接（代售 CA 的）SSL 证书服务，可以实现源站是 HTTP 协议的，而对外开放的网站是基于 HTTPS 的。同理，可以实现源站到 CDN 是 HTTP/1.x 协议，CDN 提供的外部服务是 HTTP/2 或 HTTP/3 协议、实现源站是基于 IPv4 网络的，CDN 提供的外部服务支持 IPv6 网络，等等。
状态缓存：第一节介绍客户端缓存时简要提到了状态缓存，CDN 不仅可以缓存源站的资源，还可以缓存源站的状态，譬如源站的 301/302 转向就可以缓存起来让客户端直接跳转、还可以通过 CDN 开启HSTS、可以通过 CDN 进行加速 SSL 证书访问，等等。
修改资源：CDN 可以在返回资源给用户的时候修改它的任何内容，以实现不同的目的。譬如，可以对源站未压缩的资源自动压缩并修改 Content-Encoding，以节省用户的网络带宽消耗、可以对源站未启用客户端缓存的内容加上缓存 Header，自动启用客户端缓存，可以修改CORS的相关 Header，将源站不支持跨域的资源提供跨域能力，等等。
访问控制：CDN 可以实现 IP 黑/白名单功能，根据不同的来访 IP 提供不同的响应结果，根据 IP 的访问流量来实现 QoS 控制、根据 HTTP 的 Referer 来实现防盗链，等等。

五、负载均衡

负载均衡（Load Balancing）：调度后方的多台机器，以统一的接口对外提供服务，承担此职责的技术组件被称为“负载均衡”。从形式上来说都可以分为两种：四层负载均衡和七层负载均衡。维基百科上对 OSI 七层模型的介绍如下图：

Layer层级			Protocol data unit (PDU) 协议数据单元	功能	流量在哪负载均衡
主机层（Host Layers）	7	应用层 Application Layer	数据 Data	提供为应用软件提供服务的接口，用于与其他应用软件之间的通信。典型协议：HTTP、HTTPS、FTP、Telnet、SSH、SMTP、POP3 等	Nginx、Kong等。
	6	表达层 Presentation Layer		把数据转换为能与接收者的系统格式兼容并适合传输的格式。	主机。
	5	会话层 Session Layer		负责在数据传输中设置和维护计算机网络中两台计算机之间的通信连接。	主机。
	4	传输层 Transport Layer	Segment 数据段, Datagram数据报	把传输表头加至数据以形成数据包。传输表头包含了所使用的协议等发送信息。典型协议：TCP、UDP、RDP、SCTP、FCP 等	主机。协议里包含了主机的port端口号，如果说IP确定了互联网上主机的位置，那么port指向该主机上监听该端口的程序。
媒体层（Media Layers）	3	网络层 Network Layer	数据包 Packet	决定数据的传输路径选择和转发，将网络表头附加至数据段后以形成报文（即数据包）。典型协议：IPv4/IPv6、IGMP、ICMP、EGP、RIP 等	路由器，设备之间依靠 IPv4/IPv6地址寻址。网络包可以跨越LAN子网，在整个WAN广域网上通信了（比如 internet）。
	2	数据链路层 Data Link Layer	数据帧 Frame	负责点对点的网络寻址、错误侦测和纠错。当表头和表尾被附加至数据包后，就形成数据帧（Frame）。典型协议：WiFi（802.11）、Ethernet（802.3）、PPP 等。	交换机，设备之间依靠MAC地址寻址。同一个LAN里面的设备可以相互通信。
	1	物理层 Physical Layer	比特流 Bit	在物理网络上传送数据帧，它负责管理电脑通信设备和网络媒体之间的互通。包括了针脚、电压、线缆规范、集线器、中继器、网卡、主机接口卡等。	网卡、电缆光纤，设备之间需要靠交叉线进行直连通信。

看了上图后，就可以清晰理解L4/L7负载均衡的概念：

L4四层负载均衡：基于OSI模型的下四层（上图1-4）的负载均衡。简单理解：根据IP+TCP端口，主要依靠2、3层交换器、路由器设备转发流量。特点是性能高。
L7七层负载均衡：基于OSI模型的下七层（上图1-7）的负载均衡。简单理解：基于URL等应用层信息的负载均衡，类似一层代理。特点是功能强，性能低。

下面我们来看看最常用负载均衡方案：L4负载均衡的数据链路层（5.1）、网络层（5.2）和L7负载均衡的应用层（5.3）。

5.1 数据链路层负载均衡

负载均衡器在转发请求过程中直接修改帧的 MAC 目标地址。

如上图，整个请求、转发、响应的链路形成一个“三角关系”，所以这种负载均衡模式也常被很形象地称为“三角传输模式”（Direct Server Return，DSR），也有叫“单臂模式”（Single Legged Mode）或者“直接路由”（Direct Routing），笔者觉得最后这个最贴切，一刀见血。

优点：直接路由，响应由真实服务器直接返回，负载均衡器不会成为网络瓶颈，性能高。
缺点：负载均衡器必须与真实服务器之间的通信必须是二层可达的，即在一个子网当中，无法跨 VLAN。

5.2 网络层负载均衡

两种模式：

1.IP 隧道模式

保持原来的数据包不变，新创建一个数据包，把原来数据包的 Headers 和 Payload 整体作为另一个新的数据包的 Payload，在这个新数据包的 Headers 中写入真实服务器的 IP 作为目标地址，然后把它发送出去。设计者给这种“套娃式”的传输起名叫做“IP 隧道”（IP Tunnel）传输，也还是相当的形象。

优点：可跨越VLAN。
缺点：需要封包拆包，性能损失。

2.NAT 模式

即网络地址转换（Network Address Translation）。直接把数据包 Headers 中的目标地址改掉，请求转发给真实服务器，并响应给均衡器，由均衡器把应答包的源 IP 改回自己的 IP，再发给客户端，这样才能保证客户端与真实服务器之间的正常通信。

优点：可跨越VLAN。
缺点：流量大时，网络成为瓶颈。家用路由器基本就是这个原理。

5.3 应用层负载均衡

1.概念

四层负载均衡（L4）工作模式都属于“转发”，即直接将承载着 TCP 报文的底层数据格式（IP 数据包或以太网帧）转发到真实服务器上，此时客户端到响应请求的真实服务器维持着同一条 TCP 通道。但工作在四层之后（L7）的负载均衡模式就无法再进行转发了，只能进行代理，此时真实服务器、负载均衡器、客户端三者之间由两条独立的 TCP 通道来维持通信，转发与代理的区别如下图所示。

正向代理：最基本的代理，指在客户端设置的（多个client->proxy->服务器）、代表客户端与服务器通信的代理服务，它是客户端可知，而对服务器透明的（无感知）。
反向代理：在服务器设置（proxy->多个服务器），代表真实服务器来与客户端通信的代理服务，此时它对客户端来说是透明的（无感知）。
透明代理：指对双方都透明的，配置在网络中间设备上的代理服务，譬如，架设在路由器上的透明FQ代理。

七层负载均衡器它就属于反向代理中的一种。网络性能不如四层负载均衡器，但它工作在应用层，可以感知应用层通信的具体内容，能够做出更智能的决策。

2. 可实现功能

CDN 可以做的缓存方面的工作（就是除去 CDN 根据物理位置就近返回这种优化链路的工作外），七层均衡器全都可以实现，譬如静态资源缓存、协议升级、安全防护、访问控制，等等。
七层均衡器可以实现更智能化的路由。譬如，根据 Session 路由，以实现亲和性的集群；根据 URL 路由，实现专职化服务（此时就相当于网关的职责）；甚至根据用户身份路由，实现对部分用户的特殊服务（如某些站点的贵宾服务器），等等。
某些安全攻击可以由七层均衡器来抵御，譬如一种常见的 DDoS 手段是 SYN Flood 攻击。
很多微服务架构的系统中，链路治理措施都需要在七层中进行，譬如服务降级、熔断、异常注入，等等。

5.4 均衡策略与实现

常见的均衡策略如下：

轮循均衡（Round Robin）：每一次来自网络的请求轮流分配给内部中的服务器，从 1 至 N 然后重新开始。此种均衡算法适合于集群中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况。
权重轮循均衡（Weighted Round Robin）：根据服务器的不同处理能力，给每个服务器分配不同的权值。能确保高性能的服务器得到更多的使用率，避免低性能的服务器负载过重。
随机均衡（Random）：把来自客户端的请求随机分配给内部中的多个服务器，在数据足够大的场景下能达到相对均衡的分布。
权重随机均衡（Weighted Random）：此种均衡算法类似于权重轮循算法，不过在分配处理请求时是个随机选择的过程。
一致性哈希均衡（Consistency Hash）：根据请求中某一些数据作为特征值来计算需要落在的节点上，保证同一个特征值每次都一定落在相同的服务器上。当服务集群某个服务器出现故障，不会导致整个服务集群的哈希键值重新分布。
响应速度均衡（Response Time）：负载均衡设备对内部各服务器发出一个探测请求（例如 Ping），根据最快响应时间来决定哪一台服务器来响应客户端的服务请求。此种均衡算法能较好的反映服务器的当前运行状态。
最少连接数均衡（Least Connection）：当有新的服务连接请求时，将把当前请求分配给连接数最少的服务器，使均衡更加符合实际情况，负载更加均衡。此种均衡策略适合长时处理的请求服务，如 FTP 传输。

六、服务端缓存

缓存（Cache）：软件开发中的缓存并非多多益善，它有收益，也有风险。服务端缓存大体可分为两类：

为缓解 CPU 压力：譬如把方法运行结果存储起来、把原本要实时计算的内容提前算好、把一些公用的数据进行复用，这可以节省 CPU 算力，顺带提升响应性能。
为缓解 I/O 压力：譬如把原本对网络、磁盘等较慢介质的读写访问变为对内存等较快介质的访问，将原本对单点部件（如数据库）的读写访问变为到可扩缩部件（如缓存中间件）的访问，顺带提升响应性能。

tip:总监级岗位需要关注的东西：硬件提升和缓存带来的风险，需要做一个均衡考量。

6.1 缓存属性

通常，我们设计或者选择缓存至少会考虑以下四个维度的属性：

吞吐量：缓存的吞吐量使用 OPS 值（每秒操作数，Operations per Second，ops/s）来衡量，反映了对缓存进行并发读、写操作的效率，即缓存本身的工作效率高低。
命中率：缓存的命中率即成功从缓存中返回结果次数与总请求次数的比值，反映了引入缓存的价值高低，命中率越低，引入缓存的收益越小，价值越低。
扩展功能：缓存除了基本读写功能外，还提供哪些额外的管理功能，譬如最大容量、失效时间、失效事件、命中率统计，等等。
分布式支持：缓存可分为“进程内缓存”和“分布式缓存”两大类，前者只为节点本身提供服务，无网络访问操作，速度快但缓存的数据不能在各个服务节点中共享，后者则相反。

1.吞吐量

根据 Caffeine 给出的一组目前业界主流进程内缓存实现方案，包括有 Caffeine、ConcurrentLinkedHashMap、LinkedHashMap、Guava Cache、Ehcache 和 Infinispan Embedded 的对比，从Benchmarks中体现出的它们在 8 线程、75%读操作、25%写操作下的吞吐量来看，各种缓存组件库的性能差异还是十分明显的，最高与最低的相差了足有一个数量级，如下图所示。

在 Caffeine 的实现中，设有专门的环形缓存区（Ring Buffer，也常称作 Circular Buffer）来记录由于数据读取而产生的状态变动日志。为进一步减少竞争，Caffeine 给每条线程（对线程取 Hash，哈希值相同的使用同一个缓冲区）都设置一个专用的环形缓冲。所谓环形缓冲，并非 Caffeine 的专有概念，它是一种拥有读、写两个指针的数据复用结构，在计算机科学中有非常广泛的应用。Ring Buffer原理如下图：

2.命中率与淘汰策略

最基础的淘汰策略实现方案有以下三种：

FIFO（First In First Out）：优先淘汰最早进入被缓存的数据。采用这种淘汰策略，很可能会大幅降低缓存的命中率。
LRU（Least Recent Used）：优先淘汰最久未被使用访问过的数据。LRU 通常会采用 HashMap 加 LinkedList 双重结构（如 LinkedHashMap）来实现，以 HashMap 来提供访问接口，保证常量时间复杂度的读取性能，以 LinkedList 的链表元素顺序来表示数据的时间顺序，每次缓存命中时把返回对象调整到 LinkedList 开头，每次缓存淘汰时从链表末端开始清理数据。LRU 尤其适合用来处理短时间内频繁访问的热点对象。但如果短时间内因为某种原因未被访问过，此时这些热点数据依然要面临淘汰的命运。
LFU（Least Frequently Used）：优先淘汰访问次数最少的数据。LFU 会给每个数据添加一个访问计数器，每访问一次就加 1，需要淘汰时就清理计数器数值最小的那批数据。LFU 可以解决上面 LRU 中热点数据间隔一段时间不访问就被淘汰的问题，但同时它又引入了两个新的问题，首先是需要对每个缓存的数据专门去维护一个计数器，每次访问都要更新，在上一节“吞吐量”里解释了这样做会带来高昂的维护开销；另一个问题是不便于处理随时间变化的热度变化，譬如某个曾经频繁访问的数据现在不需要了，它也很难自动被清理出缓存。

近年来提出的 TinyLFU 和 W-TinyLFU 算法：

TinyLFU（Tiny Least Frequently Used）：TinyLFU 是 LFU 的改进版本。为了缓解 LFU 每次访问都要修改计数器所带来的性能负担，TinyLFU 会首先采用 Sketch 对访问数据进行分析，所谓 Sketch 是统计学上的概念，指用少量的样本数据来估计全体数据的特征，这种做法显然牺牲了一定程度的准确性，但是只要样本数据与全体数据具有相同的概率分布，Sketch 得出的结论仍不失为一种高效与准确之间权衡的有效结论。借助Count–Min Sketch算法（可视为布隆过滤器的一种等价变种结构），TinyLFU 可以用相对小得多的记录频率和空间来近似地找出缓存中的低价值数据。为了解决 LFU 不便于处理随时间变化的热度变化问题，TinyLFU 采用了基于“滑动时间窗”（在“流量控制”中我们会更详细地分析这种算法）的热度衰减算法，简单理解就是每隔一段时间，便会把计数器的数值减半，以此解决“旧热点”数据难以清除的问题。

W-TinyLFU（Windows-TinyLFU）：W-TinyLFU 又是 TinyLFU 的改进版本。为了应对稀疏突发访问（绝对频率较小，但突发访问频率很高的数据）的问题，W-TinyLFU 就结合了 LRU 和 LFU 两者的优点，从整体上看是它是 LFU 策略，从局部实现上看又是 LRU 策略。具体做法是将新记录暂时放入一个名为 Window Cache 的前端 LRU 缓存里面，让这些对象可以在 Window Cache 中累积热度，如果能通过 TinyLFU 的过滤器，再进入名为 Main Cache 的主缓存中存储，主缓存根据数据的访问频繁程度分为不同的段（LFU 策略，实际上 W-TinyLFU 只分了两段），但单独某一段局部来看又是基于 LRU 策略去实现的（称为 Segmented LRU）。每当前一段缓存满了之后，会将低价值数据淘汰到后一段中去存储，直至最后一段也满了之后，该数据就彻底清理出缓存。

Caffeine 官方给出的 W-TinyLFU 以及另外两种高级淘汰策略ARC（Adaptive Replacement Cache）、LIRS（Low Inter-Reference Recency Set）与基础的 LFU 策略之间的对比，如下图所示。

3.扩展功能

一般来说，一套标准的 Map 接口（或者来自JSR 107的 javax.cache.Cache 接口）就可以满足缓存访问的基本需要，不过在“访问”之外，专业的缓存往往还会提供很多额外的功能。笔者简要列举如下：

加载器：许多缓存都有“CacheLoader”之类的设计，加载器可以让缓存从只能被动存储外部放入的数据，变为能够主动通过加载器去加载指定 Key 值的数据，加载器也是实现自动刷新功能的基础前提。
淘汰策略：有的缓存淘汰策略是固定的，也有一些缓存能够支持用户自己根据需要选择不同的淘汰策略。
失效策略：要求缓存的数据在一定时间后自动失效（移除出缓存）或者自动刷新（使用加载器重新加载）。
事件通知：缓存可能会提供一些事件监听器，让你在数据状态变动（如失效、刷新、移除）时进行一些额外操作。有的缓存还提供了对缓存数据本身的监视能力（Watch 功能）。
并发级别：对于通过分段加锁来实现的缓存（以 Guava Cache 为代表），往往会提供并发级别的设置。可以简单将其理解为缓存内部是使用多个 Map 来分段存储数据的，并发级别就用于计算出使用 Map 的数量。如果将这个参数设置过大，会引入更多的 Map，需要额外维护这些 Map 而导致更大的时间和空间上的开销；如果设置过小，又会导致在访问时产生线程阻塞，因为多个线程更新同一个 ConcurrentMap 的同一个值时会产生锁竞争。
容量控制：缓存通常都支持指定初始容量和最大容量，初始容量目的是减少扩容频率，这与 Map 接口本身的初始容量含义是一致的。最大容量类似于控制 Java 堆的-Xmx 参数，当缓存接近最大容量时，会自动清理掉低价值的数据。
引用方式：支持将数据设置为软引用或者弱引用，提供引用方式的设置是为了将缓存与 Java 虚拟机的垃圾收集机制联系起来。
统计信息：提供诸如缓存命中率、平均加载时间、自动回收计数等统计。
持久化：支持将缓存的内容存储到数据库或者磁盘中，进程内缓存提供持久化功能的作用不是太大，但分布式缓存大多都会考虑提供持久化功能。

几款主流进程内缓存方案对比结果如下图：

4.分布式缓存

复制式缓存：复制式缓存可以看作是“能够支持分布式的进程内缓存”，读取数据时直接从当前节点的进程内存中返回，理论上可以做到与进程内缓存一样高的读取性能；当数据发生变化时，就必须遵循复制协议，将变更同步到集群的每个节点中，复制性能随着节点的增加呈现平方级下降。

集中式缓存：集中式缓存是目前分布式缓存的主流形式，集中式缓存的读、写都需要网络访问，其好处是不会随着集群节点数量的增加而产生额外的负担，其坏处是读、写都不再可能达到进程内缓存那样的高性能。典型案例就是Redis。

分布式缓存与进程内缓存各有所长，也有各有局限，它们是互补而非竞争的关系，如有需要，完全可以同时把进程内缓存和分布式缓存互相搭配，构成透明多级缓存（Transparent Multilevel Cache，TMC），如下图所示：

6.2 缓存风险

1.缓存穿透

概念：缓存中没有，数据库中也没有，这种查询不存在数据的现象被称为缓存穿透。

解决方案：

对于业务逻辑本身就不能避免的缓存穿透，可以约定在一定时间内对返回为空的 Key 值依然进行缓存，使得在一段时间内缓存最多被穿透一次。
对于恶意攻击导致的缓存穿透，通常会在缓存之前设置一个布隆过滤器来解决。

2.缓存击穿

概念：如果缓存中某些热点数据忽然因某种原因失效了，譬如典型地由于超期而失效，请求未能命中缓存，都到达真实数据源中去，导致其压力剧增，这种现象被称为缓存击穿。

解决方案：

加锁同步，以请求该数据的 Key 值为锁，使得只有第一个请求可以流入到真实的数据源中，其他线程采取阻塞或重试策略。如果是进程内缓存出现问题，施加普通互斥锁即可，如果是分布式缓存中出现的问题，就施加分布式锁，这样数据源就不会同时收到大量针对同一个数据的请求了。
热点数据由代码来手动管理，例如分散缓存失效时间等（设置不同失效时间+随机数）。

3.缓存雪崩

概念：缓存击穿是针对单个热点数据失效，缓存雪崩是大批量缓存数据失效给数据源带来压力。

解决方案：

提升缓存系统可用性，建设分布式缓存的集群。
启用透明多级缓存，各个服务节点一级缓存中的数据通常会具有不一样的加载时间，也就分散了它们的过期时间。
将缓存的生存期从固定时间改为一个时间段内的随机时间，譬如原本是一个小时过期，那可以缓存不同数据时，设置生存期为 55 分钟到 65 分钟之间的某个随机时间。