# Improving the default routing hash function **URL:** \ **Category:** Elasticsearch\ **Created:** [January 18, 2015, 8:22pm UTC](https://discuss.elastic.co/t/improving-the-default-routing-hash-function/21702 "2015-01-18T20:22:30Z")\ **Posts on this page:** 3\ **Page:** 1
**Author:** ![Andrew\_White](https://avatars.discourse-cdn.com/v4/letter/a/77aa72/32.png) [@Andrew\_White](https://discuss.elastic.co/u/Andrew_White)\ **Post date:** [January 18, 2015, 8:22pm UTC](https://discuss.elastic.co/t/improving-the-default-routing-hash-function/21702/1 "2015-01-18T20:22:30Z")
I noticed that the default routing hash function is DJB. This function is particularly poor at routing when the input keys are short and are mildly different. For example, basic two digit hex based values "00" -\> "FF" produce very large hot spots on clusters of size 11, 16, and 17 and others. By "large" I mean that on an uniform input distribution, the largest shards is over 2x larger (sometimes up to 4x!) than the smallest shard. I feel it is reasonable to assume from a usability standpoint that if the routing key is an order of magnitude larger than the modulus that the resulting document distribution in the shards to be uniform. In our case, we had 255 distinct routing keys over 17 shards and the smallest shard is 40% the size of the largest. Furthermore, we know that the number of documents per routing key is roughly the same. This almost feels like a bug (maybe it is). It is certainly unexpected. Something like FNV seems like a good alternative. I would add the the Java string hash alternative isn't much better in a lot of cases, especially short inputs. Is there a particular reason for using DJB? Any chance of changing the default or including something like FNV out-of-the box? I would also suggest a note in the documentation about the potential for hotspot simply due to routing key selection. Any thoughts in general? Thanks, Andrew White -- You received this message because you are subscribed to the Google Groups "elasticsearch" group. To unsubscribe from this group and stop receiving emails from it, send an email to [elasticsearch+unsubscribe@googlegroups.com](mailto:elasticsearch+unsubscribe@googlegroups.com). To view this discussion on the web visit [https://groups.google.com/d/msgid/elasticsearch/cff4dd98-411e-47f8-9679-6d44f5f97806%40googlegroups.com](https://groups.google.com/d/msgid/elasticsearch/cff4dd98-411e-47f8-9679-6d44f5f97806%40googlegroups.com). For more options, visit [https://groups.google.com/d/optout](https://groups.google.com/d/optout). ---
**Author:** ![jpountz](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/jpountz/32/45836_2.png) [@jpountz](https://discuss.elastic.co/u/jpountz)\ **Post date:** [January 18, 2015, 9:25pm UTC](https://discuss.elastic.co/t/improving-the-default-routing-hash-function/21702/2 "2015-01-18T21:25:35Z")
Hi Andrew, This is indeed an issue. For your information, elasticsearch will switch to murmur3 in the next major version. For backward compatibility, old indices will still use DJB, but newly created indices will use murmur3. There is more background about this issue at > > > We currently use the djb2 hash function in order to compute the shard a > document… should go to. Unfortunately this hash function is not very > sophisticated and you can sometimes hit adversarial cases, such as numeric ids > on 33 shards. > > Murmur3 generates hashes with a better distribution, which should avoid the > adversarial cases. > > Here are some examples of how 100000 incremental ids are distributed to shards > using either djb2 or murmur3. > > 5 shards: > Murmur3: \[19933, 19964, 19940, 20030, 20133\] > DJB: \[20000, 20000, 20000, 20000, 20000\] > > 3 shards: > Murmur3: \[33185, 33347, 33468\] > DJB: \[30100, 30000, 39900\] > > 33 shards: > Murmur3: \[2999, 3096, 2930, 2986, 3070, 3093, 3023, 3052, 3112, 2940, 3036, 2985, 3031, 3048, 3127, 2961, 2901, 3105, 3041, 3130, 3013, 3035, 3031, 3019, 3008, 3022, 3111, 3086, 3016, 2996, 3075, 2945, 2977\] > DJB: \[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 900, 900, 900, 900, 1000, 1000, 10000, 10000, 10000, 10000, 9100, 9100, 9100, 9100, 9000, 9000, 0, 0, 0, 0, 0, 0\] > > Even if djb2 looks ideal in some cases (5 shards), the fact that the > distribution of its hashes has some patterns can raise issues with some shard > counts (eg. 3, or even worse 33). > > Some tests have been modified because they relied on implementation details of > the routing hash function. > > This change only affects indices that are created on or after elasticsearch 2.0. I don't know why DJB was chosen, but I believe that the fact that it performs well on incremental ids (0, 1, 2, 3, ...) and the default number of shards played a role into this choice (wild guess). On Sun, Jan 18, 2015 at 9:22 PM, Andrew White [andrew@datarank.com](mailto:andrew@datarank.com) wrote: > I noticed that the default routing hash function is DJB. This function is > particularly poor at routing when the input keys are short and are mildly > different. For example, basic two digit hex based values "00" -\> "FF" > produce very large hot spots on clusters of size 11, 16, and 17 and others. > By "large" I mean that on an uniform input distribution, the largest shards > is over 2x larger (sometimes up to 4x!) than the smallest shard. > > I feel it is reasonable to assume from a usability standpoint that if the > routing key is an order of magnitude larger than the modulus that the > resulting document distribution in the shards to be uniform. In our case, > we had 255 distinct routing keys over 17 shards and the smallest shard is > 40% the size of the largest. Furthermore, we know that the number of > documents per routing key is roughly the same. > > This almost feels like a bug (maybe it is). It is certainly unexpected. > Something like FNV seems like a good alternative. I would add the the Java > string hash alternative isn't much better in a lot of cases, especially > short inputs. > > Is there a particular reason for using DJB? Any chance of changing the > default or including something like FNV out-of-the box? I would also > suggest a note in the documentation about the potential for hotspot simply > due to routing key selection. Any thoughts in general? > > Thanks, > Andrew White > > -- > You received this message because you are subscribed to the Google Groups > "elasticsearch" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [elasticsearch+unsubscribe@googlegroups.com](mailto:elasticsearch+unsubscribe@googlegroups.com). > To view this discussion on the web visit > [https://groups.google.com/d/msgid/elasticsearch/cff4dd98-411e-47f8-9679-6d44f5f97806%40googlegroups.com](https://groups.google.com/d/msgid/elasticsearch/cff4dd98-411e-47f8-9679-6d44f5f97806%40googlegroups.com) > [https://groups.google.com/d/msgid/elasticsearch/cff4dd98-411e-47f8-9679-6d44f5f97806%40googlegroups.com?utm\_medium=email&utm\_source=footer](https://groups.google.com/d/msgid/elasticsearch/cff4dd98-411e-47f8-9679-6d44f5f97806%40googlegroups.com?utm_medium=email&utm_source=footer) > . > For more options, visit [https://groups.google.com/d/optout](https://groups.google.com/d/optout). -- Adrien Grand -- You received this message because you are subscribed to the Google Groups "elasticsearch" group. To unsubscribe from this group and stop receiving emails from it, send an email to [elasticsearch+unsubscribe@googlegroups.com](mailto:elasticsearch+unsubscribe@googlegroups.com). To view this discussion on the web visit [https://groups.google.com/d/msgid/elasticsearch/CAL6Z4j7i5oYWVNg1Qnyt2U9-gFYyoKGabSb49tWgCOcLTW5O2g%40mail.gmail.com](https://groups.google.com/d/msgid/elasticsearch/CAL6Z4j7i5oYWVNg1Qnyt2U9-gFYyoKGabSb49tWgCOcLTW5O2g%40mail.gmail.com). For more options, visit [https://groups.google.com/d/optout](https://groups.google.com/d/optout). ---
**Author:** ![system](https://us1.discourse-cdn.com/elastic/original/3X/1/a/1ac57faf039f6b580b3f104ef42a2a89e41014de.png) [@system](https://discuss.elastic.co/u/system)\ **Post date:** [July 6, 2017, 12:38am UTC](https://discuss.elastic.co/t/improving-the-default-routing-hash-function/21702/3 "2017-07-06T00:38:10Z")