云计算开发之CoT：云环境的去中心化分布式弹性缓存方案

摘要

分布式缓存被广泛应用于以十亿用户规模服务于社交网络和网络应用。然而，典型的工作负载偏差会导致缓存服务器之间的负载不平衡。这种负载不平衡降低了请求吞吐量，并增加了请求延迟，从而降低了缓存的好处。最近的研究从理论上表明，前端一个小的完美缓存对分布式缓存的负载平衡有很大的影响。然而，确定在前端服务器上实现近乎完美的缓存的缓存大小和替换策略是一项挑战，特别是对于动态变化和不断变化的工作负载。这篇文章介绍了Cache on Track（CoT），这是一个用于云环境的分散、弹性和预测性的缓存框架。CoT是以下问题的答案：在缓存服务器端实现负载平衡所需的前端缓存大小是多少？CoT提出了一个新的缓存替换策略，专门为服务于倾斜工作负载的小型前端缓存量身定制。前端服务器使用重击跟踪算法来连续跟踪top-k热键。CoT从跟踪的密钥中动态缓存最热的C密钥。此外，每个前端服务器独立地监视其对缓存服务器负载不平衡的影响，并相应地调整其跟踪器和缓存大小。我们的实验表明，CoT的替换策略在不同的倾斜工作负载下，对于相同的缓存大小，始终超过LRU、LFU和ARC的命中率。此外，CoT的命中率略高于LRU-2当两个策略的跟踪（历史）大小相同时。CoT实现了服务器大小的负载平衡，与其他替换策略相比，前端缓存减少了50%到93.75%。最后，我们的实验表明，CoT的大小调整算法成功地自动配置了跟踪器和缓存大小，以在工作负载分布发生变化的情况下实现后端负载平衡。

介绍

社交网络、网络和移动应用吸引了数亿用户[3，7]。这些用户分享他们的关系，并在及时的个性化体验中交换图像和视频[13]。为了实现这种实时体验，底层存储系统必须提供对大数据的高效、可扩展和高可用性访问。社交网络用户消耗的数据比他们产生的数据多出几个数量级[10]。此外，单页加载需要数百个对象查找，这些对象查找需要在几秒钟内完成[13]。因此，传统的基于磁盘的存储系统不适合处理这种规模的请求，因为磁盘的高访问延迟和I/O吞吐量限制[50]。

为了克服这些限制，分布式缓存服务被广泛地部署在每个客户存储的顶部，以便高效地为大规模的用户请求提供服务[49]。Memcached[4]和Redis[5]等分布式缓存系统被Amazon Elasti Cache[1]和Azure Redis Cache[2]等云服务提供商广泛采用。这些缓存服务为直接访问每一个电阻存储层的系统提供了显著的延迟和吞吐量提升。Redis和Memcached使用con-sistent散列[35]在多个缓存服务器之间分发密钥。尽管一致散列确保了分配给每个缓存碎片的密钥数量的公平分布，但它不考虑分配过程中每个密钥的工作负载。现实世界的工作负载通常是倾斜的，很少有键比其他键更热[30]。这种倾斜导致缓存服务器之间的负载不平衡。

缓存层中的负载不平衡可能会对整个应用程序性能产生显著影响。尤其是，它可能导致在接入频率分布的尾部的操作延迟急剧增加[29]。此外，当工作负载偏差增加时，平均吞吐量降低，平均延迟增加[15]。当在依赖数据对象链中执行操作时，实际工作负载的平均延迟和尾部延迟的这种增加是放大的[41]。一次Facebook页面加载会在多轮数据获取操作中检索数百个对象[44，13]。最后，解决方案同样会过度配置缓存层资源，以处理负载最重的缓存服务器所带来的资源利用率低的缓存服务器所带来的影响。

为了解决负载不平衡问题，人们提出了多种方法，使用集中负载监控[9，48]、服务器端负载监控[29]或前端负载监控[24]。Adya等人。[9] 提出将数据服务平面与控制平面分离的切片器。控制平面是一个集中化的系统组件，它收集有关碎片访问和服务器工作负载的元数据。它定期运行一个优化算法，该算法决定重新分配、重新分区或复制密钥空间的片段，以实现更好的后端负载平衡。Hong等人。[29]使用分布式服务器端负载监控来解决负载不平衡问题。每个后端服务器都独立地跟踪其热键和取消决定，以便将其热键的工作负载分配给其他后端服务器。[9，48]和[29]中的解决方案要求后端更改缓存的密钥-服务器映射并将新映射公布到所有的前端服务器。Fan等人。[24]使用分布式前端负载监控方法。这种方法表明，在前端服务器中添加一个小缓存对解决后端负载不平衡有很大的影响。在前端服务器上缓存重量级用户可以减少缓存服务器提供的密钥之间的偏差，从而实现更好的后端负载平衡。Fan等人。理论上通过分析和仿真表明，每个前端都有一个小的完美缓存，解决了后端负载不平衡的问题。然而，完美的缓存实际上很难实现。为了动态地改变和发展工作负载，确定缓存大小和在前端实现接近每影响缓存的替换策略是一项挑战。

