CraftConf 15–Takeaways from “Jepsen IV: Hope Springs Eternal”

This talk by Kyle Kingsbury (aka @aphyr on twitter) was my favourite at CraftConf, and gave us an update on the state of consistency with MongoDB, Elasticsearch and Aerospike.

 

Kyle opened the talk by talking about how we so often build applications on top of databases, queues, streams, etc. and that these systems we depend on are really quite flammable (hence the tyre analogy).

image

..as anybody who’s ever used any database knows, everything is on fire all the time! But our goal is to pretend, and ensure that everything still works… we need to isolate the system from failures.

 

– Kyle Kingsbury

image

 

Which led nicely into the type of failures that the rest of the talk will focus on – split brain, broken foreign keys, etc. And the purpose of his Jepsen project is to analyse a system against these failures.

 

A system has boundaries, and these boundaries should be protected by a set of invariants – e.g. if you put something into a queue then you should be able to read it out afterwards.

The rest of the talk splits into two halves.

The 1st half builds up a model for talking about consistency:

image

and the 2nd half of the talk looked at a number of specific instances of databases – Elasticsearch, MongoDB and AeroSpike – and see how they stacked up against the consistency guarantees they claim to have.

 

Rather than trying to explain them here and doing a bad job of it, I suggest you read Kyle’s post on the different consistency models from his diagram.

It’s a 15-20 mins read, after which you might also be interested to give these two posts a read too:

 

Instead I’ll just list a few key points I noted during the session:

  • CAP theorem tells us that a linearizable system cannot be totally available
  • for the consistency models in red, you can’t have total availability (the A in CAP) during a partition
  • for total availability, look to the area
  • weaker consistency models are more available in case of failure
  • weaker consistency models are also less intuitive
  • weaker consistency models are faster because they require less coordination
  • weak is not the same as unsafe – safety depends on what you’re trying to do, e.g. eventual consistency is ok for counters, but for claiming unique usernames you need linearizability

Kyle’s Jepsen client uses black-box testing approach to test database systems (i.e. only looking at results from a client’s perspective) whilst inducing network partitions to see how the database behaves during a partition.

The clients generate random operations and apply them to the system. Since clients run on the same JVM so you can use linearizable data structures to record a history of results as received by the clients and use that history to detect consistency violations.

This is similar to the generative testing approach used by QuickCheck. Scott Wlaschin has two excellent posts to help you get started with FsCheck, a F# port of QuickCheck.

 

“MongoDB is not a bug, it’s a database”

– Kyle Kingsbury

and thus began a very entertaining second half of the talk as Kyle shared results from his tests against MongoDB, Elasticsearch and AeroSpike.

 

TL;DR

None of the databases were able to meet the consistency level they claim to offer, but at least Elasticsearch is honest about it and doesn’t promise you the moon.

 

Again, seeing as Kyle has recently written about these results in detail, I won’t repeat them here. The talk doesn’t go into quite as much depth, so if you have time I recommend reading his posts:

 

Whilst it was fun watching Kyle shoot holes through these database vendors’ consistency claims, and some of the fun-poking is really quite funny (and well deserved on the vendor’s part).

If there’s one thing you should takeaway from Kyle’s talk, and his work with Jepsen in general is, don’t drink the kool-aid.

Database vendors have a history of over-selling and at times out-right false marketing. As developers, we have the means to verify their claims, so next time you hear a claim that’s too good to be true, verify it, don’t drink the kool-aid.

 

Links

Interview with Rik Van Bruggen @ QCon London 2015

Modelling game economy with Neo4j

In Here Be Monsters, we have a MMORPG that is content-heavy with over:

  • 5000 items
  • 800 recipes
  • 500 locations
  • 1500 quests

and since the contents are highly connected, it makes balancing the game a rather interesting and challenging problem for our small team behind the project.

The Challenge

Consider a simple example involving the Camouflage Trap, which is one of the very first traps you’ll make. It’s made from a number of ingredients, each can be:

  • found in the certain parts of the world
  • purchased at shops
  • awarded for completing quests/achievements
  • crafted using other ingredients

Now, suppose you want to raise the price of basic ingredients such as Water, that increase needs to propagate all the way through the chain.

Furthermore, when you consider how many items are made from Water, and how many more items are made from those items.

