论文研究-基于(.pdf

所需积分/C币:9 2019-07-22 19:15:48 1.78MB .PDF
收藏 收藏
举报

NWR数据库的写延时估计,可用于发现实现集群构建和运行成本最小化的节点数量、副本因子的配置组合。现有基于基准测试或模拟队列的方法受限于特定的测试配置和测试环境,只能给出写延时随配置变动的粗略结果。从分析NWR数据库Cassandra的写操作的(n,r,k)fork-join队列结构入手,给出了该类队列期望逗留时间的解析解和NWR数据库写延时的理论模型,可用于建立更完备的写延时结论。分别在模拟队列和Cassandra集群上验证了(n,r,k)队列解析解和写延时模型的准确性。
468 计算机应用研究 第36卷 1.2指数服务时间队列的估计 误差项被积累到了估计值中。未来可以通过改进指数队列 鉴于独立同指数服务时间分布的(,讠,)fork-oin队列的.的估计方法来降低该误差。 期望逗留时间T,在较为准确的Nlsm估计方法,本文2 Cassandra写操作排队分析 在定理3中给出该类队列期望逗留时间的估计值。 定理3服务时间为独立同指数分布的非清除(n,r,h) Cassandra写操作的执行榘构如图3所示。其中:a)客户 端( Cassandra driver)向由n个节点构成的 Cassandra集群提交 fork-join队列的期望逗留时间:T"k≈min(max( NelsoN,,写操作请求,所连接的节点成为 coordinator;b) ordinator将写 LowT.,),UpT.)。其中 命令发送到存储有月标记录副本的r个节点上(即副本因子为 P 7)88 r);e)当 coordinator从副本节点收到的回复数量达到一致性要 Nelson lin4/E./1Inll, +4 p(2-h=1 求的下限k时,就给出客户端写完成的响应。当 coordinator本 身是副本节点时,称之为本地 coordinator,否则为远程 coordina- 12n-x tor。默认配置下,一条key- value记录顺时针连续地存放在集 群的r个节点上,其屮第1个节点的位置是通过对key进行散 S1n11H1+4p(H2-H1) k≥2 列确定的。这种存储划分方式可以基木保证各个节点存储同 H 等数量的key- value记录。 6 local coordinator h=1 aremote coordinator 12 k≥ response 上述公式中:H=∑为词和级数;H(m-n)= (-p 证明将文献[17的式(6)代人定理1可以得出T,的 具体估计值 Nelso俨,4:将文献[17的式(6)代入定理2的下 界可以得出1的下界Low1。很容易得出r个独立同指 图3 Cassandra写操作的执行架构 数分布的服务时间变量的第h次序统计量的期望E[X(A]= Cassandra内部采用SFDA( staged event- driven archites H,-H, 将该值代入定理2的上界得出UpTm3由于单独 tre)18的设计框架,将写操作表达为一个由 native- transport requests、 mutation、 requestResponse等步骤组成的串行操作序 使用 Nelson作为估计值可能带来较大的误差,本文采列。每个步骤包含一个处理线程池,空闲线程从一个事件到达 用上下界Lp⑦,、Low,对估计值进行了限定。 队列中取操作请求并执行,执行结果送入下一个步骤的到达队 如图2所示,本文采用模拟值(SM)对从定理3中得出的列。写操作的具体实现为:a)客户端的请求送到 coordinator的 估计值(APP)进行了验证。针对每组(n,r,h),本文给模拟 ative- transport- -requests阶段的到达队刎,该阶段首先获取目标 器 Fokulator-p(htp; github. com/excel wang/ forkulator-p)加副本所在的节点信息,然后通过 messagingService组件将写操 指定负载压力p)的作业到达流。当队列到达稳态后,以10%作传输到每个副本节点的 Incoming队列b)副本节点上的mu 的采样率获得100样本作业的延时均值为模拟值。误tiom阶段从 Incomin队列中获取并执行写清求(追加cm 差率的计算公式为sM-1 milos和写 A memtable);c)副本节点通过 messagingservice组 0 件将写操作的执行结果传输回 coordinator的 Inc oming队列;d) 挡AA。A coordinator的 requestResponse阶段读取并计算 Incoming队列屮 答复写操作的消息数量;e)若该数量达到一致性水平要求的 下限,则向客户端发出最终响应。由于上述各阶段的队列长度 _ -+SIM 0(-7-APPp: 0.6-+ p: 0.8-*-Arr p: 0.8-S[M p: 0.9*- Appp.0.9-+-SIM p: 0.95*APP/: 0.951 上限为231-1,所以当不对操作施加 timeout限制时,所有阶段 的到达队列都可近似为非损失制。 探10x 如上所述, Cassandra写操作的执行过程非常适合采用本 SIM 001--APPp: 0.01-+-SIM p: 0.2--APP p: 0.3- -SIM 4: 0.4-+APP 004-+SIM 0: 0.5-xAPP p: 0 文定义的非清除(n,r,k)fork-join队列进行描述。木文将写操 ¥ 作的每个内部执行步骤视为队列服务过程的一部分,得出如图 4所示的简化 Cassandra写操作排队模型。 cassandra客户端可以设置不同的负载均衡策略来控制 的能上是 CHESED ac是E是 22 A22228总 图2报务时间为独立同指数分布的非清除(n,rkok-join队列的 coordinator的选取: oken aware policy优先使用本地 coordinator, 朗望逗留时间的模拟值(SIM与估计值(APP的对(=1 若所有本地 coordinaton过载,则尝试使用远程 coordinator; 从图2中可以看出,与模拟值对比,估计值的误差在大部 undrobinPalicy等概率选取集群中的所有节点作为 coordina- 分情况下较为可控。只有当负载特别重(p>0.8)且k<2时tr; nost FilterPolicy可以指定具体节点做 coordinator由于本地 coordinator下的写操作(本地写)的服务时间远小于远程coor 误差较为明显(>25%)。这是由于当p较大时,通过 Nelson dinator下的写操作(运程写)的服务时间,写延时模型必须反 估计方法得出的72的误差较大;而当k较小时,更多的2.,映本地写的比例。据此本文得出如下写延时模型。 第2期 王华进,等:基于(n,r,k) fork-join队列分析的NWR数据库写延时模型 469 变动,一致性水平从one(k=1)、 quorum(k="+1)、al(h= )中选取,施加的目标负载压力标记为A。本文为各副本因子 预先创建个表空间( keyspace),并各存人I亿条key-vlue 记录 B 为获取定理4给出的延时模型的输入参数,并详细界定该 延时模型的适用范围,本文设计∫微测试和扩展测试两种实验 方案 3.1微测试 response for write A 微测试在不同副本因子、一致性水平、负载压力、负载均衡 (a远程写 (b)本地写 策略下大量重复执行针对同一个key- value记录的写操作,以 图4 Cassandra写操作的简化ork-join排队模型 a)获取延时模型的输入参数L/:和R7,;b)校验基于(n,r, 定理4运行在一个同质集群上的 Cassandra数据库的写k)fkin队列的简单形式(r,r,k)队列的延时模型估计Gas- 摸作期望延时模型为 数据库单写操作延时的适用性。其中,负载均衡策晔 !×L72,x,k+(1-D)×R 是基于 hostFilter Policy定制实现的全部本地写策略( local)和 其中 全部远程写策略 )。这两种策略对应的延时模型!参 R7A=SW“RT2 数值分别为1和0。 每种配置组合的测试结果抽样率为1%,样本数为 k=1 60000。实验结果如图5所示。延时模型的估计值( approx) 1,41 RT k≥2 较为接近测出值( bench),基本验证了延时模型估计单一写操 模型输入参数:a)l为本地写的比例:)1.为本地写在作延时的适用性,其中误差率的计算为mn-1汁意:图中 负载压力为,节点数、副本因子、致性水平均为时的期的A只是测试程序施加的压力目标,受限于 Python测试脚本 自身的开销、基丁 sleep()函数间隔相邻操作的精度、 Cassandra 望延时;c)7.(k-1≤i≤r)为远程写在负载压力为,节点集群的实际处理能力,实际负载压力要低于目标压力。 TTTTTT I 数(不计入 coordinator节点)、副本因子、致性水平均为i时 800 的期望延时。上述参数共计r-k+4个。 60 司40 参数!可以从负载均衠策略中推出,如 roundRobin Policy黜 丫 T appro=5|2 bench:=102400 ×→ppmx2=102400 对应的l=—、轻量级负载下 tokena ware Policy对应的l=1;参 数Lp和R,既可以从本地写/远程写的服务时间的概率分 布中估算得出(参见1.2节,即一般服务时间分布的(i,i,i)队 刎的期望逗留时间的估计方法19),也可以用基准测试测得 A=51200 102400 的延时样本均值佔计。 0.1 3实验 本文通过实验测得由六个同质节点组成的 Cassandra集群 在不同副本因子(r)、一致性水平(k)、负载均衡策略(l)、负载 压力(ρ)下的写延时,并与基于定理4的延时模型得出的估计 图5估计值与微测试测出值的对比 值进行比较,以验证延时模型的适用性。其中 (ocal全部本地写, remote:全部远程写) a)测出值通过 Cassandra自带的杳询追踪(trc功能得3.2扩展测试 出,其精度为微秒级(10-6s);出于查询造踪本身的开销不可忽 扩展测试在不同副本因子、一致性水平、负载压力、负载均 咯,本文限定一个写操作被追踪的概率不大丁6%;测试中,每衡策略下大量执行混合在一起的针对不同 kev-value记录的写 秒提交写操作的数量标记为A写操作的提交间隔依照指数分操作,以:a)获取延时模型的输入参数L万,和R点;b)校验 布exp(A)选取。 Cassandra写延时模型估计混合写操作延时的适用性。混合测 b)预测值将通过从集群测出的LP1和R72,等参数值代试负载的构造确保了每个节点等慨率地成为 coordinator,且承 入定理4得出。 受同等压力的副木写入请求,以尽可能反映实际场景下负载在 为了得出可比较和可重复的测出值,本文尽可能固定除副各节点上的均衡分配特性。其中,被测试的负载均衡策略包括 本因子、一致性水平、负载压力、负载均衡策略之外的变量(如全鄙本地写、全部远程写和 roundRobin Policy。这种策略对 写操作的数据量),并采用六台位于同一机架的相同配置的物应的延时模型l参数值分别为10r/n 理机节点作为测试床。每个测试节点的配置为:双路 ntel Xe 每种配置组合的测试结果抽样率为6%,全部本地写、全 onES26033处理器、64GB内存、3.6TB机械磁盘、万兆以太部远程与、 roundRobin Policy的样本数分别为4200.60000 网互连。测试用 Cassandra版木为3.1.0。副木囚子在1~54200。实验结果如图6所示。延时模型的大部分估计值(ap 470 计算机应用研究 第36卷 prox)非常接近测出值( bench).基本验证了延时模型估计混合鲁棒的一般服务时间(,,i)队列的估计方法。 写操作延时的适用性。注意:图中的λ同样为日标值,实际达 成的负载压力水平低丁该值。 5相关工作 运60米美美 ¥ 5.1 fork-join队列分析 率美卖雯 答浜派翠 虽然(,i,)队列是最基本的 fork-join队列,当i>2时其 1g000 期望逗留时间仍然没有确切的解析解,只有一些估计方法存 在。例如, Nelson等人「给出∫指数服务时间分布的(i,i,i) 滑总 8影 队列的期望逗留时间估计式;针对服务时间分布较为一般的 (i,i,)队列, Varma等人提出了基于插值的估计方法,Tho 0 人=18000 maslan等人0提出了基于测试结果回归分析的的估计方法 0.1·:·: Rik等人给出了基于鞅( martingales)的上界, Fidler等人 -0.1 给出了多步骤lork-join队列网络的上下界。本文提出的延时 模型的准确性依賴于上述估计方法的准确性。 对于清除型(r,r,k)队列的期望逗留时间,仅当k=1时存 1点21距2在确切的解析解;k>2时仅存在较为粗略的上下 图6估计值与扩展测试测出值的对比 界1::;对于非清除(r,r,k)队列的期望逗留时间, Fidler等 ocal:全部本地写, remote全部远程写,RR: undRobinPolicy) 人2给出了较为粗略的非渐进统计型上下界,Wamg等人° 值得注意的是,图6中的基准测试测岀值和延时模型佔给出了基十线性变换的确切解析解,并用该解改进了清除型 计值均显示了在相同副本齿子、一致性水半,负戳压力下,全部(r,,h)队列的期望逗留时间的上界。 本地写、 round Robin policy、全部远程写这种负载均衡策略的 针对n≠r的一般(n,r,k)队列的期望逗留时间, Joshi等 写延时呈递增趋势。从该结果可以推断出 token Aware Policy均 人给出了清除型队列的上下界。本文在Wng等人1工作 衡策略(该策略与全部本地写策略相近,值均为1)要优于的基础上第一次给岀了非清除(n,r,k)队列的确切解析解。 roundrobin Policy均衠策略。 5.2NWR数据库延时分析 4讨论 目前针对 Cassandra等NWR数据车的操作延时分析,主 如引言所述,该理论模型的输入参数为最高一致性水平 要分为基十基准测试的方法和基于模拟队列的方法。 (W=y)下的写操作在不同配置组合下的期望延时,输出为各 通过基痄测试分析NwR数据库性能的I作。采用主 种较弱一致性水平(W=1,2,…,N-1)下的写操作在相关配流的分布式数据库基准测试工具YCSB23),分析包括节点数 置组合下的期望延时的估计值。如第3章所述,文采用基准量、副本因子、一致性水平、负载压力等配置变量对读写操作延 测试测出理论延时模型的输人参数。显然,在进行同等开销的时的影响。限丁基准测试不能穷尽所有的配置组合,这些工作 基准测试时,理论廷吋模型可以得出比仅来用基准测试多N 只是各自给出了延时随配置变量变动的粗略趋势。此外,测试 倍的延时结论。 结果是基于特定负载下的特定集群得出的,并不能证明其结论 第3章初步验证了本文提出的NWR数据库理论延时模具有普遍适用性(完备性)。与之相比,本文给出综合了各配 型的准确性,但通过基准测试获取模型参数的开销铰大。更为置变量的通用写延时理沦模型。基准测试只是用来获取模型 理想的方案是,只需通过实验测出无压力下本地写和远程写操的参数捡证模型适用性的辅助手段。 作的服务时间分布,然后借助该分布计算出上述参数在各种负 通过模拟队列分析NWR数据库性能的卞要思路是:a)基 载压力下的估计值。 于对目标数据库读写操作过程的详细分析,建立与之等价的模 目前独立同指数服务时间分布的(i,i,讠Dork-in队列的 拟队列网络( queue network);b)通过基准测试确定模拟队列的 期望逗舀时间存在较为准确的估算方法,但本文实验测出 服务时间、閃络传输延吋等各种参数;c)针对一些配置变量组 的服务时间分布并不符合指数分布(图7)。 合运行模拟队列,以获取目标配置下的延时。例如 huang等 0005 人详细分析了 Cassano写换作的执行过程和队列结构;Os- 0.004 man等人。详细分析了 Cassandra的读操作的队列结构,并使 餐0003 0002 用 queueing Petri nels对其模拟。其他相关工作有文献L9~ 13]。相比基准测试,这类工作减轻了测试的运行开销,但由 0.00 0000 于模拟队列的结构很难宄全反抉真实集群的内部结构,其参数 4006008001000120014001600 延时 也很难概括真实集群在各类负载下的实际值,导致基于模拟队 图7 Cassandra集群的远程写服务时间分布(样本量5000 列测试结果的可靠性要差于基准测试。此外,其结论同样是粗 尽管对于一般服务时间分布的(i,,队列存在一些某于略且不完备的 插值和回归2的估计方法,但其准确性依赖于所测出的服6结束语 务时间分布的精度。受限测量精度,本文测出的服务时间的 分布并不十分稳定。这也是目前fork-jin队列的理论研究(如 由于NWR数据库的广泛应用,对该类数据库的性能分 文献[14,21])鲜有能被实际集群验证的原因,大部分工作只析,尤其是节点数量、副木囚子、一致性水平、负载压力对读写 是给出了在模拟队列上的验证。未来笔者将进一步研究更为操作延时的影响日显重要。现有基于基准测试或模拟队列的 第2期 王华进,等:基于(n,r,k) fork-join队列分析的NWR数据库写延时模型 471 分析方法存在结论粗略、完备性欠缺等问题。本文首先从分析 tional Conference on Global Software Engineering Workshops. Pisca NwR数据库写操作的排队模型——非清除(n,r,k)fork-join队 tawny. NJ: IEEE Press, 2015: 27-34 列入于,第一次给出∫该类队列的期望逗留时间的解析解,并12 Dipietro S, Casale g, Serazzi g. A queueing network model for per 在独立同指数服务时间分布的模拟(n,r,k)队列上验证了解析 formance prediction of apache Cassandra C//Proc of the 10th EAI 解的准确性;然后基于上述解析解,第一次给出了NWR数据 International Conference on Performance Evaluation Methodologies 库的理论延时模型。该模型可以反映不同节点数量、副木囚 and Tools. New York: ACM Press, 2017: 186-193 于、一致性水平、负载压力、鱼载均衡略对写延时的影响。模[13] Huang Xiangdong, Wang Jiamin, Qiao Jialin, et aL. Performance and replica consistency simulation for quorum-based NoSQL system cas- 型的输入为最高一致性(all)下的期望延时的基准测试测出值 sandra[ C]//Proc of International Conference on Applications and 或理论估计值,输出为其他一致性(one、 quorum等)下的期望 Theory of Petri Nels and Coneurreney. Piscalaway, NJ: IFFE Press 延时估计值。相较已有工作,基于该模型得出的结论更为详细 2017:78-98 和完备。本文在NWH数据库 Cassandra的真实集群上验证了[l4] Joshi g, Soljanin e, Wornell. Efficient redundancy techniques for 写延时模犁的适用性 latency reduction in cloud systems LJ.. ACM Trans on Modeling 未来的斫究方向包括:a)借助非清除(n,r,k)队列的期望 and Performance Evaluation of Computing Systems, 2017, 2 逗留吋间的解析解,改进清除型(n,r,k)队列的期望逗留吋间 的上界;b)借助 limited processor sharing(LPS)排队理论2,将 [15 Wang Weina, Harchol-Balter M, Jiang Haotian, et al. Asymptotic re- cassandra seDa每个阶段的线程池的大小纳入延时樸型,从而 sponse lime analysis for muilti-lask parallel jabs[ EB/L..(2017 10-27)[2017-11-12].htps:// arxIV. org/pdf//1710.00296.pdi. 使其可以反映不同线程数对写延时的影响;c)更为鲁棒的 [16 Wang Huajin, Li Jianhui, Shen Zhihong, et aL. Approximations and 股服务时间(i,,队列的期望逗留时间估计方法,从而进 bounds for (n, h)fork-join queues: a linear transformation approach 步减少延时模型的输入参数;d)更为综合的负载(不同读写比 EB/OL.(2017-09-08)[2017-09-12].htps:// arxI\.org/abs 例、访问数据的分布、整体数据的分布)的延时模型;e)满足 1707,08860 SLA延时要求,且能够实现集群构建和运行成本最小化的节点[17] Nelson r, Tantawi N. Approximate analysis of fork/ join synchron 数和副本因子的配置组合的计算方法。 . alion in parallel queues[ J]. IEEE Trans on Computers, 1988, 37 参考文献 (6):739-743 [18 Welsh M, Culler 1, Brewer E. Seda: an architecture for well-condi I 11 Decandia G, Hastorun D, Jampani M, ct al. Dynamo[ J 1. ACM tioned, scalable internet services[ J. ACM SIGOPS Operating SIGOPS Operating Systems Review, 2007, 41(6): 205-220 Systems Review [2] Lakshman A, Malik P. Cassandra[ J]. ACM SIGOPS Operating [191 Varma 5. Makowski A M. Interpolation approximations for symmetric Systems Review, 2010, 44(2): 35-40 fork-join queues [ J. Performance Evaluation, 1994, 20(1-3) [3 Dede F, Sendi Kuzlu p el u. An evaluation of cassandra for 245-265 Hadoop[C//Proc of IEEE International Conference on Cloud Com 20 1 Thomasian A, T'antawi A N. Approximate solutions for m/g/l fork/ join synchronization[ C]//Proc of Winter Simulation Conference. can [4 Wang Huajin, Li Jianhui, Zhang Haiming, et al. Benchmarking rep Diego Society for Computer, 1994: 361-368 lication and consistency strategies in cloud serving databases hbase [211 Joshi C. Liu Yanpei, Soljanin E. Coding for fast content download and cassandra[ C_//Proc of Workshop on Big Data Benchmarks [C//Proc of the 50th Annual Allerton Conference on Communica Performance Optimization, and Emerging Hardware. Cham: Sprin tion,Control, and Computing. Piscataway, NJ IEEE Press, 2012 ger,2014:71-82 [5J Kuhlenkamp Klems M, Ross O. Benchmarking scalability and [22] Rizk A, Poloczek F, Ciucu F. Computable bounds in fork-join elasticity of distributed database systems[ C]//Proc of VLDB Endow queueing systems[ C ]//Proc of ACM SIGMETRICS International ment. New York: ACM Press, 2014: 1219-1230 Conference on Measurement and Modeling of Computer Systems. New [6 luang Xiangdong, Wang Jianmin, Yu PS, et al. An experimental York. ACM Press 2015: 335-346 study on tuning the consistency of NoSQL systemsL J]. Concurrency [23] Fidler M, Jiang Yuming. Non-asymplotic delay bounds for (k, I) and Computation Practice and Experience, 2017. 29(12): doi fork-join systems and multi-stage fork-join networke[C]//Proc of the 0.1002/cpe.4l29 35th Annual IEEE International Conference on Computer Communica- [7] Huang Xiaodong, Wang Jiamin, Bai Jian, el al. Inherent replica in lions. Piscataway. J: IFFF. Press, 2016 consistency in cassandra[ C]//Proc of IEEE International Congress [24] Lee K, Pedarsani R, Ramchandran K. On scheduling redundant re- on Big Data. Piscataway, NJ: IEEE Press, 2014: 740-747 quests with cancellation overheads[ J].IEEE/ ACM Trans on Net- [81 Osman R, Piazzolla P. Modelling replication in NoSQL data stores working,2017,25(2):1279-1290 L CJ//Proc of International Conference on Quantitative Evaluation of [ 25] Gardner K, Zbarsky S, Doroudi S, et al. Reducing latency via re- Systems. Cham: Springer, 2014: 194-209 dundant requests: exact analysis C//Proc of ACM SIGMETRICS [9 Gandini A, Gribaudo M, Knottenbelt W J et al. Performance evalua International Conference on Measurement and Modeling of Computer tion of NoSQL databases[C]//Proc of European Workshop on Per Systems. New York: ACM Press, 2015 347-360 formance e g. Cham: Springer, 2014: 16-29 [26] Cooper B F, Silberstein A, Tam E, et al. Benchmarking cloud ser- [10 Perez-Miguel C, Mendiburu A, Miguel-Alonso J. Modeling the avai ving systems with YCSB[ C//Pre lability of Cassandra[ J. Journal of Parallel and Distributed Com- Cloud Computing. New York: ACM Press, 2010: 143-154 , puting,2015.6(12):294 I 27 Towsley D, Rommel C G, Stankovic J A. Analysis of fork-join pro- Niemann R. Evaluating the performance and energy consumption of ram response times on multiprocessors J]. IEEE Trans on Parallel dislributed dal:a management syslems[C]//Proc of the: 10th Interna- and Distributed Systems, 1990, 1(3): 286-303

...展开详情
试读 6P 论文研究-基于(.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-基于(.pdf 9积分/C币 立即下载
1/6
论文研究-基于(.pdf第1页
论文研究-基于(.pdf第2页

试读结束, 可继续阅读

9积分/C币 立即下载 >