Details

    • Type: Improvement Improvement
    • Status: Resolved
    • Priority: Major Major
    • Resolution: Fixed
    • Fix Version/s: 2.0.1
    • Component/s: Core
    • Labels:
      None

      Description

      Adler is significantly faster than CRC32: http://java-performance.info/java-crc32-and-adler32/

      (Adler is weaker for short inputs, so we should leave the commitlog alone, as it checksums each mutation individually.)

      1. 5862.txt
        13 kB
        T Jake Luciani

        Issue Links

          Activity

          Jonathan Ellis created issue -
          Hide
          T Jake Luciani added a comment -

          I have been working on a jni library to allow fast CRC checks using the newest SSE instruction set. this is what Hadoop and Impala are now using. I'll do some micro benchmarks of adler32 to this approach and see if it's worth it. The benefit of a fast CRC is the code could be used on commit log and thereby speed up writes as well.

          Show
          T Jake Luciani added a comment - I have been working on a jni library to allow fast CRC checks using the newest SSE instruction set. this is what Hadoop and Impala are now using. I'll do some micro benchmarks of adler32 to this approach and see if it's worth it. The benefit of a fast CRC is the code could be used on commit log and thereby speed up writes as well.
          Hide
          Radim Kolar added a comment -

          Adler is unreliable, i had bad experience with it, switched from crc32 to adler for a while. Use CRC32C.

          Show
          Radim Kolar added a comment - Adler is unreliable, i had bad experience with it, switched from crc32 to adler for a while. Use CRC32C.
          Hide
          T Jake Luciani added a comment -

          Looks like Adler32 wins!

          benchmark:
               [java]  0% Scenario{vm=java, trial=0, benchmark=JavaCrc32} 58541.04 ns; σ=334.60 ns @ 3 trials
               [java] 33% Scenario{vm=java, trial=0, benchmark=SSECrc32} 15504.47 ns; σ=46.66 ns @ 3 trials
               [java] 67% Scenario{vm=java, trial=0, benchmark=JavaAdler32} 6610.37 ns; σ=232.76 ns @ 10 trials
               [java]
               [java]   benchmark    us linear runtime
               [java]   JavaCrc32 58.54 ==============================
               [java]    SSECrc32 15.50 =======
               [java] JavaAdler32  6.61 ===
               [java]
               [java] vm: java
               [java] trial: 0
          
          Show
          T Jake Luciani added a comment - Looks like Adler32 wins! benchmark: [java] 0% Scenario{vm=java, trial=0, benchmark=JavaCrc32} 58541.04 ns; σ=334.60 ns @ 3 trials [java] 33% Scenario{vm=java, trial=0, benchmark=SSECrc32} 15504.47 ns; σ=46.66 ns @ 3 trials [java] 67% Scenario{vm=java, trial=0, benchmark=JavaAdler32} 6610.37 ns; σ=232.76 ns @ 10 trials [java] [java] benchmark us linear runtime [java] JavaCrc32 58.54 ============================== [java] SSECrc32 15.50 ======= [java] JavaAdler32 6.61 === [java] [java] vm: java [java] trial: 0
          Hide
          T Jake Luciani added a comment -

          Radim Kolar do you have any details? what size was the payload you were checksumming?

          Show
          T Jake Luciani added a comment - Radim Kolar do you have any details? what size was the payload you were checksumming?
          Hide
          Lior Golan added a comment -

          Are you computing the checksum on the data before or after compression? If you are computing the checksum of the uncompressed data, then it might be useful to switch to checksum the compressed data (less data to checksum)

          Show
          Lior Golan added a comment - Are you computing the checksum on the data before or after compression? If you are computing the checksum of the uncompressed data, then it might be useful to switch to checksum the compressed data (less data to checksum)
          Hide
          Radim Kolar added a comment -

          60-80 bytes

          Show
          Radim Kolar added a comment - 60-80 bytes
          Hide
          T Jake Luciani added a comment -

          Radim Kolar ah ok, well as Jonathan Ellis mentioned it's a poor choice for small values. Compression chunks are a much larger value (default of 64kb)

          Lior Golan good point, we do checksum the uncompressed data, but since adler32 is bad with small values we should prob keep it as is.

          Show
          T Jake Luciani added a comment - Radim Kolar ah ok, well as Jonathan Ellis mentioned it's a poor choice for small values. Compression chunks are a much larger value (default of 64kb) Lior Golan good point, we do checksum the uncompressed data, but since adler32 is bad with small values we should prob keep it as is.
          Hide
          Jonathan Ellis added a comment -

          we do checksum the uncompressed data, but since adler32 is bad with small values we should prob keep it as is

          Even with 10x compression (2x as high as I've actually seen) that's still thousands of bytes to work with. I think we'd be okay.

          Show
          Jonathan Ellis added a comment - we do checksum the uncompressed data, but since adler32 is bad with small values we should prob keep it as is Even with 10x compression (2x as high as I've actually seen) that's still thousands of bytes to work with. I think we'd be okay.
          Hide
          Lior Golan added a comment -

          What's the typical size of a compressed chunk (after compression)? If it's above a few 100 bytes then Adler should be ok. In addition, compressed data has higher entropy which improves the quality of the adler32 checksum

          Show
          Lior Golan added a comment - What's the typical size of a compressed chunk (after compression)? If it's above a few 100 bytes then Adler should be ok. In addition, compressed data has higher entropy which improves the quality of the adler32 checksum
          Hide
          T Jake Luciani added a comment -

          Patch attached, I switched to adler32 and changed checksumming to be on the compressed value. Going to run some benchmarks now.

          Show
          T Jake Luciani added a comment - Patch attached, I switched to adler32 and changed checksumming to be on the compressed value. Going to run some benchmarks now.
          T Jake Luciani made changes -
          Field Original Value New Value
          Attachment 5862.txt [ 12596924 ]
          T Jake Luciani made changes -
          Status Open [ 1 ] Patch Available [ 10002 ]
          Hide
          Radim Kolar added a comment -

          Today all new projects should use CRC32C, it can be done in cpu hardware SSE4 and polynomial is improved from crc32.

          In my test notes Adler32 has 5 times higher collision rate then CRC32, CRC32C is better then CRC32 but very little.

          Show
          Radim Kolar added a comment - Today all new projects should use CRC32C, it can be done in cpu hardware SSE4 and polynomial is improved from crc32. In my test notes Adler32 has 5 times higher collision rate then CRC32, CRC32C is better then CRC32 but very little.
          Hide
          Jonathan Ellis added a comment -

          Radim: hardware CRC32C is exactly what Jake tested above.

          Jake: the dual checksum fields in CRAR are a bit clunky; the approach of instantiating the correct one in the constructor that you use in CIS is cleaner.

          Nit: if we can come up with a single name to represent "adler and post-compression" then I'd prefer that to passing two booleans around that are always the same value.

          Otherwise LGTM.

          Show
          Jonathan Ellis added a comment - Radim: hardware CRC32C is exactly what Jake tested above. Jake: the dual checksum fields in CRAR are a bit clunky; the approach of instantiating the correct one in the constructor that you use in CIS is cleaner. Nit: if we can come up with a single name to represent "adler and post-compression" then I'd prefer that to passing two booleans around that are always the same value. Otherwise LGTM.
          Hide
          T Jake Luciani added a comment -

          with current crc32

          verages from the middle 80% of values:
          interval_op_rate          : 14556
          interval_key_rate         : 14556
          latency median            : 2.7
          latency 95th percentile   : 4.7
          latency 99.9th percentile : 37.0
          Total operation time      : 00:01:15
          END
          

          with adler32

          Averages from the middle 80% of values:
          interval_op_rate          : 17985
          interval_key_rate         : 17985
          latency median            : 2.0
          latency 95th percentile   : 3.9
          latency 99.9th percentile : 73.7
          Total operation time      : 00:01:02
          END
          
          Show
          T Jake Luciani added a comment - with current crc32 verages from the middle 80% of values: interval_op_rate : 14556 interval_key_rate : 14556 latency median : 2.7 latency 95th percentile : 4.7 latency 99.9th percentile : 37.0 Total operation time : 00:01:15 END with adler32 Averages from the middle 80% of values: interval_op_rate : 17985 interval_key_rate : 17985 latency median : 2.0 latency 95th percentile : 3.9 latency 99.9th percentile : 73.7 Total operation time : 00:01:02 END
          Hide
          T Jake Luciani added a comment - - edited

          the dual checksum fields in CRAR are a bit clunky; the approach of instantiating the correct one in the constructor that you use in CIS is cleaner.

          My concern was the instance would be re-used across multiple sstables therefore should be chosen per buffer. Is that not the case?

          Show
          T Jake Luciani added a comment - - edited the dual checksum fields in CRAR are a bit clunky; the approach of instantiating the correct one in the constructor that you use in CIS is cleaner. My concern was the instance would be re-used across multiple sstables therefore should be chosen per buffer. Is that not the case?
          Hide
          T Jake Luciani added a comment -

          if we can come up with a single name to represent "adler and post-compression" then I'd prefer

          I was trying to future proof us switching back to crc or something but not changing the post-compression. Think its safe to merge?

          Show
          T Jake Luciani added a comment - if we can come up with a single name to represent "adler and post-compression" then I'd prefer I was trying to future proof us switching back to crc or something but not changing the post-compression. Think its safe to merge?
          Hide
          Jonathan Ellis added a comment -

          My concern was the instance would be re-used across multiple sstables therefore should be chosen per buffer. Is that not the case?

          CRAR is always tied to a single SSTable.

          I was trying to future proof us switching back to crc or something but not changing the post-compression. Think its safe to merge?

          Yeah, if we do that we'll end up adding new version tests anyway. I think YAGNI applies.

          Show
          Jonathan Ellis added a comment - My concern was the instance would be re-used across multiple sstables therefore should be chosen per buffer. Is that not the case? CRAR is always tied to a single SSTable. I was trying to future proof us switching back to crc or something but not changing the post-compression. Think its safe to merge? Yeah, if we do that we'll end up adding new version tests anyway. I think YAGNI applies.
          Brandon Williams made changes -
          Tester alexzar
          Hide
          T Jake Luciani added a comment - - edited

          committed with suggested changes

          Show
          T Jake Luciani added a comment - - edited committed with suggested changes
          T Jake Luciani made changes -
          Status Patch Available [ 10002 ] Resolved [ 5 ]
          Resolution Fixed [ 1 ]
          Hide
          Adrien Grand added a comment -

          I just learned about this issue and was wondering if you had considered XXHash (http://code.google.com/p/xxhash/) for checksuming. I am a little biased since I wrote the JNI bindings and Java ports of XXHash but the benchmarks show interesting results compared to other hash/checksum implementations: http://jpountz.github.io/lz4-java/1.2.0/xxhash-benchmark/. Just beware that depending on the size of the input, the fastest impl of XXHash is not always the same: for large inputs (> 1024 bytes), the JNI one is faster while on smaller input (<= 1024 bytes), the Java port using the Unsafe API is faster, probably because of the JNI overhead.

          You can find the sources of the benchmark at https://github.com/jpountz/jvm-checksum-benchmark.

          Show
          Adrien Grand added a comment - I just learned about this issue and was wondering if you had considered XXHash ( http://code.google.com/p/xxhash/ ) for checksuming. I am a little biased since I wrote the JNI bindings and Java ports of XXHash but the benchmarks show interesting results compared to other hash/checksum implementations: http://jpountz.github.io/lz4-java/1.2.0/xxhash-benchmark/ . Just beware that depending on the size of the input, the fastest impl of XXHash is not always the same: for large inputs (> 1024 bytes), the JNI one is faster while on smaller input (<= 1024 bytes), the Java port using the Unsafe API is faster, probably because of the JNI overhead. You can find the sources of the benchmark at https://github.com/jpountz/jvm-checksum-benchmark .
          Hide
          T Jake Luciani added a comment -

          Hi Adrien, Interesting benchmark! Did you run your benchmark with JDK7? I ask because I thought they sped up the implementations quite a bit for adler and crc

          Show
          T Jake Luciani added a comment - Hi Adrien, Interesting benchmark! Did you run your benchmark with JDK7? I ask because I thought they sped up the implementations quite a bit for adler and crc
          Hide
          Adrien Grand added a comment -

          I ran this benchmark several weeks ago and I'm not sure but I think it was with JDK7. I'll run it again to be sure...

          Show
          Adrien Grand added a comment - I ran this benchmark several weeks ago and I'm not sure but I think it was with JDK7. I'll run it again to be sure...
          Hide
          Adrien Grand added a comment -

          I ran the benchmark again with Java 6 and 7, here is the raw data:

          There are indeed performance differences for CRC32 and Adler32 between Java 6 and 7 but in both cases, XXHash performs even better.

          Show
          Adrien Grand added a comment - I ran the benchmark again with Java 6 and 7, here is the raw data: Java 6u45: https://microbenchmarks.appspot.com/runs/7340dcbf-d314-4ac4-bcb4-806f2e7f6f7b#r:scenario.benchmarkSpec.parameters.size,scenario.benchmarkSpec.parameters.checksum Java 7u21: https://microbenchmarks.appspot.com/runs/4e7ed509-e2ea-4405-bcb6-06a119a06d2b#r:scenario.benchmarkSpec.parameters.size,scenario.benchmarkSpec.parameters.checksum There are indeed performance differences for CRC32 and Adler32 between Java 6 and 7 but in both cases, XXHash performs even better.
          Hide
          Jonathan Ellis added a comment -

          Am I reading that wrong or is that saying that Adler32 got significantly slower for java7?

          Show
          Jonathan Ellis added a comment - Am I reading that wrong or is that saying that Adler32 got significantly slower for java7?
          Hide
          Adrien Grand added a comment -

          Indeed, this is what it suggests.

          Show
          Adrien Grand added a comment - Indeed, this is what it suggests.
          Hide
          Bert Sanders added a comment -

          What is the gain from switching to xxHash ?
          I mean, the proposed Hash might be very fast, but does it translate into real world benefit ?
          The speed of hash functions might be dwarfed by other effects.

          Specifically, I'm interested in hash diversity. For a Bloom filter, this helps getting better distribution, and reduce false positives. And I guess that's where most of the gains should be expected.

          Show
          Bert Sanders added a comment - What is the gain from switching to xxHash ? I mean, the proposed Hash might be very fast, but does it translate into real world benefit ? The speed of hash functions might be dwarfed by other effects. Specifically, I'm interested in hash diversity. For a Bloom filter, this helps getting better distribution, and reduce false positives. And I guess that's where most of the gains should be expected.
          Hide
          Jonathan Ellis added a comment -

          We're specifically talking about sstable checksumming here. We're happy with Murmur3 in the bloom filters.

          Show
          Jonathan Ellis added a comment - We're specifically talking about sstable checksumming here. We're happy with Murmur3 in the bloom filters.
          Hide
          Bert Sanders added a comment -

          Thanks, my bad, I was confused.

          If my understanding is correct, SStables are a set of 2 files,
          one index, with bloom filters and Key/offset pairs
          and one for data by column.

          So I guess this issue is only about checksumming of the data part.

          And about real-world benefits :
          I guess that if testing with Adler32 was enough to measure benefits,
          a faster Hash should be even easier to measure.

          Show
          Bert Sanders added a comment - Thanks, my bad, I was confused. If my understanding is correct, SStables are a set of 2 files, one index, with bloom filters and Key/offset pairs and one for data by column. So I guess this issue is only about checksumming of the data part. And about real-world benefits : I guess that if testing with Adler32 was enough to measure benefits, a faster Hash should be even easier to measure.
          Hide
          Adrien Grand added a comment -

          What is the gain from switching to xxHash ? [...] Specifically, I'm interested in hash diversity.

          xxHash happens to pass all tests of the SMHasher test suite (http://code.google.com/p/smhasher/wiki/SMHasher, see scores and speed of some common hash function at http://code.google.com/p/xxhash/) which has many tests including hash diversity.

          Show
          Adrien Grand added a comment - What is the gain from switching to xxHash ? [...] Specifically, I'm interested in hash diversity. xxHash happens to pass all tests of the SMHasher test suite ( http://code.google.com/p/smhasher/wiki/SMHasher , see scores and speed of some common hash function at http://code.google.com/p/xxhash/ ) which has many tests including hash diversity.
          Hide
          Dave Brosius added a comment -

          I notice that aside from the switch to adler, the checksumming was switched from the uncompressed buffer to the compressed buffer. Was this intended? If so CompressedSequentialWriter.resetAndTruncate can remove the code that uncompresses the buffer, as it's not used.

          Show
          Dave Brosius added a comment - I notice that aside from the switch to adler, the checksumming was switched from the uncompressed buffer to the compressed buffer. Was this intended? If so CompressedSequentialWriter.resetAndTruncate can remove the code that uncompresses the buffer, as it's not used.
          Hide
          T Jake Luciani added a comment -

          Dave Brosius Yes it was intended, less data to checksum.

          Show
          T Jake Luciani added a comment - Dave Brosius Yes it was intended, less data to checksum.
          Dave Brosius made changes -
          Link This issue is cloned as CASSANDRA-6176 [ CASSANDRA-6176 ]
          Transition Time In Source Status Execution Times Last Executer Last Execution Date
          Open Open Patch Available Patch Available
          4h 45m 1 T Jake Luciani 08/Aug/13 20:53
          Patch Available Patch Available Resolved Resolved
          1h 31m 1 T Jake Luciani 08/Aug/13 22:25

            People

            • Assignee:
              T Jake Luciani
              Reporter:
              Jonathan Ellis
              Reviewer:
              Jonathan Ellis
              Tester:
              Alex Zarutin
            • Votes:
              0 Vote for this issue
              Watchers:
              8 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development