Skip to content

Instantly share code, notes, and snippets.

@eliwjones
Last active January 3, 2016 09:59
Show Gist options
  • Save eliwjones/8446915 to your computer and use it in GitHub Desktop.
Save eliwjones/8446915 to your computer and use it in GitHub Desktop.
Protean gossip protocol simulator.
package main
import (
"fmt"
"math"
"math/rand"
"runtime"
"sort"
"strconv"
"strings"
"time"
)
type Gossip struct {
Key string
Path []int64
TS int64
Bounce int
}
var (
totalCounterChannel chan int
uniqueCounterChannel chan int
node_map = map[string]map[string]Gossip{}
node_channels = map[string]chan Gossip{}
GossipFunc = map[string]func(string, Gossip){}
current_func = ""
bounceLimit = 0
pathLimit = 0
nodeCount = 0
gossipeeCount = 0
gossipCount = 0
uniqueGossipCount = 0
)
func init() {
// Init mapped GossipGossip funcs here since can't figure out to assign to map on outside.
/*
GossipFunc["GossipGossip0"] = func(node_key string, gossip Gossip) {
// Choose random hosts to gossip to.
node_idx := ExtractNodeIDX(node_key)
if node_idx >= 0 && node_idx < 1000 {
next_idx := node_idx + 1
next_node_key := fmt.Sprintf("node_%d", next_idx)
SendGossip(next_node_key, gossip)
}
}
*/
GossipFunc["GossipGossip1"] = func(node_key string, gossip Gossip) {
if gossip.Bounce > bounceLimit {
return
}
if len(gossip.Path) > pathLimit {
return
}
// Choose random hosts to gossip to.
for i := 0; i < gossipeeCount; i++ {
//Choose idx. SendGossip.
ready := false
idx := int64(0)
for !ready {
ready = true
idx = int64(rand.Intn(len(node_map)))
for _, val := range gossip.Path {
if idx == val {
ready = false
}
}
}
next_node_key := fmt.Sprintf("node_%d", idx)
SendGossip(next_node_key, gossip)
}
}
GossipFunc["GossipGossip2"] = func(node_key string, gossip Gossip) {
if gossip.Bounce > bounceLimit {
return
}
if len(gossip.Path) > pathLimit {
return
}
// Choose random hosts to gossip to.
seen_map := map[int64]bool{}
for _, val := range gossip.Path {
seen_map[val] = true
}
// Way slower since has to iterate over all nodes.
for i := 0; i < nodeCount; i++ {
if seen_map[int64(i)] {
continue
}
dest_node_key := fmt.Sprintf("node_%d", i)
// draw rand to see if should send.
rand := rand.Intn(nodeCount)
if rand <= gossipeeCount {
SendGossip(dest_node_key, gossip)
}
}
}
}
func main() {
rand.Seed(time.Now().UTC().UnixNano())
runtime.GOMAXPROCS(runtime.NumCPU())
// Make 1000 nodes and start ReceiveGossip() routines.
pathLimit = 7
bounceLimit = 0
nodeCount = 10000
gossipeeCount = int(math.Log2(float64(nodeCount)))
for fnName, _ := range GossipFunc {
current_func = fnName
initCounters()
initNodes(nodeCount)
initChannels()
// Percolate update gossip.
g := Gossip{Key: "test_key", TS: int64(99)}
SendGossip("node_0", g)
// Replace once have not-so-dumb way to singal gossiping is done.
time.Sleep(time.Duration(1000) * time.Millisecond)
calculateStats()
}
}
func ProcessGossip(node_key string, gossip Gossip) {
if node_map[node_key][gossip.Key].TS < gossip.TS {
node_map[node_key][gossip.Key] = gossip
uniqueCounterChannel <-1
} else {
gossip.Bounce += 1
}
gossip.Path = append(gossip.Path, ExtractNodeIDX(node_key))
GossipFunc[current_func](node_key, gossip)
}
func SendGossip(node_key string, gossip Gossip) {
// send Gossip down node_channels[node_key]
totalCounterChannel <- 1
node_channels[node_key] <- gossip
}
func ReceiveGossip(node_key string) {
// Gossip comes down channel. Take it and update node_map accordingly.
for {
select {
case gossip := <-node_channels[node_key]:
ProcessGossip(node_key, gossip)
}
}
}
func ExtractNodeIDX(node_key string) int64 {
node_parts := strings.Split(node_key, "_")
idx, _ := strconv.ParseInt(node_parts[1], 10, 64)
return idx
}
func initNodes(nodeCount int){
node_map = map[string]map[string]Gossip{}
for i := 0; i < nodeCount; i++ {
node_key := fmt.Sprintf("node_%d", i)
node_map[node_key] = map[string]Gossip{}
}
}
func initCounters(){
gossipCount = 0
uniqueGossipCount = 0
}
func initChannels(){
node_channels = map[string]chan Gossip{}
for node_key, _ := range node_map {
node_channels[node_key] = make(chan Gossip, 100)
go ReceiveGossip(node_key)
}
totalCounterChannel = make(chan int, 1000)
uniqueCounterChannel = make(chan int, 1000)
go gossipCounter()
}
func gossipCounter(){
for {
select {
case <-totalCounterChannel:
gossipCount += 1
case <-uniqueCounterChannel:
uniqueGossipCount += 1
}
}
}
func calculateStats() {
fmt.Printf("******** [%s] ********\n", current_func)
fmt.Printf("Node Count: %d\nGossipee Count: %d\nBounce Limit: %d\nPath Limit: %d\n", nodeCount, gossipeeCount, bounceLimit, pathLimit)
missing_updates := 0
path_lens := []int{}
max_path_len := 0
for _, val := range node_map {
if val["test_key"].TS != int64(99) {
missing_updates += 1
}
path_len := len(val["test_key"].Path)
if path_len > max_path_len {
max_path_len = path_len
}
path_lens = append(path_lens, path_len)
}
sort.Ints(path_lens)
//fmt.Printf("Path Lens:\n%v\n", path_lens)
fmt.Printf("Max Path Length: %d\n", path_lens[len(path_lens)-1])
fmt.Printf("Med Path Length: %d\n", path_lens[int(len(path_lens)/2)])
fmt.Printf("Missing Updates: %d\n", missing_updates)
fmt.Printf("Total Gossip: %d\n", gossipCount)
fmt.Printf("Unique Gossip: %d\n", uniqueGossipCount)
fmt.Printf("Multiplier: %d\n", gossipCount/nodeCount)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment