Details

    • Type: Improvement Improvement
    • Status: Resolved
    • Priority: Trivial Trivial
    • Resolution: Fixed
    • Fix Version/s: 1.2.0 beta 1
    • Component/s: Core
    • Labels:

      Description

      MurmurHash version 3 was finalized on June 3. It provides an enormous speedup and increased robustness over version 2, which is implemented in Cassandra. Information here:

      http://code.google.com/p/smhasher/

      The reference implementation is here:
      http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp?spec=svn136&r=136

      I have already done the work to port the (public domain) reference implementation to Java in the MurmurHash class and updated the BloomFilter class to use the new implementation:

      https://github.com/lindauer/cassandra/commit/cea6068a4a3e5d7d9509335394f9ef3350d37e93

      Apart from the faster hash time, the new version only requires one call to hash() rather than 2, since it returns 128 bits of hash instead of 64.

      1. 0001-Convert-BloomFilter-to-use-MurmurHash-v3-instead-of-.patch
        5 kB
        Brian Lindauer
      2. 0002-Backwards-compatibility-with-files-using-Murmur2-blo.patch
        28 kB
        Brian Lindauer
      3. Murmur3Benchmark.java
        8 kB
        David Allsopp
      4. 0001-CASSANDRA-2975.patch
        48 kB
        Vijay
      5. 0001-CASSANDRA-2975-v2.patch
        51 kB
        Vijay
      6. CASSANDRA-2975-v2-additions.patch
        1 kB
        Pavel Yaskevich

        Issue Links

          Activity

          Hide
          Pavel Yaskevich added a comment -

          Committed with cleaned white spaces and added license headers to the new files.

          Show
          Pavel Yaskevich added a comment - Committed with cleaned white spaces and added license headers to the new files.
          Hide
          Pavel Yaskevich added a comment -

          +1 with following nit - LazilyCompactedRowTest modifications are redundant and my additions patch which adds "clear()" method to the Filter class and fixes problem in the LongBloomFilterTest.

          Show
          Pavel Yaskevich added a comment - +1 with following nit - LazilyCompactedRowTest modifications are redundant and my additions patch which adds "clear()" method to the Filter class and fixes problem in the LongBloomFilterTest.
          Hide
          Vijay added a comment -

          Done! unit tests and functional tests works fine.

          Show
          Vijay added a comment - Done! unit tests and functional tests works fine.
          Hide
          Pavel Yaskevich added a comment -

          Vijay, can you please rebase?

          Show
          Pavel Yaskevich added a comment - Vijay, can you please rebase?
          Hide
          Jonathan Ellis added a comment -

          The latter. CASSANDRA-3772 is open to try a Murmur-based partitioner.

          Show
          Jonathan Ellis added a comment - The latter. CASSANDRA-3772 is open to try a Murmur-based partitioner.
          Hide
          Radim Kolar added a comment -

          This patch is for murmur partitioner also or it is just faster bloom filter?

          Show
          Radim Kolar added a comment - This patch is for murmur partitioner also or it is just faster bloom filter?
          Hide
          Vijay added a comment -

          updating the patch because old one missed the new files created.

          Show
          Vijay added a comment - updating the patch because old one missed the new files created.
          Hide
          Vijay added a comment -

          Attached is the refactor which includes fixes as per the suggestions. Added a factory to make adding newer hashesh easier but left the Legacy alone but it will be fairly trivial and more cleaner if we want to refactor a little more. Let me know thanks! Tests passed and the long test shows significant improvement Thanks Brian!

          Show
          Vijay added a comment - Attached is the refactor which includes fixes as per the suggestions. Added a factory to make adding newer hashesh easier but left the Legacy alone but it will be fairly trivial and more cleaner if we want to refactor a little more. Let me know thanks! Tests passed and the long test shows significant improvement Thanks Brian!
          Hide
          Brian Lindauer added a comment -

          Thanks, Vijay.

          Show
          Brian Lindauer added a comment - Thanks, Vijay.
          Hide
          Vijay added a comment -

          Will do

          Sent from my iPhone

          Show
          Vijay added a comment - Will do Sent from my iPhone
          Hide
          Jonathan Ellis added a comment -

          Vijay, would you mind picking this up by addressing Stu's feedback to Brian's patchset?

          Show
          Jonathan Ellis added a comment - Vijay, would you mind picking this up by addressing Stu's feedback to Brian's patchset?
          Hide
          David Allsopp added a comment -

          Have just repeated the benchmark with HeapByteBuffer as input rather than DirectByteBuffer (using ByteBuffer allocate() rather than allocateDirect()), and the performance improvement seems to almost vanish.

          The input to MurmurHash within Cassandra seems to be a HeapByteBuffer (based on adding a println to the existing MurmurHash2 hash64() method), so the inlining is probably of no benefit in practice.

          Show
          David Allsopp added a comment - Have just repeated the benchmark with HeapByteBuffer as input rather than DirectByteBuffer (using ByteBuffer allocate() rather than allocateDirect()), and the performance improvement seems to almost vanish. The input to MurmurHash within Cassandra seems to be a HeapByteBuffer (based on adding a println to the existing MurmurHash2 hash64() method), so the inlining is probably of no benefit in practice.
          Hide
          David Allsopp added a comment -

          The benchmark does several rounds of warmup for each iteration (i.e. for each buffer size from 1 to 32 bytes).

          It reduces the number of iterations as the input buffer size grows, so that each run processes a similar number of bytes - though this is probably irrelevant since the performance seems fairly constant with respect to buffer size.

          Running test for buffer lengths from 1 to 32
                   *|    Ratio: 0.96 for keylength 1 iterations=100000000
                   *|    Ratio: 0.95 for keylength 2 iterations=50000000
                   *|    Ratio: 0.95 for keylength 3 iterations=33333333
                   *|    Ratio: 0.96 for keylength 4 iterations=25000000
                   *|    Ratio: 0.94 for keylength 5 iterations=20000000
                   *|    Ratio: 0.94 for keylength 6 iterations=16666666
                   *|    Ratio: 0.96 for keylength 7 iterations=14285714
                   *|    Ratio: 0.93 for keylength 8 iterations=12500000
                  * |    Ratio: 0.89 for keylength 9 iterations=11111111
                   *|    Ratio: 0.93 for keylength 10 iterations=10000000
                   *|    Ratio: 0.95 for keylength 11 iterations=9090909
                   *|    Ratio: 0.95 for keylength 12 iterations=8333333
                   *|    Ratio: 0.93 for keylength 13 iterations=7692307
                   *|    Ratio: 0.90 for keylength 14 iterations=7142857
                   *|    Ratio: 0.95 for keylength 15 iterations=6666666
                  * |    Ratio: 0.86 for keylength 16 iterations=6250000
                  * |    Ratio: 0.87 for keylength 17 iterations=5882352
                   *|    Ratio: 0.91 for keylength 18 iterations=5555555
                  * |    Ratio: 0.83 for keylength 19 iterations=5263157
                  * |    Ratio: 0.83 for keylength 20 iterations=5000000
                  * |    Ratio: 0.80 for keylength 21 iterations=4761904
                  * |    Ratio: 0.88 for keylength 22 iterations=4545454
                   *|    Ratio: 0.91 for keylength 23 iterations=4347826
                   *|    Ratio: 0.91 for keylength 24 iterations=4166666
                  * |    Ratio: 0.88 for keylength 25 iterations=4000000
                   *|    Ratio: 0.92 for keylength 26 iterations=3846153
                  * |    Ratio: 0.85 for keylength 27 iterations=3703703
                  * |    Ratio: 0.88 for keylength 28 iterations=3571428
                  * |    Ratio: 0.88 for keylength 29 iterations=3448275
                  * |    Ratio: 0.89 for keylength 30 iterations=3333333
                   *|    Ratio: 0.92 for keylength 31 iterations=3225806
          --------
          Old (ms): 18938
          New (ms): 17470
          Overall ratio: 0.9224838948146583
          

          i.e. 8% improvement on average.

          Show
          David Allsopp added a comment - The benchmark does several rounds of warmup for each iteration (i.e. for each buffer size from 1 to 32 bytes). It reduces the number of iterations as the input buffer size grows, so that each run processes a similar number of bytes - though this is probably irrelevant since the performance seems fairly constant with respect to buffer size. Running test for buffer lengths from 1 to 32 *| Ratio: 0.96 for keylength 1 iterations=100000000 *| Ratio: 0.95 for keylength 2 iterations=50000000 *| Ratio: 0.95 for keylength 3 iterations=33333333 *| Ratio: 0.96 for keylength 4 iterations=25000000 *| Ratio: 0.94 for keylength 5 iterations=20000000 *| Ratio: 0.94 for keylength 6 iterations=16666666 *| Ratio: 0.96 for keylength 7 iterations=14285714 *| Ratio: 0.93 for keylength 8 iterations=12500000 * | Ratio: 0.89 for keylength 9 iterations=11111111 *| Ratio: 0.93 for keylength 10 iterations=10000000 *| Ratio: 0.95 for keylength 11 iterations=9090909 *| Ratio: 0.95 for keylength 12 iterations=8333333 *| Ratio: 0.93 for keylength 13 iterations=7692307 *| Ratio: 0.90 for keylength 14 iterations=7142857 *| Ratio: 0.95 for keylength 15 iterations=6666666 * | Ratio: 0.86 for keylength 16 iterations=6250000 * | Ratio: 0.87 for keylength 17 iterations=5882352 *| Ratio: 0.91 for keylength 18 iterations=5555555 * | Ratio: 0.83 for keylength 19 iterations=5263157 * | Ratio: 0.83 for keylength 20 iterations=5000000 * | Ratio: 0.80 for keylength 21 iterations=4761904 * | Ratio: 0.88 for keylength 22 iterations=4545454 *| Ratio: 0.91 for keylength 23 iterations=4347826 *| Ratio: 0.91 for keylength 24 iterations=4166666 * | Ratio: 0.88 for keylength 25 iterations=4000000 *| Ratio: 0.92 for keylength 26 iterations=3846153 * | Ratio: 0.85 for keylength 27 iterations=3703703 * | Ratio: 0.88 for keylength 28 iterations=3571428 * | Ratio: 0.88 for keylength 29 iterations=3448275 * | Ratio: 0.89 for keylength 30 iterations=3333333 *| Ratio: 0.92 for keylength 31 iterations=3225806 -------- Old (ms): 18938 New (ms): 17470 Overall ratio: 0.9224838948146583 i.e. 8% improvement on average.
          Hide
          David Allsopp added a comment -

          It appears not! Benchmark is attached so folks can try it on other hardware (no point if the advantage is specific to my particular machine!) Will post my results below:

          Show
          David Allsopp added a comment - It appears not! Benchmark is attached so folks can try it on other hardware (no point if the advantage is specific to my particular machine!) Will post my results below:
          Hide
          Jonathan Ellis added a comment -

          Really, JIT doesn't inline the rot164? Did you "warm up" the JVM before timing things? http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java

          Show
          Jonathan Ellis added a comment - Really, JIT doesn't inline the rot164? Did you "warm up" the JVM before timing things? http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java
          Hide
          David Allsopp added a comment -

          I really must learn not to post stuff late at night . The "optimisation" of the switch-case breaks the algorithm because it relies on the fall-through behaviour of switch-case in C and Java. Oh well. The inlining only speeds things up a few percent, but might be worthwhile if others see the same improvement on other hardware.

          Show
          David Allsopp added a comment - I really must learn not to post stuff late at night . The "optimisation" of the switch-case breaks the algorithm because it relies on the fall-through behaviour of switch-case in C and Java. Oh well. The inlining only speeds things up a few percent, but might be worthwhile if others see the same improvement on other hardware.
          Hide
          Radim Kolar added a comment -

          Our typical key size is under 20 bytes.

          Show
          Radim Kolar added a comment - Our typical key size is under 20 bytes.
          Hide
          David Allsopp added a comment - - edited

          Does anyone have any data on what the typical key size is (i.e. the average input size for the hash)?

          I have a couple of optimisations for the MurmurHash3 implementation that I think give another 10-40% speedup, particularly for smaller values (e.g. 30% speedup for buffer lengths under 256 bytes) and no worse for large values (tens of KB). These results were on a AMD Phenom II X6 1055T @ 2.80 GHz, under 64-bit Windows 7, Java 1.6.0_27.

          Firstly, inline the rotl64 calls , e.g. so that

          k1 = rotl64(k1, 31);
          

          becomes

          k1 = (k1 << 31) | (k1 >>> 33);
          

          Secondly, rather than a large switch-case to handle the 'tail', use nested if-else to form a simple binary search. Particularly for relatively small inputs, handling the 'tail' is a significant part of the computation. E.g:

          int ln = length & 15;
          if (ln > 8)
            {
               if (ln > 12)
                 {
                    // etc for cases 13 - 15
                 }
               else
                 {
                    // cases 11 and 12
                 }
          
            }
          else
            {
               // etc for cases 1-7
            }
          

          Will try to post a proper benchmark when I've tidied it up (run out of time today!) so anyone interested can try it on other hardware...

          This latter optimisation is pretty verbose and ugly to look at - it might be just as fast, and much more concise, to lookup the offsets and shifts from an array, and deal with the special cases 1 and 9 as, well, special cases - but haven't benchmarked this alternative yet...

          Show
          David Allsopp added a comment - - edited Does anyone have any data on what the typical key size is (i.e. the average input size for the hash)? I have a couple of optimisations for the MurmurHash3 implementation that I think give another 10-40% speedup, particularly for smaller values (e.g. 30% speedup for buffer lengths under 256 bytes) and no worse for large values (tens of KB). These results were on a AMD Phenom II X6 1055T @ 2.80 GHz, under 64-bit Windows 7, Java 1.6.0_27. Firstly, inline the rotl64 calls , e.g. so that k1 = rotl64(k1, 31); becomes k1 = (k1 << 31) | (k1 >>> 33); Secondly, rather than a large switch-case to handle the 'tail', use nested if-else to form a simple binary search. Particularly for relatively small inputs, handling the 'tail' is a significant part of the computation. E.g: int ln = length & 15; if (ln > 8) { if (ln > 12) { // etc for cases 13 - 15 } else { // cases 11 and 12 } } else { // etc for cases 1-7 } Will try to post a proper benchmark when I've tidied it up (run out of time today!) so anyone interested can try it on other hardware... This latter optimisation is pretty verbose and ugly to look at - it might be just as fast, and much more concise, to lookup the offsets and shifts from an array, and deal with the special cases 1 and 9 as, well, special cases - but haven't benchmarked this alternative yet...
          Hide
          David Allsopp added a comment -

          In the attached patch, in MurmurHash.hash3_x64_128(), in the main loop:

                  for(int i = 0; i < nblocks; i++)
                  {
                      int i_8 = i << 4;
                  ...
          

          i_8 is assigned but not used, as far as I can see?

          Show
          David Allsopp added a comment - In the attached patch, in MurmurHash.hash3_x64_128(), in the main loop: for(int i = 0; i < nblocks; i++) { int i_8 = i << 4; ... i_8 is assigned but not used, as far as I can see?
          Hide
          Brian Lindauer added a comment -

          No, sorry. I'll try to get to Stu's requests soon.

          Show
          Brian Lindauer added a comment - No, sorry. I'll try to get to Stu's requests soon.
          Hide
          Victor Z. Peng added a comment -

          Has this fix been finalized?

          Show
          Victor Z. Peng added a comment - Has this fix been finalized?
          Hide
          Stu Hood added a comment -
          • sstable.Descriptor
            • Add a description for the version 'i' bump
            • Could you rename "usesOldBloomFilter" to "uses32BitBloomFilter"? I know you didn't add it, but with 3 filter-related bools, it's time to get more descriptive
          • sstable.IndexHelper
            • Rather than 2 booleans being passed to defreezeBloomFilter, maybe just pass the Descriptor
          • sstable.SSTableReader
            • In .loadBloomFilter(), could the .uses*BloomFilter checks move into a factory function on one of the bloom filter classes, or in a deserializer?

          Other than those nits, this looks great: thanks Brian!

          (the committer for this patch should probably generate a new legacy-sstables entry for version 'h': see LegacySSTableTest)

          Show
          Stu Hood added a comment - sstable.Descriptor Add a description for the version 'i' bump Could you rename "usesOldBloomFilter" to "uses32BitBloomFilter"? I know you didn't add it, but with 3 filter-related bools, it's time to get more descriptive sstable.IndexHelper Rather than 2 booleans being passed to defreezeBloomFilter, maybe just pass the Descriptor sstable.SSTableReader In .loadBloomFilter(), could the .uses*BloomFilter checks move into a factory function on one of the bloom filter classes, or in a deserializer? Other than those nits, this looks great: thanks Brian! (the committer for this patch should probably generate a new legacy-sstables entry for version 'h': see LegacySSTableTest)
          Hide
          Brian Lindauer added a comment -

          Murmur3->Murmur2 backwards compatibility

          Show
          Brian Lindauer added a comment - Murmur3->Murmur2 backwards compatibility
          Hide
          Brian Lindauer added a comment -

          Murmur3 changes

          Show
          Brian Lindauer added a comment - Murmur3 changes
          Hide
          Pavel Yaskevich added a comment -

          First of all - can you please rebase both with latest trunk and attach them to JIRA?

          What I see from first look (about patch for backward compatibility):

          • I think we should extract interface from BloomFilter class and make BF a factory as now we have Murmur {2,3}

            BloomFilter classes

          • Needs a test for compatibility with old SSTables (which are using Murmur2BF)
          • minor note: comment about new SSTable version is missing at the top of the Descriptor class

          As soon as you attach files in here I will apply and play with them and maybe find other problems.

          Show
          Pavel Yaskevich added a comment - First of all - can you please rebase both with latest trunk and attach them to JIRA? What I see from first look (about patch for backward compatibility): I think we should extract interface from BloomFilter class and make BF a factory as now we have Murmur {2,3} BloomFilter classes Needs a test for compatibility with old SSTables (which are using Murmur2BF) minor note: comment about new SSTable version is missing at the top of the Descriptor class As soon as you attach files in here I will apply and play with them and maybe find other problems.
          Hide
          Jonathan Ellis added a comment -

          Stu said he could review this since they're particularly interested in bloom filter performance.

          Show
          Jonathan Ellis added a comment - Stu said he could review this since they're particularly interested in bloom filter performance.
          Hide
          Brian Lindauer added a comment -

          You weren't kidding about compatibility with old data files not being simple. It actually turned out to be fairly major surgery. The original changes just to support Mumur3 are here:

          https://github.com/lindauer/cassandra/commit/cea6068a4a3e5d7d9509335394f9ef3350d37e93

          The additional proposed changes to support backward compatibility are at:

          https://github.com/lindauer/cassandra/commit/9d7479675752a07732f434b307be6642d8b3e85f

          I can't say I'm completely satisfied with these changes. It feels like we should unify with LegacyBloomFilter now that there are 3 versions. It also feels like all of the places where a serializer is selected based on a Descriptor version/flag could be moved under one roof, where callers just pass the Descriptor and it returns the correct serializer instance. But, not being too familiar with Cassandra, I was trying to be minimally invasive for fear of breaking something.

          All of the tests pass, but I haven't added any tests, such as making sure that old files can still be read in. Like I said, I'm not very familiar with Cassandra, so you should review these changes carefully. (I'm sure you would anyway.)

          Show
          Brian Lindauer added a comment - You weren't kidding about compatibility with old data files not being simple. It actually turned out to be fairly major surgery. The original changes just to support Mumur3 are here: https://github.com/lindauer/cassandra/commit/cea6068a4a3e5d7d9509335394f9ef3350d37e93 The additional proposed changes to support backward compatibility are at: https://github.com/lindauer/cassandra/commit/9d7479675752a07732f434b307be6642d8b3e85f I can't say I'm completely satisfied with these changes. It feels like we should unify with LegacyBloomFilter now that there are 3 versions. It also feels like all of the places where a serializer is selected based on a Descriptor version/flag could be moved under one roof, where callers just pass the Descriptor and it returns the correct serializer instance. But, not being too familiar with Cassandra, I was trying to be minimally invasive for fear of breaking something. All of the tests pass, but I haven't added any tests, such as making sure that old files can still be read in. Like I said, I'm not very familiar with Cassandra, so you should review these changes carefully. (I'm sure you would anyway.)
          Hide
          Brian Lindauer added a comment -

          Summary:

          Mean FP rates for version 2:
          LongBloomFilterTest: 0.997967059178744
          LongLegacyBloomFilterTest: 0.997908061594203
          
          Mean FP rates for version 3:
          LongBloomFilterTest: 0.998045621980676
          LongLegacyBloomFilterTest: 0.998863888888889
          

          Details:

          Version 2:
               [echo] running long tests
              [junit] WARNING: multiple versions of ant detected in path for junit 
              [junit]          jar:file:/usr/share/ant/lib/ant.jar!/org/apache/tools/ant/Project.class
              [junit]      and jar:file:/Users/jbl/git/cassandra/build/lib/jars/ant-1.6.5.jar!/org/apache/tools/ant/Project.class
              [junit] Testsuite: org.apache.cassandra.utils.LongBloomFilterTest
              [junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 106.213 sec
              [junit] 
              [junit] ------------- Standard Error -----------------
              [junit] fp_ratio = 0.9973043478260869
              [junit] fp_ratio = 0.9965793478260869
              [junit] fp_ratio = 0.9996123188405797
              [junit] fp_ratio = 1.0004746376811595
              [junit] fp_ratio = 0.998409420289855
              [junit] fp_ratio = 0.9920978260869565
              [junit] fp_ratio = 0.9979420289855072
              [junit] fp_ratio = 0.9940797101449276
              [junit] fp_ratio = 0.9983913043478261
              [junit] fp_ratio = 1.0006159420289855
              [junit] fp_ratio = 1.0000362318840579
              [junit] fp_ratio = 1.0000615942028985
              [junit] ------------- ---------------- ---------------
          mean = 0.997967059178744
          
              [junit] Testsuite: org.apache.cassandra.utils.LongLegacyBloomFilterTest
              [junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 61.721 sec
              [junit] 
              [junit] ------------- Standard Error -----------------
              [junit] fp_ratio = 0.998095652173913
              [junit] fp_ratio = 0.9982576086956522
              [junit] fp_ratio = 0.999159420289855
              [junit] fp_ratio = 1.0001340579710145
              [junit] fp_ratio = 1.0011557971014493
              [junit] fp_ratio = 0.9967717391304348
              [junit] fp_ratio = 0.9955978260869566
              [junit] fp_ratio = 0.9989673913043479
              [junit] fp_ratio = 0.9966231884057971
              [junit] fp_ratio = 0.9973514492753623
              [junit] fp_ratio = 0.9969855072463768
              [junit] fp_ratio = 0.9957971014492754
              [junit] ------------- ---------------- ---------------
          mean      = 0.997908061594203
          
          
          Version 3:
               [echo] running long tests
              [junit] WARNING: multiple versions of ant detected in path for junit 
              [junit]          jar:file:/usr/share/ant/lib/ant.jar!/org/apache/tools/ant/Project.class
              [junit]      and jar:file:/Users/jbl/git/cassandra/build/lib/jars/ant-1.6.5.jar!/org/apache/tools/ant/Project.class
              [junit] Testsuite: org.apache.cassandra.utils.LongBloomFilterTest
              [junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 75.994 sec
              [junit] 
              [junit] ------------- Standard Error -----------------
              [junit] fp_ratio = 0.9986532608695652
              [junit] fp_ratio = 0.997158695652174
              [junit] fp_ratio = 0.9995797101449275
              [junit] fp_ratio = 0.9995
              [junit] fp_ratio = 0.9984565217391305
              [junit] fp_ratio = 0.9987101449275362
              [junit] fp_ratio = 0.9979528985507247
              [junit] fp_ratio = 0.9998224637681159
              [junit] fp_ratio = 0.9938876811594203
              [junit] fp_ratio = 0.9993623188405797
              [junit] fp_ratio = 0.9953369565217391
              [junit] fp_ratio = 0.9981268115942029
              [junit] ------------- ---------------- ---------------
          mean      = 0.998045621980676
          
              [junit] Testsuite: org.apache.cassandra.utils.LongLegacyBloomFilterTest
              [junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 60.999 sec
              [junit] 
              [junit] ------------- Standard Error -----------------
              [junit] fp_ratio = 0.998095652173913
              [junit] fp_ratio = 0.9983760869565217
              [junit] fp_ratio = 0.9993043478260869
              [junit] fp_ratio = 0.9996159420289855
              [junit] fp_ratio = 0.9980217391304348
              [junit] fp_ratio = 1.0016920289855074
              [junit] fp_ratio = 0.9953623188405797
              [junit] fp_ratio = 0.9968188405797102
              [junit] fp_ratio = 0.9947173913043478
              [junit] fp_ratio = 1.000695652173913
              [junit] fp_ratio = 1.0030760869565218
              [junit] fp_ratio = 1.0005905797101449
              [junit] ------------- ---------------- ---------------
          mean      = 0.998863888888889
          
          Show
          Brian Lindauer added a comment - Summary: Mean FP rates for version 2: LongBloomFilterTest: 0.997967059178744 LongLegacyBloomFilterTest: 0.997908061594203 Mean FP rates for version 3: LongBloomFilterTest: 0.998045621980676 LongLegacyBloomFilterTest: 0.998863888888889 Details: Version 2: [echo] running long tests [junit] WARNING: multiple versions of ant detected in path for junit [junit] jar:file:/usr/share/ant/lib/ant.jar!/org/apache/tools/ant/Project.class [junit] and jar:file:/Users/jbl/git/cassandra/build/lib/jars/ant-1.6.5.jar!/org/apache/tools/ant/Project.class [junit] Testsuite: org.apache.cassandra.utils.LongBloomFilterTest [junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 106.213 sec [junit] [junit] ------------- Standard Error ----------------- [junit] fp_ratio = 0.9973043478260869 [junit] fp_ratio = 0.9965793478260869 [junit] fp_ratio = 0.9996123188405797 [junit] fp_ratio = 1.0004746376811595 [junit] fp_ratio = 0.998409420289855 [junit] fp_ratio = 0.9920978260869565 [junit] fp_ratio = 0.9979420289855072 [junit] fp_ratio = 0.9940797101449276 [junit] fp_ratio = 0.9983913043478261 [junit] fp_ratio = 1.0006159420289855 [junit] fp_ratio = 1.0000362318840579 [junit] fp_ratio = 1.0000615942028985 [junit] ------------- ---------------- --------------- mean = 0.997967059178744 [junit] Testsuite: org.apache.cassandra.utils.LongLegacyBloomFilterTest [junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 61.721 sec [junit] [junit] ------------- Standard Error ----------------- [junit] fp_ratio = 0.998095652173913 [junit] fp_ratio = 0.9982576086956522 [junit] fp_ratio = 0.999159420289855 [junit] fp_ratio = 1.0001340579710145 [junit] fp_ratio = 1.0011557971014493 [junit] fp_ratio = 0.9967717391304348 [junit] fp_ratio = 0.9955978260869566 [junit] fp_ratio = 0.9989673913043479 [junit] fp_ratio = 0.9966231884057971 [junit] fp_ratio = 0.9973514492753623 [junit] fp_ratio = 0.9969855072463768 [junit] fp_ratio = 0.9957971014492754 [junit] ------------- ---------------- --------------- mean = 0.997908061594203 Version 3: [echo] running long tests [junit] WARNING: multiple versions of ant detected in path for junit [junit] jar:file:/usr/share/ant/lib/ant.jar!/org/apache/tools/ant/Project.class [junit] and jar:file:/Users/jbl/git/cassandra/build/lib/jars/ant-1.6.5.jar!/org/apache/tools/ant/Project.class [junit] Testsuite: org.apache.cassandra.utils.LongBloomFilterTest [junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 75.994 sec [junit] [junit] ------------- Standard Error ----------------- [junit] fp_ratio = 0.9986532608695652 [junit] fp_ratio = 0.997158695652174 [junit] fp_ratio = 0.9995797101449275 [junit] fp_ratio = 0.9995 [junit] fp_ratio = 0.9984565217391305 [junit] fp_ratio = 0.9987101449275362 [junit] fp_ratio = 0.9979528985507247 [junit] fp_ratio = 0.9998224637681159 [junit] fp_ratio = 0.9938876811594203 [junit] fp_ratio = 0.9993623188405797 [junit] fp_ratio = 0.9953369565217391 [junit] fp_ratio = 0.9981268115942029 [junit] ------------- ---------------- --------------- mean = 0.998045621980676 [junit] Testsuite: org.apache.cassandra.utils.LongLegacyBloomFilterTest [junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 60.999 sec [junit] [junit] ------------- Standard Error ----------------- [junit] fp_ratio = 0.998095652173913 [junit] fp_ratio = 0.9983760869565217 [junit] fp_ratio = 0.9993043478260869 [junit] fp_ratio = 0.9996159420289855 [junit] fp_ratio = 0.9980217391304348 [junit] fp_ratio = 1.0016920289855074 [junit] fp_ratio = 0.9953623188405797 [junit] fp_ratio = 0.9968188405797102 [junit] fp_ratio = 0.9947173913043478 [junit] fp_ratio = 1.000695652173913 [junit] fp_ratio = 1.0030760869565218 [junit] fp_ratio = 1.0005905797101449 [junit] ------------- ---------------- --------------- mean = 0.998863888888889
          Hide
          Jonathan Ellis added a comment -

          Can you dig a little deeper and compare actual FP rates?

          logging/printing fpratio before

                  assert fp_ratio < 1.03 : fp_ratio;
          

          should be fine.

          Show
          Jonathan Ellis added a comment - Can you dig a little deeper and compare actual FP rates? logging/printing fpratio before assert fp_ratio < 1.03 : fp_ratio; should be fine.
          Hide
          Brian Lindauer added a comment -

          The test didn't seem to produce any errors:

          [junit] Testsuite: org.apache.cassandra.utils.LongBloomFilterTest
          [junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 75.354 sec
          [junit] 
          [junit] Testsuite: org.apache.cassandra.utils.LongLegacyBloomFilterTest
          [junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 76.545 sec
          

          I'll have to familiarize myself more with Cassandra before dealing with the other issue you pointed out. I've just been using the BloomFilter class and only have a very general understanding of the overall system.

          Show
          Brian Lindauer added a comment - The test didn't seem to produce any errors: [junit] Testsuite: org.apache.cassandra.utils.LongBloomFilterTest [junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 75.354 sec [junit] [junit] Testsuite: org.apache.cassandra.utils.LongLegacyBloomFilterTest [junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 76.545 sec I'll have to familiarize myself more with Cassandra before dealing with the other issue you pointed out. I've just been using the BloomFilter class and only have a very general understanding of the overall system.
          Hide
          Jonathan Ellis added a comment -

          Also, it's not quite as simple as ripping out M2 and replacing with M3 – we need to continue to support M2 for compatibility with old data files. Look at uses of Descriptor.hasStringsInBloomFilter for a similar change.

          Show
          Jonathan Ellis added a comment - Also, it's not quite as simple as ripping out M2 and replacing with M3 – we need to continue to support M2 for compatibility with old data files. Look at uses of Descriptor.hasStringsInBloomFilter for a similar change.
          Hide
          Jonathan Ellis added a comment -

          Interesting. Sounds like a free lunch.

          Besides speed, we'd need to make sure Murmur3 gives us as good a hash distribution as Murmur2, so our bloom filter false positive rate doesn't go up – see BloomFilterTest, which runs with "ant long-test".

          Show
          Jonathan Ellis added a comment - Interesting. Sounds like a free lunch. Besides speed, we'd need to make sure Murmur3 gives us as good a hash distribution as Murmur2, so our bloom filter false positive rate doesn't go up – see BloomFilterTest, which runs with "ant long-test".
          Hide
          Brian Lindauer added a comment -

          Surprising, but yes. It's dramatically faster. The MurmurHash author reports a 50% speedup over v2 at http://code.google.com/p/smhasher/wiki/MurmurHash3. I ran my own simple benchmark on the Java version comparing the existing MurmurHash.hash64() function to the MurmurHash.hash3_x64_128() I added and found an even larger advantage. The improvement is so huge that I wonder a little bit if there isn't a flaw in my test, but here it is:

          start = System.currentTimeMillis();
          long[] reta = {0, 0};
          ByteBuffer buf = strToByteBuffer(key);
          for (int i=0; i<cnt; i++)
          {
            buf.clear();
            reta = MurmurHash.hash3_x64_128(buf, 0, key.length(), (int) reta[0]);
          }
          end = System.currentTimeMillis();
          System.err.println("Ran v3 " + cnt + " times in " + (end - start) + " ms.");
          

          Similarly for v2.

          Output:

          Ran v2 100000000 times in 19993 ms.
          Ran v3 100000000 times in 3104 ms.
          

          FWIW, I also ran some tests where I generated random strings and seeds and submitted them to both the reference implementation and the Java port and found no differences.

          Show
          Brian Lindauer added a comment - Surprising, but yes. It's dramatically faster. The MurmurHash author reports a 50% speedup over v2 at http://code.google.com/p/smhasher/wiki/MurmurHash3 . I ran my own simple benchmark on the Java version comparing the existing MurmurHash.hash64() function to the MurmurHash.hash3_x64_128() I added and found an even larger advantage. The improvement is so huge that I wonder a little bit if there isn't a flaw in my test, but here it is: start = System .currentTimeMillis(); long [] reta = {0, 0}; ByteBuffer buf = strToByteBuffer(key); for ( int i=0; i<cnt; i++) { buf.clear(); reta = MurmurHash.hash3_x64_128(buf, 0, key.length(), ( int ) reta[0]); } end = System .currentTimeMillis(); System .err.println( "Ran v3 " + cnt + " times in " + (end - start) + " ms." ); Similarly for v2. Output: Ran v2 100000000 times in 19993 ms. Ran v3 100000000 times in 3104 ms. FWIW, I also ran some tests where I generated random strings and seeds and submitted them to both the reference implementation and the Java port and found no differences.
          Hide
          Jonathan Ellis added a comment -

          So v3 is faster to compute a 128bit hash, than v2 is to compute a 64bit one?

          Show
          Jonathan Ellis added a comment - So v3 is faster to compute a 128bit hash, than v2 is to compute a 64bit one?

            People

            • Assignee:
              Vijay
              Reporter:
              Brian Lindauer
              Reviewer:
              Pavel Yaskevich
            • Votes:
              2 Vote for this issue
              Watchers:
              7 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development