Queueing Simulations

Waiting in lines is something we've all experienced. But how long will the wait for a table really be? How many checkouts should the grocery store have open? Queueing theory gives us the tools to be able to answer questions like these and more. It's also relevant to understanding software under heavy load. I've seen it come up recently in The Amazon Builder's Library Avoiding Insurmountable Queue Backlogs and Site Reliability Engineering's Addressing Cascading Failures chapter. 

Since you are reading this blog it is assumed that you are already familiar with queues and the idea of using them in software systems. To summarize, queues can improve availability and throughput at the expense of latency and resource consumption. Here we will see what the field of queueing theory can teach us about how and when to best use them. 

The Builder's Library article warns us of the bi-modal behavior of queue-based systems: the behavior can be very different based on whether there is a backlog or not. Recovery time after an outage can be dramatically increased and time can be wasted doing work that is no longer useful. We then get the first hints of how to manage this. Using more than one queue helps shape traffic. LIFO-ish behavior can be more desirable than FIFO. The SRE book discusses throttling via small queue sizes so requests are rejected when the incoming request rate is too high to be sustained. Traffic patterns, queue sizes, and the number of threads removing work from the queue are all intertwined. Can we better quantify these recommendations though?

I first learned of queueing theory in The Essential Guide to Queueing Theory e-book from VividCortex and wanted to revisit it in the context of the SRE reading. Right from the beginning we are warned that while queues are linear data structures, queueing systems behave non-linearly. Queueing theory is probabilistic. We won't understand the behavior exactly, but will know about wait times on average or a distribution of wait times.

The first thing they suggest we must understand is that queueing happens even when there is enough capacity to do the work. This is because work arrives to the queue in irregular sizes and at irregular intervals. Queueing gets worse at high utilization, when there is high variability, and when fewer workers are servicing the queues.

Any system can be decomposed into networks of queues and workers. These are the parameters and metrics commonly used to understand these systems:

• arrival rate to the queue (λ or A) - in a stable system this is the same as throughput
• average wait time or residence time in the queue (W or W_q)
• average post-queue service time (S)
• service rate (μ) - inverse of service time
• latency or residence time (R) - sum of wait time and service time
• worker utilization (ρ or U) - 0 to 1
• average number of requests waiting or in service concurrently (L or L_q)
• number of workers (M)

Little's Law states that concurrency is arrival rate times residence time: L = λR and L_{q =} λW_q

The Utilization Law states that utilization is throughput times service time: ρ = λS or ρ = λ/μ or with M workers ρ = λS/M

Kendall's Notation is a shorthand for describing queue systems. Normally we'll be working with M/M/m systems. The first M says events arrive randomly and independently (memoryless) meaning they are generated by a Poisson process. The second M says the service times are exponentially distributed. The last m is the number of workers or M from above. These are safe assumptions unless you know otherwise.

For a M/M/1 system R = S / (1 - ρ) which is a fast-growing curve (the non-linear mentioned above). Residence time is inversely proportional to idle capacity. By rearranging the equations above we can solve for other parameters as well. For systems beyond M/M/1 it gets more complicated. For M/M/m, for example, we need to bring in Erlang's C-formula.

To do that, and to see these laws in action, it's time to write some code. There appear to be several Python packages for simulating queueing systems. I will use Ciw for this simulation. We'll assume we have 1,000 requests per minute, several servers pulling work from a queue, and need enough capacity such that 2 servers could be offline without the system falling behind.

servers	utilization %	latency (sec)
3	83	.35
4	63	.18
5	50	.15

We can use this simulation to figure out what "levers to pull" to get the behavior we want. It could even become a Linear Programming optimization problem. Based on the arrival rate and service rate it's easy to see we need at least 3 servers, but not as easy to see how the latency would change going from 3 to 5 or what the minimum queue size is.

While not always intuitive, especially with multiple queues, there are ways to understand how queue-based systems will behave. If you are interested in the topic, I suggest reading the linked resources as they go into much more detail. If you have other examples of queueing theory in action, please share in the comments.

