On my off hours, I’ve been working through volumes 4A and 4B. They are really wonderful, I highly recommend them. They’re not practical for the vast majority of programmers, but the way he designs and writes about algorithms is remarkable, truly unique. The Dancing Links implementation in 4B in particular (updated significantly from his famous paper) is like a work of art, it’s such an intricate and gorgeous data structure, and blazing fast as well. Man still got it, in his 80s.
Back in 2010 when we were building Amazon Route 53, we had a really big problem to solve. DDOS attacks. DNS is critical, and it uses UDP, which is a protocol that allows attackers to spoof their source IP address. We knew that DNS services are a common target for attacks from botnets; and our research at the time showed that our established competitors used large and expensive "packet scrubbers" to handle this.
We budgeted out what we think it would cost to handle our scale and the price tag came to tens of millions of dollars. You might think that would be no problem for a big company like Amazon, but our total infrastructure budget for Route 53 was something like tens of thousands of dollars. At the edge, we were re-using CloudFront servers that had failed hard drives for our name servers; since we wouldn't need much storage, and our API servers were pretty modest. We had a team of about ~6 people. That's what "scrappy" looks like at AWS; spend nothing, minimize downside risk, get things done quickly. There was no way I was going to ask for tens of millions of dollars for packet scrubbers. Besides, they would take too long to arrive, and would make us too reliant on a vendor.
Early on we had decided to run Route 53 name servers on its own dedicated IP range to give some measure of isolation. We could use dedicated network links to make sure that Amazon's other infrastructure wouldn't be impacted. But that wouldn't help Route 53's customers from sharing fate with each other. We didn't have a real plan beyond "When it happens, get really good filtering using our existing network and system tools".
Early that summer, I was reading one of Knuth's recent fascicles for 4A and was swimming in combinatorial algorithms. One night it just "clicked" that by creating many virtual name servers, we could easily assign every customer to a unique combination of four of those virtual name servers. We could even control the amount of overlap; some quick math showed that we about two thousand name servers, we could guarantee that no two customer would share more than two name servers. That number is important because our experiments showed that domains resolve just fine even when two name servers are unreachable, but beyond that it starts to be a problem.
The recursive search algorithm to assign the IPs was inspired directly by the algorithms in 4A; it gives customer domains two more independent dimensions of isolation. They also get 4 name servers from 4 independent "stripes", which correspond to the different TLDs we use for the name server names (co.uk, com, net, org). This guarantees that if one of those TLDs has an issue (like a DNSSEC mistake), only one of the name servers is impacted. They also come from 4 independent "braids", which can be used to ensure that no two name servers share certain network paths or physical hardware. I just wouldn't have known how to do any of this without reading 4A. And I even have a background in combinatorials; from statistics and cryptography.
I've never been more excited by a solution; this approach gave us provable network IP level isolation between customer domains while costing basically nothing in real infrastructure. It's math. It wasn't completely free; we had to use 2,000 anycast IP addresses, and it turns out that we also had to register 512 domains for them because of how many TLDs require name servers to be registered and to have glue records; so that was a fun process working with our registrar. But we got it done.
I named the approach "Shuffle Sharding", and it's more discovery than invention. Many multi-tenant systems that use some kind of random placement get a kind of shuffle sharding, and network filtering techniques like Stochastic Fair Blue use time-seeded hashing to similar effect. But I've never seen anything quite the same, or with the level of control that we could apply; I could even extend it to a kind of recursive nested shuffle shading that isolates at even more levels. For example if you want to isolate not just a caller, but a caller's callers when they are in some kind of "on behalf of" call pattern.
Years later, I made a personal pilgrimage of gratitude to see a Knuth Christmas lecture in person, and sat in the front row. I still read every scrap of material that Knuth puts out (including the Organ pieces!) because I never know what it might inspire. All of this to say ... I do think his volumes are surprisingly practical for programmers; they broaden your mind as well as deepen your understanding. What more could you want.
These are the kinds of stories I love from HN! Stories of theory meeting practice are my absolute favorite.
My dad got me a set of TAoCP a few years back as a birthday gift (before 4b) and I realized that I do not have the background to even begin on 1 (at least not without some daily devotion of time). Maybe I'll have to take some more time and try again.
I suggest picking up Knuth's Concrete Mathematics. It helps you get used to the math in TAoCP as well as his writing style, which manages to be simultaneously rigorous, serious, and humorous.
Utterly unrelated to Knuth, and probably not useful for picking DNS servers because of their more static nature, but you might enjoy Ceph's CRUSH load distribution algorithm. Very rough gist: you can use it to e.g. set policy to avoid two replicas in the same rack, and ensure third replica goes on a different floor. And you can express server overload to migrate data off of one gradually, etc. Ceph uses that, with servers gossiping about failures & overload, to have clients directly contact the right servers.
> Early that summer, I was reading one of Knuth's recent fascicles for 4A and was swimming in combinatorial algorithms. One night it just "clicked" that...
It's frankly unbelievable how frequently this happens. "Swimming around" in these concepts inspires solutions that otherwise seem to come from nowhere.
Hehe, I also got the box set at a huge discount when 4B came out. Amazon took their sweet time (and I had to confirm I didn't want to cancel the order), but they came through and I got my box set. It will be my son's graduation present.
I was not aware of an update to this algorithm, I'll have to look it out.
The original dancing link is one of my favorite papers, you can really see Knuth's love for algorithms (it's not in every paper you see sentences like "This process causes the pointer variables inside the global data structure to execute an exquisitely choreographed dance"). I'm using it to generate crosswords (the horizontal and vertical words forming an exact cover of the grid).
I cannot recommend checking out Volume 4B enough, then. He goes much deeper, improves the algorithm, adapts it to different constraint problems, and provides hundreds of really cool exercises (including word problems like crosswords, I think). It's the best.
Yes that's the one ! I found it when I was trying to solve the tetraminos in The Talos Principle without looking for a game guide... I agree with OskarS it is a rewarding algorithm to implement.
I have made an implementation of the original Dancing Links algorithm, but for some large problem, more than a million rows and 104 columns with an average of about sixteen positions per row, it is killed because it takes too much memory.
I wonder if the updated algorithm is using less memory.
My guess is that this large problem has about a hundred million solutions. So, even if it finds a hundred solutions per second, it still would require about ten days to finish.
The problem, I am working on, is the number of solutions to the 'Fancy Tetris Houten Puzzel' where all pieces of the same color touch are connected by at least one side touching another side of a piece with the same color.
I have been thinking about other algorithms for solving this Exact Cover problem that are less memory sensitive.
It does improve memory usage! In the version in the paper, each item has four links, in the book version they only have two. So memory usage is roughly cut in half.
From a rough estimation, it should not run out of memory with these constraints. The matrix should be about 1m rows * 16 cells/row * (4 pointers/cell + overhead?) * 8 bytes/pointer = approx 1 GB. That's quite little.
The dynamic memory is negligible with 104 cols, avg search depth should only be around 104/16.
How did Dancing Links change from the paper? When I implemented it I could not see anything that could possibly be changed, so any improvement would be surprising and wonderful to me.
You know in the sparse matrix, every item has four links (left, right, up and down)? In the version in the book, each item only has two links, up and down. The left/right links become implicit, because he stores the items contiguously in an array (so right of item 14 is item 15), and inserts "spacers" so you know when a row ends and the next one begins. This doesn't algorithmically improve the runtime, but it uses half the memory and gives it much better cache behaviour (btw: this is sometimes a charge levied at Knuth, he only cares about algorithms and not practical runtime when it comes to things like cache coherency. This is ludicrous, as this example shows.)
That's the change to the "basic" algorithm, but he then goes on to add a bunch of new features to basic Dancing Links, modifying it so that it's suitable for different kinds of constraint solving (adding required rows, things like that).
If you've implemented Dancing Links in the past, you owe it to yourself to check out the book version! He also has hundreds of really great exercises about it.
I feel that there is no good answer to this. For me It is more about the parts of the solution than the big problems. Some of the big solutions stay but it is mostly how you fit things together that stays with me. Everyone works differently here, e.g. I tend to reuse lots of things other people reimplement them there are drawbacks with both types of learning. I read a lot of code.
