[HN Gopher] Queueing Theory
___________________________________________________________________
Queueing Theory
Author : tosh
Score : 167 points
Date : 2022-10-14 11:48 UTC (1 days ago)
(HTM) web link (en.wikipedia.org)
(TXT) w3m dump (en.wikipedia.org)
| dang wrote:
| Related:
|
| _Seven Insights into Queueing Theory [pdf]_ -
| https://news.ycombinator.com/item?id=20313834 - June 2019 (17
| comments)
|
| _It's Time for Some Queueing Theory_ -
| https://news.ycombinator.com/item?id=20290042 - June 2019 (62
| comments)
|
| _Show HN: Queueing theory intro for software developers_ -
| https://news.ycombinator.com/item?id=18995551 - Jan 2019 (12
| comments)
|
| _Queueing theory: The science of waiting in line_ -
| https://news.ycombinator.com/item?id=18983072 - Jan 2019 (134
| comments)
|
| _Queueing Theory -- Why the other lines always seem to move
| faster than yours_ - https://news.ycombinator.com/item?id=2038752
| - Dec 2010 (15 comments)
| MikeYasnev007 wrote:
| rockmeamedee wrote:
| As a regular programmer, I got really into queuing theory
| thinking I was going to learn secrets of performance tuning, then
| was slightly disappointed.
|
| But it turns out the simple parts of it go a long way! Eg at work
| we have a single deployment queue for a monorepo. At first approx
| this is an MD1 queue (deploy job takes roughly the same amount of
| time every time, though arrivals are actually way spikier than
| poisson), and realized that wait time was inversely proportional
| to total utilization.
|
| While the infra team was saying "we do X deploys per day out of
| 4X and are only at 25% capacity", I realized even hitting 2X
| would more than double the already bad wait time.
|
| What happened is that a few initiatives were under way to
| increase capacity, but then out of nowhere the queue got log
| jammed (bc of high arrival rate variability) and we had to switch
| to Gitlab merge trains, which run CI concurrently on the
| optimistic result of merging. I wrote about it here:
| https://engineering.outschool.com/posts/doubling-deploys-git...
|
| I'm planning on writing a blog post about the math of CI/CD
| deploy queues as G/D/1 queues.
|
| For a programmer's view of queuing theory and great performance
| testing foundations, I highly recommend "Analysing Computer
| system performance with Perl:PDQ" (don't worry about the Perl,
| the book is very relevant)
| http://www.perfdynamics.com/iBook/ppa_new.html, which shows
| examples of queues inside computer systems and how to model them.
| The author has a nice little library to model different computer
| systems you come across.
|
| I liked realizing that the dreaded "coordinated omission" problem
| in load testing (when you can only generate X rps and the server
| can handle more than that, your numbers are bunk) is actually
| when you think you are modeling an open system but you don't have
| enough resources and end up seeing the closed system behaviour.
| pramodbiligiri wrote:
| That was a neat blog post! Can you clarify this bit: "If a
| pipeline fails, the associated MR is kicked from the train and
| all preceding pipelines are restarted." - Do you mean all the
| pipelines _already started_ are restarted? Because I'm guessing
| that if a pipeline fails, the _preceding_ pipelines shouldn 't
| be affected, strictly speaking.
| cool-RR wrote:
| Off-topic: I'm toying with GPT-3 and I used it to extend
| rockmeamedee's comment: https://gist.github.com/cool-
| RR/12b0fc8106f6df18925de632f2b6...
| kqr wrote:
| That's not what coordinated omission is. CO happens when your
| load generator can do, say, 500 requests/second, and you're
| aiming for something well below that, e.g. 100, but! the top
| throughput for the server is 80 requests per second, and
| instead of building up an infinite queue, the load generator
| throttles itself to roughly 80 requests per second.
|
| Why would you build a load generator like this? Normally
| because you run out of threads -- you have 800 parallel
| requests in flight and you can't open a new one until one has
| returned.
|
| Correcting for CO takes a mathematical sleight of hand.
| gillh wrote:
| Anyone building web-scale apps should check out Aperture[1] - a
| flow control platform that dynamically adjusts concurrency limits
| on services when queue buildup is detected. Aperture has a
| weighted fair queuing scheduler that prioritizes workloads when
| concurrency limits are adjusted.
|
| [1] https://github.com/fluxninja/aperture
| sriram_malhar wrote:
| Heh. I'm curious how a link to a wikipedia entry made it to the
| front page, or why it was even submitted at all! Is it Poisson's
| birthday or something?
| welder wrote:
| Yea, are we going to see a link to Wikipedia's page for
| Calculus next?
|
| HN is for _new_ information, not wikipedia pages that happen to
| be interesting but are already common knowledge. Although I
| guess it does technically fit the guidelines [1].
|
| [1] https://news.ycombinator.com/newsguidelines.html
| IshKebab wrote:
| This happens all the time and they always say it is fine
| according to the HN rules. I agree it is a bit stupid. It's
| clearly not _news_.
| User23 wrote:
| Ever hear the phrase "that's news to me?"
| orzig wrote:
| I, for one, appreciated the reminder that this mathematical
| subject exists. and I've loved some of the ideas discussed
| in this thread.
| kqr wrote:
| HN is for information that might be new _to enough of its
| readers_ , even if the information itself was not published
| in the last few days.
| welder wrote:
| I would assume most programmers have heard of queueing
| theory, and I thought most HN readers were programmers. The
| comments look interesting and it's not against the
| guidelines, I was just surprised to see it on the front
| page.
| pthreads wrote:
| Perhaps, however I find decent value in some of these kinds
| of submissions - it is in the comments. The book
| recommendations and benefits of queueing theory mentioned
| here have already been worth it for me. I love going down
| technical rabbit holes.
| isaacg wrote:
| I'm a queueing theory researcher, just completing my PhD. My
| advisor, Mor Harchol-Balter, wrote one of the most popular
| textbooks in the area: http://performancemodeling.org/. If anyone
| has questions about the field, please ask, I'd love to answer any
| questions.
|
| Here's my website, if you want to see more of what I do:
| https://isaacg1.github.io/
| mapme wrote:
| what are the most common types of queues for large data center
| applications (eg. Stateless app that handles rpcs, running on N
| machines). Are they mostly M/M/N? For example, is memcached
| different than nginx, or Postgres?
| isaacg wrote:
| While an M/M/n is a good starting point, there are several
| extra important features to capture.
|
| First, many of these applications have a load-balancing step,
| where arriving jobs are dispatched to queues at each of the
| machines. The performance will depend on how this load-
| balancing is done.
|
| Second, some applications will parallelize across many cores
| or machine, while others will run each job on a single core
| or machine. This obviously has major implications for
| performance.
|
| Third, your application may have variance in interarrival
| times or in job completion lengths. This is also important to
| measure and incorporate into a model. Something like
| Kingman's formula can be useful:
| https://en.wikipedia.org/wiki/Kingman%27s_formula
| mapme wrote:
| That is very helpful, thank you! Good point on load
| balancing, and also retries, back pressure, etc. would
| change it as well.
| mjb wrote:
| That really is a great book, and very approachable! All the
| examples are practical, results derived clearly, and a nice
| build up.
|
| Here's my question for you: queue theory is a nice tool, but
| most of the classic results are about systems (like M/M/c) that
| don't match the real world in important ways. Are there good
| rules of thumb for thinking about how different changes (e.g.
| burstier than Poisson, seasonality, constrained queue lengths,
| etc) map to these results?
|
| Obviously, simulation is a powerful tool for more general
| systems, but being able to reason about effects quickly is
| super useful.
| kqr wrote:
| I'm a little confused -- it sounds like you've read the book,
| but it also answers all of your question. If you haven't had
| time to finish it, do!
| [deleted]
| isaacg wrote:
| Thanks for the question!
|
| For thinking about bursty arrivals, a good rule of thumb is
| to look at the variance of the inter-arrival times. The key
| number is the variance of interarrival times divided by the
| mean interarrival time squared. The waiting time in a system
| with bursty arrivals will roughly be larger than the M/M/c by
| this multiplicative factor. Kingman's formula is the
| equivalent for the single-server setting:
| https://en.wikipedia.org/wiki/Kingman%27s_formula
|
| For seasonality, if the arrival rates fluctuate over a long
| time period relative to the typical waiting time, it makes
| sense to just do separate calculations for the different
| conditions you experience. If the fluctuation is very fast,
| just use the average arrival rate.
|
| For constrained queue lengths, there are a lot of theoretical
| results in this area, such as the M/M/c/c model:
| https://en.wikipedia.org/wiki/M/M/c_queue. The second "c"
| refers to the buffer size.
| mjb wrote:
| > For seasonality, if the arrival rates fluctuate over a
| long time period relative to the typical waiting time, it
| makes sense to just do separate calculations for the
| different conditions you experience. If the fluctuation is
| very fast, just use the average arrival rate.
|
| Thanks, that makes sense. More quantitatively, about where
| would get set the bar on "very fast"? Is it ~1x the mean
| interarrival time, or ~1 million x?
|
| By the way, I really enjoyed your "Nudge" paper from last
| year. The result about FCFS was very surprising to me!
| isaacg wrote:
| There's a transition zone from "fast" to "slow"
| fluctuations around the mean waiting time that's more
| complicated and is an area of active research. If the
| fluctuations are 5x below the mean waiting time, I'd
| guess the effects of fluctuation will be gone.
|
| Here's a recent paper on the topic, if you're interested
| in the cutting edge research: http://www.cs.cmu.edu/afs/c
| s.cmu.edu/user/harchol/www/Papers...
|
| Thanks, I'm glad to hear you liked the Nudge result!
| mjb wrote:
| Thanks!
|
| One more: my understanding is that in Nudge I need to
| know processing time, but in FCFS I don't. How sensitive
| is your optimality result to errors in processing time
| estimates (I don't recall this being covered in the
| paper, but if it is feel free to tell me).
|
| In the cloud services and databases settings, we seldom
| have accurate processing time estimates until we're quite
| far down processing a request (post-auth, post-parse, at
| least, but also for databases post-query-plan).
| isaacg wrote:
| The only thing we use processing time for in the Nudge
| paper is to classify jobs as "Large", "Small" or "Other".
| If instead of exact processing times, we had estimates,
| the result would still work as long as a job that was
| estimated to large was typically longer than a job
| estimated to be small. So Nudge totally works in these
| more realistic settings.
|
| If the estimates were super noisy, you might be better
| off using Nudge very sparingly, only when you're more
| confident about the relative sizes.
| greymalik wrote:
| Where does one start with understanding and applying queueing
| theory to real world problems? I manage a system that receives a
| highly variable number of requests that are queued for processing
| by a horizontally scalable number of VMs up to a resource cap.
| Success of this system is based on the 95p of aggregate
| processing times over a specified time period being below a
| certain threshold value. It's my responsibility to manage the
| system such that this threshold is always met. I also need to
| pre-allocate additional system capacity to the right bottlenecks
| based on predicted increases in demand. So it sounds like knowing
| queuing theory could be a big help. Where do I begin?
| mjb wrote:
| Simulation, as kqr said. I like to use the classic queue theory
| results (e.g. results on M/M/1 and M/M/c) as unit tests for the
| simulators I build. I've found that application of queue theory
| very helpful in avoiding silly simulation bugs.
| kqr wrote:
| The practical answer is to simulate it. Even if you knew a
| bunch of queueing theory, you would end up simulating something
| like this.
|
| If you want inspiration and some background, though, I can
| strongly recommend the book mentioned downthread:
| http://www.performancemodeling.org/
|
| You're absolutely right that queueing theory would be helpful.
| A little part of me is wondering how on Earth you're doing your
| job without it!
| setr wrote:
| I've implemented queuing simulators in the past, but two
| questions I've always been bugged by (which I feel like are
| easily answered if I ever took proper math courses...):
|
| 1. I don't understand how you "know" you're in the steady
| state, beyond looking at the graph -- I've always just made
| it go like 10k steps to force it, but this seems needlessly
| wasteful. I imagine you could track the derivative but if it
| oscillates?
|
| 2. I don't know how to verify if the distributions are
| poisson/exponential in reality, except by plotting
|
| More relevant note, I've always been surprised by how little
| exists online on the subject, and how little code it actually
| requires; I forget the terms but multiple event classes,
| multiple agent, infinite buffer sim took maybe 100 LoC C#
| from stdlib. Maybe 60 LoC in python -- probably 25% was just
| tracking the stats I wanted like wait time.
|
| Biggest performance trick is that poison inter-arrival rate
| is exponential, and so you can generate all arrival times up
| front; then instead of simulating every second, you can just
| skip forward in time to when the events actually occur... so
| your sim scales on number of events occurring, rather than
| length of time simulated. Pretty sure you can even do
| arbitrarily length simulations in constant memory but never
| tried
| toolslive wrote:
| Yes, even the experts quickly go "pfff, this is getting too
| complicated, let's simulate"
| kfarr wrote:
| Correct, in real life queued objects (or people) are "agents"
| that exhibit imperfect behavior that doesn't really adhere to
| a perfect queuing equation. Classic example is motor vehicle
| throughput: queuing equations might be helpful in broad
| strokes for coarse estimates but need agent level simulation
| to accurately predict outcome.
| aaron695 wrote:
| Maro wrote:
| I studied queueing theory at school 20 years ago for my CompSci
| degree. Last year I implemented a QT model (relatively simple
| version of M/M/1) to control the queueing length at a very large
| chain of hypermarkets (core mechanism: use historic lambda and mu
| timeseries to predict future lambda and mu, reverse engineer the
| formula to get the right number of checkout counters to keep
| average queueing length to the desired number of seconds). The
| thing is now used across many countries. Very satisfying payoff
| after 20 years..
| bad416f1f5a2 wrote:
| Erlang's formulas are incredibly applicable to things we work on
| today - and shockingly unknown to many developers.
|
| I've used them several times to show that a proposed system is
| mathematically impossible: "if the backend processes n
| requests/sec with a max response time of X, and the P95 of the
| backend is Y, the queue satisfaction is 0%". People think you're
| a wizard while you're just plugging numbers into a century-old
| formula.
| hrunt wrote:
| I worked for a Usenet provider for a number of years designing
| and writing the software that powered their Usenet feeding
| infrastructure. The Usenet feed is basically a giant stream of
| articles, and we used queuing theory to scale out the systems
| that read it in, process it, and distribute it to readers.
|
| My experience with the formula's is a little different from
| yours. People thought what I showed them couldn't be true. "If
| the feed is X articles/second and system's P95 is Y, the
| backlog will continue to grow," would often be met with, "That
| can't be true ..."
| erk__ wrote:
| In Denmark Erlang is probably more know for his logarithm
| tables since those were used for many years in the schools
| before calculators became normal
| cmrdporcupine wrote:
| Totally! I worked for a time, in the mid 00s, at a company that
| built realtime dashboards for old school telephone call centres
| (contact centers) and it was there that I became aware of the
| _other_ (original) meaning of Erlang, beyond the nifty cool up
| and coming programming language.
|
| For a while for me _everything_ was about queuing theory. Since
| then I keep forgetting and remembering things about this later.
|
| Strikes me that I would like to have an easy to use and generic
| library for Rust with the various formulas etc. in it.
| jrochkind1 wrote:
| What's the other original meaning? Googling I find no
| meanings except the programming language, although it was
| originally used by telecom. But it seems to be the same
| language originally used by telecom that is now getting use
| elsewhere, not two languages with the same name or two
| meanings, no?
| https://en.wikipedia.org/wiki/Erlang_(programming_language)
| dadadad100 wrote:
| Google harder :)
| https://en.wikipedia.org/wiki/Erlang_(unit)
| jrochkind1 wrote:
| Nice, thanks!
| kgwgk wrote:
| Or look into TFA - it (person, distribution, unit)
| appears ten times :-)
| pdpi wrote:
| Agner Krarup Erlang, Danish mathematician and originator of
| queueing theory. The language is named after him.
| pgt wrote:
| Ahh, thanks! I had always assumed it was named after the
| Er- in Ericsson :).
| cmrdporcupine wrote:
| I think it's a clever name pulling from both.
| rahulgoel wrote:
| Surprisingly applicable to modern problems, such as queuing
| within computer systems. I studied this for my industrial
| engineering degree and thought it was extremely elegant.
| belter wrote:
| An hotel where a mathematical congress on queuing theory was
| happening that weekend, tried to provide the best service, by
| opening extra check-in counters at registration time, with their
| most professional receptionists...Guess what happened when the
| mathematicians arrived?
| loehnsberg wrote:
| M/M/s queues have nice properties, but require that arrival and
| service times are exponentially distributed. Once you deviate
| from this assumption, closed-form solutions become difficult to
| obtain and numerical approximations are quite messy.
|
| I've therefore always wondered whether there is software that
| uses theoretical results from queueing theory to improve control
| or to optimize parameters of complex systems. Any references?
| kqr wrote:
| ...except! If the server is processor-sharing/timeslicing. The
| results derived for timeslicing servers are surprisingly
| general in service distribution, and can be stated in product
| form like the networks of simple M/M/c servers you know.
|
| (Arrivals still need to be Poisson, but that's a fairly nice
| requirement in that many real-life arrivals actually look
| Poisson.)
| wslh wrote:
| I learnt about queueing practice on an IBM Mainframe (MVS/CICS)
| mixing with theory at the university. From that point I was very
| disappointed with RabbitMQ and other technologies way back
| because these systems were overpromoted as message brokers but it
| didn't have the basic capabilities of a message broker
| (contention) [1]. My take away from this is: stay alert of
| overpromotion and have real implementations (yes IBM...) And
| theory in mind.
|
| [1] https://lists.rabbitmq.com/pipermail/rabbitmq-
| discuss/2010-M...
| laichzeit0 wrote:
| Which are considered "classic" text books for queueing theory?
| Mathematically rigorous, like Feller on Probability.
| tokenrove wrote:
| Check out Kleinrock's Queueing Systems.
| SmartestUnknown wrote:
| http://www.performancemodeling.org
|
| People who take the course by the author at CMU say very good
| things about the class and the professor.
| kqr wrote:
| I love this book but its focus is primarily on practical
| applications and not as much on mathematical foundations,
| which was the question, if I read it right.
| mirker wrote:
| The book comparable to the mathematical level of CLRS, in
| my opinion. Which is either an intro book or very dense
| depending on a person's math background.
| [deleted]
| eterm wrote:
| One classic is Kelly:
| http://www.statslab.cam.ac.uk/~frank/BOOKS/kelly_book.html
|
| But there are probably better books written since I was an
| undergrad.
| spapas82 wrote:
| This has a lot of very complex mathematics involving stochastic
| processes and probabilities but results in a bunch of rather
| simple equations that can help you solve problems like:
|
| "How many operators I need to have at the same time when my
| telephone center receives 10 calls per minute with an average
| duration of 30 seconds so that the wait time won't be over 5
| minutes."
|
| The fact that such problems can be solved but I still need to
| wait 2 hours on the phone angers me very much.
| Someone wrote:
| Q: How many operators I need to have at the same time when my
| telephone center receives 10 calls per minute with an average
| duration of 30 seconds so that the wait time won't be over 5
| minutes?
|
| A: X, and then the operators will be busy Y% of their time.
|
| Especially if Y is low, many callcenter operators will rethink
| what SLAs they want to give callers.
|
| Many call centers optimise for keeping their operators busy aka
| paying as few operators as possible (and some of them then show
| their personnel the queue length or average waiting time and
| expect them to more rapidly kick out callers when that gets too
| long)
|
| For most people, it's the same with doctor visits. There is no
| inherent need to have to wait at a dentist, for example, but if
| dentists plan to have their day filled with paid work, there
| has to be. They may even schedule their first patient (possibly
| even the second) at a time before they plan to start working.
|
| It's different for people whose time is worth (much) more than
| that of the dentist. They (effectively) pay their dentist to
| wait for them.
| omnicognate wrote:
| They're just experiencing very high call volumes, you see.
|
| Not understaffing, no no.
|
| _Exceptionally_ high call volumes _all the time_.
| roenxi wrote:
| Queueing theory is an interesting discipline because the benefits
| of being a queue-theory expert are extremely subtle. There are
| some pressures that make it hard to show off:
|
| - There aren't really any flashy results (the whole thing could
| be sold as restatements of "if the average processing rate is
| similar to the arrival rate, any variance in arrivals will lead
| to long queues".
|
| - As a corollary, most queues encountered in practice can also be
| dealt with using very simple techniques or making the queue
| negligible. Neither of which require the study of queue theory.
|
| - The quick recommendations are really boring (if you want the
| queue to get shorter, you need to process faster or add more
| servers).
|
| But studying queue theory handy nonetheless because it turns out
| that queues are, in practical systems, about as common as list
| data structures or associative maps in programming. They are
| everywhere. Every time a stream meets a buffer, in fact. Being
| able to see a situation and reducing a lot of the noise to
| (M/M/n, lambda = 0.2, mu = 0.4) can free up a lot of thinking
| horsepower for more interesting problems. Then there is no need
| to try to reason about queue lengths vs serving times vs variance
| vs how those change with the addition of servers. An expert
| understands that a lot of results flow from a few simple
| variables, and doesn't have to remember the details because they
| are just symptoms of a few key observations.
|
| So, in a sense, the reward for knowing a lot of queue theory is
| not having to think very much about queues.
| [deleted]
| photochemsyn wrote:
| I feel like this would go hand-in-hand with graph theory, as
| many problems are something like a graph with a queue at each
| node, with the goal being to manage traffic through the graph
| so that each queue is kept as short as possible.
| cagenut wrote:
| Thats what the "theory of constraints" is in
| organizational/systems management.
|
| Limit WIP!
| kqr wrote:
| Theory of constraints is different from local WIP limits,
| though. (The latter are more efficient.)
| kqr wrote:
| Something not as obvious is the relationship between service
| time, utilisation, and response time. Even rough estimations of
| that can be very helpful, but most people I speak to don't even
| know there _is_ a useful relationship -- some even think
| service time and response time are the same.
|
| Come to think of it, the obvious general principles of queueing
| theory have several consequences that aren't immediately
| intuitive to people:
|
| - A system where concurrency is limited (practically all
| systems) often bottlenecks on its slowest component, meaning
| almost any upgrade will do nothing to improve its performance.
|
| - The average time a task is stuck waiting is longer than the
| average waiting time, once there's significant variation
| (greater than Poisson) in arrivals.
|
| - Based on only local measurements in an auxiliary,
| asynchronous component you can determine global throughput for
| the whole system.
| gillh wrote:
| You should really check out the recent Aperture[1] project on
| GitHub that applies all these ideas in practice to protect
| services from cascading failures.
|
| 1. Aperture automatically detects queue buildup based on
| metrics such as latency. 2. Adjusts the concurrency on a
| service. 3. Weighted Fair Scheduling of workloads (i.e. APIs)
| based on their labels.
|
| [1] https://github.com/fluxninja/aperture
| kqr wrote:
| I'm confused the decision would be based on latency, which
| is somewhat lagging. Queue length would seem more
| efficient, since it's leading.
| gillh wrote:
| The metric and the control circuit is
| configurable/programmable.
|
| [1] https://github.com/fluxninja/aperture/blob/main/bluep
| rints/b...
| roenxi wrote:
| If we're intellectually honest, how many hours of studying
| Markov chains does any one insight there really justify? And
| what are the odds that any one insight is useful even while
| dealing with an honest-to-goodness queue? We're not exactly
| talking e^{i\pi} levels of "wow!" which almost justify
| teaching complex numbers just to hit people with the one
| equation.
|
| The power is in the sheer number of semi-trivial observations
| that a queue theorist can start making after seeing only a
| small part of the system. And that is impressive - but mostly
| because you don't need to consider all those individual
| things as variables once the basic theory is understood. So
| the theorist can start ignoring all those variables really
| quickly and move on to dealing with the problem at hand.
| gnull wrote:
| Another fun fact: if instead of considering a distribution on
| the inputs, you consider worst case, then Queueing Theory
| becomes Online Algorithms. The techniques there seem very
| different from Queueing Theory, but I also heard some Computer
| Scientists calling Online Algorithms boring because the
| techniques used there are very similar and results aren't too
| suprizing (I can't say I share this sentiment).
| Der_Einzige wrote:
| If by "online algorithm" you mean incremental learning, the
| problem is that they still don't work well due to
| catastrophic forgetting...
| q-big wrote:
| > If by "online algorithm" you mean incremental learning,
| the problem is that they still don't work well due to
| catastrophic forgetting...
|
| I rather think that with "online algorithm", gnull means
| exactly this classic computer science topic:
|
| > https://en.wikipedia.org/wiki/Online_algorithm
| dunham wrote:
| Back when I was in college, an online algorithm was one
| where you had to make scheduling decisions as the jobs came
| in. There would be an optimal schedule (say differing size
| jobs coming in with n cpus) if you knew the future, and you
| prove things like "this algorithm can hit that optimal time
| with 1.x as many CPUs" or "this algorithm is within 1.x of
| optimal".
|
| This also applies to stuff like swapping / expiring cache -
| if you knew all of the future disk / memory accesses you
| could hit optimal, otherwise you need some heuristics.
|
| It's been a couple of decades, but I think some the proofs
| involved playing the part of an omniscient adversary.
| User23 wrote:
| I've found Little's law to be a pretty deep observation.
| kqr wrote:
| It can also be applied in creative ways! In a company's
| annual report they state revenue for the year as well as a
| snapshot of accounts receivable. Divide one by the other and
| you get a snapshot of how long time it takes the company to
| collect on its debts!
___________________________________________________________________
(page generated 2022-10-15 23:01 UTC)