Alterative hashings for data

[dunstantom]

Since md5 is sensitive to the order and format of the data, simple changes to the schema (eg. swapping two columns) or changing the type of a column (eg. integer to float) leads to new hash values and duplicated datasets. There are some alternatives that attempt to address this, such as UNF (http://guides.dataverse.org/en/latest/developers/unf/index.html).

It would be great to specify an alternative hash function in DVC, particularly to be able to provide a user-defined function.

[efiop]

Hi @dunstantom !

That is a very interesting idea! So is the cache duplication the main motivation for this request? Or do you also want to use something different than md5 for checking if your dependencies are changed in pipeline scenario?

Thanks,
ruslan

[dunstantom]

I would say mainly it is having an alternative for md5. On one hand, one could argue about how SHA1 compares to md5, but on the other hand (and what I had in mind) we may have our own preferences on what kind of changes necessitate recalculating/updating a dataset. This ties in to limiting cache duplication as well, but more from the perspective of avoiding unnecessary computation rather than a concern of having storage for the cache. Hope that answers your question.

[efiop]

@dunstantom Thank you for your answer! 🙂 We do think about moving to SHA too, but other users also requested some faster hashing as well, so looks like it is a general problem of supporting different hashing algos . Related to #1568 . This is something we'll take a closer look later. Thanks for the feedback! 🙂

[rasmuse]

@efiop I asked earlier this week in #1568 about the possibility to use other hash algorithms. I'm shifting that part of the discussion here since this issue seems to be a better match for my request (#1568 could be solved in principle by changing to one other hash algorithm, i.e., just switch the md5 function for another one).

Short report on my progress: I made a local git checkout -b not-only-md5 yesterday. I notice that the code assumes in many places that each Remote implementation is tied to a single hash algoritm. This is most evident from the class-level constant PARAM_CHECKSUM (the name of the hash algorithm).

My first idea about how to implement this is to move the info about the hash algorithm to the Output and to let each instance of an Output have its own hash algoritm. At present the OutputBase class has a property checksum that depends on its self.remote.PARAM_CHECKSUM, and my idea would be to invert this relationship so that the Remote would get Output-specific information on the hash algorithm from the Output.

But I only know a very small part of the code base, so I'm hoping you can help me judge if this idea makes any sense at all.

It would then instead be up to the specific cache implementation to check the hash function on the Output instance and decide on a cache path. In principle one could imagine something like this in the cache directory:

cache
├── md5
│   └── ab
│       └── cdef
└── sha256
    ├── 12
    │   └── 3456
    └── 89
        └── 0123

But for backwards compatibility any md5 hashed files could be stored under their old paths, like so:

cache
├── ab
│   └── cdef
└── sha256
    ├── 12
    │   └── 3456
    └── 89
        └── 0123

[efiop]

Hi @rasmuse !

We used to have an assumption that you might have a few checksums, but the code evolved in such a way, that we started to stick with single-checksum assumption. That being said, the underlying logic is still partially there. For example, if you take a look at checksum_info(also called info sometimes), you'll see that it is a dict, so you could have a few checksums there. Also, each remote has its own checksums(mostly), but even if you use the same remote for external cache(e.g. where cache is organized by etags) and push your local cache there (organized by md5s), you'll get the same dir structure(say we have a cache file with md5 123456 and a cache file with etag ABCDEF):

cache
├── 12
│   └── 3456
└── AB
    └── CDEF

So far, the likelihood of those two colliding was pretty slim, so we didn't worry about it too much. But if we are moving to a more general approach, it totally makes sense to separate them somehow. I like your idea with creating subdirs for each hash type and I agree that for backward compatibility we should stick with current cache structure for md5 caches, meaning that it won't be put into cache/md5/ for now.

We actually have a few problems with a current hashing (for example, see #992) and I think we could switch to using cache/md5 then, so we could distinguish between the old md5 cache and the new true one. Btw, our ssh remote in external outputs scenario is using true md5, so we could make it use new cache dir structure right away 💅

This is how I see it (approximately):

1. Introduce hash config option in section core, that would tell dvc which default hash algo to use;

OPTIONAL make it also accept a number of hashes in a given order of priority. E.g. if config looks like

[core]
hash = sha256, md5

it would try to compute sha256 first, but if remote doesn't support sha256 for some reason, it would try to fallback to md5.

NOTE if we would want to, we could easilly support per-remote and even per-output/dep hash type configuration later.

2. Make OutputBase by default use hash type that is specified in the config(this is effectively going to replace current PARAM_CHECKSUM constant); Note that if we are simply checking if anything has changed (e.g. with dvc status), output should be smart enough to fallback to md5 checks if it doesn't have sha recorded in the dvcfile yet. E.g.

$ dvc config core.hash md5 # default
$ echo foo > foo
$ dvc add foo
$ dvc status # should report that everything is up to date
$ dvc config core.hash sha256
$ dvc status # should still report that everything is fine

Or, maybe, if you specify strictly hash = sha256, you would actually want to forbid using any other hashes(such as md5s) at all. This is where that optional part from 1) would come in handy, because the behaviour described above would be only possible with

dvc config core.hash sha256, md5

🙂 But we could totally start with a simple fallback approach for now.

3. Make OutputBase use self.remote.hash(self.hash_name, self.path_info) method instead of self.remote.save_info that is used right now;

4. Implement RemoteBase.hash(hash_name, path_info) that would call specific hash method like self.md5(path_info) or self.sha256(path_info). Obviously, for now, only dvc/remote/local.py would support sha and all others would have to rise smth like a NotImplementedError. But we will be able to generalize that for all remotes later (Related to azure/gs/s3: re-design checksum computation for external dependencies/outputs #1410).

5. Implement RemoteLOCAL.md5(path_info) and RemoteLOCAL.sha256(path_info);

NOTE this is where it might get tricky, because our RemoteLOCAL uses our state db for caching md5s, so we don't have to recompute them each time. For now, you could simply not cache sha values at all, to make it simpler for you. We have some state generalization logic coming in #1654 , that will help us easilly cache sha (and other hash types) the same way as md5, so will be able to help you with that later. 🙂

Hope this helps :) Let us know if you have any questions and/or need help.

Thanks,
Ruslan