排行榜 统计
  • 建站日期:2017-05-20
  • 文章总数:139 篇
  • 评论总数:482 条
  • 分类总数:26 个
  • 最后更新:昨天 21:08

PAXOS性能建模-2

本文阅读 18 分钟
广告
头图源自 xp

在这篇文章中,我们将研究在队列 queue 或处理管道 pipeline 的帮助下估计处理开销。我将展示这些开销如何限制性能并影响不同集群负载下的延迟。

我看可伸缩性有几个原因:一是在云时代,3个或5个节点的集群可能不足以提供良好的弹性,特别是在节点位置控制有限的环境中。毕竟,一个好的集群需要避免共享的节点常见故障点。第二,我认为这有助于更多地了解paxos及其风格,以及为什么某些应用程序选择使用它。第三,我想看看更奇特的paxos变体,以及它们的性能如何受到不同因素的影响,例如WAN或 Flexible Quorum。例如,Flexible Quorum 提供了在性能和弹性之间进行权衡的机会。我们通过调整第一阶段和第二阶段的数量来实现这一点。这就是建模变得很方便的地方,因为我们可以检查特定的 quorum 或 deployment 从性能的角度来看有什么不同。

上次,我们研究了在服务器数量上扩展集群时,本地网络变化如何影响性能。我意识到消息往返时间(RTT)的波动只能解释从3个节点到5个节点的大约3%的性能下降,而在我们的paxos实现中,性能下降了30-35%。我们还发现这种降级取决于quorum 大小,并且对于某些 manjority quorum 部署,由于网络的原因,甚至可能没有任何区别[见1.5节]. 在本文中,我进一步改进了模型,以解决处理瓶颈问题。

作为上一次的复习,我列出了我一直使用的一些参数和变量:

  • $Tl$ – message RTT in local area network 局域网中的消息RTT
  • $μl$ – average message RTT in local area network 局域网中的平均消息RTT
  • $σl$ – standard deviation of message RTT in local area network 局域网中消息RTT的标准偏差
  • $N$ – number of nodes participating in a paxos phase 参与Paxos 阶段的节点数
  • $q$ – quorum size. For a majority quorum $q=⌊N/2⌋+1$
  • $ms$ – time to serialize a message 序列化消息的时间
  • $md$ – time to deserialize and process a message. This involves various message-related round tasks, such as ballot comparisons, log maintenance/updated, etc. 反序列化消息和处理消息的时间;涉及到各种与消息相关的任务,比如 ballot 比较,日志维护,更新等等。
  • $\sigma_{ms}$–消息序列化时间的标准偏差
  • $\sigma_{md}$–消息反序列化时间的标准偏差

这个 round 的延迟$L r$是由 $L_r=m_s+r_{lq-1}+m_d$估计的,其中$r_{lq-1}$是第 $q-1$条最快消息$L_{q-1}$的RTT+副本处理时间。

消息处理队列

上述模型中的大部分性能差异来自于网络性能波动,考虑到$m_s$、$m_d$及其方差与网络延迟相比较小。但是,处理每条消息会在节点上造成很大的开销,而我之前没有对此进行说明。我将消息处理想象为一个队列或管道;如果有足够的计算资源可用,那么消息可以立即处理,否则它必须等到之前的消息通过并且资源可用。我说的是,当消息不能立即开始处理时,管道就被阻塞了。

round leader 更容易被阻塞,因为它需要处理$N-1$个在每一轮大致相同时间发出的回复。出于模型的目的,我只考虑在 leader 处的queuing/pipline 成本。 pipline是为传入和传出消息共享的。

让我们考虑一个通用的FIFO管道来处理来自所有并发 round 和客户端的消息。当一条消息在某个时间进入管道时,如果管道是空的,它可以立即处理,或者在等待轮到它处理时遇到一些延迟。

对于空管道,消息在时间$t_{fi}=t_{ei}+o$退出队列,其中 $o$ 是消息处理开销$m_s$或$m_d$,具体取决于消息是传出还是传入。但是,如果队列中已经有一条消息,那么$l_i$的处理将在某个队列等待时间$w_i$中暂停或阻塞,因此它将在时间$t_{fi}=t_{ei}+w_i+o$退出管道。要计算$w_i$我们需要知道消息$l_{i-1}$何时离开队列:$w_i=t_{fi-1}–t_{ei}$。反过来,退出时间$t_{fi-1}$依赖于$w_{i-1}$,因此我们需要先计算它。我们可以继续“展开”管道,直到有消息$l_n$而没有任何队列等待时间$w{i-n}=0$。我们可以计算该消息的出列时间$l_n$,这反过来又允许我们计算所有后续消息的退出时间。图1显示了管道堵塞的不同方式,以及随着时间的推移堵塞的影响。

图1.管道状态

与之前不同的是,今天我还想对与 communicating with the clients 的开销进行建模,因为在实践中,我们倾向于根据 clients 的观察来衡量绩效。这需要round模型来考虑客户机通信延迟$r_ c$,这是一个网络RTT。每轮 round 还向队列添加一个消息反序列化(客户端的请求)和一个消息序列化(回复客户端)。

让我总结一下我们建模排队 queuing 成本所需的参数和变量:

  • $r_c$ – RTT time to communicate with the client –与客户通信的RTT时间
  • $n_p$ – the number of parallel queues/pipelines. You can roughly think of this as number of cores you wish to give the node. 并行队列/管道的数量。您可以粗略地将其视为希望为节点提供的核心数量。
  • $s_p$ – pipeline’s service rate (messages per unit of time). $s_p=\frac{N+2}{Nμ_{md}+2μ_s}$ 管道的服务速率(每单位时间的消息数)
  • $w_i$ – pipeline waiting time for message $l_i$ 消息的管道等待时间
  • $R$ – throughput in rounds per unit of time. 单位时间内的吞吐量(单位:round)。
  • $μ_r$ – mean delay between rounds. $μr=\frac{1}{R}$ 每一轮 round 之间平均延迟
  • $σ_r$ – standard deviation of inter-round delay. 每一轮 round 延迟的标准偏差。

现在让我们更详细地讨论一下这些参数以及它们与模型的关系。

