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 methods CompareAndSwap, CompareAndDelete, Swap #51972

Closed
9072997 opened this issue Mar 27, 2022 · 20 comments
Closed

sync: add new Map methods CompareAndSwap, CompareAndDelete, Swap #51972

9072997 opened this issue Mar 27, 2022 · 20 comments
Assignees
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FrozenDueToAge Proposal Proposal-Accepted
Milestone

Comments

@9072997
Copy link

9072997 commented Mar 27, 2022

I propose adding a new method on sync.Map similar to atomic.Value's Swap() method. I think either the name LoadAndStore() to match the existing LoadOrStore or Swap() to match atomic.Value would make sense. The function signature would look something like this

func (m *Map) LoadAndStore(key, newValue any) (previous any, loaded bool)

I think the fact that this already exists in atomic.Value is a good argument that there is a use case for it. The same thing could be achieved by creating a sync.Map of atomic.Values, but that is a lot of type-assertion, and I have to stare at it pretty hard to make sure it's free of race conditions. My specific use case is basically de-bouncing abuse reports. If a worker detects abuse from a client it would

lastReport, hasReportHistory := lastReportTimes.LoadAndStore(clientIP, time.Now())
if hasReportHistory && time.Since(lastReport.(time.Time)) < time.Hour {
    log("not re-sending abuse report")
    return
}
sendAbuseReport(clientIP)
@gopherbot gopherbot added this to the Proposal milestone Mar 27, 2022
@ianlancetaylor
Copy link
Member

CC @bcmills

@rsc rsc changed the title proposal: sync: add new Map method LoadAndStore proposal: sync: add new Map method Swap Mar 30, 2022
@rsc
Copy link
Contributor

rsc commented Mar 30, 2022

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

@rsc
Copy link
Contributor

rsc commented Apr 6, 2022

@bcmills, what do you think?

@bcmills
Copy link
Contributor

bcmills commented Apr 6, 2022

func (m *Map) Swap(key, value any) (previous any, loaded bool) seems like a reasonable addition to me.

It has the right granularity to fit with the other Map methods (only synchronizes access to a specific key, and has similar atomicity properties to LoadOrStore), and it enables coding patterns that are otherwise complicated or inefficient.

@bcmills
Copy link
Contributor

bcmills commented Apr 6, 2022

We may also want to consider CompareAndSwap and CompareAndDelete at the same time to parallel (*atomic.Value).CompareAndSwap, which was added along with Swap in proposal #39351. That might look like:

// CompareAndSwap swaps the old and new values for key
// if the value stored in the map is equal to old.
// The old value must be of a comparable type.
//
// If old is the nil interface value, the swap will occur if either there
// is no existing value for the key or the existing value is also the
// nil interface.
func (m *Map) CompareAndSwap(key, old, new any) (swapped bool)

// CompareAndDelete deletes the entry for key if its value is equal to old.
// The old value must be of a comparable type.
//
// If there is no current value for key in the map, CompareAndDelete
// returns false (even if the old value is the nil interface value).
func (m *Map) CompareAndDelete(key, old any) (deleted bool)

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/399094 mentions this issue: sync: add new Map method Swap

@rsc rsc changed the title proposal: sync: add new Map method Swap proposal: sync: add new Map methods CompareAndSwap, CompareAndDelete, Swap Apr 13, 2022
@rsc
Copy link
Contributor

rsc commented Apr 13, 2022

Does anyone object to adding Swap, CompareAndSwap, and CompareAndDelete?

@changkun
Copy link
Member

changkun commented Apr 14, 2022

While prototyping the CompareAndDelete, it got me thinking: is it really make sense to have CompareAndDelete?

sync.Map has two maps inside and is optimized for read-most context.

Since we don't have an atomic compare and delete primitive. What can we do to the read map to compare the old value, and delete it atomically? I could not yet make sense out of this implementation:

func (m *Map) CompareAndDelete(key, old any) (deleted bool) {
	read, _ := m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
		if e.tryCompareAndSwap(&old, nil) {
			// Here is clearly(?) non-atomic
			// what if something happens between the above CAS and below delete?
			// Is it possible?
			delete(read.m, key)
			deleted = true
			return
		}
	}

	m.mu.Lock()
	...
}

Or is this something I am not going in the right direction of implementation? It looks like to me that we have to lock the entire Map to proceed? Am I overthinking here? What is the fast path in this case?

@bcmills
Copy link
Contributor

bcmills commented Apr 18, 2022

@changkun, the use case for CompareAndDelete is to delete, say, stale entries from a cache (which otherwise could have the right properties).

If the key is a hit in the read-only map, the entry will still remain but be marked as deleted.

@rsc
Copy link
Contributor

rsc commented May 4, 2022

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

@rsc
Copy link
Contributor

rsc commented May 11, 2022

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

@rsc rsc changed the title proposal: sync: add new Map methods CompareAndSwap, CompareAndDelete, Swap sync: add new Map methods CompareAndSwap, CompareAndDelete, Swap May 11, 2022
@rsc rsc modified the milestones: Proposal, Backlog May 11, 2022
@bcmills
Copy link
Contributor

bcmills commented May 13, 2022

In #51972 (comment) I suggested that a CompareAndSwap wild old == nil should succeed if there is no existing key in the map. However, reading @changkun's implementation in https://go.dev/cl/399094 I think it probably makes more sense to never swap with a nonexistent key.

