tinyraft/model_update.js

#!/usr/bin/nodejs
// https://github.com/hashicorp/memberlist simulation tool

class LimQ
{
    constructor(retransmit, maxlen)
    {
        this.buckets = [];
        for (let i = 0; i < retransmit; i++)
        {
            this.buckets.push([]);
        }
        this.len = 0;
        this.maxlen = maxlen;
    }

    push(item)
    {
        if (this.len >= this.maxlen)
            return;
        const b = this.buckets[this.buckets.length-1];
        b.push(item);
    }

    shift(n)
    {
        let items = [];
        let move = [];
        for (let i = this.buckets.length-1; i >= 0 && items.length < n; i--)
        {
            const rm = this.buckets[i].splice(0, n-items.length);
            items.push.apply(items, rm);
            if (i > 0)
                for (const e of rm)
                    move.push([ e, i-1 ]);
            else
                this.len -= rm.length;
        }
        for (const e of move)
        {
            this.buckets[e[1]].push(e[0]);
        }
        return items;
    }
}

function test_memberlist(options)
{
    options.gossip ||= 4;
    options.msgcap ||= 5;
    options.max_ticks ||= 100000;
    options.total ||= 100;
    options.retransmit ||= 12;
    options.update ||= 0;
    options.initial ||= 5;
    let tick = 0;
    let messages_sent = 0;
    const queue = {};
    const known = {}; // { node: { other_node: meta_version } }
    const lists = {};
    const listsv2 = {};
    for (let i = 1; i <= options.total; i++)
    {
        known[i] = {};
        lists[i] = [];
        for (let j = 1; j <= (options.update ? options.total : options.initial); j++)
        {
            known[i][j] = 1; // meta version 1
            lists[i].push(j);
        }
        listsv2[i] = [];
        queue[i] = new LimQ(options.retransmit, options.max_queue);
    }
    let cmp_lists;
    let cmp_n;
    if (options.update)
    {
        // We want to update <options.update> nodes metadata to version 2
        for (let i = 1; i <= options.update; i++)
        {
            known[i][i] = 2;
            listsv2[i].push(i);
            queue[i].push(i);
        }
        cmp_lists = listsv2;
        cmp_n = options.update;
    }
    else
    {
        // We want <options.total-options.initial> to join <options.initial>
        for (let i = 1; i <= options.initial; i++)
        {
            for (let alive = options.initial+1; alive <= options.total; alive++)
            {
                known[i][alive] = 1;
                lists[i].push(alive);
                queue[i].push(alive);
            }
        }
        cmp_lists = lists;
        cmp_n = options.total;
    }
    let in_sync = 0;
    for (let i = 1; i <= options.total; i++)
    {
        if (cmp_lists[i].length == cmp_n)
        {
            in_sync++;
        }
    }
    let avg_known = 0;
    while (in_sync < options.total && tick < options.max_ticks)
    {
        console.log('tick '+tick+': '+in_sync+' in sync, avg '+avg_known);
        for (let i = 1; i <= options.total; i++)
        {
            const known_i = lists[i];
            for (let g = 0; g < options.gossip; g++)
            {
                const to = known_i[0|(Math.random()*known_i.length)];
                let send_what = queue[i].shift(options.msgcap);
                messages_sent += send_what.length;
                for (const alive of send_what)
                {
                    if (!known[to][alive] || known[i][alive] > known[to][alive])
                    {
                        known[to][alive] = known[i][alive];
                        cmp_lists[to].push(alive);
                        queue[to].push(alive);
                        const cur_updated = cmp_lists[to].length;
                        if (cur_updated == cmp_n)
                        {
                            console.log('node '+to+': synced at tick '+tick);
                            in_sync++;
                        }
                    }
                }
            }
        }
        avg_known = 0;
        for (let i = 1; i <= options.total; i++)
        {
            avg_known += cmp_lists[i].length;
        }
        avg_known /= options.total;
        tick++;
    }
    console.log('tick '+tick+': '+in_sync+' in sync, avg '+avg_known);
    console.log(messages_sent+' messages sent');
}

const options = {};

for (let i = 2; i < process.argv.length; i++)
{
    if (process.argv[i] === '-h' || process.argv[i] === '--help')
    {
        console.error('USAGE: '+process.argv[0]+' '+process.argv[1]+` [OPTIONS]

--gossip 4            how many nodes to gossip with every tick
--msgcap 5            how many "alive" messages fits in a single packet (meta size/UDP packet size in memberlist)
--max_ticks 100000    execution limit
--max_queue 1024      queue size limit
--total 100           total nodes
--retransmit 12       retransmission count. by default log(total)*4 in memberlist
--update 0            total nodes to update if testing update. if 0 then test joining
--initial 5           initial nodes in sync to test joining (when --update is 0)`);
        process.exit();
    }
    else if (process.argv[i].substr(0, 2) == '--')
    {
        options[process.argv[i].substr(2)] = 0|process.argv[i+1];
        i++;
    }
}

test_memberlist(options);