通过数据层缓存提高 SOA 性能
面向服务的架构
通过数据层缓存提高 SOA 性能 作者：Kiran Dattani、Milind Pandit、Markus Zirn
将高性能注入数据服务
文章系列的一部分。
2010 年 2 月发布 下载
简介 面向服务的架构 (SOA) 正在改变应用程序开发和集成的理念。Web 服务标准使人们可以更容易地重用现有的业务逻辑，而不必考虑业务逻辑中实现的具体技术。通过组合流程，BPEL 和其他编排标准可以很容易地将这些服务整合在一起。因此，SOA 提供了更容易访问信息和组合信息的方法。 这带来了很大的好处，显著提高了敏捷性并增强了生产效率，所有这一切都归功于跨现有单体应用程序的互操作性得以提高。同时，SOA 还提升了 IT 的水平，因为业务用户有了更高的期望。现在，业务用户非常习惯使用消费型 Internet 应用程序以及由 Google、Yahoo 及其他公司提供的混搭程序，因此他们也要求自己的企业系统能提供类似的功能。SOA 可以帮助实现这些混搭程序。 这一积极进步的不利之处体现在性能方面。性能/可伸缩性问题已经上升为构建 SOA 应用程序时最令人担忧的问题之一。这种担忧并不奇怪。SOA 组合应用程序的结果显示在用户界面中，因此受可接受的响应时间的制约。用户通常认为超出 5 秒钟才显示的结果无法使用。对在线零售业务的调查显示，只要响应时间超过一秒钟，购物者就会放弃。因为 SOA 采用的是详细 XML（可扩展标记语言）格式，因此在调用 Web 服务时就需要转换数据（编组和取消编组），这就会产生开销。这一抽象加重了 SOA 应用程序性能上的负担。 业务流程中的服务越多，业务流程就越脆弱。如果一个业务流程依赖六个数据服务，每个服务的正常运行时间达到 99％，则业务流程本身的停机时间可能高达 6％。这相当于每年多达 525 小时的意外停机时间。问题并非仅仅如此。尽管数据服务设计为集中数据访问，但如果多个业务流程依赖同一组数据服务，就会出现可伸缩性问题。很重要的一点是，如果强制要求 IT 满足严格的 SLA 协议，那么构建可在所有 RASP 级别执行的 SOA 应用程序就变得极为重要。但是，在数据层构建可伸缩的数据访问存储的最好方法是什么呢？使用户应用程序（进而使业务流程）能够快速访问通常存储在数据库中的数据的最好方法是什么呢？ 在本文中，我们将讨论中间层缓存策略如何将高性能作为 SOA 的一部分注入数据服务。我们还将介绍一个大型制药公司结合使用 Oracle Coherence 网格解决方案和 Oracle SOA Suite 提高组合应用程序性能的方法。 SOA 缓存策略 任何 SOA 应用程序的性能都与它检索底层数据所需的时间直接相关。SOA 中的数据一般分为两类：
服务状态 & 这类数据与业务流程/服务的当前状态有关，即，当前流程实例此时位于何处，哪些流程处于活动状态，哪些流程已关闭，哪些流程被中止，等等。这类数据特别适用于长期运行的业务流程，通常存储在数据库中以实现与计算机故障的隔离。 服务结果 & 这类数据是由业务流程/数据服务交付回表示层的。通常，这类数据具有持久性并存储在后端数据库和数据仓库中。
缓存在提高访问服务状态/结果数据的速度方面可发挥非常重要的作用。缓存用于最大限度地减少使用缓存和底层数据提供程序的服务间的数据流量和延迟。与所有缓存解决方案一样，为业务服务设计的缓存方案也必须考虑以下问题：需要多长时间更新一次缓存的数据，数据是特定于用户的还是应用程序级的，使用什么机制来指示缓存需要更新，等等。 可能缓存两种类型的数据：服务状态和服务结果。
服务状态缓存允许一个业务流程中的多个服务共享内存中的服务状态数据。 服务结果缓存允许您缓存来自经常访问的业务服务或数据服务的结果。
图 1：SOA 组合应用程序可通过缓存数据服务和业务服务数据来提高性能 图 2 说明了如何通过实现两层缓存来构建组合 SOA 应用程序以提高性能：
上面的缓存层缓存业务服务状态及业务服务结果（即来自数据服务层的结果） 下面的缓存层依次缓存数据服务状态（如果需要）以及来自底层数据库和应用程序的应用程序数据。
我们来了解一下数据服务层的工作原理。基本思想是：在访问数据源之前先访问缓存，如果在缓存中找到目标数据，则无需访问数据源，否则，访问数据源，然后添加一个缓存更新。首次调用一个服务时，结果被缓存并送达给使用者。以后再调用时，应用程序逻辑首先查找缓存，如果在缓存中找到目标数据，则直接从缓存中检索数据。这种技术被称为预留缓存 (cache-aside)。
图 2：预留缓存架构可避免开销较大的数据库访问
现在数据位于中间层的内存中，数据访问速度比以往快得多，可实现更智能的服务且响应时间更短。基本上来说，以下问题的主要目标是尽可能多地避免会导致性能下降的数据库访问：&这些信息必须是实时的吗？还是近乎实时就足够了？&如果短时间内对一个服务的多次调用可能返回同一结果，则将这一需求放宽为由缓存提供近乎实时的数据将显著增强性能。 预留缓存是一个重要的性能增强策略，专门针对主要从多个不同后端源读取数据的 SOA 应用程序。一个典型用例是汇集一个跨多个数据存储的全方位客户视图。 预留缓存在旅游业中很常用，例如，预订数据近乎实时地存储在缓存中。如果每次浏览酒店床位或机票时都访问数据库，则可能会转化为可伸缩性问题。有时，这甚至需要查找第三方系统，每次查找都会产生费用。因此，大多数情况下都是浏览由缓存提供的近乎实时的旅行数据。您可以使用同样的方法来加快您 SOA 应用程序的速度。 提供全方位的客户视图 一个非常大型的以研究为基础的制药公司曾经面临着客户信息遍布多个数据存储分布的挑战。业务方面的地域扩张、兼并和收购已经使其添加了额外的后端系统。客户信息位于事务性 CRM 和 ERP 系统、主数据管理存储和业务智能数据仓库中。这种环境很难提供一个反映特定客户以往所有可用交际信息的全方位视图。因此，该公司的销售团队需要为获得有关客户（即医生）的最新信息不断努力。跨多个数据源汇总和筛选任何特定医生的信息列表也构成了巨大挑战。 各地的销售人员都需要实时访问客户信息，这使得问题进一步加剧。试想一名销售代表正在与一名医生交谈，必须根据该医生的专长、研究课题和购买模式推荐新产品。缺少这些信息可能妨碍交流的效果，也可能导致错过追加销售/交叉销售的机会。因此，有必要实现一种依托移动设备为公司的销售团队提供实时体验的新解决方案。 这家制药公司很快意识到，它必须使用基于 SOA 和 Web 2.0 的多渠道解决方案表示层构建一个敏捷的、完全可配置的数据集成解决方案，以便提供一个医疗保健提供程序的全方位视图，从而可以跨医疗保健项目管理 (HCPM)、基层医疗个案管理 (PCCM)、市场营销/活动管理应用程序 (UNICA) 和 CRM (Siebel)、Finance (Oracle e-Business Suite)、主数据管理 (Siperian) 和其他一些数据源成功搜索客户。 结合使用 Oracle SOA Suite 和 Oracle Coherence 的解决方案 这个解决方案的架构支持构建&获取客户活动&的组合应用程序，它将提供以下特性：
从多个数据源并发启动数据操作和检索数据 根据搜索条件返回一个候选客户列表 从候选客户列表中选择一个客户，然后跨多个数据源（Betsy、USDW 和 PubMed）返回特定于该候选客户的一组经过整合和筛选的活动信息 选择一个客户活动以查看活动的详细信息并返回特定于该客户的活动信息的细节 根据用户的权利限制用户对数据的可见性（活动、渠道和地区范围） 以语音方式返回匹配数据。
图 3：显示整合的客户信息的 GCA 组合应用程序 这家制药公司选择 Oracle SOA Suite 用于流程和数据集成，选择 Microsoft SharePoint 来提供 Web 2.0 层，以便向销售代表提供最终信息。 该公司还决定采用缓存策略来提升 SOA 数据服务的性能。但是，该解决方案必须能够满足以下三个重要缓存需求：
该解决方案必须能够承载可轻易超过一个系统的可用内存大小的数据服务缓存大小 考虑到会在全球范围逐渐采用的预期，该解决方案必须能够通过向分布式缓存添加服务器进行线性扩展 该解决方案必须以尽可能最高效的方式将公司 SOA 中间层中一组现有的商用服务器用于缓存。
总之，公司需要一个可将多台异构服务器上可用的 RAM 内存组合到一个分布式共享内存池中的解决方案。根据这些要求，公司选择了 Oracle Coherence 将服务数据分布在多台异构服务器中，并且跨集群缓存的所有节点对这些数据进行协调。
图 4：结合使用 Oracle SOA Suite 和 Oracle Coherence 的&获取客户活动 (GCA)&组合应用程序 GCA 组合应用程序通过以下流程提供有关特定客户活动的重要信息：
Oracle BPEL PM 编排业务服务（GetCustomer Spain、GetCustomer Germany 等） 这些业务服务调用 Oracle ESB 数据服务（getActivities、按区域的 getCustomers、按应用程序的 getCustomeractivity） 数据服务依次从相关的数据源（Siebel、UNICA、Siperian 等）提取所需的数据（通过安全和治理层），然后将数据返回给 Oracle BPEL PM 最后，Oracle BPEL PM 在 Sharepoint 门户中将结果显示给销售代表。
图 5：GetCustomers (Germany) 流程 向销售代表的 PDA 传送数据的速度取决于数据服务从底层数据层检索数据的速度。下面，我们来了解一下 Oracle Coherence 在该流程中扮演的角色。 BPEL & Coherence 集成架构 在 GCA 组合应用程序内部，Oracle Coherence 用于缓存数据服务结果数据。因为这些数据不经常变化，因此 Oracle Coherence 从内存而不是通过数据库调用从数据源供应这些数据。
图 6：BPEL PM、Coherence 和 ESB 之间的交互 上面的图 6 说明了提取客户活动信息时 BPEL PM、Coherence 和 ESB 之间的顺序流。GetCustomer 是一个基于 BPEL 的业务服务。这种业务服务通常将调用 GetCustomerActivity 数据服务（位于 ESB 层），该数据服务再从底层数据服务提取所需的数据。 不过，由于使用了 Coherence 缓存来自 ESB 数据服务的结果数据，因此该序列稍有不同。首次调用 GetCustomer 服务时，缓存来自 GetCustomerActivity 的结果，同时 将结果送达使用者。以后再调用时，GetCustomer BPEL 服务首先查找缓存，如果在缓存中找到目标数据，则直接从缓存中检索数据。在中间层内存中缓存 CustomerActivity 数据提升了数据访问速度。 到底应该如何从 BPEL 使用 Coherence 这一 SOA 编排语言呢？因为该制药公司使用中间层缓存的目标是实现可伸缩的性能，所以架构不能影响到效率。Oracle Coherence 提供了一个 Java API；通过标准 Web 服务接口实现从 BPEL 到 Coherence 的本机服务调用是首选的方法。调用 Web 服务操作的性能开销比调用本机 Java 类的性能开销要大几个数量级。这是因为编组和取消编组 XML、处理 SOAP 信封等都是开销很大的操作。
图 7：使用 WSIF 绑定优化方法 到 Java 资源的本机连接性不是 BPEL 的标准特性，但是 Oracle BPEL Process Manager (PM) 提供了专用于此目的解决方案 & WebServices 调用框架（WSIF） & 无需修改或扩展 BPEL 代码。中详细介绍了如何结合使用 Oracle BPEL Process Manager 和 WSIF。在测试中，我们已经体验了利用 WSIF 绑定通过标准 Web 服务接口实现到 Oracle Coherence 的连接所带来的数量级的性能提高。 集成 Oracle BPEL PM 和 Oracle Coherence 现在，我们快速浏览一下 GetCustomer BPEL 流程。如下面的图 8 所示，该流程首先检查缓存（另请参见图 10 中的条件）。如果缓存为空，该流程调用底层数据服务，否则，从缓存返回结果。
图 8：BPEL PM 流程 (GetCustomer) 调用 Coherence 缓存 伙伴链接定义不同实体（在本例中为 Coherence Web 服务）如何与 BPEL 流程交互。每个伙伴链接与一个特定的 partnerLinkType 相关，以该 partnerLinkType 为特征。（参见图 9。） InvokePagingCacheService 内部调用 Coherence WSIF Web 服务。ParnerLinkType 在 WSDL 文件中定义。
图 9：PagingCacheService 伙伴链接 下面的图 10 说明了如何根据从 PagingCacheService 检索到的缓存值定义条件表达式。
图 10：检查缓存是否为空的条件 既然我们已经了解了 BPEL 流程如何调用 Coherence 缓存服务，下面我们看一下如何创建这个缓存服务。简单说，该流程包括创建一个将从缓存读取/写入缓存的 Java 应用程序。然后，我们将这个 Java 应用程序封装为一个从 BPEL 流程调用的 Web 服务。 从实现的角度看，以下步骤是必须的：
为请求和响应创建模式并为缓存服务创建 WSDL 使用模式创建 Java 对象 为缓存服务创建 Java 实现类 创建 coherence_config.xml 以配置 coherence 将 coherence.jar 和 tangosol.jar 打包到 BPEL Jar 中 部署并验证流程
1. 为请求和响应创建模式并为缓存服务创建 WSDL 由于 BPEL 流程与其他 Web 服务通信，因此它在很大程度上依赖于组合 Web 服务所调用的 Web 服务的 WSDL 描述。 根据不同的客户模式，必须准备搜索请求模式和响应模式。例如，一个客户搜索请求将包含名字、姓氏、搜索类型等。响应将包含一个客户列表，其中包括每个客户的地址、订购的产品等。
图 11：Coherence 缓存服务的 WSDL
2. 使用模式创建 Java 对象 使用模式（SOA Suite 捆绑的实用程序）创建 Java 类，然后进行编译 3. 创建调用 Coherence 的 Java 实现类 这是 BPEL PM 服务将通过 WSIF 接口调用的 Java 应用程序。下面是读取 Coherence 缓存并向 BPEL PM 服务返回结果所需的 Java 代码的快照。相关的部分高亮显示为黄色。
public class CacheServiceImpl {
static NamedCache _customerQueryResultCache=
/** Read coherence configuration file to initialize parameters like cache
expiration, eviction policy **/
System.setProperty(&tangosol.coherence.cacheconfig&, &coherence_config.xml&);
Thread thread = Thread.currentThread();
ClassLoader loaderPrev = thread.getContextClassLoader();
{
thread.setContextClassLoader(com.tangosol.net.NamedCache.class.getClassLoader());
/** An instance of a cache is created from the CacheFactory class.
instance, called CustomerQueryResultCache, is created using the getCache()
method of the CacheFactory class. Cache name GetCustomer.cache is mapped
to a distributed caching scheme.**/
_customerQueryResultCache = CacheFactory.getCache(&GetCustomer.cache&);
System.out.println(&cache: &+_customerQueryResultCache);
Thread.currentThread().setContextClassLoader(loaderPrev);
public CacheReadResponseType cacheRead(CacheReadRequestType input) throws
ApplicationFault, SystemFault, BusinessFault
{
String key = input.getInput().getKey();
CacheReadResponseType cacheResponseType =
/** A CustomerQueryResultCache is a java.util.Map that holds resources
shared across nodes in a cluster. Use the key (in this case customer id)
to retrieve the cache entry using the get() method) **/
CustomerQueryResultSet customerQueryResultSet =
(CustomerQueryResultSet)_customerQueryResultCache.get(key);
System.out.println(& Requested key Id is : & + key);
System.out.println(& Read from cache is : & + customerQueryResultSet);
cacheResponseType = CacheReadResponseTypeFactory.createFacade();
CacheReadResponse cacheResp =
CacheReadResponseFactory.createFacade();
if (customerQueryResultSet != null)
cacheResp.setCustomerQueryResultSet(customerQueryResultSet);
cacheResponseType.setResult(cacheResp);
return cacheResponseT
4. 创建 coherence_config.xml 以配置 coherence 现在，我们设置缓存配置，包括逐出策略和缓存过期。我们将使用过期设置为 0 的分布式缓存，这样缓存数据永不会过期。否则，数据库中的数据变化时我们将更新缓存。
&distributed-scheme&
&scheme-name&default-distributed&/scheme-name&
&service-name&DistributedCache&/service-name&
&backing-map-scheme&
&local-scheme&
&scheme-ref&default-eviction&/scheme-ref&
&!-- Eviction policy set to LRU, so that least recently used cache
data is evicted to make room for new cache --&
&eviction-policy&LRU&/eviction-policy&
&high-units&0&/high-units&
&!--Expiry set to 0, so that the cached data never expires. --&
&expiry-delay&0&/expiry-delay&
&/local-scheme&
&/backing-map-scheme&
&/distributed-scheme&
该 coherence_config.xml 文件应放在一个 jar 文件中并添加到项目库。（参见图 9。） 5. 将 coherence.jar 和 tangosol.jar 打包到 BPEL Jar 中 Coherence.jar 和 tangosol.jar 现在已经添加到项目库中，项目库是与 BPEL Jar 一起部署的，因此它位于 BPEL-INF/lib 中。（参见图 12。）
图 12：Coherence jar 文件与 BPEL Jar 文件一起部署
6. 部署并验证流程 流程一旦部署完成并进行了首次调用，流程将创建 cacheserver 并创建缓存 getCustomer.cache。此缓存映射到分布式缓存模式。从这个缓存实例读取/写入数据。 总结 通过使用 Oracle Coherence 实现中间层缓存，我们的组合应用程序获得了巨大的好处：
图 13：Coherence 缓存读取速度提高了 30-50％
& 内部性能测试（参见图 13）显示来自缓存数据的响应速度提高了 30％ 至 50％。此外，由于数据更接近应用服务器，因此容易获得并且免除了对数据库的访问。 增加了 GCA 组合应用程序的容错能力。在任何单个计算机或服务器发生故障时，数据始终可用。 提高了服务器硬件利用率，从而更高效地使用服务器容量。 减少了数据服务调用期间的数据编组/取消编组。
正如本文所演示的，使用复杂的中间层缓存解决方案可以提升 SOA 应用程序的性能。一个设计良好的缓存产品可以将复杂的分布式缓存和集群缓存机制隐藏起来，使 SOA 架构师/开发人员将注意力放在利用缓存上。这将带来额外的好处，包括由缓存冗余带来的可靠性提高，以及由无共享架构带来的线性缓存可伸缩性。
Kiran Dattani 是一家大型制药公司架构建设的财务和采购总监，他负责全球架构和企业集成项目。他还是公认的生命科学和制造行业的企业集成和供应链方面的专家，也是一位造诣颇深的演讲者。
Milind Pandit 是 Oracle Consulting Services 的 SOA 架构师，他负责协助客户部署基于 SOA 的架构。他在企业应用程序集成、J2EE 和面向对象的分析与设计方面的软件设计、开发和实现方面拥有 11 年的经验。
Markus Zirn 是 Oracle 融合中间件产品管理副总裁。他是《》的编辑，还撰写了几篇有关 SOA 及相关主题的，经常在行业领先的会议和分析师大会上发表演讲。
关于甲骨文
Integrated Cloud Applications & Platform Services2010年5月 Java大版内专家分月排行榜第一2010年2月 Java大版内专家分月排行榜第一2010年1月 Java大版内专家分月排行榜第一2010年1月 Oracle大版内专家分月排行榜第一2009年12月 Java大版内专家分月排行榜第一2009年12月 Oracle大版内专家分月排行榜第一
2010年2月 Oracle大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。缓存、缓存算法和缓存框架简介 - 文章 - 伯乐在线
& 缓存、缓存算法和缓存框架简介
我们都听过 cache，当你问他们是什么是缓存的时候，他们会给你一个完美的答案，可是他们不知道缓存是怎么构建的，或者没有告诉你应该采用什么标准去选择缓存框架。在这边文章，我们会去讨论缓存，缓存算法，缓存框架以及哪个缓存框架会更好。
“缓存就是存贮数据（使用频繁的数据）的临时地方，因为取原始数据的代价太大了，所以我可以取得快一些。”
这就是 programmer one （programmer one 是一个面试者）在面试中的回答（一个月前，他向公司提交了简历，想要应聘要求在缓存，缓存框架，大规模数据操作有着丰富经验的 java 开发职位）。
programmer one 通过 hash table 实现了他自己的缓存，但是他知道的只是他的缓存和他那存储着150条记录的 hash table，这就是他认为的大规模数据（缓存 = hashtable，只需要在 hash table 查找就好了），所以，让我们来看看面试的过程吧。
面试官：你选择的缓存方案，是基于什么标准的？
programmer one：呃，（想了5分钟）嗯，基于，基于，基于数据（咳嗽……）
面试官：excese me ! 能不能重复一下？
programmer one：数据？！
面试官：好的。说说几种缓存算法以及它们的作用
programmer one：（凝视着面试官，脸上露出了很奇怪的表情，没有人知道原来人类可以做出这种表情
面试官：好吧，那我换个说法，当缓存达到容量时，会怎么做？
programmer one：容量？嗯（思考……hash table 的容量时没有限制的，我能任意增加条目，它会自动扩充容量的）（这是 programmer one 的想法，但是他没有说出来）
面试官对 programmer one 表示感谢（面试过程持续了10分钟），之后一个女士走过来说：谢谢你的时间，我们会给你打电话的，祝你好心情。这是 programmer one 最糟糕的面试（他没有看到招聘对求职者有丰富的缓存经验背景要求，实际上，他只看到了丰厚的报酬
programmer one 离开之后，他想要知道这个面试者说的问题和答案，所以他上网去查，programmer one 对缓存一无所知，除了：当我需要缓存的时候，我就会用 hash table。
在他使用了他最爱的搜索引擎搜索之后，他找到了一篇很不错的关于缓存文章，并且开始去阅读……
为什么我们需要缓存？
很久很久以前，在还没有缓存的时候……用户经常是去请求一个对象，而这个对象是从数据库去取，然后，这个对象变得越来越大，这个用户每次的请求时间也越来越长了，这也把数据库弄得很痛苦，他无时不刻不在工作。所以，这个事情就把用户和数据库弄得很生气，接着就有可能发生下面两件事情：
１.用户很烦，在抱怨，甚至不去用这个应用了（这是大多数情况下都会发生的）
２.数据库为打包回家，离开这个应用，然后，就出现了大麻烦（没地方去存储数据了）（发生在极少数情况下）
上帝派来了缓存
在几年之后，IBM（60年代）的研究人员引进了一个新概念，它叫“缓存”。
什么是缓存？
正如开篇所讲，缓存是“存贮数据（使用频繁的数据）的临时地方，因为取原始数据的代价太大了，所以我可以取得快一些。”
缓存可以认为是数据的池，这些数据是从数据库里的真实数据复制出来的，并且为了能别取回，被标上了标签（键 ID）。太棒了
programmer one 已经知道这点了，但是他还不知道下面的缓存术语。
当客户发起一个请求（我们说他想要查看一个产品信息），我们的应用接受这个请求，并且如果是在第一次检查缓存的时候，需要去数据库读取产品信息。
如果在缓存中，一个条目通过一个标记被找到了，这个条目就会被使用、我们就叫它缓存命中。所以，命中率也就不难理解了。
Cache Miss：
但是这里需要注意两点：
１.　如果还有缓存的空间，那么，没有命中的对象会被存储到缓存中来。
２.　如果缓存满了，而又没有命中缓存，那么就会按照某一种策略，把缓存中的旧对象踢出，而把新的对象加入缓存池。而这些策略统称为替代策略（缓存算法），这些策略会决定到底应该提出哪些对象。
存储成本：
当没有命中时，我们会从数据库取出数据，然后放入缓存。而把这个数据放入缓存所需要的时间和空间，就是存储成本。
索引成本：
和存储成本相仿。
当存在缓存中的数据需要更新时，就意味着缓存中的这个数据失效了。
替代策略：
当缓存没有命中时，并且缓存容量已经满了，就需要在缓存中踢出一个老的条目，加入一条新的条目，而到底应该踢出什么条目，就由替代策略决定。
最优替代策略：
最优的替代策略就是想把缓存中最没用的条目给踢出去，但是未来是不能够被预知的，所以这种策略是不可能实现的。但是有很多策略，都是朝着这个目前去努力。
Java 街恶梦：
当 programmer one 在读这篇文章的时候，他睡着了，并且做了个恶梦（每个人都有做恶梦的时候）。
programmer one：nihahha，我要把你弄失效！（疯狂的状态）
缓存对象：别别，让我活着，他们还需要我，我还有孩子。
programmer one：每个缓存对象在失效之前都会那样说。你从什么时候开始有孩子的？不用担心，现在就永远消失吧！
哈哈哈哈哈……programmer one 恐怖的笑着，但是警笛打破了沉静，警察把 programmer one 抓了起来，并且控告他杀死了（失效）一个仍需被使用的缓存对象，他被押到了监狱。
programmer one 突然醒了，他被吓到了，浑身是汗，他开始环顾四周，发现这确实是个梦，然后赶紧继续阅读这篇文章，努力的消除自己的恐慌。
在programmer one 醒来之后，他又开始阅读文章了。
没有人能说清哪种缓存算法优于其他的缓存算法
Least Frequently Used（LFU）：
大家好，我是 LFU，我会计算为每个缓存对象计算他们被使用的频率。我会把最不常用的缓存对象踢走。
Least Recently User（LRU）：
我是 LRU 缓存算法，我把最近最少使用的缓存对象给踢走。
我总是需要去了解在什么时候，用了哪个缓存对象。如果有人想要了解我为什么总能把最近最少使用的对象踢掉，是非常困难的。
浏览器就是使用了我（LRU）作为缓存算法。新的对象会被放在缓存的顶部，当缓存达到了容量极限，我会把底部的对象踢走，而技巧就是：我会把最新被访问的缓存对象，放到缓存池的顶部。
所以，经常被读取的缓存对象就会一直呆在缓存池中。有两种方法可以实现我，array 或者是 linked list。
我的速度很快，我也可以被数据访问模式适配。我有一个大家庭，他们都可以完善我，甚至做的比我更好（我确实有时会嫉妒，但是没关系）。我家庭的一些成员包括 LRU2 和 2Q，他们就是为了完善 LRU 而存在的。
Least Recently Used 2（LRU2）：
我是 Least Recently Used 2，有人叫我最近最少使用 twice，我更喜欢这个叫法。我会把被两次访问过的对象放入缓存池，当缓存池满了之后，我会把有两次最少使用的缓存对象踢走。因为需要跟踪对象2次，访问负载就会随着缓存池的增加而增加。如果把我用在大容量的缓存池中，就会有问题。另外，我还需要跟踪那么不在缓存的对象，因为他们还没有被第二次读取。我比LRU好，而且是 adoptive to access 模式 。
Two Queues（2Q）：
我是 Two Queues；我把被访问的数据放到 LRU 的缓存中，如果这个对象再一次被访问，我就把他转移到第二个、更大的 LRU 缓存。
我踢走缓存对象是为了保持第一个缓存池是第二个缓存池的1/3。当缓存的访问负载是固定的时候，把 LRU 换成 LRU2，就比增加缓存的容量更好。这种机制使得我比 LRU2 更好，我也是 LRU 家族中的一员，而且是 adoptive to access 模式 。
Adaptive Replacement Cache（ARC）：
我是 ARC，有人说我是介于 LRU 和 LFU 之间，为了提高效果，我是由2个 LRU 组成，第一个，也就是 L1，包含的条目是最近只被使用过一次的，而第二个 LRU，也就是 L2，包含的是最近被使用过两次的条目。因此， L1 放的是新的对象，而 L2 放的是常用的对象。所以，别人才会认为我是介于 LRU 和 LFU 之间的，不过没关系，我不介意。
我被认为是性能最好的缓存算法之一，能够自调，并且是低负载的。我也保存着历史对象，这样，我就可以记住那些被移除的对象，同时，也让我可以看到被移除的对象是否可以留下，取而代之的是踢走别的对象。我的记忆力很差，但是我很快，适用性也强。
Most Recently Used（MRU）：
我是 MRU，和 LRU 是对应的。我会移除最近最多被使用的对象，你一定会问我为什么。好吧，让我告诉你，当一次访问过来的时候，有些事情是无法预测的，并且在缓存系统中找出最少最近使用的对象是一项时间复杂度非常高的运算，这就是为什么我是最好的选择。
我是数据库内存缓存中是多么的常见！每当一次缓存记录的使用，我会把它放到栈的顶端。当栈满了的时候，你猜怎么着？我会把栈顶的对象给换成新进来的对象！
First in First out（FIFO）：
我是先进先出，我是一个低负载的算法，并且对缓存对象的管理要求不高。我通过一个队列去跟踪所有的缓存对象，最近最常用的缓存对象放在后面，而更早的缓存对象放在前面，当缓存容量满时，排在前面的缓存对象会被踢走，然后把新的缓存对象加进去。我很快，但是我并不适用。
Second Chance：
大家好，我是 second chance，我是通过 FIFO 修改而来的，被大家叫做 second chance 缓存算法，我比 FIFO 好的地方是我改善了 FIFO 的成本。我是 FIFO 一样也是在观察队列的前端，但是很FIFO的立刻踢出不同，我会检查即将要被踢出的对象有没有之前被使用过的标志（1一个 bit 表示），没有没有被使用过，我就把他踢出；否则，我会把这个标志位清除，然后把这个缓存对象当做新增缓存对象加入队列。你可以想象就这就像一个环队列。当我再一次在队头碰到这个对象时，由于他已经没有这个标志位了，所以我立刻就把他踢开了。我在速度上比 FIFO 快。
我是 Clock，一个更好的 FIFO，也比 second chance 更好。因为我不会像 second chance 那样把有标志的缓存对象放到队列的尾部，但是也可以达到 second chance 的效果。
我持有一个装有缓存对象的环形列表，头指针指向列表中最老的缓存对象。当缓存 miss 发生并且没有新的缓存空间时，我会问问指针指向的缓存对象的标志位去决定我应该怎么做。如果标志是0，我会直接用新的缓存对象替代这个缓存对象；如果标志位是1，我会把头指针递增，然后重复这个过程，知道新的缓存对象能够被放入。我比 second chance 更快。
Simple time-based：
我是 simple time-based 缓存算法，我通过绝对的时间周期去失效那些缓存对象。对于新增的对象，我会保存特定的时间。我很快，但是我并不适用。
Extended time-based expiration：
我是 extended time-based expiration 缓存算法，我是通过相对时间去失效缓存对象的；对于新增的缓存对象，我会保存特定的时间，比如是每5分钟，每天的12点。
Sliding time-based expiration：
我是 sliding time-based expiration，与前面不同的是，被我管理的缓存对象的生命起点是在这个缓存的最后被访问时间算起的。我很快，但是我也不太适用。
其他的缓存算法还考虑到了下面几点：
成本：如果缓存对象有不同的成本，应该把那些难以获得的对象保存下来。
容量：如果缓存对象有不同的大小，应该把那些大的缓存对象清除，这样就可以让更多的小缓存对象进来了。
时间：一些缓存还保存着缓存的过期时间。电脑会失效他们，因为他们已经过期了。
根据缓存对象的大小而不管其他的缓存算法可能是有必要的。
电子邮件！
在读完这篇文章之后，programmer one 想了一会儿，然后决定给作者发封邮件，他感觉作者的名字在哪听过，但是已经想不起来了。不管怎样，他还是把邮件发送出来了，他询问了作者在分布式环境中，缓存是怎么样工作的。
文章的作者收到了邮件，具有讽刺意味的是，这个作者就是面试 programmer one 的人
，作者回复了……
在这一部分中，我们来看看如何实现这些著名的缓存算法。以下的代码只是示例用的，如果你想自己实现缓存算法，可能自己还得加上一些额外的工作。
LeftOver 机制
在 programmer one 阅读了文章之后，他接着看了文章的评论，其中有一篇评论提到了 leftover 机制——random cache。
Random Cache
我是随机缓存，我随意的替换缓存实体，没人敢抱怨。你可以说那个被替换的实体很倒霉。通过这些行为，我随意的去处缓存实体。我比 FIFO 机制好，在某些情况下，我甚至比 LRU 好，但是，通常LRU都会比我好。
现在是评论时间
当 programmer one 继续阅读评论的时候，他发现有个评论非常有趣，这个评论实现了一些缓存算法，应该说这个评论做了一个链向评论者网站的链接，programmer one顺着链接到了那个网站，接着阅读。
看看缓存元素（缓存实体）
public class CacheElement
private Object objectV
private Object objectK
private int hitC　// getters and setters
public class CacheElement {&&&& private Object objectValue;&&&& private Object objectKey;&&&& private int index;&&&& private int hitCount;　// getters and setters }
这个缓存实体拥有缓存的key和value，这个实体的数据结构会被以下所有缓存算法用到。
缓存算法的公用代码
public final synchronized void addElement(Object key, Object value)
// get the entry from the table
obj = table.get(key);
// If we have the entry already in our table
// then get it and replace only its value.
obj = table.get(key);
if (obj != null)
element = (CacheElement)
element.setObjectValue(value);
element.setObjectKey(key);
12345678910111213141516171819
public final synchronized void addElement(Object key, Object value) {&&&& int index;&&&& Object obj;&&&& // get the entry from the table&&&& obj = table.get(key);&&&& // If we have the entry already in our table&&&& // then get it and replace only its value.&&&& obj = table.get(key);&&&&& if (obj != null)&&&& {&&&&&&&& CacheElement element;&&&&&&&& element = (CacheElement) obj;&&&&&&&& element.setObjectValue(value);&&&&&&&& element.setObjectKey(key);&&&&&&&& return;&&&& } ｝
上面的代码会被所有的缓存算法实现用到。这段代码是用来检查缓存元素是否在缓存中了，如果是，我们就替换它，但是如果我们找不到这个 key 对应的缓存，我们会怎么做呢？那我们就来深入的看看会发生什么吧！
今天的专题很特殊，因为我们有特殊的客人，事实上他们是我们想要听的与会者，但是首先，先介绍一下我们的客人：Random Cache，FIFO Cache。让我们从 Random Cache开始。
看看随机缓存的实现
public final synchronized void addElement(Object key, Object value)
obj = table.get(key);
if (obj != null)
CacheE// Just replace the value.
element = (CacheElement)
element.setObjectValue(value);
element.setObjectKey(key);
}// If we haven't filled the cache yet, put it at the end.
if (!isFull())
index = numE
else { // Otherwise, replace a random entry.
index = (int) (cache.length * random.nextFloat());
table.remove(cache[index].getObjectKey());
cache[index].setObjectValue(value);
cache[index].setObjectKey(key);
table.put(key, cache[index]);
1234567891011121314151617181920212223242526
public final synchronized void addElement(Object key, Object value) {&&&& int index;&&&& Object obj;&&&& obj = table.get(key);&&&& if (obj != null)&&&& {&&&&&&&& CacheElement element;// Just replace the value.&&&&&&&& element = (CacheElement) obj;&&&&&&&& element.setObjectValue(value);&&&&&&&& element.setObjectKey(key);&&&&&&&& return;&&&& }// If we haven't filled the cache yet, put it at the end.&&&& if (!isFull())&&&& {&&&&&&&& index = numEntries;&&&&&&&& ++numEntries;&&&& }&&&& else { // Otherwise, replace a random entry.&&&&&&&& index = (int) (cache.length * random.nextFloat());&&&&&&&& table.remove(cache[index].getObjectKey());&&&& }&&&& cache[index].setObjectValue(value);&&&& cache[index].setObjectKey(key);&&&& table.put(key, cache[index]); }
看看FIFO缓算法的实现
public final synchronized void addElement(Objectkey, Object value)
obj = table.get(key);
if (obj != null)
CacheE // Just replace the value.
element = (CacheElement)
element.setObjectValue(value);
element.setObjectKey(key);
// If we haven't filled the cache yet, put it at the end.
if (!isFull())
index = numE
else { // Otherwise, replace the current pointer,
// entry with the new one.
// in order to make Circular FIFO
if (++current &= cache.length)
current = 0;
table.remove(cache[index].getObjectKey());
cache[index].setObjectValue(value);
cache[index].setObjectKey(key);
table.put(key, cache[index]);
12345678910111213141516171819202122232425262728293031
public final synchronized void addElement(Objectkey, Object value) {&&&& int index;&&&& Object obj;&&&& obj = table.get(key);&&&& if (obj != null)&&&& {&&&&&&&& CacheElement element; // Just replace the value.&&&&&&&& element = (CacheElement) obj;&&&&&&&& element.setObjectValue(value);&&&&&&&& element.setObjectKey(key);&&&&&&&& return;&&&& }&&&& // If we haven't filled the cache yet, put it at the end.&&&& if (!isFull())&&&& {&&&&&&&& index = numEntries;&&&&&&&& ++numEntries;&&&& }&&&& else { // Otherwise, replace the current pointer,&&&&&&&&&&&&// entry with the new one.&&&&&&&& index = current;&&&&&&&& // in order to make Circular FIFO&&&&&&&& if (++current &= cache.length)&&&&&&&&&&&& current = 0;&&&&&&&& table.remove(cache[index].getObjectKey());&&&& }&&&& cache[index].setObjectValue(value);&&&& cache[index].setObjectKey(key);&&&& table.put(key, cache[index]); }
看看LFU缓存算法的实现
public synchronized Object getElement(Object key)
obj = table.get(key);
if (obj != null)
CacheElement element = (CacheElement)
element.setHitCount(element.getHitCount() + 1);
return element.getObjectValue();
public final synchronized void addElement(Object key, Object value)
obj = table.get(key);
if (obj != null)
CacheE // Just replace the value.
element = (CacheElement)
element.setObjectValue(value);
element.setObjectKey(key);
if (!isFull())
index = numE
CacheElement element = removeLfuElement();
index = element.getIndex();
table.remove(element.getObjectKey());
cache[index].setObjectValue(value);
cache[index].setObjectKey(key);
cache[index].setIndex(index);
table.put(key, cache[index]);
public CacheElement removeLfuElement()
CacheElement[] elements = getElementsFromTable();
CacheElement leastElement = leastHit(elements);
return leastE
public static CacheElement leastHit(CacheElement[] elements)
CacheElement lowestElement =
for (int i = 0; i & elements. i++)
CacheElement element = elements[i];
if (lowestElement == null)
lowestElement =
if (element.getHitCount() & lowestElement.getHitCount())
lowestElement =
return lowestE
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
public synchronized Object getElement(Object key) {&&&& Object obj;&&&& obj = table.get(key);&&&& if (obj != null)&&&& {&&&&&&&& CacheElement element = (CacheElement) obj;&&&&&&&& element.setHitCount(element.getHitCount() + 1);&&&&&&&& return element.getObjectValue();&&&& }&&&& return null; } public final synchronized void addElement(Object key, Object value) {&&&& Object obj;&&&& obj = table.get(key);&&&& if (obj != null)&&&& {&&&&&&&& CacheElement element; // Just replace the value.&&&&&&&& element = (CacheElement) obj;&&&&&&&& element.setObjectValue(value);&&&&&&&& element.setObjectKey(key);&&&&&&&& return;&&&& }&&&& if (!isFull())&&&& {&&&&&&&& index = numEntries;&&&&&&&& ++numEntries;&&&& }&&&& else&&&& {&&&&&&&& CacheElement element = removeLfuElement();&&&&&&&& index = element.getIndex();&&&&&&&& table.remove(element.getObjectKey());&&&& }&&&& cache[index].setObjectValue(value);&&&& cache[index].setObjectKey(key);&&&& cache[index].setIndex(index);&&&& table.put(key, cache[index]); } public CacheElement removeLfuElement() {&&&& CacheElement[] elements = getElementsFromTable();&&&& CacheElement leastElement = leastHit(elements);&&&& return leastElement; } public static CacheElement leastHit(CacheElement[] elements) {&&&& CacheElement lowestElement = null;&&&& for (int i = 0; i & elements.length; i++)&&&& {&&&&&&&& CacheElement element = elements[i];&&&&&&&& if (lowestElement == null)&&&&&&&& {&&&&&&&&&&&& lowestElement = element;&&&&&&&& }&&&&&&&& else {&&&&&&&&&&&& if (element.getHitCount() & lowestElement.getHitCount())&&&&&&&&&&&& {&&&&&&&&&&&&&&&& lowestElement = element;&&&&&&&&&&&& }&&&&&&&& }&&&& }&&&& return lowestElement; }
今天的专题很特殊，因为我们有特殊的客人，事实上他们是我们想要听的与会者，但是首先，先介绍一下我们的客人：Random Cache, FIFO Cache。让我们从 Random Cache开始。
最重点的代码，就应该是 leastHit 这个方法，这段代码就是把
hitCount 最低的元素找出来，然后删除，给新进的缓存元素留位置。
看看LRU缓存算法实现
private void moveToFront(int index)
int nextIndex, prevI
if(head != index)
nextIndex = next[index];
prevIndex = prev[index];
// Only the head has a prev entry that is an invalid index
// so we don't check.
next[prevIndex] = nextI
// Make sure index is valid. If it isn't, we're at the tail
// and don't set prev[next].
if(nextIndex &= 0)
prev[nextIndex] = prevI
tail = prevI
prev[index] = -1;
next[index] =
prev[head] =
public final synchronized void addElement(Object key, Object value)
obj = table.get(key);
if(obj != null)
// Just replace the value, but move it to the front.
entry = (CacheElement)
entry.setObjectValue(value);
entry.setObjectKey(key);
moveToFront(entry.getIndex());
// If we haven't filled the cache yet, place in next available
// spot and move to front.
if(!isFull())
if(_numEntries & 0)
prev[_numEntries] =
next[_numEntries] = -1;
moveToFront(numEntries);
else { // We replace the tail of the list.
table.remove(cache[tail].getObjectKey());
moveToFront(tail);
cache[head].setObjectValue(value);
cache[head].setObjectKey(key);
table.put(key, cache[head]);
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
private void moveToFront(int index) {&&&& int nextIndex, prevIndex;&&&& if(head != index)&&&& {&&&&&&&& nextIndex = next[index];&&&&&&&& prevIndex = prev[index];&&&&&&&& // Only the head has a prev entry that is an invalid index&&&&&&&& // so we don't check.&&&&&&&& next[prevIndex] = nextIndex;&&&&&&&& // Make sure index is valid. If it isn't, we're at the tail&&&&&&&& // and don't set prev[next].&&&&&&&& if(nextIndex &= 0)&&&&&&&&&&&& prev[nextIndex] = prevIndex;&&&&&&&& else&&&&&&&&&&&& tail = prevIndex;&&&&&&&& prev[index] = -1;&&&&&&&& next[index] = head;&&&&&&&& prev[head] = index;&&&&&&&& head = index;&&&& } } public final synchronized void addElement(Object key, Object value) {&&&& int index;Object obj;&&&& obj = table.get(key);&&&& if(obj != null)&&&& {&&&&&&&& CacheElement entry;&&&&&&&& // Just replace the value, but move it to the front.&&&&&&&& entry = (CacheElement)obj;&&&&&&&& entry.setObjectValue(value);&&&&&&&& entry.setObjectKey(key);&&&&&&&& moveToFront(entry.getIndex());&&&&&&&& return;&&&& }&&&& // If we haven't filled the cache yet, place in next available&&&& // spot and move to front.&&&& if(!isFull())&&&& {&&&&&&&& if(_numEntries & 0)&&&&&&&& {&&&&&&&&&&&& prev[_numEntries] = tail;&&&&&&&&&&&& next[_numEntries] = -1;&&&&&&&&&&&& moveToFront(numEntries);&&&&&&&& }&&&&&&&& ++numEntries;&&&& }&&&& else { // We replace the tail of the list.&&&&&&&& table.remove(cache[tail].getObjectKey());&&&&&&&& moveToFront(tail);&&&& }&&&& cache[head].setObjectValue(value);&&&& cache[head].setObjectKey(key);&&&& table.put(key, cache[head]); }
这段代码的逻辑如 LRU算法 的描述一样，把再次用到的缓存提取到最前面，而每次删除的都是最后面的元素。
我们已经看到 LFU缓存算法 和 LRU缓存算法的实现方式，至于如何实现，采用数组还是 LinkedHashMap，都由你决定，不够我一般是小的缓存容量用数组，大的用 LinkedHashMap。
可能感兴趣的话题
内容很翔实 很不错！ 存在的问题是，既然是译文，就应该只翻译 不修改内容，此译文比原文添加了具体的代码实现，删减的关于分布式缓存的部分。(撇嘴)
关于伯乐在线博客
在这个信息爆炸的时代，人们已然被大量、快速并且简短的信息所包围。然而，我们相信：过多“快餐”式的阅读只会令人“虚胖”，缺乏实质的内涵。伯乐在线内容团队正试图以我们微薄的力量，把优秀的原创文章和译文分享给读者，为“快餐”添加一些“营养”元素。
新浪微博：
推荐微信号
（加好友请注明来意）
– 好的话题、有启发的回复、值得信赖的圈子
– 分享和发现有价值的内容与观点
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 翻译传播优秀的外文文章
– 国内外的精选文章
– UI,网页，交互和用户体验
– 专注iOS技术分享
– 专注Android技术分享
– JavaScript, HTML5, CSS
– 专注Java技术分享
– 专注Python技术分享
& 2018 伯乐在线