Details

    • Type: Improvement Improvement
    • Status: Resolved
    • Priority: Major Major
    • Resolution: Won't Fix
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: None
    • Labels:
      None

      Description

      hash partitioner is using object.hashCode() for splitting keys into partitions. This results in bad distributions because hashCode() quality is poor.

      These hashCode() functions are sometimes written by hand (very poor quality) and sometimes generated from by commons lang code (poor quality). Applying some transformation on top of hashCode() provides better distribution.

      1. betterhash1.txt
        1 kB
        Radim Kolar
      2. betterhash2.txt
        3 kB
        Radim Kolar

        Activity

        Hide
        Radim Kolar added a comment -

        more of my patches for partitioner needs review

        MAPREDUCE-4839
        MAPREDUCE-4594

        Show
        Radim Kolar added a comment - more of my patches for partitioner needs review MAPREDUCE-4839 MAPREDUCE-4594
        Hide
        Radim Kolar added a comment -

        Patch rejected for backward compatibility reasons.

        Show
        Radim Kolar added a comment - Patch rejected for backward compatibility reasons.
        Hide
        Luke Lu added a comment -

        Thanks for the discussions, Robert and Radim. I think that you guys make a good case given the state of our hashCode impls. But People do use hash partitioner output for persistence (directory names in hdfs), so it'll break backward compatibility for such user cases, documented or not. A new partitioner is the most reasonable way to move forward, IMO.

        Show
        Luke Lu added a comment - Thanks for the discussions, Robert and Radim. I think that you guys make a good case given the state of our hashCode impls. But People do use hash partitioner output for persistence (directory names in hdfs), so it'll break backward compatibility for such user cases, documented or not. A new partitioner is the most reasonable way to move forward, IMO.
        Hide
        Radim Kolar added a comment -

        changing hashCode() has much greater effect then just changing partitioner because it invalidates all hash based lookups and serialized hashtables. Changing partitioner touches only code depending on undocumented behavior, its not breaking backward compatibility.

        If your current formula for hashing is modulo n, then you have to see that feeding numbers like 4,8,12,16 will get crap bucket distribution with npartitions=8. This is reason why all hashtables are doing rehashing or they use prime number in modulo operation.

        Show
        Radim Kolar added a comment - changing hashCode() has much greater effect then just changing partitioner because it invalidates all hash based lookups and serialized hashtables. Changing partitioner touches only code depending on undocumented behavior, its not breaking backward compatibility. If your current formula for hashing is modulo n, then you have to see that feeding numbers like 4,8,12,16 will get crap bucket distribution with npartitions=8. This is reason why all hashtables are doing rehashing or they use prime number in modulo operation.
        Hide
        Robert Joseph Evans added a comment -

        I agree fixing bad hashCode impls will probably have a bigger impact in general, and making a simple util to help out is a great idea. I just don't want to discount a potential performance optimization without actually running any benchmarks. Performance is very finicky, the impact this type of a change can have is very complicate, and I have been wrong too many times to guess how a change like this is really going to impact performance. If we can show that it has essentially no impact, good or bad, in the common case but can make some corner cases a lot better I would prefer to make it the default impl and provide a way to get old behavior back if needed. However, if it actually does have a measurable negative impact then we should leave things the way they are. But that is just my gut feeling and without numbers showing the impact I have a hard time really pushing either way.

        Show
        Robert Joseph Evans added a comment - I agree fixing bad hashCode impls will probably have a bigger impact in general, and making a simple util to help out is a great idea. I just don't want to discount a potential performance optimization without actually running any benchmarks. Performance is very finicky, the impact this type of a change can have is very complicate, and I have been wrong too many times to guess how a change like this is really going to impact performance. If we can show that it has essentially no impact, good or bad, in the common case but can make some corner cases a lot better I would prefer to make it the default impl and provide a way to get old behavior back if needed. However, if it actually does have a measurable negative impact then we should leave things the way they are. But that is just my gut feeling and without numbers showing the impact I have a hard time really pushing either way.
        Hide
        Radim Kolar added a comment -

        You do not have good hash function implemented. Writables are hashed using WritableComparator.hashBytes which is h = i + k * n. Using initial seed value 1 did not helps either.

        Show
        Radim Kolar added a comment - You do not have good hash function implemented. Writables are hashed using WritableComparator.hashBytes which is h = i + k * n. Using initial seed value 1 did not helps either.
        Hide
        Luke Lu added a comment -

        I'm fine with a separate partitioner (RehashPartitioner?) for historically "broken" hashCode impls. OTOH, I think the goal should strive for better hashCode impls moving forward, otherwise we'll be paying for the cost of rehash even if we have good hashCode impls.

        Show
        Luke Lu added a comment - I'm fine with a separate partitioner (RehashPartitioner?) for historically "broken" hashCode impls. OTOH, I think the goal should strive for better hashCode impls moving forward, otherwise we'll be paying for the cost of rehash even if we have good hashCode impls.
        Hide
        Robert Joseph Evans added a comment -

        However, I do think it has a place. For example LongWritable's hash function is

        @Override
        public int hashCode() {
          return (int)value;
        }
        

        This is contrived I know, but it could be that I have 7 reducers and I primarily output keys that are a multiple of 7 for whatever reason. There is plenty of cardinality but the distribution is still skewed. I think that is what this JIRA is trying to fix, not a lack of cardinality in the original hash function. We could change hashCode in LongWritable, but that too would be backwards incompatible for the same reason that changing HashPartitioner is backwards incompatible. The code is so simple someone could rely on this undocumented behavior in the code.

        This ultimately comes down to a performance optimization, so if we can get some benchmarks that can show benefit vs. cost of having this patch in we can make an informed decision. Or like Steve suggested previously we make it a separate partitioner that can be enabled by depending on who wants/needs it.

        Show
        Robert Joseph Evans added a comment - However, I do think it has a place. For example LongWritable's hash function is @Override public int hashCode() { return ( int )value; } This is contrived I know, but it could be that I have 7 reducers and I primarily output keys that are a multiple of 7 for whatever reason. There is plenty of cardinality but the distribution is still skewed. I think that is what this JIRA is trying to fix, not a lack of cardinality in the original hash function. We could change hashCode in LongWritable, but that too would be backwards incompatible for the same reason that changing HashPartitioner is backwards incompatible. The code is so simple someone could rely on this undocumented behavior in the code. This ultimately comes down to a performance optimization, so if we can get some benchmarks that can show benefit vs. cost of having this patch in we can make an informed decision. Or like Steve suggested previously we make it a separate partitioner that can be enabled by depending on who wants/needs it.
        Hide
        Doug Cutting added a comment -

        Luke, I agree that it might be better to fix weak hashCode() implementations directly rather than to try to fix them after-the-fact in HashPartitioner, especially when this introduces an incompatibility.

        Show
        Doug Cutting added a comment - Luke, I agree that it might be better to fix weak hashCode() implementations directly rather than to try to fix them after-the-fact in HashPartitioner, especially when this introduces an incompatibility.
        Hide
        Luke Lu added a comment -

        It does nothing for really bad hash functions (e.g. returns 0 or limited cardinality). I'd suggest that we put these as helper functions in util.hash. We have reasonable hash function for strings now. Helpers for other primitives would be useful to implement better hashCode for our writables.

        Show
        Luke Lu added a comment - It does nothing for really bad hash functions (e.g. returns 0 or limited cardinality). I'd suggest that we put these as helper functions in util.hash. We have reasonable hash function for strings now. Helpers for other primitives would be useful to implement better hashCode for our writables.
        Hide
        Radim Kolar added a comment -

        also to get good distribution and defend against week hash function, number after % (in your formula numReduceTasks) has to be prime. See glib source code.

        Show
        Radim Kolar added a comment - also to get good distribution and defend against week hash function, number after % (in your formula numReduceTasks) has to be prime. See glib source code.
        Hide
        Luke Lu added a comment -

        I don't see this as generally useful, it only works with hashCode already returns reasonable numbers (enough cardinality). It'll do absolutely nothing to improve quality but wasting CPU cycles for bad hashCode implementations. I suggest that we close this as won't fix, as it's not a good place to do this.

        Show
        Luke Lu added a comment - I don't see this as generally useful, it only works with hashCode already returns reasonable numbers (enough cardinality). It'll do absolutely nothing to improve quality but wasting CPU cycles for bad hashCode implementations. I suggest that we close this as won't fix, as it's not a good place to do this.
        Hide
        Hadoop QA added a comment -

        -1 overall. Here are the results of testing the latest attachment
        http://issues.apache.org/jira/secure/attachment/12556183/betterhash2.txt
        against trunk revision .

        +1 @author. The patch does not contain any @author tags.

        -1 tests included. The patch doesn't appear to include any new or modified tests.
        Please justify why no new tests are needed for this patch.
        Also please list what manual steps were performed to verify this patch.

        +1 javac. The applied patch does not increase the total number of javac compiler warnings.

        +1 javadoc. The javadoc tool did not generate any warning messages.

        +1 eclipse:eclipse. The patch built with eclipse:eclipse.

        +1 findbugs. The patch does not introduce any new Findbugs (version 1.3.9) warnings.

        +1 release audit. The applied patch does not increase the total number of release audit warnings.

        +1 core tests. The patch passed unit tests in hadoop-mapreduce-project/hadoop-mapreduce-client/hadoop-mapreduce-client-core.

        +1 contrib tests. The patch passed contrib unit tests.

        Test results: https://builds.apache.org/job/PreCommit-MAPREDUCE-Build/3100//testReport/
        Console output: https://builds.apache.org/job/PreCommit-MAPREDUCE-Build/3100//console

        This message is automatically generated.

        Show
        Hadoop QA added a comment - -1 overall . Here are the results of testing the latest attachment http://issues.apache.org/jira/secure/attachment/12556183/betterhash2.txt against trunk revision . +1 @author . The patch does not contain any @author tags. -1 tests included . The patch doesn't appear to include any new or modified tests. Please justify why no new tests are needed for this patch. Also please list what manual steps were performed to verify this patch. +1 javac . The applied patch does not increase the total number of javac compiler warnings. +1 javadoc . The javadoc tool did not generate any warning messages. +1 eclipse:eclipse . The patch built with eclipse:eclipse. +1 findbugs . The patch does not introduce any new Findbugs (version 1.3.9) warnings. +1 release audit . The applied patch does not increase the total number of release audit warnings. +1 core tests . The patch passed unit tests in hadoop-mapreduce-project/hadoop-mapreduce-client/hadoop-mapreduce-client-core. +1 contrib tests . The patch passed contrib unit tests. Test results: https://builds.apache.org/job/PreCommit-MAPREDUCE-Build/3100//testReport/ Console output: https://builds.apache.org/job/PreCommit-MAPREDUCE-Build/3100//console This message is automatically generated.
        Hide
        Radim Kolar added a comment -

        change it for old mapred api as well

        Show
        Radim Kolar added a comment - change it for old mapred api as well
        Hide
        Hadoop QA added a comment -

        -1 overall. Here are the results of testing the latest attachment
        http://issues.apache.org/jira/secure/attachment/12555191/betterhash1.txt
        against trunk revision .

        +1 @author. The patch does not contain any @author tags.

        -1 tests included. The patch doesn't appear to include any new or modified tests.
        Please justify why no new tests are needed for this patch.
        Also please list what manual steps were performed to verify this patch.

        -1 javac. The patch appears to cause the build to fail.

        Console output: https://builds.apache.org/job/PreCommit-MAPREDUCE-Build/3097//console

        This message is automatically generated.

        Show
        Hadoop QA added a comment - -1 overall . Here are the results of testing the latest attachment http://issues.apache.org/jira/secure/attachment/12555191/betterhash1.txt against trunk revision . +1 @author . The patch does not contain any @author tags. -1 tests included . The patch doesn't appear to include any new or modified tests. Please justify why no new tests are needed for this patch. Also please list what manual steps were performed to verify this patch. -1 javac . The patch appears to cause the build to fail. Console output: https://builds.apache.org/job/PreCommit-MAPREDUCE-Build/3097//console This message is automatically generated.
        Hide
        Radim Kolar added a comment -

        We can get another fast hash function from Knutt book if you are so paranoid.

        Thus the hash function is:

        h(k) = floor(m * (kA - floor(kA)))

        In this case, the value of m is not critical and we typically choose a power of 2 so that we can get the following efficient procedure on most digital computers:

        Choose m = 2p.
        Multiply the w bits of k by floor(A * 2w) to obtain a 2w bit product.
        Extract the p most significant bits of the lower half of this product.

        It seems that:

        A = (sqrt(5)-1)/2 = 0.6180339887

        is a good choice

        Knuth, "Sorting and Searching", v. 3 of "The Art of Computer Programming"

        Show
        Radim Kolar added a comment - We can get another fast hash function from Knutt book if you are so paranoid. Thus the hash function is: h(k) = floor(m * (kA - floor(kA))) In this case, the value of m is not critical and we typically choose a power of 2 so that we can get the following efficient procedure on most digital computers: Choose m = 2p. Multiply the w bits of k by floor(A * 2w) to obtain a 2w bit product. Extract the p most significant bits of the lower half of this product. It seems that: A = (sqrt(5)-1)/2 = 0.6180339887 is a good choice Knuth, "Sorting and Searching", v. 3 of "The Art of Computer Programming"
        Hide
        Steve Loughran added a comment -

        This looks good to me

        1. as doug says, this could be a regression, perhaps a BetterHashPartitioner is needed, or make this an option.
        2. we cannot put code from the JDK into the tree -or code that looks exactly like it, as we don't want another Oracle related lawsuit. That means we need to find some tangible reference -such as the page in Knuth, and we have to work it out from there by someone who hasn't looked at the HashMap code.
          This is being over cautious, but given Oracle sued google over a max function we have to show that diligence.
        Show
        Steve Loughran added a comment - This looks good to me as doug says, this could be a regression, perhaps a BetterHashPartitioner is needed, or make this an option. we cannot put code from the JDK into the tree -or code that looks exactly like it, as we don't want another Oracle related lawsuit. That means we need to find some tangible reference -such as the page in Knuth, and we have to work it out from there by someone who hasn't looked at the HashMap code. This is being over cautious, but given Oracle sued google over a max function we have to show that diligence.
        Hide
        Doug Cutting added a comment -

        > Most writables do not implement hashCode()

        All WritableComparable (i.e., key) implementations included with Hadoop implement hashCode(). Moreover a WritableComparable would be a poor key implementation if it did not implement hashCode() and was used with HashPartitioner since it wouldn't send equivalent values at the same reducer. The WritableComparable documentation specifically advises implementing hashCode().

        http://hadoop.apache.org/docs/current/api/org/apache/hadoop/io/WritableComparable.html

        Show
        Doug Cutting added a comment - > Most writables do not implement hashCode() All WritableComparable (i.e., key) implementations included with Hadoop implement hashCode(). Moreover a WritableComparable would be a poor key implementation if it did not implement hashCode() and was used with HashPartitioner since it wouldn't send equivalent values at the same reducer. The WritableComparable documentation specifically advises implementing hashCode(). http://hadoop.apache.org/docs/current/api/org/apache/hadoop/io/WritableComparable.html
        Hide
        Radim Kolar added a comment -

        this one is platform dependent and more or less random. Most writables do not implement hashCode()

        http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#hashCode%28%29

        Show
        Radim Kolar added a comment - this one is platform dependent and more or less random. Most writables do not implement hashCode() http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#hashCode%28%29
        Hide
        Doug Cutting added a comment -

        Integer#hashCode() is documented to be the integer value.

        http://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#hashCode()

        Similarly, the hashCode() implelementations for String, Double, Float, Long, etc. are specified and do not change from one JVM to another.

        Also, I didn't veto this change. I just observed that it was not back-compatible. That should be taken into account if/when it is committed.

        Show
        Doug Cutting added a comment - Integer#hashCode() is documented to be the integer value. http://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#hashCode( ) Similarly, the hashCode() implelementations for String, Double, Float, Long, etc. are specified and do not change from one JVM to another. Also, I didn't veto this change. I just observed that it was not back-compatible. That should be taken into account if/when it is committed.
        Hide
        Radim Kolar added a comment -

        If applications requires stable partitioning, then it needs to provide own partitioner because hashCode() for Object is not same across JVMs. No need to push backward compatibility that hard. I never seen such app and we have about 2 mils lines of mapred stuff.

        Show
        Radim Kolar added a comment - If applications requires stable partitioning, then it needs to provide own partitioner because hashCode() for Object is not same across JVMs. No need to push backward compatibility that hard. I never seen such app and we have about 2 mils lines of mapred stuff.
        Hide
        Doug Cutting added a comment -

        This is an incompatible change; it will change the output of jobs. In most cases this shouldn't matter, but there might be applications which expect, e.g., the key '1' to go to the output file numbered '1'. This could be avoided by, instead of modifying HashPartitioner, adding a new partitioner.

        Show
        Doug Cutting added a comment - This is an incompatible change; it will change the output of jobs. In most cases this shouldn't matter, but there might be applications which expect, e.g., the key '1' to go to the output file numbered '1'. This could be avoided by, instead of modifying HashPartitioner, adding a new partitioner.
        Hide
        Robert Joseph Evans added a comment -

        That is very interesting. I can see it in java.util.HashMap but it looks like java.util.Hashtable does not. Assuming that Jenkins comes back with a +1 I am OK with putting this in. I would like to have some numbers, because this is a "performance" improvement, but the citation of the code in HashMap.java, which is almost identical to this patch, is good enough for me. +1

        Show
        Robert Joseph Evans added a comment - That is very interesting. I can see it in java.util.HashMap but it looks like java.util.Hashtable does not. Assuming that Jenkins comes back with a +1 I am OK with putting this in. I would like to have some numbers, because this is a "performance" improvement, but the citation of the code in HashMap.java, which is almost identical to this patch, is good enough for me. +1
        Hide
        Radim Kolar added a comment -

        i have no numbers available

        Show
        Radim Kolar added a comment - i have no numbers available
        Hide
        Radim Kolar added a comment -

        its knutt formula commonly used in hashtables for improve hashing. java hashtable is using it too

        Show
        Radim Kolar added a comment - its knutt formula commonly used in hashtables for improve hashing. java hashtable is using it too
        Hide
        Robert Joseph Evans added a comment -

        I can see that there may be a need to improve the hashing of some poor quality implementations and the patch looks OK. I am not an expert on hash functions but from what I know it looks good. Do you have some concrete numbers that we can see how it improved the distribution in some specific cases?

        Show
        Robert Joseph Evans added a comment - I can see that there may be a need to improve the hashing of some poor quality implementations and the patch looks OK. I am not an expert on hash functions but from what I know it looks good. Do you have some concrete numbers that we can see how it improved the distribution in some specific cases?

          People

          • Assignee:
            Unassigned
            Reporter:
            Radim Kolar
          • Votes:
            0 Vote for this issue
            Watchers:
            14 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development