Get a random entity in Google App Engine datastore

Question

I am using Google App Engine to build a web game. The game has a list of stored user-created levels (which may be a lot, and dynamically increasing as well), and each user has a list of levels which he has played already. I need to randomly pick up a level for a user which he has not played before. The Entities are modeled like this:

class User(ndb.Model):
    uid = ndb.StringProperty()
    levels_played = ndb.KeyProperty(kind='Level', repeated=True)

class Level(ndb.Model):
    #some stuff here

So basically I need to perform a query which, given a uid, chooses a random Level which does not belong to the corresponding list levels_played. What would be the most efficient way to do this?

Answer 1

There will be no easy way as you cannot do a join in a way that will perform for you requirement.

Have a look at the strategies here for selecting a random record.

Query random row in ndb

Personally I would go for the randomly chosen id from a range key then fetch the next n records option. And then check that the choice from the n records fetched is not in the list of played records. If it is pick a different level from that list of n records.

However even this won't scale well once you have large numbers of played records, unless you keep a binary blob of keys, that you can quickly check if a level has been played against.

How many levels and how many players do you reasonably expect to have. You will probably have to trade off performance for a lot of house keeping data to get the performance up once the set of levels and players grows.

An alternative approach would be to use allocids (to get sequential id's) for levels and build bitmaps. Maintain a global bitmap with a bit set for each level id that has been created and then a bitmap for each user setting each bit for a level played. You could store around 8million levels in a single 1MB blobproperty. A few bit operations and you have the set of unplayed games to choose from. Pick a bit, and fetch the level.