There’s a huge knock-on effect here. Failing to address these knock-on effects will create arbitrage opportunities in your economy for players to exploit. They will be able to mine coins by buying and selling items and will therefore have less need to make real-money purchases with us.

As a game designer, whenever you want to make a change you are faced with this huge uncertainty because of the hidden knock-on effects that you don’t see.

It’s a complexity that we have to manage, but managing this complexity by hand is:

  • laborious – involving many iterations of trial and error, and likely repeated each time new contents are added
  • slow
  • error prone
  • subjective – what ‘feels’ right can vary greatly from person to person

Instead, we opted for a more automated process whereby every item’s intrinsic value in the game can be evaluated based on the values of its inputs (e.g. baits for monsters, ingredients for crafted items, etc.). The amount of time involved, and your chance of success is also taken into account. We can then use the intrinsic value of an item to drive or quantify other less tangible aspects of the game’s model.

This is where Neo4j comes in.

Hello, Neo

One of the main challenges that came up in our effort to automate the economic balancing was to understand the complex relationships between items, quests, achievements, as well as locations and activities that can be performed against/with specific items at specific locations.

Take Bigfoot as an example, from his almanac page in the game:

We can see that to catch the Bigfoot you need to consider:

  • location – he’s only available in certain parts of the world
  • bait – to lure him out you need the Alluring Goat which gives you a roughly 4 in 7 chance of seeing the monster
  • trap – you need a trap strong enough to hold him after you’ve managed to lure him out, the Musket-teer Trap has a 5 in 7 chance of success
  • loot – upon a successful catch, Bigfoot occasionally drops Bigfoot Toenail Clippings as loot, which you might need in future quests or as ingredient to make other items

We can model all the information we see on this screen as a graph in Neo4j:

Additionally, each node and edge can have an arbitrary set of properties.

For instance, Bigfoot and the Musket-teer Trap will have their stats. The lootsrelationship that exists between Bigfoot and his loot will also specify the chance of him dropping the loot.

Looking beyond the immediate connections to Bigfoot, the Alluring Goat and Musket-teer Trap each have numerous connections of their own.

To make the Alluring Goat, you need to gather:

  • Honey, which you need to build a Bee Hive in your homestead and harvest from it;
  • Goat, which you can buy from animal traders in cities around the world such asLondon and NanJing;
  • Golden Hair, which is a loot dropped by Blonde Mermaid, Dandelion Pixie and Blonde Selkie;

This diagram illustrates the highly connected and complex nature of the data we’re dealing with – the result of us making a game where everything you can do and every item you find has a purpose and can be used for something else.

It is also by no means an unconnected subset of the overall graph. For simplicity sake I have omitted many types of relationships and connected nodes.

Visualizing the 8,000+ nodes and around 40,000+ edges in Gephi, where the colour and size of the nodes represent the number of connections they have, this is what the internal data model for Here Be Monsters look like:

As you can see, the degree of connectedness varies greatly. For common low-level monsters such as Sylph, Spriggan, Sprite and Salamander, they are each connected to no less than 300 locations, traps and items.

Similarly, for common ingredients such as Salt, it can be found through many items (e.g. most fish drop Seaweed and Salt as loot when you catch them) and is used in many recipes – Pastry, Pizza Base, Ketchup to name a few.

With the internal data model captured as a graph in Neo4j, we were able to ask some interesting questions that would have been difficult or impossible to answer otherwise.

To give you a few examples.

Impact Analysis

In the earlier pricing example with Water and Camouflage Trap, the key challenge is to be able to understand the impact of change. This is a very similar problem to the ones you face in derivative pricing in Finance.

If you take White Bread as an example, to work out the blast radius of a price change, let’s look at the relationships that exist between an item and a recipe.

To find all the items that are made from White Bread, directly or indirectly, we can run the following Cypher (which is the built-in query language for Neo4j) query against our Neo4j database:

MATCH
(wb:BaseItem { Name:”White Bread”})
-[rel:CRAFTS | IS_USED_IN*1..] ->(i:BaseItem)
RETURN i, rel, wb