Java Updates Versions 9-19

The past few years I haven't written much Java code and when I did, it was Java 8. Many projects, it seems, have stuck with Java 8 which was released back in 2014. Per the roadmap, Java 8 is designated as LTS, but so are Java 11 and Java 17. In fact, Java 19 is available as of last month and many interesting features have been introduced in the past 8 years. This post is an overview of what's changed. The highlights, in my opinion, so we're up-to-date. I think it's enough to be interesting but not so much that it can't be picked up quickly if you have experience with older Java versions.

First, some name conventions. Java EE is now Jakarta EE. Definitely don't call it J2EE anymore. And since Java 11 Oracle JDK and OpenJDK are basically the same.

Tooling Updates

I won't go into too much detail here. If we are interested in using any of these they are explained and documented well elsewhere. For awareness:

• Java got a REPL called JShell for learning and prototyping interactively (9)
• Java Module System as a new package abstraction (9) - my impression is that this more for the JDK itself and some libraries while OSGi continues to be applicable for regular, modular apps
• Single-file programs can be executed directly and don't need the intermediate javac step (11)
• Multiple new garbage collection options for improved and more consistent performance (11)
• ZGC for low latency
• Epsilon GC no-op
• Linux container awareness for GC, thread pool sizes, etc. (11)
• Application class data sharing (CDS) for improved startup times and lower memory footprints (12) - this also seems to have implications for apps running in containers

API Updates

We want to start incorporating these into our code where applicable, so I created examples to help get used to some of these updates.

Private interface methods (9). Helps to encapsulate code in default methods and create more reusable code.

Variables can have implicit types, including in lambdas, to reduce the verbosity of code (10 and 11).

Switch expressions to simplify code and prepare for pattern matching in the future (12).

Text blocks as way to simplify code with multi-line strings (13).

Simple pattern matching (14). I was introduced to pattern matching when programming in Scala and this seems to continue a trend of Scala features making their way, in some form, to Java. It looks like more is coming in terms of pattern matching options.

Record keyword for immutable data classes (14). Getters, a public constructor, plus equals, hashCode, and toString methods are generated automatically. Lombok is still more flexible, but this is nice for simple cases.

Sealed classes for fine-grained inheritance control (15). Super-classes that are widely accessible but not widely extensible.

Paradigm Updates

For lack of a better name I'll call these paradigm updates as they relate more to programming models. 

Flow API as an implementation of the Reactive Streams Specification (9). This seems to be a way to get the specification interfaces into the JDK but not necessarily replace libraries with better implementations.

Vector API introduces vectorization to Java (16). It looks like it doesn't happen automatically and requires special code, so to be more useful I think it needs to be included in a common library like NumPy in Python.

Virtual threads and structured concurrency (19). The one-to-one kernel to user thread mapping is broken enabling easier asynchronous programming. Read/watch Project Loom: Revolution in Java Concurrency or Obscure Implementation Detail? The tl;dr is we'll still need a higher level of abstraction like reactive programming unless you want to relearn all the low-level concurrency structures.

Probabilistic Graphical Models

Deep learning and neural networks get a lot of (deserved) attention, but there is another class of ML models called Probabilistic Graphical Models (PGMs) that can also be used for inference and prediction. They have applications in fields such as medical diagnosis, image understanding, and speech recognition. Think decision making based on incomplete or insufficient knowledge.

More formally, PGMs use graphs to encode joint probability distributions as opposed to the more traditional ML approach of learning a function that directly maps input to a target variable. This post isn't a technical introduction though. Rather, it is more of an introduction-by-example and a summary of pgmpy's excellent notebooks.

Given a simple graph for flower type:

Our two approaches would look something like this:

Bayesian networks

In this section I'll use a more complex graph for student grades:

