https://github.com/joelparkerhenderson/queueing-theory Skip to content Toggle navigation Sign up * Product + Actions Automate any workflow + Packages Host and manage packages + Security Find and fix vulnerabilities + Codespaces Instant dev environments + Copilot Write better code with AI + Code review Manage code changes + Issues Plan and track work + Discussions Collaborate outside of code Explore + All features + Documentation + GitHub Skills + Blog * Solutions For + Enterprise + Teams + Startups + Education By Solution + CI/CD & Automation + DevOps + DevSecOps Resources + Customer Stories + White papers, Ebooks, Webinars + Partners * Open Source + GitHub Sponsors Fund open source developers + The ReadME Project GitHub community articles Repositories + Topics + Trending + Collections * Pricing Search or jump to... Search code, repositories, users, issues, pull requests... Search [ ] Clear Search syntax tips Provide feedback We read every piece of feedback, and take your input very seriously. [ ] [ ] Include my email address so I can be contacted Cancel Submit feedback Saved searches Use saved searches to filter your results more quickly Name [ ] Query [ ] To see all available qualifiers, see our documentation. Cancel Create saved search Sign in Sign up You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert {{ message }} joelparkerhenderson / queueing-theory Public * * Notifications * Fork 68 * Star 1.8k Queueing theory: an introduction for software development 1.8k stars 68 forks Activity Star Notifications * Code * Issues 0 * Pull requests 0 * Actions * Projects 0 * Security * Insights More * Code * Issues * Pull requests * Actions * Projects * Security * Insights joelparkerhenderson/queueing-theory This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. main Switch branches/tags [ ] Branches Tags Could not load branches Nothing to show {{ refName }} default View all branches Could not load tags Nothing to show {{ refName }} default View all tags Name already in use A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch? Cancel Create 2 branches 0 tags Code * Local * Codespaces * Clone HTTPS GitHub CLI [https://github.com/j] Use Git or checkout with SVN using the web URL. [gh repo clone joelpa] Work fast with our official CLI. Learn more about the CLI. * Open with GitHub Desktop * Download ZIP Sign In Required Please sign in to use Codespaces. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching Xcode If nothing happens, download Xcode and try again. Launching Visual Studio Code Your codespace will open once ready. There was a problem preparing your codespace, please try again. Latest commit @joelparkerhenderson joelparkerhenderson Add code of conduct ... d342d54 Sep 15, 2023 Add code of conduct d342d54 Git stats * 26 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time CODE_OF_CONDUCT.md Add code of conduct September 15, 2023 15:39 README.md Add link March 8, 2022 05:37 View code [ ] Queueing theory Introduction Customer service responsiveness Project management kanban planning Inter-process communication message queues Devops continuous deployment pipelines Queue terminology Queue types and service types Queue dropouts Queueing theory notation Arrival rate, service rate, dropout rate Utilization ratio Error ratio Lead time, wait time, work time, step time Count Standard notation Activity tracking Activity examples Little's Law Key performance indicators (KPIs) Epilog See also Thanks README.md 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 + Customer service responsiveness + Project management kanban planning + Inter-process communication message queues + Devops continuous deployment pipelines * Queue terminology + Queue types and service types + Queue dropouts * Queueing theory notation + Arrival rate, service rate, dropout rate + Utilization ratio + Error ratio + Lead time, wait time, work time, step time + Count + Standard notation * Activity tracking + Activity examples + Little's Law + Key performance indicators (KPIs) * Epilog + See also + Thanks 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: * l: arrival rate. This measures how fast new items are coming into the queue. * m: service rate. This measures how fast items in the queue are being handled. * s: dropout rate. This measures how fast items are skipping out the queue unhandled. Examples: * l = m means the arrival rate equals the service rate; the queue is staying the same size, other than dropouts. * l > m means the arrival rate is greater than the service rate; the queue is getting larger, other than dropouts. * l < m 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: * r: utilization ratio = l / m Examples: * r = 1 means the arrival rate is equal to the service rate; the queue is staying the same size. * r > 1 means the arrival rate is greater than the service rate; the queue is getting larger. * r < 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: * e: error ratio = service failure count / service total count Examples: * e = 0 means no errors. * e = 0.1 means 10% of services have an error. * e = 1 means every service has an error. Lead time, wait time, work time, step time We track four times: * t: lead time = from arrival to finish * o: wait time = from arrival to start of work * ph: work time = from start of work to finish * th: step time = from finish to next finish Examples: * t = 5s means an item is added to the queue, then serviced 5 seconds later. * o = 4s means an item waits in the queue for 4 seconds, then work starts. * ph = 1s means an item takes 1 second of work, then is complete. * th = 1s means there's 1 second between one completion and the next completion. Count We count items often, and we use this notation: * k: count Example: * k = 100 means there are 100 items. * k > 100 means there are more than 100 items. * k [?] 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: * Ak: Activity count: how many items are in the queue. * Al: Activity arrival rate: how many items are incoming per time unit. * Am: Activity service rate: how many items are completed per time unit. * As: Activity dropout rate: how many items are abandoned per time unit. * Ar: Activity utilization ratio: how many items are arriving vs. completing. * Ae: Activity error ratio: how many items are completed with errors vs. total. * At: Activity lead time: how much time elapses from requested to completed. * Ao: Activity wait time: how much time elapses from requested to started. * Aph: Activity work time: how much time elapses from started to completed. * Ath: 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 l 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. * l is the long-term average effective arrival rate. * W is the average time that a customer spends in the system. * L = 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: * Dt = Delivery lead time. Product teams may say "from concept to customer" or "from idea to implementation". * Dm = Delivery service rate. Devops teams may say "deployment frequency" or "we ship X times per day". * De = Delivery error ratio. Quality teams may say "change fail rate" or "percentage of rollbacks". * Rt = Restore lead time. Site reliability engineers may say "time to restore service" or "mean time to restore (MTTR)". Epilog See also Wikipedia: * Queueing theory * M/M/1 queue * Little's law * Markov chain Wikipedia areas where we use queues in many projects: * Project management * Message queue * DevOps Introductions by John D. Cook: * The science of waiting in line * Server utilization: Joel on queuing * What happens when you add a new teller? Introductions with more detail: * Queuing Theory: Simple Definition, Notation and Terminology * The most important thing to understand about queues - By Dan Slimmon * Operations Research - Notes. By J E Beasley * Little's Law - the basis of Lean and Kanban * Investopedia: Queueing theory Blog posts: * It's time for some queueing theory - By Kottke 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. About Queueing theory: an introduction for software development Resources Readme Code of conduct Code of conduct Activity Stars 1.8k stars Watchers 45 watching Forks 68 forks Report repository Releases No releases published Sponsor this project * * patreon patreon.com/joelparkerhenderson * ko_fi ko-fi.com/joelparkerhenderson * https://paypal.me/joelparkerhenderson Learn more about GitHub Sponsors Packages 0 No packages published Contributors 3 * @joelparkerhenderson joelparkerhenderson Joel Parker Henderson * @madislohmus madislohmus Madis Lohmus * @0xflotus 0xflotus 0xflotus Footer (c) 2023 GitHub, Inc. Footer navigation * Terms * Privacy * Security * Status * Docs * Contact GitHub * Pricing * API * Training * Blog * About You can't perform that action at this time.