Couple of things to note from this query.

  • notice how we are basically pattern matching against the graph using the pattern node-[relationship]->node?
  • we capture the nodes and relationships into variables wb, i and rel so we can return them from the query;
  • we can optionally filter the nodes by type, e.g. (i:BaseItem) will only match against nodes that are of type BaseItem;
  • to identify White Bread, we also filter one of the nodes by the value of its properties, in this case the node wb must have a Name property with the value of White Bread;
  • we can use OR semantic when filtering on relationship types, here we’re looking for relationships of type CRAFTS or IS_USED_IN;
  • for the pattern to work, there must exist 1 or more instance of such relationships between any two nodes, hence the cardinality of *1..

Running this query yields the following result, where the purple nodes are items and red nodes are recipes.

From this graph we can see that White Bread is used directly in 10 recipes, and then indirectly (virtue of being an ingredient for making Sausage) in a further 5. If we were to change the price of White Bread, all 15 of these items will need to have their prices adjusted based on the number of White Bread required to make them.

For example, if it takes 2 pieces of White Bread to make 1 Sausage and 2 Sausage to make a Full English Breakfast, then the change to White Bread‘s price would need to be multiplied by 4 when applied to Full English Breakfast.

Scarcity Analysis

Not all items can be priced as derivatives of others. Some need to be priced based on their scarcity in the world, such as the fruits that you can forage from fruit trees you find on your travels.

To find out how scarcely available Durian and Dragonfruit is, we can use the following Cypher query:

MATCH
(fruit)<-[:FORAGES]-(tree)-[:EXISTS_IN]->(spot)
WHERE
fruit.Name=‘Durian’ OR fruit.Name=‘Dragonfruit’
RETURN fruit, tree, spot

Again, we’re simply pattern matching against our graph using the pattern node<-[relationship1]-node-[relationship2]->node. The expressive power of Cypher lies in the ability to take our relationship diagram above and translate it like-for-like into an executable query.

You might also noticed that I’m not filtering any of the nodes by type here. This is because I know those relationships exist only between the specified types of nodes, hence it’s safe for me to omit them.

Immediately, you can see that Dragonfruit Tree is much more readily available in the world compared to Durian Tree. However, you still need to consider:

  • the number of trees at each location, which you can find out from the EXISTS_IN relationship
  • the number of fruits you get by foraging the tree, which you can find out from the FORAGES relationship

Taking all these factors into account, we can set prices for Durian and Dragonfruit which reflects their scarcity in the world.

Quest Progression

Some quests require specific items to complete. For instance, an NPC might ask you to fetch an item from Bob in Cambridge, or find some feature under a rock somewhere, or catch a Griffin and get a Griffin Egg as loot.

On the other hand, completing a quest can sometimes award you items as well. If the quest is part of a quest line then you will also unlock follow-up quests too, so there is a self-recursive relationship there.

To answer questions such as

What comes after the Year of the Horse quest?

you can use a simple Cypher query like the one below.

MATCH
(q1:Quest { Name: “Year of the Horse” })
-[:UNLOCKS] ->(q2:Quest)
RETURN q1, q2

From the resulting graph, you can quickly see the quests that are unlocked by completing the Year of the Horse quest.

In fact, if you connect all the quests in the game then you’ll end up with the following.

No wonder our game designers need a hand working with the data!

But, just being able to work out how quests are connected to each other and visualize them is not all that exciting or useful. We can do much more.

With our price model in full swing, we are able to:

  1. price baseline items based on factors such as scarcity
  2. price items that are derived from the baseline items

Since the price of an item reflects the difficulty in obtaining it, we can make use of the relationships between quests and items to “price” quests the same way – i.e. the more expensive the items a quest require, the more difficult that quest is to complete.

From there, you can establish simple rules such as:

  • cheaper quests should come before more expensive ones, to ensure a sense of progression for the players
  • a quest should not reward items whose total price exceeds the quest’s price

Monster Hierarchy

Finally, monster trapping is a big part of the game as its name suggests. As mentioned earlier, to catch a monster you need the right combination of bait and trap.

To catch a monster, sometimes you have to first catch a lower level monster; get its loot; and use the loot to make the bait for the monster you want to catch. Using the following relationships you can place the monsters into a hierarchy.

Which can be translated into the following Cypher query:

MATCH
(monster1:Monster)-[:LOOTS]->(loot)
-[r:IS_USED_IN | CRAFTS*0..] ->(bait)-[:CAN_ATTRACT]->(monster2)
RETURN monster1,  monster2

