How to achieve Twtter of FB-like dynamism on Appengine
Kaan Soral
Problem:
On both Twtter and FB, when you visit their Homepage, you see a summary of what your friends or interests are doing.
You might have up to 1000 of these on average.
How to combine this information?
Some thinking:
a) A naive approach would be to query for everyone, every time = impossible-ish
b) To make this naive approach work we might determine popular friends of a user and achieve a query once, construct a callback for near time updates approach (to achieve real time info)
c) Another approach is to not query at all but update everyone who are subscribed to a user, when that user posts an action
This would work for FB I guess, but for Twtter, considering some people have 1Ms of followers, this may be a problem
But the complexity is the sum of all followers over the network, and this number may be low, considering not everyone has that many followers, so this might be worth it
I am leaning over the (c) method, what do you guys think, how would you implement these Social Networks?
(I combined these 2 networks in the problem definition, but you may provide separate solutions)
Barry Hunter
I think it called "fan out".
Overall its probably the most scalable - as you note a) is pretty hard-core.
However saying that using DataStore 'stringlists' could make it work
it pretty well. When someone makes a post, you add a string list
listing all their followers. Each post will have to store the whole
followers list.
Then to display someone's "inbox" you just run a query looking for all
posts with the user listed in the followers list.
- writing the post - will be expensive - due to all the index writes.
(2 per follower?) But ultimately that might be cheaper than writing a
whole entity to everyones inbox.
- and when someone gains or looses a follower you have to iterate
though their posts adding/removing the new user. (but compare that to
have to iterate though all their posts, and copy/remove all the posts
into the second users inbox)
... there probably is no perfect answer :)
> --
> You received this message because you are subscribed to the Google Groups
> "Google App Engine" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/google-appengine/-/1WEnOApSj4sJ.
> To post to this group, send email to google-a...@googlegroups.com.
> To unsubscribe from this group, send email to
> google-appengi...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/google-appengine?hl=en.
jon
Relation Index Entity pattern that Google suggested years ago (
http://www.google.com/events/io/2009/sessions/BuildingScalableComplexApps.html
). Thanks to Google's amazingly powerful datastore, you'd need to
write only a few lines of code to solve what is essentially a
difficult scalability problem. If I understand you correctly, your
approach c) is similar to this.
HOWEVER! The new pricing scheme has made the above solution cost
prohibitive. See its cost breakdown here:
http://groups.google.com/group/google-appengine/browse_thread/thread/1e8d694ce1e30cc7/b2e9e5476b33aea5?q=#b2e9e5476b33aea5
(note that the scary figure I initially arrived upon was actually an
underestimation!)
In the end I had to throw away a solution which took no more than 1
day of learning, thinking and coding, and build an alternative
solution that took a couple of weeks to complete (and involves many
moving parts, thus harder to maintain).
Here's the summary of my new solution:
1. As users make a new post, save the post ID in data structures in
memcache.
2. As a user views his feed, query said memcache data structures to
grab post IDs relevant to him
3. Take those IDs and query the datastore to retrieve matching
entities. I use Objectify's caching (memcache) to reduce datastore
hits in this step.
4. Keep data in the datastore in such a way that the data structures
in memcache can be restored, in case memcache loses them.
Now my app is different from Twitter/Facebook in that people don't
follow each other but rather a small number of topics, which keeps the
amount of data in memcache to a minimum. This lucky coincidence allows
all users to never hit the datastore as long as memcache keeps the
data structures. Unless users go back far enough and view really old
posts, in which case the data is pulled from the datastore. Luckily
this is rare.
Your case is different as the combination of user follows would result
in much bigger data. Ideally you'd want to add some intelligence so
that most use cases can be satisfied by memcache thereby keeping the
datastore costs low.
Nowadays I try to avoid using the datastore as much as possible by
using memcache or pull queues. It's a shame though, because the single
most compelling reason to use GAE over other platforms is the
awesomeness of the datastore, IMHO.
Here's my response to another fan out question
http://groups.google.com/group/google-appengine/msg/53d415bac2a04dca
Marcelo Nunes
Brandon Wirtz
GAE memcache is limited.
I’m about to crash so here is how I’d do it really fast.
User A posts update.
All Subscribed users get marker to check for updates
If UserB has Marker to check for updates he does.
If no marker last “report” is repeated.
Marker is a single byte you can keep lots of them in memcache.
GAE is going to be expensive because you basically have to plan on 1 read and write per update from the user and 1 read for each updated online friend, and 1 write for the final version
If average user is online 1 hour a day, and during their hour they see 20 updates. That is 40 reads and 20 writes
And you can’t very well miss stuff, though Fb and twitter do… but they have as much memcache as they want. We don’t.
Brandon Wirtz |
| |||
| ||||
--