在这篇文章中，我们提出了Cache-on-Track（CoT），它是一种分散的、弹性的、预测性强的前端服务器缓存。CoT pro提出了一个新的缓存替换策略，专门针对服务于倾斜工作负载的小型前端缓存。CoT使用一个小的前端缓存来解决后端负载不平衡的问题，如[24]中介绍的。然而，CoT并不认为前端有完美的缓存。CoT使用节省空间的算法[43]来跟踪top-k重击手。跟踪信息允许CoT从top-k跟踪的近似键中缓存出准确的top-C最热键，以防止长尾的冷键和噪声键替换缓存中的热键。CoT是分散的，因为每个前端独立地根据在这个特定前端服务的密钥访问分配来确定其热键集。这种低成本的CoT解决了后端负载不平衡的问题，没有引入单一的故障点或瓶颈，这些通常都是集中解决方案带来的。此外，这使得CoT可以扩展到数千个前端服务器，这是社交网络和现代web应用程序的共同要求。CoT是弹性的，因为每个前端使用其本地负载信息来监视其对后端负载不平衡的贡献。每个前端弹性地调整其跟踪器和缓存大小，以减少由这个前端引起的负载不平衡。在工作负载发生变化的情况下，CoT除了动态调整跟踪器和缓存大小之外，还动态调整前端跟踪器与缓存的比率，以消除任何后端负载不平衡。

在传统的架构中，内存大小是静态的，缓存算法努力实现所有可用资源的利用。然而，在云环境中，理论上存在有限的内存和处理资源，而云站姿迁移是一种常态，云最终用户的目标是实现其slo，同时减少所需的云资源，从而降低其货币部署成本。CoT的主要目标是在每个前端减少必要的前端缓存大小，以消除服务器端负载不平衡。减少前端缓存大小对于以下方面至关重要：1）它降低了部署前端缓存的金钱成本。为此，我们引用大卫•洛米特（David Lomet）最近的著作[40，39，38]中的话，他指出成本/性能通常比纯粹的性能更重要：“这里的论点不是没有足够的主内存来保存数据，而是有一种成本更低的数据管理方法。”。

2） 在数据更新的情况下，当需要数据一致性时，增加前端缓存大小会显著增加数据一致性管理技术的成本。请注意，社交网络和现代web应用程序运行在成千上万的前端服务器上。增加前端缓存大小不仅会使部署更大缓存的成本乘以前端服务器的数量，但也增加了一致性管理管道中的一些成本，包括a）跟踪不同前端服务器中的密钥体现的成本，b）将更新传播到前端服务器的网络和处理成本。3） 由于工作负载是倾斜的，我们的经验清楚地表明，添加更多前端缓存线的相对成本（以每个缓存线的平均缓存命中率和后端负载不平衡减少来衡量）随着前端缓存大小的增加而急剧减少。

CoT的调整大小算法根据动态工作负载的变化动态地增加或减少前端分配的内存。CoT的动态调整大小算法在不同的云设置中很有价值

1） 所有前端服务器部署在同一个数据中心，并获得相同的动态演进工作负载分布；2）所有前端服务器部署在同一个数据中心，但获得不同的动态演进工作负载分布，最终3）前端服务器部署在不同的边缘数据中心，并获得不同的动态变化的工作负载分布。特别是，CoT旨在从每个单独的前端服务器的角度捕捉本地趋势。在社交网络应用程序中，服务于不同地理区域的前端服务器可能会经历不同的密钥访问分布和不同的本地趋势（例如，迈阿密与纽约）。类似地，在大型数据处理管道中，几个应用程序部署在共享缓存层的顶部。每个应用程序可能对不同的数据分区感兴趣，因此体验不同的密钥访问分布和本地趋势。CoT在前端服务器上运行的是细粒度密钥级别，而Slicer[9]这样的解决方案在缓存服务器上运行的是较粗的细粒度切片或碎片。服务器端解决方案是对CoT的补充。虽然捕获本地趋势可以减轻缓存服务器之间的负载并减少负载不平衡，但其他因素可能会导致负载不平衡，因此使用服务器端负载平衡（例如切片器）可能仍然是有益的。

我们在本文中的贡献总结如下。

•缓存在轨（CoT）是一种分散的、有弹性的，

以及预测性的前端缓存框架

减少后端负载不平衡并改进

整体表现。

•

CoT动态地最小化所需的前端缓存大小，以实现后端负载平衡。与其他替代政策相比，CoT的内置弹性是一个关键的新优势。

•

广泛的实验研究，将CoT的替代政策与传统的以及最先进的替代政策，即LFU、LRU、ARC和LRU-2进行比较。实验结果表明，与其他替换策略相比，CoT在不同工作负载下实现了服务器大小的负载平衡，前端缓存减少了50%到93.75%。

•实验研究表明

成功地自动配置跟踪程序和缓存

大小以实现后端负载平衡。

•在我们的实验中，我们发现

YCSB的[19]加密工作负载发生器-

阿托尔。这个生成器生成的工作负载

明显没有承诺的那么偏斜

压缩分布。

论文的其余部分安排如下。第二节介绍了系统和数据模型。在第3节中，我们通过介绍在前端使用LRU、LFU、ARC和LRU-k缓存的主要优点和局限性来激励CoT。我们在第四节介绍了婴儿床的细节。第五节对胶辊的性能和运行费用进行了评估，第六节对相关工作进行了讨论，第七节对论文进行了总结。