Implement blake3

[allada]

Sha256 is known to be quite slow. There's a new kid in town, Blake3. It's crazy fast, super secure and just better overall.

BRE already supports it:
https://github.com/bazelbuild/remote-apis/blob/39c174e10d224c46b556d8d4615863804d5b2ff6/build/bazel/remote/execution/v2/remote_execution.proto#L1900

Bazel appears to be in the process of supporting it:
bazelbuild/bazel#18658

Micro-bench testing shows it is worth the effort:
https://gist.github.com/allada/6b4321a6487c2888ff73ce1cc0fc86ed

All results are on a 16 core i9 with (no threads):
1GB @ 10:

sha256: 35.546221869s
blake3: 2.346503712s

abs difference: 33.199718157s
% difference r: 1514.86%
% difference i: 6.60%

1MB @ 10_000:

sha256: 34.653737424s
blake3: 2.129524155s

abs difference: 32.524213269s
% difference r: 1627.30%
% difference i: 6.15%

1KB @ 1_000_000:

sha256: 3.714629289s
blake3: 725.049013ms

abs difference: 2.989580276s
% difference r: 512.33%
% difference i: 19.52%

100B @ 1_000_000:

sha256: 453.309362ms
blake3: 113.922135ms

abs difference: 339.387227ms
% difference r: 397.91%
% difference i: 25.13%

This is a significant difference and when things are under high workload, it is often because we are spending so much time hashing. This hash a very high chance of dramatically improving performance of the cas stores.

[aaronmondal]

This looks fantastic! It even has an official implementation for Rust 😍

There don't seem to be any viable alternatives either since this is also officially endorsed by the RBE. As for usability it seems like Buck2 already supports it.

cc @JannisFengler since this might interest you 😄

[allada]

For anyone that is interested in implementing it, I think a great first step is to support it in some of our internal Store<->Store mappings like DedupStore. Because in Dedup store we can use Blake3 for both content_store, since this is all implementation detail that client's don't know about.

[SpamDoodler]

I would be interested in working on this issue!

[SpamDoodler]

The hash in check_missing_last_chunk_test() in cas/store/tests/dedup_store_test.rs seems to be wrong (it should be since it's computed with sha256).
How do I get the correct test hash for blake3 there?

Other tests are already passing.

[aaronmondal]

How do I get the correct test hash for blake3 there?

If you use an assert to check for equality failing tests should print something like "you gave me hash but I expected other_hash". Then you can copy-paste it from that message and if the CI runner passes on that new hash things should be fine.

As an additional test you could also use the testvectors from the blake3 repo to make sure that the "basecase" of running blake3 on something is really the same: https://github.com/BLAKE3-team/BLAKE3/blob/master/test_vectors/test_vectors.json

[allada]

Awesome thanks @SpamDoodler , but for some reason it looks like #205 's commit was attributed to me instead of you. This is probably because of some rebase issues. If you want I can revert and recommit if you really care about the attribution.

[chrisstaite-menlo]

The v2.3 format specifies the hash type in the URL, meaning that BLAKE3 can now be supported by CAS in general... #281 parses the value in. It's worth noting that the hash type is supposed to be interpreted based on length of the hash if it isn't specified. See the remote_execution.proto for more details.

Our capabilities response should also be updated to specify that we support BLAKE3.

[allada]

Done.