fabric

package module
v0.0.0-...-69869d7 Latest Latest
Warning

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

 Go to latest Published: Oct 2, 2017 License: Apache-2.0 Imports: 5 Imported by: 3

README

Fabric

Concepts

Slides discussing the core concepts behind Fabric: http://jeremykhawaja.com/fabric/Fabric.html#1

The initial paper outlining the core concepts (needs revision): https://github.com/JKhawaja/concurrency

Project State

Note to Developers: Fabric is still a work-in-progress. The current implementation is usable but will likely undergo several breaking changes in the near future. Please vendor if used, and/or use with caution.

Please don't hesitate to complain or make a recommendation with an issue on GitHub. :)

Summary

A Concurrency control primitives package. Utilizing dependency graphs to avoid conflict in concurrent access to a single data structure. Fine-Grained Blocking.

This code package is less of a "here are some functions and objects. Use them." And more of a "here are some interfaces. Implement them." And this allows the package to behave more as a design guidance tool rather than a "strict" dependency.

In other words: the purpose of this package is to use it in creating your own Concurrent-Data-Structure packages. Another option is to take an existing data structure package and fabric-ate (hehe, get it?) a new package from it.

In Progress

  • Fabgen: A small code generation tool that can be used to generate boilerplate for projects that will be using the fabric package.

Future

  • FabCheck: methods for formal verification of system design using fabric package in order to avoid undesired behavior
  • Make fabric work for multiple CDSs simultaneously
  • Parallel distributed batch process scheduling (taking a batch of e.g. transactions, and scheduling them across a set of machines in parallel, dependent on their relationship with each other within a fine-grained blocking dependency graph).

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func ContainsEdge 

func ContainsEdge(l EdgeList, e Edge) bool

ContainsEdge checks if a CDS edge (reference) is in an Edglist

func ContainsNode 

func ContainsNode(l NodeList, n Node) bool

ContainsNode checks if a CDS node (reference) is in a NodeList

Types

type AccessType 

type AccessType interface {
	// Class() string                             // the "class" of action (e.g. "read")
	ID() int                                   // integer id assigned to Access Type
	Priority() int                             // priorities are not a necessity but can be helpful for ordering algorithms for posets
	Commit(DGNode) error                       // takes a DGNode to signal for ...
	Rollback(RestoreNodes, RestoreEdges) error // takes a list of all CDS nodes and edges that have been operated on

}

AccessType is the interface to define how an access procedure should behave; Create an Access Procedure function signature type and add these methods to it. IMPORTANT: In order to best utilize the commit and rollback features the Access Type should have an error return value.

type BasicSignalHandler 

type BasicSignalHandler func(<-chan NodeSignal, sync.WaitGroup)

BasicSignalHandler is the basic function type for handling signals from a dependency node Used in total-blocking, to call wg.Done() on certain Signal Values and return. will not allow for more complex signal handling e.g. handling an Abort or AbortRetry with more resilience (use with caution)

type Branch 

type Branch struct {
	Nodes *NodeList
	Edges *EdgeList
}

Branch ...

func (*Branch) ListEdges 

func (b *Branch) ListEdges() *EdgeList

ListEdges ...

func (*Branch) ListNodes 

func (b *Branch) ListNodes() *NodeList

ListNodes ...

func (*Branch) UpdateEdgeList 

func (b *Branch) UpdateEdgeList(elp *EdgeList)

UpdateEdgeList ...

func (*Branch) UpdateNodeList 

func (b *Branch) UpdateNodeList(nlp *NodeList)

UpdateNodeList ...

type CDS 

type CDS interface {
	GenNodeID() int
	GenEdgeID() int
	ListNodes() NodeList // a simple `return MyCDS.Nodes` will suffice here; once a NodeList has been created
	ListEdges() EdgeList // a simple `return MyCDS.Edges` will suffice here; once an EdgesList has been created
}

