checksums for chunks

[ttung]

Problem description

Having checksums for individual chunks is good for verifying the integrity of the data we're loading. The existing mechanisms for checksumming data are inadequate for various reasons:

1. Checksum of the entire array's data: This does not work for loading a subset of the data.
2. Checksum of each individual chunk recorded by a filter as part of the chunk: This does not protect against chunks being swapped, and does not help for building a persistent cache for previously read chunks.

Recording the checksums in the .zarray file could work, but may be problematic for larger data sets.

---

see also:

• Extension for data integrity zarr-specs#75
• Add nested data generation and tests (zarr-python and zarrita) zarr_implementations#33 (comment)

[jakirkham]

Thanks for raising this, @ttung.

It sounds like we have a partial solution for this, but we may need an additional codec to close the gap. For example including the chunk key as part of the checksum computation. Would have to think about how we add this information in a reasonable way while still keeping the API friendly.

...and does not help for building a persistent cache for previously read chunks.

Can you please expand on this a bit?

[alimanfoo]

It might be helpful to know when you would want to verify data integrity. E.g., would you want to verify a chunk every time it was read? Or something else?

[ttung]

It sounds like we have a partial solution for this, but we may need an additional codec to close the gap. For example including the chunk key as part of the checksum computation. Would have to think about how we add this information in a reasonable way while still keeping the API friendly.

Including the chunk key as part of the checksum computation is still prone to mistakes if one is dealing with multiple data sets. One possible strategy is to write a UUID into the .zarray file, and include that and the chunk key as part of the checksum computation. That would not eliminate the risk of data corruption, but would lessen it.

I would personally still prefer the checksums be included in the .zarray file or something alongside it.

Can you please expand on this a bit?

We use the chunk checksums in our current data format to index into a persistent cache on disk, and the chunk checksums are included in the metadata files. If we are loading data from the network, we can avoid doing a network transfer.

The strategy where the checksum is written into the chunk can feasibly be worked into such a scheme, but requires us to:

1. have a predictable offset to the checksum in the chunk output file.
2. do a ranged HTTP/S3/GS/etc GET to retrieve the checksum.
3. index into a local cache.
4. if the local cache doesn't have the data, retrieve the chunk.

It might be helpful to know when you would want to verify data integrity. E.g., would you want to verify a chunk every time it was read? Or something else?

Currently in our existing file format, we verify a chunk every time it is read. There hasn't been any indication that this is an onerous requirement.

[alimanfoo]

Hi Tony, I think I would suggest two possible approaches. One would be to adopt a convention where you write a checksum file alongside every chunk file into your zarr store. E.g., if you have an array at path /foo/bar within a store, and you have chunks at /foo/bar/0.0, /foo/bar/0.1, etc., then write checksums into files at /foo/bar/0.0.md5, /foo/bar/0.1.md5, etc. For the format of these checksum files you could just write the hex digest as ascii text, or you could follow the format of the md5sum command line utility, which would mean you could also use md5sum directly on the command line if you have the data on a file system. Obviously this could be adapted to use other types of hash. Another option would be to adopt a convention where you write a special file for each array containing all chunk checksums as a JSON object. E.g., if you have an array at path /foo/bar then you could store a JSON document at /foo/bar/.md5 which looks something like: { "0.0": "4f20243c7cd186a8353798c0adbf2300", "0.1": "f6869ce45bf74338b41c4c1a6f8e58a5", etc. } Note that for both options I am basically suggesting that you layer your own convention on top of the store API, regarding what keys and values you use to store chunk checksums. The exact keys and values you use would be up to you. The only essential ideas in the two options above is that in option 1 you store the checksum for each chunk under a separate key, and in option 2 you store all chunk checksums together in a single document under a single key. Which option would depend on usage patterns, numbers of chunks, I/O latency, etc. You could also use the ".zattrs" key for option 2 rather than a separate ".md5" key, but then with lots of chunks you might slow down access to other user attributes. Hence may be better to use a different key. Hope that makes some sense.

…

