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

proposal: builtin: First-Class Cancellation #10562

Closed
invino4 opened this issue Apr 23, 2015 · 6 comments
Closed

proposal: builtin: First-Class Cancellation #10562

invino4 opened this issue Apr 23, 2015 · 6 comments

Comments

@invino4
Copy link

@invino4 invino4 commented Apr 23, 2015

Go should have a first-class cancellation pattern (in much the same way that it has a first class error pattern). The cancellation pattern should meet the following requirements:

  1. Very light-weight: Such that it can be used to control cancellation at a very fine grained level. e.g. it should be perfectly reasonable for every goroutine started in an application to have a cancellation token. It should not be unreasonable for many individual methods to have cancellation.
  2. Least Privilege: The ability to observe cancellation and the ability to cause cancellation MUST be independent.
  3. Broadcast: It MUST be possible for multiple consumers to observe the same cancellation token without impacting each other.
  4. Idempotent: A cancellation token, once cancelled, should never become uncancelled.
  5. Concurrency Safe: It MUST be possible for multiple consumers to observe cancellation in parallel without additional synchronization.
  6. Asynchronous: Cancellation of the token only guarantees that all observes will eventually see the cancellation, NOT that cancellation of a tree of computation will be cancelled synchronously.
  7. Synchronous Polling: It MUST be possible to synchronous poll whether cancellation has occurred. This allows long running computations to periodically check whether they should stop running even if they never block on IO.
  8. Blocking Composition: It MUST be possible to compose a cancellation token with blocking I/O in a select statement. e.g. block on a data channel value or cancellation, which ever happens first.
  9. Boolean Composition: It MUST be possible to combine cancellation token in an and or or manner such that you get a new cancellation token that becomes cancelled when its inputs become cancelled.
  10. Hierarchical Composition: It MUST be possible to create child cancellation tokens that cancel when their parent cancels, but can also be cancelled independently without affect their parent.
  11. IO Composition: It MUST be possible to create RPC contexts, HTTP contexts, etc. that are linked to a standard cancellation token as its parent.
  12. Debuggable: Cancellation SHOULD provide a diagnostic message that can be used in logging or other debugging to indicate the reason a computation was asked to cancel.

What Is It For

Cancellation allows a tree or pipeline of computation whose output is no longer needed to be terminated. Go makes describing pipelines of computation easy. Goroutines representing each stage of such a pipeline link together via channels to form a computational pipeline whose final channel delivers the final result of the computation. Once a pipeline has produced sufficient output for the final consumer the pipeline needs to be torn down. Sometimes this corresponds to natural boundaries of data being produced but sometimes it doesn't (e.g. when errors are encountered or the consumer disconnects abruptly).

What

I propose that cancellation be implemented like errors through an interface of the following form:

type Cancel interface {
    // Returns a channel that is closed when signalled by the cancellation function.  
    // Guaranteed to return the same channel on each call 
    // (i.e. can be safely cached by the caller.)
    Done() <-chan struct{}
    // Err returns the error provided to the cancellation function.  
    // If not yet signalled always returns nil.  
    // (i.e. can be called at any time to poll the state of cancellation.)
    Err() error
}

// CancelFunc is called to signal that cancellation should begin.  
// Signalling the cancellation token is synchronous and atomic.
// CancelFunc is idempotent but only the first reason is preserved.  
// If reason is nil, CancelFunc panics.
type CancelFunc func(reason error)

// NewCancel creates a new cancellation signal and a cancellation 
// function to cancel it.
func NewCancel() (Cancel, CancelFunc) { ... }

// WithParent creates a new cancellation signal and a cancellation 
// function to cancel it.  The resulting token is cancelled with either
// the cancellation function is called or the parent becomes cancelled.
func WithParent(parent Cancel) (Cancel, CancelFunc) { ... }

// And creates a new cancellation signal that becomes cancelled when
// both of its inputs become cancelled.
func And(left Cancel, right Cancel) Cancel { ... }

// Or creates a new cancellation signal that becomes cancelled when
// either of its inputs become cancelled.
func Or(left Cancel, right Cancel) Cancel { ... }

This interface allows for implementations that meet all of the above specifications. Because the Done() channel's write endpoint is closely held in this design, it is possible for a language runtime implementation to use a cheaper channel implementation that allows for Boolean and Hierarchical composition without actually allocating a goroutine to wait on the inputs.

Why It Should Be Part Of The Language

For most of the same reasons that error is part of the language. First-class treatment of cancellation will guarantee the proper level of composability that an external implementation cannot achieve.

First-class treatment allows the core libraries to also level the pattern.

As mentioned above, a language runtime level implementation can be significantly less expensive for composition that would be possible by a pure library implementation. A low-cost enables its ubiquity as it allows it to be used in domains that simply would not permit a more expensive implementation.

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Apr 23, 2015

I don't see any proposed language changes. Do you mean it should be part of the Go standard library?

Otherwise, it just seems to be an extension to the golang.org/x/net/context API, namely adding the And and Or functions. Maybe you can elaborate on why those are useful.

@invino4
Copy link
Author

@invino4 invino4 commented Apr 23, 2015

The interface "error" is part of the language spec, not just the standard library. E.g. it doesn't have a package and is documented in the pseudo-package "builtin". The interface cancel should have the same treatment.

I agree there is considerable overlap between cancellation and network contexts. Networks contexts are, however, a proper superset of cancellation. They add deadlines and timeouts which require a notion of time that is not universal. They add "values" which provide the additional context of an RPC or networking call. (The latter being where the name "context" comes from.) These additions, while important in their domain, are not required elements of the most basic cancellation framework and should be stripped from the core language feature.

It is certainly reasonable that net/context.Context would "derive from" the cancel interface. Since cancel is a proper subset of its definition any context.Context would, of course, already implement cancel even if the definition were not changed. This provides for a convenient backward compatibility in the deployment of the new language feature.

@minux
Copy link
Member

@minux minux commented Apr 23, 2015

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Apr 23, 2015

Closing until there's an agreement to do something.

Like Minux alluded, Go uses mailing lists for discussion unlike many Github projects which converse in Issues. Either model is fine, but historically we've had and used mailing lists.

We can reopen this if/when the time comes.

@bradfitz bradfitz closed this Apr 23, 2015
@mikioh mikioh changed the title First-Class Cancellation builtin: First-Class Cancellation Apr 25, 2015
@dzrw
Copy link

@dzrw dzrw commented Aug 19, 2015

Can someone add a link to the relevant mailing list thread? I came here from Google looking for cancellation token support.

@mikioh
Copy link
Contributor

@mikioh mikioh commented Aug 21, 2015

@mikioh mikioh changed the title builtin: First-Class Cancellation proposal: builtin: First-Class Cancellation Aug 21, 2015
@golang golang locked and limited conversation to collaborators Aug 22, 2016
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
7 participants