cockroach: Index | Files

package spanlatch

import ""

Package spanlatch provides a latch management structure for serializing access to keys and key ranges. Latch acquisitions affecting keys or key ranges must wait on already-acquired latches which overlap their key range to be released.

The evolution of complexity can best be understood as a series of incremental changes, each in the name of increased lock granularity to reduce contention and enable more concurrency between requests. The structure can trace its lineage back to a simple sync.Mutex. From there, the structure evolved through the following progression:

* The structure began by enforcing strict mutual exclusion for access to any
  keys. Conceptually, it was a sync.Mutex.
* Concurrent read-only access to keys and key ranges was permitted. Read and
  writes were serialized with each other, writes were serialized with each other,
  but no ordering was enforced between reads. Conceptually, the structure became
  a sync.RWMutex.
* The structure became key range-aware and concurrent access to non-overlapping
  key ranges was permitted. Conceptually, the structure became an interval
  tree of sync.RWMutexes.
* The structure became timestamp-aware and concurrent access of non-causal
  read and write pairs was permitted. The effect of this was that reads no
  longer waited for writes at higher timestamps and writes no longer waited
  for reads at lower timestamps. Conceptually, the structure became an interval
  tree of timestamp-aware sync.RWMutexes.


Package Files

doc.go latch_interval_btree.go list.go manager.go signal.go

type Guard Uses

type Guard struct {
    // contains filtered or unexported fields

Guard is a handle to a set of acquired latches. It is returned by Manager.Acquire and accepted by Manager.Release.

type Manager Uses

type Manager struct {
    // contains filtered or unexported fields

A Manager maintains an interval tree of key and key range latches. Latch acquisitions affecting keys or key ranges must wait on already-acquired latches which overlap their key ranges to be released.

Latch acquisition attempts invoke Manager.Acquire and provide details about the spans that they plan to touch and the timestamps they plan to touch them at. Acquire inserts the latch into the Manager's tree and waits on prerequisite latch attempts that are already tracked by the Manager. Manager.Acquire blocks until the latch acquisition completes, at which point it returns a Guard, which is scoped to the lifetime of the latch ownership.

When the latches are no longer needed, they are released by invoking Manager.Release with the Guard returned when the latches were originally acquired. Doing so removes the latches from the Manager's tree and signals to dependent latch acquisitions that they no longer need to wait on the released latches.

Manager is safe for concurrent use by multiple goroutines. Concurrent access is made efficient using a copy-on-write technique to capture immutable snapshots of the type's inner btree structures. Using this strategy, tasks requiring mutual exclusion are limited to updating the type's trees and grabbing snapshots. Notably, scanning for and waiting on prerequisite latches is performed outside of the mutual exclusion zone. This means that the work performed under lock is linear with respect to the number of spans that a latch acquisition declares but NOT linear with respect to the number of other latch attempts that it will wait on.

Manager's zero value can be used directly.

func Make Uses

func Make(stopper *stop.Stopper, slowReqs *metric.Gauge) Manager

Make returns an initialized Manager. Using this constructor is optional as the type's zero value is valid to use directly.

func (*Manager) Acquire Uses

func (m *Manager) Acquire(ctx context.Context, spans *spanset.SpanSet) (*Guard, error)

Acquire acquires latches from the Manager for each of the provided spans, at the specified timestamp. In doing so, it waits for latches over all overlapping spans to be released before returning. If the provided context is canceled before the method is done waiting for overlapping latches to be released, it stops waiting and releases all latches that it has already acquired.

It returns a Guard which must be provided to Release.

func (*Manager) Info Uses

func (m *Manager) Info() (global, local kvserverpb.LatchManagerInfo)

Info returns information about the state of the Manager.

func (*Manager) Release Uses

func (m *Manager) Release(lg *Guard)

Release releases the latches held by the provided Guard. After being called, dependent latch acquisition attempts can complete if not blocked on any other owned latches.

Package spanlatch imports 18 packages (graph) and is imported by 2 packages. Updated 2020-08-12. Refresh now. Tools for package owners.