hyparview

package module
v0.0.0-...-036f6e6 Latest Latest
Warning

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

 Go to latest Published: Sep 23, 2025 License: MPL-2.0 Imports: 3 Imported by: 0

README

What's This?

Modernized fork of HashiCorp's HyParView implementation, updated with Go 1.24+ and current dependencies. Created for thesis research on a Plumtree-based protocol. Core of the implementation has been largely left unchanged.

HyParView implements:

  • Partial membership for gossip clusters
  • The Paper in production in Partisan
  • 10k node cluster requires 5 active and 30 passive peers in views at each node
  • Side goal: demonstrate separation of state changes from async or mutex behavior to improve testing options

Running The Simulation

brew install gnuplot
make simulation

See data for the data input. Plotting output is in plot

Known bugs

  • The simulation consistently shows a number of asymmetric links, these would actually be repaired in a stable system that continued to shuffle. The simulation should be extended to demonstrate that.

  • When running with only a single send attempt, failure recovery causes a stack overflow. The simulator send plugin should use an external stack that doesn't overflow so easily

  • Related Topics for Improving the Approach

  • Thicket ([[https://www.gsd.inesc-id.pt/~ler/reports/srds10.pdf][Thicket PDF]], also by Leitão and Rodrigues) describes multiple spanning tree approach to sending application messages, which reduces waste messages while remaining resilient to churn. The simulator currently implements very simple epidemic gossip transmission where the active view size is the degree of fanout (novel messages are forwarded to all active peers). Waste and path length are plotted.

  • In the [[https://www.semanticscholar.org/paper/Gossip-based-peer-sampling-Jelasity-Voulgaris/b571ec0ac7173bcecfe1b3095af2f6a5232526a9][Peer Sample]] paper (which uses only the passive view), entries are tagged with a timestamp of the last direct active contact, and the shuffling algorithm is biased to penalize old entries. This allows a dead node to fall out of the passive view of the total network more quickly. This may have a detrimental effect if a network is partitioned on recovery.

  • Partion recovery in general needs more investigation, there may be a risk that partioned networks would repair their respective active views and interconnected tightly, so that repairing the partion would lead to two well connected networks joined by just a few nodes.

  • Improvements to the Code

  • Isolated nodes in simulation runs have asymmetric active views. Refactor the simulator to support periodic messages like active view keepalive and shuffle from the perspective of each node.

  • Incorporate =failActive= directly into the code. Because it relies on synchronous low priority =Neighbor= requests, it requires a sort of iterator interface (or some other refactoring)

  • Minor, dependent on research results: the view constructor takes the expected number of peers as an argument, and should use that to set the appropriate default configuration, once it's factors are known outside the values given in the paper

  • Live Test

There's an example secure GRPC application of this library at hashicorp/hyparview-example. It will be used for a live test on hardware.

Documentation

Index

Constants

View Source 
const (
	HighPriority = true
	LowPriority  = false
)

Variables

This section is empty.

Functions

func EqualNode 

func EqualNode(n, m Node) bool

func Rint 

func Rint(n int) int

rint is a placeholder so we can swap out for rintCrypto in testing rand [0, n] inclusive

func Rint64Crypto 

func Rint64Crypto(n int64) int64

rand [0, n] inclusive

func RintCrypto 

func RintCrypto(n int) int

rand [0, n] inclusive

func RintWithSource 

func RintWithSource(n int, src RandomSource) int

RintWithSource uses the provided RandomSource, falls back to DefaultRandom if nil rand [0, n] inclusive

Types

type Config 

type Config struct {
	// ActiveViewSize the size is based on log(n) + c
	ActiveViewSize int
	// PassiveViewSize the size is based on k(log(n) + c)
	PassiveViewSize int

	ShuffleActive  int
	ShufflePassive int

	// RWLActive max number of hops a ForwardJoin request is forwarded
	RWLActive int
	// RWLPassive specifies at which point in the walk the node is inserted into the passive view
	RWLPassive int
	RWLShuffle int
}

Config values should be based on the cluster size n. The passive view has to be larger then the active view. Configuration parameter used in the paper for cluster of size n = 10000 are: ActiveViewSize = 5, PassiveViewSize = 30, with c = 1, k = 6

type DisconnectRequest 

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

func NewDisconnect 

func NewDisconnect(to Node, from Node) *DisconnectRequest

func (*DisconnectRequest) AssocTo 

func (r *DisconnectRequest) AssocTo(n Node) Message

func (*DisconnectRequest) From 

func (r *DisconnectRequest) From() Node

func (*DisconnectRequest) To 

func (r *DisconnectRequest) To() Node

func (*DisconnectRequest) Type 

func (*DisconnectRequest) Type() string

type ForwardJoinRequest 

type ForwardJoinRequest struct {
	Join Node
	TTL  int
	// contains filtered or unexported fields
}

func NewForwardJoin 

func NewForwardJoin(to Node, from Node, join Node, ttl int) *ForwardJoinRequest

func (*ForwardJoinRequest) AssocTo 

func (r *ForwardJoinRequest) AssocTo(n Node) Message

func (*ForwardJoinRequest) From 

func (r *ForwardJoinRequest) From() Node

func (*ForwardJoinRequest) To 

func (r *ForwardJoinRequest) To() Node

func (*ForwardJoinRequest) Type 

func (*ForwardJoinRequest) Type() string

type Hyparview 

type Hyparview struct {
	Config
	S       Send
	Active  *ViewPart
	Passive *ViewPart
	Self    Node
	// The passive window peers sent in the last shuffle request
	LastShuffle []Node
}

func CreateView 

func CreateView(s Send, self Node, config Config) *Hyparview

CreateView creates the view with the given configuration. Does not start any process.

func (*Hyparview) AddActive 

func (v *Hyparview) AddActive(node Node)

AddActive adds a node to the active view, possibly dropping an active peer to make room. Paper

func (*Hyparview) AddActiveWithSource 

func (v *Hyparview) AddActiveWithSource(node Node, src RandomSource)

AddActiveWithSource adds a node to the active view using the provided RandomSource

func (*Hyparview) AddPassive 

func (v *Hyparview) AddPassive(node Node)

AddPassive adds a node to the passive view, possibly dropping a passive peer to make room. Paper

func (*Hyparview) Bootstrap 

func (v *Hyparview) Bootstrap() Node

func (*Hyparview) Copy 

func (v *Hyparview) Copy() *Hyparview

Copy returns a copy thats safe to modify. Shuffle is copied as a pointer because each ShuffleRequest is immutable once created

func (*Hyparview) DelPassive 

func (v *Hyparview) DelPassive(node Node)

DelPassive is a helper function to delete the node from the passive view

func (*Hyparview) DropRandActive 

func (v *Hyparview) DropRandActive()

DropRandActive removes a random active peer and returns the disconnect message following the paper

func (*Hyparview) DropRandActiveWithSource 

func (v *Hyparview) DropRandActiveWithSource(src RandomSource)

DropRandActiveWithSource removes a random active peer using the provided RandomSource

func (*Hyparview) Gossip 

func (v *Hyparview) Gossip(m Message)

func (*Hyparview) Peer 

func (v *Hyparview) Peer() Node

Peer returns a random active peer

func (*Hyparview) PromotePassive 

func (v *Hyparview) PromotePassive() Node

func (*Hyparview) PromotePassiveBut 

func (v *Hyparview) PromotePassiveBut(peer Node) Node

func (*Hyparview) Recv 

func (v *Hyparview) Recv(m Message) *NeighborRefuse

Recv is a helper method that dispatches to the correct recv

func (*Hyparview) RecvDisconnect 

func (v *Hyparview) RecvDisconnect(r *DisconnectRequest)

RecvDisconnect processes a disconnect, demoting the sender to the passive view

func (*Hyparview) RecvForwardJoin 

func (v *Hyparview) RecvForwardJoin(r *ForwardJoinRequest)

RecvForwardJoin processes a ForwardJoin following the paper

func (*Hyparview) RecvJoin 

func (v *Hyparview) RecvJoin(r *JoinRequest)

RecvJoin processes a Join following the paper

func (*Hyparview) RecvNeighbor 

func (v *Hyparview) RecvNeighbor(r *NeighborRequest) *NeighborRefuse

RecvNeighbor processes a neighbor, sent during failure recovery Returns at most one NeighborRefuse, which must be replied to the client

func (*Hyparview) RecvShuffle 

func (v *Hyparview) RecvShuffle(r *ShuffleRequest)

RecvShuffle processes a shuffle request. Paper

func (*Hyparview) RecvShuffleReply 

func (v *Hyparview) RecvShuffleReply(r *ShuffleReply)

func (*Hyparview) Send 

func (v *Hyparview) Send(ms ...Message)

Send wraps the S.Send sender in appropriate error handling

func (*Hyparview) SendJoin 

func (v *Hyparview) SendJoin(peer Node)

func (*Hyparview) SendKeepalives 

func (v *Hyparview) SendKeepalives()

SendKeepalives actively repairs the active view

func (*Hyparview) SendShuffle 

func (v *Hyparview) SendShuffle()

SendShuffle creates and sends a shuffle request to maintain the passive view

type JoinRequest 

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

func NewJoin 

func NewJoin(to Node, from Node) *JoinRequest

func (*JoinRequest) AssocTo 

func (r *JoinRequest) AssocTo(n Node) Message

func (*JoinRequest) From 

func (r *JoinRequest) From() Node

func (*JoinRequest) To 

func (r *JoinRequest) To() Node

func (*JoinRequest) Type 

func (*JoinRequest) Type() string

type Message 

type Message interface {
	To() Node
	AssocTo(Node) Message
	From() Node
	Type() string
}

Message allows clients to redefine hyparview messages to carry additional meta information

type NeighborRefuse 

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

func NewNeighborRefuse 

func NewNeighborRefuse(to Node, from Node) *NeighborRefuse

func (*NeighborRefuse) AssocTo 

func (r *NeighborRefuse) AssocTo(n Node) Message

func (*NeighborRefuse) From 

func (r *NeighborRefuse) From() Node

func (*NeighborRefuse) To 

func (r *NeighborRefuse) To() Node

func (*NeighborRefuse) Type 

func (*NeighborRefuse) Type() string

type NeighborRequest 

type NeighborRequest struct {
	Priority  bool
	Join      bool
	Keepalive bool
	// contains filtered or unexported fields
}

func NewNeighbor 

func NewNeighbor(to Node, from Node, priority bool) *NeighborRequest

func NewNeighborJoin 

func NewNeighborJoin(to Node, from Node) *NeighborRequest

func NewNeighborKeepalive 

func NewNeighborKeepalive(to Node, from Node) *NeighborRequest

func (*NeighborRequest) AssocTo 

func (r *NeighborRequest) AssocTo(n Node) Message

func (*NeighborRequest) From 

func (r *NeighborRequest) From() Node

func (*NeighborRequest) To 

func (r *NeighborRequest) To() Node

func (*NeighborRequest) Type 

func (*NeighborRequest) Type() string

type Node 

type Node interface {
	Addr() string
}

func NewNode 

func NewNode(addr string) Node

type RandomSource 

type RandomSource interface {
	Intn(n int) int
}
var DefaultRandom RandomSource = defaultRandom{}

type Send 

type Send interface {
	// Send sends one message at a time to a peer. TODO simplify batching?
	// send should use a timeout to detect blocking as failure
	Send(Message) (*NeighborRefuse, error)
	// Failed is called after hyparview has handled the failure, to handle e.g.
	// connection cleanup
	Failed(Node)
	// Bootstrap sends a join to some server, discovered by some external consideration
	Bootstrap() Node
}

type ShuffleReply 

type ShuffleReply struct {
	Passive []Node
	// contains filtered or unexported fields
}

func NewShuffleReply 

func NewShuffleReply(to Node, from Node, passive []Node) *ShuffleReply

func (*ShuffleReply) AssocTo 

func (r *ShuffleReply) AssocTo(n Node) Message

func (*ShuffleReply) From 

func (r *ShuffleReply) From() Node

func (*ShuffleReply) To 

func (r *ShuffleReply) To() Node

func (*ShuffleReply) Type 

func (*ShuffleReply) Type() string

type ShuffleRequest 

type ShuffleRequest struct {
	Origin  Node
	Active  []Node
	Passive []Node
	TTL     int
	// contains filtered or unexported fields
}

func NewShuffle 

func NewShuffle(to, from, origin Node, active, passive []Node, ttl int) *ShuffleRequest

func (*ShuffleRequest) AssocTo 

func (r *ShuffleRequest) AssocTo(n Node) Message

func (*ShuffleRequest) From 

func (r *ShuffleRequest) From() Node

func (*ShuffleRequest) To 

func (r *ShuffleRequest) To() Node

func (*ShuffleRequest) Type 

func (*ShuffleRequest) Type() string

type ViewPart 

type ViewPart struct {
	Nodes []Node
	Max   int
}

func CreateViewPart 

func CreateViewPart(size int) *ViewPart

func (*ViewPart) Add 

func (v *ViewPart) Add(n Node)

func (*ViewPart) Contains 

func (v *ViewPart) Contains(n Node) bool

func (*ViewPart) ContainsIndex 

func (v *ViewPart) ContainsIndex(n Node) int

func (*ViewPart) Copy 

func (v *ViewPart) Copy() *ViewPart

func (*ViewPart) DelIndex 

func (v *ViewPart) DelIndex(i int)

func (*ViewPart) DelNode 

func (v *ViewPart) DelNode(n Node) bool

func (*ViewPart) Equal 

func (v *ViewPart) Equal(w *ViewPart) bool

func (*ViewPart) GetIndex 

func (v *ViewPart) GetIndex(i int) Node

func (*ViewPart) IsEmpty 

func (v *ViewPart) IsEmpty() bool

func (*ViewPart) IsEmptyBut 

func (v *ViewPart) IsEmptyBut(peer Node) bool

func (*ViewPart) IsFull 

func (v *ViewPart) IsFull() bool

func (*ViewPart) RandIndex 

func (v *ViewPart) RandIndex() int

func (*ViewPart) RandIndexWithSource 

func (v *ViewPart) RandIndexWithSource(src RandomSource) int

func (*ViewPart) RandNode 

func (v *ViewPart) RandNode() Node

func (*ViewPart) RandNodeWithSource 

func (v *ViewPart) RandNodeWithSource(src RandomSource) Node

func (*ViewPart) Shuffled 

func (v *ViewPart) Shuffled() []Node

func (*ViewPart) ShuffledWithSource 

func (v *ViewPart) ShuffledWithSource(src RandomSource) []Node

func (*ViewPart) Size 

func (v *ViewPart) Size() int

Source Files

View all Source files

Directories

Path Synopsis

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.