arielshaqed
commented
2 years ago 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).
- 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
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...).
ozkatz
github-actions[bot]
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".