5 ms·

Stray 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 t

by nkurz 11y ago

Stray 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 ago
1) 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 ago
If the issue is in the kernel, containers won't solve it.
- nkurz 11y ago
  You are correct. As evidenced by the mention of "each OS", I mangled that sentence and wrote containerization where I should have said virtualization. I meant something like "While containerization wouldn't have helped here, would virtualization (perhaps with each OS pinned to a different set of cores) have helped?"
  - Florin_Andrei 11y ago
    Yeah, that sounds better. 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.
- ryao 11y ago
  The hash function includes the address of the struct net when mount namespaces are in use, so if the same service were spread among different containers (or more specifically, different mount namespaces), the hash collisions per bucket might be somewhat more uniform. It would likely be far better to patch the kernel than it would be to abuse mount namespaces to workaround this. That workaround would add complexity for a fairly limited gain that is more by accident than anything else.
  - ryao 11y ago
    This should have been net means bases not mount names basis. In which case I'll be doesn't make much sense even as a horrible hack.
    - ryao 11y ago
      That will be the last time that I try using dictation to compose a hacker news comment without reading it. That should have read: "This should have been net namespaces, not mount name spaces. In that case, it does not make sense even as a horrible hack".
ryao 11y ago
> 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. 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/ 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: http://xorshift.di.unimi.it/ http://xorshift.di.unimi.it/ 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.
- ryao 11y ago
  By the way, the bandaid solution lowers the latency not just for each request, but also each queued request waiting for CPU time making the reduction in time culminative. As long as the bandaid solution keeps the maximum queue depth and average time spent processing low enough, it would probably suffice. If the spikes remain low under load tests, implementing it would be more of an exercise in seeing how much you can reduce CPU time in this code path for the sake of reducing it than it would be a useful improvement. 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/0b43696e6676391e5bee8ba49e76e599bac1d89d https://github.com/zfsonlinux/spl/commit/0b43696e6676391e5be...

by nkurz 11y ago

majke 11y ago

1) 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 ago

If the issue is in the kernel, containers won't solve it.

nkurz 11y ago
You are correct. As evidenced by the mention of "each OS", I mangled that sentence and wrote containerization where I should have said virtualization. I meant something like "While containerization wouldn't have helped here, would virtualization (perhaps with each OS pinned to a different set of cores) have helped?"
- Florin_Andrei 11y ago
  Yeah, that sounds better. 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.
ryao 11y ago
The hash function includes the address of the struct net when mount namespaces are in use, so if the same service were spread among different containers (or more specifically, different mount namespaces), the hash collisions per bucket might be somewhat more uniform. It would likely be far better to patch the kernel than it would be to abuse mount namespaces to workaround this. That workaround would add complexity for a fairly limited gain that is more by accident than anything else.
- ryao 11y ago
  This should have been net means bases not mount names basis. In which case I'll be doesn't make much sense even as a horrible hack.
  - ryao 11y ago
    That will be the last time that I try using dictation to compose a hacker news comment without reading it. That should have read: "This should have been net namespaces, not mount name spaces. In that case, it does not make sense even as a horrible hack".

ryao 11y ago

> 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. 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/ 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: http://xorshift.di.unimi.it/ http://xorshift.di.unimi.it/ 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.

ryao 11y ago
By the way, the bandaid solution lowers the latency not just for each request, but also each queued request waiting for CPU time making the reduction in time culminative. As long as the bandaid solution keeps the maximum queue depth and average time spent processing low enough, it would probably suffice. If the spikes remain low under load tests, implementing it would be more of an exercise in seeing how much you can reduce CPU time in this code path for the sake of reducing it than it would be a useful improvement. 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/0b43696e6676391e5bee8ba49e76e599bac1d89d https://github.com/zfsonlinux/spl/commit/0b43696e6676391e5be...