🖼️ See the drawing + lab 🏠 Course home 🌿 Branch on GitHub ✏️ View source

🖼️ आकृती आणि labThe drawing + lab पूर्ण पानावर उघडा ↗Open full page ↗

🚰 धडा 09 — Queueing, Little आणि Amdahl: पाण्याच्या टेबलावरची रांग

📍 तुम्ही इथे आहात: 12 पैकी धडा 09 · मागे: lesson-08-concurrency · पुढे: lesson-10-database-queries

📦 या ब्रँचमध्ये काय आहे

धडे 01–08, आणि busy service समजावणारे तीन नियम: queueing (server जसा अधिक busy होतो, तसे थांबणे आधी हळू वाढते, मग स्फोट होतो), Little's law (एका वेळी system मध्ये किती requests आहेत) आणि Amdahl's law (जो भाग वाटून देता येत नाही तो speed-up ला मर्यादा घालतो). perf/demo.py मधील queueing() आणि perf/sim.py मधील mm1_wait_ms, simulate_queue, littles_law आणि amdahl.

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

पाण्याचे टेबल एकच आहे 🚰, आणि ऐश्वर्याला एक कप भरायला 10 सेकंद लागतात.

धावपटू अधूनमधून येतात तेव्हा टेबल अर्धा वेळ मोकळे असते. धावपटू थोडेच थांबते: कपासह सुमारे 20 सेकंद.
धावपटू वारंवार येतात, आणि टेबल 90% वेळ busy असते, तेव्हा धावपटू सुमारे 100 सेकंद थांबते.
99% busy असताना: सुमारे 1000. 😱

इतके वाईट, इतक्या लवकर का होते? कारण धावपटू समान अंतराने येत नाहीत. कधी कधी तिघी एकदम येतात. टेबल जवळजवळ नेहमी busy असेल तर त्या गर्दी भरून काढण्यासाठी त्याला कधीच शांत क्षण मिळत नाही.

क्रीडा दिनाचे आणखी दोन नियम:

Little चा नियम: दर सेकंदाला 80 धावपटू येत असतील आणि प्रत्येक जण टेबलाजवळ 0.05 सेकंद घालवत असेल, तर सरासरी 4 धावपटू टेबलाजवळ असतात.
सर्वात हळू टप्प्याचा नियम (Amdahl): रिलेमध्ये शर्यतीचा 90% भाग अनेक धावपटूंमध्ये वाटता येतो, पण 10% हा असा एक टप्पा आहे जो फक्त एकच धावपटू धावू शकते. अगणित धावपटू असल्या तरी संघ जास्तीत जास्त 10 पट वेगवान होऊ शकतो, कारण तो एक टप्पा कधीच लहान होत नाही.

🗺️ आकृती

flowchart LR
    arr["🏃 runners arrive<br/>at random"] --> q["🚶🚶🚶 the queue"] --> t["🚰 one table<br/>10 ms a cup"]
    u50["50% busy → 20 ms"] --> u90["90% busy → 100 ms"] --> u99["99% busy → 1000 ms"]
    little["Little: L = λW<br/>80/s × 50 ms = 4"]
    amd["Amdahl, 90% parallel:<br/>8 runners 4.71× · endless 10×"]

🗺️ रेखाटलेली आवृत्ती + एक lab: https://school-edh.pages.dev/performance/lesson-diagrams.html#l09

❓ काय

