Provide helper utility API to compute CRC32 across concurrent (map/reduce) chunks

[mikemccand]

Lucene uses CRC32 for its end-to-end checksumming. Every index file records its own checksum on write, and when lighting a new segment in IndexReader we also validate when we can. CheckIndex validates all files. IndexWriter validates source segment files when merging.

It's awesome, it catches insidious bit flips for those people still not using ECC RAM. I know at least @rmuir and myself and maybe @uschindler (?) have been hit by intermittent bad RAM. Once it strikes you personally you will never again tolerate non-ECC RAM on your dev boxes hah.

At Amazon customer facing product search, we validate Lucene's checksum through each step of our near-real-time segment replication (via S3), so we can (hopefully -- there are still technically vulnerabilities if you have adversarial bit-flipping RAM monster lurking in your box (see visuals from Gemini and Grok)) prevent any bit flips from metastasizing into our persistent S3 index snapshots. This really matters at Amazon's crazy scale (~ 10s of PiB replicated per day to/from S3 -- many chances for errant bit flips!). S3 write/read also does its own checksumming, but that won't catch bit flips on the IndexWriter node before a file is uploaded, so we use/validate both checksums.

One of the delightful properties of CRC32 (thank you MATH!) is you can map/reduce it!

I.e. slice up a large (5 GB is Lucene's default max merged segment) segment into N chunks, compute CRC32 of each chunk concurrently, and then use crc32_combine zlib API to merge the N CRC32s into a single CRC32 that matches the whole file's sequential CRC32 checksum. It's quite simple (says Claude and Grok). This would be awesome because then users like us could use chunk'd upload/download to improve aggregate S3 throughput and lower the nrt refresh latency during replication.

But, annoyingly, it looks like JDK's CRC32 implementation (java.util.zip.CRC32) does not expose crc32_combine?

Maybe Lucene could provide a utility class to make this simple? Claude provides a java implementation of crc32_combine, perhaps it is hallucination free? Or maybe we could use FFM to access the crc32_combine -- but I'm not sure we can rely on it always being accessible/visible to the JVM, always.

[uschindler]

Here is the original C code in the ZLib or Mark Adler. I don't think we need to use FFM, it is basically just a one-liner with the code you oosted before:

https://github.com/madler/zlib/blob/51b7f2abdade71cd9bb0e7a373ef2610ec6f9daf/crc32.c#L1020-L1031

P.S.: Internally Zlib can already be multithreaded (see the ifdef), but Java does not use that!

I would say: Just add a helper function in BitUtil or like that to combine two integer checksums. Plain simple!

[uschindler]

Wah this is several loops, not nice code. Sorry ignore my previous comment.

[rmuir]

I'm trying to understand the use-case, for s3 wouldn't you use it's native checksum functionality instead?

[rmuir]

Oh i see, i didnt realize they had pluggable algorithms: https://docs.aws.amazon.com/AmazonS3/latest/userguide/checking-object-integrity.html

But we should be careful about exposing too much here? I feel like lucene should be free to change the polynomial if we want, for improved performance (e.g. switch to java.util.zip.CRC32C). It is hardware-accelerated via dedicated insns on all modern cpus.

[Tony-X]

There are some relevant code in the AWS Java SDK v2 which seems to contain efforts to make the combining (reducing) routine faster.

https://github.com/aws/aws-sdk-java-v2/blob/84d5c3453732268187920125c4ab796870618ebb/core/checksums/src/main/java/software/amazon/awssdk/checksums/internal/SdkCrc32Checksum.java#L590

https://github.com/aws/aws-sdk-java-v2/blob/master/core/checksums/src/main/java/software/amazon/awssdk/checksums/internal/CrcCombineChecksumUtil.java#L31

[uschindler]

But we should be careful about exposing too much here? I feel like lucene should be free to change the polynomial if we want, for improved performance (e.g. switch to java.util.zip.CRC32C). It is hardware-accelerated via dedicated insns on all modern cpus.

Yes! We can change or fileformats with some extra version number in the checksum header two switch checkums. The code for combining them is same only the POLY constant is different depending on CRC32 variant.

[rmuir]

Yeah i haven't had the time to benchmark the CRC32C openjdk code, I wouldn't be surprised if there is a speedup, so I can't be sure if it is worth the trouble or not. The currently CRC32 is already vectorized and very fast.

[rmuir]

For speeding up the current one, maybe look into bumping this one to 2KB: https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/store/BufferedChecksum.java#L32

1KB value was benchmarked a long time ago with an AVX-128 or AVX-256 machine. These days people have 64-byte vectors.