zalando / skipper / 23137875601

79%

push

github

Optimize: consistent hash algorithm (#3918)

optimize: limit hash ring bucket size to max 10k
optimize: consistentHash linear scan by using binary search in case it
is actually faster than linear scan

In practice we will see better results as the worst case will be in
favor of the new code, because the linear scan had only to walk to index
332 instead of 5000 for example. I added some log during test to check
it.

```
% benchstat old.txt new.txt
goos: linux
goarch: amd64
pkg: github.com/zalando/skipper/proxy
cpu: AMD Ryzen 7 PRO 4750U with Radeon Graphics
                                               │   old.txt    │               new.txt               │
                                               │    sec/op    │   sec/op     vs base                │
ConsistentHashSelectEndpoint/10_endpoints        195.8n ±  3%   182.7n ± 2%   -6.72% (p=0.001 n=10)
ConsistentHashSelectEndpoint/10_endpoints-2      243.4n ±  2%   231.6n ± 3%   -4.87% (p=0.001 n=10)
ConsistentHashSelectEndpoint/10_endpoints-4      235.2n ±  2%   218.1n ± 3%   -7.27% (p=0.000 n=10)
ConsistentHashSelectEndpoint/10_endpoints-8      240.6n ±  3%   232.3n ± 2%   -3.41% (p=0.000 n=10)
ConsistentHashSelectEndpoint/10_endpoints-16     239.9n ±  3%   231.1n ± 1%   -3.65% (p=0.000 n=10)
ConsistentHashSelectEndpoint/100_endpoints       339.0n ±  5%   334.4n ± 1%   -1.36% (p=0.011 n=10)
ConsistentHashSelectEndpoint/100_endpoints-2     376.8n ±  2%   360.0n ± 3%   -4.45% (p=0.000 n=10)
ConsistentHashSelectEndpoint/100_endpoints-4     390.5n ±  4%   356.1n ± 3%   -8.80% (p=0.000 n=10)
ConsistentHashSelectEndpoint/100_endpoints-8     394.8n ±  4%   370.8n ± 1%   -6.07% (p=0.000 n=10)
ConsistentHashSelectEndpoint/100_endpoints-16    391.8n ±  3%   368.4n ± 1%   -5.97% (p=0.000 n=10)
ConsistentHashSelectEndpoint/250_endpoints       276.8n ±  3%   286.2n ± 1%   +3.41% (p=0.003 n=10)
ConsistentHashSelectEndpoint/250_endpoints-2     296.0n ±  4%   303.2n ± 4%   +2.45% (p=0.043 n=10)
ConsistentHashSele... (continued)

5 of 39 new or added lines in 2 files covered. (12.82%)

25840 of 32960 relevant lines covered (78.4%)

87891.93 hits per line