Utilisation (ρ, "rho") — server busy असलेल्या वेळेचा वाटा: arrival rate × service time. 80 requests/s × 10 ms = 0.8 = 80%.
M/M/1 — सर्वात सोपे queueing model: random (Poisson) arrivals, random (exponential) service times, एक server, आधी येईल त्याला आधी सेवा. त्याचा system मधला सरासरी वेळ W = S / (1 − ρ) (S = service time); फक्त थांबण्याचा भाग ρ·S / (1 − ρ) आहे. हे एक अंदाजे मोजमाप (approximation) आहे — खरे traffic अधिक झटकेदार किंवा अधिक सुरळीत असते — पण त्याचा आकार हाच धडा आहे: 50% busy वर W = 2S; 90% वर 10S; 99% वर 100S.
बदलत्या स्वरूपाला (variability) महत्त्व आहे — इतर arrival आणि service patterns साठी, Kingman चे सूत्र (आणखी एक approximation) सांगते की प्रतीक्षा ρ / (1 − ρ) सोबत आणि arrivals व service times किती बदलतात त्यासोबत वाढते. सुरळीत traffic आणि स्थिर service म्हणजे त्याच utilisation वर लहान रांगा.
Little's law: L = λ W — system मधील सरासरी संख्या (L) = arrival rate (λ) × प्रत्येकाने तिथे घालवलेला सरासरी वेळ (W). कोणत्याही स्थिर system साठी, पुरेशा दीर्घ काळाची सरासरी घेतल्यास, arrivals चा pattern कसाही असला तरी हे लागू होते. Connection pools, thread pools आणि queues चा आकार ठरवण्यासाठी हे वापरा.
Amdahl's law — कामाचा p इतका भाग n workers वापरू शकत असेल आणि उरलेला नाही, तर सर्वोत्तम speed-up 1 / ((1 − p) + p / n) असतो, आणि 1 / (1 − p) पेक्षा कधीच जास्त नाही. Serial भाग — एक lock, सगळे update करतात अशी database ची एकच row, क्रमानेच चालावी लागणारी पायरी — हा रिलेतील सर्वात हळू धावपटू आहे.
Amdahl च्या पलीकडे — workers ना समन्वय करावा लागत असेल (locks, cores दरम्यान cache traffic) तर workers वाढवल्याने गोष्टी अधिक हळूही होऊ शकतात. Neil Gunther चा Universal Scalability Law हा खर्च जोडतो. अनेक machines वर scale out करणे हा Scaling school चा विषय आहे.

🤔 का

कारण "server फक्त 90% CPU वर आहे, अजून जागा आहे" अशानेच outages सुरू होतात. 90% busy वर सरासरी request आधीच 10 service times थांबते, आणि छोटासा burst ती खूप वर ढकलतो. Latency-sensitive service साठी सुरक्षित जागा 100% busy च्या बऱ्याच खाली आहे. आणि 16 वा worker जोडल्याने फारशी मदत का झाली नाही हे Amdahl समजावतो: serial भागच आधीपासून बहुतेक वेळ घेत होता.

🔧 कसे (या repo मध्ये)

perf/sim.py मधील mm1_wait_ms(service_ms, util) हे M/M/1 सूत्र S / (1 − ρ) आहे. simulate_queue(rate, service_ms, n, seed) एका first-come first-served server चे simulation करते, arrivals मधील seeded random (exponential) अंतरे आणि random service times सह, आणि प्रत्येक request चा system मधील वेळ परत देते. littles_law(rate, wait_ms) म्हणजे λW; amdahl(p, n) म्हणजे speed-up चे सूत्र. perf/demo.py मधील queueing() सूत्राची 20,000 simulated धावपटूंशी तुलना करते.

🧪 करून पाहा

python3 perf/demo.py queueing
python3 - <<'EOF'
import sys; sys.path.insert(0, "perf"); from sim import mm1_wait_ms, littles_law, amdahl
for s in (10, 5):
    print(f"service {s:>2} ms: " + " · ".join(f"{u:.0%} busy → {mm1_wait_ms(s, u):.0f} ms" for u in (0.5, 0.7, 0.9)))
print("Little: 200 req/s × 250 ms =", littles_law(200, 250), "requests in flight")
for p in (0.5, 0.9, 0.99):
    print(f"parallel share {p:.0%}: 8 workers → {amdahl(p, 8):.2f}× · the limit {1 / (1 - p):.0f}×")
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

queueing हे छापते:

── one water table, 10 ms to serve a runner · M/M/1 approximation: time at the table = 10 ms ÷ (1 − utilisation)
   utilisation 50% → formula     20 ms · simulated (20,000 runners)     20 ms
   utilisation 80% → formula     50 ms · simulated (20,000 runners)     49 ms
   utilisation 90% → formula    100 ms · simulated (20,000 runners)    104 ms
   utilisation 95% → formula    200 ms · simulated (20,000 runners)    186 ms
   utilisation 99% → formula   1000 ms · simulated (20,000 runners)    519 ms
   near 100% busy, the wait explodes (and a short simulation has not caught up with it yet)