Again, see how it mirrors our diagram?

Suppose we are on a quest to catch Bigfoot, we can use this query to identify the monsters we have to catch first in order to get the ingredients to make the bait for Bigfoot. The query yields the following result where the purple nodes are monsters and the red node in the middle is the recipe for crafting the Alluring Goat.

This places Bigfoot at the peak of its hierarchy.

If you repeat the same exercise for every monster in the game and compose their hierarchies together, then you’ll end up with a more complete monster hierarchy covering most of the monsters that exist in the game.

Once we have both the quest hierarchy and monster hierarchy we can do some interesting analysis.

For instance, if completing Quest 1 unlocks Quest 2, and catching Monster 2 gives you the loot you need to make the bait for Monster 1:

then Quest 1 cannot ask the player to catch Monster 1 if Quest 2 asks the player to catch Monster 2.

This is to ensure that we do not break the sense of progression as the player progresses through the quests.

Otherwise, as a player, you have to catch Monster 2 multiple times to get the loot to make the bait for Monster 1, and then take several attempts to successfully catch Monster 1. Just as you had finished with that cycle, the very next quest (or shortly after) you are asked to catch the same monster again, which doesn’t make for a very satisfying playing experience.

Remember, the situation might be even worse if you have to first catch other monsters in order to make the bait for Monster 2.

Even more Impact Analysis

We looked at how impact analysis applies to item pricing earlier, but we have another interesting use for impact analysis with regards to the monster hierarchy.

When you successfully catch a monster, you receive a gold reward from the Ministry of Monsters and a chance to get the monster’s loot.

Successful Catch = Gold + (maybe)Loot

Therefore, for monster catching, there’s an equation that needs to be balanced:

Whenever you change the price of an item that is either a bait or a loot, it can have a profound impact on the monster hierarchy:

  • change to one side of the equation (item price, drop/attraction rate, gold reward) requires change to the other side to keep things in balance
  • change to the input side of the equation requires changes to all preceding monsters in the hierarchy
  • change to the output side requires changes to all subsequent monsters in the hierarchy

Thankfully, Neo4j makes this really easy, which is important because whenever we introduce a new monster (and it happens pretty regularly) it has an impact on all other monsters in the same region as there is a new competitor for food!

Conclusions

I hope I have given you a flavour of our use case with Neo4j. In general I find graph databases to be the most powerful and natural way to model a domain, especially for domains with complex and/or highly connected datasets.

Slides and Recording

Modelling Game Economy using Neo4j

Hello! Just to quick shout to say that the slides for my Neo4j talk tonight on modelling and balancing an in-game economy using Neo4j is now available on Slideshare:

 

You can also watch the recording of the talk on SkillsMatter here.

 

Oh, and did I mention that we’re hiring for a wide range of positions across the organization? Check out our careers page for details: http://www.gamesyscorporate.com/careers

Here Be Monsters – updates and hello, Neo4j

Here Be Monsters is one year old!

Big things are happening behind the scenes in the world of our episodic MMORPG Here Be Monsters, since the beta started back in September 2012 we have attracted a small but dedicated group of players who have watched the game grew with us and who has lived through the majority of the first two episodes of the evolving storyline in Here Be Monsters and we thank everyone for their continued support and faith in our ability to deliver.

 

Major refactoring on the way

We have learnt an awful lot this past year and over time we have added many features and capabilities to our system so that our game designers can continue to create new and fun contents for our players. After much deliberation we have decided to rework large parts of the first two episodes of the game (Europe and Nanjing) because:

  1. our game designers can create much more interesting contents these days as they are no longer limited by the system capabilities we had a year ago
  2. we have a better understanding of what types of contents our players find most interesting and fun to play through feedbacks and analysis

 

We hope the refactored quest lines will be much more engaging and allow players to see the best the world of Here Be Monsters has to offer. The new quest lines are under the last stages of testing and once ready will be available for new players joining the game from there after.

 

Balancing the Economy

Balancing a RPG, or any game for that matter, is never easy, and often:

  • laborious – involving many iterations of trial and error, and likely repeated each time new contents are added
  • subjective – what ‘feels’ right can vary greatly from person to person

with hundreds of quests and recipes and thousands of items already available in Here Be Monster and many more added on a weekly/bi-weekly basis, manual balancing is simply not a solution that will scale, especially for a relatively small team as ours.

 

