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

Directories

Path Synopsis
examples
cmd

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL