Skip to content

Instantly share code, notes, and snippets.

@benjaminjt

benjaminjt/approach.md

Last active August 9, 2016 02:31
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save benjaminjt/70f9db8e1a4c7b3a6da6dd16ab5403f3 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save benjaminjt/70f9db8e1a4c7b3a6da6dd16ab5403f3 to your computer and use it in GitHub Desktop.
Download ZIP
Coding Exercise
Raw
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.

Raw
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'));
Raw
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'));
Raw
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'));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment