Hacker News Reader

> I enjoy knowing a little bit of queue theory because it is a subject where not only can you gain an advantage in many areas but few people will be able to figure out why

Yes! I’ve been building web applications for 15 years, but queuing systems were rarely discussed with any importance. I only picked up on it in the past few years, but since then, I consider it one of the most commercially-beneficial ways to scale and grow most kinds of software.

When it comes to scaling, it seems like 90% of the advice just focusses on RDMS, optimising indexes, etc. Database theory is vitally important to understand, but I now consider queue theory essential knowledge for modern application developers too.

Case in point: over the years I’ve reviewed thousands of PHP projects, articles, blogs, and other resources in the ecosystem. There are more guides to scaling Nginx or optimising MariaDB than I could ever need.

But I simply never see any discussion or usage of the low-level queue features offered by the language, like Deques: https://www.php.net/manual/en/class.ds-deque.php

I appreciate these have niche use cases, but a background queue handler builds on this kind of understanding, and is general purpose.

Knowledge of queue theory directly helped me scale my own projects, in ways I couldn’t have imagined otherwise.

> But I simply never see any discussion or usage of the low-level queue features offered by the language, like Deques

I respectfully disagree:

1. Deques is not a "feature[s] offered by the language". Its part of an external extension (meaning it's a C compiled plug-in to the main engine). It's development is outside of the language scope, see https://pecl.php.net/package/ds

2. Deques is barely a "low-level queue feature". It's just a data structure that can be performant for some implementations of queues. Native arrays provide slower but similar features.

3. It's sane that this (Deques) implementation detail (the in-memory data structure) is less discussed than more central and generic subjects, like scaling MariaDB.

If I consider the first two problems mentioned in the article (systems for issues and for kanban), I think Deques is unsuitable to them, because it's meant to replace arrays for in-memory works. The problems require a persistent storage, and the optimization of a PHP storage for the queue is probably irrelevant.

You're totally right and I agree too :) I forgot Deques (and DS) were via PECL.

It's a poor example to give in relation to the article's real-world cases. Nonetheless, it is relevant to queue theory, and knowledge of how, why, and when these data structures can be more optimal than simple arrays has helped me more broadly in the past.

A much more real-world example would be Laravel Horizon, which uses Redis queues to build scalable distributed systems very easily. The last time I set it up I think it took me 5 minutes at most... https://laravel.com/docs/10.x/horizon

> But I simply never see any discussion or usage of the low-level queue features offered by the language...

Assuming we're talking about something that serves requests over the network, it rarely makes sense to define or use queues within the program itself. The network stack already contains many layers of queues which will almost always manage load concerns (e.g. throttling, backpressure, etc.) more effectively than your application can do itself. In general you want your app to accept and process requests as fast as it can, and leave queueing concerns to other authorities.

Ugh...

A few companies back, there was a problem where we were provisioning phone numbers that appeared directly in ads and too few numbers caused problems, but of course it costs money to do the provisioning.

I don't know much about queue theory, but I immediately recognized that this was a queue theory problem, and recommended we figure out the answer as such. I got blank stares and "how about we just provision 10 numbers more than we think we need" or something like that.

Sometimes a quick answer like that is better than wasting a lot of engineering time over optimising, but this was actually fairly critical to their business and they were spending significant amounts on the ads and phone numbers and needed both to work well.

https://en.wikipedia.org/wiki/M/M/1_queue to link it

Indeed! A great deal of mathematics has this property when it comes to applying it to the real world. Queuing theory might stand out as an especially high ROI example, given how simple its starting assumptions are and how easy it is to roughly model a lot of situations off of it.

Can almost use it as a checklist while balancing service level against the cost of resources needed to achieve the service.

A great tool in the toolbox to have while building software!

Hm, I wonder what other examples of high-ROI math are?

Set theory might seem almost mundane in many cases, but it's really powerful to express certain solutions in a very concise way. I've refactored code into much simpler code by just thinking about it in terms of set manipulation, vastly reducing the number of classes/tables necessary. Operations became self-explanatory (it's "just a set").

It also gives you a good foothold to realize whether the solution works or not into the future, a bit of a barebones formalism. You get to play with it in math terms before writing any code. This particular refactoring became the only thing in the codebase that didn't need to change as new requirements came along.

Good pick, I'm a big fan of using set() in Python. The fact that they're unordered and do not allow duplicates communicates a lot about the nature of the problem you're working with.

Simple random sampling. You can do anything with meaningful precision -- often at a fraction of the cost.

The key insight is you rarely need an exact number, just something in the right ballpark. And sometimes that ballpark is surprisingly big.

(More advanced sampling methods are basically just variance-reducing techniques which give you better precision at cost or lower cost for the same precision, but the big leap in ROI is learning to sample in the first place.)

Could you please give a concrete example on this, sounds interesting?

Say you're assigned yea many tickets to complete each sprint. You have a tough time completing them all in one sprint and expect your boss is going to be unhappy about work-not-done.

If you've got a good grasp on queue theory, so you prepare for the talk by assuming an M/M/1 and working out the arrival rate of tickets vs. the rate you complete work at. You work out probability (uncompleted items >= tickets not done).

Now you're in a great position to negotiate workload because you have all the figures to work out what just happened - is the problem that you completed tickets too slowly, that there were too many tickets, that even basic variance in task completion rates would result in this happening 5% of the time, et cetera. You have on hand immediately how common this must be so you are in a position to guess at how you compare to colleagues. You can make relatively low-ego determinations about whether this is a sprint-specific mistake you made or if it was all but certain to happen due to basic task variance.

There are a lot of conclusions to be drawn there just by a cursory review of past performance. There isn't anything magic to it, but you're going to be able to spend the conversation worrying about the social aspects of how to manage said boss and don't have to waste valuable brain cyles working out what just happened yourself. You only need to remember 2 numbers and a few napkin-level formula. Works even better if you happen to be the boss because now you can make some quick guesses about whether there is a problem here or just statistical variance.

This relies on the assumption that work time per ticket follows a distribution described by the second M. If you get tickets that require much more work, i.e. tickets that are outliers and not from the distribution described by the M, then your estimates will end up wrong, too.

Eh, not necessarily. Queuing is a function of throughput, which by definition takes processing time into account.

  Queue length = arrival rate * processing time

Transitive properties allow you to solve for one variable, given you have the other two. This is known as Little’s Law[0].

With this, you can now deduce/estimate how long a ticket will be in the backlog, how fast you need to complete a task, how long until everything is finished.

[0]: https://en.m.wikipedia.org/wiki/Little%27s_law

> This is known as Little’s Law

Little's law lets you calculate the third variable easily, given that you know the other two. You can calculate from existing data.

As such, it doesn't help you calculate forecasts. Or you can, if you make assumptions on the distributions. But some outliers can then turn the reality very different from what your forecast was.

> how fast you need to complete a task

You can calculate how fast you need to complete a task. But if an outlier task comes your way, it doesn't help you to actually complete that particular task in time.

If you're able to multiplex a little bit (which most humans naturally do) the shape of the service time distribution does not matter as much as it may seem. (In the limit, perfect timesharing across tasks makes even the fattest of tails look M/M/k.)

The more severe constraint is actually the first M. Fortunately, that holds true in practise very often.

Ah nice! In fact a neat little trick most people don't realize is system designs interviews are effectively queue designs!