On Thu, 21 Feb 2019 at 10:05, Tony Tung ***@***.***> wrote: It sounds like we have a partial solution <https://numcodecs.readthedocs.io/en/latest/checksum32.html> for this, but we may need an additional codec to close the gap. For example including the chunk key as part of the checksum computation. Would have to think about how we add this information in a reasonable way while still keeping the API friendly. Including the chunk key as part of the checksum computation is still prone to mistakes if one is dealing with multiple data sets. One possible strategy is to write a UUID into the .zarray file, and include that and the chunk key as part of the checksum computation. That would not eliminate the risk of data corruption, but would lessen it. I would personally still prefer the checksums be included in the .zarray file or something alongside it. Can you please expand on this a bit? We use the chunk checksums in our current data format to index into a persistent cache on disk, and the chunk checksums are included in the metadata files. If we are loading data from the network, we can avoid doing a network transfer. The strategy where the checksum is written into the chunk can feasibly be worked into such a scheme, but requires us to: 1. have a predictable offset to the checksum in the chunk output file. 2. do a ranged HTTP/S3/GS/etc GET to retrieve the checksum. 3. index into a local cache. 4. if the local cache doesn't have the data, retrieve the chunk. It might be helpful to know when you would want to verify data integrity. E.g., would you want to verify a chunk every time it was read? Or something else? Currently in our existing file format, we verify a chunk every time it is read. There hasn't been any indication that this is an onerous requirement. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#392 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAq8QkILtx1kHzD4ihb9IPzLZBteReHDks5vPm9_gaJpZM4aDtpG> .

-- Alistair Miles Head of Epidemiological Informatics Centre for Genomics and Global Health Big Data Institute Li Ka Shing Centre for Health Information and Discovery University of Oxford Old Road Campus Headington Oxford OX3 7LF United Kingdom Phone: +44 (0)1865 743596 or +44 (0)7866 541624 Email: alimanfoo@googlemail.com Web: http://a <http://purl.org/net/aliman>limanfoo.github.io/ Twitter: @alimanfoo <https://twitter.com/alimanfoo> Please feel free to resend your email and/or contact me by other means if you need an urgent reply.

[jeffdlb]

Hello-

Has anybody implemented this? I like Alistair's suggestion above to "write a special
file for each array containing all chunk checksums as a JSON object."
A different site suggested MurmurHash as something simpler and faster than MD5 or SHA256 but is not intended to be cryptographically secure.

-Jeff DLB

[rabernat]

For some reason, I have been thinking about this instead of doing other more important things like sleeping.

I think I have come up with a scalable algorithm that should work to compute a single hash for a large chunked ndarray that is independent of on-disk chunk size. This algorithm presumes that you are working with dask or a similar parallel computing framework that has the ability to rechunk on the fly.

The idea is to use a Merkle tree to iteratively reduce the array to a single hash. The steps are as follows.

1. First flatten the ND array to one dimension. (This may not be necessary, but it helps to just think about the 1D problem for now.)
2. Then rechunk the array to a pre-determined chunk size N (e.g. N=1000 elements). This value will be be a parameter of the hash; changing it will result in a different hash.
3. Compute the hash of each chunk. Since we don't care about cryptographic security but just correctness, we can use whatever checksum algorithm is fastest. Recently I like xxhash.
4. Now perform a tree reduction on these hashes, computing the hash of the sum of hashes for each pair, all the way up to the root of the tree. The last hash is our array's hash.

Pros

• This method will deliver a deterministic checksum for a chunked array independent of the chunking scheme
• The algorithm is distributed so can be applied to arbitrarily large data

Cons

• We have to flatten the array. This can be done lazily via Dask but may not be efficient for all chunking schemes.
• The value of the hash depends on N, which needs to be stored somehow together with the hash itself.
• Getting the right value of the final hash requires us to compute do the tree reduction in step 4 in the same way every time. This might be hard.

As an alternative to flattening the array, we could do the tree reduction in multiple dimensions, but this makes my head hurt to think about.

[d70-t]

Thanks @rabernat for pointing me here.

I'm thinking a bit around this and our little initial discussion about IPLD. After reading this thread, I believe that IPLD might indeed be a very good fit.
I believe that building the checksum via a Merkle tree will indeed also work for ND-chunks, but in that case, the entire chunk shape must be fixed and the order in which the chunk checksums are aggregated to a tree checksum must be fixed as well. The advantage of ND-chunk-checksums might be that rechunking may become cheaper or even unnecessary. Apart from that, this method might still share the same cons of @rabernat's approach.

But now for IPLD: as a very brief primer, IPLD is a system of linked data structures which are representable in various formats (including CBOR and JSON). Those structures consist of a set of a few data kinds:

