• Stars
    star
    2,078
  • Rank 21,600 (Top 0.5 %)
  • Language
  • Created over 5 years ago
  • Updated 9 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Queueing theory: an introduction for software development

Queueing theory

Queueing theory is the mathematical study of waiting lines, or queues. We use queueing theory in our software development, for purposes such as analyzing and optimizing our practices and processes, such as our customer service responsiveness, project management kanban planning, inter-process communication message queues, and devops continuous deployment pipelines.

Contents:

Introduction

We use queueing theory in our projects for many purposes:

  • Customer service responsiveness

  • Project management kanban planning

  • Inter-process communication message queues

  • Devops continuous deployment pipelines

Customer service responsiveness

For example, we want to analyze how customers request sales help and support help, and how fast we respond.

Some relevant products are e.g. Salesforce, LiveChat, Zendesk.

Project management kanban planning

For example, we want to track the lead times and progress times as a new feature idea evolves from design to delivery.

Some relevant products are e.g. Asana, Jira, Microsoft Project.

Inter-process communication message queues

For example, we want to maximize throughputs and minimize pressures as one program sends requests to another program.

Some relevant products are e.g. RabbitMQ, ActiveMQ, ZeroMQ.

Devops continuous deployment pipelines

For example, we want to ensure our continuous integration server has capacity to test our software then deploy it.

Some relevant products are e.g. Jenkins, Bamboo, Azure DevOps.

Queue terminology

Queue terminology is a big topic. This section has some of our common terminology. For the examples, we will use the idea of a customer waiting in line.

Queue types and service types

Queue types and service types describe how the queue chooses which items to process.

  • First In First Out (FIFO): serve the customer who has been waiting for the longest time.

  • Last In First Out (LIFO): serve the customer who has been waiting for the shortest time.

  • Priority: serve customers based on their priority level; these levels could be based on status, urgency, payment, etc.

  • Shortest Job First (SJF): serve the customer who needs the smallest amount of service.

  • Longest Job First (LJF): serve the customer who needs the largest amount of service.

  • Time Sharing: serve everyone at the same time; service capacity is distributed evenly among everyone waiting.

Queue dropouts

Queue dropouts are when a customer does not make it through the queue.

  • Balking: when a customer decides not to start waiting for service because the wait time threatens to be too long.

  • Reneging: when a customer who has waited already decides to leave because they’ve wasted too much time.

  • Jockeying: when a customer switches between queues in a tandem queue system, trying to get a shorter wait.

Queueing theory notation

Queueing theory uses notation with Greek letters.

Our teams use some of the popular notation; we also add some custom notion that help us with software projects.

Arrival rate, service rate, dropout rate

The most important notation:

  • λ: arrival rate. This measures how fast new items are coming into the queue.

  • μ: service rate. This measures how fast items in the queue are being handled.

  • σ: dropout rate. This measures how fast items are skipping out the queue unhandled.

Examples:

  • λ = μ means the arrival rate equals the service rate; the queue is staying the same size, other than dropouts.

  • λ > μ means the arrival rate is greater than the service rate; the queue is getting larger, other than dropouts.

  • λ < μ means the arrival rate is less than the service rate; the queue is getting smaller, other than dropouts.

Utilization ratio

The most important notation that summarizes a queue:

  • ρ: utilization ratio = λ / μ

Examples:

  • ρ = 1 means the arrival rate is equal to the service rate; the queue is staying the same size.

  • ρ > 1 means the arrival rate is greater than the service rate; the queue is getting larger.

  • ρ < 1 means the arrival rate is less than the service rate; the queue is getting smaller.

Error ratio

The most important notation that summarizes a queue's success:

  • ε: error ratio = service failure count / service total count

Examples:

  • ε = 0 means no errors.

  • ε = 0.1 means 10% of services have an error.

  • ε = 1 means every service has an error.

Lead time, wait time, work time, step time

We track four times:

  • τ: lead time = from arrival to finish

  • ω: wait time = from arrival to start of work

  • φ: work time = from start of work to finish

  • θ: step time = from finish to next finish

Examples:

  • τ = 5s means an item is added to the queue, then serviced 5 seconds later.

  • ω = 4s means an item waits in the queue for 4 seconds, then work starts.

  • φ = 1s means an item takes 1 second of work, then is complete.

  • θ = 1s means there's 1 second between one completion and the next completion.

Count

We count items often, and we use this notation:

  • κ: count

