storage

package
v0.0.0-...-7e18a6a Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 13, 2015 License: Apache-2.0 Imports: 28 Imported by: 0

Documentation

Overview

Package storage provides access to the Store and Range abstractions. Each Cockroach node handles one or more stores, each of which multiplexes to one or more ranges, identified by [start, end) keys. Ranges are contiguous regions of the keyspace. Each range implements an instance of the Raft consensus algorithm to synchronize participating range replicas.

Each store is represented by a single engine.Engine instance. The ranges hosted by a store all have access to the same engine, but write to only a range-limited keyspace within it. Ranges access the underlying engine via the MVCC interface, which provides historical versioned values.

Index

Constants

View Source 
const (
	// UserRoot is the username for the root user.
	UserRoot = "root"
	// GCResponseCacheExpiration is the expiration duration for response
	// cache entries.
	GCResponseCacheExpiration = 1 * time.Hour
)

Variables

View Source 
var (
	// DefaultHeartbeatInterval is how often heartbeats are sent from the
	// transaction coordinator to a live transaction. These keep it from
	// being preempted by other transactions writing the same keys. If a
	// transaction fails to be heartbeat within 2x the heartbeat interval,
	// it may be aborted by conflicting txns.
	DefaultHeartbeatInterval = 5 * time.Second
)
View Source 
var TestingCommandFilter func(string, proto.Request, proto.Response) bool

TestingCommandFilter may be set in tests to intercept the handling of commands and artificially generate errors. Return true to terminate processing with the filled-in response, or false to continue with regular processing. Note that in a multi-replica test this filter will be run once for each replica and must produce consistent results each time. Should only be used in tests in the storage package but needs to be exported due to circular import issues.

Functions

func MergeRangeAddressing 

func MergeRangeAddressing(db *client.KV, left, merged *proto.RangeDescriptor) error

MergeRangeAddressing removes subsumed meta1 and meta2 range addressing records caused by merging and updates the records for the new merged range. Left is the range descriptor for the "left" range before merging and merged describes the left to right merge.

func ReplicaSetsEqual 

func ReplicaSetsEqual(a, b []proto.Replica) bool

ReplicaSetsEqual is used in AdminMerge to ensure that the ranges are all collocate on the same set of replicas.

func SplitRangeAddressing 

func SplitRangeAddressing(db *client.KV, left, right *proto.RangeDescriptor) error

SplitRangeAddressing creates (or overwrites if necessary) the meta1 and meta2 range addressing records for the left and right ranges caused by a split.

func UsesTimestampCache 

func UsesTimestampCache(method string) bool

UsesTimestampCache returns true if the method affects or is affected by the timestamp cache.

Types

type CommandQueue 

type CommandQueue struct {
	// contains filtered or unexported fields
}

A CommandQueue maintains an interval tree of keys or key ranges for executing commands. New commands affecting keys or key ranges must wait on already-executing commands which overlap their key range.

Before executing, a command invokes GetWait() to initialize a WaitGroup with the number of overlapping commands which are already running. The wait group is waited on by the caller for confirmation that all overlapping, pending commands have completed and the pending command can proceed.

After waiting, a command is added to the queue's already-executing set via Add(). Add accepts a parameter indicating whether the command is read-only. Read-only commands don't need to wait on other read-only commands, so the wait group returned via GetWait() doesn't include read-only on read-only overlapping commands as an optimization.

Once commands complete, Remove() is invoked to remove the executing command and decrement the counts on any pending WaitGroups, possibly signaling waiting commands who were gated by the executing command's affected key(s).

CommandQueue is not thread safe.

func NewCommandQueue 

func NewCommandQueue() *CommandQueue

NewCommandQueue returns a new command queue.

func (*CommandQueue) Add 

func (cq *CommandQueue) Add(start, end proto.Key, readOnly bool) interface{}

Add adds a command to the queue which affects the specified key range. If end is empty, it is set to start.Next(), meaning the command affects a single key. The returned interface is the key for the command queue and must be re-supplied on subsequent invocation of Remove().

Add should be invoked after waiting on already-executing, overlapping commands via the WaitGroup initialized through GetWait().

func (*CommandQueue) Clear 

func (cq *CommandQueue) Clear()

Clear removes all executing commands, signaling any waiting commands.

func (*CommandQueue) GetWait 

func (cq *CommandQueue) GetWait(start, end proto.Key, readOnly bool, wg *sync.WaitGroup)

GetWait initializes the supplied wait group with the number of executing commands which overlap the specified key range. If end is empty, end is set to start.Next(), meaning the command affects a single key. The caller should call wg.Wait() to wait for confirmation that all gating commands have completed or failed. readOnly is true if the requester is a read-only command; false for read-write.

func (*CommandQueue) Remove 

func (cq *CommandQueue) Remove(key interface{})

