Springer Analyzing Computer Systems Performance with Perl下载

Springer Analyzing Computer Systems Performance with Perl Preface ........................................................ vii Part I Theory of System Performance Analysis 1 Time—The Zeroth Performance Metric.................... 3 1.1 Introduction.......................................... 3 1.2 WhatIsTime?........................................ 4 1.2.1 PhysicalTime................................. 5 1.2.2 SynchronizationandCausality .................. 5 1.2.3 DiscreteandContinuousTime .................. 6 1.2.4 TimeScales................................... 6 1.3 WhatIsaClock?...................................... 8 1.3.1 PhysicalClocks ............................... 8 1.3.2 DistributedPhysicalClocks..................... 9 1.3.3 DistributedProcessing ......................... 9 1.3.4 Binary Precedence. ............................ 10 1.3.5 LogicalClocks ................................ 10 1.3.6 ClockTicks................................... 12 1.3.7 VirtualClocks ................................ 13 1.4 RepresentationsofTime................................ 14 1.4.1 IntheBeginning .............................. 14 1.4.2 MakingaDateWithPerl....................... 15 1.4.3 High-ResolutionTiming........................ 17 1.4.4 BenchmarkTimers ............................ 18 1.4.5 CrossingTimeZones........................... 19 1.5 TimeDistributions .................................... 21 1.5.1 GammaDistribution........................... 22 1.5.2 ExponentialDistribution....................... 22 1.5.3 PoissonDistribution........................... 24 1.5.4 ServerResponseTimeDistribution .............. 25 xvi Contents 1.5.5 NetworkResponseTimeDistribution ............ 26 1.6 TimingChainsandBottlenecks ......................... 28 1.6.1 BottlenecksandQueues........................ 30 1.6.2 DistributedInstrumentation .................... 30 1.6.3 DiskTimingChains ........................... 31 1.6.4 LifeandTimesofanNFSOperation............. 32 1.7 Failing Big Time ...................................... 33 1.7.1 Hardware Availability.......................... 34 1.7.2 TyrannyoftheNines .......................... 34 1.7.3 Hardware Reliability........................... 35 1.7.4 MeanTimeBetweenFailures ................... 36 1.7.5 DistributedHardware.......................... 38 1.7.6 ComponentsinSeries .......................... 38 1.7.7 ComponentsinParallel ........................ 38 1.7.8 Software Reliability ............................ 39 1.8 MetastableLifetimes................................... 39 1.8.1 Microscopic Metastability ...................... 40 1.8.2 Macroscopic Metastability ...................... 43 1.8.3 Metastability in Networks ...................... 43 1.8.4 QuantumlikePhaseTransitions ................. 45 1.9 Review............................................... 45 Exercises................................................... 46 2 Getting the Jump on Queueing ............................ 47 2.1 Introduction.......................................... 47 2.2 WhatIsaQueue? ..................................... 48 2.3 TheGroceryStore—CheckingItOut .................... 48 2.3.1 QueueingAnalysisView........................ 49 2.3.2 Perceptions and Deceptions . .................... 50 2.3.3 ThePostO?ce—SnailMail .................... 51 2.4 Fundamental Metric Relationships ....................... 51 2.4.1 PerformanceMeasures ......................... 52 2.4.2 ArrivalRate.................................. 53 2.4.3 System Throughput ........................... 55 2.4.4 Nodal Throughput............................. 56 2.4.5 Relative Throughput........................... 56 2.4.6 ServiceTime.................................. 57 2.4.7 ServiceDemand............................... 58 2.4.8 Utilization.................................... 58 2.4.9 ResidenceTime ............................... 59 2.5 Little’sLawMeansaLot............................... 59 2.5.1 ALittleIntuition.............................. 60 2.5.2 AVisualProof................................ 61 2.5.3 Little’sMicroscopicLaw........................ 66 2.5.4 Little’sMacroscopicLaw ....................... 66 Contents xvii 2.6 UnlimitedRequest(Open)Queues....................... 67 2.6.1 SingleServerQueue ........................... 67 2.6.2 MeasuredServiceDemand...................... 68 2.6.3 QueueingDelays .............................. 68 2.6.4 TwinQueueingCenter ......................... 73 2.6.5 ParallelQueues ............................... 74 2.6.6 DualServerQueue—HeuristicAnalysis........... 76 2.7 MultiserverQueue..................................... 79 2.7.1 Erlang’s C Formula............................ 80 2.7.2 AccuracyoftheHeuristicFormula............... 82 2.7.3 Erlang’s B Formula............................ 83 2.7.4 ErlangAlgorithmsinPerl ...................... 84 2.7.5 DualServerQueue—ExactAnalysis ............. 86 2.8 LimitedRequest(Closed)Queues........................ 88 2.8.1 ClosedQueueingCenter........................ 88 2.8.2 InteractiveResponseTimeLaw ................. 89 2.8.3 RepairmanAlgorithminPerl ................... 90 2.8.4 ResponseTimeCharacteristic................... 92 2.8.5 Throughput Characteristic...................... 93 2.8.6 FiniteResponseTimes......................... 94 2.8.7 ApproximatingaClosedQueues................. 95 2.9 ShorthandforQueues.................................. 99 2.9.1 QueueSchematics ............................. 99 2.9.2 KendallNotation..............................100 2.10 ComparativePerformance ..............................101 2.10.1 MultiserverVersusUniserver....................102 2.10.2 MultiqueueVersusMultiserver ..................102 2.10.3 TheEnvelopePlease! ..........................104 2.11 GeneralizedServers....................................105 2.11.1 Infinite Capacity (IS) Server ....................106 2.11.2 Exponential(M)Server ........................107 2.11.3 Deterministic(D)Server .......................108 2.11.4 Uniform(U)Server............................108 2.11.5 Erlang-k (Ek)Server...........................108 2.11.6 Hypoexponential (Hypo–k)Server...............109 2.11.7 Hyperexponential (Hk)Server...................109 2.11.8 Coxian (Cox–k)Server.........................110 2.11.9 General(G)Server ............................111 2.11.10 Pollaczek–Khintchine Formula ..................112 2.11.11 Polling Systems ...............................113 2.12 Review...............................................115 Exercises...................................................116 xviii Contents 3 Queueing Systems for Computer Systems..................119 3.1 Introduction..........................................119 3.2 TypesofCircuits......................................120 3.3 PoissonProperties.....................................122 3.3.1 PoissonMerging...............................122 3.3.2 PoissonBranching.............................123 3.3.3 PoissonPasta.................................123 3.4 Open-CircuitQueues ..................................124 3.4.1 SeriesCircuits ................................125 3.4.2 FeedforwardCircuits...........................125 3.4.3 FeedbackCircuits .............................126 3.4.4 Jackson’sTheorem ............................129 3.4.5 ParallelQueuesinSeries .......................131 3.4.6 MultipleWorkloadsinOpenCircuits ............135 3.5 Closed-CircuitQueues .................................136 3.5.1 ArrivalTheorem ..............................136 3.5.2 IterativeMVAAlgorithm.......................138 3.5.3 ApproximateSolution..........................139 3.6 Visit Ratios and Routing Probabilities ...................140 3.6.1 VisitRatiosandOpenCircuits..................142 3.6.2 VisitRatiosandClosedCircuits.................143 3.7 MultipleWorkloadsinClosedCircuits ...................144 3.7.1 WorkloadClasses..............................144 3.7.2 BaselineAnalysis..............................145 3.7.3 AggregateAnalysis ............................146 3.7.4 ComponentAnalysis...........................150 3.8 WhenIsaQueueingCircuitSolvable?....................151 3.8.1 MVAIsaStyleofThinking.....................152 3.8.2 BCMPRules .................................153 3.8.3 ServiceClasses................................154 3.9 ClassicComputerSystems..............................155 3.9.1 Time-ShareScheduler..........................155 3.9.2 Fair-ShareScheduler...........................157 3.9.3 PriorityScheduling ............................158 3.9.4 ThreadsScheduler.............................160 3.10 WhatQueueingModelsCannotDo......................161 3.11 Review...............................................163 Exercises...................................................164 4 Linux Load Average—Take a Load O?! ....................167 4.1 Introduction..........................................167 4.1.1 LoadAverageReporting .......................168 4.1.2 WhatIsan“Average”Load? ...................169 4.2 ASimpleExperiment ..................................170 4.2.1 ExperimentalResults ..........................172 Contents xix 4.2.2 Submerging Into the Kernel. ....................173 4.3 LoadCalculation......................................174 4.3.1 Fixed-PointArithmetic.........................175 4.3.2 MagicNumbers ...............................176 4.3.3 EmptyRun-Queue ............................178 4.3.4 OccupiedRun-Queue ..........................179 4.3.5 ExponentialDamping..........................180 4.4 Steady-StateAverages .................................183 4.4.1 Time-AveragedQueueLength...................184 4.4.2 LinuxSchedulerModel.........................184 4.5 LoadAveragesandTrendVisualization ..................187 4.5.1 WhatIsWrongwithLoadAverages .............187 4.5.2 NewVisualParadigm..........................187 4.5.3 ApplicationtoWorkloadManagement ...........189 4.6 Review...............................................190 Exercises...................................................190 5 Performance Bounds and Log Jams........................191 5.1 Introduction..........................................191 5.2 Out of Bounds in Florida...............................191 5.2.1 LoadTestResults .............................192 5.2.2 Bottlenecks and Bounds ........................192 5.3 Throughput Bounds ...................................193 5.3.1 Saturation Throughput.........................193 5.3.2 Uncontended Throughput ......................194 5.3.3 OptimalLoad.................................195 5.4 Response Time Bounds ................................196 5.4.1 UncontendedResponseTime....................196 5.4.2 SaturationResponseTime......................196 5.4.3 Worst–CaseResponseBound ...................197 5.5 Meanwhile, Back in Florida ... ..........................198 5.5.1 Balanced Bounds ..............................199 5.5.2 BalancedDemand.............................199 5.5.3 Balanced Throughput ..........................199 5.6 TheX–Files:EncounterswithPerformanceAliens.........201 5.6.1 X-WindowsArchitecture .......................201 5.6.2 ProductionEnvironment .......................202 5.7 CloseEncountersofthePerformanceKind................202 5.7.1 CloseEncountersI:Rumors ....................202 5.7.2 CloseEncountersII:Measurements ..............203 5.7.3 CloseEncountersIII:Analysis ..................203 5.8 PerformanceAliensRevealed............................205 5.8.1 OutofSight,OutofMind......................205 5.8.2 Log–Jammed Performance . .....................207 5.8.3 ToGetaLogYouNeedaTree..................208 xx Contents 5.9 X-Windows Scalability .................................210 5.9.1 MeasuringSiblingX-Events.....................210 5.9.2 SuperlinearResponse ..........................211 5.10 Review...............................................212 Exercises...................................................212 Part II Practice of System Performance Analysis 6 Pretty Damn Quick (PDQ)—A Slow Introduction .........215 6.1 Introduction..........................................215 6.2 HowtoBuildPDQCircuits.............................215 6.3 Inputs and Outputs....................................215 6.3.1 SettingUpPDQ ..............................216 6.3.2 SomeGeneralGuidelines.......................218 6.4 SimpleAnnotatedExample.............................219 6.4.1 CreatingthePDQModel.......................219 6.4.2 ReadingthePDQReport.......................221 6.4.3 ValidatingthePDQModel .....................222 6.5 PerlPDQModule .....................................223 6.5.1 PDQDataTypes..............................223 6.5.2 PDQGlobalVariables .........................224 6.5.3 PDQFunctions ...............................225 6.6 FunctionSynopses.....................................225 6.6.1 PDQ::CreateClosed............................225 6.6.2 PDQ::CreateMultiNode ........................226 6.6.3 PDQ::CreateNode .............................226 6.6.4 PDQ::CreateOpen.............................227 6.6.5 PDQ::CreateSingleNode........................228 6.6.6 PDQ::GetLoadOpt ............................228 6.6.7 PDQ::GetQueueLength.........................229 6.6.8 PDQ::GetResidenceTime.......................229 6.6.9 PDQ::GetResponse ............................230 6.6.10 PDQ::GetThruMax............................231 6.6.11 PDQ::GetThruput. ............................231 6.6.12 PDQ::GetUtilization ...........................232 6.6.13 PDQ::Init ....................................232 6.6.14 PDQ::Report .................................233 6.6.15 PDQ::SetDebug...............................234 6.6.16 PDQ::SetDemand .............................235 6.6.17 PDQ::SetTUnit ...............................236 6.6.18 PDQ::SetVisits................................236 6.6.19 PDQ::SetWUnit...............................237 6.6.20 PDQ::Solve...................................237 6.7 ClassicQueuesinPDQ.................................238 Contents xxi 6.7.1 DelayNodeinPDQ ...........................238 6.7.2 M/M/1inPDQ...............................238 6.7.3 M/M/m inPDQ..............................239 6.7.4 M/M/1//N inPDQ...........................239 6.7.5 M/M/m//N inPDQ ..........................240 6.7.6 FeedforwardCircuitsinPDQ ...................240 6.7.7 FeedbackCircuitsinPDQ......................242 6.7.8 ParallelQueuesinSeries .......................244 6.7.9 MultipleWorkloadsinPDQ ....................246 6.7.10 PriorityQueueinginPDQ......................252 6.7.11 Load-DependentServersinPDQ ................258 6.7.12 Bounds Analysis with PDQ .....................263 6.8 Review...............................................264 Exercises...................................................264 7 Multicomputer Analysis with PDQ ........................267 7.1 Introduction..........................................267 7.2 MultiprocessorArchitectures............................268 7.2.1 SymmetricMultiprocessors .....................269 7.2.2 MultiprocessorCaches .........................270 7.2.3 CacheBashing ................................271 7.3 MultiprocessorModels .................................272 7.3.1 Single-BusModels.............................273 7.3.2 ProcessingPower..............................274 7.3.3 Multiple-BusModels...........................276 7.3.4 CacheProtocols...............................278 7.3.5 IronLawofPerformance .......................287 7.4 MulticomputerModels.................................289 7.4.1 ParallelQueryCluster .........................290 7.4.2 QuerySaturationMethod ......................294 7.5 Review...............................................298 Exercises...................................................299 8 How to Scale an Elephant with PDQ ......................301 8.1 AnElephantStory ....................................301 8.1.1 What Is Scalability? ...........................302 8.1.2 SPECMultiuserBenchmark ....................303 8.1.3 Steady-stateMeasurements .....................305 8.2 PartsoftheElephant..................................306 8.2.1 ServiceDemandPart ..........................307 8.2.2 ThinkTimePart..............................307 8.2.3 UserLoadPart ...............................308 8.3 PDQ Scalability Model. ................................308 8.3.1 Interpretation.................................311 8.3.2 Amdahl’sLaw ................................312 xxii Contents 8.3.3 TheElephant’sDimensions.....................314 8.4 Review...............................................315 Exercises...................................................315 9 Client/Server Analysis with PDQ..........................317 9.1 Introduction..........................................317 9.2 Client/ServerArchitectures.............................318 9.2.1 MultitierEnvironments ........................319 9.2.2 Three–TierOptions............................319 9.3 BenchmarkEnvironment ...............................321 9.3.1 PerformanceScenarios .........................322 9.3.2 WorkloadCharacterization .....................322 9.3.3 DistributedWorkflow..........................324 9.4 Scalability Analysis with PDQ ..........................325 9.4.1 BenchmarkBaseline ...........................326 9.4.2 ClientScaleup ................................333 9.4.3 LoadBalancerBottleneck ......................334 9.4.4 DatabaseServerBottleneck.....................334 9.4.5 ProductionClientLoad ........................335 9.4.6 SaturationClientLoad.........................336 9.4.7 Per-ProcessAnalysis...........................338 9.5 Review...............................................339 Exercises...................................................339 10 Web Application Analysis with PDQ ......................341 10.1 Introduction..........................................341 10.2 HTTPProtocol .......................................341 10.2.1 HTTPPerformance............................346 10.2.2 HTTPAnalysisUsingPDQ ....................347 10.2.3 Fork-on-DemandAnalysis ......................348 10.2.4 PreforkAnalysis ..............................349 10.3 Two-TierPDQModel..................................355 10.3.1 DataandInformationAreNottheSame .........355 10.3.2 HTTPdPerformanceMeasurements .............355 10.3.3 JavaPerformanceMeasurements ................357 10.4 MiddlewareAnalysisUsingPDQ ........................357 10.4.1 ActiveClientThreads..........................359 10.4.2 LoadTestResults .............................359 10.4.3 DerivedServiceDemands.......................360 10.4.4 NaivePDQModel.............................360 10.4.5 AddingHiddenLatenciesinPDQ ...............365 10.4.6 Adding Overdriven Throughput in PDQ..........366 10.5 Review...............................................370 Exercises...................................................370 Contents xxiii Part III Appendices A Glossary of Terms .........................................373 B A Short History of Bu?ers.................................385 C Thanks for No Memories ..................................391 C.1 LifeintheMarkovLane................................391 C.2 ExponentialInvariance.................................392 C.3 ShapePreservation ....................................394 C.4 ACounterexample.....................................394 D Performance Measurements and Tools .....................397 D.1 PerformanceCountersandObjects ......................397 D.2 JavaBytecodeInstrumentation..........................397 D.3 GenericPerformanceTools .............................398 D.4 DisplayingPerformanceMetrics.........................398 D.5 StoringPerformanceMetrics............................401 D.6 PerformancePredictionTools...........................401 D.7 HowAccurateareYourData? ..........................402 D.8 AreYourDataPoissonian? .............................402 D.9 PerformanceMeasurementStandards ....................407 E Compendium of Queueing Equations ......................409 E.1 Fundamental Metrics ..................................409 E.2 QueueingDelays ......................................410 F Installing PDQ and PerlPrograms .........................411 F.1 PerlScripts...........................................411 F.2 PDQScripts..........................................412 F.3 Installing the PDQ Module .............................412 G Units and Abbreviations...................................415 G.1 SIPrefixes............................................415 G.2 TimeSu?xes .........................................415 G.3 CapacitySu?xes......................................415 H Solutions to Selected Exercises ............................417 Bibliography...................................................421 Index ..........................................................427