Hacker News Reader

Comment by harryh | Hacker News Reader

> Is it acceptable/preferred to store your entire db in RAM?

This is actually one of the big long term challenges we're going to have to deal with @ foursquare. Right now we calculate whether you should be awarded a badge when you check in by examining your entire checkin history (which means it needs to be in ram so we can load it fast). While this works now, as we continue to grow it will become more and more of a problem so we'll have to switch to another method of calculating how badges are awarded. Several different options here, each with pluses and minuses.

View on HN

Would it be too difficult to keep a state for every badge that you update when a new checkin happens? You'd need some specialized logic for every badge, but not much more complex than you already have. Depending on how much space you save it could be worth it.

E.g. for "you've seen foo 4 times today" you'd keep a list of the foos visited. When a new foo comes in you first remove the foos older than 1 day from the list, and insert the new foo. If the list now contains 4 foos you award the badge.

You can use a bitvector to record the badges that have any active state at all, so for badges that have no state associated with them yet (e.g. no foos seen yet) you only pay 1 bit. Or if very few badges have active state on average you could use a list of badges that have state instead of a bitvector, so that you only pay for badges that actually have active state. So total storage is 1 bit per badge or less + a couple of bytes per badge with active state?

I suspect most of check-ins are happening in big cities such as NYC, SF etc. So some sort of "geo-based sharding" would be more helpful.

Also I recommend giving @naveen a separate shard. The guy just keeps roaming around in the city. Thank you.

Why not keep the algorithm and process in batches? You don't need to have EVERY users checkin history in RAM at any moment. Throw the checkin on a queue, have a few processes that query a db for the checkin history and you're fine. Heck, if you delay the awards it's also a good excuse to throw the user an alert to come back to the site/app.

That is definitely one of the options we are considering. It (obviously) involves a change to the product, which we have to think about carefully, but it certainly could help from a technical standpoint.

It also depends on your algorithms. Some algorithms are amenable to "running tallies," so a third possible approach would be to store and update various values based only on the aggregate past data plus the incremental data, instead of looking back through the entire history and recomputing when a new piece of data comes in. This of course depends on whether or not this is even theoretically possible with what you're computing.

This is probably feasible for some badges, but would be hard to do for all of them.

This approach also increases the complexity of adding new badges, which is undesirable for product and business reasons.

It could certainly help in some case though, and it's something we're considering.

Can you design the system such that you can turn off ("darkmode") features in an emergency? For example, in an emergency you can turn off badge-awarding as it is known to be RAM intensive (and degrade by seeking to disk).

To the extent that you do this across the board, you'll have yet another tool to defend against being over capacity.

We have a framework for doing this sort of thing but it's only implemented around certain features so it doesn't provide us a ton of benefit at the moment. Obviously doing work to give us more control like this could be a big win, so we'll probably be doing some of that.

There is no better time than during an outage to add these features. In my experience, band-aids are better way to resolve an outage than fixing root-causes. Make the problem go away by commenting out code, returning empty result-sets, (or whatever) - and re-balance your partitioned database at some later date.

you don't need to keep their entire history in ram, you only need to keep their check-in history of places that they are on the verge of becoming mayors to in ram, (you are one day away from becoming mayor of xyz) and that you can calculate offline, and all you need to do is see if onedayaway:xyz:user_id => true on checkins, which you can keep in memcache

You could set up a user-place relationship and simply increment the number of check-ins for that place, then periodically correct the number, subtracting old ones which no longer count. Or look at the entire history only if there is a chance of getting a badge based on this number and otherwise just increment it. For badges for the total number of check-ins this is even easier, since no recalculation is necessary.

I suppose if your CPU load is not too high you could even run background processes to monitor "near-badge" status for all users with high enough frequency. This you could really get wild with: people with most number of recent check-ins should get scanned first and of course this list should be updated as a separate entity so it stays small and always in memory.

This is similar to one of the problem I used to deal with in tracking huge volume of billing events. Since the data (checkins) are immutable, it's fairly easy to build summary running totals daily. The total count then becomes the running-total plus the current day's count. The summary job can be run offline in the background. Just make sure to mark the current day's events as processed and update the running total at the same transaction.

In this way, the amount of current day's events are pretty small and you don't need to keep all historic events in memory.

Have you thought about how much extra overhead there is in storing the checkins using MongoDB's BSON structures? Considering how often you do this, you might consider packing a specialized version of a user's history (at least for this purpose -- sort of a denormalization) into a array of 64-bit placeIDs? This means a checkin would only occupy 8 bytes of space and there would be no overhead. 1 billion checkins = 8GB of data. You could even keep these in memcached and use a sort of write-through strategy.

EDIT: I thought about this a bit more, and the checkins are probably time-sensitive, so another 32-bit timestamp (Foursquare Epoch) would need to be stored for each checkin.

Unfortunately we have some badges that require more than just the venueid + timestamp, but some sort of "compressed" checkin format is something we'll probably end up looking at.

Bummer. It's really amazing how 1 seemingly simple (but quite important and engagement driving) feature like instant gratification badges can drive your architecture decisions and keep you guys up at night.

you can analyze the statistics of when/where specific people are most probable to check-in and pre-load (or even pre-calculate) the data in advance.

For example, starting at ~9pm the data about check-ins into library may be safely unloaded to disk (the probability of needing this data is low and reading from disk for whose rare cases would do just fine) and be replaced in memory with data about check-ins to clubs, etc...

I think what you are looking for is called "memoization" and is common in many functional programming languages such as Lisp; however many other languages have this readily available.

http://en.wikipedia.org/wiki/Memoization ; see the list of implementations at the bottom - there are ones for Lisp, Python, Perl, Java, etc.

Reply on news.ycombinator.com