2024-12-20 08:00:00
ALAN M. TURING 23 June 1912 – 7 June 1954
In 1928, David Hilbert, one of the most influential mathematicians of his time, asked whether it is possible to create an algorithm that could determine the correctness of a mathematical statement. This was called the "decision problem," or "Entscheidungsproblem" in Hilbert's native German. In 1936 both Alan Turing and Alonzo Church independently reached the conclusion, using different methods, that the answer is "no."
The way Turing did it was to imagine a "universal machine", a machine that could compute anything that could be computed. This idea, the "Turing machine" as Alonzo Church christened it in 1937, laid the foundations for the device you are using to read this post. If we look hard enough we can see Turing's legacy in today's CPUs.
By the end of this post, you will know:
You might expect a universal machine, capable of computing anything that can be computed, to be a complex device. Nothing could be further from the truth. The machine has just 4 parts, and the language used to program it has just 5 instructions.
The parts are: a !tape, a !head, a !program, and a !state. When you're ready, go ahead and press !play.
What you're seeing here is a program that executes P(0) to print 0 to the tape, moves the head right with the R instruction, then !jumps back to the start. It will go on printing 0s forever.
At any point, feel free to !pause, step the machine !forwards or !backwards one instruction at a time, or !restart the program from the beginning. There is also a speed selector on the far right of the controls if you want to speed up the machine.
Notice that !state and !value never change. Every time the machine performs a !jump, the current state and value are used to pick the correct next row of instructions to execute. This program only has a single state, start, and every time it jumps, the symbol under the !head is !blank.
Let's take a look at a program with multiple states.
This program prints alternating 0s and 1s to the tape. It has 2 states, zero and one, to illustrate what happens when you !jump to a different state.
You can also achieve this same result by using a single !state and alternating the !value. Here's an example of that:
The !value column always stays up to date with what the current symbol is under the !head, then when we !jump that value is used to know which row of instructions to execute. Combining state and value gives us a surprising amount of control over what our !program does.
We've so far seen 3 instructions:
There are 2 more:
This program prints the word "Alan" from right to left then halts. If you can't see the full word, you can drag the !tape left and right. If the machine has halted, you can use !restart to start it again from the beginning.
All of it! You're probably not going to get Crysis running at 60fps on a simulated Turing machine, but all of the calculations required to render each frame can be done with just these 5 instructions. Everything you have ever seen a computer do can be done with a Turing machine. We'll see a glimpse of how that can work in practice a little later.
The last example I want to show you before we move on is the very first program Alan Turing showed the world. It's the first program featured in his 1936 paper: "On Computable Numbers, with an application to the Entsheidungsproblem."
Turing liked to leave spaces between symbols, going as far as to even define them as "F-squares" and "E-squares". F for figure, and E for erasable. His algorithms would often make use of E-squares to help the machine remember the location of specific !tape squares.
Something is said to be "computable" if there exists an algorithm that can get from the given input to the expected output. For example, adding together 2 integers is computable. Here I'm giving the machine a !tape that starts out with the values 2 and 6 in binary separated by a !blank.
b2 | 0 | R -> b2
b2 | 1 | R -> b2
b2 | | L -> dec
dec | 0 | P(1) L -> dec
dec | 1 | P(0) L -> b3
dec | | H
b3 | 0 | L -> b3
b3 | 1 | L -> b3
b3 | | L -> inc
inc | 0 | P(1) R -> b1
inc | 1 | P(0) L -> inc
inc | | P(1) R -> b1
This program adds the two numbers together, arriving at the answer 8. It does this by decrementing from the right number and incrementing the left number until the right number is 0. Here's the purpose of each state:
That we can write this program at all is proof that addition is computable, but it also implies that all integers are computable. If we can add any 2 integers, we can compute any other integer. 1 is 0+1, 2 is 1+1, 3 is 2+1, and so on.
It's tricky to write the equivalent of if (rightNum === 0) break; in a Turing
machine, so this program does it as part of the decrementing process. If, while
decrementing, it gets all the way to a !blank square, it interprets that to mean
the number has hit 0 and halts.
You may have wondered why I'm choosing to work with binary numbers rather than decimal. It's not just because that's how modern computers work. I'm going to show you 2 examples, and from those examples you'll be able to see why modern computers choose to work in binary.
The first example is a program that increments a binary number in an endless loop.
The second example is a program that increments a decimal number in an endless loop.
These two programs are doing the same thing, but the program for manipulating decimal numbers is much longer. We've even introduced some new syntax, the * symbol, to handle a !value under the !head that does not match any of the other values for that !state. It's for this reason when programming Turing machines we prefer binary numbers: the programs end up being shorter and easier to reason about.
This benefit also translates to the physical world. Components that switch between 2 states are cheaper, smaller, and more reliable than components that switch between 10. It was more practical to build computers that worked in binary than ones that work in decimal, though attempts to build decimal computers were made.
To approach this question we need to explain the "Halting problem." It goes like this:
Given a program and some input, is it possible to write a second program that will tell you with certainty whether the first program will halt or run forever?
The answer is no, and this is what Turing essentially proved. The proof is complicated and I'm not ashamed to admit I don't understand it, but there is an example I can give you that can be intuitively understood to be "undecidable."
Imagine you write a program that takes as its input the program being used to decide whether it will halt or not. What it then does is run the decider program on itself, and then do the opposite of what the decider program says.
function undecidable(willHalt) {
if (willHalt(undecidable)) {
while (true);
} else {
return true;
}
}
This program intentionally enters an infinite loop if it is told it will halt, and halts if it is told it will run forever. It seems like a silly example, the kind of answer a cheeky high school student might try to get away with, but it is a legitimate counterexample to the idea that the halting problem can be solved.
If you were to imagine encoding the program and input into something that could be represented on the !tape, there would be no !program that could determine whether the program would halt or not. Imagining this encoding becomes quite natural when you realise that modern programs are encoded as binary data to be saved to disk.
If you've been involved in the world of programming for more than a few years, there's a good chance you've come across the term "Turing complete." Most likely in the context of things that really ought not to be Turing complete, like C++ templates, TypeScript's type system or Microsoft Excel.
But what does it mean?
Like the Halting problem, the proof is complicated but there's a straightforward test you can apply to something to judge it Turing complete:
A system is Turing complete if it can be used to simulate a Turing machine.
I've written this post, with the Turing machine simulations, in JavaScript. Therefore JavaScript is Turing complete. The C++ template example given above simulates a Turing machine in C++'s template system. The TypeScript example takes the route of writing an interpreter for a different Turing complete language.
You're right, and everyone tends to cheat a bit with the definition. When someone says something is Turing complete, what they mean is it would be Turing complete if it had an infinite amount of memory. The infinite tape limitation means no Turing machine could ever exist in our physical reality, so that requirement tends to get waived.
If you read around the topic of Turing machines outside of this post, you might see it said that modern computers are effectively Turing machines. You would be forgiven for finding it difficult to imagine how you go from adding 2 integers in binary on a !tape to running a web browser, but the line is there.
A key difference between our Turing machine and the device you're reading this on is that your device's CPU has "registers." These are small pieces of memory that live directly on the CPU and are used to store values temporarily while they're being operated on. Values are being constantly loaded from memory into registers and saved back again. You can think of registers as variables for your CPU, but they can only store fixed-size numbers.
We can create registers in our Turing machine. We can do this by creating a "format" for our tape.
Here we define 3 registers: A, B, and C. Each register contains a 3 bits and can store numbers between 0 and 7. Then at the far left we have an H, which stands for "home", which will help us navigate.
To increment register C, we can write a program like this:
We're making a lot more liberal use of the * symbol here to help us navigate to specific parts of the !tape without having to enumerate all possible values that could be under the !head on the way there.
This program is effectively equivalent to the following x86 assembly code, if
x86 had a register named c:
mov c, 0 ; Load 0 into c
inc c ; Increment c by 1
If we wanted to add values in A and B, storing the result in C, we need to do more work. Here's the assembly code we're trying to replicate:
mov a, 2 ; Load 2 into a
mov b, 3 ; Load 3 into b
add c, a ; Add a to c
add c, b ; Add b to c
Before you scroll down I will warn you that the program is long and complex. It is the last program we will see in this post, and I don't expect you to understand it in full to continue to the end. Its main purpose is to show you that we can implement operations seen in modern assembly code on a Turing machine.
start | * | L -> start
start | H | R -> go_a
go_a | * | R -> go_a
go_a | A | R R R -> dec_a
dec_a | 0 | P(1) L -> cry_a
dec_a | 1 | P(0) -> go_c1
cry_a | 0 | P(1) L -> cry_a
cry_a | 1 | P(0) -> go_c1
cry_a | * | R P(0) R P(0) R P(0) -> goto_b
go_c1 | * | R -> go_c1
go_c1 | C | R R R -> inc_c1
inc_c1 | 0 | P(1) -> h2a
inc_c1 | 1 | P(0) L -> cry_ca
cry_ca | 0 | P(1) -> h2a
cry_ca | 1 | P(0) L -> cry_ca
cry_ca | * | R -> h2a
h2a | * | L -> h2a
h2a | H | R -> go_a
goto_b | * | R -> goto_b
goto_b | B | R R R -> dec_b
dec_b | 0 | P(1) L -> dec_bc
dec_b | 1 | P(0) -> go_c2
dec_bc | 0 | P(1) L -> dec_bc
dec_bc | 1 | P(0) -> go_c2
dec_bc | * | R P(0) R P(0) R P(0) -> end
go_c2 | * | R -> go_c2
go_c2 | C | R R R -> inc_c2
inc_c2 | 0 | P(1) -> go_hb
inc_c2 | 1 | P(0) L -> cry_cb
cry_cb | 0 | P(1) -> go_hb
cry_cb | 1 | P(0) L -> cry_cb
cry_cb | * | R -> go_hb
go_hb | * | L -> go_hb
go_hb | H | R -> goto_b
end | * | L -> end
end | H | H
This is painfully laborious, and it doesn't even precisely match the assembly code. It destroys the values in A and B as it adds them together, and it doesn't handle overflow. But it's a start, and I hope it gives you a glimpse of how this theoretical machine can be built up to operate like a modern CPU.
If you watch the program run to completion, something that might strike you is just how much work is required to do something as simple as adding 2 numbers. Turing machines were not designed to be practical, Turing never intended anyone to go out and build one of these machines in the hope it will be useful.
Modern machines have circuits within them that can add 2 numbers together by passing 2 electrical signals in and getting the sum as a single signal out. This happens in less than a nanosecond. Modern machines have memory where any byte can be accessed at any time, no tape manipulation required. This memory access takes a few dozen nanoseconds.
I've built a web-based development environment for writing programs that will run on the Turing machine visualisations you've seen throughout the post.
You can access the editor here.
I encourage you to play around with it. Set a simple goal, like adding together 2 numbers without going back to look at the way I did it in the post. It's a great way to get a feel for how the machine works.
To recap, we've covered:
And you now have access to an environment for writing and running your own Turing machine programs. If you use it to make something neat, please do reach out to me and show me! My email address is [email protected].
These posts are never a solo effort, and this one is no exception. Sincere thanks go to the following people:
2024-06-01 08:00:00
Back in Memory Allocation, I introduced Haskie.
Hello!
The idea behind Haskie was to create a character that could ask questions the reader might have, and to "soften" the posts to make them feel less intimidating. I got some feedback from people that Haskie was a bit too childish, and didn't feel like he belonged in posts about serious topics. This feedback was in the minority, though, and most people liked him. So I kept him and used him again in Hashing.
Having a proxy to the reader was useful. I could anticipate areas of confusion and clear them up without creating enormous walls of text. I don't like it when the entire screen is filled with text, I like to break it up with images and interactive elements. And now dogs.
Then in Bloom Filters, I found myself needing a character to represent the "adult in the room." If Haskie was my proxy to the reader, this new character would serve as a proxy to all of the material I learned from in the writing of the post. This is Sage.
Well met!
I liked the idea of having a cast of characters, each with their own personality and purpose. But I had a few problems.
Both Haskie and Sage, because I have no artistic ability, were generated by AI. Back when I made them I was making no money from this blog, and I had no idea if I was going to keep them around. I didn't want to invest money in an idea that could flop, so I didn't feel bad about using AI to try it out.
Since then, however, I have been paid twice to write posts for companies, and I know that I'm keeping the dogs. It wasn't ethical to continue piggybacking on AI.
While ethics were the primary motivation, there were some other smaller problems with the dogs:
So I worked with the wonderful Andy Carolan to create a new design for my dogs. A design that would be consistent, fit with my brand, and look good at any size.
The redesigned dogs are consistent, use simple colours and shapes, and use the SVG file format to look good at any size. Each variant clocks in at around 20kb, which is slightly larger than the small AI-generated images, but I'll be able to use them at any size.
Together the dogs represent a family unit: Sage as the dad, Haskie as the youngest child, and Doe as his older sister.
They also come in a variety of poses, so I can use them to represent different emotions or actions.
We were careful to make the dogs recognisable apart. They differ in colour, ear shape, tail shape, and collar tag. Sage and Doe have further distinguishing features: Sage with his glasses, and Doe with her bandana. Doe's bandana uses the same colours as the transgender flag, to show my support for the trans community and as a nod to her identity.
I'm so happy with the new dogs, and plan to use them in my posts going forward. I suspect I will, at some point, replace the dogs in my old posts as well. I don't plan to add any more characters, and I want to be careful to avoid overusing them. I don't want them to become a crutch, or to distract from the content of the posts.
I also haven't forgotten the many people that pointed out to me that you can't pet the dogs. I'm working on it.
2024-02-19 08:00:00
This page makes heavy use of JavaScript to visualise the concepts discussed. Viewing it without JavaScript will be a strange experience, as the text talks about the visualisations. I strongly recommend either enabling JavaScript, or not wasting your time.
Everyone has a set of tools they use to solve problems. Growing this set helps you to solve ever more difficult problems. In this post, I'm going to teach you about a tool you may not have heard of before. It's a niche tool that won't apply to many problems, but when it does you'll find it invaluable. It's called a "bloom filter."
Bloom filters are similar to the Set data structure. You can add items to
them, and check if an item is present. Here's what it might look like to use
a bloom filter in JavaScript, using a made-up BloomFilter class:
let bf = new BloomFilter();
bf.add("Ant");
bf.add("Rhino");
bf.contains("Ant"); // true
bf.contains("Rhino"); // true
While this looks almost identical to a Set, there are some key differences.
Bloom filters are what's called a probabilistic data structure. Where a
Set can give you a concrete "yes" or "no" answer when you call contains, a
bloom filter can't. Bloom filters can give definite "no"s, but they can't be
certain about "yes."
In the example above, when we ask bf if it contains "Ant" and "Rhino", the
true that it returns isn't a guarantee that they're present. We know that
they're present because we added them just a couple of lines before, but it
would be possible for this to happen:
let bf = new BloomFilter();
bf.add("Ant");
bf.add("Rhino");
bf.contains("Fox"); // true
We'll demonstrate why over the course of this post. For now, we'll say that
when bloom filters return true it doesn't mean "yes", it means "maybe". When
this happens and the item has never been added before, it's called a
false-positive.
The opposite, claiming "no" when the answer is "yes," is called a false-negative. A bloom filter will never give a false-negative, and this is what makes them useful.
It's not strictly lying, it's just not giving you a definite answer. Let's look at an example where we can use this property to our advantage.
Imagine you're building a web browser, and you want to protect users from malicious links. You could build and maintain a list of all known malicious links and check the list every time a user navigates the browser. If the link they're trying to visit is in the list, you warn the user that they might be about to visit a malicious website.
If we assume there are, say, 1,000,000 malicious links on the Internet, and each link is 20 characters long, then the list of malicious links would be 20MB in size. This isn't a huge amount of data, but it's not small either. If you have lots of users and want to keep this list up to date, the bandwidth could add up.
However, if you're happy to accept being wrong 0.0001% of the time (1 in a million), you could use a bloom filter which can store the same data in 3.59MB. That's an 82% reduction in size, and all it costs you is showing the user an incorrect warning 1 in every million links visited. If you wanted to take it even further, and you were happy to accept being wrong 0.1% of the time (1 in 1000), the bloom filter would only be 1.8MB.
This use-case isn't hypothetical, either. Google Chrome used a bloom filter for this exact purpose until 2012. If you were worried about showing a warning when it wasn't needed, you could always make an API that has the full list of malicious links in a database. When the bloom filter says "maybe," you would then make an API call to check the full list to be sure. No more spurious warnings, and the bloom filter would save you from having to call the API for every link visited.
At its core, a bloom filter is an array of
To add an item to the bloom filter, we're going to hash it with 3 different hash
functions, then use the 3 resulting values to set 3
For this post I'm choosing to use 3 of the
SHA family of hash
functions:
The
Go ahead and
You might occasionally notice that only 2, or even 1,
Exactly right. A bloom filter with every Set that always returns true for contains. It will claim to contain
everything you ask it about, even if that thing was never added.
The rate of false-positives in our bloom filter will grow as the percentage of
set
It grows slowly at first, but as we get closer to having all
x^3, where x is the percentage of set
3 is the number of hash functions used. To give an
example of why we calculate it with this formula, imagine we have a bloom filter
with half of its bits set, x = 0.5. If we assume that our hash function has
an equal chance of setting any of the bits, then the chance that all 3 hash
functions set a bit that is already set is 0.5 * 0.5 * 0.5, or x^3.
Let's have a look at the false-positive rate of bloom filters that use different numbers of hash functions.
The problem that using lots of hash functions introduces is that it makes the
bloom filter fill up faster. The more hash functions you use, the more
It's possible to calculate how full a bloom filter will be after inserting a
number of items, based on the number of hash functions used. The graph below
assumes a bloom filter with 1000
The more hash functions we use, the faster we set all of the bits. You'll notice that
the curve tails off as more items are added. This is because the more
In practice, 1000
The lines barely leave the bottom of the graph, meaning the bloom filter will be very empty and the false-positive rate will be low. All this cost us was 12.5kB of memory, which is still a very small amount by 2024 standards.
Picking the correct number of hash functions and
The bloom filter page on Wikipedia covers the mathematics involved, which I'm going to translate into JavaScript functions for us to use. I want to stress that you don't need to understand the maths to use a bloom filter or read this post. I'm including the link to it only for completeness.
The following JavaScript function, which might look a bit scary but bear with
me, takes the number of items you want to store (items) and the desired
false-positive rate (fpr, where 1% == 0.01), and returns how many
function bits(items, fpr) {
const n = -items * Math.log(fpr);
const d = Math.log(2) ** 2;
return Math.ceil(n / d);
}
We can see how this grows for a variety of fpr values in the graph below.
After we've used the JavaScript above to calculate how many
function hashFunctions(bits, items) {
return Math.ceil((bits / items) * Math.log(2));
}
Pause for a second here and have a think about how the number of hash functions might grow based on the size of the bloom filter and the number of items you expect to add. Do you think you'll use more hash functions, or fewer, as the bloom filter gets larger? What about as the number of items increases?
The more items you plan to add, the fewer hash functions you should use. Yet, a larger bloom filter means you can use more hash functions. More hash functions keep the false-positive rate lower for longer, but more items fills up the bloom filter faster. It's a complex balancing act, and I am thankful that mathematicians have done the hard work of figuring it out for us.
While we can stand on the shoulders of giants and pick the optimal number of
We've spent the whole post talking about adding things to a bloom filter, and the optimal parameters to use. We haven't spoken at all about removing items.
And that's because you can't!
In a bloom filter, we're using
Click the buttons of the bloom filter below to see this in action. First we will add "foo", then "baz", and then we will remove "baz". Hit "clear" if you want to start again.
The end result of this sequence is a bloom filter that doesn't contain "baz",
but doesn't contain "foo" either. Because both "foo" and "baz" set
Something else you might have noticed playing with the above example is that if
you add "foo" and then attempt to remove "baz" before having added it, nothing
happens. Even though
While you can't remove items from a standard bloom filter, there are variants that allow you to do so. One of these variants is called a "counting bloom filter," which uses an array of counters instead of bits to keep track of items.
Now when you go through the sequence, the end result is that the bloom filter still contains "foo." It solves the problem.
The trade-off, though, is that counters are bigger than
Counting bloom filters also introduce the possibility of false-negatives, which are impossible in standard bloom filters. Consider the following example.
Because "loved" and "response" both hash to the
let bf = new CountingBloomFilter();
bf.add("loved");
bf.add("your");
bf.remove("response");
bf.contains("loved"); // false
Even though we know for sure we've added "loved" in this snippet, the call to
contains will return false. This sort of false-negative can't happen in a
standard bloom filter, and it removes one of the key benefits of using a bloom
filter in the first place: the guarantee of no false-negatives.
Real-world users of bloom filters include Akamai, who
use them to avoid caching web pages that are accessed once and never again. They
do this by storing all page accesses in a bloom filter, and only writing them
into cache if the bloom filter says they've been seen before. This does result
in some pages being cached on the first access, but that's fine because it's
still an improvement. It would be impractical for them to store all page
accesses in a Set, so they accept the small false-positive rate in favour of
the significantly smaller bloom filter. Akamai released a
paper
about this that goes into the full details if you're interested.
Google's BigTable is a distributed key-value store, and uses bloom filters internally to know what keys are stored within. When a read request for a key comes in, a bloom filter in memory is first checked to see if the key is in the database. If not, BigTable can respond with "not found" without ever needing to read from disk. Sometimes the bloom filter will say a key might be in the database when it isn't, but this is fine because when that happens a disk access will confirm the key in fact isn't in the database.
Bloom filters, while niche, can be a huge optimisation in the right situation. They're a wonderful application of hash functions, and a great example of making a deliberate trade-off to achieve a specific goal.
Trade-offs, and combining simpler building blocks to create more complex, purpose-built data structures, are present everywhere in software engineering. Being able to spot where a data structure could net a big win can separate you from the pack, and take your career to the next level.
I hope you've enjoyed this post, and that you find a way to apply bloom filters to a problem you're working on.
Join the discussion on Hacker News or Lobste.rs!
Enormous thank you to my reviewers, without whom this post would be a shadow of what you read today. In no particular order:
rylon, Indy, Aaron, Sophie, Davis, ed, Michael Drury, Anton Zhiyanov, Christoph Berger, Andrew Kingston, Tom Hall.
2023-05-24 08:00:00
This page makes heavy use of JavaScript to visualise the concepts discussed. Viewing it without JavaScript will be a strange experience, as the text talks about the visualisations. I strongly recommend either enabling JavaScript, or not wasting your time.
As a programmer, you use hash functions every day. They're used in databases to optimise queries, they're used in data structures to make things faster, they're used in security to keep data safe. Almost every interaction you have with technology will involve hash functions in one way or another.
Hash functions are foundational, and they are everywhere.
But what is a hash function, and how do they work?
In this post, we're going to demystify hash functions. We're going to start by looking at a simple hash function, then we're going to learn how to test if a hash function is good or not, and then we're going to look at a real-world use of hash functions: the hash map.
This article has visualisations that can be clicked.
Hash functions are functions that take an input, usually a string, and produce a number. If you were to call a hash function multiple times with the same input, it will always return the same number, and that number returned will always be within a promised range. What that range is will depend on the hash function, some use 32-bit integers (so 0 to 4 billion), others go much larger.
If we were to write a dummy hash function in JavaScript, it might look like this:
function hash(input) {
return 0;
}
Even without knowing how hash functions are used, it's probably no surprise that this hash function is useless. Let's see how we can measure how good a hash function is, and after that we'll do a deep dive on how they're used within hash maps.
Because input can be any string, but the number returned is within some
promised range, it's possible that two different inputs can return the same
number. This is called a "collision," and good hash functions try to minimise
how many collisions they produce.
It's not possible to completely eliminate collisions, though. If we wrote a hash function that returned a number in the range 0 to 7, and we gave it 9 unique inputs, we're guaranteed at least 1 collision.
hash("to") == 3
hash("the") == 2
hash("café") == 0
hash("de") == 6
hash("versailles") == 4
hash("for") == 5
hash("coffee") == 0
hash("we") == 7
hash("had") == 1
Output values from a well-known hash function, modulo 8. No matter what 9 values we pass, there are only 8 unique numbers and so collisions are inevitable. The goal is to have as few as possible.
To visualise collisions, I'm going to use a grid. Each square of the grid is going to represent a number output by a hash function. Here's an example 8x2 grid. Click on the grid to increment the example hash output value and see how we map it to a grid square. See what happens when you get a number larger than the number of grid squares.
13 % 16 == 13
Every time we hash a value, we're going to make its corresponding square on the grid a bit darker. The idea is to create an easy way to see how well a hash function avoids collisions. What we're looking for is a nice, even distribution. We'll know that the hash function isn't good if we have clumps or patterns of dark squares.
You said that when a hash function outputs the same value for 2 different inputs, that's a collision. But if we have a hash function that outputs values in a big range, and we mapped those to a small grid, aren't we going to create lots of collisions on the grid that aren't actually collisions? On our 8x2 grid, 1 and 17 both map to the 2nd square.
This is a great observation. You're absolutely right, we're going to be creating "pseudo-collisions" on our grid. It's okay, though, because if the hash function is good we will still see an even distribution. Incrementing every square by 100 is just as good a distribution as incrementing every square by 1. If we have a bad hash function that collides a lot, that will still stand out. We'll see this shortly.
Let's take a larger grid and hash 1,000 randomly-generated strings. You can click on the grid to hash a new set of random inputs, and the grid will animate to show you each input being hashed and placed on the grid.
The values are nice and evenly distributed because we're using a good,
well-known hash function called murmur3. This hash
is widely used in the real-world because it has great distribution while also
being really, really fast.
What would our grid look like if we used a bad hash function?
function hash(input) {
let hash = 0;
for (let c of input) {
hash += c.charCodeAt(0);
}
return hash % 1000000;
}
This hash function loops through the string that we're given and sums the
numeric values of each character. It then makes sure that the value is between 0
and 1000000 by using the modulus operator (%). Let's call this hash function
stringSum.
Here it is on the grid. Reminder, this is 1,000 randomly generated strings that we're hashing.
This doesn't look all that different from murmur3.
What gives?
The problem is that the strings we're giving to be hashed are random. Let's see how each function performs when given input that is not random: the numbers from 1 to 1000 converted to strings.
Now the problem is more clear. When the input isn't random, the output of stringSum forms a pattern. Our murmur3 grid, however, looks the same as how it looked with
random values.
How about if we hash the top 1,000 most common English words:
It's more subtle, but we do see a pattern on the stringSum grid. As usual, murmur3
looks the same as it always does.
This is the power of a good hash function: no matter the input, the output is evenly distributed. Let's talk about one more way to visualise this and then talk about why it matters.
Another way hash functions get evaluated is on something called the "avalanche effect." This refers to how many bits in the output value change when just a single bit of the input changes. To say that a hash function has a good avalanche effect, a single bit flip in the input should result in an average of 50% the output bits flipping.
It's this property that helps hash functions avoid forming patterns in the grid. If small changes in the input result in small changes in the output, you get patterns. Patterns indicate poor distribution, and a higher rate of collisions.
Below, we are visualising the avalanche effect by showing two 8-bit binary
numbers. The top number is the input value, and the bottom number is the murmur3 output value. Click on it to flip a single bit
in the input. Bits that change in the output will be green, bits that stay the same will be red.
murmur3 does well, though you will notice that sometimes fewer than 50% of the bits flip and sometimes more. This is okay, provided that it is 50% on average.
Let's see how stringSum performs.
Well this is embarassing. The output is equal to the input, and so only a single bit flips each time. This does make sense, because stringSum just sums the numeric value of each character in the string. This example only hashes the equivalent of a single character, which means the output will always be the same as the input.
We've taken the time to understand some of the ways to determine if a hash function is good, but we've not spent any time talking about why it matters. Let's fix that by talking about hash maps.
To understand hash maps, we first must understand what a map is. A map is a data structure that allows you to store key-value pairs. Here's an example in JavaScript:
let map = new Map();
map.set("hello", "world");
console.log(map.get("hello"));
Here we take a key-value pair ("hello" → "world") and store it in the map.
Then we print out the value associated with the key "hello", which will be
"world".
A more fun real-world use-case would be to find anagrams. An anagram is when two different words contain the same letters, for example "antlers" and "rentals" or "article" and "recital." If you have a list of words and you want to find all of the anagrams, you can sort the letters in each word alphabetically and use that as a key in a map.
let words = [
"antlers",
"rentals",
"sternal",
"article",
"recital",
"flamboyant",
];
let map = new Map();
for (let word of words) {
let key = word.split("").sort().join("");
if (!map.has(key)) {
map.set(key, []);
}
map.get(key).push(word);
}
This code results in a map with the following structure:
{
"aelnrst": ["antlers", "rentals", "sternal"],
"aceilrt": ["article", "recital"],
"aabflmnoty": ["flamboyant"]
}
Hash maps are one of many map implementations, and there are many ways to implement hash maps. The simplest way, and the way we're going to demonstrate, is to use a list of lists. The inner lists are often referred to as "buckets" in the real-world, so that's what we'll call them here. A hash function is used on the key to determine which bucket to store the key-value pair in, then the key-value pair is added to that bucket.
Let's walk through a simple hash map implementation in JavaScript. We're going
to go through it bottom-up, so we'll see some utility methods before getting to
the set and get implementations.
class HashMap {
constructor() {
this.bs = [[], [], []];
}
}
We start off by creating a HashMap class with a constructor that sets up 3
buckets. We use 3 buckets and the short variable name bs so that this code
displays nicely on devices with smaller screens. In reality, you could have
however many buckets you want (and better variable names).
class HashMap {
// ...
bucket(key) {
let h = murmur3(key);
return this.bs[h % this.bs.length];
}
}
The bucket method uses murmur3 on the key
passed in to find a bucket to use. This is the only place in our hash map code
that a hash function is used.
class HashMap {
// ...
entry(bucket, key) {
for (let e of bucket) {
if (e.key === key) {
return e;
}
}
return null;
}
}
The entry method takes a bucket and a key and scans the bucket until it
finds an entry with the given key. If no entry is found, null is returned.
class HashMap {
// ...
set(key, value) {
let b = this.bucket(key);
let e = this.entry(b, key);
if (e) {
e.value = value;
return;
}
b.push({ key, value });
}
}
The set method is the first one we should recognise from our earlier
JavaScript Map examples. It takes a key-value pair and stores it in our hash
map. It does this by using the bucket and entry methods we created earlier.
If an entry is found, its value is overwritten. If no entry is found, the
key-value pair is added to the map. In JavaScript, { key, value } is
shorthand for { key: key, value: value }.
class HashMap {
// ...
get(key) {
let b = this.bucket(key);
let e = this.entry(b, key);
if (e) {
return e.value;
}
return null;
}
}
The get method is very similar to set. It uses bucket and entry to find
the entry related to the key passed in, just like set does. If an entry is
found, its value is returned. If one isn't found, null is returned.
That was quite a lot of code. What you should take away from it is that our hash map is a list of lists, and a hash function is used to know which of the lists to store and retrieve a given key from.
Here's a visual representation of this hash map in action. Click anywhere on the buckets to add a new key-value pair using our
set method. To keep the visualisation simple, if a bucket were to "overflow",
the buckets are all reset.
Because we're using murmur3 as our hash
function, you should see good distribution between the buckets. It's expected
you'll see some imbalance, but it should generally be quite even.
To get a value out of the hash map, we first hash the key to figure out which bucket the value will be in. Then we have to compare the key we're searching for against all of the keys in the bucket.
It's this search step that we minimise through hashing, and why murmur3 is optimised for speed. The faster the hash
function, the faster we find the right bucket to search, the faster our hash
map is overall.
This is also why reducing collisions is so crucial. If we did decide to use that dummy hash function from all the way at the start of this article, the one that returns 0 all the time, we'll put all of our key-value pairs into the first bucket. Finding anything could mean we have to check all of the values in the hash map. With a good hash function, with good distribution, we reduce the amount of searching we have to do to 1/N, where N is the number of buckets.
Let's see how stringSum does.
Interestingly, stringSum seems to distribute
values quite well. You notice a pattern, but the overall distribution looks
good.
Finally! A win for
stringSum. I knew it would be good for something.
Not so fast, Haskie. We need to talk about a serious problem. The distribution
looks okay on these sequential numbers, but we've seen that stringSum doesn't have a good avalanche effect. This doesn't end
well.
Let's look at 2 real-world data sets: IP addresses and English words. What I'm
going to do is take 100,000,000 random IP addresses and 466,550 English
words, hash all of them with both murmur3
and stringSum, and see how many collisions we get.
IP Addresses
murmur3
|
stringSum
|
|
|---|---|---|
| Collisions | 1,156,959 | 99,999,566 |
| 1.157% | 99.999% |
English words
murmur3
|
stringSum
|
|
|---|---|---|
| Collisions | 25 | 464,220 |
| 0.005% | 99.5% |
When we use hash maps for real, we aren't usually storing random values in them.
We can imagine counting the number of times we've seen an IP address in rate
limiting code for a server. Or code that counts the occurrences of words in
books throughout history to track their origin and popularity. stringSum sucks for these applications because of it's extremely
high collision rate.
Now it's murmur3's turn for some bad news.
It's not just collisions caused by similarity in the input we have to worry
about. Check this out.
What's happening here? Why do all of these jibberish strings hash to the same number?
I hashed 141 trillion random strings to find values that hash to the number
1228476406 when using murmur3. Hash functions
have to always return the same output for a specific input, so it's possible to
find collisions by brute force.
I'm sorry, 141 trillion? Like... 141 and then 12 zeroes?
Yes, and it only took me 25 minutes. Computers are fast.
Bad actors having easy access to collisions can be devastating if your software builds hash maps out of user input. Take HTTP headers, for example. An HTTP request looks like this:
GET / HTTP/1.1
Accept: */*
Accept-Encoding: gzip, deflate
Connection: keep-alive
Host: google.com
You don't have to understand all of the words, just that the first line is the
path being requested and all of the other lines are headers. Headers are Key: Value pairs, so HTTP servers tend to use maps to store them. Nothing stops us
from passing any headers we want, so we can be really mean and pass headers we
know will cause collisions. This can significantly slow down the server.
This isn't theoretical, either. If you search "HashDoS" you'll find a lot more examples of this. It was a really big deal in the mid-2000s.
There are a few ways to mitigate this specific to HTTP servers: ignoring
jibberish header keys and limiting the number of headers you store, for
example. But modern hash functions like murmur3
offer a more generalised solution: randomisation.
Earlier in this post we showed some examples of hash function implementations.
Those implementations took a single argument: input. Lots of modern hash
functions take a 2nd parameter: seed (sometimes called salt). In the case
of murmur3, this seed is a number.
So far, we've been using 0 as the seed. Let's see what happens with the collisions I've collected when we use a seed of 1.
Just like that, 0 to 1, the collisions are gone. This is the purpose of the seed: it randomises the output of the hash function in an unpredictable way. How it achieves this is beyond the scope of this article, all hash functions do this in their own way.
The hash function still returns the same output for the same input, it's just
that the input is a combination of input and seed. Things that collide with
one seed shouldn't collide when using another. Programming languages often
generate a random number to use as the seed when the process starts, so that
every time you run your program the seed is different. As a bad guy, not knowing
the seed, it is now impossible for me to reliably cause harm.
If you look closely in the above visualisation and the one before it, they're the same values being hashed but they produce different hash values. The implication of this is that if you hash a value with one seed, and want to be able to compare against it in the future, you need to make sure you use the same seed.
Having different values for different seeds doesn't affect the hash map use-case, because hash maps only live for the duration the program is running. Provided you use the same seed for the lifetime of the program, your hash maps will continue to work just fine. If you ever store hash values outside of your program, in a file for example, you need to be careful you know what seed has been used.
As is tradition, I've made a playground for you to write your own hash functions and see them visualised with the grids seen in this article. Click here to try it!
We've covered what a hash function is, some ways to measure how good it is, what happens when it's not good, and some of the ways they can be broken by bad actors.
The universe of hash functions is a large one, and we've really only scratched the surface in this post. We haven't spoken about cryptographic vs non-cryptographic hashing, we've touched on only 1 of the thousands of use-cases for hash functions, and we haven't talked about how exactly modern hash functions actually work.
Some further reading I recommend if you're really enthusiastic about this topic and want to learn more:
Feel free to join the discussion on Hacker News!
Thanks to everyone who read early drafts and provided invaluable feedback.
And everyone who helped me find murmur3 hash
collisions:
After the success of Load Balancing and Memory Allocation, I have decided to set up a Patreon page: https://patreon.com/samwho. For all of these articles going forward, I am going to post a Patreon-exclusive behind-the-scenes post talking about decisions, difficulties, and lessons learned from each post. It will give you a deep look in to how these articles evolve, and I'm really stoked about the one I've written for this one.
If you enjoy my writing, and want to support it going forward, I'd really appreciate you becoming a Patreon. ❤️
2023-04-13 08:00:00
One thing that all programs on your computer have in common is a need for memory. Programs need to be loaded from your hard drive into memory before they can be run. While running, the majority of what programs do is load values from memory, do some computation on them, and then store the result back in memory.
In this post I'm going to introduce you to the basics of memory allocation. Allocators exist because it's not enough to have memory available, you need to use it effectively. We will visually explore how simple allocators work. We'll see some of the problems that they try to solve, and some of the techniques used to solve them. At the end of this post, you should know everything you need to know to write your own allocator.
malloc and free
To understand the job of a memory allocator, it's essential to understand how
programs request and return memory. malloc and free are functions that were
first introduced in a recognisable form in UNIX v7 in 1979(!). Let's take a look
at a short C program demonstrating their use.
Woah, hold on. I've never written any C code before. Will I still be able to follow along?
If you have beginner-level familiarity with another language, e.g. JavaScript, Python, or C#, you should have no problem following along. You don't need to understand every word, as long as you get the overall idea. This is the only C code in the article, I promise.
#include <stdlib.h>
int main() {
void *ptr = malloc(4);
free(ptr);
return 0;
}
In the above program we ask for 4 bytes of memory by calling malloc(4), we
store the value returned in a variable called ptr, then we indicate that we're
done with the memory by calling free(ptr).
These two functions are how almost all programs manage the memory they use.
Even when you're not writing C, the code that is executing your Java, Python,
Ruby, JavaScript, and so on make use of malloc and free.
The smallest unit of memory that allocators work with is called a "byte." A byte can store any number between 0 and 255. You can think of memory as being a long sequence of bytes. We're going to represent this sequence as a grid of squares, with each square representing a byte of memory.
In the C code from before, malloc(4) allocates 4 bytes of memory. We're going
to represent memory that has been allocated as darker squares.
Then free(ptr) tells the allocator we're done with that memory. It is returned
back to the pool of available memory.
Here's what 4 malloc calls followed by 4 free calls looks like. You'll
notice there's now a slider. Dragging the slider to the right advances time
forward, and dragging it left rewinds. You can also click anywhere on the grid
and then use the arrow keys on your keyboard, or you can use the left and right
buttons. The ticks along the slider represent calls to malloc and free.
Wait a sec... What is
mallocactually returning as a value? What does it mean to "give" memory to a program?
What malloc returns is called a "pointer" or a "memory address." It's a number
that identifies a byte in memory. We typically write addresses in a form called
"hexadecimal." Hexadecimal numbers are written with a 0x prefix to distinguish
them from decimal numbers. Move the slider below to see a comparison between
decimal numbers and hexadecimal numbers.
0
==
0x0
Here's our familiar grid of memory. Each byte is annotated with its address in
hexadecimal form. For space reasons, I've omitted the 0x prefix.
The examples we use in this article pretend that your computer only has a very small amount of memory, but in real life you have billions of bytes to work with. Real addresses are much larger than what we're using here, but the idea is exactly the same. Memory addresses are numbers that refer to a specific byte in memory.
malloc
The "hello world" of malloc implementations would hand out blocks of memory by
keeping track of where the previous block ended and starting the next block
right after. Below we represent where the next block should start with a grey
square.
You'll notice no memory is freed. If we're only keeping track of where the
next block should start, and we don't know where previous blocks start or end,
free doesn't have enough information to do anything. So it doesn't. This is
called a "memory leak" because, once allocated, the memory can never be used
again.
Believe it or not, this isn't a completely useless implementation. For programs
that use a known amount of memory, this can be a very efficient strategy. It's
extremely fast and extremely simple. As a general-purpose memory allocator,
though, we can't get away with having no free implementation.
malloc
In order to free memory, we need to keep better track of memory. We can do
this by saving the address and size of all allocations, and the address and size
of blocks of free memory. We'll call these an "allocation list" and a "free
list" respectively.
We're representing free list entries as 2 grey squares linked together with a
line. You can imagine this entry being represented in code as address=0 and
size=32. When our program starts, all of memory is marked as free. When
malloc is called, we loop through our free list until we find a block large
enough to accommodate it. When we find one, we save the address and size of the
allocation in our allocation list, and shrink the free list entry accordingly.
Where do we save allocations and free list entries? Aren't we pretending our computer only has 32 bytes of memory?
You caught me. One of the benefits of being a memory allocator is that you're in charge of memory. You could store your allocation/free list in a reserved area that's just for you. Or you could store it inline, in a few bytes immediately preceding each allocation. For now, assume we have reserved some unseen memory for ourselves and we're using it to store our allocation and free lists.
So what about free? Because we've saved the address and size of the allocation
in our allocation list, we can search that list and move the allocation back in
to the free list. Without the size information, we wouldn't be able to do this.
Our free list now has 2 entries. This might look harmless, but actually represents a significant problem. Let's see that problem in action.
We allocated 8 blocks of memory, each 4 bytes in size. Then we freed them all,
resulting in 8 free list entries. The problem we have now is that if we tried
to do a malloc(8), there are no items in our free list that can hold 8 bytes
and the malloc(8) will fail.
To solve this, we need to do a bit more work. When we free memory, we should
make sure that if the block we return to the free list is next to any other
free blocks, we combine them together. This is called "coalescing."
Much better.
A perfectly coalesced free list doesn't solve all of our problems. The following example shows a longer sequence of allocations. Have a look at the state memory is in at the end.
We end this sequence with 6 of our 32 bytes free, but they're split into 2
blocks of 3 bytes. If we had to service a malloc(6), while we have enough free
memory in theory, we wouldn't be able to. This is called "fragmentation."
Couldn't we rearrange the memory to get a block of 6 contiguous bytes? Some sort of defragmentation process?
Sadly not. Remember earlier we talked about how the return value of malloc is
the address of a byte in memory? Moving allocations won't change the pointers we
have already returned from malloc. We would change the value those pointers
are pointed at, effectively breaking them. This is one of the downsides of the
malloc/free API.
If we can't move allocations after creating them, we need to be more careful about where we put them to begin with.
One way to combat fragmentation is, confusingly, to overallocate. If we always allocate a minimum of 4 bytes, even when the request is for 1 byte, watch what happens. This is the exact same sequence of allocations as above.
Now we can service a malloc(6). It's worth keeping in mind that this is just
one example. Programs will call malloc and free in very different patterns
depending on what they do, which makes it challenging to design an allocator
that always performs well.
After the first
malloc, the start of the free list seems to fall out of sync with allocated memory. Is that a bug in the visualisation?
No, that's a side-effect of overallocating. The visualisation shows "true"
memory use, whereas the free list is updated from the allocator's perspective.
So when the first malloc happens, 1 byte of memory is allocated but the free
list entry is moved forward 4 bytes. We trade some wasted space in return for
less fragmentation.
It's worth noting that this unused space that results from overallocation is another form of fragmentation. It's memory that cannot be used until the allocation that created it is freed. As a result, we wouldn't want to go too wild with overallocation. If our program only ever allocated 1 byte at a time, for example, we'd be wasting 75% of all memory.
Another way to combat fragmentation is to segment memory into a space for small allocations and a space for big ones. In this next visualisation we start with two free lists. The lighter grey one is for allocations 3 bytes or smaller, and the darker grey one is for allocations 4 bytes or larger. Again, this is the exact same sequence of allocations as before.
Nice! This also reduces fragmentation. If we're strictly only allowing
allocations of 3 bytes or less in the first segment, though, then we can't
service that malloc(6). The trade-off here is that reserving a segment of
memory for smaller allocations gives you less memory to work with for bigger
ones.
Hey, the first allocation in the dark grey free list is 3 bytes! You said this was for allocations 4 bytes and up. What gives?
Got me again. This implementation I've written will put small allocations in the dark grey space when the light grey space is full. It will overallocate when it does this, otherwise we'd end up with avoidable fragmentation in the dark grey space thanks to small allocations.
Allocators that split memory up based on the size of allocation are called "slab allocators." In practice they have many more size classes than the 2 in our example.
malloc puzzleWhat happens if you malloc(0)? Have a think about this before playing with
the slider below.
This is using our free list implementation that mandates a minimum size of 4 bytes for allocations. All memory gets allocated, but none is actually used. Do you think this is correct behaviour?
It turns out that what happens when you malloc(0) differs between
implementations. Some of them behave as above, allocating space they probably
didn't have to. Others will return what's called a "null pointer", a special
pointer that will crash your program if you try to read or write the memory it
points to. Others pick one specific location in memory and return that same
location for all calls to malloc(0), regardless how many times it is called.
Moral of the story? Don't malloc(0).
Remember earlier on when you asked about where allocation list and free list information gets stored, and I gave an unsatisfying answer about how it's stored in some other area of memory we've reserved for ourselves?
Yes...
This isn't the only way to do it. Lots of allocators store information right next to the blocks of memory they relate to. Have a look at this.
What we have here is memory with no allocations, but free list information
stored inline in that memory. Each block of memory, free or used, gets 3
additional bytes of bookkeeping information. If address is the address of the
first byte of the allocation, here's the layout of a block:
address + 0 is the size of the blockaddress + 1 is whether the block is free (1) or used (2)
address + 2 is where the usable memory startsaddress + 2 + size -- the size of the block againSo in this above example, the byte at 0x0 is storing the value 29. This means
it's a block containing 29 bytes of memory. The value 1 at 0x1 indicates that
the block is free memory.
We store the size twice? Isn't that wasteful?
It seems wasteful at first, but it is necessary if we want to do any form of coalescing. Let's take a look at an example.
Here we've allocated 4 bytes of memory. To do this, our malloc implementation
starts at the beginning of memory and checks to see if the block there is used.
It knows that at address + 1 it will find either a 1 or a 2. If it finds a
1, it can check the value at address for how big the block is. If it is big
enough, it can allocate into it. If it's not big enough, it knows it can add
the value it finds in address to address to get to the start of the next
block of memory.
This has resulted in the creation of a used block (notice the 2 stored in the 2nd byte), and it has pushed start of the free block forward by 7 bytes. Let's do the same again and allocate another 4 bytes.
Next, let's free our first malloc(4). The implementation of free is where
storing information inline starts to shine. In our previous allocators, we had
to search the allocation list to know the size of the block being freed. Now
we know we'll find it at address. What's better than that is that for this
free, we don't even need to know how big the allocation is. We can just set
address + 1 to 1!
How great is that? Simple, fast.
What if we wanted to free the 2nd block of used memory? We know that we want to coalesce to avoid fragmentation, but how do we do that? This is where the seemingly wasteful bookkeeping comes into play.
When we coalesce, we check to see the state of the blocks immediately before and
immediately after the block we're freeing. We know that we can get to the next
block by adding the value at address to address, but how do we get to the
previous block? We take the value at address - 1 and subtract that from
address. Without this duplicated size information at the end of the block, it
would be impossible to find the previous block and impossible to coalesce
properly.
Allocators that store bookkeeping information like this alongside allocations are called "boundary tag allocators."
What's stopping a program from modifying the bookkeeping information? Wouldn't that completely break memory?
Surprisingly, nothing truly prevents this. We rely heavily, as an industry, on
the correctness of code. You might have heard of "buffer overrun" or "use after
free" bugs before. These are when a program modifies memory past the end of an
allocated block, or accidentally uses a block of memory after freeing it.
These are indeed catastrophic. They can result in your program immediately
crashing, they can result in your program crashing in several minutes, hours, or
days time. They can even result in hackers using the bug to gain access to
systems they shouldn't have access to.
We're seeing a rise in popularity of "memory safe" languages, for example Rust. These languages invest a lot in making sure it's not possible to make these types of mistake in the first place. Exactly how they do that is outside of the scope of this article, but if this interests you I highly recommend giving Rust a try.
You might have also realised that calling free on a pointer that's in the
middle of a block of memory could also have disastrous consequences. Depending
on what values are in memory, the allocator could be tricked into thinking it's
freeing something but what it's really doing is modifying memory it shouldn't
be.
To get around this, some allocators inject "magic" values as part of the
bookkeeping information. They store, say, 0x55 at address + 2. This would
waste an extra byte of memory per allocation, but would allow them to know when
a mistake has been made. To reduce the impact of this, allocators often disable
this behaviour by default and allow you to enable it only when you're debugging.
If you're keen to take your new found knowledge and try your hand at writing
your own allocators, you can click here to go to my
allocator playground. You'll be able to write JavaScript code that implements
the malloc/free API and visualise how it works!
We've covered a lot in this post, and if it has left you yearning for more you
won't be disappointed. I've specifically avoided the topics of virtual memory,
brk vs mmap, the role of CPU caches, and the endless tricks real malloc
implementations pull out of their sleeves. There's no shortage of information
about memory allocators on the Internet, and if you've read this far you should
be well-placed to dive in to it.
Join the discussion on Hacker News!
Special thanks to the following people:
2023-04-10 08:00:00
Past a certain point, web applications outgrow a single server deployment. Companies either want to increase their availability, scalability, or both! To do this, they deploy their application across multiple servers with a load balancer in front to distribute incoming requests. Big companies may need thousands of servers running their web application to handle the load.
In this post we're going to focus on the ways that a single load balancer might distribute HTTP requests to a set of servers. We'll start from the bottom and work our way up to modern load balancing algorithms.
Let's start at the beginning: a single load balancer sending requests to a single server. Requests are being sent at a rate of 1 request per second (RPS), and each request reduces in size as the server processes it.
For a lot of websites, this setup works just fine. Modern servers are powerful and can handle a lot of requests. But what happens when they can't keep up?
Here we see that a rate of 3 RPS causes some requests to get dropped. If a request arrives at the server while another request is being processed, the server will drop it. This will result in an error being shown to the user and is something we want to avoid. We can add another server to our load balancer to fix this.
No more dropped requests! The way our load balancer is behaving here, sending a request to each server in turn, is called "round robin" load balancing. It's one of the simplest forms of load balancing, and works well when your servers are all equally powerful and your requests are all equally expensive.
In the real world, it's rare for servers to be equally powerful and requests to be equally expensive. Even if you use the exact same server hardware, performance may differ. Applications may have to service many different types of requests, and these will likely have different performance characteristics.
Let's see what happens when we vary request cost. In the following simulation, requests aren't equally expensive. You'll be able to see this by some requests taking longer to shrink than others.
While most requests get served successfully, we do drop some. One of the ways we can mitigate this is to have a "request queue."
Request queues help us deal with uncertainty, but it's a trade-off. We will drop fewer requests, but at the cost of some requests having a higher latency. If you watch the above simulation long enough, you might notice the requests subtly changing colour. The longer they go without being served, the more their colour will change. You'll also notice that thanks to the request cost variance, servers start to exhibit an imbalance. Queues will get backed up on servers that get unlucky and have to serve multiple expensive requests in a row. If a queue is full, we will drop the request.
Everything said above applies equally to servers that vary in power. In the next simulation we also vary the power of each server, which is represented visually with a darker shade of grey.
The servers are given a random power value, but odds are some are less powerful than others and quickly start to drop requests. At the same time, the more powerful servers sit idle most of the time. This scenario shows the key weakness of round robin: variance.
Despite its flaws, however, round robin is still the default HTTP load balancing method for nginx.
It's possible to tweak round robin to perform better with variance. There's an algorithm called "weighted round robin" which involves getting humans to tag each server with a weight that dictates how many requests to send to it.
In this simulation, we use each server's known power value as its weight, and we give more powerful servers more requests as we loop through them.
While this handles the variance of server power better than vanilla round robin, we still have request variance to contend with. In practice, getting humans to set the weight by hand falls apart quickly. Boiling server performance down to a single number is hard, and would require careful load testing with real workloads. This is rarely done, so another variant of weighted round robin calculates weights dynamically by using a proxy metric: latency.
It stands to reason that if one server serves requests 3 times faster than another server, it's probably 3 times faster and should receive 3 times more requests than the other server.
I've added text to each server this time that shows the average latency of the last 3 requests served. We then decide whether to send 1, 2, or 3 requests to each server based on the relative differences in the latencies. The result is very similar to the initial weighted round robin simulation, but there's no need to specify the weight of each server up front. This algorithm will also be able to adapt to changes in server performance over time. This is called "dynamic weighted round robin."
Let's see how it handles a complex situation, with high variance in both server power and request cost. The following simulation uses randomised values, so feel free to refresh the page a few times to see it adapt to new variants.
Dynamic weighted round robin seems to account well for variance in both server power and request cost. But what if I told you we could do even better, and with a simpler algorithm?
This is called "least connections" load balancing.
Because the load balancer sits between the server and the user, it can accurately keep track of how many outstanding requests each server has. Then when a new request comes in and it's time to determine where to send it, it knows which servers have the least work to do and prioritises those.
This algorithm performs extremely well regardless how much variance exists. It cuts through uncertainty by maintaining an accurate understanding of what each server is doing. It also has the benefit of being very simple to implement.
Let's see this in action in a similarly complex simulation, the same parameters we gave the dynamic weighted round robin algorithm above. Again, these parameters are randomised within given ranges, so refresh the page to see new variants.
While this algorithm is a great balance between simplicity and performance, it's not immune to dropping requests. However, what you'll notice is that the only time this algorithm drops requests is when there is literally no more queue space available. It will make sure all available resources are in use, and that makes it a great default choice for most workloads.
Up until now I've been avoiding a crucial part of the discussion: what we're optimising for. Implicitly, I've been considering dropped requests to be really bad and seeking to avoid them. This is a nice goal, but it's not the metric we most want to optimise for in an HTTP load balancer.
What we're often more concerned about is latency. This is measured in milliseconds from the moment a request is created to the moment it has been served. When we're discussing latency in this context, it is common to talk about different "percentiles." For example, the 50th percentile (also called the "median") is defined as the millisecond value for which 50% of requests are below, and 50% are above.
I ran 3 simulations with identical parameters for 60 seconds and took a variety of measurements every second. Each simulation varied only by the load balancing algorithm used. Let's compare the medians for each of the 3 simulations:
You might not have expected it, but round robin has the best median latency. If we weren't looking at any other data points, we'd miss the full story. Let's take a look at the 95th and 99th percentiles.
Note: there's no colour difference between the different percentiles for each load balancing algorithm. Higher percentiles will always be higher on the graph.
We see that round robin doesn't perform well in the higher percentiles. How can it be that round robin has a great median, but bad 95th and 99th percentiles?
In round robin, the state of each server isn't considered, so you'll get quite a lot of requests going to servers that are idle. This is how we get the low 50th percentile. On the flip side, we'll also happily send requests to servers that are overloaded, hence the bad 95th and 99th percentiles.
We can take a look at the full data in histogram form:
I chose the parameters for these simulations to avoid dropping any requests. This guarantees we compare the same number of data points for all 3 algorithms. Let's run the simulations again but with an increased RPS value, designed to push all of the algorithms past what they can handle. The following is a graph of cumulative requests dropped over time.
Least connections handles overload much better, but the cost of doing that is slightly higher 95th and 99th percentile latencies. Depending on your use-case, this might be a worthwhile trade-off.
If we really want to optimise for latency, we need an algorithm that takes latency into account. Wouldn't it be great if we could combine the dynamic weighted round robin algorithm with the least connections algorithm? The latency of weighted round robin and the resilience of least connections.
Turns out we're not the first people to have this thought. Below is a simulation using an algorithm called "peak exponentially weighted moving average" (or PEWMA). It's a long and complex name but hang in there, I'll break down how it works in a moment.
I've set specific parameters for this simulation that are guaranteed to exhibit an expected behaviour. If you watch closely, you'll notice that the algorithm just stops sending requests to the leftmost server after a while. It does this because it figures out that all of the other servers are faster, and there's no need to send requests to the slowest one. That will just result in requests with a higher latency.
So how does it do this? It combines techniques from dynamic weighted round robin with techniques from least connections, and sprinkles a little bit of its own magic on top.
For each server, the algorithm keeps track of the latency from the last N requests. Instead of using this to calculate an average, it sums the values but with an exponentially decreasing scale factor. This results in a value where the older a latency is, the less it contributes to the sum. Recent requests influence the calculation more than old ones.
That value is then taken and multiplied by the number of open connections to the server and the result is the value we use to choose which server to send the next request to. Lower is better.
So how does it compare? First let's take a look at the 50th, 95th, and 99th percentiles when compared against the least connections data from earlier.
We see a marked improvement across the board! It's far more pronounced at the higher percentiles, but consistently present for the median as well. Here we can see the same data in histogram form.
How about dropped requests?
It starts out performing better, but over time performs worse than least connections. This makes sense. PEWMA is opportunistic in that it tries to get the best latency, and this means it may sometimes leave a server less than fully loaded.
I want to add here that PEWMA has a lot of parameters that can be tweaked. The implementation I wrote for this post uses a configuration that seemed to work well for the situations I tested it in, but further tweaking could get you better results vs least connections. This is one of the downsides of PEWMA vs least connections: extra complexity.
I spent a long time on this post. It was difficult to balance realism against ease of understanding, but I feel good about where I landed. I'm hopeful that being able to see how these complex systems behave in practice, in ideal and less-than-ideal scenarios, helps you grow an intuitive understanding of when they would best apply to your workloads.
Obligatory disclaimer: You must always benchmark your own workloads over taking advice from the Internet as gospel. My simulations here ignore some real life constraints (server slow start, network latency), and are set up to display specific properties of each algorithm. They aren't realistic benchmarks to be taken at face value.
To round this out, I leave you with a version of the simulation that lets you tweak most of the parameters in real time. Have fun!
EDIT: Thanks to everyone who participated in the discussions on Hacker News, Twitter and Lobste.rs!
You all had a tonne of great questions and I tried to answer all of them. Some of the common themes were about missing things, either algorithms (like "power of 2 choices") or downsides of algorithms covered (like how "least connections" handles errors from servers).
I tried to strike a balance between post length and complexity of the simulations. I'm quite happy with where I landed, but like you I also wish I could have covered more. I'd love to see people taking inspiration from this and covering more topics in this space in a visual way. Please ping me if you do!
The other common theme was "how did you make this?" I used PixiJS and I'm really happy with how it turned out. It's my first time using this library and it was quite easy to get to grips with. If writing visual explanations like this are something you're interested in, I recommend it!
