Facebook runs primarily out of ram via memcached. The last numbers I'm aware of were that they had about 200TB in memcache capacity [1]. They use a variety of data stores, but primarily sharded mysql. I don't have recent numbers there, but they were above 1000 master-master pairs as of 2008.

While buying that much ram sound costly, that's only looking at capacity. Assuming typical 1u servers and common pricing at the moment, you're paying roughly $1k in capital for each 10GB of ram capacity. However, each of these servers gives you a couple hundred thousand random reads per second. To duplicate that with spinning hard drives would take several hundred spindles at least. SSD's are better, but still, it ends up being a lot of devices to duplicate that io capacity.

This is why virtually everyone at stupendous scale (google, facebook, etc) ends up with very ram centric architectures.

There's a simple way to decide how much of what storage you need [2]. Look at the distribution of access times. With current technology, in very rough terms, if an item is accessed more than once a day, it's more cost effective to store it on SSD. If it's accessed more than once in an hour, it's more cost effective to store it in ram.

[1]: http://perspectives.mvdirona.com/2010/07/01/Velocity2010.asp...

[2]: http://www.cs.cmu.edu/~damon2007/pdf/graefe07fiveminrule.pdf

Anything that is both latency sensitive (web apps are) and requires high throughput is going to be RAM-centric. Even services operating at much smaller scales with "old school" single DB boxes need to keep the vast majority of active data in RAM and use things like battery-backed write caches to get acceptable write throughput. Even with the sophisticated tricks mature RDBMS software uses to squeeze every ounce of performance out of spindles, most "old school" DBAs will tell you that to get high throughput for a database you basically need to have RAM = database size.

I have had very acceptable performance for latency critical applications where the db have exceeded the available memory by a factor between 10 and 50.

So far I have never heard of any one running a commercial RDBMS reiterate the MySQL-mantra that you need the entire DB in RAM and I find it a very puzzling attitude to efficient database usage.

While you may just be trying to talk-down on the MySQL dudes, I don't think that "RAM is faster than disk, so you're more performant if you can fit your data in RAM" is really all that puzzling.

I'm not debating that RAM is faster than disk. I'm debating that you need to have the entire DB in RAM to get good performance.

Most of the time, less than 10% of your DB represents the active working-set of your data and a good database-system should be able to analyse what is being used, gather statistics about the data, use those statistics to intelligently optimize your queries and minimize the need for disk IO.

For any decent RDBMS, having to match total memory with the database size, is wasting money on RAM for very little extra gain in performance and this doesn't really make much business sense.

A concrete example would be a server I manage. It has 16GBs of RAM and handles around 5000 GBs worth of DBs. Due to a good RDBMS and intelligent caching and use of statistics, that server has a cache-hit ratio of 98%. That means that only 2% of queries entering the system results in actual disk IO.

In order to get the last 2% of queries to get into RAM, I would have to increase the system memory by a factor of 30. At that point just getting another server and setting up replication would be much cheaper and also allow a theoretical doubling of troughput.

Really. Having the DB all in RAM is not something which makes marginal sense at all when you compare it to the costs it involves. No amount of internet-argument can convince me that this goal is anything besides a pure waste of money.

There's a reason I mentioned object inter-access times. To properly size storage you need to know your query distribution.

"It has 16GBs of RAM and handles around 5000 GBs worth of DBs. Due to a good RDBMS and intelligent caching and use of statistics, that server has a cache-hit ratio of 98%."

This may be your query distribution but it plainly is not everyone's.

"No amount of internet-argument can convince me that this goal is anything besides a pure waste of money."

If Jim Gray's published work doesn't convince you there's not really much left to discuss.

> 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.

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.

Depends on what you are doing. If you have high volume and care about latency, you pretty much have to put everything in RAM.

If your disk is spinning at 6000 rpm, a given sector spins past 100 times per second, which makes lookup time anywhere from 0 to 1/100th of a second, or 1/200th of a second on average. Disks only let you look for a limited number of things at once, so you can do less than 1000 disk seeks per second. Period.

If data is living on disk and you have high query volume, it is really, really easy to blow past that limit. The solution is to shard data on multiple machines in RAM. This gives a fixed cost per unit of RAM. As long as you don't exceed available RAM, it works well. Luckily it isn't hard to monitor available RAM and respond in advance. (They didn't do that in this case.)

If you don't care about latency, or have a lower query volume, then you can live with data on disk, and frequently accessed data in RAM. A few well-designed caching layers in front can give you even more headroom. This is much cheaper. But has more complicated failure modes, and they can be tricky to monitor properly.

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

If you can fit your db into RAM that's the ideal, but of course you also have to have a reliable, persistent backup. The best current compromise is probably PCI based SSD drives.

John Ousterhout (of Tcl fame) and his group at Stanford are working on a project called RAMCloud that's exploring the feasibility of storing data in RAM at all times, using disk only as backup. See his projects page http://www.stanford.edu/~ouster/cgi-bin/projects.php for more info. IMO, given the continuous improvements in RAM prices and network latencies, this type of setup for permanent storage will be the norm in data centers in a few years.

It doesn't mean the DB files have to be stored in a ramdisk or something like that - you just need enough ram so your working set can fit in ram.

These new projects really seem a lot like re-hashing problems that have already been solved over and over again - people just keep forgetting to do proper systems engineering in the first place. There is no magic bullet.

This talk gives a good high level overview of the Facebook infrastructure:

http://www.infoq.com/presentations/Scale-at-Facebook

In short they use sharded mysql instances (sans joins) as a key-value store with memcache on top of that.

In general you want to have memcached implemented for stuff like this. Have most used stuff closer/faster with memcached.

I don't understand why they are running the whole nosql db on those monster machines - it just defeats the purpose. And sharding architecture that they are mentioning is quite error prone. I would go with read/write seperate channels for things of their nature - it appears they don't have that either.

Your first three sentences are kind of funny; many people actually consider memecached a NoSQL data store by now.

It's okay to have hundreds of terrabytes of data but you need to keep your "working set" hot. Even if you have 10TB of data, 1TB of it might actually be hot.

Monitoring your working set is tough.

Yea, but that doesn't look like what they're describing here. They seem to be describing having the entire dataset in memory.

It is easy to turn swap off. There are many reasons why it can be good to turn swap off in servers. (But only if you've got sufficient monitoring to hear about it before you run out of RAM.)

It can be entirely acceptable and preferred. Knowing your working set size and how your memory is being utilized is a critical part of any systems planning... and memory is one heck of a lot faster than disk, hands down, no debate there.

Not we're not talking necessarily about a ramdisk here or specialized software (though we could be) - we're talking about proper system design with enough ram and tuning to get the response times you need.