CDS is the interface definition that must be satisfied for the global shared data structure

type DGNode 

type DGNode interface {
	ID() int           // must be unique from all other DGNodes in our graph
	GetType() NodeType // specifies whether node is UI, VUI, etc.
	GetPriority() int  // not necessary, but can be useful
	ListProcedures() ProcedureList
	UpdateSignaling(SignalingMap, SignalsMap) // makes it possible to update the SignalingMap and SignalsMap for a DGNode
	ListSignalers() SignalingMap
	ListSignals() SignalsMap
	Signal(NodeSignal) // used to send the same signal to all dependents in signalers list
}

DGNode (Dependency Graph Node) ... every DGNode has an id, a Type, a state, and a set of Access Procedures NOTE: This will require assigning signals to their appropriate nodes 

when setting up a dependency graph.

type Disjoint 

type Disjoint struct {
	Nodes *NodeList
	Edges *EdgeList
}

Disjoint ...

func NewDisjoint 

func NewDisjoint(nlp *NodeList, elp *EdgeList) *Disjoint

NewDisjoint ...

func (*Disjoint) ListEdges 

func (d *Disjoint) ListEdges() *EdgeList

ListEdges ...

func (*Disjoint) ListNodes 

func (d *Disjoint) ListNodes() *NodeList

ListNodes ...

func (*Disjoint) UpdateEdgeList 

func (d *Disjoint) UpdateEdgeList(elp *EdgeList)

UpdateEdgeList ...

func (*Disjoint) UpdateNodeList 

func (d *Disjoint) UpdateNodeList(nlp *NodeList)

UpdateNodeList ...

type Edge 

type Edge interface {
	ID() int // returns edge id
	GetSource() Node
	GetDestination() Node
	Immutable() bool
}

Edge ...

type EdgeList 

type EdgeList []Edge

EdgeList is a list of references to each edge in the CDS

type EmptyUI 

type EmptyUI struct {
	AccessProcedures *ProcedureList
	Signalers        *SignalingMap
	Signals          *SignalsMap
	CDS              Section
}

EmptyUI can be used when a UI is needed codewise, but the CDS system will not be using any spatial virtualization (UI DDAGs).

func (*EmptyUI) GetPriority 

func (u *EmptyUI) GetPriority() int

GetPriority ...

func (*EmptyUI) GetSection 

func (u *EmptyUI) GetSection() Section

GetSection ...

func (*EmptyUI) GetType 

func (u *EmptyUI) GetType() NodeType

GetType ...

func (*EmptyUI) ID 

func (u *EmptyUI) ID() int

ID ...

func (*EmptyUI) IsUnique 

func (u *EmptyUI) IsUnique() bool

IsUnique ...

func (*EmptyUI) IsVirtual 

func (u *EmptyUI) IsVirtual() bool

IsVirtual ...

func (*EmptyUI) ListProcedures 

func (u *EmptyUI) ListProcedures() ProcedureList

ListProcedures ...

func (*EmptyUI) ListSignalers 

func (u *EmptyUI) ListSignalers() SignalingMap

ListSignalers ...

func (*EmptyUI) ListSignals 

func (u *EmptyUI) ListSignals() SignalsMap

ListSignals ...

func (*EmptyUI) Signal 

func (u *EmptyUI) Signal(s NodeSignal)

Signal ...

func (*EmptyUI) UpdateSignaling 

func (u *EmptyUI) UpdateSignaling(sm SignalingMap, s SignalsMap)

UpdateSignaling ...

type Graph 

type Graph struct {
	DS  CDS
	Top map[DGNode][]DGNode
	VDG []*VDG
}

Graph can be either UI DDAG, Temporal DAG or VDG

func NewGraph 

func NewGraph() *Graph

NewGraph creates a new empty graph

func SingleUIGraph 

func SingleUIGraph(cds CDS) (*Graph, error)

func (*Graph) AddRealEdge 

func (g *Graph) AddRealEdge(source int, dest DGNode)

