云计算开发之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]中的话，他指出成本/性能通常比纯粹的性能更重要：“这里的论点不是没有足够的主内存来保存数据，而是有一种成本更低的数据管理方法。”。

（编辑：新余站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!