Posted on by Eric

Lets Make It: Planet scale UGC

LetsMakeIt was up until recently a beta Flash app that connected users to a shared whiteboard they could publish.  Since Flash is dead, I figured I’d dig through some of the lessons learned in building such a beast.  The first lesson is how to scale a service that allows near-unlimited User Generated Content (UGC).  There’s lots of details around the margins like user searches, but here we’ll focus on supporting a simplified core API one might expect to implement in UGC using Redis data structures.  Every API will run in sub-linear time (with some cheating), letting you scale to a well-populated Jupiter.

The API

create(c) // Make new content

read(id) // Get content by id

update(id, content)  // Update content by id

delete(id) // Delete by content id

follow(uid) // Follow a user with id: uid, adding them to your feed

unfollow(uid) // Unfollow a user from your feed

list_recent(a, b) // List my content, from a’th to b’th most recent

list_public_feed(a, b) // List my followees’ content, from a’th to b’th most recent

Redis State

To pull this off, I mostly abuse a distributed hashmap that maps string keys to what Redis calls a SortedSet.  A sorted set is a lot like a SQL index, allowing logarithmic lookups and adds.  Notice though, that there’s a HUGE difference swimming through the log of all content size (typical in naive SQL) versus the log of a single user’s SortedSet size, specific to that user.  You’ll see user Id’s and content Id’s as strings mapping to, essentially, their own personal mini SQL indices.

Let:

G[Cid]=C denote the Redis (G)lobal map between content Id and the content itself.

M[Uid]=Cid denote the Redis map between (M)y user Id and a SortedSet of their own personal content Ids, sorted by content Id

P[Uid]=Cid denote the Redis map between my user Id and a SortedSet of (P)ublic content Ids from users you’re following, sorted by content Id, similar to Facebook’s wall.

F[Uid]=Uid denote the Redis map between user Id and a SortedSet of user Ids that are (F)ollowing the user id key.

API Implementation

It’s assumed that every API below has your user Id to hash into Redis maps with.

create(c):

  1. Let cid = new unique, autoincrementing Id
  2. Put cid, c in G
  3. Put my uid, cid in M
  4. Get all my followers F[uid], and insert cid into all followers’ P[fid]

O( 1 + 1 + log( |M[uid]| ) )  =  O( log( |M[uid]| ) ) online work (steps 1-3)

O( |F[uid]| * log( |P[fid]| ) ) offline work (step 4)

read(cid):                                              

  1. Read from G[cid]

O(1)

update(cid, c):        

  1. Put c in G[cid]

O(1)

delete(cid):          

  1. Delete cid from G
  2. Delete cid from M
  3. Get all my followers F[uid], and delete cid from all followers’ P[fid]

O( 1 + log( |M[uid]| ) )  =  O( log( |M[uid]| ) ) online work (steps 1-2)

O( |F[uid]| * log( |P[fid]| ) ) offline work (step 3)

follow(fid):

  1. Add uid to F[fid]
  2. For all cid’s in M[fid], add cid to P[uid]

O(1) Online work (step 1)

O( |M[fid]| * log( |P[uid]| ) )  Offline work (step 2)

 

unfollow(fid):

  1. Remove uid from F[fid]
  2. Let I = the intersection of P[uid] with M[fid] using ZINTERSTORE.  These are the content Ids in my public content list that were created by user fid.
  3. For all cid’s in I, delete cid in P[uid]

O(1) Online work (step 1)

Assuming my public content list size P[uid] is greater than the followee’s content list size M[fid]:

O( |M[fid]| + |M[fid]|*log(|M[fid]|)) + |M[fid]| * log( |P[uid]| ) )  =

O( |M[fid]| * (log( |P[uid]| ) + log(|M[fid]|)) )  =

O( |M[fid]| * log( |P[uid]| ) )    Offline work (steps 2-3)

list_recent(a, b):

  1. Let k = b – a, the constant page size
  2. Lookup k elements from M[uid] using ZRANGE

O( log( |M[uid]| + k )  =  O( log(|M[uid]|) )

list_public_feed(a, b)

  1. Let k = b – a, the constant page size
  2. Lookup k elements from P[uid] using ZRANGE

O( log( |P[uid]| + k )  =  O( log(|P[uid]|) )

 

Summary

So if we cheat a bit and allow the system to be eventually-consistent (ex.: content won’t show up in follower lists immediately after publishing), we can push all 4 worst case costs of order N*log(N) into offline processes in the API call.  Remember that the N in O( N * log(N) ) is only specific to 1 user’s scale, so this is much better than it sounds!  This all lets us get away with only 4 simple structures that serve either constant or (user-scale) logarithmic online time for all operations.

Leave a Reply