9 ms·
Hidden latency in the Linux network stack
- charliedevolve 11y agoWhy did increasing the size of the hash help? Wouldn't the %64 (or whatever the new value was) just send all the port 53 sockets into the same bucket again? It seems you'd need a different hash function that provides more uniformity.
- majke 11y agoIt would reduce the probability of collision. Sure, port 53 will always go to unlucky bucket. But port 16275 may or may not collide depending on thehash size.
- charliedevolve 11y agoReduce the collisions how much, though? Are you using a port number == N*hashSize+53 for something else a lot? A collision is guaranteed for every connection to port 53, so isn't that a much bigger source of collisions? I think the hash size of 32 isn't the problem. It's the function.
- majke 11y agoI think I understand the confusion. The packets are hashed based on DESTINATION PORT. 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.
- charliedevolve 11y agoOh yes, I forgot that tcp/53 is mostly (if not entirely) for zone transfers.
- majke 11y ago:) 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.
- bboreham 11y agoRecalling that CloudFlare's business is dealing with malicious actors, you should assume that the caller has read all the RFCs and then deliberately disobeyed them.
- kbenson 11y agoFor TCP connections our DNS server now binds to ANY_IP address (aka: 0.0.0.0:53, :53). We call this "bind to star". While binding to specific IP addresses is still necessary for UDP, there is little benefit in doing that for the TCP traffic. For TCP we can bind to star safely, without compromising our DDoS defenses. 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.
- creshal 11y ago> 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.
- stingraycharles 11y agoA bit pedantic, but it doesn't necessarily reduce the risk, but rather the impact: using 64 buckets would only have half as many connections go into a bad bucket. This, however, does not in any way decrease the chance of the problem occuring again.
- sinxoveretothex 11y agoUsing twice as many buckets, there will be half as many destination ports in the same bucket (65535 / 32 ≈ 2048, 65535 / 64 ≈ 1024), but since the "bad" connections described in the blogpost all use the same destination port, it won't change anything wrt that. It does, however, reduce the overall impact when all connections are considered.
- jcoffland 11y ago
- deleted 11y ago[deleted]
- readams 11y agoThey might hash the source port also. Maybe they didn't mention this.
- charliedevolve 11y agoMixing in the source port might be a good way to fix that hash function.
- seabee 11y agoThe hash is used to find listening sockets. Source port doesn't help you there. Destination IP is a reasonable addition to the hash function, however.
- xigency 11y agoAs others have answered, it doesn't help fix this problem in any way. I'm assuming the team doing this investigation wasn't willing to rewrite `__inet_lookup_listener`. I guess the quick fix became the concern at that point. (Compared to rewriting kernel modules.) But yes, it seems like an unnecessary change.
- majke 11y agoPlease read my other comment in this thread. https://news.ycombinator.com/item?id=11448987 https://news.ycombinator.com/item?id=11448987 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.
- jandrese 11y agoI'm not sure inet_lookup_listener requires a rewrite for a general purpose kernel. They were hitting this problem because they were doing something unusual (starting thousands of listeners on the same port) and they found a pretty reasonable workaround. In particular, a rewrite would have to make sure not to make the general case worse in an attempt to avoid this pathological situation.
- jcoffland 11y ago__inet_lookup_listener could be modified to use a two level hash that only kicked in for buckets which exceeded a certain threshold. The second level hash tables would xor the parts of the destination IP address modulo the hash table size. Special care would have to be taken for listeners on 0.0.0.0. This would solve the problem with negligible cost to the general case but at the expense of added complexity.
- edwintorok 11y agoIn fact wouldn't it be simpler to just use an array with all 64k destination ports for the 1st level, and a hash based on destination IP for the 2nd level? This would only need 64k*sizeof(pointer) memory globally for the 1st level, which sounds reasonable for everything except low-memory embedded devices. Or does cache-locality matter here so much that its worth taking the hash-collision penalty on the 1st level? 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.
- Gratsby 11y agoWhy not look into changing the hash keys such that they are not bound to listening port or alternatively put a new lookup and hash in place for this specific purpose? While bind to star works, it feels like you answered an operational concern but left the design consideration on the table.
- deegles 11y agoI love these mysterious bug deep dives. I should start aggregating them somewhere...
- nkurz 11y agoStray thoughts: 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/frederic/dynticks-testing/+/master https://kernel.googlesource.com/pub/scm/linux/kernel/git/fre...
- majke 11y ago1) Not really. Connection resets have nothing to do here. Are you by any chance running on a slow network? We did some debugging of problems slow clients recently. 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.
- Florin_Andrei 11y agoIf the issue is in the kernel, containers won't solve it.
- ishtu 11y agoCan anyone suggest a good reading on differences in linux and freebsd network stacks?
- alberth 11y agoWhat about DragonflyBSD? I'm curious is if Cloudflare has investigated using DrafonflyBSD, given that it has a lockless network stack.
- shiftoutbox 11y agoI think Matt Dillon would love to see that . Also I would love to see the analysis of their situation on a UNIX , BSD's and even Windows .
- caf 11y agoThis wasn't a locking issue.
- js2 11y agoWhat did you increase the size of LHTABLE to? I don't see that mentioned in the post.
- majke 11y agoIn order to reduce the number of packets hitting the bad bucket. With LHTABLE of size 32 port 16257 will hit bad bucket. With other sizes port 16257 may not hit the naughty bucket.
- nkurz 11y agoI think the question was what number you used for the new LHTABLE, rather than the purpose of increasing it. That is, did you double it from 32 to 64? Choose a prime? Something else?
- js2 11y agoCorrect, that was my question. The post doesn't say what they chose for the LHTABLE size when they recompiled the kernel, only that it was increased from 32. BTW, according to the patch the article linked to, the size has to be a power of 2. http://patchwork.ozlabs.org/patch/79014/ http://patchwork.ozlabs.org/patch/79014/
- wrigby 11y agoThat makes sense - since port numbers are unsigned integers, you can just use a bitwise AND rather than a more costly MOD. I haven't actually looked at the internals of the hash, so I'm just assuming it's simply BUCKET = DPORT & MASK.
- forgotmypassw 11y agoEven though I'm not using CloudFlare myself, I always enjoy reading their blog posts, these guys are amazing hackers.
- triplenineteen 11y agoIt seems like they are using a non-standard netstat switch: $ netstat -ep4ln --udp Is that '4' a typo or something?
- Negitivefrags 11y agoIt means only list ipv4 sockets. It's pretty standard across many command line network tools.
- dice 11y agoIt's present in my netstat, from `net-tools 2.10-alpha`. Man page says it's shorthand for `--protocol=inet` (as opposed to `inet6`) which shows only IPv4 sockets.
- kazinator 11y agoIn the internet protocol suite, there is something called ARP. That will cause a small latency spike whenever an ARP cache entry expires. 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.
- ecma 11y agoI'm not entirely convinced that increasing the size of LHTABLE solves anything. True, it may remove some collisions in the hash table but note that 63925 % 64 = 53. Given that the two slow ports listed seem to be arbitrary and assigned to customers, they're probably just a symptom of the overload on 53/UDP. I'm not suggesting they chose 64, that's unclear, but whatever they chose probably just shifts problem the elsewhere. Increasing it /would/ inherently reduce the frequency of the events though so you can call that a win. 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.
- eridius 11y agoYou can't include the source port in the hash, because this is a table of listening sockets, i.e. no connection has been established yet and the socket needs to see packets from ANY source as long as they go to the right destination. 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).
- caf 11y agoYou wouldn't need a separate hash table, you could first look up Hash(destip, destport) then if that fails to find a listener, look up Hash(0, destport).
- ecma 11y agoGood catch. I did mean that mixing in the source would apply to the established table if it's constructed in the same way but doesn't do so already (which would surprise me now that I think about it properly). 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.
- lttlrck 11y agoIt would be helpful to show the improvement for the two changes made individually instead of lumping them together.
- known 11y agoCan't we fix/configure it in /etc/sysctl.conf
- wrigby 11y agoThat would actually be pretty cool, but the data would have to be redistributed across the new set of buckets when the parameter was changed. That could get really messy...
- Zenst 11y agoI wonder how if this was IPv6 if this problem would still entail and if IPv6 has design aspects that would negate this issue? 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.