AddRealEdge will create an edge and an appropriate signaling channel between nodes

func (*Graph) AddRealNode 

func (g *Graph) AddRealNode(node DGNode) (DGNode, error)

AddRealNode ... This should only be used for adding nodes to a graph to intialize the graph.

func (*Graph) AddVDG 

func (g *Graph) AddVDG(v *VDG) error

AddVDG ...

func (*Graph) AddVUI 

func (g *Graph) AddVUI(node UI) (DGNode, error)

AddVUI requires that the node return a true value for its IsVirtual method

func (*Graph) AllowedProcedure 

func (g *Graph) AllowedProcedure(node DGNode, procedure AccessType) bool

AllowedProcedure checks whether or not an access procedure is allowed to act on a node ...

func (*Graph) Covered 

func (g *Graph) Covered() bool

Covered returns true if all CDS nodes and edges are covered

func (*Graph) CycleDetect 

func (g *Graph) CycleDetect() bool

CycleDetect will check whether a graph has cycles or not

func (*Graph) Dependencies 

func (g *Graph) Dependencies(n DGNode) []DGNode

Dependencies ...

func (*Graph) Dependents 

func (g *Graph) Dependents(n DGNode) []DGNode

Dependents ...

func (*Graph) GenID 

func (g *Graph) GenID() int

GenID ...

func (*Graph) GetAdjacents 

func (g *Graph) GetAdjacents(node DGNode) []DGNode

GetAdjacents will return the list of nodes that a node is connected too

func (*Graph) IsLeafBoundary 

func (g *Graph) IsLeafBoundary(n DGNode) bool

IsLeafBoundary ...

func (*Graph) IsRootBoundary 

func (g *Graph) IsRootBoundary(n DGNode) bool

IsRootBoundary ...

func (*Graph) RemoveVDG 

func (g *Graph) RemoveVDG(v *VDG)

RemoveVDG ...

func (*Graph) RemoveVUI 

func (g *Graph) RemoveVUI(n DGNode) error

RemoveVUI ...

func (*Graph) SignalsAndSignalers 

func (g *Graph) SignalsAndSignalers()

SignalsAndSignalers will udpate the SignalingMaps and SignalsMaps for all DGNodes in the graph

func (*Graph) TotalBlock 

func (g *Graph) TotalBlock(nodeID int, handler BasicSignalHandler) bool

TotalBlock is the most basic format for signal checking (used when a node wants to simply totally-block all further operations until its dependencies have signaled) as it only accepts a BasicSignalHandler it will not be a very powerful form of blocking (only use if lazy)

func (*Graph) TotalityUnique 

func (g *Graph) TotalityUnique() bool

TotalityUnique is a Totality-Uniqueness check for the UI nodes of a graph... should only be called once when creating the UI dependency graph; can be called with the creation of each UI if needed for more "real-time" verification.

func (*Graph) Type 

func (g *Graph) Type(n DGNode) NodeType

Type will return the proper NodeType value for a given DGNode argument

type Node 

type Node interface {
	ID() int // returns node id
	Immutable() bool
}

Node is used to wrap data structure elements to become generic CDS Nodes

type NodeList 

type NodeList []Node

NodeList is a list of references to each node in the CDS

type NodeSignal 

type NodeSignal struct {
	AccessType int // should be equivalent to the ID() method return value for the Access Type
	Value      Signal
	Space      UI
}

NodeSignal carries all the information a dependent node will need in order to know what action a dependent node has just taken.

type NodeType 

type NodeType int

NodeType defines the possible values for types of dependency graph nodes 

const (
	// UINode are the spatial definitions usually assigned to a single thread
	UINode NodeType = iota
	// TemporalNode are assigned to threads which address the same UI as the temporals UI dependent
	TemporalNode
	// VirtualTemporalNode is a spawned temporary temporal node
	VirtualTemporalNode
	// VUINode is a temporary UI node
	VUINode
	// VDGNode is a node in a virtual dependency graph
	VDGNode
	// Unknown is a catch-all for an improperly constructed dependency graph node
	Unknown
)