Instead, we have opted for a more automated process where by every item’s intrinsic value in the game can be evaluated based on the values of its inputs (e.g. bait for monsters, and ingredients for crafted items, etc.), the amount of time involved and your chance of success. Once we are able to definitely say what the intrinsic value of an item is, it can then be used to derive or quantify other less tangible aspects of the game’s model.

Economic value of items

How much an item can be purchased with and sold for should be directly proportional to the item’s intrinsic value.

Difficulty and Reward for quests and achievements

Many quests and achievements involves acquiring items (via foraging, farming, chipping rocks, etc.) or catching monsters, and their difficulty can therefore be quantified by the intrinsic values of the items/monster involved.

Once you can quantify the difficulty of quests and achievements, you can then balance their rewards against their level of difficulty so that players are always appropriately rewarded for their efforts.

Progression through the game

Since the storyline of the game is largely driven by a sequence of core story quests, and if you are able to quantify the difficulty of the quests you can then use that knowledge to ensure a smooth progression through the quests so that players are given tasks that are appropriate to their level at that point in the game and not bored by dull, unchallenging tasks or; frustrated by tasks that are clearly beyond their ability to complete within a reasonable amount of time and effort.

 

Of course, not everything is straight forward and there are many types of quests and items which we can’t easily quantify using our model and at the same time we also don’t want the game to feel cold and formulated so a guided form of human subjectivity is still very much a necessity in the process (although importantly, as a supplement rather than the driving force).

Once again, this major change in the underlying economic model is well underway and very close to being released into the game, we certainly have some exciting times ahead!

 

The Complexity Challenge

One of the main challenges that came up in our effort to automate the economic balancing was that we really needed to understand the complex relationships between the items, quests, achievements as well as locations and activities that can be performed against/with specific items at specific locations.

To look at a specific example, let’s consider everyone’s favourite mythical creature, the Bigfoot:

image

to catch the Bigfoot (in order to cure him of the corruption caused by Stariums, no harms are done to creatures that you catch I must add), you need to consider:

  • location – Bigfoot is only available in particular parts of the world
  • bait – to lure him out you need the Alluring Goat which gives you a roughly 4 out of 7 chance of seeing the monster
  • trap – you need a trap strong enough to hold him after you’ve managed to lure him out, and only the Musket-teer Trap is strong enough for the task when it comes to the Bigfoot, even then you only have 5 out of 7 chance of succeeding (which is pretty good, considering!)
  • loot – upon successful of a Bigfoot you occasionally get a loot drop which you might need in future quests or to make other items which requires the loot as an ingredient

Looking beyond the immediate connections to the Bigfoot, you have the Alluring Goat and Musket-teer Trap which each have numerous connections of their own.

To make the Alluring Goat, you need to gather

  • Honey (which you need to harvest from Bee Hives you have to build in your homestead)
  • Goat (which you can buy baby goat from animal traders in cities around the world such as London and Nanjing)
  • Golden Hair (which is a loot drop when you catch Blonde Mermaid, Dandelion Pixie and Blonde Selkie monsters)
  • Fiery Hair (which is a loot drop when you catch Redheaded Mermaid, Banksia Pixie and Redhead Selkie monsters)
  • Yeit Fur (which is a loot drop when you catch the Yeti monster)

And similarly the Musket-teer Trap requires a number of ingredients to make, each requiring their own ingredients and so on and so forth, you get the idea.

image image

There can be an arbitrary level of connections between two items, some even recursive, and it’s nigh-on impossible for any one person to understand and rationalize all of these connections in order to make informed decisions around the design and validation of the proposed economic model. We needed a way to store and query against these connections to help us answer questions about our data model in order to build an economic model that runs along it.

 

Hello, Neo

image

If you have been following the NoSQL movement the last couple of years then you might have heard about graph databases. In case you have missed all the fun (and public confusion, debates and misguided PR about what it is and why we should care), check out my slidedeck below to get a quick introduction to the vast landscape of NoSQL.

 

One of the more mature and most widely used graph database today is Neo4j, and whilst graph databases are most frequently associated with social data (friends, followers, etc.) thanks to the prominence of companies that are operating in that space, but they’re actually very powerful and scalable ways to store and query any form of highly connected and/or complex data in general and have use cases beyond modelling social data, including fraud detection and network management.

 