── Little's law L = λW: 80 runners/s × 50 ms = 4 runners at the table on average
── Amdahl's law: 90% of the relay can be shared out, 10% is one runner's leg that nobody can help with
   2 runners → 1.82× · 4 runners → 3.08× · 8 runners → 4.71× · 16 runners → 6.40× · endless runners → 10.00×

तुमचा snippet हे छापतो:

service 10 ms: 50% busy → 20 ms · 70% busy → 33 ms · 90% busy → 100 ms
service  5 ms: 50% busy → 10 ms · 70% busy → 17 ms · 90% busy → 50 ms
Little: 200 req/s × 250 ms = 50.0 requests in flight
parallel share 50%: 8 workers → 1.78× · the limit 2×
parallel share 90%: 8 workers → 4.71× · the limit 10×
parallel share 99%: 8 workers → 7.48× · the limit 100×

🏁 तुम्ही आत्ताच काय सिद्ध केले

50–90% busy वर simulation सूत्राशी जुळले (20, 49, 104 ms). 99% वर ते फक्त 519 ms दाखवले, 1000 नव्हे — इतकी busy रांग तिच्या सरासरीपर्यंत पोहोचायला खूप वेळ घेते, आणि हीच एक धोक्याची सूचना आहे: 100% जवळ प्रतीक्षा फक्त लांब नसते, ती अनिश्चित असते. Service time अर्धा केल्याने (धडा 03 सारखा उपाय) त्याच utilisation वर प्रत्येक प्रतीक्षा अर्धी झाली. आणि 50% serial भाग असताना 8 workers नी फक्त 1.78× दिले.

⚠️ नेहमीच्या चुका

latency-sensitive service साठी 90–100% utilisation गृहीत धरून capacity चा आराखडा करणे
Little's law (rate × pool मधील वेळ) ऐवजी अंदाजाने pool चा आकार ठरवणे
वेळ serial भागात (एक lock, एक hot row, एक leader) जात असताना workers वाढवणे
पूर्णपणे समान traffic ने test करणे, ज्यामुळे रांगा निर्माण करणारे bursts लपतात
तासाभराच्या utilisation ची सरासरी घेणे, ज्यामुळे 100% वरची मिनिटे लपतात

🏭 प्रत्यक्ष वापरात

Database connection pool चा आकार Little's law ने ठरवा. 200 requests/s वर, प्रत्येक request 25 ms connection धरून ठेवत असेल तर: 200 × 0.025 = सरासरी 5 connections busy — bursts साठी जादा जागा ठेवा, आणि लक्षात ठेवा की प्रत्येक app instance चा स्वतःचा pool असतो. खऱ्या account वर, SQLAlchemy:

engine = create_engine(DB_URL, pool_size=10, max_overflow=5, pool_timeout=2)

फक्त CPU नव्हे, तर utilisation आणि queue length वर लक्ष ठेवा. Linux वर:

vmstat 1           # r = runnable threads waiting for a CPU; above the core count means a queue
iostat -x 1        # %util and aqu-sz (average queue size) for each disk

Prometheus मध्ये, worker pool चा busy वाटा (metric ची नावे तुमच्या exporter वर अवलंबून असतात):

sum(rate(worker_busy_seconds_total[5m])) / count(worker_up)

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: प्रत्येक latency-sensitive service ला एक utilisation target द्या (उदाहरणार्थ "60–70% busy च्या वर गेल्यास scale out करा"), queue length वर alert लावा, आणि workers वाढवण्याआधी serial भाग शोधा.

⏭️ पुढे

Requests सर्वाधिक रांगेत थांबतात ती जागा म्हणजे database. पुढे: प्रत्येक पत्रक वाचून, की index वापरून, एका धावपटूचे laps शोधणे — EXPLAIN QUERY PLAN.

git checkout lesson-10-database-queries

🚰 Lesson 09 — Queueing, Little & Amdahl: the queue at the water table

📍 You are here: Lesson 09 of 12 · Previous: lesson-08-concurrency · Next: lesson-10-database-queries