Example:

  • κ = 100 means there are 100 items.

  • κ > 100 means there are more than 100 items.

  • κ ≫ 100 means there are many more than 100 items.

Standard notation

Standard notation for queueing theory also uses these symbols:

  • n: the number of items in the system.

  • A: the arrival process probability distribution.

  • B: the service process probability distribution.

  • C: the number of servers.

  • D: the maximum number of items allowed in the queue at any given time, waiting or being served (without getting bumped).

  • E: the maximum number of items total.

Activity tracking

Activity examples

Suppose we have something we want to track, and we call it something generic such as "Activity" and abbrievated as "A".

We can efficiently use queuing notation to describe the activity and how it moves through a queue.

Examples:

  • Aκ: Activity count: how many items are in the queue.

  • Aλ: Activity arrival rate: how many items are incoming per time unit.

  • Aμ: Activity service rate: how many items are completed per time unit.

  • Aσ: Activity dropout rate: how many items are abandoned per time unit.

  • Aρ: Activity utilization ratio: how many items are arriving vs. completing.

  • Aε: Activity error ratio: how many items are completed with errors vs. total.

  • Aτ: Activity lead time: how much time elapses from requested to completed.

  • Aω: Activity wait time: how much time elapses from requested to started.

  • Aφ: Activity work time: how much time elapses from started to completed.

  • Aθ: Activity step time: how much time elapses from completed to next completed.

Little's Law

Little's law is a theorem by John Little which states: the long-term average number L of customers in a stationary system is equal to the long-term average effective arrival rate λ multiplied by the average time W that a customer spends in the system.

Example notation:

  • L is the long-term average number of customers in the system.

  • λ is the long-term average effective arrival rate.

  • W is the average time that a customer spends in the system.

  • L = λ W is Little's law.

Little's law assumptions:

  • All measurement units are consistent.

  • Conservation of flow, meaning the average arrival rate equals the average departure rate.

  • All work that enters the system then flows through to completion.

  • The system is “stable”, meaning the average age of items are neither increasing or decreasing, and the total number of items is roughly the same at the beginning and at the end.

Key performance indicators (KPIs)

We typically track many things about the activities in the queue, and we want to summarize the results by choosing a shortlist of the most relevant ones for our projects.

We have built many projects, and we believe the most valuable summary indicators are:

  • Dτ = Delivery lead time. Product teams may say "from concept to customer" or "from idea to implementation".

  • Dμ = Delivery service rate. Devops teams may say "deployment frequency" or "we ship X times per day".

  • Dε = Delivery error ratio. Quality teams may say "change fail rate" or "percentage of rollbacks".

  • Rτ = Restore lead time. Site reliability engineers may say "time to restore service" or "mean time to restore (MTTR)".

Epilog

See also

Wikipedia:

Wikipedia areas where we use queues in many projects:

Introductions by John D. Cook:

Introductions with more detail:

Blog posts:

Seven Insights Into Queueing Theory:

  • The slower the service center, the lower the maximum utilization you should plan for at peak load.

  • It’s very hard to use the last 15% of anything.

  • The closer you are to the edge, the higher the price for being wrong.

  • Response time increases are limited by the number that can wait.

  • Remember this is an average, not a maximum.

  • There is a human denial effect in multiple service centers.

  • Show small improvements in their best light.

Thanks

Accelerate: The Science of Lean Software and DevOps: Building and Scaling High Performing Technology Organizations. By Nicole Forsgren, Jez Humble, Gene Kim. This book is excellent for high level devops, and directly informs our choice of KPIs. The KPIs on this page align with the book's recommendations.

More Repositories

1

architecture-decision-record

Architecture decision record (ADR) examples for software planning, IT leadership, and template documentation
11,128
star
2

monorepo-vs-polyrepo

Monorepo vs. polyrepo: architecture for source code management (SCM) version control systems (VCS)
991
star
3

git-commit-message

Git commit message: how to write a great git commit message and commit template for version control
915
star
4

ways-of-working

Ways of Working (WoW) with team principles, values, tenets, ground rules, aspirations, norms, working agreements, shared expectations, and group understandings
619
star
5

objectives-and-key-results

Objectives and Key Results (OKR) examples for goals, tasks, plans, projects, and strategy.
344
star
6

pitch-deck

Pitch deck advice for startup founders who want to raise venture capital investment
285
star
7

demo-rust-axum

Demo of Rust and axum web framework with Tokio, Tower, Hyper, Serde
Rust
278
star
8

github-special-files-and-paths

