Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

sync: add new Map method LoadAndDelete #33762

Closed
wkonkel opened this issue Aug 21, 2019 · 16 comments
Closed

sync: add new Map method LoadAndDelete #33762

wkonkel opened this issue Aug 21, 2019 · 16 comments

Comments

@wkonkel
Copy link

wkonkel commented Aug 21, 2019

Problem

It is not currently possible to determine if a value was deleted from a sync.Map. For example:

actual, ok := m.Load("key")
if ok {
  m.Delete("key")
  doSomething(actual)
}

This is not atomic in that another goroutine could Delete the value between Load and Delete and doSomething() would be called twice.

Previous issues #25396 and #23547 suggested modifying Delete signature which would break backwards compatibility.

Solution

Create a new function:

func DeleteWithLoad(key interface{}) (actual interface{}, deleted bool)

If the key is found in the map, this function would return the deleted value and true. If the value is not found, this would return nil, false. The above code would then become:

actual, deleted := m.DeleteWithLoad("key")
if deleted {
  doSomething(actual)
}
@gopherbot gopherbot added this to the Proposal milestone Aug 21, 2019
@ianlancetaylor ianlancetaylor changed the title proposal: sync.Map should provide DeleteWithLoad which returns loaded value and boolean proposal: sync: Map should provide DeleteWithLoad which returns loaded value and boolean Aug 21, 2019
@ianlancetaylor
Copy link
Contributor

CC @bcmills

@bcmills
Copy link
Contributor

bcmills commented Aug 22, 2019

On a cosmetic note, I would want to name the method Remove rather than DeleteWithLoad.

@bcmills
Copy link
Contributor

bcmills commented Aug 22, 2019

I'm curious what the concrete use-cases are. (The proposed operation seems useful in theory, but I wonder whether it actually is in practice.)

Could you give some examples of existing code using sync.Map or a similar API that would benefit from this API?

@bcmills bcmills added the WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. label Aug 22, 2019
@wkonkel
Copy link
Author

wkonkel commented Aug 22, 2019

A practical example would be using sync.Map as an in-memory cache above a remote database. Since database insert/delete operations are relatively expensive, we want to only call them as needed. The LoadOrStore function allows us to perform a single insert operation even if many goroutines are trying to insert the same data. But there is no equivalent way to ensure a single operation for delete.

func (self *Cache) Add(key interface{}, value interface{}) {
  _, loaded := self.syncMap.LoadOrStore(key, value)
  if !loaded {
    self.database.Insert(key, value) // expensive operation
  }
}

func (self *Cache) Remove(key interface{}) {
  _, removed := self.syncMap.Remove(key) // proposed function
  if removed {
    self.database.Delete(key) // expensive operation
  }
}

@bcmills
Copy link
Contributor

bcmills commented Aug 22, 2019

That example seems racy, though: nothing in sync.Map serializes the calls to Insert and Delete, so you could end up with an execution trace that looks like:

  • LoadOrStoreloaded = false
  • Removeremoved = true
  • database.Delete(key) (a no-op)
  • database.Insert(key, value)

Now your cache is out of sync with the underlying database: the cache contains no mapping for key, but the underlying database maps it to value.

I suspect that you'll find this sort of insert/delete race in most concrete examples, and the fix is generally to add some other exclusion mechanism (for example, a sync.Mutex) on the slow path, and to recheck the sync.Map once more once the exclusive lock has been acquired. In that case, the Load and Delete operations on the map no longer need to be atomic (since they're synchronized externally).

@wkonkel
Copy link
Author

wkonkel commented Aug 22, 2019

By that logic, shouldn't LoadOrStore be removed since it enables similar behavior if 2 goroutines ran in parallel:

  • [1] LoadOrStoreloaded = false
  • [2] Delete
  • [1] if loaded { ... }

By the time if loaded { ... } is evaluated, the underlying sync.Map has changed.

