trie

Documentation

Overview

Package trie provides a trie implementation specialised to Flair's requirements.

Not every possible setup is supported. Maybe eventually it will get cleverer.

Index

• type DialCallback
• type ReplicatedAckFunc
• type ReplicatedFunc
• type Replicator
  • func NewReplicator(t *Trie, replicas int) *Replicator
  • func (r *Replicator) All(key string, f ReplicatedFunc) error
  • func (r *Replicator) Parallel(key string, f ReplicatedFunc) error
  • func (r *Replicator) ParallelDigest(digest *pb.Digest, f ReplicatedFunc) error
  • func (r *Replicator) Sequential(key string, f ReplicatedFunc) error
  • func (r *Replicator) SequentialAck(key string, f ReplicatedAckFunc) error
  • func (r *Replicator) SequentialDigest(digest *pb.Digest, f ReplicatedFunc) error
• type Server
• type Trie
  • func New(callback DialCallback) *Trie
  • func (t *Trie) Add(rangeSpec, address string) error
  • func (t *Trie) AddAll(spec map[string]string) error
  • func (t *Trie) AddRange(start, end, address string) error
  • func (t *Trie) Check() error
  • func (t *Trie) Get(key string) *Server
  • func (t *Trie) GetOffset(key string, offset int) *Server

Types

type DialCallback

type DialCallback func(address string) (*grpc.ClientConn, error)

A DialCallback is called when we need to dial a new gRPC server.

type ReplicatedAckFunc

type ReplicatedAckFunc func(*Server) (bool, error)

A ReplicatedAckFunc is like a ReplicatedFunc but allows the caller to specify whether the call should retry on the next replica by returning true, or not by returning false.

type ReplicatedFunc

type ReplicatedFunc func(*Server) error

A ReplicatedFunc is a function that is passed to the replicator that gets called potentially more than once against different servers. If the returned appear appears to be retryable we will try on a new replica (e.g. we would retry Unavailable errors where the server is down, we wouldn't retry InvalidArgument where it seems it would be pointless).

type Replicator

type Replicator struct {
	Trie     *Trie
	Replicas int
	// contains filtered or unexported fields
}

A Replicator implements replication for our RPCs.

func NewReplicator

func NewReplicator(t *Trie, replicas int) *Replicator

NewReplicator returns a new Replicator instance.

func (*Replicator) All

func (r *Replicator) All(key string, f ReplicatedFunc) error

All sends a request to all replicas for a particular key simultaneously; it is like Parallel but waits for all replicas to complete.

func (*Replicator) Parallel

func (r *Replicator) Parallel(key string, f ReplicatedFunc) error

Parallel replicates the given function to all replicas at once. It returns an error if all replicas fail, hence it is possible for some replicas not to receive data.

func (*Replicator) ParallelDigest

func (r *Replicator) ParallelDigest(digest *pb.Digest, f ReplicatedFunc) error

ParallelDigest is like Parallel but takes a digest instead of the raw hash.

func (*Replicator) Sequential

func (r *Replicator) Sequential(key string, f ReplicatedFunc) error

Sequential runs the function sequentially from the primary, attempting each replica in sequence until either one is successful or they all fail. It returns an error if all replicas fail, which is the error of the primary replica (with appropriate status code etc).

func (*Replicator) SequentialAck

func (r *Replicator) SequentialAck(key string, f ReplicatedAckFunc) error

SequentialAck is like Sequential but allows the caller to specify whether the call should continue to the next replica even on a non-error response. This facilitates the BatchReadBlobs endpoint that basically never returns an 'actual' error because they're all inline.

func (*Replicator) SequentialDigest

func (r *Replicator) SequentialDigest(digest *pb.Digest, f ReplicatedFunc) error

SequentialDigest is like Sequential but takes a digest instead of the raw hash.

type Server

type Server struct {
	CAS   pb.ContentAddressableStorageClient
	AC    pb.ActionCacheClient
	BS    bs.ByteStreamClient
	Exe   pb.ExecutionClient
	Fetch apb.FetchClient
	GC    ppb.GCClient
	Start string
	End   string
}

A Server holds several gRPC connections to the same server.

type Trie

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

A Trie provides fast lookups on hash keys.

func New

func New(callback DialCallback) *Trie

New creates a new trie.

func (*Trie) Add

func (t *Trie) Add(rangeSpec, address string) error

Add adds a node to this trie. It returns an error on any failure, including overlapping ranges.

func (*Trie) AddAll

func (t *Trie) AddAll(spec map[string]string) error

AddAll adds everything from the given map to this trie. It produces a mildly better memory layout than repeatedly calling Add.

func (*Trie) AddRange

func (t *Trie) AddRange(start, end, address string) error

AddRange adds a specific hash range to this trie.

func (*Trie) Check

func (t *Trie) Check() error

Check performs a check on this trie, validating that all ranges are accounted for.

func (*Trie) Get

func (t *Trie) Get(key string) *Server

Get returns a server from this trie. It is assumed not to fail since the trie is already complete.

func (*Trie) GetOffset

func (t *Trie) GetOffset(key string, offset int) *Server

GetOffset gets a server with the hash offset by a given amount.