Hidden latency in the Linux network stack
blog.cloudflare.com
blog.cloudflare.com
1) Any chance this bug would have manifested as "connection reset" errors when accessing HN? I exchanged email with Dan a couple months ago trying to figure out why about 10% of my requests were failing, but we never figured out the root cause before (after some weeks) the problem went away.
2) As others have pointed out, doubling the number of hash buckets seems like a bandaid. But other than the scolding comment, is there any reason not to go to an appropriately sized hash? If you know in advance that you are going to have 16K addresses (ie, not the use case the original code anticipated), it would seem beneficial to choose a data structure that has a fighting chance of providing good performance.
3) This seems like a wonderful argument for _against_ running your high performance DNS server on the same machine as your other services. Would containerization have helped here, possibly with each OS pinned to a set of cores? Is the cost of splitting it off onto a separate physical machine prohibitive? At the optimization level you are aiming for, "process isolation" seems like a pretty leaky abstraction.
4) Going farther down the path of reducing jitter, have you considered running a tickless (NOHZ_FULL) kernel? Perhaps you are already doing it, but quieting down the cores running your important services can make a significant difference. I've been exploring this direction, and have found it rewarding. Info on one way to measure is here: https://kernel.googlesource.com/pub/scm/linux/kernel/git/fre...
2) Correct. Increasing number of buckets is a bandaid. Improving the linux code for inet_lookup_listener is not a trivial task. But for some reason Linux did optimize similar function for UDP. Wonders of the network stack.
3) Not really, dns can coexist with other services. The bug was having many TCP listening sockets on the same port without a good reason really. There is no DDoS benefit in splitting receive queues for TCP.
Containers won't help, the packets go to the same instance of LHTABLE.
4) Scheduling jitter is a subject for separate story.
Either way, if it's a critical service, I'd rather have it running on hardware where there isn't much competition for resources, so not a whole lot of virtualization.
I am not familiar with the code, but it looks to me like having a separate hash table for address-bound sockets like you suggest would work.
I suggest using some sort of extensible hash table (possibly with a bounded maximum size so things do not become crazy) to avoid statically sizing it. That way it is not too big on systems where it is not often used and not too small on systems where it is heavily used. The type of extensible hash table should be picked for compatibility with RCU to avoid causing a regression in multicore scaling. A quick google search suggests that a split-ordered list might work here:
https://lwn.net/Articles/573431/
As for the hash function, I would suggest adding the IP address and a random value calculated at boot time to the sum calculated by the current hash function before it currently truncates, run that sum through a next() function from a fast PRNG and then truncate the result to whatever the extensible hash table wants at the given moment. As for potential PRNG next() function donors, the xorshift128+ at the following site is fairly nice:
The idea behind using a PRNG's next() function would be to avoid artifacts in how IP addresses are assigned that would cause abnormally many hash table collisions. The idea behind adding a random number to the sum before the hash function is to ensure that people could not pick IP address + port combinations that hash to the same location as part of an algorithmic complexity attack. The potential for an algorithmic complexity attack here is relatively minor given that the problem occurs in normal use, but fixing it is rather inexpensive, so someone might as well do it when changing this.
Anyway, this does not do anything for the wild card case, but barring gratuitous use of SO_REUSEPORT, the number of sockets should be be small. Cloudflare is using address-bound sockets, so it probably would not matter for them.
That is not meant to discount the fun that one can have when using overkill to eliminate the potential for historical issue to resurface in some new situation. It can be very fun, as long as one does not spend too much time on it. I have been known to do it on occasion:
https://github.com/zfsonlinux/spl/commit/0b43696e6676391e5be...
I suspect that's the real fix. Now all those (16k) bound addresses aren't creating hash table entries, so other connections that happen to use a port that hashes to 21 (or 53 after enlarging the table) aren't being shoved into a hash bucket that starts with 16k entries already in it.
The enlarging of the hash table I think is less a fix for this problem (although it would halve the number of later connections being put in the bucket), and more just a good fix they happened to do at the same time.
Yes. It just reduces the risk that they run into this problem again with a different port constellation.
It does, however, reduce the overall impact when all connections are considered.
It works out the same for the application: 1 fd or 16k fds doesn't really matter if you're using epoll, and that single fd can accept connections to any of those 16k IP addresses.
Now, from a server point of view there are two types of connections: inbound and outbound. Our servers accept connections but they also establish connections, for example to your http origin hosts.
So from the point of view of our server the "colliding" packets will fit two categories: A) incoming packets to port 53 B) incoming packets to outbound connections which source port % 32 == 21.
For A) this is not that a big deal. DNS usually works over UDP, there are not _that_ many DNS queries done using TCP.
For B), since Linux choses source port incrementally, that means every 32'nd connection will possibly have some packets hitting the unhappy bucket.
Therefore increasing the hash size twice, reduces the chance of collision twice: now every 64th outbound connection will have some packets hitting the unhappy bucket.
The full answer is: depending on which RFC you read :)
Initially the RFC's specified that you could only use TCP if you got UDP truncation _first_.
Nowadays that's relaxed but it's very vague when you should use TCP except for after UDP TR. For example Bind will try to connect over TCP if UDP fails.
Generally speaking most of the traffic goes over UDP, and sometimes, in undefined circumstances, some stuff may be requested over TCP. No hard rule.
But yes, it seems like an unnecessary change.
In particular, a rewrite would have to make sure not to make the general case worse in an attempt to avoid this pathological situation.
Increasing the hash size doesn't fix the unhappy bucket, but it does reduce chance that packets will ever hit it. So yes, traversal of this bucket will be slow, but it will be hit less often.
For the 2nd level you could size the hash table appropriately since you always know the maximum number of IP addresses a host has.
Would be nice if this 2level array/hash was tunable from /proc or /sys.
Using a binary tree at each bucket could also work well but you would have to rebalance the tree periodically if listeners were inserted in sorted order. A self balancing tree could be used instead but then again this adds complexity.
Destination IP is a reasonable addition to the hash function, however.
The host wants to send a datagram to some IP address Y somewhere. It knows that the route for that IP goes through some local gateway with IP address X, so it must actually send the datagram to X, for which it needs the MAC. Normally, it knows the MAC of that gateway, because X is associated with the MAC in the ARP cache.
From time to time, the ARP cache entry expires. In that case, before the packet can be sent to the remote host Y, an ARP query must be performed: an ARP "who has X?" broadcast request is generated, to which the gateway will reply. Only then can that host send the packet to Y, through X.
This extra ARP exchange shouldn't take anywhere near 100 milliseconds, of course. But that is beyond the control of the host that is querying.
A naïve solution would be to choose a bucket based on the destination port as well as the source port if one is available (e.g. TCP). This might help balance load affecting particular local ports since we can assume the source port for TCP will be random enough. However, it doesn't solve the problem - it'll just hide it. Random spikes in latency for connections to random customers? Sounds undesirable.
A reasonable solution might be to work out a way to map gateway 53/UDP to a diverse set of ports which are bound to rrdns processes on the boxes which currently have 16K IP addresses. For UDP packets, this would be possible by doing on-wire modifications to the transport header and recalculating any checksums. Perhaps that just shifts the burden though.
You could suggest including the bound destination IP in the hash, but then you'd also need a separate hashtable for sockets that are bound to any IP (instead of being bound to a specific IP).
I don't think that you'd need a separate table for star bound listeners if the IP is mixed in since you could just hash in 0.0.0.0 but you'd need to check both the real IP and the special value too which is a potentially damaging performance hit. It's probably done with just the destination port for a good reason.
While bind to star works, it feels like you answered an operational concern but left the design consideration on the table.
I'm curious is if Cloudflare has investigated using DrafonflyBSD, given that it has a lockless network stack.
Would the lookup be different or the design aspect that produces what many would class a edge case instance, one that as companies grow, is only going to become more common.
$ netstat -ep4ln --udp