Building a badge system that gives feedback in real-time on top of Google App Engine involved more than one technical challenge worth sharing. This long post winds in and out of geeky tricks we used for the Khan Academy badges, ranging from protocol buffer serialization for fast memcache communication to App Engine’s mapreduce framework.
Everything mentioned below is qualified with the standard “I was just figuring this out and I’m far from a Python expert and you probably know a better way and please tell me in the comments” disclaimer.
Self-imposed requirements
- Must support lots of deep badges for interesting behavior like “Answered 90% of the questions in this exercise correctly” and “Watched half an hour of video and answered 20 problems in 45 minutes,” not just two or three shallow “Watched 10 videos” things.
- When badges are earned the user must see the award immediately, not a few pageloads or minutes later.
- Must be implemented on Google’s App Engine and, more notably, their NoSQL BigTable datastore.
An immediate challenge
How do you constantly query for every single badge a user may have earned with every single action they take so you can provide immediate feedback without causing terrible performance problems?
for badge in possible_badges:
if not badge.is_already_owned_by(user_data=user_data):
if badge.is_satisfied_by(user_data=user_data, action_cache=action_cache):
badge.award_to(user=user, user_data=user_data)
Would switching to SQL really help?
At first glance it sounds like a real pain to try to figure out who owns what badge without being able to run complicated SQL queries with joins and SUM()s and AVG()s and stuff. You can’t really do that on App Engine.
Even if we assume for a second that we’re dealing with a SQL database and can straightforwardly write a single query for each badge that determines which users are deserving, we’re still in for a doozy.
We’ll wind up with a system that adds one new (probably complicated) database query for every type of badge we add, and running every single one of these queries every time a user performs some of the most common actions on the site (like watching a piece of a video or answering a question) in order to provide immediate badge feedback will quickly degrade performance of those actions.
It doesn’t take a performance expert to tell you that building database queries for a badging system is likely to require a bunch of messy joins, aggregate functions, and other headache-inducing bottlenecks that you don’t want your most frequent pageloads sitting around waiting for every. single. time.
Anything pretty that catches your eye when a new badge slides down is almost certainly the work of Jason.
That’s why the common wisdom when building badging systems in web apps these days is to drop Requirement #2 instead. If you don’t have to show the user immediate feedback after they’ve performed the specific action that earned a badge, you can take your pick of the cron job/scheduled task litter to rake through your database in the background and award badges anywhere from a few seconds to a couple hours after the user has technically paid their dues.
Firebug’d. I don’t have this many badges.
While using a SQL database would certainly change the nature of the solution, it wouldn’t resolve the performance challenge associated with providing immediate feedback.
Why do we care about seeing badge awards immediately?
Games aren’t just more fun when you get immediate feedback. They make a lot more sense. When a new badge award slides down from the top of the screen, it’s our chance as developers to not only entertain the user but to communicate that whatever you just did, it’s a step in the right direction…so keep going. Handy usability tool.
Guidelines for tackling this problem
- Each badge has two sets of data at its disposal when assessing whether or not it’s been earned by a user: long-term, precalculated stats that are stored for each user (like number of video seconds watched per playlist) and a medium-term, highly-optimized in-memory history of the user’s most recent actions on the site, (Last Action Cache, explained below).
- Don’t talk to the datastore for anything when figuring out whether or not each badge has been earned. Don’t even talk to memcache.
- Keep the set of eligible badges for each action as small as possible. If a user is watching a video, they’re not going to be awarded a badge from the Trigonometry exercise module, so don’t waste your time.
- Every time a user performs a possibly badge-worthy action on the site such as watching part of a video or answering a question, load up the very small, highly-optimized data from Guideline #1 and pass it to each eligible badge for assessment. Depending on the state of the request, this involves at most one or zero datastore requests and one memcache request for all badges combined.
- When assessing whether or not a badge should be awarded to a particular user, fail as quickly as possible. Nothing is faster than “return False”. See the clip from badges/unfinished_streak_problem_badge.py below:
class UnfinishedStreakProblemBadge(ExerciseBadge):
def is_satisfied_by(self, *args, **kwargs):
user_data = kwargs.get("user_data", None)
user_exercise = kwargs.get("user_exercise", None)
action_cache = kwargs.get("action_cache", None)
if user_data is None or user_exercise is None or action_cache is None:
return False
# Make sure they've done the required minimum of problems in this exercise
if user_exercise.total_done < self.problems_required:
return False
# Make sure they haven't yet reached explicit proficiency
if user_data.is_explicitly_proficient_at(user_exercise.exercise):
return False
c_logs = len(action_cache.problem_logs)
# We need a history of at least 10 problem_logs in the action cache
if c_logs < 10:
return False
# Make sure the last problem is from this exercise and that they got it wrong
last_problem_log = action_cache.get_problem_log(c_logs - 1)
if (last_problem_log.exercise != user_exercise.exercise or last_problem_log.correct):
return False
# Look through the last 50 problems. If they've done at least 10 in the exercise
# and gotten at least 75% correct but haven't managed to put together a streak, give 'em the badge.
...see the rest at http://code.google.com/p/khanacademy/source/browse/trunk/badges/unfinished_streak_problem_badges.py
Precalculated stats (Snooze boring)
Standard advice for improving an app’s read performance is to break your back doing all the work on write (by duplicating/denormalizing data and recalculating/caching computed values).
We have to make sure that any long-term per-user statistic used by badges is recalculated on write and stored in the datastore for fast access during badge ownership logic. This goes for each user’s amount of time spent watching each playlist, total number of completed exercises, longest streak of correct answers for each exercise, and more. Technically all of this data is available in the datastore’s exhaustive historical log of each user’s activity, but recalculating every time we need it is impractical.
class UserPlaylist(db.Model):
user = db.UserProperty()
playlist = db.ReferenceProperty(Playlist)
seconds_watched = db.IntegerProperty(default = 0)
last_watched = db.DateTimeProperty(auto_now_add = True)
Protocol buffer-serialized, memcached list of each user’s recent history (Hey, that’s more exciting)
If a badge needs access to information that isn’t stored in those long-term stats, it can quickly take a peek at the latest ~1,000 last actions a user performed via the Last Action Cache.
class LastActionCache:
CACHED_ACTIONS_PER_TYPE = 500
def __init__(self, user):
self.problem_logs = [] # Protobuf version of problem logs for extremely fast (de)serialization
self.problem_log_models = {} # Full problem log models
self.video_logs = [] # Protobuf version of video logs for extremely fast (de)serialization
self.video_log_models = {} # Full video log models
self.user = user
@staticmethod
def get_for_user(user):
action_cache = memcache.get(LastActionCache.key_for_user(user))
if action_cache is None:
action_cache = LastActionCache(user)
return action_cache
def store(self):
# Wipe out instantiated models before pickling for speed
self.problem_log_models = {}
self.video_log_models = {}
memcache.set(LastActionCache.key_for_user(self.user), self)
The Last Action Cache is basically a couple of arrays of two types of objects, VideoLog and ProblemLog, both of which are App Engine datastore models. It’s only special in that each array only stores the protocol buffer serialization of each object, which means extremely fast pickling back and forth from memcache between pageloads. We can retrieve the cache, push a new action, and re-store 1,000 of the last VideoLog and ProblemLog entities for a user quickly on every request because we’re a) only talking to memcache once and b) only pickling and de-pickling the already protocol buffer-serialized version of each object, which thanks to GOOG is Seriously Fast.
# Push a new video log to the cache using protobuf for fast serialization/pickle
def push_video_log(self, video_log):
self.video_logs.append(db.model_to_protobuf(video_log).Encode())
if len(self.video_logs) > LastActionCache.CACHED_ACTIONS_PER_TYPE:
self.video_logs = self.video_logs[-1 * LastActionCache.CACHED_ACTIONS_PER_TYPE:]
self.store()
The trade-off here is the reconstitution of VideoLog and ProblemLog entities from the protocol buffers whenever badges need to poke around the objects for their logic. This part’s a bit slower, so each entity is only model_from_protobuf‘ed on demand, and the deserialized instance is cached for use by other badges during the request. Since badge logic fails as early as possible, very few of the latest models are actually instantiated from their protobuf versions each request.
# Get a new video log from the cache via protobuf deserialization
def get_video_log(self, ix):
if not self.video_log_models.has_key(ix):
self.video_log_models[ix] = db.model_from_protobuf(entity_pb.EntityProto(self.video_logs[ix]))
return self.video_log_models[ix]
Ok I lied we have a background task too. App Engine’s MapReduce
What if the above doesn’t work? If memcache is down or there’s a bug in badge logic during the real-time check will a user ever get their hard-earned badge? A background task that hands out badges over time doesn’t sound so bad.
The App Engine team is building a mapreduce library that helps you iterate over a ton of datastore entities in the background and spread the task out among a bunch of different machines.
Perfect. Twice a day a cronjob kicks off a new mapreducemapper that iterates over every user in our datastore and hands out any badges they deserve, all in the background without interrupting any user experience. This is useful for backfilling new badges that we create, and if we ever design some badges that shouldn’t be awarded in real-time (think “Top Trigonometrician, July ‘11”), we’ll use this tool.
# /admin/startnewbadgemapreduce is called periodically by a cron job
class StartNewBadgeMapReduce(request_handler.RequestHandler):
def get(self):
# Admin-only restriction is handled by /admin/* URL pattern
# so this can be called by a cron job.
# Start a new Mapper task for calling badge_update_map
mapreduce_id = control.start_map(
name = "UpdateUserBadges",
handler_spec = "badges.util_badges.badge_update_map",
reader_spec = "mapreduce.input_readers.DatastoreInputReader",
reader_parameters = {"entity_kind": "models.UserData"})
self.response.out.write("OK: " + str(mapreduce_id))
It’s not perfect
We had to make lots of compromises to get instant feedback. Any really complicated badge that needs data we don’t have in our precalc’ed stats or Last Action cache will either have to wait or be awarded in non-real-time. The good news is we’ve already built a fairly deep badge collection without many issues.
We’re also relying heavily on memcache for the Last Action Cache, and if memcache goes flaky (which is a perfectly legitimate assumption) for any reason, badge progress might go flaky too. If this becomes a problem we can start running a background task that occasionally persists the memcache data in the datastore, but for now everything is running pretty smoothly.
It’s going
We’ve awarded tens of thousands of badges so far. We’re adding more types because it’s pretty funbecause it’s an effective way to drive user behavior. The first iteration of the system described here works, but it’ll need to survive the test of time and plethora of new badges we’ll be building. Here’s hoping.
class BadgeCategory:
# Sorted by astronomical size...
BRONZE = 0 # Meteorite, "Common"
SILVER = 1 # Moon, "Uncommon"
GOLD = 2 # Earth, "Rare"
PLATINUM = 3 # Sun, "Epic"
DIAMOND = 4 # Black Hole, "Legendary"
All comments and suggestions welcome.
