分布式键值存储中的数据放置策略及其性能分析

1/分布式键值存储中数据放置的可证明好的随机策略柘汪华盛顿大学路易zhe.wang邮件wustl.edu何柳基金会DBheliu@apple.com赵金浩华盛顿大学路易jinhaoz@wustl.edu孟旭基金会DBmeng_xu@apple.com库纳尔·阿格拉瓦尔华盛顿大学路易kunal@wustl.edu井梨新泽西理工jingli@njit.edu摘要分布式存储系统广泛应用于云、数据库和文件系统中.这些系统在多个服务器上存储大量数据当访问数据的请求进来时，它被路由到适当的服务器，排队，并最终处理。如果服务器因此，在设计用于将数据分配给服务器的算法时的一个重要挑战是请求模式可能是不平衡的、不可预测的并且可能随时间而改变的事实如果某些服务器获得了很大一部分请求，它们就会过载，导致许多拒绝。 在本文中，我们分析了这个问题的理论下的对抗性假设。特别地，我们假设请求序列是由对抗过程生成的，以最大化拒绝的数量，并根据拒绝的请求的比例分析各种算法策略的性能。我们发现，没有确定性的策略可以很好地执行。另一方面，一个简单的随机化策略保证了最多一个恒定比例的请求在预期中被拒绝我们还表明，如果我们想拒绝一小部分（1/2，其中1/2是服务器的数量）的请求，移动数据负载平衡是必不可少的 我们设计了一个随机化和数据传输的策略，以实现这种性能与速度增强。最后，我们进行了实验，并表明我们的算法在实践中表现良好。关键词：负载均衡，分布式键值存储Correpondingauthor允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要以其他方式复制、重新发布、在服务器上发布或重新分发到列表中，需要事先获得特定许可和/或付费。请求权限请发邮件至permissions@acm.org。PPoPP©2023计算机协会。ACM ISBN 979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.35775011介绍分布式键值存储在现代平台上被广泛使用，特别是在云应用程序中[1，8，11，17，18]，而且在大规模数据库[12，20，24，36，41]和分布式文件系统[15，22，39]中也是如此。 在这些应用中，存在大量的数据项语料库（例如， 键值对、对象、文件）存储在许多服务器上。系统的客户端发送请求，访问某些特定的数据。每个请求都被路由到拥有这些项的服务器，服务器负责处理此请求并响应客户端。如果服务器忙，则请求可以排队。对于这样的系统，一个重要的优化标准是吞吐量-系统在每个时间段内平均可以处理的请求数量。 如果大多数请求最终访问的服务器数量很少，那么大多数系统容量可能会闲置，而少数服务器的队列会无限增长。客户端可能关心延迟-发送请求和接收回复之间等待由于长队列影响延迟，分布式存储系统为服务器实现有界队列，使得具有满队列的服务器拒绝未来的请求。系统的目标是接受或消耗尽可能多的请求，或者相反地拒绝尽可能少的请求，同时保持队列大小较小-这相当于在保持延迟较小的同时最大化吞吐量。为了避免拒绝许多请求（从而降低系统吞吐量），分布式存储系统尝试跨服务器平衡负载。但是，它们不能直接控制负载，因为请求是由客户端生成的，并且请求访问模式可能会随时间而变化因此，如果所有的避免过载可能需要通过动态地将这些项移动到其他服务器来进行负载用于分布式存储系统的负载平衡算法通常具有以下步骤：（1）初始地以某种方式跨服务器分布数据;（2）每个服务器具有具有有限大小的队列（由算法决定），并且如果其队列已满则拒绝传入的请求;（3）通过选择一些数据从服务器移动来进行动态数据分布2（）下一页–（/）–PPoPP“超载”服务器到其他服务器。在这项工作中考虑的问题是应该如何做这些步骤。这个问题已经使用基于过去系统行为的各种算法或理论上使用请求到达的排队理论假设进行了经验研究[9，30]。在本文中，我们从理论的角度考虑这个问题。更正式地说，假设数据被划分为必须存放在MySQL服务器上的MySQL块在每个时间步，每个服务器可以处理一个请求。我们假设这些请求是由一个对抗过程生成的，该���过程在每个时间步生成请求，并最大化拒绝请求的数量。我们的目标是了解什么样的策略与小队列可能对各种对抗性假设。我们有以下结果：简单的确定性策略对随机客户端有效，但没有确定性策略对对抗性客户端有效：如果客户端不是对抗性的，并且在每个时间步选择一个随机块进行请求，那么任何将块均匀分配到服务器的简单策略都可以很好地工作;然而，如果客户端是对抗性的，那么对于任何确定性算法，都存在一个请求序列，使得算法拒绝大多数请求。简单的随机策略效果相当好对抗不经意的对手：一个简单的随机化策略，将块均匀随机地放置在服务器上，然后永远不移动它们，效果不错-也就是说，它至少接受预期中的恒定部分请求此外，如果以下任一情况为真，则该策略提供了仅拒绝0.01%请求的强约束：（1）如果对手被削弱，使得其访问同一块的频率有一个������将每个时间步长的请求数记录为1。数据传输是有用的：我们表明，没有数据传输和恒定速度的策略可以消耗1 1 ���frac-tion的请求与敌对客户端。我们还设计了一个算法，该算法从随机分配开始，然后将块从负载沉重的服务器中移出以平衡负载。考虑到不断的处理和数据传输的加速，我们表明，这种策略消耗1 -���1部分的请求，即使对一个完全敌对的客户端。实证评价很有希望：考虑到这项工作中所考虑的系统模型的实用性我们使用FoundationDB [41]构建了一个案例研究，在真实的集群上运行现实的基准测试我们使用对抗性和现实的工作负载进行模拟实验，以评估我们提出的算法的经验性能。结果表明，随机算法与不带数据传输只需要一个小的加速比，以达到相同的性能作为离线的最佳算法。2在分布式数据存储中，我们有���存储大量项（如键值对、对象或文件）的分布式数据存储服务器。我们可以将数据划分为100（100>102）个数据块，其中块是键的集合或键的连续范围���系统根据其负载平衡策略将块分发到服务器。在本文中，我们将抽象出数据分区是如何完成的细节，并假设���和���是给定的，并且不会随着时间的推移而改变。我们还将其他问题，如数据复制（和其他数据库机制，如写前日志和多版本控制）作为未来的工作。客户端在线向集群发送请求，我们假设每个请求访问单个数据块。当请求到达时，它被传递到承载适当数据块的服务器出于分析目的，我们将时间轴划分为相同的时隙，其长度等于处理请求的时间 为了简单起见，我们不区分读、写和读范围操作。 每个服务器都有一个FIFO队列（先进先出），最大长度���为存储未服务的客户端请求。 当请求到达时，它们被存储在相应服务器的队列中，除非没有空间，在这种情况下，请求被拒绝。由于服务器可以在一个插槽中使用一个请求，因此在理想情况下，集群最多可以使用100个请求其中所述服务器请求访问位于不同服务器处的组块因此，为了使工作负载可行，我们假设最多有一个HTTP请求在一个时隙内到达集群，并且每个请求访问不同的块。在系统初始化期间，系统根据一些负载平衡算法将块分配给服务器之后服务客户端请求。对于本文的前几个结果，我们假设分配在初始化后是固定的。然而，某些服务器可能会过载，负载平衡算法可能需要将数据从一台服务器移动到另一台服务器;因此，本文后面的部分将分析移动数据的算法我们对数据移动（称为数据传输）的过程进行正式建模，如下所示。在任何时候，服务器都可以参与一次数据传输。 在每次传输中，最多���将块传输到另一个服务器，这需要���时间槽。换句话说，���从一个服务器到另一个服务器传输或更少的块需要���时间;因此，传输时间是一个阶梯函数，而不是线性的。这模拟了将数据从一台服务器移动到另一台服务器的延迟通常很大，但带宽也很大的事实-因此，发送或接收1个块与直到带宽的几个块花费相同的时间量另一方面，将两组块从两个不同的服务器移动或移动到两个不同的服务器需要2个时隙，因为服务器必须准备传输并发起传输。我们使用单个参数���对数据传输中的最大块数（总大小低于带宽）和数据传输的延迟进行建模。我们的案例研究3（）下一页| |（）≥· （）（−/）||（）≥（−（/））（）///Probably Good Randomized Strategies for Data Placement in Distributed Key-Value Stores PPoPP在第6节中，表明该模型在实际平台上是合理的如第1节所述，目标是最小化拒绝请求的数量，这是吞吐量的一个度量定义1（缩略语）。 给定一���个随时间到达的请求序列，������表示算法按序列接受的���请求数���。我们假设客户端请求的输入序列是由一个不经意的对手生成的，定义如下。定义2（不经意的对手）。不经意的对手知道在线算法是如何工作的，但它不知道算法所做的随机选择。对于确定性数据分配，不经意的对手总是知道块在任何时间点的确切位置;因此，毫不奇怪，我们能够证明没有确定性算法表现良好。本文主要分析了各种随机化算法的性能算法的理论性能可以通过比较其吞吐量与最佳吞吐量来分析。定义3（持续竞争）。 一个在线算法���是（常数）���-竞争的，如果���������������������对任何有限的输入序列���，其中���������是离线最优的。一个算法���1. 虽然持续的竞争力是好的，我们宁愿不拒绝一个恒定的请求的一部分。因此，我们定义了以下更强的性能标准。定义4（几乎最佳）。一个在线算法���几乎是最优的，如果������������������������对于任何有限的输入序列11���，其中���������是最优的离线调度。对于随机化算法，类似的定义适用，除了我们将算法的预期吞吐量与随机化算法的吞吐量进行比较。注意，在离线最优的最佳情况下，在一个时隙中到达的所有请求访问不同的服务器并在该时隙中处理，有限输入序列中的所有请求都可以被最优接受。因此，如果在线算法可以接受针对所有输入序列的11次重复请求，则该在线算法接近最优最后，我们的一些算法将需要资源扩增或加速。资源增加意味着我们允许算法更快比最优算法更好 我们考虑两种类型的资源增加：（1）服务器上处理请求的速度和（2）数据传输的速度。通常，资源扩充是实现重要结果所必需的。然而，所需的资源增加越小，算法越好。我们通常希望资源增加系数不超过一个常数。3确定性政策本节分析用于将数据块分配给服务器的确定性策略为了热身，我们将首先展示如果客户端请求访问随机组块，则均衡每个服务器上的组块数量的任何策略都执行得很好。 另一方面，没有确定性策略可以很好地对抗不经意的对手-对于任何确定性策略，都存在一种访问模式，导致系统只接受少量请求。简单的策略可以很好地应对随机客户端。我们现在做一个简单的分析，表明所有合理的分配都适用于随机客户端，其中每个请求都随机和独立地选择一个块进行访问。在不失一般性的情况下，我们放松了假设，允许多个请求即使在同一时隙中访问同一块。对于这个随机的客户端，我们考虑一个简单的均匀分配，其中每个服务器都分配了100个块������分配只生成一次，不需要更改。下面的引理很容易用Buckoff边界证明引理1. 对于随机客户端和均匀分配，在任何日志���连续时隙中，超过3个日志���请求到达特定服务器的概率小于1/���2。引理1导致下面的定理。定理1. 给定一个随机客户端，速度为3且队列大小���为6的 偶 数 分 配 log��� 至少接 受 （ 1 - 1/��� ） |���||��� 请求。|requests.证据 将执行分为几轮，每轮都有���日志���请求-因此，每轮至少有日志���时间步长，因此服务器可以从其队列中以速度3处理3个日志���请求。 根据引理1，服务器在一轮中接收到多于3个日志���请求的概率至多为���12。通过联合边界，在特定轮中���，至少一个服务器接收到超过3个日志���请求的概率至多为1���。对于一个特定的回合，我们将通过归纳证明，在每一轮开始时，任何服务器队列中上一轮剩余的请求数量���我们有两个案子。首先，在回合中���，没有服务器获得超过3个日志���请求。 在这种情况下，在回合结束时服务器的队列大小���不会增加，因为服务器���可以在一个回合期间处理3个日志���请求（如果可用）。 在此轮中，任何队列中最多可以有6个日志���请求，并且没有请求被拒绝。第二，在一轮搜索中，一些服务器收到超过3个日志搜索请求。我们可以悲观地假设，所有3个日志���请求���都被拒绝，保持归纳假设。由于请求仅在第二种类型的回合中被拒绝，其发生的概率最多为1/���，因此我们在期望中的请求的最多1/���分数。□没有任何确定性策略能对抗对抗性客户端。我们现在考虑一个健忘的对手。直觉上，由于算法是确定性的，对手知道分配，它总是可以过载一些服务器。这里我们4（）/（）（/（+））≤+−−（−）.最小的要求是���= ���−���≥（1−）���。任何服务（）下一页≤������（）下一页–（）下一页���������！������！PPoPP我认为，没有一种确定性策略，即使它将数据移动到负载平衡，也可以很好地处理小队列。定理2. 考虑���在具有���服务器、���块、最大队列长度���、数据传输时间���以及请求处理和数据传输的恒定加速的系统上运行的确定性算法，其中���>���2。存在一个请求序列���，使得������������������= Ω���������������，其中���������是离线最优的。证据 因为���> ���2，在任何时刻，存在具有多于个���块的服务器。由于该算法是决定性的，因此对手总是知道哪个服务器拥有更多定理3. 给定一个包含���服务器和���请求的系统。对于任何序列���，假设���[������]是球接受到bin分配的请求的预期数量���。然后，���[������]/|���|≥ 1 −1/���即使队列大小���= 1且没有资源增加。证据 考虑将球分配到容器中，并考虑���客户端向������不同块发送请求时的特定时间步长。这些垃圾块被随机扔到垃圾服务器上。现在考虑一个特定的服务器���。这些请求命中的���������概率是：. ���-是的 1美元���。���−1Σ���−������并可以将所有的HTTP请求发送到这些块。���������由于服务器在每个时间步只能处理缓存块队列很快就会填满，导致大多数请求被拒绝。现在，假设该块移动块。我们把时间轴分成几轮。 每轮都有������时隙，其中���是执行数据传输的时隙数。 这是对手的策略。在轮重定向开始时，选择重定向的块，这些块都在一个特定的服务器上���，比如重定向，并只在下一个重定向时间步向这些块发送年底前���步骤，���可以���将这些块���从���请求中移除。 具有���请求处理速度，���可以在时间步中处理最多������请求���，并在队列中存储最多���请求。因此，它最多���������接受其中������两个请求。在此之后，对于该回合的剩余时间（剩余的���������时间步），对手不发送任何请求。由于OPT知道序列，在前一轮���1，它将设置为确保所有这些���块都在不同的服务器上，因此它可以接受所有请求。其余���1 轮的���时间步长���，OPT（与对手合作）为下一轮设置。 它知道哪个服务器���在下一轮开始时至少有块，因此���，它会将这些块分布在多个服务器上，以实现OPT���这样OPT就可以在下一轮中回答所有的匿名请求因此，至少获得1的服务器的预期数量���1���1获取至少一个请求处理至少一个请求- 因此，在此时间步，在总共1000个请求中，至少有1000个请求被消耗������因此，通过将所有时间步长相加，我们得到结果。□我们看到，球进入垃圾箱的分配是恒定的竞争，没有速度增加，队列非常如果我们给它加速呢？我们现在证明，在足够的（Θlogθ）速度增加的情况下，它几乎是最优的。定理4. 给定一个包含���服务器和���请求的系统。对于任何序列���，假设���[������]是球接受到bin分配的请求的预期数量���。然后，���[������]/|���|≥ 1 −���（1/���），请求处理加速比为Θ（log���），队列大小���= Θ（log���）。证据 考虑���客户端向������不同块发送请求时的特定时间步长。当分配完成时，这些内存块被随机抛出到内存服务器上。 现在考虑一个特定的服务器���。在此时间步长，至少有一个HTTP请求访问此服务器的概率为然后对手可以重复下一轮。□最多���-是的 1Σ��� ≤ ������ . 1=1<1/1/2，对于= log，���（）下一页4无转移的随机策略在本节中，我们考虑一个简单的随机化策略，它将块随机分配给服务器，这类似于将随机球扔进垃圾箱的游戏。我们将证明它是持续竞争的。 我们还将证明，没有一种不移动数据的策略可以几乎是最佳的。在下一节中，我们将看到一个几乎是最优的策略。定义5（M−）。对于���块和���服务器，该算法随机且独立地为每个块统一选择服务器。 M-映射表示块和服务器之间的映射。球入箱的上界 我们现在要证明一个对抗性客户的定理。足够大的水。在任何时间步长，以Θ log���速度，���=日志请求可以由服务器处理因此，我们认为，球入仓分配可以处理���在该时间步上以至少11的概率到达的所有请求���。即使悲观地假设其他时间的所有请求都被拒绝，对时间求和仍然会得到结果。□没有数据传输的算法的下限 我们看到球入箱算法在Θlog���速度下几乎是最优的;然而，恒定速度呢？ 我们现在给出一个下界，即任何不移动数据的算法在恒定速度下都不可能是几乎最优的。定理5. 给定用于分配块的任何策略n，对于长度为n的任何队列，处理的恒定加速，如果n>n2，则存在输入序列，使得���[���]/���[���������] ≤���其中���<1是常数。5（/）–八块八块 ·––（）下一页/−/−/. Σ−–（/）Probably Good Randomized Strategies for Data Placement in Distributed Key-Value Stores PPoPP这是对手���挑战是要表明，没有随机化的策略，可以提供一个几乎最佳的接受率，在预期的这个序列。 为了做到这一点，我们将定义一个群的概念，这将允许我们提取所有分布的共同属性。定义6（组）。假设一个���-group由���位于同一服务器中的块组成，并且不同的组没有任何共同的块。我们希望所有组都有相同数量的块，以便计算概率。如果服务器至少具有现在我们可以证明定理5了。由于对手重复请求相同的���块，因此过载的组仍然过载。因此，无论队列大小如何，组过载的服务器最终都会拒绝许多请求。证据根据引理2，每个20-22-组以概率20 -22过载--它们在每个时间步上至少得到20 - 22个请求因此，对于任何小于���这些组永远保持过载，因为它们的总容量小于它们的平均负载。因此，这些块将在每个时间步拒绝至少一个请求。以来过载组的期望数量是1000=1000·1002，���chunk，我们创建了一个组，每个组都有两个chunks，剩下的chunk不分组。���重复地将���未分组的块放入组中，直到我们有少于���未分组的块。下面的观察只是说有大量的群体。观察1. 对于���块在���服务器中的任何位置，（���/2���）-组的数量至少为���。我们现在只考虑分组块，我们将展示发送到分组块的大量请求将被拒绝。特别地，我们将首先证明一个组获得大量请求的概率并不太小。引理2. 给定块的特定分布，并假设对手随机选择���块。那么对于���������������如果一个（n/2 n）-群在速度限制下，在每一个������<时间步长在期望范围内，而最优算法可以处理所有的重复请求。因此，任何算法接受的请求的分数是���，并且���对于任何常量都是常量���。□约束请求序列。上一节中的论点表明，对于任何不移动数据的随机化策略，最坏情况下的工作负载是重复请求相同的随机化策略的对手然而，这往往不是现实世界中发生的事情 在本节中，我们展示了如果对手不能重复请求相同的块，我们可以做得更好-我们假设客户端在任何连续的日志时间步长中最多向特定块���发出一个请求，并展示了球入箱策略几乎是最佳的。我们把时间分成大小为对数的阶段。下面的引理类似于引理1，除了随机性至少有100个请求大于100=1���二、我们可以说这些群体超负荷了证据 由于对手随机选择���不同的块，每组中的块的数量遵循超几何分布。特别是，考虑到���=和组大小��� =���2��� 。 我 们 可 以 假 设 ， ������>���2 和 ������> ���2 和������<������。然后，我们可以将特定组在多个块中具有多个块的概率限制为���以下内容：来自随机分配而不是客户。引理3. 针对一个在一个阶段内不能向同一服务器发送多个日志请求的约束对手，任何服务器���在一个阶段内收到3个以上日志请求的概率至多为1/���2。利用引理3，我们可以以与定理1的证明非常相似的方式证明定理6。定理6. 给定一个size ���=���（log���）的队列和一个con-. ���-是的− Σ���！ ·（ − ）！紧张的对抗性输入，预期的请求数量���������������-���-（ −）！（ − ）！（− −（ −））！���！快！（ −）！由球消耗到垃圾箱的策略是���[���]≥（1 − 1/���）���。结果表明，如果请求是一个���！·（ − ）！·���！而不是连续和重复地访问同一块。- ���- · （���−）！（ − −（ − ））！���！（ −）！（���−���）！5带有转移的随机策略1>���啊！·1（−）·（− −（−���））−·（−���）���������（）·（）·（（���1 −1−1）） − ���������22在本节中，我们的目标是设计一个几乎是最优的策略（消耗请求的1/21/ 1），具有恒定的加速，并且没有对> ！ ·2������输入序列。特别地，我们提出了一种算法，���1=·（31������−>>1 ·-3，假设满足以下强保证的条件八������！���–2八������！定理7.假设我们有一个恒定的数据移动加速-这证明了引理。□并在系统配置上不断加速处理16（）下一页（）下一页（）下一页（）下一页（）下一页PPoPP其中队列长度���= Θ ���log 2���，其中���是完成数据传输的时隙数。对于任何输入序列，如果是，则预计由Oracle消耗的请求数至少为（1 −���（1/���2））���。系统概述���：在前面的章节中，我们已经看到，虽然确定性策略不能被证明是恒定的竞争性（即使允许数据移动）（定理2），但简单的随机策略，如随机均匀分配块，可以实现恒定的竞争性（定理3）。特别地，在球随机进入箱的情况下，可以在每个时间步长上消耗请求的恒定部分。然而，由于一些服务器在每个时间步长上获得多于恒定数量的请求（一些服务器获得Ω log���请求），这些服务器过载，并且对手可以使它们过载-因此，在最恒定的速度和对输入序列没有限制的情况下，没有数据移动的随机化策略几乎是最优的（定理5）。为了解决这个问题，我们将设计一个系统，我们称之为，���它移动数据以获得良好的负载平衡。特别是，我们开始与随机球到箱分配就像前面的部分。因此，所有块都有一个主服务器，在那里它们通过球被分配到bin中。然而，当服务器的队列包含已经在系统中存在了0���log���时间的请求时，这指示该服务器过载并且不能处理发送到它的所有请求。此时，在该服务器上触发批量移动过程，并且将服务器中具有未决请求的块分发到其他服务器，使得这些旧的未决请求可以由其他服务器有效地处理。一旦这些未决请求被处理，这些块就被移回它们的主服务器，以便恢复原始的随机分配建模假设：为了简化分析，我们将做出一些不影响总体结果的建模假设。特别地，我们将假设每个服务器有两个处理器：一个主处理器，它消耗从客户端到达该服务器的请求;一个辅助处理器，它消耗从其他服务器发送到它的请求，用于其他处理器的负载平衡目的。 每个服务器都有自己的队列，其中主队列和辅助队列的大小都是Θ ���log2���。请注意，这并不影响定理陈述，因为我们允许恒定的加速-如果我们允许处理器速度���为1000，那么每个处理器都可以以一半的速度运行。类似地，队列长度可以在两个队列之间分割，同时仅影响常数因子。在此分析中，我们不会尝试优化常数因子;因此，计算的常数因子将很大。 在评估部分，我们将看到该算法在实践中需要一个相当小的常数才能表现得很好。使用这些术语来重述算法：当请求从客户端到达服务器时，它被放入主队列。如果主队列已满，则拒绝请求 如果主队列中最老的请求的年龄是6���log���，则服务器触发批量移动过程，并且主队列中具有请求的任何块被移动到其他服务器，并且它们对应的请求被移动到这些服务器的辅助队列（移出阶段）。这些移动的请求由目标处理器的辅助服务器处理 一旦服务器的辅助队列为空，移动到那里的块就会被发送回它们的主服务器（移回阶段）。 我们将立即定义精确的运动策略，但让我们首先考虑设计这一策略的挑战是什么。挑战：直觉上，系统应该工作，因为���(1) 它及时地将请求移出主队列，以避免填满主队列;（2）它将请求分散在辅助队列中，这有效地消耗请求并避免填满辅助队列。然而，也存在一些挑战。首先，如果批次很大，则批次移动过程可能需要很长时间 当服务器触发批量移动时，该服务器中的许多块可能在主队列中具有挂起的请求，并且必须移动所有这些块。回想一下，在第2节中，在两个特定的服务器之间移动最多100个块需要100秒的时间-我们称之为传输。因此，根据需要多少传输这可能导致服务器的队列在批处理进程执行时变得更长，并阻止其他批处理进程启动。第二，我们可能运气不好，服务器可能在同一时间收到来自客户端的大量请求。 当这种情况发生时，主队列可能会非常快地过载，从而可能导致下游影响。第三，批处理是确定性的，因此，原则上，当块在远离其主服务器的地方被处理时，对手可以猜测块的位置，并且可以通过向这些块所在的服务器发送太多请求来使这些块所在的服务器过载。算法描述。 我们现在可以���描述它如何应对这些挑战。每个服务器的队列大小是Θ ���log 2���，这是一个隐藏在θ符号中的足够大的常数。(I) 批处理触发器：当特定服务器上的最旧请求（该请求尚未成为较旧批处理的一部分）超过6个日志记录时，将触发该服务器上的批处理(II) 批处理启动：在Y中，批处理过程可能不会在触发后立即启动;它们按顺序执行也就是说，批处理过程���在批处理过程���被触发之前被触发。如果在同一服务器上触 发 了 这 些 进 程 ， 则 在 SQL Server 完 成 后 将 执 行SQLServer，因为相同的块可能两者都要参与如果它们位于不同的服务器上，则可以并行执行。我们的分发算法确保服务器一次最多参与传输。7（）下一页（）下一页/（）≥������+（/）––联系我们≤（）（）.Σ=Probably Good Randomized Strategies for Data Placement in Distributed Key-Value Stores PPoPP(III) 移出期间的数据分布：一旦触发了一个批处理，我们就知道哪些块是该批处理的一部分-也就是说，哪些块有属于该批处理的挂起请求。这些块被划分为日志存储包以进行传输，使得每个存储桶具有日志存储块，并且最多���浏览日志请求。我们后来表明，这是可能的，很有可能因此，这些包中的每一个都可以使用一次传输移动到目标服务器。 当批处理开始时，这些存储桶被移动到���不同的服务器上，相应的请求被移动到这些服务器的辅助队列中。(IV) 处理块并向后移动次要批处理的一部分已在队列中等待了6个logn时间。因此，一个批处理进程最多可以包含来自6个对数时间步长的请求我们可以按照如下方式限制批处理中的请求数量引理5. 给定球到仓分配，常数���1和���<������log���。在6个���log���连续时隙中，特定服务器接收12���个log 2���或更多请求的概率小于12���。证据请注意，客户端可以在不同的时间步向同一个块发送请求，但在一个时隙中，它必须发送���不同的请求。在每个时间步中，对于特定的目标服务器的处理器处理来自服务器端，比如说，服务器端是代表���二级排队。一旦特定传输的所有请求在时间步长命中此服务器的请求数���。为���=2 log���家庭服务器。(V) 批处理期间的请求处理即使是块Pr（���λ≥λ）≤. ���- 是的1Σ��������� 1���1 1<3已移动到其他服务器以处理其挂起-������������！ ������！ ���ing requests，对该块的任何新请求仍然会被发送最后一个方程在λ>4时成立。因此我们可以到其主服务器通过所有的对数迭代步骤和使用伯努利������一旦块移回其主服务器，(VI) 流量控制和批量截止：为了避免一些边界条件，我们执行一些控制：（1）如果单个服务器在单个时间步内收到超过2个日志���请求，则立即拒绝其中的一些请求，以确保在任何单个时间步上只有2个日志���请求被添加到任何主队列。（2）如果服务器在主队列中有超过24���个请求的日志���块，则服务器仅移动请求最多的24���个日志���块，并且服务器拒绝未移动的块的请求。拒绝的原因 我们想表明，这个过程中拒绝最多������12分数的要求，在预期。请注意，请求可能由于以下原因而被拒绝：（1）流量控制和批量切割;（2）如果主队列变满，则从主队列拒绝;以及（3）如果辅助队列变满，则从辅助队列拒绝我们将表明，前两个原因导致很少拒绝的预期和最后一个原因导致没有拒绝一个良好的负载平衡策略。但是，为了说明这一点，我们必须首先绑定完成一个批处理过程所需的时间。限定批处理的执行时间。我们首先定义了批处理的执行时间--批处理从触发到完成我们将时间分成大小为3���log的阶段���。我们说������ 是在阶段期间触发的批处理过程的集合���。我们将证明下面的关键引理。引理4.在阶段期间触发的任何批处理过程���将在第1阶段结束时完成���，处理速度和传输速度都保持不变。为了证明这个引理，我们首先证明一些支持引理。首先，我们回想一下，当队列中最旧的请求尚未被发送时，不等式来得到我们需要的边界。□我们也可以通过一个非常类似于引理1的方法来限制批处理中涉及的块的数量。引理6. 给定球进入仓分配，可以在6个���日志���时间内请求的来自特定服务器的块的总数是24���个日志���，概率至少为 112��� 。 因 此 ， 批 处 理 中 涉 及 的 块 的 总 数 是24���log���，概率为112���。因此，每个批处理都会将日志���传输到不同的目标。给定这些引理，我们可以定义一个转移打包策略。回想一下，每次数据传输最多可以将200个数据块传输到特定的服务器。一旦我们定义了一个最多������包含log2���个请求和������日志���块的批处理，我们就将这些打包到日志���传输greetings中。我们不断向传输中添加块，直到传输中的请求数大于���1���log���（对于某个常数���1），或者传输中的块数大于���2���。此时，此传输完成，我们开始新的传输。由于前面的两个引理，一个特定的批处理的总转移次数最多是logn，对于适当的选择n1和n2。因此，我们有以下推论：推论7.1。将属于同一批处理的所有块移动到日志���目标服务器所需的时间是���log���，假设我们的数据移动速度为24，那么我们可以及时移动24���个块���。我们还可以在某些条件下限制seconception队列中的请求数量。考虑1中的批处理过程������������-在两个连续阶段期间触发的批处理过程。我们希望限制由于这些批处理过程而最终出现在同一服务器的辅助队列中的请求数量8联系我们联系我们//���！+++++公司简介正+ ++/（）下一页–（）下一页PPoPP引理7. 仅考虑属于以下批次的请求：������������ 1，则对于某个常数3，最终进入特定辅助服务器队列的这些请求的数量������������最多为3 log。证据中批处理的所有请求���������由于来自批处理的任何请求必须在批处理开始之前最多6个log���时间到达，因此，批处理1在12个 log时间间隔内到达。因此，这些批处理最多可以包含12������个日志���请求。由于请求在批处理移动期间在服务器之间均匀平衡，并且我们有���服务器，因此对于适当大的3个日志请求，没有服务器具有超过���3���个日志���请求���。□限制拒绝的请求数 我们现在可以证明，被拒绝的请求数量很少。 下面是定理7的证明。证据回想一下，由于两种控制策略，请求可能会被拒绝。首先，引理6意味着一个批次具有多于24���个所涉及的日志���块的概率小于���12。由于由于第二个策略拒绝请求只发生在这些批次上，因此此概率也小于1/2。第二，考虑两个日志重定向请求到达同一服务器的情况对于一个特定的服务器来说，比如说，服务器是一个随机变量，代表了在这个时间步到达这个服务器记为=2log，���我们有我们现在观察到以下关于连续的不变量Pr. ���-是的1Σ��������� . 1Σ���1=阶段，因为当最旧的请求不是6���年前到的那批货的一部分（≥）���≤���≤！ 你好！对于n>4，我们有1/1/2/3。<根据工会的规定，观察2. 考虑任何两个连续的阶段，������ 1，并考虑set ������������+1-在这些阶段期间触发的批处理过程的集合。同一台服务器不能触发此集中的两个批处理进程现在我们可以通过归纳法证明引理4证据 基本情况很简单，因为第一阶段没有触发任何批处理过程。 对于归纳假设，假设在阶段1结束时完成阶段期间触发的所有批处理过程������。因此，在阶段1期间触发的所有批处理���都准备好在阶段2开始时���开始，因为在它们各自的服务器上的所有先前批处理都已经完成。在第二阶段未触发任何批处理过程1有相同的来源（观察2）。此外，它们各自触发日志���传输（推论6）。因此，总共有���最多的传输源和最多的���传输日志���目标-这些可以在日志时间中调度������，而没有源或目的地冲突，数据传输速度有足够大的恒定加速。现在考虑由辅助服务器处理这些请求。 辅助服务器只能包含由于在阶段���1和阶段���2期间触发的批处理过程而产生的请求（由于阶段���2已经开始，因此该阶段中的某些批处理过程也可能已经开始）。 根据引理7，对于某个常数3，由于来自这两个阶段的请求而导致的任何次级队列中的请求的总数至多为������3log������。因此，同样，在处理上有足够的持续加速，所有这些请求都可以在接下来的日志步骤中由辅助服务器������处理。最后，来自阶段1的批处理过程���的所有块必须来回移动，这可以������通过使用移出调度的反向调度在日志时间内完成。因此，在阶段1+1开始后最多3个对数周期内，即，第10+2阶段结束时-所有这些批次均已完成。 □通过所有服务器，由于第一策略而被拒绝的概率小于1/2。除了控制策略之外，如果主队列已满，则可以拒绝请求。然而，回想一下，每个批处理在时间上最多完成10000000，并且由于引理5，在该时间段内到达的请求的总数最多为100000000，概率为2000000。������������������1112.由于主队列具有此容量，因此