Disclosure : my employer, Gamesys, already uses Neo4j for a number of social features in our real money gaming business so the choice of using Neo4j was an obvious one since we already have both operational knowledge as well as site license within the company. I didn’t go through a careful venting process to decide which graph db to go with.

 

If you represent every item in the game, ever location, recipe, monster, fish, etc. as nodes on a graph and linking them with relationships such as:

  • item A drops item B as loot
  • item A is available at location X
  • monster A can be lured by item B
  • monster A can be caught by item B

you end up with something along the lines of:

HBM-Nodes

This diagram illustrates the highly connected and complex nature of the data we’re dealing with, the result of us making a game where everything you can do and every item you find has a purpose and can be used for something else.

Each node and relationship also has a set of metadata associated with it, for instance the can_catch relationship contains the probability (or catch rate) whilst the Musket-teer Trap node contains the buy/sell price as well as stats of the trap and many more.

 

This diagram is also by no means an unconnected subset of the overall graph, for simplicity sake I have omitted many types of relationship and connected nodes. Visualizing the 5000+ nodes and around 25000 relationships in Gephi (using a Neo4j plugin), with the colour and size of the nodes representative of the number of connections it has, this is what the internal data model for Here Be Monster looks like from afar:

High-level

 

As you can see, the degree of connectedness varies greatly, and for common low-level monsters such as Sylph, Spriggan, Sprite and Salamander, they are each connected to no less than 300 location, trap and item nodes.

Sylph

 

Similarly, for common ingredients such as Salt, which can be found through many items (e.g. most fish drops seaweed and salt as loot when you catch them) and are used in the recipes of many items (Pastry, Pizza Base, Ketchup just to name a few)

Salt

 

With the internal data model captured as a huge graph in Neo4j, we were then able to ask questions that would have been difficult or impossible to answer otherwise.

To give you a few examples.

 

Impact Analysis

An item can be connected to other items, quests, achievements, monsters, and even level up rewards through n-levels of connections, so changing the value of an item can cause unforeseen and unintentional knock-on effects further down the chain (think the butterfly effect but in a miniature scale).

Neo4j allows us to start with the said item, easily and quickly traverse through the graph to identify all the nodes that are connected to it through arbitrary levels of connections.

 

Monster Hierarchy

By design, in order to catch those high-level, rare monsters, you will first catch lower-level more common monsters in the same family of related monster as you need their loot to make the baits for higher level monsters.

Going back to the Bigfoot example. You need to first catch the Yowie, use its loot to make the baits for the Yeti, and use the Yeti’s loot to make the bait for the Bigfoot which represents the top of this particular chain and whose loot drop will then be used in future quests and/or monsters.

To understand the total amount of effort required to catch the monster at the top of its chain, and to acquire its loot (which could be the goal if you need it to progress on a quest), you need to:

  • identify the monsters on the chain
  • take into account the attraction rate and catch rate of the baits and traps capable of luring and catching each of the monsters along the chain
  • drop rate of each monster’s loot and the amount of effort required to make the bait for the next monster (time, success rate, number of loots required, etc.)

Again, this is a difficult question to answer considering there are more than 100 live monsters and more are added regularly, with many such chains leading to one another.

image

 

Scarcity Analysis

As you explore the world of Here Be Monsters, you will find different types of trees, plants, rocks, butterflies, and many more, depending on where you are. For instance, you can forage durians from durian trees, but durian trees are available in certain parts of the world as you can see from the screenshots below.

image

image image

The scarcity of durian (and durian trees) is therefore linked to the number of travelable spots in the parts of the world where they durian trees are available.

With Neo4j’s help, to understand the scarcity of items in the world it became a simple query to aggregate the is_available_at relationships between items and locations. As you’ve probably guessed already, this also applies to monsters and fish which are also available at specific parts of the world.

 

So there, I hope you find these insights into the world of Here Be Monsters interesting and thanks to the guys at Neo Technology for building such a wonderful product!

 

Links

Slides for my Introduction to NoSQL talk

A good introduction to graph databases and their use cases

Neo4j use cases

Gephi – a visualization tool for graph data

Gephi plugin for Neo4j

Graph Databases by O’Reilly (free download)