GitHub special files and paths, such as README, LICENSE, .github, docs, dependabot, workflows.
192
star
9

stable-diffusion-image-prompt-gallery

Stable Diffusion: image prompt gallery of examples for various prompts
Shell
178
star
10

maturity-models

Maturity models for IT, Agile, DevOps, TOGAF, Six Sigma, P3M3, etc.
172
star
11

plantuml-examples

PlantUML eaxmples for UML, ERD, wireframes, mind maps, JSON, YAML, WBS, ASCII art, Gantt charts, C4 models, and more
168
star
12

git-commit-template

Git commit template for better commit messages
163
star
13

stable-diffusion-macos-install-help

Stable Diffusion: macOS install help with homebrew, python, anaconda, dream, etc.
130
star
14

key-performance-indicator

Key performance indicator (KPI) examples for metrics, measurements, objectives and key results (OKRs)
129
star
15

brewfile

Brewfile
Ruby
111
star
16

crucial-conversations

Crucial conversations: lessons from the worldwide bestseller book
95
star
17

decision-record

Decision record: how to initiate and complete decisions for teams, organizations, and systems
92
star
18

statement-of-work

Statement Of Work (SOW) example
67
star
19

demo-swift-excel-xlsx-reader-writer

Demo Swift Excel Xlsx Reader Writer
Swift
60
star
20

inclusive-language

Inclusive language
57
star
21

strategic-balanced-scorecard

Strategic Balanced Scorecard: planning business by using OKRs, KPIs, and initiatives
49
star
22

issues

Issues: feature requests, bug reports, customer complaints, security alerts, etc.
44
star
23

oblique-strategies

Oblique Strategies: ideas for creative lateral thinking
42
star
24

care-plan

Care plan: a free open source care plan template for caregivers to help with medical, financial, government, legal, and practical care.
41
star
25

startup-superset

Startup superset: summaries of key concepts, ideas, insights
40
star
26

functional-specifications-template

Functional specifications template
40
star
27

always-improving

Book summaries by "alwaysimproving" for business, productivity, life skills, etc.
35
star
28

milestones

Milestones ideas and examples for project management
32
star
29

software-development-methodologies

Software development methodologies: summaries of agile, scrum, DAD, SAFe, etc.
31
star
30

social-network-plan

Social network plan - goals, ideas, step, and tasks for a new site
30
star
31

company-culture

Company culture ideas from Amazon, Netflix, Harvard, Ultimate, etc.
28
star
32

versioning

Versioning: what it is, how to do it, comments and discussion
28
star
33

leadership

Leadership and management ideas
27
star
34

spade-decision-framework

SPADE decision framework: Setting, People, Alternatives, Decide, Explain
27
star
35

system-quality-attributes

Cross-Functional Requirements a.k.a. Quality Attributes
26
star
36

ooda-loop

OODA loop: notes on John Boyd, strategy, tactics, planning, and paradigms
25
star
37

powerful-questions

Powerful questions - catalyzing insight, innovation, action
25
star
38

business-model-canvas

Business model canvas for value propositions, customer relationships, partner collaborations, etc.
25
star
39

thought-leadership-writing

Thought leadership writing tips for content creators, bloggers, authors, and editors
24
star
40

awesome-developing

Awesome developing: ideas for how to create better software code and collaboration
24
star
41

value-stream-mapping

Value Stream Mapping (VSM) tutorial (work in progress)
24
star
42

big-five-personality-traits

Big Five personality traits: domains, aspects, facets
22
star
43

source-code-management

Source code management → notes and ideas → mono-repos, trunk-based-development, etc.
21
star
44

key-risk-indicator

Key risk indicator (KRI) for risk management and business strategy
20
star
45

wordbooks

Demo wordbooks for business, projects, industries, software, consulting, and more
Lua
20
star
46

code-of-conduct-guidelines

Code of Conduct Guidelines
Shell
19
star
47

git-branch-name

Git branch name ideas, naming conventions, and how to use git branch edit description
19
star
48

git-workflow-help

Git flow help: research on Git flow, GitHub flow, GitLab flow, etc.
18
star
49

demo-tailwind-css

Demo Tailwind CSS along with Gulp and PostCSS
JavaScript
18
star
50

functional-specifications-tutorial

Functional specifications tutorial
17
star
51

sha256-sentence

SHA256 sentence: discover a SHA256 checksum that matches a sentence's description of hex digit words.
Rust
17
star
52

team-focus

TEAM FOCUS concepts by Paul N. Friga in McKinsey Engagement.
17
star
53

