Skip to content

endpoint: switch rendezvous hash func to xxhash

Warren Gifford requested to merge endpoints-switch-to-xxhash into main

Created by: tsenart

My original testing didn't use the exact list of indexable repos that we get in production. With that list, xxhash has better distribution than fnv.

=== RUN   TestConsistentHashing
=== RUN   TestConsistentHashing/Distribution
    consistenthash_test.go:114:
          node  0  consistent(crc32ieee)  =>  52210    5.04%  rendezvous(xxhash64)  =>  43174    4.17%  rendezvous(fnv)  =>  43051    4.16%  rendezvous(fnva)  =>  43399  4.19%
          node  1  consistent(crc32ieee)  =>  54174    5.23%  rendezvous(xxhash64)  =>  42875    4.14%  rendezvous(fnv)  =>  42897    4.14%  rendezvous(fnva)  =>  43101  4.16%
          node  2  consistent(crc32ieee)  =>  54347    5.25%  rendezvous(xxhash64)  =>  43121    4.16%  rendezvous(fnv)  =>  43446    4.19%  rendezvous(fnva)  =>  43269  4.18%
          node  3  consistent(crc32ieee)  =>  49201    4.75%  rendezvous(xxhash64)  =>  43233    4.17%  rendezvous(fnv)  =>  43349    4.19%  rendezvous(fnva)  =>  43214  4.17%
          node  4  consistent(crc32ieee)  =>  47923    4.63%  rendezvous(xxhash64)  =>  43341    4.18%  rendezvous(fnv)  =>  43013    4.15%  rendezvous(fnva)  =>  42545  4.11%
          node  5  consistent(crc32ieee)  =>  43086    4.16%  rendezvous(xxhash64)  =>  43459    4.20%  rendezvous(fnv)  =>  43500    4.20%  rendezvous(fnva)  =>  43105  4.16%
          node  6  consistent(crc32ieee)  =>  48694    4.70%  rendezvous(xxhash64)  =>  42994    4.15%  rendezvous(fnv)  =>  43048    4.16%  rendezvous(fnva)  =>  43052  4.16%
          node  7  consistent(crc32ieee)  =>  38602    3.73%  rendezvous(xxhash64)  =>  43204    4.17%  rendezvous(fnv)  =>  43194    4.17%  rendezvous(fnva)  =>  43526  4.20%
          node  8  consistent(crc32ieee)  =>  39859    3.85%  rendezvous(xxhash64)  =>  43157    4.17%  rendezvous(fnv)  =>  43112    4.16%  rendezvous(fnva)  =>  43181  4.17%
          node  9  consistent(crc32ieee)  =>  38588    3.73%  rendezvous(xxhash64)  =>  43337    4.18%  rendezvous(fnv)  =>  43223    4.17%  rendezvous(fnva)  =>  42959  4.15%
          node 10  consistent(crc32ieee)  =>  44316    4.28%  rendezvous(xxhash64)  =>  43031    4.15%  rendezvous(fnv)  =>  43043    4.16%  rendezvous(fnva)  =>  43351  4.19%
          node 11  consistent(crc32ieee)  =>  41337    3.99%  rendezvous(xxhash64)  =>  43168    4.17%  rendezvous(fnv)  =>  43084    4.16%  rendezvous(fnva)  =>  43208  4.17%
          node 12  consistent(crc32ieee)  =>  38353    3.70%  rendezvous(xxhash64)  =>  43071    4.16%  rendezvous(fnv)  =>  42881    4.14%  rendezvous(fnva)  =>  43374  4.19%
          node 13  consistent(crc32ieee)  =>  32474    3.14%  rendezvous(xxhash64)  =>  43501    4.20%  rendezvous(fnv)  =>  43049    4.16%  rendezvous(fnva)  =>  43240  4.17%
          node 14  consistent(crc32ieee)  =>  37253    3.60%  rendezvous(xxhash64)  =>  43130    4.16%  rendezvous(fnv)  =>  43518    4.20%  rendezvous(fnva)  =>  43372  4.19%
          node 15  consistent(crc32ieee)  =>  38416    3.71%  rendezvous(xxhash64)  =>  42947    4.15%  rendezvous(fnv)  =>  43482    4.20%  rendezvous(fnva)  =>  43020  4.15%
          node 16  consistent(crc32ieee)  =>  30456    2.94%  rendezvous(xxhash64)  =>  43461    4.20%  rendezvous(fnv)  =>  42631    4.12%  rendezvous(fnva)  =>  42990  4.15%
          node 17  consistent(crc32ieee)  =>  38790    3.75%  rendezvous(xxhash64)  =>  42883    4.14%  rendezvous(fnv)  =>  43150    4.17%  rendezvous(fnva)  =>  43543  4.20%
          node 18  consistent(crc32ieee)  =>  48634    4.70%  rendezvous(xxhash64)  =>  43296    4.18%  rendezvous(fnv)  =>  43126    4.16%  rendezvous(fnva)  =>  42951  4.15%
          node 19  consistent(crc32ieee)  =>  43723    4.22%  rendezvous(xxhash64)  =>  43313    4.18%  rendezvous(fnv)  =>  43208    4.17%  rendezvous(fnva)  =>  42776  4.13%
          node 20  consistent(crc32ieee)  =>  43108    4.16%  rendezvous(xxhash64)  =>  43117    4.16%  rendezvous(fnv)  =>  43449    4.20%  rendezvous(fnva)  =>  43154  4.17%
          node 21  consistent(crc32ieee)  =>  48880    4.72%  rendezvous(xxhash64)  =>  42812    4.13%  rendezvous(fnv)  =>  43116    4.16%  rendezvous(fnva)  =>  43305  4.18%
          node 22  consistent(crc32ieee)  =>  45607    4.40%  rendezvous(xxhash64)  =>  43031    4.15%  rendezvous(fnv)  =>  43166    4.17%  rendezvous(fnva)  =>  42901  4.14%
          node 23  consistent(crc32ieee)  =>  37682    3.64%  rendezvous(xxhash64)  =>  43057    4.16%  rendezvous(fnv)  =>  42977    4.15%  rendezvous(fnva)  =>  43177  4.17%

        Stats:
          consistent(crc32ieee)  min: 30456  max: 54347  mean: 43154.708  median: 43097  stdev: 6290.164
           rendezvous(xxhash64)  min: 42812  max: 43501  mean: 43154.708  median: 43143  stdev: 184.527
                rendezvous(fnv)  min: 42631  max: 43518  mean: 43154.708  median: 43121  stdev: 213.984
               rendezvous(fnva)  min: 42545  max: 43543  mean: 43154.708  median: 43179  stdev: 228.502

Merge request reports