search

scality / Arsenal

Common utilities for the open-source Scality S3 project components
Apache License 2.0
15 stars 19 forks source link

ft: ARSN-388 implement GapSet (caching of listing gaps) #2211

Closed jonathan-gramain closed 9 months ago

jonathan-gramain commented 9 months ago

The GapSet class is intended for caching listing "gaps", which are contiguous series of current delete markers in buckets, although the semantics can allow for other uses in the future.

The end goal is to increase the performance of listings on V0 buckets when a lot of delete markers are present, as a temporary solution until buckets are migrated to V1 format.

This data structure is intented to be used by a GapCache instance, which implements specific caching semantics (to ensure consistency wrt. DB updates for example).

bert-e commented 9 months ago

Hello jonathan-gramain,

My role is to assist you with the merge of this pull request. Please type @bert-e help to get information on this process, or consult the user documentation.

Status report is not available.

bert-e commented 9 months ago

Incorrect fix version

The Fix Version/s in issue ARSN-388 contains:

Considering where you are trying to merge, I ignored possible hotfix versions and I expected to find:

Please check the Fix Version/s of ARSN-388, or the target branch of this pull request.

bert-e commented 9 months ago

Request integration branches

Waiting for integration branch creation to be requested by the user.

To request integration branches, please comment on this pull request with the following command:

/create_integration_branches

Alternatively, the /approve and /create_pull_requests commands will automatically create the integration branches.

fredmnl commented 9 months ago

One question on parallelism, I'm still new to Node so maybe all potential race conditions are handled by the mono-threaded nature of node. Could we have the following situation for example:

Initial state of the storage is that there are delete markers on key 1 to 5. 

Listing operation: x starts listing  1 .. 2 .. 3 .. 4 .. 5 .. done, broadcast gap 1-5
Put operation:     x                         puts 2
GapSet:            x                         2 clears cache                    add 1-5 to cache

Basically a concurrent list and PUT operation will not update the data store in the right order. Is this possible?

jonathan-gramain commented 9 months ago

One question on parallelism, I'm still new to Node so maybe all potential race conditions are handled by the mono-threaded nature of node. Could we have the following situation for example:

Initial state of the storage is that there are delete markers on key 1 to 5. 

Listing operation: x starts listing  1 .. 2 .. 3 .. 4 .. 5 .. done, broadcast gap 1-5
Put operation:     x                         puts 2
GapSet:            x                         2 clears cache                    add 1-5 to cache

Basically a concurrent list and PUT operation will not update the data store in the right order. Is this possible?

Yes you're totally correct, there is a race condition that we need to address in some way. I started thinking about this yesterday and potential solutions to it. Updating the cache after every listed key would not be enough as we can always have updates on or between listed keys (i.e. in the inclusive range between two listed keys).

My current idea is that the GapSet class somehow needs to be aware of the gaps that are in construction from the listings in progress, and either ignore or invalidate calls to setGap when those gaps overlap with PUT/DELETE updates that occurred while this gap construction was happening. In other words, if GapSet.setGap(firstKey, lastKey) is aware of when the firstKey was initialized, it can know whether there were new updates in the range [firstKey, lastKey] when the gap is set and ignore the call in such case.

Another idea can be to track all listings in progress, and push invalidation to each listing in progress when removeOverlappingGaps is called. Basically considering that the gaps in construction are already part of the gap set (but not yet usable by other listings).

The funny thing is originally I though of an API for setGap that takes a gap object returned from a prior call, rather than a first and last key, but I was concerned about such race conditions (in the sense that the gap may have been invalidated in the meantime), and decided to switch to first/last strings instead. Using a gap object could actually provide a way to deal with those race conditions by storing some state in the gap objects, although I'm not sure of the details. It could be a raft sequence number (cseq) that would be compared against the recent updates, for example.

jonathan-gramain commented 9 months ago

So I came up with another approach to ensure atomicity, this PR should explain it: https://github.com/scality/Arsenal/pull/2213

jonathan-gramain commented 9 months ago

/approve

bert-e commented 9 months ago

Conflict

A conflict has been raised during the creation of integration branch w/8.1/feature/ARSN-388-gapSet with contents from feature/ARSN-388-gapSet and development/8.1.

I have not created the integration branch.

Here are the steps to resolve this conflict:

 $ git fetch
 $ git checkout -B w/8.1/feature/ARSN-388-gapSet origin/development/8.1
 $ git merge origin/feature/ARSN-388-gapSet
 $ # <intense conflict resolution>
 $ git commit
 $ git push -u origin w/8.1/feature/ARSN-388-gapSet

The following options are set: approve

bert-e commented 9 months ago

In the queue

The changeset has received all authorizations and has been added to the relevant queue(s). The queue(s) will be merged in the target development branch(es) as soon as builds have passed.

The changeset will be merged in:

The following branches will NOT be impacted:

There is no action required on your side. You will be notified here once the changeset has been merged. In the unlikely event that the changeset fails permanently on the queue, a member of the admin team will contact you to help resolve the matter.

IMPORTANT

Please do not attempt to modify this pull request.

If you need this pull request to be removed from the queue, please contact a member of the admin team now.

The following options are set: approve

bert-e commented 9 months ago

I have successfully merged the changeset of this pull request into targetted development branches:

The following branches have NOT changed:

Please check the status of the associated issue ARSN-388.

Goodbye jonathan-gramain.