Here's my thinking: if we use a stricter CompareAndSwap that requires the key to exist, then the more lax semantics can be implemented in terms of that:

func StoreOrCompareAndSwapNil(m *sync.Map, key, new interface) (swapped bool) {
	old, loaded := m.LoadOrStore(key, new)
	if !loaded {
		return true  // Swapped new against “no key”.
	}
	if old != nil {
		return false  // Old value was not the nil interface value.
	}
	// Try to swap new against an explicit, existing nil.
	return m.CompareAndSwap(key, old, new)
}

The reverse does not hold, so the stricter CompareAndSwap seems more expressive overall.

Moreover, the Map operations need to know about explicit nil values for the other methods anyway, so it's not like the implementation gets any simpler if we use the lax semantics instead.

@bcmills
Copy link
Contributor

bcmills commented May 13, 2022

The stricter CompareAndSwap (that never swaps against “no existing value”) also better matches CompareAndDelete, which never deletes a nonexistent value.

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 7, 2022
@prattmic prattmic moved this to Triage Backlog in Go Compiler / Runtime Jul 25, 2022
@dsnet
Copy link
Member

dsnet commented Aug 1, 2022

If a generic version of sync.Map gets added, I would expect certain methods that rely on comparability of the value type to be expressed as functions, rather than methods.

For example, this is the signature I would expect for a generic map:

type Map[K comparable, V any] struct { ... }

Given that signature, the following methods are not type safe:

func (m *Map[K, V]) CompareAndSwap(key K, old, new V) (swapped bool)
func (m *Map[K, V]) CompareAndDelete(key K, old V) (deleted bool)

However, we could do:

func CompareAndSwap[K, V comparable](m *Map[K, V], key K, old, new V) (swapped bool)
func CompareAndDelete[K, V comparable](m *Map[K, V], key K, old V) (deleted bool)

where it forces the caller to provide a generic Map that have a comparable value type.

@rsc rsc moved this to Accepted in Proposals Aug 10, 2022
@rsc rsc added this to Proposals Aug 10, 2022
@changkun
Copy link
Member

What was the conclusion by #48287? When did it close? How will it impact the design of a generic sync.Map?

@ianlancetaylor
Copy link
Member

#48287 is not yet resolved. There is no conclusion.

Repository owner moved this from Triage Backlog to Done in Go Compiler / Runtime Nov 15, 2022
@bcmills
Copy link
Contributor

bcmills commented Nov 15, 2022

Thinking about the matrix of operations, it appears to be complete: we now have operations that support atomically changing a map entry from any one of {no value, any value, specific value} to any one of { value, no value } in a way that allows the caller to confirm the state of the entry prior to the change.

From To Operation
no value no value Load
no value value LoadOrStore
any value no value LoadAndDelete
any value value Swap
specific value no value CompareAndDelete
specific value value CompareAndSwap

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/450797 mentions this issue: doc/go1.20: document new sync.Map methods

gopherbot pushed a commit that referenced this issue Nov 15, 2022
For #51972.

Change-Id: I86dcd8abc3b62e20b524541327af2cc891cb251d
Reviewed-on: https://go-review.googlesource.com/c/go/+/450797
Reviewed-by: Ian Lance Taylor <iant@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Auto-Submit: Bryan Mills <bcmills@google.com>
Run-TryBot: Bryan Mills <bcmills@google.com>
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/459715 mentions this issue: sync: document memory model for Swap/CompareAnd{Swap,Delete} in Map

gopherbot pushed a commit that referenced this issue Jan 20, 2023
CL 381316 documented the memory model of Map's APIs. However, the newly
introduced Swap, CompareAndSwap, and CompareAndDelete are missing from
this documentation as CL 399094 did not add this info.

This CL specifies the defined read/write operations of the new Map APIs.

For #51972

Change-Id: I519a04040a0b429a3f978823a183cd62e42c90ae
Reviewed-on: https://go-review.googlesource.com/c/go/+/459715
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
Run-TryBot: Changkun Ou <mail@changkun.de>
Auto-Submit: Bryan Mills <bcmills@google.com>
Reviewed-by: Bryan Mills <bcmills@google.com>
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/463416 mentions this issue: [release-branch.go1.20] sync: document memory model for Swap/CompareAnd{Swap,Delete} in Map

gopherbot pushed a commit that referenced this issue Jan 25, 2023
…nd{Swap,Delete} in Map

CL 381316 documented the memory model of Map's APIs. However, the newly
introduced Swap, CompareAndSwap, and CompareAndDelete are missing from
this documentation as CL 399094 did not add this info.

This CL specifies the defined read/write operations of the new Map APIs.

For #51972

Change-Id: I519a04040a0b429a3f978823a183cd62e42c90ae
Reviewed-on: https://go-review.googlesource.com/c/go/+/459715
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
Run-TryBot: Changkun Ou <mail@changkun.de>
Auto-Submit: Bryan Mills <bcmills@google.com>
Reviewed-by: Bryan Mills <bcmills@google.com>
(cherry picked from commit f07910b)
Reviewed-on: https://go-review.googlesource.com/c/go/+/463416
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
Auto-Submit: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Changkun Ou <mail@changkun.de>
@rsc rsc removed this from Proposals Nov 16, 2023
@golang golang locked and limited conversation to collaborators Jan 25, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FrozenDueToAge Proposal Proposal-Accepted
Projects
None yet
Development

No branches or pull requests

7 participants