• Null
• Boolean
• Integer
• Float
• String
• Bytes
• List
• Map
• Link

So this is basically JSON plus Bytes and Link, which might be the most important kinds for the zarr use case.
Each datastructure in IPLD is addressed by a hash of its contents (called CID) and a Link kind is a reference from one data structure to another datastructure, identified by CID.
IPLD specifies that entries in a Map must have a defined order (not necessarily sorted), to make the computation of the hash deterministic and unique.
It is possible to write out raw leaves which are not embedded in a Codec, so it would be possible to have just the bytes of a chunk in a single object (identified by CID) in stead of e.g. a CBOR object with a single Bytes-Kind entry.

Based on those building blocks, one could create the chunks in a defined shape (as suggested by @rabernat), create hashes (CIDs) of each chunk and create a mapping as suggested by @alimanfoo:

{
    "0.0": {"/": "4f20243c7cd186a8353798c0adbf2300"},
    "0.1": {"/": "f6869ce45bf74338b41c4c1a6f8e58a5"},
    etc.
}

the subtle difference here is the "/", which is IPLD's way of embedding Links into JSON. The on-disk encoding would likely be CBOR in stead, because it's binary and more efficient, but is less illustrative. Furthermore, because Maps have a defined order, one can compute a deterministic hash of that object, even in case of N-D chunking.

This approach can be continued up the levels, so let's say the CID of the above would be "0123456789abcdef", a natural extension would be to have a toplevel object like:

{
    ".zgroup": {"zarr_format": 2},
    "temperature": {"/": "0123456789abcdef"},
}

In which case one would obtain a checksum for the entire dataset as well.

Note that is would be possible to create inline nested objects as well as referenced objects (so the smaller metadata objects do not necessarily have to live separately), but one would of course want to specify deterministically how to do this, because this would change the overall hash. It is possible to have an IPLD implementation which makes reads across links transparent, which gives you filesystem-like paths (e.g. access via root_CID/temperature/0.1 would return the Bytes behind f6869ce45bf74338b41c4c1a6f8e58a5).

One could use this scheme just to compute the toplevel hash for verification and throw away all the intermediate data, but one could also write out the (intermediate or all) blocks based on this scheme such that one could verify only parts later on (one would need the mapping from chunk id to chunk CID to verify individual chunks).
Each of the blocks identified by CID can be transported individually. One could write them out in a CAR stream (a bit like tar, but usind CIDs in stead of paths as keys), put them onto a key-value store (using CIDs as keys) or transport them via IPFS. Either of the methods might be suitable for different purposes but any of them could be converted into any other.

[d70-t]

Oh... and given someone has written out the Merkle tree structure in the form of IPLD including .zarray-Metadata, like:

{
    ".zarray": {"chunks": [...], "compressor": {...}, "dtype": "...", ...},
    "0.0": {"/": "4f20243c7cd186a8353798c0adbf2300"},
    "0.1": {"/": "f6869ce45bf74338b41c4c1a6f8e58a5"},
    etc.
}

one could fetch only that level of the Merkle tree (excluding the actual data blocks). But based on this information (which is itself verifiably by the CID), one would know to which shape, compression, datatype etc... one would have to rearange some locally available data in order to verify correctless based on the given hashes. Thus one would have a flexible and natural way of specifying the required "hash-parameters".

[rabernat]

One complexity here is that there are two possible hashes for each chunk:

• The hash of the uncompressed data - needed to verify the array contents; should be independent of choice of compression codec
• The hash of the compressed data - appropriate for using in a CID system

My post above was more about the former. However, it may make sense to focus on the latter if we are interested in IPLD.

[rabernat]

Oh... and given someone has written out the Merkle tree structure in the form of IPLD

This looks a lot like consolidated metadata. 🚀

[d70-t]

One complexity here is that there are two possible hashes for each chunk:

I'd say yes and no. If we'd make the way of compressing the data a parameter (just as the chunking is a parameter), then any author of a hash-set could decide about using a null-compression to arrive at hashes for uncompressed data or to use another compression to arrive at a different set of hashes. In any case, the one verifying the data must use the same algorithm (including hash, chunking and compression).

There might be a question though if compression one way (i.e. without decompression) is a deterministic process or if it changes across versions...