type Partition 

type Partition struct {
	Nodes *NodeList
	Edges *EdgeList
}

Partition ...

func (*Partition) ListEdges 

func (p *Partition) ListEdges() *EdgeList

ListEdges ...

func (*Partition) ListNodes 

func (p *Partition) ListNodes() *NodeList

ListNodes ...

func (*Partition) UpdateEdgeList 

func (p *Partition) UpdateEdgeList(elp *EdgeList)

UpdateEdgeList ...

func (*Partition) UpdateNodeList 

func (p *Partition) UpdateNodeList(nlp *NodeList)

UpdateNodeList ...

type Poset 

type Poset interface {
	// Graph should return a pointer to the graph that our POSET object is "wrapping"
	Graph() *Graph
	// InitGraph should take a list of nodes and order them according to the Order() method and return a new Graph
	InitGraph([]DGNode) *Graph
	// Order should be a method that determines what dependents and what
	// dependencies to assign a node in the wrapped Graph i.e. it determines
	// what edges to make for the node in the Graph.
	// Order returns the location of the DGnode inside the Graph
	Order(DGNode) error
}

Poset is an object that wraps a dependency graph

type ProcedureList 

type ProcedureList []AccessType

ProcedureList ...

type RestoreEdges 

type RestoreEdges []Edge

RestoreEdges is a list of Edge values that can be used to overwrite existing Edge values after an operation failure.

type RestoreNodes 

type RestoreNodes []Node

RestoreNodes is a list of Node values that can be used to overwrite existing Node values after an operation failure.

type Root 

type Root struct {
	AccessProcedures *ProcedureList
	CDS              Section
	Isroot           bool
	IsLeaf           bool
	Signalers        *SignalingMap
	Signals          *SignalsMap
	Executing        bool
	Type             NodeType
}

Root is the object type for pre-made root nodes Root is also is able to satisfy the UI interface in order to add itself as it's subspace

func (*Root) GetPriority 

func (r *Root) GetPriority() int

GetPriority ...

func (*Root) GetSection 

func (r *Root) GetSection() Section

GetSection ...

func (*Root) GetType 

func (r *Root) GetType() NodeType

GetType ...

func (*Root) ID 

func (r *Root) ID() int

ID ...

func (*Root) IsRoot 

func (r *Root) IsRoot() bool

IsRoot ...

func (*Root) IsUnique 

func (r *Root) IsUnique() bool

IsUnique ...

func (*Root) IsVirtual 

func (r *Root) IsVirtual() bool

IsVirtual ...

func (*Root) ListProcedures 

func (r *Root) ListProcedures() ProcedureList

ListProcedures ...

func (*Root) ListSignalers 

func (r *Root) ListSignalers() SignalingMap

ListSignalers ...

func (*Root) ListSignals 

func (r *Root) ListSignals() SignalsMap

ListSignals ...

func (*Root) Signal 

func (r *Root) Signal(s NodeSignal)

Signal ...

func (*Root) Start 

func (r *Root) Start()

Start ...

func (*Root) Started 

func (r *Root) Started() bool

Started ...

func (*Root) Subspace 

func (r *Root) Subspace() UI

Subspace ...

func (*Root) UpdateSignaling 

func (r *Root) UpdateSignaling(sm SignalingMap, s SignalsMap)

UpdateSignaling ...

type Section 

type Section interface {
	ListNodes() *NodeList
	ListEdges() *EdgeList
	// NOTE: UpdateNodes and UpdateEdges can be used to add or remove nodes
	// and edges from the Sections list and provide the section with a new list.
	UpdateNodeList(*NodeList)
	UpdateEdgeList(*EdgeList)
}

Section is the interface definition for cutting out a section of the global CDS