Ultimately, I don't think there is an expectation that the loaded return value from LoadOrStore represents the current state of the Map but rather just what happened when LoadOrStore was called. Similarly, the removed return value from the proposed Remove would have the same expected behavior. It doesn't represent current state but rather the result of the function call. If a guarantee of current state is needed for either LoadOrStore or Remove, then sync.Mutex is the only approach.

In my specific use case, deletes happen substantially later than adds, so there is never Store-Delete contention. Instead, I'm trying to prevent hundreds of goroutines from triggering the same Add or Remove query from running. I currently use LoadOrStore to solve for the contentious Add use case, but am forced to use sync.Mutex to solve for contentious Delete.

@ianlancetaylor ianlancetaylor removed the WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. label Sep 3, 2019
@ianlancetaylor
Copy link
Contributor

Ping @bcmills

@bcmills
Copy link
Contributor

bcmills commented Sep 11, 2019

Ok, I think I can see what you mean. For example, you may have a wave of Store calls, followed by some external synchronization point, followed by a wave of Remove calls, and at that point you're guaranteed that none of the Removes races with a Store.

In that case, I'd be ok with a new method with a signature along the lines of:

func (m *Map) Remove(key interface{}) (prevValue interface{}, removed bool)

@rsc
Copy link
Contributor

rsc commented Sep 25, 2019

Why call it Remove? Then we'd have Delete and Remove, with no obvious distinction between them (but a big difference).

We have LoadOrStore already; why is this not LoadAndDelete?

@bcmills
Copy link
Contributor

bcmills commented Sep 25, 2019

Why call it Remove?

For me “delete” carries the connotation of destroying the thing to be deleted, especially “by blotting out, cutting out, or erasing”. The proposed function erases a key or entry from the map, but does not erase the corresponding value; in contrast, a Store stores the value (not just the key), and a Delete does blot out (at least the reference to) the value.

In contrast, “remove” carries the connotation of “[changing] the location, position, station, or residence of” the thing, which is what we are doing with the proposed function: changing the location (of the reference to the value) from the map to the caller.

We have LoadOrStore already; why is this not LoadAndDelete?

I would be ok with naming it LoadAndDelete, although that seems needlessly verbose.

@wkonkel
Copy link
Author

wkonkel commented Sep 26, 2019

My preference would be naming this Remove and also deprecating Delete.

@bcmills
Copy link
Contributor

bcmills commented Sep 26, 2019

@wkonkel, I don't think we need to deprecate Delete. It can potentially be more efficient than Remove when the caller does not need the deleted reference.

@rsc rsc changed the title proposal: sync: Map should provide DeleteWithLoad which returns loaded value and boolean proposal: sync: add new Map method LoadAndDelete Oct 2, 2019
@rsc
Copy link
Contributor

rsc commented Oct 2, 2019

@bcmills, I admire your precision with the different meanings of delete and remove but I don't think many users will see that distinction.
@wkonkel, this is an unusual operation - there are plenty of times you may just want delete, and it is more efficient as Bryan pointed out.

I retitled this to be about adding LoadAndDelete.

Are there any objections to adding LoadAndDelete?

@rsc
Copy link
Contributor

rsc commented Oct 2, 2019

Rereading the thread, based on this discussion it seems like this is a likely accept.

Leaving open for a week for final comments.

@rsc rsc modified the milestones: Proposal, Go1.14 Oct 9, 2019
@rsc rsc changed the title proposal: sync: add new Map method LoadAndDelete sync: add new Map method LoadAndDelete Oct 9, 2019
@rsc
Copy link
Contributor

rsc commented Oct 9, 2019

Accepted.

@rsc rsc removed this from the Go1.14 milestone Oct 9, 2019
@rsc rsc added this to the Backlog milestone Oct 9, 2019
@gopherbot
Copy link
Contributor

Change https://golang.org/cl/205899 mentions this issue: sync: add new Map method LoadAndDelete

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

5 participants