Remove is invoked to signal that the command associated with the specified key has completed and should be removed. Any pending commands waiting on this command will be signaled if this is the only command upon which they are still waiting.

Remove is invoked after a mutating command has been committed to the Raft log and applied to the underlying state machine. Similarly, Remove is invoked after a read-only command has been executed against the underlying state machine.

type FindStoreFunc 

type FindStoreFunc func(proto.Attributes) ([]*StoreDescriptor, error)

FindStoreFunc finds the disks in a datacenter that have the requested attributes.

type IDAllocator 

type IDAllocator struct {
	// contains filtered or unexported fields
}

An IDAllocator is used to increment a key in allocation blocks of arbitrary size starting at a minimum ID.

func NewIDAllocator 

func NewIDAllocator(idKey proto.Key, db *client.KV, minID int64, blockSize int64) *IDAllocator

NewIDAllocator creates a new ID allocator which increments the specified key in allocation blocks of size blockSize, with allocated IDs starting at minID. Allocated IDs are positive integers.

func (*IDAllocator) Allocate 

func (ia *IDAllocator) Allocate() int64

Allocate allocates a new ID from the global KV DB. If multiple

type NodeDescriptor 

type NodeDescriptor struct {
	NodeID  proto.NodeID
	Address net.Addr
	Attrs   proto.Attributes // node specific attributes (e.g. datacenter, machine info)
}

NodeDescriptor holds details on node physical/network topology.

type NotBootstrappedError 

type NotBootstrappedError struct{}

A NotBootstrappedError indicates that an engine has not yet been bootstrapped due to a store identifier not being present.

func (*NotBootstrappedError) Error 

func (e *NotBootstrappedError) Error() string

Error formats error.

type PrefixConfig 

type PrefixConfig struct {
	Prefix    proto.Key   // the prefix the config affects
	Canonical proto.Key   // the prefix for the canonical config, if applicable
	Config    interface{} // the config object
}

PrefixConfig relate a string prefix to a config object. Config objects include accounting, permissions, and zones. PrefixConfig objects are the constituents of PrefixConfigMap objects. In order to support binary searches of hierarchical prefixes (see the comments in NewPrefixConfigMap), PrefixConfig objects are additionally added to a PrefixConfigMap to demarcate the end of a prefix range. Such end-of-range sentinels need to refer back to the next "higher-up" prefix in the hierarchy (many times this is the default prefix which covers the entire range of keys). The Canonical key refers to this "higher-up" PrefixConfig by specifying its prefix so it can be binary searched from within a PrefixConfigMap.

type PrefixConfigMap 

type PrefixConfigMap []*PrefixConfig

PrefixConfigMap is a slice of prefix configs, sorted by prefix. Along with various accessor methods, the config map also contains additional prefix configs in the slice to account for the ends of prefix ranges.

func NewPrefixConfigMap 

func NewPrefixConfigMap(configs []*PrefixConfig) (PrefixConfigMap, error)

NewPrefixConfigMap creates a new prefix config map and sorts the entries by key prefix and then adds additional entries to mark the ends of each key prefix range. For example, if the map contains entries for: 

"/":          config1
"/db1":       config2
"/db1/table": config3
"/db3":       config4

...then entries will be added for: 

"/db1/tablf": config2
"/db2":       config1
"/db4":       config1

These additional entries allow for simple lookups by prefix and provide a way to split a range by prefixes which affect it. This last is necessary for accounting and zone configs; ranges must not span accounting or zone config boundaries.

Similarly, if the map contains successive prefix entries: 

"/":           config1
"/db1":        config2
"/db1/table1": config3
"/db1/table2": config4
"/db2":        config5