For problems with many features and/or high cardinality features, inference will be difficult because the size of the joint probability distribution increases exponentially. PGMs can compactly represent it by exploiting conditional independence. They provide us efficient methods for doing inference over these joint distributions.

In this graph we have cardinalities of 2 for each node except Letter which is 3. The joint distribution would require storing 48 values (2*2*2*2*3) while the PGM only requires 26 (see notebook 1 for details).

This is what's known as a Bayesian network, which is always represented as a directed acyclic graph. Each node is parameterized by a conditional probability distribution (CPD) like P(node|parents). For example, the Grade node has the CPD P(G|D,I). Bayesian networks are used when you want to represent causal relationships between random variables. Naive Bayes is a special case where all random variables are assumed to be independent of each other, each only directly affecting the target variable.

Given tabular data and a graph structure, CPDs can be estimated using Maximum Likelihood Estimation (MLE). It's similar to what was done with the Iris data in the first code block above. It's also fragile because it is so dependent on the amount and quality of the observed data (see notebook 10 for details). This explains why that code breaks with some random seeds. 

A better solution is Bayesian Parameter Estimation. There you start with CPDs based on your prior beliefs (or uniform priors) and update them based on the observed data.

One method of exact inference in PGMs is variable elimination. It efficiently avoids computing the entire joint probability distribution (see notebooks 2 and 5 for details). For larger graphs there are other, approximate algorithms because an exact solution would be intractable.

Making predictions is similar. Instead of getting a distribution we get the most probably state.

Markov networks

Markov networks are represented by undirected graphs. They represent non-causal relationships. They can, however, represent dependencies that a Bayesian model can't, like cycles and bi-directional dependencies. Factors describe connected variable affinity, or how much two nodes agree with each other. The joint probability distribution is the product of all factors.

A quick note because the names sound similar. Markov chains are not PGMs because the nodes are not random variables. They can be represented as as Bayesian networks and PGM algorithms would be available.

Sampling

Sampling algorithms approximate exact inference by generating a large number of samples that will converge to the original distribution. One of these is Hamiltonian Monte Carlo. It is a Markov Chain Monte Carlo (MCMC) that proposes future states in the Markov Chain using Hamilton dynamics from physics (see notebook 8 for details). Other MCMC algorithms you may encounter are Metropolis-Hastings and Gibb's Sampling. See Monte Carlo Approximation Methods: Which one should you choose and when? for a comparison of these methods.

Another interesting find that fits in at this point is the PyMC3 library and the Probabilistic Programming and Bayesian Methods for Hackers open source book. 

I also think this is a nice writeup on Bayesian Logistic Regression using Pyro, another probabilistic programming library, and MCMC.

Learning networks

Learning a Bayesian network can be done as an optimization problem by scoring networks on how well they fit a data set, and searching through the space of all possible models. For non-trivial graphs where an exhaustive search is not possible, hill climbing can be used (see notebook 11 for details).

Wrap-up

I've only scratched the surface here, but I think it's a more intuitive introduction to the topic than most of the material in this space. We could build up to more complex graphs and problems from here.

Hidden Markov Models Explained with a Real Life Example and Python code is a nice extension, for example.

And to bring things full circle on where PGMs fit in to the ML landscape, here is an opinion from well-known ML researcher Ian Goodfellow:

The two aren’t mutually exclusive. Most applications of neural nets can be considered graphical models that use neural nets to provide some of the conditional probability distributions. You could argue that the graphical model perspective is growing less useful because so many recent neural models have such simple graph structure … These graphs are not very structured compared to neural models that were popular a few years ago like … But there are some recent models that make a little bit of use of graph structure, like VAEs with auxiliary variables.

Plus a tweet from the Standford NLP group:

There is increasing convergence between this decade’s neural models and last decade’s probabilistic graphical models… https://t.co/MKlIP4Sayx

— Stanford NLP Group (@stanfordnlp) May 15, 2018

Thus is would seem that knowing these concepts will continue to be useful even if we don't directly use PGMs or focus solely on PGMs.