📦 What's in this branch

Lessons 01–08, plus the three laws that explain a busy service: queueing (as a server gets busier, waiting grows slowly, then explodes), Little's law (how many requests are in the system at once) and Amdahl's law (the part you cannot share out caps the speed-up). queueing() in perf/demo.py and mm1_wait_ms, simulate_queue, littles_law and amdahl in perf/sim.py.

🧒 Explain like I'm 5

There is one water table 🚰, and Aishwarya takes 10 seconds to fill a cup.

When runners come now and then, the table is free half the time. A runner waits a little: about 20 seconds, cup included.
When runners come often, and the table is busy 90% of the time, a runner waits about 100 seconds.
At 99% busy: about 1000. 😱

Why does it get so bad, so fast? Because runners do not arrive evenly. Sometimes three come at once. When the table is almost always busy, it never gets a quiet moment to catch up with those bunches.

Two more rules of sports day:

Little's rule: if 80 runners arrive every second and each spends 0.05 seconds at the table, then on average 4 runners are at the table.
The slowest leg rule (Amdahl): in a relay, 90% of the race can be shared among many runners, but 10% is one leg that only one runner can run. Even with endless runners, the team can be at most 10 times faster, because that one leg never gets shorter.

🗺️ Diagram

flowchart LR
    arr["🏃 runners arrive<br/>at random"] --> q["🚶🚶🚶 the queue"] --> t["🚰 one table<br/>10 ms a cup"]
    u50["50% busy → 20 ms"] --> u90["90% busy → 100 ms"] --> u99["99% busy → 1000 ms"]
    little["Little: L = λW<br/>80/s × 50 ms = 4"]
    amd["Amdahl, 90% parallel:<br/>8 runners 4.71× · endless 10×"]

🗺️ Drawn version + a lab: https://school-edh.pages.dev/performance/lesson-diagrams.html#l09

❓ What

Utilisation (ρ, "rho") — the share of time a server is busy: arrival rate × service time. 80 requests/s × 10 ms = 0.8 = 80%.
M/M/1 — the simplest queueing model: random (Poisson) arrivals, random (exponential) service times, one server, first come first served. Its average time in the system is W = S / (1 − ρ) (S = service time); the waiting part alone is ρ·S / (1 − ρ). It is an approximation — real traffic is burstier or smoother — but its shape is the lesson: at 50% busy, W = 2S; at 90%, 10S; at 99%, 100S.
Variability matters — for other arrival and service patterns, Kingman's formula (another approximation) says the wait grows with ρ / (1 − ρ) and with how variable arrivals and service times are. Smoother traffic and steadier service mean shorter queues at the same utilisation.
Little's law: L = λ W — the average number in the system (L) equals the arrival rate (λ) times the average time each one spends there (W). It holds for any stable system, averaged over a long enough time, whatever the pattern of arrivals. Use it to size connection pools, thread pools and queues.
Amdahl's law — if a fraction p of the work can use n workers and the rest cannot, the best speed-up is 1 / ((1 − p) + p / n), and never more than 1 / (1 − p). The serial part — a lock, a single database row everybody updates, a step that must run in order — is the slowest runner in the relay.
Beyond Amdahl — adding workers can even make things slower when they have to coordinate (locks, cache traffic between cores). Neil Gunther's Universal Scalability Law adds that cost. Scaling out across many machines is the Scaling school.

🤔 Why

Because "the server is only at 90% CPU, there is room left" is how outages start. At 90% busy the average request already waits 10 service times, and a small burst pushes it much higher. The safe place for a latency-sensitive service is well below 100% busy. And Amdahl explains why adding a 16th worker barely helped: the serial part was already most of the time.

🔧 How (in this repo)

mm1_wait_ms(service_ms, util) in perf/sim.py is the M/M/1 formula S / (1 − ρ). simulate_queue(rate, service_ms, n, seed) simulates one first-come first-served server with seeded random (exponential) gaps between arrivals and random service times, and returns every request's time in the system. littles_law(rate, wait_ms) is λW; amdahl(p, n) is the speed-up formula. queueing() in perf/demo.py compares the formula with 20,000 simulated runners.

🧪 Try it