func ComposeSections 

func ComposeSections(graphs []*Section) Section

ComposeSections takes a list of CDS graphs (sections) and composes them into a new single disjoint

func NewBranch 

func NewBranch(root Node, c CDS) Section

NewBranch ...

func NewPartition 

func NewPartition(start, end Node, c CDS) Section

NewPartition ...

func NewSubgraph 

func NewSubgraph(nlp *NodeList, c CDS) Section

NewSubgraph will grab all edges from nodes that connect to other nodes that are in our list.

func NewSubset 

func NewSubset(nlp *NodeList, c CDS) Section

NewSubset grabs all (and only all) edges that are connected to a node in the list of nodes supplied.

type Signal 

type Signal int

Signal defines the possible signal values one dependency graph node can send to another RECOMMENDATION: every thread should have a proper reaction (which may be a non-reaction) 

to each signal value for each access procedure in each dependency node.

EXAMPLE: an example reaction to an abort signal could be "Abort Chain/Tree" where the dependents 

and their dependents, etc. all abort their operations if a signal value from a dependency node
is an 'Abort' signal.

const (
	// Waiting can be used for an access procedure that has not begun but is in line too
	Waiting Signal = iota
	// Started can be used for an access procedure that is no longer waiting and has begun execution
	Started
	// Completed can be used for an access procedure that has finished execution successfully
	Completed
	// Aborted can be used for an access procedure that failed to finish execution
	Aborted
	// AbortRetry EXAMPLE: could use exponential backoff checks on retries for AbortRetry signals from dependencies ...
	AbortRetry
	// PartialAbort can be used to specify if an operation partially-completed before aborting
	PartialAbort
	// Help can be used to specify that a helping mechanism should be triggered in the dependent node
	Help
)

type SignalingMap 

type SignalingMap map[int]chan NodeSignal

SignalingMap is a map of dependent node ids to a channel of signals

type SignalsMap 

type SignalsMap map[int]<-chan NodeSignal

SignalsMap is a map of dependency node ids to recieve-only channel of signals

type Subgraph 

type Subgraph struct {
	Nodes *NodeList
	Edges *EdgeList
}

Subgraph ...

func (*Subgraph) ListEdges 

func (s *Subgraph) ListEdges() *EdgeList

ListEdges ...

func (*Subgraph) ListNodes 

func (s *Subgraph) ListNodes() *NodeList

ListNodes ...

func (*Subgraph) UpdateEdgeList 

func (s *Subgraph) UpdateEdgeList(elp *EdgeList)

UpdateEdgeList ...

func (*Subgraph) UpdateNodeList 

func (s *Subgraph) UpdateNodeList(nlp *NodeList)

UpdateNodeList ...

type Subset 

type Subset struct {
	Nodes *NodeList
	Edges *EdgeList
}

Subset ...

func (*Subset) ListEdges 

func (s *Subset) ListEdges() *EdgeList

ListEdges ...

func (*Subset) ListNodes 

func (s *Subset) ListNodes() *NodeList

ListNodes ...

func (*Subset) UpdateEdgeList 

func (s *Subset) UpdateEdgeList(elp *EdgeList)

UpdateEdgeList ...

func (*Subset) UpdateNodeList 

func (s *Subset) UpdateNodeList(nlp *NodeList)

UpdateNodeList ...

type Temporal 

type Temporal interface {
	DGNode
	GetRoots() []UI
	IsVirtual() bool
}

Temporal is what is assigned to Threads beyond the first thread assigned to a particular UI.

type UI 

type UI interface {
	DGNode
	GetSection() Section
	IsUnique() bool  // specifies whether a UI is *strictly* unique or not (a UI will always have totality-uniqueness)
	IsVirtual() bool // specifies whether a UI is virtual or not
}

UI ...

func NewEmptyUI 

func NewEmptyUI() UI

NewEmptyUI ...

func NewTotalUI 

func NewTotalUI(section Section) UI

