3 ms·
> 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
by 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 agoBy 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...