stakeholder-analysis

Stakeholder analysis for business project management
HTML
17
star
54

smart-criteria

SMART criteria for goals, objectives, plans, etc.
16
star
55

interviewing

Interviewing ideas for hiring managers, job seekers, and recruiting candidates
16
star
56

vision_mission_statements

Vision statements and mission statements by many companies and organizations
16
star
57

goals-ideas-steps-tasks

Goals, Ideas, Steps, Tasks: GIST Planning
14
star
58

icebreaker-questions

Icebreaker questions to help people, groups, teams, meetings, and such
14
star
59

coordinated-disclosure

Coordinated disclosure for security discoveries, bug reports, etc.
13
star
60

outputs-vs-outcomes

Outputs vs. outcomes: what's the different and why does it matter?
12
star
61

discovery-assessment

Discovery assessment for project management
12
star
62

critical-success-factor

Critical Success Factor (CSF) tutorial
12
star
63

software-operations-items

Software operations items
12
star
64

demo-rust-cargo-tdd

Demo of Rust and Cargo for TDD (test driven development)
Rust
11
star
65

agile-assessment

Agile assessment exercise ideas
11
star
66

metrics

Metrics
10
star
67

responsibility-assignment-matrix

Responsibility assignment matrix (RAM) a.k.a. linear responsibility chart (LRC)
10
star
68

social-value-orientation

Social value orientation (SVO) notes for pro-social pro-self concepts
10
star
69

demo-elixir-phoenix

Demonstration of Elixir language and Phoenix framework
Elixir
10
star
70

pgp-gpg-help

Pretty Good Privacy (PGP) GNU Privacy Guard (GPG) help for encryption
9
star
71

causal-analysis-based-on-system-theory

Causal Analysis based on System Theory (CAST)
9
star
72

demo-job-descriptions

Demo job descriptions
9
star
73

demo-terraform-aws

Demo of Terraform by Hasicorp for AWS
HCL
9
star
74

lean-business-lists

Lean business lists
9
star
75

issue-postmortem-template

Issue postmortem template for incident response documentation
8
star
76

net-promoter-score

Net Promoter Score (NPS) introduction and recommendations
8
star
77

initiatives-and-experiments

Initiatives and experiments
8
star
78

demo-rust-cursive

Demo Rust Cursive crate for terminal user interface (TUI)
Rust
8
star
79

demo-swift-rest

Demo Swift REST
HTML
8
star
80

git-hooks

Git hooks
Shell
7
star
81

demo-devops

Demo devops
7
star
82

adkar-change-management-model

ADKAR change management model: awareness, desire, knowledge, ability, reinforcement
7
star
83

demo-optaplanner

Demo OptaPlanner constraint solver
Java
6
star
84

intent-plan

Intent plan for mision, state, sequence, decisions, antigoals, constraints, expressives
6
star
85

demo-rust-rocket

Demo of Rust Rocket web application framework
Rust
6
star
86

task-life-cycle

Task life cycle (TLC)
5
star
87

feedback-request-template

Feedback request template
5
star
88

first-aid-kit

First Aid Kit
5
star
89

inspiring-people

Inspiring people: one hundred living people with short bios thanks to Wikipedia
5
star
90

principles

Principles: summaries of ethical prinicples, leadership principles, teamwork principles, ui/ux design principles, software programming principles, etc.
5
star
91

demo-aws-ses-smtp

Demo of Amazon Web Services (AWS) Simple Email Service (SES) Simple Mail Transfer Protocol (SMTP)
4
star
92

aberystwyth-wales-book

Aberystwth Wales Book - Photos of the Town
Shell
4
star
93

safety-philosophy

Safety philosopy: example principles for an organization and management
4
star
94

demo-shopping-cart-exercise-with-ruby

Shopping cart exercise with Ruby: how to program a shop, cart, till, checkout, etc. with TDD
Ruby
4
star
95

demo-gulp

Demo gulpfile.js using Gulp, PostCSS, Tailwind CSS, Pino, unfold, and more
JavaScript
4
star
96

git-troubleshooting

Git troubleshooting
4
star
97

demo-svelte-hello-world

Demo Svelte JavaScript framework "hello world" app
JavaScript
4
star
98

demo-ansible

Demo Ansible configuration tool for install, update, users, groups, etc.
4
star
99

quad-chart

Quad chart: a rapid project planning summary guide
4
star
100

adventure-gear

Adventure gear for traveling, backpacking, camping, and more
4
star