Coding Exercise

approach.md

Overview

I thought it might be fun to put together a horizontally scalable, distributed micro-services approach to this problem. This would allow the simulation to be run either locally (with multiple threads to make use of features on modern processors) or in a scalable cluster environment with any number of hosts, where vastly more resources would be available to simulate a much more populous environment.

The basic plan would be to use the following dockerised services to run the simulation:

• 4 Redis instances/clusters
• 1 master node; to control the clock, save state and monitor stats
• N r_worker nodes; to process the rules for each rabbit
• M w_worker nodes; to process the rules for each wolf
• L render nodes; to pull the state and render the map

Redis (the fast key/value datastore) v3.2 includes GeoHash based structures and a GEORADIUS command; which searches for members within a radius around a given position. Since this function represents a decent portion of the trig algorithms required for the simulation this makes it a good choice for storing the simulation data.

These services could be orchestrated with Kubernetes or Rancher to run threads across any number of hosts, with work queues for managing and distributing work between r_worker and w_worker nodes. Splitting the Redis instances/clusters into 4 shards (one each for geo:wolves, geo:rabbits, geo:carrots, and then the rest) allows the expensive (O(log(N))) GEO transactions to be run on different hosts. These shards themselves could be single instances, or clusters using the master-slave model to further distribute reads and writes.

The limitations of this architecture would be as follows:

• The simulation area would be limited by the Redis GeoHash implementation to longitudes between -180 and 180 degrees and latitudes between -85.05112878 and 85.05112878 degrees; so practically, planet Earth.
• The population of any single group (wolves, rabbits or carrots) would be limited to what could be stored in memory of the host that redis instance lands on; since the GeoHash is stored as 52bit integers, this translates to populations in the order of 10 billion or so using AWS m4.10xlarge instances.
• The simulation rate would probably be limited by latency between the nodes and the redis instances/clusters introduced by the the TCP/IP stack and the network (since even on a single machine, docker services communicate with an overlay network).

Technical Details

Redis Config

Work Queues

The follows keys would be Redis lists to be used as processing queues for each tick:

• wolves
• rabbits

Sorted Sets

The following sorted sets would be created and accessed with redis GEO commands to track position of each member:

• geo:wolves
• geo:wolves:near:rabbits
• geo:rabbits
• geo:rabbits:near:carrots
• geo:carrots

Keys

These keys would store information and stats

• <wolf>:count
• <rabbit>:count
• <wolf>:nearby:rabbit
• <rabbit>:nearby:carrots
• <rabbit>:carrot:quota
• <wolf>:rabbit:quota
• <carrot>:patch:qty

Master Node

The master node would be responsible for setting up the initial conditions for the simulation, and filling the work queues with the contents of each sorted set at the start of each tick. It would also store/log/serve stats and the homeostatic conditions on a regular basis and could probably even be used to automatically scale the number of hosts and worker nodes in a cluster as required using AWS and Kuberenetes APIs (or similar).

See master.js for a brief pseudocode overview of the functionality of a basic master node.

Rabbit Workers

The r_worker nodes would process the rules for the simulated rabbits and update their positions, update eaten carrot quotas, drop them from geo:rabbits when eaten, and spawn duplicates when full.

See r_worker.js for a brief pseudocode overview of the functionality of a basic r_worker node.

Wolf Workers

The w_worker nodes would process the rules for the simulated wolves and update their positions, update eaten rabbit quotas, and spawn duplicates when full.

See w_worker.js for a brief pseudocode overview of the functionality of a basic w_worker node.

master.js

/*
 * Master Node
 *
 * This psudocode outlines the implimentation approach for the master node
*/

// Setup Initial Conditions

const initCommands = [];

[
  { key: 'wolves', count: INITIAL_WOLF_COUNT queue: true },
  { key: 'rabbits', count: INITIAL_RABBIT_COUNT queue: true },
  { key: 'carrots', count: INITIAL_CARROT_COUNT },
].forEach((item) => {
  range(item.count).forEach((nothing, i) => {
    // Spawn with a random position
    initCommands.push(['GEOADD', `geo:${item.key}`, randomLat(), randomLong(), i]);

    // Initialise the first work queue
    if (item.queue === true) initCommands.push(['LPUSH', item.key, i]);
  })
});


// Set Up Loop
subscribe('rabbits_processed', () => {
  emit('process_wolves');
});

subscribe('wolves_processed', () => {
  emit('end_tick');
});

subscribe('end_tick', () => {
  finishTick()
    .then(() => emit('process_rabbits'))
    .catch((err) => {
      log(err);
      emit('process_rabbits');
    });
});

// Start
redis.pipeline(initCommands).then(() => emit('process_rabbits'));

r_worker.js

/*
 * R_worker node
 *
 * This psudocode outlines the implimentation approach for the r_workers
*/

