gc: parallelize garbage collection

[isidentical]

It seems like there is nothing blocking this, and for cloud providers, this might mean up to 16-20x speed up (dvc gc -c). Just for some numbers as the motivation, removing 1000~ cache files from the s3 takes about 20-25 minutes.

[skshetry]

@isidentical, is this required for fsspec? If not, I'd prefer that we prioritize this #4218 over the performance. I am not trying to say that they should not be a priority, not trying to discourage you, but I feel strongly that we should have a way to remove a file from the cache.

[isidentical]

@skshetry is #4218 a blocker for this issue? I don't have the whole context, though it seems something relevant with the used cache calculation and what this issue proposes is speeding up the part after that (running fs.remove() calls concurrently).

Another occurrence we hit during my support duty is dvc gc -c being slow (taking 95+ hours): https://discord.com/channels/485586884165107732/563406153334128681/846717782145368134

[skshetry]

@skshetry is #4218 a blocker for this issue?

@isidentical, sorry for misleading, no it's not related. I was just trying to push #4218 up for prioritization. Please feel free to work on this. 🙂

Regarding #4218, the gc in whole is just stuck in the discussion for more than a year (see #5928). Internally, it might be already possible to implement that (even more so after #6008 with filter).

[SolomidHero]

I have 6M items on s3 storage and wanted to dvc gc them. It never finished. Even querying stage

[daavoo]

Coming from #8549 .

I have faced similar performance issues (latest version). It gets worse with a larger number of files but it is already a real pain around the order of 1000.

Even for just 100 files, there is too much overhead added:

• AWS

# List
$ aws s3 ls s3://${BUCKET} --recursive
real    0m1.247s                                                                                                         
user    0m0.327s                                                                                                         
sys     0m0.072s
# Wipe
$ aws s3 rm s3://${BUCKET} --recursive
real    0m3.570s                                                                                                         
user    0m0.755s      
sys     0m0.128s

• DVC

Note in the reproduction script below I have tried to minimize the overhead from unrelated operations (i.e. local gc, etc) ; you can verify in the attached profile that most time is spent on our equivalent of ls and rm.

$  time dvc gc -f -w -c
real    2m52.810s
user    0m5.885s
sys     0m0.790s

Reproduction script

import random
from pathlib import Path

data = Path("data")
data.mkdir(exist_ok=True)

for i in range(100):
    n = random.random()
    file = data / str(n)
    file.write_text(str(random.random()))

#!/bin/bash
BUCKET=diglesia-gc-testing
aws s3 rm s3://$BUCKET --recursive
rm -rf tmp
mkdir tmp

cp create_data.py tmp
cd tmp

git init
dvc init
dvc remote add -d myremote s3://$BUCKET            
git add .
git commit -m "init"

python create_data.py
dvc add data
# Just because is faster than push
aws s3 cp .dvc/cache s3://$BUCKET --recursive
# Don't spend time on local gc
rm -rf data
rm -rf .dvc/cache

python create_data.py
dvc add data
git add data.dvc
git commit -m "track data"

time dvc gc -f -w -c

dvc doctor

DVC version: 2.38.1 (pip)
---------------------------------
Platform: Python 3.9.5 on macOS-10.16-x86_64-i386-64bit
Subprojects:
        dvc_data = 0.28.4
        dvc_objects = 0.14.0
        dvc_render = 0.0.15
        dvc_task = 0.1.8
        dvclive = 1.2.2
        scmrepo = 0.1.4
Supports:
        http (aiohttp = 3.8.3, aiohttp-retry = 2.8.3),
        https (aiohttp = 3.8.3, aiohttp-retry = 2.8.3),
        s3 (s3fs = 2022.11.0, boto3 = 1.24.59)
Cache types: reflink, hardlink, symlink
Cache directory: apfs on /dev/disk1s1s1
Caches: local
Remotes: None
Workspace directory: apfs on /dev/disk1s1s1
Repo: dvc, git

---

Viztracer profile (see https://github.com/iterative/dvc/wiki/Debugging,-Profiling-and-Benchmarking-DVC#generating-viztracer-data):

viztracer.dvc-20221221_185659.json.zip

[daavoo]

Using treeverse/dvc-data#244 , for 1000 files the overhead is significantly reduced:

• Without patch

$ time dvc gc -f -w -c
real    18m54.253s

• With patch

$ time dvc gc -f -w -c
real    8m19.650s

---

However, there is still a ridiculous overhead compared to aws CLI:

$ time aws s3 ls s3://${BUCKET} --recursive
real    0m2.702s
$ time aws s3 rm s3://${BUCKET} --recursive
real    0m23.851s

For the rm part, checking the profiles shows that all overhead is introduced by _expand_path in https://github.com/fsspec/s3fs/blob/5917684f96226ee855921d1c614d21cc46b3edeb/s3fs/core.py#L1836 (which in this case for us is just a very expensive noop)

[daavoo]

For the rm part, checking the profiles shows that all overhead is introduced by _expand_path in https://github.com/fsspec/s3fs/blob/5917684f96226ee855921d1c614d21cc46b3edeb/s3fs/core.py#L1836 (which in this case for us is just a very expensive noop)

A quick and dirty change of removing _expand_path calls (which in our case have no effect) makes our rm operation to be on pair with aws s3 rm, so no overhead is introduced.

Still need to discuss after vacation how to properly address it in fsspec but IMO makes sense to be able to bypass _expand_path if you know you don't need it (like in our use case).

All the overhead left now comes from our ls vs aws s3 ls, will look into it if I find some time.