Storage Schema

[elmigranto]

Schema

I've been thinking how to implement EXPIRE of invitations and filter out stale value from user's invitations list and stumbled on couple of issues with schema.

Currently we have following data sets:

• id -> json string pairs for each invitation. This is fine.
  • easily expired with redis command
  • could be easily changed to hashes, should we need more complex stuff
• username -> [list of json strings] lists for each user store 2 extra copies of invitations (from and to). This is not right, I think.
  • ineffective check for expired ones: doubles amount of JSON.parse calls, still need to MGET
  • individual items can not be expired
  • ineffective deletion of multiple items (need multiple LREMs for this; or recreate list which is not really possible except by DELeting key followed by multiple RPUSHes)
  • removing element from list is not really possible since there are no guarantee on format of json string provided by serializer so we can't search for it: like whitespace, order of keys, etc.)
  • duplicates (???)

I suggest instead of lists with JSON we store SETS of invitation IDs for each user, and retrieve required invitations with MGET. This way we could identify expired invitations (nulls in MGET results) and update user's invitations set by SREMing.

I couldn't come up with a way of removing IDs of expired invitations from the lists of users which are other part of invitations, but that shouldn't be a problem.

Generating IDs

These should probably also depend on current time, or some autoincrementing value, so we definetly won't get collisions.

[j3k0]

Hi there!

Schema

Little things concerning this design:

• Expiring the invitation is needed so the db doesn't fill up with data from inactive users that quit playing.
• Active users will cleanup their invitation list by themselves.
• We need to expire "username -> list".
  • A user that didn't SEND, RECEIVE or DELETE any invitations for (say) 60 days is probably not interested by the game.
• The fact that an invitation exists for 1 player and not for the other doesn't matter, it has no side effect.
  • If other player rejects the invitation => no effect
  • If other player accepts the invitation => game will start, which is fine because you're the one who sent the invitation in the first place.

That's why we can keep the "Listing of invitations" feature O(1) by putting all data in "username -> list" (not only the ID).

hash

Actually your set idea made me think about duplicate invitations. One nice way of preventing that would be to put the invitation data in a hash (myusername -> otherusername -> json) using HSET.

HGETALL to list all invitations.

We can expire the myusername key (make sure to update expiry date on each write on the hash).

Generation of IDs

This token contains 32 characters from 0..9..a...z (36 possibilities)

36^32
63340286662973277706162286946811886609896461828096L

That 166 random bits. Guys did the analysis for 122 bits (this it's used by UUID v3) and said it should not be a worry http://en.wikipedia.org/wiki/Universally_unique_identifier#Random_UUID_probability_of_duplicates

[elmigranto]

• When user lists invitations, we're should not include expired ones, so we need a way to filter out old invitations.
• When expiring user's list we need to remove all the invitations as well, so we will need to do it manually. (Periodically listing every user's list and checking for oldest invitations?)

hash (myusername -> otherusername -> json)

So hash value would only store one invitation? Or do we serialize JS Array there?

That's why we can keep the "Listing of invitations" feature O(1) by putting all data in "username -> list" (not only the ID).

LRANGE is O(N), maybe there's a special case for LRANGE(0, -1) but I doubt it. SMEM followed by MGET are O(N) as well.

[j3k0]

Alright after a bit more thinking, let's go for the solution you suggest:

• "username -> list of id"
• "id -> json(invitation)"

I should not forget that "premature optimization is the root of all evil"

[elmigranto]

I think username -> set of ids is even better for that — add/remove is easy and O(1).

There are no way to expire user's list, though. We can either run periodical clean up jobs (like drop all userlists, recreate them from current invitations), or we can store username -> set of id:other_user strings, so we know all the places to remove expired invitation.

[j3k0]

Or simply expire the whole "username" set.

[j3k0]

BTW, I'm starting to think about next week. Wanna talk about it today? If so, I'm on Skype.

[elmigranto]

Or simply expire the whole "username" set.

Yeah, that sounds better. So with each invite action for username we refresh username set to expire in 15 days, same for invitations created.

Wanna talk about it today?

Sure, I'll ping within 30 minutes.

[j3k0]

Exactly.