python3 perf/demo.py queueing
python3 - <<'EOF'
import sys; sys.path.insert(0, "perf"); from sim import mm1_wait_ms, littles_law, amdahl
for s in (10, 5):
    print(f"service {s:>2} ms: " + " · ".join(f"{u:.0%} busy → {mm1_wait_ms(s, u):.0f} ms" for u in (0.5, 0.7, 0.9)))
print("Little: 200 req/s × 250 ms =", littles_law(200, 250), "requests in flight")
for p in (0.5, 0.9, 0.99):
    print(f"parallel share {p:.0%}: 8 workers → {amdahl(p, 8):.2f}× · the limit {1 / (1 - p):.0f}×")
EOF

✅ Verify — what you should see

queueing prints:

── one water table, 10 ms to serve a runner · M/M/1 approximation: time at the table = 10 ms ÷ (1 − utilisation)
   utilisation 50% → formula     20 ms · simulated (20,000 runners)     20 ms
   utilisation 80% → formula     50 ms · simulated (20,000 runners)     49 ms
   utilisation 90% → formula    100 ms · simulated (20,000 runners)    104 ms
   utilisation 95% → formula    200 ms · simulated (20,000 runners)    186 ms
   utilisation 99% → formula   1000 ms · simulated (20,000 runners)    519 ms
   near 100% busy, the wait explodes (and a short simulation has not caught up with it yet)
── Little's law L = λW: 80 runners/s × 50 ms = 4 runners at the table on average
── Amdahl's law: 90% of the relay can be shared out, 10% is one runner's leg that nobody can help with
   2 runners → 1.82× · 4 runners → 3.08× · 8 runners → 4.71× · 16 runners → 6.40× · endless runners → 10.00×

Your snippet prints:

service 10 ms: 50% busy → 20 ms · 70% busy → 33 ms · 90% busy → 100 ms
service  5 ms: 50% busy → 10 ms · 70% busy → 17 ms · 90% busy → 50 ms
Little: 200 req/s × 250 ms = 50.0 requests in flight
parallel share 50%: 8 workers → 1.78× · the limit 2×
parallel share 90%: 8 workers → 4.71× · the limit 10×
parallel share 99%: 8 workers → 7.48× · the limit 100×

🏁 What you just proved

The simulation agreed with the formula at 50–90% busy (20, 49, 104 ms). At 99% it showed only 519 ms, not 1000 — a queue that busy takes a very long time to reach its average, which is itself a warning: near 100%, the wait is not just long, it is unpredictable. Halving the service time (lesson 03's kind of fix) halved every wait at the same utilisation. And with a 50% serial part, 8 workers gave only 1.78×.

⚠️ Common mistakes

planning capacity for 90–100% utilisation of a latency-sensitive service
sizing a pool by guessing instead of Little's law (rate × time in the pool)
adding workers when the time is in a serial part (a lock, one hot row, one leader)
testing with perfectly even traffic, which hides the bursts that make queues
averaging utilisation over an hour, which hides the minutes at 100%

🏭 In production

Size a database connection pool with Little's law. At 200 requests/s, each holding a connection for 25 ms: 200 × 0.025 = 5 connections busy on average — give it headroom for bursts, and remember every app instance has its own pool. On a real account, SQLAlchemy:

engine = create_engine(DB_URL, pool_size=10, max_overflow=5, pool_timeout=2)

Watch utilisation and queue length, not just CPU. On Linux:

vmstat 1           # r = runnable threads waiting for a CPU; above the core count means a queue
iostat -x 1        # %util and aqu-sz (average queue size) for each disk

In Prometheus, the busy share of a worker pool (metric names depend on your exporter):

sum(rate(worker_busy_seconds_total[5m])) / count(worker_up)

🏭 Why this matters in production: give each latency-sensitive service a utilisation target (for example "scale out above 60–70% busy"), alert on queue length, and look for the serial part before adding workers.

⏭️ Next

The most common place requests queue is the database. Next: finding one runner's laps by reading every sheet, or by using the index — EXPLAIN QUERY PLAN.

git checkout lesson-10-database-queries

← Previousconcurrency Next →database queries

This page is the lesson's README from the lesson-09-queueing branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.