Protean gossip protocol simulator.

gossip_simulate

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)
}