Compaction: Common prefix listing on a branch is linear in # of uncommitted entries

[ozkatz]

common prefix listing that includes uncommitted changes on a branch (i.e. first screen seen in the UI when clicking on a repo) is actually o(n) where n is the amount of uncommitted changes.

The problem here is recognizing common prefixes that were deleted.
Given an underlying commit and a list of uncommitted change, the way to tell whether a common prefix exists, is by making sure not all entries within it are tombstoned in the list of uncommitted changes.

See this: https://github.com/treeverse/lakeFS/blob/v0.42.0/pkg/graveler/combined_iterator.go#L87
This is the iterator that combines a set of changes (iterA) and an underlying commit (iterB). Assuming prefix "a/" contains 1m entries in the underlying commit, and 999,999 tombstones in the diff, this iterator will scan all of them when calling Next().

Not sure if current data model allows doing anything better, but probably worth exploring and understanding the tradeoff of doing something "better".

[arielshaqed]

Not sure if current data model allows doing anything better, but probably worth exploring and understanding the tradeoff of doing something "better".

Introducing... range deletes

tl;dr: Allow tombstones to span an entire range. A range tombstone marks that all entries in the underlying commit from a to b are deleted.

This is actually an old idea, I cannot find it explicitly in the BigTable paper, but it appears at least e.g. in Cassandra. And every SSTable-based DB seems to have one, e.g. RocksDB range tombstones

Once introduced it is easy to come up with rules for managing delete ranges; it is cheap enough to add them that we can do everything online. Call every tombstone a range delete, just of size 1 (i.e. a tombstone for key K is a tombstone for the range [K, K || '\0'), where || '\0' is appending a NUL to K.

• When deleting an object at key K, check the previous and next elements in both staging (Sp, Sn) and HEAD commit (Cp, Cn).
  • If Sp is a range delete (or delete) and if Cp is not after the end of Sp, then extend Sp to include K.
  • If Sn is a range delete (or delete) and if Cn is not before the start of Sn, then extend Sn to include K.
  • To perform both operations, merge Sp and Sn.
• When adding an object at key K, check the previous staging element Sp.
  • If Sp=[A,B) includes K, then split Sp into 2 ranges and insert K between them. We now have a delete range [A,K), the object with key K, and a delete range [K || '\0',B).

We can also directly add range deletes, probably as a really fast prefix delete (rm --recursive, as performed on the client side in #2529) -- this can happen in constant time!

Note that support for partial commits (#2512) inevitable interacts with range deletions. Nothing impossible, rules will make sense, but we shall have to be aware of both of these solutions.

Range deletes are good for iteration

Object listings are a merge between iteration on committed HEAD and on staging (both with a O(log n) SeekGE operation). So whenever we see a tombstone we skip the committed past its its end.

This is still linear in # of uncommitted entries, but that was never really the point. We are now almost linear in output size. Specifically time is O(n + d log N) where n is the output size, N is the size of the entire commit, and d is the number of range deletions on staging. (We can make it O(n + d log n) if the SSTable library can use previous iterator hints correctly, but that probably barely matters...).

[arielshaqed]

Also relevant: #2466. But ranges are quite easy to support on a sorted-key KV: use either start or end of the range as a key, store the other inside the value, and because there is never any overlap between ranges or keys in the staging area, the application logic can do the rest.

[ozkatz]

@arielshaqed This is a great idea and I think deserves a proposal on its own right!

Just clarifying: this doesn't solve the issue (or at least not all occurrences of it), at least not without some client integration (i.e. if s3a still deletes partitions object-wise, or if the AWS SDKs do the same),
It does, however, open the door to implementing those.

[arielshaqed]

@arielshaqed This is a great idea and I think deserves a proposal on its own right!

Given that the range deletes proposal is intended solely to resolve the problem of many tombstones, I think I like it here :-)

Just clarifying: this doesn't solve the issue (or at least not all occurrences of it), at least not without some client integration (i.e. if s3a still deletes partitions object-wise, or if the AWS SDKs do the same), It does, however, open the door to implementing those.

Not sure that this is true. This proposal does NOT add a "range delete" API. Instead it adds a new(-ish) datatype to store in the Graveler staging area. Specifically this on how to delete:

• When adding an object at key K, check the previous staging element Sp.
  proceeds to explain how to extend any adjacent delete ranges.

So any S3 client that deletes all elements of a range (in any order) will end up generating the exact same range delete tombstone. (And as noted in the proposal, this is a stolen not a particularly novel idea.)

[github-actions]

This issue is now marked as stale after 90 days of inactivity, and will be closed soon. To keep it, mark it with the "no stale" label.

[github-actions]

Closing this issue because it has been stale for 7 days with no activity.