排队论及其应用浅析

排队论及其应用浅析——QueueingTheory网易杭研：何登成新浪微博：何_登成H1391大纲(一)•排队–现实生活中–计算机领域•排队论浅析–排队论问题分析–OperationalLaw•UtilizationLaw•Little’sLaw–D.G.Kendall–Little’sLaw–Erlang’sFormula大纲(二)•排队论应用分析–更好的理解系统监控•LinuxI/OStats–更好的架构选型–排队论与Performance•什么是Performance？•何谓平衡的系统？•如何监控系统？•如何进行高性能程序设计？–容量规划（入门）排队问题•在排队过程中，人们会关心哪些问题？–什么时候过去，排队的时间会比较短？–不排队的话，需要多少时间？–是否需要排队？–(不)包括正在被服务的人，我前面一共还有几人？–排到我需要多少时间？等我服务结束，又需要多少时间？–这次排队是否合算？–队伍长队达到什么程度，我就会放弃本次排队？–系统有多少个窗口？是否已经高负荷运转了？•无论是现实中的排队，电话通讯领域的排队，还是计算机领域的排队，最后都能够抽象化为一个经典的理论——排队论(QueuingTheory)。•排队论起源于20世纪初的电话通话。1909—1920年丹麦数学家、电气工程师爱尔兰（A.K.Erlang）用概率论方法研究电话通话问题，从而开创了这门应用数学学科，并为这门学科建立许多基本原则...•Erlang在电话通讯领域，解决了两个基本问题：电话损失率(Erlang-BFormula)，电话等待概率(Erlang-CFormula)。在介绍这些之前，让我们先来认识D.G.Kendall与J.D.C.Little...QueueingTheory•排队论用于解决什么问题？–核心问题•对用户来说：响应时间(满意度)•对服务提供者来说：利用率(成本)•在保障用户满意度的前提下，最大限度的控制成本，充分挖掘系统的潜力。QueueingTheory(形式化)•什么时候过去，排队的时间会比较短？–达到请求的分布；单位时间平均到达请求数量：•不排队的话，需要多少时间？–服务时间(ServiceTime)；单位时间平均完成的服务数量：•是否需要排队？•(不)包括正在被服务的人，我前面一共还有几人？–平均队列长度(不包括正在服务的人：)•排到我需要多少时间？等我服务结束，又需要多少时间？–WaitTimevsReponseTimeor•队伍长队达到什么程度，我就会放弃本次排队？–服务丢失率：；队列最大长度；•系统有多少个窗口？是否已经高负荷运转了？–窗口数量；利用率；qLBPqWWULRUtilizationLaw•UtilizationLaw•排队系统中，Server的利用率，为平均到达速率与平均服务速率的比值；–UtilizationLaw解读•保持Server的平均服务速率不变，平均到达速率越高-Server利用率越高；•保持平均到达速率不变，Server的平均服务速率越高-Server利用率越低；–一个简单的证明(求下面这个系统的利用率)/ULittle’sLaw•Little’sLaw•排队系统中，队列长度(包括正在接受服务的人)=到达率*平均响应时间•由J.D.C.Little在1961年的论文【AProoffortheQueuingFormulaL=λW】中给出形式化的证明；•证明：略•变种：排队长度=到达率*平均等待时间（）–Little’sLaw解读•Little’sLaw/UtilizationLaw，均属于OperationalLaws中的一种；•平均响应时间越长，队列长度也越长；•单位时间到达的请求越多，队列长度越长；•符合日常的理解；•平均请求数量，已知中的任何一个，都可以计算出另外三个；WLqqWL1WWqWWLLq,,,Little’sLaw（续）•Little’sLaw的应用场景–最基础的Law，对请求到达/离开的分布没有特殊要求；–超市、银行、KFC等管理•SixSigma（六西格玛管理法）–系统性能监控–...Little’sLaw（例1）•一个小酒馆，客户平均访问频率为40人/小时；–客户在小酒馆的平均消费时间是15分钟；•问题：请问小酒馆的平均客户数量是多少？•解答：–：40人/小时–：0.25小时/人–：40*0.25=10WWLLittle’sLaw（例2）•一证券经纪公司，其网站有110万注册用户。高峰期，同时有20000用户在线。同时观察到，在高峰期网站一小时处理360万笔业务。•问题：请问处理每笔业务的响应时间是多少？•解答：–：3600000/3600=1000笔/秒–：20000–：20000/1000笔/秒=20秒/笔L/LWLittle’sLaw（例3）•公式：–avgqu-sz=(r/s+w/s)*await/1000=(173.83+39.22)*11.67/1000=2.49–%util=(r/s+w/s)*svctm/1000=(173.83+39.22)*0.28/1000=6%KendallNotation•六元组–A/S/c/K/N/D•现实中所有系统的形式化模型；–解读•A：到达请求的分布–M(exponential/Markov)；D(Deterministic)；G(General)；...•S：服务时间的分布–M(exponential/Markov)；D(Deterministic)；G(General)；...•c：排队系统中Server的数量–1到无限•K：排队系统中队列最大长度(包括正在服务的队列)–1到无限•N：请求总数量–有限vs无限•D：请求的服务调度策略–FCFS/FIFO;LCFS/LIFO;SIRO;...KendallNotation(举例)•M/D/5/40/200/FCFS–到达请求的时间间隔指数分布/平均到达请求数量泊松分布(M)–服务时间确定(D)；–一个有5个Servers(5)；–5个Servers，一共有40个Buffers(5个服务窗口，35个等待队列)；–一共有200个请求；–服务调度策略为先到先服务(FCFS)；•M/M/1–到达请求的时间间隔指数分布/平均到达请求数量泊松分布(M)–服务时间指数分布(M)–一个Server(1)–无限等待队列长度(默认)–无限请求数量(默认)–先到先服务的调度策略(默认)概率分布•指数分布泊松分布M/M/1•模型分析–M/M/1模型，是排队论中最典型、应用领域最广的模型；•给定此模型，需要解决什么问题？(仍旧是那些老问题)–已知：•单位时间平均达到的请求数量：•单位时间平均处理能力：–未知：•Server的利用率是多少：•平均服务时间是多少：•平均等待时间是多少：•平均响应时间是多少：•服务队列长度是多少：•等待队列长度是多少：•总队列长度是多少：•Server空闲概率是多少：•一个请求，需要等待的概率是多少：USWRsLqLL0PbPM/M/1（原理1）•状态转移（birth-deathprocess）–马尔科夫过程(MarkovProcess)•每一个状态，只跟他前后两个状态有关；–每个状态，标识排队系统中有多少请求•j状态，有的概率来一个请求，进入j+1状态；同样，有的概率处理一个请求，进入j-1状态；–每个状态，都有一个概率•状态转移公式–每个状态的转入=每个状态的转出(稳态系统：SteadyState)LnP1120110)()(jjjPPPPPPPPM/M/1（原理2）•计算各状态概率•利用率–定义，既为Server的利用率（UtilizationLaw）；•SteadyState（稳态）–若1，到达速度快于处理速度，系统中的累积的未处理请求会越来越长，系统会最终崩溃非稳态系统；–稳态系统：1(=1是特殊情况，也是不稳定的，后续会提到)–稳态系统：请求不会累计，系统能够长时稳定运行：002201)()(PPPPPPnn10iiPM/M/1（问题解答1）•Server的利用率是多少？•平均服务时间是多少？•服务队列长度是多少？•Server空闲概率是多少？•一个请求，需要等待的概率是多少？)(U1S1sL110UP01PPbM/M/1（问题解答2）•总队列长度是多少？•等待队列长度是多少？•平均响应时间是多少？•平均等待时间是多少？1)1(10iiiiiiPL1)1(21iiwPiL1111LRSRLWw11M/M/1•利用率与响应时间之间的关系)为常数1其中：(111RM/M/1（解读）•OLTP模型–请求随机，服务时间随机；•请求速度处理速度：稳态系统•资源利用率与响应时间的关系–控制资源利用率；D/D/1•模型分析–D/D/1模型，是排队论中最简单的模型；•到达请求的时间间隔分布：确定的；•服务时间的分布：确定的；•OLAP模型–请求确定，服务时间确定，定时任务；•资源利用率与响应时间的关系–可以人为调度各任务，做到完全的串行化；–资源利用率可以达到100%，而不影响响应时间；M/M/1vsM/D/1vsD/D/1M/M/1/k•FiniteBuffer–等待队列数量有限•1个服务窗口，K-1个等待Buffers；–若当前已有K个请求，则第K+1个请求被丢弃•状态转移(birth-deathprocess)M/M/1/k•现实意义–大部分现实中的系统，都是有最大等待队列限制的；–哪怕是没有等待队列限制的系统，用户发现队列长度过长时，也会主动放弃等待；•最重要的问题–请求到达时，发现队列已满，而被丢弃的概率是多少？–问题：•已知=0.5，若要让请求被丢弃的概率小于0.1%，那么系统需要支持多大的队列k？BPnnkBPP111M/M/1/k•问题解答•深入分析–M/M/1/k系统，不要求1，因为超过系统限制的请求，都被丢弃了；–M/M/1/k系统，实际进入系统的平均请求数量为996.91105.015.05.05.015.011031113kkPkkkkB)1('BPM/M/m•M/M/m系统–m个Servers，一个排队队列（无限），每个Server的处理能力相同；•状态转移（birth-deathprocess）M/M/m•M/M/m系统公式–Erlang-CFormula–代表了有m（或以上）个请求正在处理的概率。此时，新的请求进入系统需要等待；•响应时间R]!)(!)()1/[(!)(),(其中，))1(),(1(1010mmkmmmmcmmcRmUmmkkm),(mcm-111))1(),(1(1mmcRM/M/m•应用：–一个电话呼叫系统，每分钟平均有10个电话打入，每个电话平均持续1分钟。–电话的呼入间隔与服务时间均服从正态分布(M)。•问题：–请问需要提供多少话务员，才能够满足用户的需求？使得用户不至于因等待而放弃。•分析：–M/M/m系统，话务员即为Server；–：10个/分钟–：1分钟/个–：m101mM/M/m•解答衡量指标M/M/11M/M/12M/M/13等待队列Lq6.8212.2470.951等待概率Wq0.6820.2250.095利用率E0.9090.8330.767mM/M/1vsM/M/m•mM/M/1vsM/M/m–均为m个Servers，单队列与多队列系统，哪个更好？•mM/M/1•M/M/m•随着的增大，响应时间哪个增加的更快？111Rm-111R）（mUmM/M/1vsM/M/mM/M/mvsM/M/1•M/M/mvsM/M/1–M/M/m