...then entries will be added for (note that we don't add a redundant entry for /db2 or /db1/table2).: 

"/db1/table3": config2
"/db3":        config1

func (PrefixConfigMap) Len 

func (p PrefixConfigMap) Len() int

Implementation of sort.Interface.

func (PrefixConfigMap) Less 

func (p PrefixConfigMap) Less(i, j int) bool

func (PrefixConfigMap) MatchByPrefix 

func (p PrefixConfigMap) MatchByPrefix(key proto.Key) *PrefixConfig

MatchByPrefix returns the longest matching PrefixConfig. If the key specified does not match an existing prefix, a panic will result. Based on the comments in build(), that example will have a final list of PrefixConfig entries which look like: 

"/":          config1
"/db1":       config2
"/db1/table": config3
"/db1/tablf": config2
"/db2":       config1
"/db3":       config4
"/db4":       config1

To find the longest matching prefix, we take the lower bound of the specified key.

func (PrefixConfigMap) MatchesByPrefix 

func (p PrefixConfigMap) MatchesByPrefix(key proto.Key) []*PrefixConfig

MatchesByPrefix returns a list of PrefixConfig objects with prefixes satisfying the specified key. The results are returned in order of longest matching prefix to shortest.

func (PrefixConfigMap) SplitRangeByPrefixes 

func (p PrefixConfigMap) SplitRangeByPrefixes(start, end proto.Key) ([]*RangeResult, error)

SplitRangeByPrefixes returns a list of key ranges with corresponding configs. The split is done using matching prefix config entries. For example, consider the following set of configs and prefixes: 

/:    config1
/db1: config2

A range containing keys from /0 - /db3 will map to the following split ranges and corresponding configs: 

/0   - /db1: config1
/db1 - /db2: config2
/db2 - /db3: config1

After calling PrefixConfigMap.build(), our prefixes will look like: 

/:    config1
/db1: config2
/db2: config1

The algorithm is straightforward for splitting a range by existing prefixes. Lookup start key; that is first config. Lookup end key: that is last config. We then step through the intervening PrefixConfig records and create a RangeResult for each.

func (PrefixConfigMap) Swap 

func (p PrefixConfigMap) Swap(i, j int)

func (PrefixConfigMap) VisitPrefixes 

func (p PrefixConfigMap) VisitPrefixes(start, end proto.Key,
	visitor func(start, end proto.Key, config interface{}) (bool, error)) error

VisitPrefixes invokes the visitor function for each prefix overlapped by the specified key range [start, end). If visitor returns done=true or an error, the visitation is halted.

func (PrefixConfigMap) VisitPrefixesHierarchically 

func (p PrefixConfigMap) VisitPrefixesHierarchically(key proto.Key,
	visitor func(start, end proto.Key, config interface{}) (bool, error)) error

VisitPrefixesHierarchically invokes the visitor function for each prefix matching the key argument, from longest matching prefix to shortest. If visitor returns done=true or an error, the visitation is halted.

type Range 

type Range struct {
	sync.RWMutex // Protects the following fields (and Desc)
	// contains filtered or unexported fields
}

A Range is a contiguous keyspace with writes managed via an instance of the Raft consensus algorithm. Many ranges may exist in a store and they are unlikely to be contiguous. Ranges are independent units and are responsible for maintaining their own integrity by replacing failed replicas, splitting and merging as appropriate.

func NewRange 

func NewRange(desc *proto.RangeDescriptor, rm RangeManager) (*Range, error)

NewRange initializes the range using the given metadata.

func (*Range) AddCmd 

func (r *Range) AddCmd(method string, args proto.Request, reply proto.Response, wait bool) error

AddCmd adds a command for execution on this range. The command's affected keys are verified to be contained within the range and the range's leadership is confirmed. The command is then dispatched either along the read-only execution path or the read-write Raft command queue. If wait is false, read-write commands are added to Raft without waiting for their completion.

func (*Range) AdminMerge 

func (r *Range) AdminMerge(args *proto.AdminMergeRequest, reply *proto.AdminMergeResponse)

AdminMerge extends the range to subsume the range that comes next in the key space. The range being subsumed is provided in args.SubsumedRange. The EndKey of the subsuming range must equal the start key of the range being subsumed. The merge is performed inside of a distributed transaction which writes the updated range descriptor for the subsuming range and deletes the range descriptor for the subsumed one. It also updates the range addressing metadata. The handover of responsibility for the reassigned key range is carried out seamlessly through a merge trigger carried out as part of the commit of that transaction. A merge requires that the two ranges are collocate on the same set of replicas.

func (*Range) AdminSplit 

func (r *Range) AdminSplit(args *proto.AdminSplitRequest, reply *proto.AdminSplitResponse)

AdminSplit divides the range into into two ranges, using either args.SplitKey (if provided) or an internally computed key that aims to roughly equipartition the range by size. The split is done inside of a distributed txn which writes updated and new range descriptors, and updates the range addressing metadata. The handover of responsibility for the reassigned key range is carried out seamlessly through a split trigger carried out as part of the commit of that transaction.

func (*Range) Append 

func (r *Range) Append(entries []raftpb.Entry) error

Append implements the multiraft.WriteableGroupStorage interface.

func (*Range) ApplySnapshot 

func (r *Range) ApplySnapshot(snap raftpb.Snapshot) error

ApplySnapshot implements the multiraft.WriteableGroupStorage interface.

func (*Range) ChangeReplicas 

func (r *Range) ChangeReplicas(changeType proto.ReplicaChangeType, replica proto.Replica) error

ChangeReplicas adds or removes a replica of a range. The change is performed in a distributed transaction and takes effect when that transaction is committed. When removing a replica, only the NodeID and StoreID fields of the Replica are used.

func (*Range) ConditionalPut 

func (r *Range) ConditionalPut(batch engine.Engine, ms *engine.MVCCStats, args *proto.ConditionalPutRequest, reply *proto.ConditionalPutResponse)

ConditionalPut sets the value for a specified key only if the expected value matches. If not, the return value contains the actual value.

func (*Range) Contains 

func (r *Range) Contains(batch engine.Engine, args *proto.ContainsRequest, reply *proto.ContainsResponse)

Contains verifies the existence of a key in the key value store.

func (*Range) ContainsKey 

func (r *Range) ContainsKey(key proto.Key) bool

ContainsKey returns whether this range contains the specified key. Read-lock the mutex to protect access to Desc, which might be changed concurrently via range split.

func (*Range) ContainsKeyRange 

func (r *Range) ContainsKeyRange(start, end proto.Key) bool

ContainsKeyRange returns whether this range contains the specified key range from start to end.

func (*Range) Delete 

func (r *Range) Delete(batch engine.Engine, ms *engine.MVCCStats, args *proto.DeleteRequest, reply *proto.DeleteResponse)

Delete deletes the key and value specified by key.

func (*Range) DeleteRange 

func (r *Range) DeleteRange(batch engine.Engine, ms *engine.MVCCStats, args *proto.DeleteRangeRequest, reply *proto.DeleteRangeResponse)

DeleteRange deletes the range of key/value pairs specified by start and end keys.

func (*Range) Desc 

func (r *Range) Desc() *proto.RangeDescriptor

Desc atomically returns the range's descriptor.

func (*Range) Destroy 

func (r *Range) Destroy() error

Destroy cleans up all data associated with this range.

func (*Range) EndTransaction 

func (r *Range) EndTransaction(batch engine.Engine, args *proto.EndTransactionRequest, reply *proto.EndTransactionResponse)

EndTransaction either commits or aborts (rolls back) an extant transaction according to the args.Commit parameter.

func (*Range) EnqueueMessage 

func (r *Range) EnqueueMessage(batch engine.Engine, args *proto.EnqueueMessageRequest, reply *proto.EnqueueMessageResponse)

EnqueueMessage enqueues a message (Value) for delivery to a recipient inbox.

func (*Range) EnqueueUpdate 

func (r *Range) EnqueueUpdate(batch engine.Engine, args *proto.EnqueueUpdateRequest, reply *proto.EnqueueUpdateResponse)

EnqueueUpdate sidelines an update for asynchronous execution. AccumulateTS updates are sent this way. Eventually-consistent indexes are also built using update queues. Crucially, the enqueue happens as part of the caller's transaction, so is guaranteed to be executed if the transaction succeeded.

func (*Range) Entries 

func (r *Range) Entries(lo, hi uint64) ([]raftpb.Entry, error)

Entries implements the raft.Storage interface. TODO(bdarnell): consider caching for recent entries, if rocksdb's builtin caching is insufficient.

func (*Range) FirstIndex 

func (r *Range) FirstIndex() (uint64, error)

FirstIndex implements the raft.Storage interface.

func (*Range) Get 

func (r *Range) Get(batch engine.Engine, args *proto.GetRequest, reply *proto.GetResponse)

Get returns the value for a specified key.

func (*Range) GetGCMetadata 

func (r *Range) GetGCMetadata() (*proto.GCMetadata, error)

GetGCMetadata reads the latest GC metadata for this range.

func (*Range) GetLastVerificationTimestamp 

func (r *Range) GetLastVerificationTimestamp() (proto.Timestamp, error)

GetLastVerificationTimestamp reads the timestamp at which the range's data was last verified.

func (*Range) GetReplica 

func (r *Range) GetReplica() *proto.Replica

GetReplica returns the replica for this range from the range descriptor.

func (*Range) Increment 

func (r *Range) Increment(batch engine.Engine, ms *engine.MVCCStats, args *proto.IncrementRequest, reply *proto.IncrementResponse)

Increment increments the value (interpreted as varint64 encoded) and returns the newly incremented value (encoded as varint64). If no value exists for the key, zero is incremented.

func (*Range) InitialState 

func (r *Range) InitialState() (raftpb.HardState, raftpb.ConfState, error)

InitialState implements the raft.Storage interface.

func (*Range) InternalGC 

func (r *Range) InternalGC(batch engine.Engine, ms *engine.MVCCStats, args *proto.InternalGCRequest, reply *proto.InternalGCResponse)

InternalGC iterates through the list of keys to garbage collect specified in the arguments. MVCCGarbageCollect is invoked on each listed key along with the expiration timestamp. The GC metadata specified in the args is persisted after GC.

func (*Range) InternalHeartbeatTxn 

func (r *Range) InternalHeartbeatTxn(batch engine.Engine, args *proto.InternalHeartbeatTxnRequest, reply *proto.InternalHeartbeatTxnResponse)

InternalHeartbeatTxn updates the transaction status and heartbeat timestamp after receiving transaction heartbeat messages from coordinator. Returns the updated transaction.

func (*Range) InternalMerge 

func (r *Range) InternalMerge(batch engine.Engine, ms *engine.MVCCStats, args *proto.InternalMergeRequest, reply *proto.InternalMergeResponse)

InternalMerge is used to merge a value into an existing key. Merge is an efficient accumulation operation which is exposed by RocksDB, used by Cockroach for the efficient accumulation of certain values. Due to the difficulty of making these operations transactional, merges are not currently exposed directly to clients. Merged values are explicitly not MVCC data.

func (*Range) InternalPushTxn 

func (r *Range) InternalPushTxn(batch engine.Engine, args *proto.InternalPushTxnRequest, reply *proto.InternalPushTxnResponse)

InternalPushTxn resolves conflicts between concurrent txns (or between a non-transactional reader or writer and a txn) in several ways depending on the statuses and priorities of the conflicting transactions. The InternalPushTxn operation is invoked by a "pusher" (the writer trying to abort a conflicting txn or the reader trying to push a conflicting txn's commit timestamp forward), who attempts to resolve a conflict with a "pushee" (args.PushTxn -- the pushee txn whose intent(s) caused the conflict).

Txn already committed/aborted: If pushee txn is committed or aborted return success.

Txn Timeout: If pushee txn entry isn't present or its LastHeartbeat timestamp isn't set, use PushTxn.Timestamp as LastHeartbeat. If current time - LastHeartbeat > 2 * DefaultHeartbeatInterval, then the pushee txn should be either pushed forward or aborted, depending on value of Request.Abort.

Old Txn Epoch: If persisted pushee txn entry has a newer Epoch than PushTxn.Epoch, return success, as older epoch may be removed.

Lower Txn Priority: If pushee txn has a lower priority than pusher, adjust pushee's persisted txn depending on value of args.Abort. If args.Abort is true, set txn.Status to ABORTED, and priority to one less than the pusher's priority and return success. If args.Abort is false, set txn.Timestamp to pusher's Timestamp + 1 (note that we use the pusher's Args.Timestamp, not Txn.Timestamp because the args timestamp can advance during the txn).

Higher Txn Priority: If pushee txn has a higher priority than pusher, return TransactionPushError. Transaction will be retried with priority one less than the pushee's higher priority.

func (*Range) InternalRangeLookup 

func (r *Range) InternalRangeLookup(batch engine.Engine, args *proto.InternalRangeLookupRequest, reply *proto.InternalRangeLookupResponse)

InternalRangeLookup is used to look up RangeDescriptors - a RangeDescriptor is a metadata structure which describes the key range and replica locations of a distinct range in the cluster.

RangeDescriptors are stored as values in the cockroach cluster's key-value store. However, they are always stored using special "Range Metadata keys", which are "ordinary" keys with a special prefix appended. The Range Metadata Key for an ordinary key can be generated with the `engine.RangeMetaKey(key)` function. The RangeDescriptor for the range which contains a given key can be retrieved by generating its Range Metadata Key and dispatching it to InternalRangeLookup.

Note that the Range Metadata Key sent to InternalRangeLookup is NOT the key at which the desired RangeDescriptor is stored. Instead, this method returns the RangeDescriptor stored at the _lowest_ existing key which is _greater_ than the given key. The returned RangeDescriptor will thus contain the ordinary key which was originally used to generate the Range Metadata Key sent to InternalRangeLookup.

This method has an important optimization: instead of just returning the request RangeDescriptor, it also returns a slice of additional range descriptors immediately consecutive to the desired RangeDescriptor. This is intended to serve as a sort of caching pre-fetch, so that the requesting nodes can aggressively cache RangeDescriptors which are likely to be desired by their current workload.

func (*Range) InternalResolveIntent 

func (r *Range) InternalResolveIntent(batch engine.Engine, ms *engine.MVCCStats, args *proto.InternalResolveIntentRequest, reply *proto.InternalResolveIntentResponse)

InternalResolveIntent updates the transaction status and heartbeat timestamp after receiving transaction heartbeat messages from coordinator. The range will return the current status for this transaction to the coordinator.

func (*Range) InternalTruncateLog 

func (r *Range) InternalTruncateLog(batch engine.Engine, ms *engine.MVCCStats, args *proto.InternalTruncateLogRequest, reply *proto.InternalTruncateLogResponse)

InternalTruncateLog discards a prefix of the raft log.

func (*Range) IsFirstRange 

func (r *Range) IsFirstRange() bool

IsFirstRange returns true if this is the first range.

func (*Range) IsLeader 

func (r *Range) IsLeader() bool

IsLeader returns true if this range replica is the raft leader. TODO(spencer): this is always true for now.

func (*Range) LastIndex 

func (r *Range) LastIndex() (uint64, error)

LastIndex implements the raft.Storage interface.

func (*Range) Put 

func (r *Range) Put(batch engine.Engine, ms *engine.MVCCStats, args *proto.PutRequest, reply *proto.PutResponse)

Put sets the value for a specified key.

func (*Range) ReapQueue 

func (r *Range) ReapQueue(batch engine.Engine, args *proto.ReapQueueRequest, reply *proto.ReapQueueResponse)

ReapQueue destructively queries messages from a delivery inbox queue. This method must be called from within a transaction.

func (*Range) Scan 

func (r *Range) Scan(batch engine.Engine, args *proto.ScanRequest, reply *proto.ScanResponse)

Scan scans the key range specified by start key through end key up to some maximum number of results. The last key of the iteration is returned with the reply.

func (*Range) SetDesc 

func (r *Range) SetDesc(desc *proto.RangeDescriptor)

SetDesc atomically sets the range's descriptor. This method should be called in the context of having metaLock held, as is the case for merging, splitting and updating the replica set.

func (*Range) SetHardState 

func (r *Range) SetHardState(st raftpb.HardState) error

SetHardState implements the multiraft.WriteableGroupStorage interface.

func (*Range) SetLastVerificationTimestamp 

func (r *Range) SetLastVerificationTimestamp(timestamp proto.Timestamp) error

SetLastVerificationTimestamp writes the timestamp at which the range's data was last verified.

func (*Range) ShouldSplit 

func (r *Range) ShouldSplit() bool

ShouldSplit returns whether the current size of the range exceeds the max size specified in the zone config.

func (*Range) Snapshot 

func (r *Range) Snapshot() (raftpb.Snapshot, error)

Snapshot implements the raft.Storage interface.

func (*Range) String 

func (r *Range) String() string

String returns a string representation of the range.

func (*Range) Term 

func (r *Range) Term(i uint64) (uint64, error)

Term implements the raft.Storage interface.

type RangeManager 

type RangeManager interface {
	// Accessors for shared state.
	Allocator() *allocator
	Clock() *hlc.Clock
	ClusterID() string
	DB() *client.KV
	Engine() engine.Engine
	Gossip() *gossip.Gossip
	StoreID() proto.StoreID
	RaftNodeID() multiraft.NodeID

	// Range manipulation methods.
	AddRange(rng *Range) error
	MergeRange(subsumingRng *Range, updatedEndKey proto.Key, subsumedRaftID int64) error
	NewRangeDescriptor(start, end proto.Key, replicas []proto.Replica) (*proto.RangeDescriptor, error)
	NewSnapshot() engine.Engine
	ProposeRaftCommand(cmdIDKey, proto.InternalRaftCommand)
	RemoveRange(rng *Range) error
	SplitRange(origRng, newRng *Range) error
}

A RangeManager is an interface satisfied by Store through which ranges contained in the store can access the methods required for splitting.

type RangeResult 

type RangeResult struct {
	// contains filtered or unexported fields
}

RangeResult is returned by SplitRangeByPrefixes.

type RangeSlice 

type RangeSlice []*Range

A RangeSlice is a slice of Range pointers used for replica lookups by key.

func (RangeSlice) Len 

func (rs RangeSlice) Len() int

Implementation of sort.Interface which sorts by StartKey from each range's descriptor.

func (RangeSlice) Less 

func (rs RangeSlice) Less(i, j int) bool

func (RangeSlice) Swap 

func (rs RangeSlice) Swap(i, j int)

type ResponseCache 

type ResponseCache struct {
	sync.Mutex
	// contains filtered or unexported fields
}

A ResponseCache provides idempotence for request retries. Each request to a range specifies a ClientCmdID in the request header which uniquely identifies a client command. After commands have been replicated via Raft, they are executed against the state machine and the results are stored in the ResponseCache.

The ResponseCache stores responses in the underlying engine, using keys derived from the Raft ID and the ClientCmdID.

A ResponseCache is safe for concurrent access.

func NewResponseCache 

func NewResponseCache(raftID int64, engine engine.Engine) *ResponseCache

NewResponseCache returns a new response cache. Every range replica maintains a response cache, not just the leader. However, when a replica loses or gains leadership of the Raft consensus group, the inflight map should be cleared.

func (*ResponseCache) ClearData 

func (rc *ResponseCache) ClearData() error

ClearData removes all items stored in the persistent cache. It does not alter the inflight map.

func (*ResponseCache) ClearInflight 

func (rc *ResponseCache) ClearInflight()

ClearInflight removes all pending commands from the inflight map, signaling and clearing any inflight waiters.

func (*ResponseCache) CopyFrom 

func (rc *ResponseCache) CopyFrom(e engine.Engine, originRaftID int64) error

CopyFrom copies all the cached results from another response cache into this one. Note that the cache will not be locked while copying is in progress. Failures decoding individual cache entries return an error. The copy is done directly using the engine instead of interpreting values through MVCC for efficiency.

func (*ResponseCache) CopyInto 

func (rc *ResponseCache) CopyInto(e engine.Engine, destRaftID int64) error

CopyInto copies all the cached results from one response cache into another. The cache will be locked while copying is in progress; failures decoding individual cache entries return an error. The copy is done directly using the engine instead of interpreting values through MVCC for efficiency.

func (*ResponseCache) GetResponse 

func (rc *ResponseCache) GetResponse(cmdID proto.ClientCmdID, reply proto.Response) (bool, error)

GetResponse looks up a response matching the specified cmdID and returns true if found. The response is deserialized into the supplied reply parameter. If no response is found, returns false. If a command is pending already for the cmdID, then this method will block until the the command is completed or the response cache is cleared.

func (*ResponseCache) PutResponse 

func (rc *ResponseCache) PutResponse(cmdID proto.ClientCmdID, reply proto.Response) error

PutResponse writes a response to the cache for the specified cmdID. The inflight entry corresponding to cmdID is removed from the inflight map. Any requests waiting on the outcome of the inflight command will be signaled to wakeup and read the command response from the cache.

type Store 

type Store struct {
	*StoreFinder

	Ident     proto.StoreIdent
	RetryOpts util.RetryOptions
	// contains filtered or unexported fields
}

A Store maintains a map of ranges by start key. A Store corresponds to one physical device.

func NewStore 

func NewStore(clock *hlc.Clock, eng engine.Engine, db *client.KV, gossip *gossip.Gossip,
	transport multiraft.Transport) *Store

NewStore returns a new instance of a store.

func (*Store) AddRange 

func (s *Store) AddRange(rng *Range) error

AddRange adds the range to the store's range map and to the sorted rangesByKey slice.

func (*Store) Allocator 

func (s *Store) Allocator() *allocator

Allocator accessor.

func (*Store) Attrs 

func (s *Store) Attrs() proto.Attributes

Attrs returns the attributes of the underlying store.

func (*Store) Bootstrap 

func (s *Store) Bootstrap(ident proto.StoreIdent) error

Bootstrap writes a new store ident to the underlying engine. To ensure that no crufty data already exists in the engine, it scans the engine contents before writing the new store ident. The engine should be completely empty. It returns an error if called on a non-empty engine.

func (*Store) BootstrapRange 

func (s *Store) BootstrapRange() error

BootstrapRange creates the first range in the cluster and manually writes it to the store. Default range addressing records are created for meta1 and meta2. Default configurations for accounting, permissions, and zones are created. All configs are specified for the empty key prefix, meaning they apply to the entire database. Permissions are granted to all users and the zone requires three replicas with no other specifications.

func (*Store) Capacity 

func (s *Store) Capacity() (engine.StoreCapacity, error)

Capacity returns the capacity of the underlying storage engine.

func (*Store) Clock 

func (s *Store) Clock() *hlc.Clock

Clock accessor.

func (*Store) ClusterID 

func (s *Store) ClusterID() string

ClusterID accessor.

func (*Store) DB 

func (s *Store) DB() *client.KV

DB accessor.

func (*Store) Descriptor 

func (s *Store) Descriptor(nodeDesc *NodeDescriptor) (*StoreDescriptor, error)

Descriptor returns a StoreDescriptor including current store capacity information.

func (*Store) Engine 

func (s *Store) Engine() engine.Engine

Engine accessor.

func (*Store) ExecuteCmd 

func (s *Store) ExecuteCmd(method string, args proto.Request, reply proto.Response) error

ExecuteCmd fetches a range based on the header's replica, assembles method, args & reply into a Raft Cmd struct and executes the command using the fetched range.

func (*Store) GetRange 

func (s *Store) GetRange(raftID int64) (*Range, error)

GetRange fetches a range by Raft ID. Returns an error if no range is found.

func (*Store) Gossip 

func (s *Store) Gossip() *gossip.Gossip

Gossip accessor.

func (*Store) GroupStorage 

func (s *Store) GroupStorage(groupID uint64) multiraft.WriteableGroupStorage

GroupStorage implements the multiraft.Storage interface.

func (*Store) LookupRange 

func (s *Store) LookupRange(start, end proto.Key) *Range

LookupRange looks up a range via binary search over the sorted "rangesByKey" RangeSlice. Returns nil if no range is found for specified key range. Note that the specified keys are transformed using Key.Address() to ensure we lookup ranges correctly for local keys.

func (*Store) MergeRange 

func (s *Store) MergeRange(subsumingRng *Range, updatedEndKey proto.Key, subsumedRaftID int64) error

MergeRange expands the subsuming range to absorb the subsumed range. This merge operation will fail if the two ranges are not collocated on the same store.

func (*Store) NewRangeDescriptor 

func (s *Store) NewRangeDescriptor(start, end proto.Key, replicas []proto.Replica) (*proto.RangeDescriptor, error)

NewRangeDescriptor creates a new descriptor based on start and end keys and the supplied proto.Replicas slice. It allocates new Raft and range IDs to fill out the supplied replicas.

func (*Store) NewSnapshot 

func (s *Store) NewSnapshot() engine.Engine

NewSnapshot creates a new snapshot engine.

func (*Store) ProposeRaftCommand 

func (s *Store) ProposeRaftCommand(idKey cmdIDKey, cmd proto.InternalRaftCommand)

ProposeRaftCommand submits a command to raft.

func (*Store) RaftNodeID 

func (s *Store) RaftNodeID() multiraft.NodeID

RaftNodeID accessor.

func (*Store) RemoveRange 

func (s *Store) RemoveRange(rng *Range) error

RemoveRange removes the range from the store's range map and from the sorted rangesByKey slice.

func (*Store) SplitRange 

func (s *Store) SplitRange(origRng, newRng *Range) error

SplitRange shortens the original range to accommodate the new range. The new range is added to the ranges map and the rangesByKey sorted slice.

func (*Store) Start 

func (s *Store) Start() error

Start the engine, set the GC and read the StoreIdent.

func (*Store) Stop 

func (s *Store) Stop()

Stop calls Range.Stop() on all active ranges.

func (*Store) StoreID 

func (s *Store) StoreID() proto.StoreID

StoreID accessor.

func (*Store) String 

func (s *Store) String() string

String formats a store for debug output.

type StoreDescriptor 

type StoreDescriptor struct {
	StoreID  proto.StoreID
	Attrs    proto.Attributes // store specific attributes (e.g. ssd, hdd, mem)
	Node     NodeDescriptor
	Capacity engine.StoreCapacity
}

StoreDescriptor holds store information including store attributes, node descriptor and store capacity.

func (*StoreDescriptor) CombinedAttrs 

func (s *StoreDescriptor) CombinedAttrs() *proto.Attributes

CombinedAttrs returns the full list of attributes for the store, including both the node and store attributes.

func (StoreDescriptor) Less 

func (s StoreDescriptor) Less(b util.Ordered) bool

Less compares two StoreDescriptors based on percentage of disk available.

type StoreFinder 

type StoreFinder struct {
	// contains filtered or unexported fields
}

StoreFinder provides the data necessary to find stores with particular attributes.

type TimestampCache 

type TimestampCache struct {
	// contains filtered or unexported fields
}

A TimestampCache maintains an interval tree FIFO cache of keys or key ranges and the timestamps at which they were most recently read or written. If a timestamp was read or written by a transaction, an MD5 of the txn ID is stored with the timestamp to avoid advancing timestamps on successive requests from the same transaction. We use the MD5 of the txn ID to conserve memory as txn IDs are expected to be fairly large ~100 bytes.

The cache also maintains a low-water mark which is the most recently evicted entry's timestamp. This value always ratchets with monotonic increases. The low water mark is initialized to the current system time plus the maximum clock offset.

func NewTimestampCache 

func NewTimestampCache(clock *hlc.Clock) *TimestampCache

NewTimestampCache returns a new timestamp cache with supplied hybrid clock.

func (*TimestampCache) Add 

func (tc *TimestampCache) Add(start, end proto.Key, timestamp proto.Timestamp, txnMD5 [md5.Size]byte, readOnly bool)

Add the specified timestamp to the cache as covering the range of keys from start to end. If end is nil, the range covers the start key only. txnMD5 is empty for no transaction. readOnly specifies whether the command adding this timestamp was read-only or not.

func (*TimestampCache) Clear 

func (tc *TimestampCache) Clear(clock *hlc.Clock)

Clear clears the cache and resets the low water mark to the current time plus the maximum clock offset.

func (*TimestampCache) GetMax 

func (tc *TimestampCache) GetMax(start, end proto.Key, txnMD5 [md5.Size]byte) (proto.Timestamp, proto.Timestamp)

GetMax returns the maximum read and write timestamps which overlap the interval spanning from start to end. Cached timestamps matching the specified txnID are not considered. If no part of the specified range is overlapped by timestamps in the cache, the low water timestamp is returned for both read and write timestamps.

The txnMD5 is an MD5 of the transaction ID. It prevents restarts with a pattern like: read("a"), write("a"). The read adds a timestamp for "a". Then the write (for the same transaction) would get that as the max timestamp and be forced to increment it. The MD5 allows timestamps from the same txn to be ignored.

Source Files

View all Source files

Directories

Path Synopsis
Package engine provides low-level storage.
 Package engine provides low-level storage.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.