perf: remote indexes

[Suor]

As we discussed making dvc fast should be high priority as poor performance can draw people away easily. The big part of todays slowness is working with remotes, which almost always includes collecting file statuses, which could be slow for bigger remotes. All this leads to some form of indexes.

However, our remotes don't provide a luxury of atomic group writes nor reads nor read-modify-write operations. We still can use the following strategy:

• make an index dir on remote, say index,
• write a list of files (with names, checksums, mtimes and/or file sizes) to an index file in that dir say 1.idx
• later when some client needs to update that, e.g. after pushing some new files it:
  • reads current index,
  • updates it,
  • writes new list to 2.<uuid>.idx,
  • removes 1.idx.
    This way in a case of a race we will have several index files.
• if a client needs to read an index it downloads all index files and combines them.

Since we will not only have adds, but also deletes we will need smart combine procudure like in CRDTs.

File format to be discussed, simple JSON or gzipped JSON with a list of files may do the job though.

What do you guys think? @shcheklein @dmpetrov @efiop @pared @MrOutis

[shcheklein]

First, the ideas we discussed before (just to document them and they might spark more experimentation or help focusing on a smaller problem):

1. Use hierarchical structure of the DVC cache as an index. Right now we split into up to 256 directories since we use only first two letters of a checksum, but we can (and probably should anyway to keep directories smaller) introduce at least couple more layers. Thus we will have 2^24 potential subdirectories. To get status we can run multiple parallel ls.

2. Use an index/flag file for the directory. The biggest performance bottleneck in our case is happening when we have large directories. Locally, we have done some optimizations (at least we hope they will work) to get complexity of certain operations to O(1). (Namely, we are reconstructing using hardlinks the full "shadow" copy of the directory inside the cache dir. It makes certain operations behave as if would have worked with a single file.)
   Can we do the same trick with remote? Push that json file we have for a directory to the remote or create a special flag-file that which would mean that all files exist? We will potentially need to use some data structures like @Suor mentioned.

Let me know if something above requires some clarifications :)

[shcheklein]

Back to the idea of using lock-free self-healing structures. It's hard (for me) to think this all through at once. This stuff can be tricky. Can we first discuss and decide some "data remote model" - what guarantees do we want to provide, what things are okay to happen, what of them are not, etc:

To start, stuff that comes to my mind:

1. It's ok from time to time to push things twice. One client does not see an object on remote and pushes it again.
2. It's not ok to miss a push for some reason. One client can see an object on remote which does not actually there. It might cause a data loss, which is not acceptable.

Any other scenarios that come to your mind that are not acceptable?

[efiop]

If you think about it, our .dir cache files are indexes already. If push was successful, we could pretty safely assume that if there is .dir on the remote, then all the files from it are already there as well. What we could do is:

• On push: push files from dir first and only then push .dir cache file, so anyone that would be trying to pull/status would not see that dir on remote until it is fully there.

• On pull/fetch/status: check if .dir file exists on the remote and if it does, then assume that all the files in it also exist on remote. This would basically make Nfiles exists checks into 1 .dir exists check, which would be much much faster. Then we would try to download those files and if any are missing, dvc would report that directory as incomplete(it does it already, since we have similar problems even right now).

It is pretty clear that this might be dangerous if anyone is running gc -c, but it has been that way anyway 🙁

This approach is pretty simple to implement, and is similar to how we trust remote that md5 file is not corrupted there, but we are verifying it when we download it, same as we do with directories.

[Suor]

A recap of related discussions with @dmpetrov and @efiop.

Index size might be an issue. Given 10 million items, 50 bytes per item (checksum + file size) means 0.5GB index size, which will mean significant time to simply download index, which might undermine the whole idea. However:

• listings are an order of magnitude faster when batch exists calls when we are querying for lots of checksums, downloading an index should be even faster,
• downloading a file will have progress bar unlike listing, so user won't be in a stuck-and-have-no-idea-if-it-is-still-working situation,
• there would be no single index file but series of index update files, we can cache previously downloaded/uploaded index update files, so user won't need to download them each time,
• we will still need to load the entire index into memory to efficiently check millions of checksums against it.

The discussion with @efiop was mostly about optimizing directories. This includes efficiently tracking changes and comparing changed directory to local and remote caches. The thing is solving this will make other optimizations like indexes not really needed - there is a use case of adding many files recursively, but that according to @efiop is about thousands not millions of files and millions of .dvc files will break dvc anyway, since we are building graph each time (this was never checked though).

The core idea to optimizing directory is not loosing a link to its previous listing (which we already have) and comparing it to an actual file list. Having that we can calculate a diff and then check whether a remote has that directory listing and new/modified files, no need to check for all the files. This implies that nobody would remove files before directory listing, which is probably how it works now anyway. To find a previous listing we might use name or similarity heuristics to existent listings, such as number of files, total file size, types (extensions) of files, maybe checksums of some files. To efficiently find a most close directory to the one we are working with at the moment we will need to store metadata files with those heuristics for all the directories and their history to some level. This solution is less universal than indexes and looks harder to implement, it will, however, yield a better performance for large directory case.