type VDG 

type VDG struct {
	Global *Graph // a reference to the real global graph of the system
	Root   Virtual
	Top    map[Virtual][]Virtual
	Space  []int // the set of all (V)UI ids that at least one node in the VDG has access too
}

VDG ...

func NewVDG 

func NewVDG(g *Graph) (*VDG, error)

NewVDG will return an empty VDG graph

func NewVDGWithRoot 

func NewVDGWithRoot(g *Graph) (*VDG, error)

NewVDGWithRoot ...

func (*VDG) AddTopNode 

func (g *VDG) AddTopNode(node Virtual) error

AddTopNode will add a node to the VDG and create an edge pointing from the root node to it

func (*VDG) AddVirtualEdge 

func (g *VDG) AddVirtualEdge(source int, d Virtual) error

AddVirtualEdge adds an edge to a VDG

func (*VDG) AddVirtualNode 

func (g *VDG) AddVirtualNode(node Virtual) (Virtual, error)

AddVirtualNode adds a node to a VDG

func (*VDG) CreateSignalers 

func (g *VDG) CreateSignalers(n Virtual) SignalingMap

CreateSignalers ...

func (*VDG) CycleDetect 

func (g *VDG) CycleDetect() bool

CycleDetect will check whether a graph has cycles or not

func (*VDG) Dependencies 

func (g *VDG) Dependencies(n Virtual) []Virtual

Dependencies ...

func (*VDG) Dependents 

func (g *VDG) Dependents(n Virtual) []Virtual

Dependents ...

func (*VDG) GenID 

func (g *VDG) GenID() int

GenID can generate a unique integer id for a VDG node

func (*VDG) RemoveVirtualEdge 

func (g *VDG) RemoveVirtualEdge(source int, d Virtual)

RemoveVirtualEdge removes a single edge from the VDG Useful for when a dependency node is not being removed but the dependent node no longer requires it as a dependency.

func (*VDG) RemoveVirtualNode 

func (g *VDG) RemoveVirtualNode(n Virtual) error

RemoveVirtualNode is for removing a single node from a VDG It will also remove all edges that have the node as the destination node of the edge. And it will remove the (V)UI subspace if not required by any other node in the VDG.

func (*VDG) Signals 

func (g *VDG) Signals(n Virtual) SignalsMap

Signals ...

func (*VDG) TotalBlock 

func (g *VDG) TotalBlock(nodeID int, handler BasicSignalHandler) bool

TotalBlock is the most basic format for signal checking (used when a node wants to simply totally-block all further operations until its dependencies have signaled) as it only accepts a BasicSignalHandler it will not be a very powerful form of blocking (only use if lazy)

type VPoset 

type VPoset interface {
	// VDG should return a pointer to the VDG that our VPOSET object is "wrapping"
	VDG() *VDG
	// InitGraph should take a list of nodes and order them according to the Order() method and return a new VDG
	InitGraph([]Virtual) *VDG
	// Order should be a method that determines what dependents and what
	// dependencies to assign a node in the wrapped VDG i.e. it determines
	// what edges to make for the node in the VDG.
	// Order returns the location of the Virtual node inside the VDG
	Order(Virtual) error
}

VPoset is an object that wraps a virtual dependency graph

type Virtual 

type Virtual interface {
	DGNode
	Start()        // tells the node to begin execution (usually by flipping a 'Started' boolean -- can also signal to dependents that it has started)
	Started() bool // specifies whether a node has started execution or not
	IsRoot() bool  // specifies whether VDG node is root node or not
	Subspace() UI  // the (V)UI that the Virtual node is associated to
}

Virtual is the interface definition that virtual nodes in a VDG graph need to satsify. NOTE: Virtual Dependency Graph Nodes can only have other 

VDG nodes as dependents or dependencies

Source Files

View all Source files

Directories

Path Synopsis
examples
server
server/db
server/dg
cmd

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.