Put data and deletion files in subdirectories

[wjones127]

When doing cleanup, we need to list all files to find untracked files. When we have lots of data files, this can be very slow.

The only portable way to get parallelism in this is to divide data up into directories.

For example, imagine you have 1 million lance files in the data prefix in S3. To list all these, you need to do 1,000 S3 list calls, sequentially. If we put them into 1000 unique prefixes, we could do 1 list call to get the prefixes, and then 100 parallel list calls at time, getting all results in something like 20% of the time.

Data files can have their naming scheme adjusted by changing:

https://github.com/lance-format/lance/blob/2a08ec9daa55198fe64ccd13ede2fead09261c71/rust/lance/src/dataset/fragment/write.rs#L43

Deletion files also matter, as I suspect we can create a lot of them. Each time a delete, update, or merge-insert runs, we can create these. So datasets with lots of updates will have many more deletion files than data files. Unfortunately, right now the file name is defined in the spec:

lance/protos/table.proto

Lines 424 to 425 in 964ac0e

	// The path of the deletion file is constructed as:
	// {root}/_deletions/{fragment_id}-{read_version}-{id}.{extension}

🤦 Yeah, it was I who did that... We'll need a spec change to make that hapen.

[wjones127]

@jackye1995 I know you rejected doing something like this in: #4737 (comment)

But I think we might want to add just one level of directories here, enough to get 1,000 common prefixes under data/ we can list in parallel.

What do you think?

[jackye1995]

With the latest file naming scheme, at least for data files, I think we could do that already? Because all files would be a predictable pattern of zeros or ones, if we want let's say 8 parallelism, we can just list all files with prefix 000, 001, 010, 011, .... and those should be evenly distributed. Would that work for this case?

I guess this is more of a problem for local file systems? In Iceberg that was why we did slashes in the middle, like 0101010/010101 in order to allow file systems to distribute list calls through the middle slashes. And I was the one saying Lance did not need this because we won't support systems like HDFS....

[wjones127]

I guess this is more of a problem for local file systems?

S3 Express doesn't support listing with a prefix that doesn't end with /, so also applies there.

[jackye1995]

S3 Express doesn't support listing with a prefix that doesn't end with /, so also applies there.

I see... totally forgot that. I guess data file is the easy case since we can just add / in the middle and it should work fine.

Deletion files also matter, as I suspect we can create a lot of them.

For blob v2, we are already creating blob files under data/{fragment_key}/{blob_id}.blob, I think one natural choice would be to do {root}/_deletions/{fragment_key}/{read_version}-{id}.{extension} so we can use the same folder structure. we might want to do {id}-{read_version}.{extension} for prefix entropy.