README
¶
Topology
Definitions
In Flow, the term topology captures the distributed protocol by which a node determines its fanout set. The fanout set of a node is a subset of other nodes in the system with whom the node interacts in the event of epidemic dissemination of information. The epidemic dissemination happens when a node multicasts or broadcasts a message. The former refers to the event when a node sends a message targeted for a subgroup of nodes in the system, while the latter refers to the event when a node aims at sending a message to the entire system. (Topology algorithms are not used for direct one-to-one communication). Note that the communications over the fanout set are assumed unidirectional from the node to its fanout set. The distributed and independent invocations of topology protocol on nodes of Flow hence results in a directed graph where the vertices are the Flow nodes, and the edges are the union of the fanout sets of the nodes. This directed graph is called the topology graph. It is required that the topology graph is connected with a very high probability, where the probability is taken over the number of times the topology is constructed. The topology is constructed once at the beginning of each epoch. Hence, it implies that the topology construction protocol should result in a connected graph with a very high probability over the life-time of Flow, which theoretically is infinitely-many epochs. In practice, we consider it as 2^30 many epochs.
The figure below shows an example of a topology graph with 7 nodes in the Flow network, which is a directed and connected graph. There is a path between every two nodes and traversing the topology graph with BFS or DFS visits all the vertices. Also, the fanout set of each node is colored the same as the node itself, e.g., the fanout set of the red node is illustrated using red edges from it to other nodes of the network. Also, in this example, every node has a fanout size of 3.
Topology Interface
The Topology interface provides a way to retrieve a topology for a node. It receives the approved list of nodes in the system and generates and returns the fanout of the node. The current implementations of this topology interface are topic-based topology and randomized topology. Any future topology implementation must also implement this interface to be able to be plugged into the node.
TopicBasedTopology
The topic-based topology breaks the communication space of Flow into topics, where each topic corresponds to a
single channel. Running an instance of topic-based topology on a node generates a fanout set for each topic the node is
subscribing to. As the result of independent invocations of topic-based topology on different nodes in Flow, several overlapping connected components
are shaped among the nodes, each corresponding to a single topic. The topology graph of the entire network is then the union of these connected
components. Since the individual topic-based components are connected, the entire topology graph of the network is also connected. The figure below
shows the general idea of building the topology graph of the system using connected components as it happens in the topic-based topology. The
topic-based topology provides deterministic connectedness among the nodes subscribing to a topic by creating a fanout of (x+1)/2 per node using the
linear fanout function, where x is the number of nodes subscribed to the topic. In this way, the resulted graph component of the topic is guaranteed
with connectedness. The topic-based topology is the topology in effect of Flow at the moment.
RandomizedTopology
The randomized-topology is similar to the topic-based topology, except that upon constructing a graph component for a topic, instead of choosing a
fixed-size fanout per node, it selects the fanout of the node probabilistically using an edge probability, p.
For the set of nodes subscribed to a topic, each node includes any other node in its fanout with the probability of p, hence, the expected fanout of
a node on the graph component of a topic is p * x where x is the number of nodes subscribed to the topic. Choosing an appropriate edge probability
(e.g., 0.05) the randomized topology provides a connected graph with a very high probability (e.g., 1 - 2^-30), while it needs drastically
smaller fanout per node. The randomized topology is not yet in effect, however, it is planned to replace the topic-based topology soon to support the
scalability of the network.
Documentation
¶
Index ¶
- func CheckMembership(t *testing.T, top flow.IdentityList, all flow.IdentityList)
- func CheckTopologySize(t *testing.T, total int, top flow.IdentityList)
- func ClusterNum(t *testing.T, ids flow.IdentityList, size int) int
- func Connected(t *testing.T, adjMap map[flow.Identifier]flow.IdentityList, ...)
- func LinearFanout(size int) int
- func MockStateForCollectionNodes(t *testing.T, collectorIds flow.IdentityList, clusterNum uint) (protocol.State, flow.ClusterList)
- func MockSubscriptionManager(t *testing.T, ids flow.IdentityList) []network.SubscriptionManager
- type Cache
- type EmptyListTopology
- type FanoutFunc
- type FixedListTopology
- type RandomizedTopology
- type TopicBasedTopology
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func CheckMembership ¶
func CheckMembership(t *testing.T, top flow.IdentityList, all flow.IdentityList)
CheckMembership checks each identity in a top list belongs to all identity list.
func CheckTopologySize ¶
func CheckTopologySize(t *testing.T, total int, top flow.IdentityList)
TODO: fix this test after we have fanout optimized. CheckTopologySize evaluates that overall topology size of a node is bound by the fanout of system.
func ClusterNum ¶
ClusterNum is a test helper determines the number of clusters of specific `size`.
func Connected ¶ added in v0.14.0
func Connected(t *testing.T, adjMap map[flow.Identifier]flow.IdentityList, ids flow.IdentityList, f flow.IdentityFilter)
Connected checks if the graph represented by the adjacency matrix is connected. It traverses the adjacency map starting from an arbitrary node and checks if all nodes that satisfy the filter were visited.
func LinearFanout ¶
LinearFanoutFunc guarantees full network connectivity in a deterministic way. Given system of `size` nodes, it returns `size+1/2`.
func MockStateForCollectionNodes ¶ added in v0.14.0
func MockStateForCollectionNodes(t *testing.T, collectorIds flow.IdentityList, clusterNum uint) (protocol.State, flow.ClusterList)
MockStateForCollectionNodes is a test helper function that generate a mock state clustering collection nodes into `clusterNum` clusters.
func MockSubscriptionManager ¶
func MockSubscriptionManager(t *testing.T, ids flow.IdentityList) []network.SubscriptionManager
MockSubscriptionManager returns a list of mocked subscription manages for the input identities. It only mocks the Channels method of the subscription manager. Other methods return an error, as they are not supposed to be invoked.
Types ¶
type Cache ¶ added in v0.14.0
type Cache struct {
// contains filtered or unexported fields
}
Cache provides caching the most recently generated topology. It implements the same GenerateFanout as a normal topology, so can easily replace any topology implementation. As long as the input IdentityList to it is the same, the cached topology is returned without invoking the underlying GenerateFanout. This is vital to provide a deterministic topology interface, as by its nature, the Topology interface does not guarantee a deterministic behavior.
Note: as a convention with other topology implementations, Cache is not concurrency-safe, and should be invoked in a concurrency safe way, i.e., the caller should lock for it.
func NewCache ¶ added in v0.14.0
NewCache creates and returns a topology Cache given an instance of topology implementation.
func (*Cache) GenerateFanout ¶ added in v0.14.0
func (c *Cache) GenerateFanout(ids flow.IdentityList, channels network.ChannelList) (flow.IdentityList, error)
GenerateFanout receives IdentityList of entire network and constructs the fanout IdentityList of this instance. It caches the most recently generated fanout list, so as long as the input list is the same, it returns the same output. It invalidates and updates its internal cache the first time input list changes. A node directly communicates with its fanout IdentityList on epidemic dissemination of the messages (i.e., publish and multicast). Independent invocations of GenerateFanout on different nodes collaboratively must construct a cohesive connected graph of nodes that enables them talking to each other.
Note that this implementation of GenerateFanout preserves same output as long as input is the same. This should not be assumed as a 1-1 mapping between input and output.
type EmptyListTopology ¶ added in v0.20.0
type EmptyListTopology struct {
}
EmptyListTopology always returns an empty list as the fanout
func (EmptyListTopology) GenerateFanout ¶ added in v0.20.0
func (r EmptyListTopology) GenerateFanout(_ flow.IdentityList, _ network.ChannelList) (flow.IdentityList, error)
type FanoutFunc ¶
FanoutFunc represents a function type that receiving total number of nodes in flow system, returns fanout of individual nodes.
type FixedListTopology ¶ added in v0.20.0
type FixedListTopology struct {
// contains filtered or unexported fields
}
FixedListTopology always returns the same node ID as the fanout
func NewFixedListTopology ¶ added in v0.20.0
func NewFixedListTopology(nodeID flow.Identifier) FixedListTopology
func (FixedListTopology) GenerateFanout ¶ added in v0.20.0
func (r FixedListTopology) GenerateFanout(ids flow.IdentityList, _ network.ChannelList) (flow.IdentityList, error)
type RandomizedTopology ¶ added in v0.14.0
type RandomizedTopology struct {
// contains filtered or unexported fields
}
RandomizedTopology generates a random topology per channel. By random topology we mean a node is connected to any other co-channel nodes with some edge probability.
func NewRandomizedTopology ¶ added in v0.14.0
func NewRandomizedTopology(nodeID flow.Identifier, logger zerolog.Logger, edgeProb float64, state protocol.State) (*RandomizedTopology, error)
NewRandomizedTopology returns an instance of the RandomizedTopology.
func (RandomizedTopology) GenerateFanout ¶ added in v0.14.0
func (r RandomizedTopology) GenerateFanout(ids flow.IdentityList, channels network.ChannelList) (flow.IdentityList, error)
GenerateFanout receives IdentityList of entire network and constructs the fanout IdentityList of this instance. A node directly communicates with its fanout IdentityList on epidemic dissemination of the messages (i.e., publish and multicast). Independent invocations of GenerateFanout on different nodes collaboratively must construct a cohesive connected graph of nodes that enables them talking to each other. This should be done with a very high probability in randomized topology.
type TopicBasedTopology ¶
type TopicBasedTopology struct {
// contains filtered or unexported fields
}
TopicBasedTopology is a deterministic topology mapping that creates a connected graph component among the nodes involved in each topic.
func NewTopicBasedTopology ¶
func NewTopicBasedTopology(nodeID flow.Identifier, logger zerolog.Logger, state protocol.State) (*TopicBasedTopology, error)
NewTopicBasedTopology returns an instance of the TopicBasedTopology.
func (TopicBasedTopology) GenerateFanout ¶
func (t TopicBasedTopology) GenerateFanout(ids flow.IdentityList, channels network.ChannelList) (flow.IdentityList, error)
GenerateFanout receives IdentityList of entire network and constructs the fanout IdentityList of this instance. A node directly communicates with its fanout IdentityList on epidemic dissemination of the messages (i.e., publish and multicast). Independent invocations of GenerateFanout on different nodes collaboratively must construct a cohesive connected graph of nodes that enables them talking to each other.
Source Files