this.on('get_rabbit', () => {
  this.rabbit = {};
  redis.cmd(['RPOP', 'rabbits'])
    .then((rabbit) => {
      if (!rabbit) endTick();

      // Get Rabbit Info
      this.rabbit.id = rabbit;
      return redis.pipeline([
        ['GEOPOS', 'geo:rabbits', rabbit],
        ['GET', `${rabbit}:carrot:quota`],
      ]);
    })
    .then(([pos, quota]) => {
      this.rabbit.pos = pos;

      // If carrot quota is zero, time to divide (and reset quota)
      if (quota === 0) return Promise.reject({ full: true });

      // Otherwise, search for wolves
      return redis.cmd([
        'GEORADIUS',
        'geo:wolves',
        rabbit.pos,
        WOLF_HUNT_RADIUS,
        'WITHCOORD',
        'WITHDIST',
        'ASC',
      ]);
    })
    .then((wolves) => {
      this.rabbit.wolves = wolves;

      // Am I safe? Then look for carrots
      if (wolves.length === 0) {
        return redis.cmd([
          'GEORADIUS',
          'geo:carrots',
          rabbit.pos,
          RABBIT_HUNT_RADIUS,
          'WITHCOORD',
          'WITHDIST',
          'ASC',
        ]);
      }

      // Am I being eaten?
      if (wolves[0].distance <= WOLF_EAT_RADIUS) return Promise.reject({ eaten: true });

      // Then I am being chased
      return Promise.reject({ chased: true });
    })
    .then((carrots) => {
      this.rabbit.carrots = carrots;

      // If I can't see carrots, see if any nearby rabbits have seen carrots
      if (carrots.length === 0) {
        return redis.cmd([
          'GEORADIUS',
          'geo:rabbits:near:carrots',
          rabbit.pos,
          RABBIT_HUNT_RADIUS,
          'WITHCOORD',
          'ASC'
        ]);
      }

      // Eat a carrot if close enough (and decrement carrot quota)
      if (carrots[0].distance <= RABBIT_EAT_RADIUS) return Promise.reject({ eating: true });

      // Otherwise I am moving to carrots
      return Promise.reject({ moving: true, position: carrots[0].pos });
    })
    .then((friends) => {
      this.rabbit.friends = friends;

      // If my friends haven't seen carrots, I'm searching
      if (friends.length === 0) return Promise.reject({ searching: true });

      // Otherwise, get the location of their carrots
      return redis.cmd(['GET', `${friends[0]}:nearby:carrots`]);
    })
    .then((friendsCarrot) => {
      this.rabbit.friendsCarrot = friendsCarrot;

      // If this failed, just search
      if (!friendsCarrot) return Promise.reject({ searching: true });

      // Otherwise, move towards our friends carrot
      return Promise.reject({ moving: true, position: friendsCarrot });
    })
    .catch((result) => {
      if (!result) return;

      // Process the next actions with action handlers
      if (result.full) return divide(this.rabbit);
      if (result.eaten) return dead(this.rabbit);
      if (result.chased) return runAway(this.rabbit);
      if (result.eating) return eatCarrot(this.rabbit);
      if (result.moving) return move(this.rabbit, result.position);

      // Move without a position will have to move randomly, while staing within some kind of
      // simulation bountry
      if (result.searching) return move(this.rabbit);

      // Otherwise we probably have an error to log
      return Promise.reject(result);
    })
    .catch((error) => {
      // Catch all errors from this chain and from aciton handlers
      if (error) console.error(error);
    })
    .then(() => {
      // Continue even if we get an error
      this.emit('get_rabbit');
    });
});

// Start waiting
subscribe('process_rabbits', () => this.emit('get_rabit'));

w_worker.js

/*
 * W_worker node
 *
 * This psudocode outlines the implimentation approach for the w_workers
*/

this.on('get_wolf', () => {
  this.wolf = {};
  redis.cmd(['RPOP', 'wolves'])
    .then((wolf) => {
      if (!wolf) endTick();

      // Get Wolf Info
      this.wolf.id = wolf;
      return redis.pipeline([
        ['GEOPOS', 'geo:wolves', wolf],
        ['GET', `${wolf}:rabbit:quota`],
      ]);
    })
    .then(([pos, quota]) => {
      this.wolf.pos = pos;

      // If rabbit quota is zero, time to divide (and reset quota)
      if (rabbit === 0) return Promise.reject({ full: true });

      // Look for rabbits
      return redis.cmd([
        'GEORADIUS',
        'geo:rabbits',
        wolf.pos,
        WOLF_HUNT_RADIUS,
        'WITHCOORD',
        'WITHDIST',
        'ASC',
      ]);
    })
    .then((rabbits) => {
      this.wolf.rabbits = rabbits;

      // If I can't see rabbits, see if any nearby rabbits have seen rabbits
      if (rabbits.length === 0) {
        return redis.cmd([
          'GEORADIUS',
          'geo:wolves:near:rabbits',
          rabbit.pos,
          WOLF_HUNT_RADIUS,
          'WITHCOORD',
          'ASC',
        ]);
      }

      // If close enough, eat the rabbit
      if (carrots[0].distance <= WOLF_EAT_RADIUS) return Promise.reject({ eating: true });

      // Otherwise move to the rabbit
      return Promise.reject({ moving: true, position: rabbits[0].pos });
    })
    .then((friends) => {
      this.wolf.friends = friends;

      // If my friends haven't seen rabbits, I'm searching
      if (friends.length === 0) return Promise.reject({ searching: true });

      // Otherwise, get locations of our friend's rabbit
      return redis.cmd(['GET', `${friends[0]}:nearby:rabbit`]);
    })
    .then((friendsRabbit) => {
      this.wolf.friendsRabbit = friendsRabbit;

      // If this failed, just search
      if (!friendsRabbit) return Promise.reject({ searching: true });

      // Otherwise, move towards our friends rabbit
      return Promise.reject({ moving: true, position: friendsRabbit });
    })
    .catch((result) => {
      if (!result) return;
      if (result.full) return divide(this.wolf);
      if (result.chased) return run(this.wolf);
      if (result.eating) return eatRabbit(this.wolf);
      if (result.moving) return move(this.wolf, result.position);

      // Move without a position will have to move randomly, while staing within some kind of
      // simulation bountry
      if (result.searching) return move(this.wolf);

      // Otherwise we probably have an error to log
      return Promise.reject(result);
    })
    .catch((error) => {
      // Catch all errors from this chain and from aciton handlers
      if (error) console.error(error);
    })
    .then(() => {
      // Continue even if we get an error
      this.emit('get_wolf');
    });
});

// Start waiting
subscribe('process_wolves', () => this.emit('get_wolf'));