管道服务速率$s_p$ 表示管道处理消息的速度。我们可以通过查看消息序列化$\mu_{ms}$ 和反序列化/处理 $\mu_{md}$ 的平均延迟来获得这个指标。对于集群中的$N$ 个节点,我们可以找到轮$\mu_{msg}$ 的平均消息开销。对于给定的回合,leader节点需要处理2个消息序列化(一个用于启动该round,一个用于回复客户端,以及$N$ 个反序列化($N-1$来自追随者的 ,另一个来自客户端)。这个通信模式为 $\mu_{msg}=\frac{N\mu_{md}+2\mu_{ms}}{N+2}$ 。一个$\mu_{msg}$ 的倒数给出了管道在某个时间单位内可以处理多少条消息: $s_p=\frac{N+2}{N\mu_{md}+2\mu_{s}}$ 。

变量$w_i$ 表示管道在消息$l_i$ 时的支持情况。例如,$w_i=0.002 s$ 意味着消息$l_i$ 只有在0.002秒延迟后才能开始处理。图2说明了具有队列等待开销的 round 执行模型。

为了正确模拟 multi-paxos ,我需要看 multiple rounds。变量$R$ 定义了我试图通过集群推送的吞吐量,因为较高的吞吐量可能导致更长的队列等待时间。我还需要考虑到rounds 的分布情况。在频谱的一个方面,我们可以执行突发性的round (bursty rounds),所有的回合都在大致相同的时间开始。这将给我们带来最糟糕的 round 延迟,因为管道可能会阻塞更多。另一方面,各轮可以在时间上均匀分散,大大减少了不同轮之间对管道的竞争。这种方法将导致最佳 round 延迟。我在图3中说明了这两个极端的圆形分布。

Figure 3. Spacing between rounds.

然而,无论 rounds 如何分布,最大吞吐量 $R_{max}$ 都是相同的,它只受 节点到达pipline 饱和点时间 的控制:$R_{max}(N+2)=n_ps_p$或$R_{max}(N+2)=\frac{n_p(N+2)}{N\mu_{md}+2\mu_{ms}}$。同样地,$R_{max}=\frac{n_p}{N\mu_{md}+2\mu_{ms}}$。在实际的模型模拟中,由于管道变得非常拥挤,并且越来越多地延迟消息,延迟很可能比理论上的最大吞吐量点提前一点。

可能的 round distribution 可能是更随机的,因为不同的客户端相互独立地与协议交互,使得这种完美的 round synchronization 不可能实现。对于模拟,我采用统一分离方法 uniform separation approach ,并通过从正态分布 $\mathcal{N}(\mu_r,\sigma_r^2)$绘制 round separation times 为其添加一些可变性。这个解决方案可能并不完美,但正态分布在模拟许多自然随机现象时往往做得很好。我还可以通过改变方差来控制不同 round 之间的影响程度。当$\sigma_r$接近0时,这类似于uniformly spaced rounds,而较大的$\sigma_r$值会造成更多的“混乱”和 round 之间的冲突,这会使它们更加随机。

现在我要把所有的东西拼起来。为了模拟round 延迟$L_r$,我修改了旧的公式,以包括排队成本和客户端通信延迟。由于 round 延迟由处理消息$l_{q-1}$所需的时间决定,所以我只关心 quorum message 的队列等待时间$c_{q-1}$。因此,轮延迟的新公式是$L_r=(m_s+r_{lq-1}+c_{q-1}+m_d)+(m_{cd}+m_{cs}+r_c)$。在这个公式中,$m_{cd}$是客户端请求的反序列化开销,而$m_{cs}$是服务器回复客户端的序列化开销。

模拟结果

和以前一样,我有一个python脚本它将这些部分组合起来,模拟 multi-paxos 运行。在模型中有很多参数需要考虑,所以我将只展示一些参数,但是您可以获取代码并对其进行修改,以查看它在不同设置下的行为。图 4 显示了使用我的默认参数进行的模拟:网络设置取自 AWS measurements,管道性能取自早期paxi实现(现在它快得多)。只使用一个管道/队列。rounds 在时间上的分布由轮距 ( inter-round spacing ) $\mu_r=\frac{1}{r}$和$\sigma_{r}=2\mu{r}$控制。

图4. 延迟作为不同集群大小吞吐量的函数(模拟)

下一个图(图5)显示了 inter-round delay 延迟是如何变化的。具有更高标准偏差的运行($\sigma_r$)看起来更“弯曲”,而具有更均匀延迟的运行似乎不会很快退化,直到几乎达到饱和点。高$\sigma_r$运行代表了与集群的交互更随机、不协调,在我看来,这更能代表真实世界中发生的事情。

图5. 在5节点集群中,不同轮间时延参数下 inter-round delay parameters.,时延是吞吐量的函数。

我需要模拟Paxos Rounds吗?

上面的结果通过在管道中填充消息并计算每轮的队列等待时间来模拟多个单独的回合。对所有模拟 round 的延迟进行平均会产生某些给定吞吐量的平均延迟。但是,如果我可以计算出 quorum message 的平均队列等待时间和平均延迟,那么我就不再需要模拟各个 round 来获得这些参数。这将使我可以更快地找到average round latency 延迟,而不必一遍又一遍地重复循环公式计算。

让我们从计算quorum message $r_{lq-1}$的平均延迟开始。因为这个$l_{q-1}$代表组成仲裁所需的最后一条消息,所以我可以用一些使用从正态分布$\mathcal{N}(μl+μ_{ms}+μ_{md},σ_l^2+σ_{ms}^2+σ_{md}^2) $中采样的一些$k$来模拟这个消息的延迟 kth-order statistics,在大小为 $N-1$ 的样本上,其中$k=q−1$。为了使事情简单化,我使用蒙特卡罗方法相当快速,准确地估算了该数字$r_{lq-1}$。

现在来近似估计队列等待时间$w_{q-1}$。这有点复杂,但幸运的是排队论提供一些简单的方法来计算/估计简单队列的各种参数。我用了马歇尔的平均值(Marchal’s average)等待时间近似对于具有一般分布的到达间隔 inter-arrival 和服务间隔 service intervals (G/G/1)的单队列 single queue。这种近似值使我可以将模拟中的轮间间隔和方差(inter-round interval and variance)合并到排队理论模型计算中。

我将不必解释如何使用平均轮排队等待时间(average round queue wait time )的公式(这是非常直接的改编自在这里,服务和到达率(service and arrival rates)以每秒轮数表示( rounds per second)),并仅给出 single queue 和 single worker 的结果:

  • $p=R(N_{μ_{md}}+2μ_{ms})$。其中p是队列利用率。
  • $C_s^2=\frac{N^2\sigma_{md}^2+2^2\sigma_{ms}^2}{(N\mu_{md}+2\mu_{ms})^2}$
  • $C_a^2=\frac{\sigma_r^2}{\mu_r^2}$
  • $w=\frac{p^2(1+C_s^2)(C_a^2+C_s^2p^2)}{2R(1-p)(1+C_s^2p^2)}$

通过计算平均队列等待时间(average queue waiting time) 和 消息$l_{q-1}$周转的平均时间,我可以快速计算给定吞吐量的平均轮延迟时间(average round latency time ),而不必模拟多个轮来获得这些参数的平均值。$L=2\mu_{ms}+2\mu_{md}+r_{lq-1}+w+\mu_l$,其中$r_{lq-1}$是 quorum message $l_{q-1}$的平均RTT,$w$是给定吞吐量参数的平均队列等待时间,$\mu_l$是与客户端进行消息交换的网络RTT。

因此,平均轮延迟变为:

$L=2\mu_{ms}+2\mu_{md}+r_{lq-1}+\frac{p^2(1+C_s^2)(C_a^2+C_s^2p^2)}{2R(1-p)(1+C_s^2p^2)}+\mu_l$

图6显示了 模型 不同吞吐量下的延迟结果。排队论模型显示出与仿真非常相似的模式,尽管在较高的吞吐量下,仿真的退化速度比模型更快,尤其是对于3节点集群。这可能是由于这样一个事实,即模拟捕获了每一轮中的消息分布,而模型将该轮视为一个整体。

图6. 针对不同集群大小的延迟作为吞吐量函数的模型。

Flexible Quorums

我可以通过调整 quorums 数量使用 simulation and the model 来显示paxos和 flexible paxos(FPaxos)的不同。例如,我建模了一个9节点的 flexible paxos 部署,第2阶段quorum$q2$有3个节点。在我的设置中,flexible paxos仍然必须与所有9个节点通信,但是它只需要等待2个应答,因此它可以比 majority quorum更快地完成这一阶段。然而,如图7所示,与9节点 Paxos 的正常多数仲裁 majority quorum 相比,较小的仲裁量 smaller quorum 的优势微乎其微。尽管FPaxos要求的消息数量与5节点paxos设置相同,但是与所有9个节点进行通信的成本并不能使它在性能事件中更接近于7台机器的paxos群集。

图7 建模Paxos和FPaxos 9节点,| q2 |=3

结论和下一步行动

到目前为止,我已经在局域网中建立了single leader paxos变体的模型 single-leader paxos variants。我展示了网络变化对 majority quorum Paxo的影响微乎其微。我还说明了很难从灵活的qorum中获取性能优势,因为与大型集群通信的排队成本变得难以承受。然而,对于FPaxos来说,并不是所有的东西都丢失了,因为它可以将第2阶段通信中涉及的节点数量从完整的集群大小减少到只有$| q2 | $个节点,并大大减轻了大集群的队列等待时间的影响。

仿真和模型可在github,因此您可以检查它并修改参数,以查看性能如何响应变化。

paxos还有很多其他方面我觉得很有趣,并希望在将来进行建模。特别是,我想看看广域网部署、multi-leader paxos variants。WPaxos结合了multi-leader, WAN and flexible quorums。

您的大名:
万水千山总是情,给个打赏行不行。 打赏
原创文章,作者:gogobody ,如若转载,请注明出处:https://www.ijkxs.com/378.html
-- 展开阅读全文 --
WxFans 一款 typecho 微信公账号涨粉插件,支持动态验证码
« 上一篇 03-15
PAXOS性能建模-3
下一篇 » 03-19
广告

相关推荐

发表评论

V注册会员 L评论等级
R2 条回复
  1. 如意Lv.2 说道:

    今天没新帖,偷懒了

    1. avatargogobodyVLv.5 说道:

      @如意

      有的

没有更多评论了
作者信息
热门文章
标签TAG
热评文章