计算机科学 ›› 2020, Vol. 47 ›› Issue (11): 286-293.doi: 10.11896/jsjkx.191200072
郭子亭1,2, 张文力1, 陈明宇1,2,3
GUO Zi-ting1,2, ZHANG Wen-li 1, CHEN Ming-yu1,2,3
摘要： 研究表明,在大规模的网络服务系统中,网络延迟往往表现出长尾效应,即存在一定比例的延迟远大于网络的平均延迟。延迟的长尾引起了广泛的关注,长尾效应会严重影响用户体验和内容供应商收益,尤其在对延迟敏感的大型交互式网络应用中。因此,网络服务系统研究的重点经历了从关注吞吐量和平均延迟到关注系统的尾延迟的变化。然而,现有的理论模型大多关注平均延迟,难以用来分析网络服务延迟的尾部特征,复杂网络服务中的尾延迟时间计算缺乏形式化的建模和计算方法。文中提出了一种将复杂的网络抽象为以M/M/1排队模型为基础的排队网络模型的方法,在该模型的基础上给出了串联、并行场景下逗留时间尾延迟分布的表达式,同时分析了当模型中个别子部件发生变化时对系统整体尾延迟的影响,并将模型预测结果和仿真网络的结果进行对比,误差不超过2%。
中图分类号:
| [1] DEAN J,BARROSO L A.The tail at scale[J].Communications of the Acm,2013,56(2):74-80. [2] JALAPARTI V,BODIK P,KANDULA S,et al.Speeding up distributed request-response workflows[J].ACM SIGCOMM Computer Communication Review,2013,43(4):219-230. [3] DECANDIA G,HASTORUN D,JAMPANI M,et al.Dynamo:amazon's highly available key-value store[J].ACM SIGOPS Operating Systems Review,2007,41(6):205-220. [4] HE Y,ELNIKETY S,LARUS J,et al.Zeta:Scheduling interactive services with partial execution[C]//Proceedings of the Third ACM Symposium on Cloud Computing.2012:1-14. [5] YI J,MAGHOUL F,PEDERSEN J.Deciphering mobile search patterns:a study of yahoo! mobile search queries[C]//Procee-dings of the 17th International Conference on World Wide Web.2008:257-266. [6] XU Y,MUSGRAVE Z,NOBLE B,et al.Bobtail:Avoiding Long Tails in the Cloud[C]//Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation.USENIX Association,2013:329-342. [7] NISHTALA R,FUGAL H,GRIMM S,et al.Scaling Memcache at Facebook[C]//Usenix Conference on Networked Systems Design and Implementation.USENIX Association,2013:385-398. [8] BARROSO L A,DEAN J,HOLZLE U.Web search for a pla-net:The Google cluster architecture[J].IEEE Micro,2003,23(2):22-28. [9] SURESH L,CANINI M,SCHMID S,et al.C3:Cutting tail latency in cloud data stores via adaptive replica selection[C]//12th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 15).2015:513-527. [10] DELIMITROU C,KOZYRAKIS C.Amdahl's law for tail latency[J].Communications of the ACM,2018,61(8):65-72. [11] ALESAWI S,NGUYEN M,CHE H,et al.Tail Latency Prediction for Datacenter Applications in Consolidated Environments[C]//2019 International Conference on Computing,Networking and Communications (ICNC).IEEE,2019:265-269. [12] MIRHOSSEINI A,WENISCH T F.The queuing-first approach for tail management of interactive services[J].IEEE Micro,2019,39(4):55-64. [13] LUMB C R,GANGER G R,GOLDING R.D-SPTF:Decentra-lized Request Distribution in Brick-based Storage (CMU-CS-03-202)[J].Acm Sigops Operating Systems Review,2004,39(11):37-47. [14] VULIMIRI A,GODFREY P B,MITTAL R,et al.Low latency via redundancy[C]//Acm Conference on Emerging Networking Experiments & Technologies.ACM,2013. [15] WU Z,YU C,MADHYASTHA H V.CosTLO:Cost-Effective Redundancy for Lower Latency Variance on Cloud Storage Services[C]//Usenix Conference on Networked Systems Design & Implementation.USENIX Association,2015. [16] LI J,SHARMA N K,PORTS D R K,et al.Tales of the tail:Hardware,os,and application-level sources of tail latency[C]//Proceedings of the ACM Symposium on Cloud Computing.ACM,2014:1-14. [17] JACKSON J R.Networks of waiting lines[J].OPER.RES.,1957,5(4):518-521. [18] NGUYEN M,LI Z,DUAN F,et al.The tail at scale:how to predict it?[C]//Usenix Conference on Hot Topics in Cloud Computing.USENIX Association,2016. [19] THOMASIAN A.Analysis of fork/join and related queueing systems[J].ACM Computing Surveys (CSUR),2014,47(2):1-71. [20] NELSON R,TANTAWI A N.Approximate analysis of fork/join synchronization in parallel queues[J].IEEE transactions on computers,1988,37(6):739-743. [21] CHEN R J.A hybrid solution of fork/join synchronization inparallel queues[J].IEEE Transactions on Parallel and Distributed Systems,2001,12(8):829-845. [22] BALSAMO S,DONATIELLO L,VAN DIJK N M.Bound performance models of heterogeneous parallel processing systems[J].IEEE transactions on parallel and distributed systems,1998,9(10):1041-1056. [23] CHEN R J.An upper bound solution for homogeneous fork/join queuing systems[J].IEEE Transactions on Parallel and Distributed Systems,2010,22(5):874-878. [24] RIZK A,POLOCZEK F,CIUCU F.Computable bounds in fork-join queueing systems[C]//Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Mo-deling of Computer Systems.2015:335-346. [25] NGUYEN M,ALESAWI S,LI N,et al.Forktail:a black-box fork-join tail latency prediction model for user-facing datacenter workloads[C]//Proceedings of the 27th International Sympo-sium on High-Performance Parallel and Distributed Computing.2018:206-217. [26] QIU Z,PÉREZ J F,HARRISON P G.Beyond the mean in fork-join queues:Efficient approximation for response-time tails[J].Performance Evaluation,2015,91:99-116. |
| [1] | 王子凯, 朱健, 张伯钧, 胡凯. 区块链与智能合约并行方法研究与实现 Research and Implementation of Parallel Method in Blockchain and Smart Contract 计算机科学, 2022, 49(9): 312-317. https://doi.org/10.11896/jsjkx.210800102 |
| [2] | 魏恺轩, 付莹. 基于重参数化多尺度融合网络的高效极暗光原始图像降噪 Re-parameterized Multi-scale Fusion Network for Efficient Extreme Low-light Raw Denoising 计算机科学, 2022, 49(8): 120-126. https://doi.org/10.11896/jsjkx.220200179 |
| [3] | 高雅, 赵宁, 刘文奇. 串联排队系统中各服务站间的关联性分析 Dependence Analysis Among Service Stations in Tandem Queueing Systems 计算机科学, 2022, 49(7): 304-309. https://doi.org/10.11896/jsjkx.210500218 |
| [4] | 陶礼靖, 邱菡, 朱俊虎, 李航天. 面向网络安全训练评估的受训者行为描述模型 Model for the Description of Trainee Behavior for Cyber Security Exercises Assessment 计算机科学, 2022, 49(6A): 480-484. https://doi.org/10.11896/jsjkx.210800048 |
| [5] | 宗迪迪, 谢益武. 基于法线迭代的模型中轴生成方法 Model Medial Axis Generation Method Based on Normal Iteration 计算机科学, 2022, 49(6A): 764-770. https://doi.org/10.11896/jsjkx.210400050 |
| [6] | 陈鑫, 李芳, 丁海昕, 孙唯哲, 刘鑫, 陈德训, 叶跃进, 何香. 面向国产异构众核架构的CFD非结构网格计算并行优化方法 Parallel Optimization Method of Unstructured-grid Computing in CFD for DomesticHeterogeneous Many-core Architecture 计算机科学, 2022, 49(6): 99-107. https://doi.org/10.11896/jsjkx.210400157 |
| [7] | 罗俊仁, 张万鹏, 陆丽娜, 陈璟. 即时策略博弈在线对抗规划方法综述 Survey on Online Adversarial Planning for Real-time Strategy Game 计算机科学, 2022, 49(6): 287-296. https://doi.org/10.11896/jsjkx.210600168 |
| [8] | 刘林云, 陈开颜, 李雄伟, 张阳, 谢方方. 基于卷积神经网络的旁路密码分析综述 Overview of Side Channel Analysis Based on Convolutional Neural Network 计算机科学, 2022, 49(5): 296-302. https://doi.org/10.11896/jsjkx.210300286 |
| [9] | 王奇, 王刚桥, 陈永强, 刘奕. 面向社会计算的集成建模方法与应用系统 Integrated Modeling Method and Application System for Social Computing 计算机科学, 2022, 49(4): 25-29. https://doi.org/10.11896/jsjkx.210900257 |
| [10] | 刘江, 刘文博, 张矩. OpenFoam中多面体网格生成的MPI＋OpenMP混合并行方法 Hybrid MPI+OpenMP Parallel Method on Polyhedral Grid Generation in OpenFoam 计算机科学, 2022, 49(3): 3-10. https://doi.org/10.11896/jsjkx.210700060 |
| [11] | 李家振, 纪庆革. 动态低采样环境光遮蔽的实时光线追踪分子渲染 Dynamic Low-sampling Ambient Occlusion Real-time Ray Tracing for Molecular Rendering 计算机科学, 2022, 49(1): 175-180. https://doi.org/10.11896/jsjkx.210200042 |
| [12] | 刘俊鹏, 苏劲松, 黄德根. 融合特定语言适配模块的多语言神经机器翻译 Incorporating Language-specific Adapter into Multilingual Neural Machine Translation 计算机科学, 2022, 49(1): 17-23. https://doi.org/10.11896/jsjkx.210900005 |
| [13] | 许华杰, 张晨强, 苏国韶. 基于深层卷积残差网络的航拍图建筑物精确分割方法 Accurate Segmentation Method of Aerial Photography Buildings Based on Deep Convolutional Residual Network 计算机科学, 2021, 48(8): 169-174. https://doi.org/10.11896/jsjkx.200500096 |
| [14] | 傅天豪, 田鸿运, 金煜阳, 杨章, 翟季冬, 武林平, 徐小文. 一种面向构件化并行应用程序的性能骨架分析方法 Performance Skeleton Analysis Method Towards Component-based Parallel Applications 计算机科学, 2021, 48(6): 1-9. https://doi.org/10.11896/jsjkx.201200115 |
| [15] | 何亚茹, 庞建民, 徐金龙, 朱雨, 陶小涵. 基于神威平台的Floyd并行算法的实现和优化 Implementation and Optimization of Floyd Parallel Algorithm Based on Sunway Platform 计算机科学, 2021, 48(6): 34-40. https://doi.org/10.11896/jsjkx.201100051 |
|
||
首页