10 ms·
How FriendFeed uses MySQL to store schema-less data
- derwiki 18y agoI like the trick for getting around index creation and deletion, I wasn't aware that MySQL required a full table lock. I checked the docs for DB2, and it allows read/write during index creating -- is this a MySQL only limitation or do the other major databases impose the same restriction?
- gaius 18y agoPretty much it's MySQL only. Most of the MySQL posts here are actually about clever ways to do things most DBAs and developers have taken for granted for years. Do you wonder why no-one seems to be writing blog posts about "sharding" Sybase or DB2 or Oracle or Postgres...?
- sam_in_nyc 18y agoExcuse my ignorance, but what's the Postgres solution to sharding?
- gaius 18y agoIt's to write efficient hash joins, partitioning and row versioning into your core database engine.
- simonw 18y agoHow do hash joins help with sharding? Surely once you go above a certain number of writes per second you're going to need to have more than one writable database server, at which point you need to start partitioning and better join algorithms aren't going to do anything to help.
- gaius 18y agoIf you can't hash join then you can't join over large datasets anyway, so sharding costs you nothing in that respect. Right now, using off the shelf kit and doing nothing particularly clever, running a major commercial RDBMS you could do 10,000 commits/sec and handle 100T of data on a single instance. Sure it would cost you a pretty penny, but the thing is, unless running a database is the one competitive advantage your company has, you're better off keeping your people focussed on the thing that does make you money.
- simonw 18y agoWhich commercial database? Any idea which web scale applications are using it, and why the other ones aren't?
- nl 18y agoI'm not too sure if you are arguing for or against the commercial RDBMS. To me, that sounds like a pretty good argument against it - the great thing about MySQL/Postgres+Sharding is that it scales down, as well as up. You can start out with a single server, then gradually add in extra servers as you need them. With the "single big DB server model" it doesn't work like that - you have to make a pretty decent investment early on in the software licence, build your software to use it, and then the pricing isn't linear, either. Plus, the backup/redundancy thing sucks too - with sharded MySQL you need a couple of spare cheap servers, but with Oracle etc you need to pay twice for the licence and a second server. OTOH, in a corporate environment it's much easier to predict your usage and the pricing is easier to justify. Also your priority is safety+justifiability first rather than price or even price/performance.
- paul 18y agoActually, they do, e.g. http://highscalability.com/skype-plans-postgresql-scale-1-billion-users http://highscalability.com/skype-plans-postgresql-scale-1-bi... MySQL is popular with startups though, so it's not surprising that there's a lot written about it. It's true that MySQL has some lame limitations, but I don't believe that there are any silver bullets out there. Google tried to switch their ads system from MySQL to a "real" database once, and it was basically a disaster and had to be abandoned in favor of MySQL (I wasn't working on it, so I can't really give all the details). Another problem we had with MySQL that Bret didn't mention was that it would try to be "smart", and sometimes it would "randomly" (from our perspective) choose a very inefficient strategy, and we would have to waste a lot of time figuring out what it was doing and how to force it to do the right thing. The approach Bret describes basically avoid any MySQL "smarts" and treats it as a dumb, but fast and well tested B-tree. This gives us fairly reliable and predictable performance characteristics because we know exactly what it's doing (mostly).
- davidw 18y agoNo, there are no silver bullets, but it seems to me that people reach for Mysql a bit too quickly, without considering the pros and cons. And while it's improving, Mysql has had many frustrating things in the past... to me it's always seemed like a "worse is better" kind of thing. Sure, it's "fast", but at what cost? Once you go to InnoDB, you lose that speed advantage. One thing that's not a tech tradeoff, and is generally a Postgres win, is the BSD style licensing. You can take Postgres and do whatever you want with it with no worries. > Google tried to switch their ads system from MySQL to a "real" database once, I hope the part that actually handles money has been fiddled with by Google to be robust.
- nl 18y agoActually, Postgres doesn't have any great out-of-the-box solution for partitioning the database across machines. The usual suggestion is Slony, but that is no where near as robust and widely deployed as MySQL replication. The GPL licence for MySQL isn't really a problem for webapps anyway. OTOH, Postgres does somewhat better than MySQL on a single box with multiple cores (it's fairly linear up to 8 CPU, which is much better than MySQL) - mainly because of the work Sun put into scaling it before they bought MySQL. (At least - that's according to some people from Sun who do a lot of performance work with both databases)
- sam_in_nyc 18y agoReally a great way to do things... thank you so much for sharing this. I can't really see any disadvantages to doing anything this way. You still obtain access to data in a relational sense, though where normally you compare columns of a table you'd now do joins. For example, you can get the unique users that have submitted a link by joining the index_link table to the entities table, then joining that to the index_user table. The problem here seems to be that sharding would prevent this type of operation... so how do they get around this? It's possible they just don't need this data, but lets assume they do. I'm presuming they have some slave(s) munging non-realtime-needed data into whatever real relational tables they choose. But, if the problem because realtime, I'm at a loss as to how they'd do it.
- finiteloop 18y agoWe don't do any joins in MySQL. We query the indexes in all of the shards in parallel to get a list of entity IDs and then query the entities tables in all of the shards in paralel to get the entity bodies as a second operation.
- gaius 18y agoBut would you, if MySQL could do hash joins?
- deleted 18y ago[deleted]
- nostrademons 18y agoThey explained the sharding in the text - I glossed over it on first read-through too. When they say "join" in quotation marks, they don't actually mean a join in the MySQL sense. Rather, the initial call to user_id_index.get_all reads all entity_ids for that user into the Python code (they say it consults all shards for this, but isn't the index sharded on user_id, so all entities for a given user_id live on one shard?). The Python code then uses whatever shard function applies to the entities table to query its database backends, selecting the relevant entities. Then the Python code filters the returned records by the indexed field (in case the indices are out of date) and returns it. As for disadvantages - well, it's denormalized, for starters. ("Normalization is for sissies", says Cal Henderson.) If an indexed field changes, you need to update it in both the index and the relevant entities. There're also a bunch of little inefficiencies, places where they traded performance for scalability. Imagine if you naively plugged this engine into an app with only 10 records: instead of a simple index search, it'd have to go to the index table, fetch the relevant entities, go to the entities table, fetch them, filter on indexed value, and then return them all. But then, if your database fits on one machine, you don't have the same sort of engineering challenges FriendFeed does.
- nostrademons 18y agoThis is really interesting. We did something similar for GameClay. I stored game properties as JSON-encoded dicts stored in MogileFS, then had a "regular" MySQL table that would point to the MogileFS key for the file, then the Python code would just read it out, use a JSON library to parse it, and manipulate it as a Python object. We had normal MySQL indexes on all the game metadata that appeared in the UI, so if you want all arcade games that nostrademons has posted, it would do a normal index search on (nostrademons, "arcade"), find the Mogile key for that, and then fetch it. We never got to the point where we'd need to shard, alas. I'd like to think I would've thought of the index-per-table approach independently, but probably not. Curiously, I did things this way for ease of development, not performance (and there were probably lots of little things that would've killed our performance anyway - it's really hard to diagnose performance bugs until you have real users banging away). We needed a storage system - MogileFS and MySQL work out of the box. We needed a data format - JSON works out of the box. We needed to be able to change game schemas rapidly, since we kept finding our existing design was not really fun to play with (and that's what killed us, ultimately). The rest of it followed pretty obviously.
- sam_in_nyc 18y agoI just recently wrapped up using a similar "store serialized data" set-up myself. In my example, I'm allowing the user insert/remove/reorder items on a list. This type of operation is pain to do with SQL operations. If you have a list, A,B,C,D,E,F and you want to insert G before C, then you either have to: delete all, then insert A,B,G,C,D,E,F. set "sortnumber" on G to "3", and increment sortnumber on all >= 3. set "sortnumber" of G to be the average of B and C. The latter is the cleverest, but eventually you run out of space in floating-point land, unless you have a Cron come in and clean everything up periodically. And of course, reordering (the example was an insert), and removing need to be considered as well. So it's a choice between lots of deletes and inserts (but really easy). Semi-annoying logic of reordering/removing and a few updates. Or clever hack that requires a cron to cover your ass. What I did instead was stored the list as JSON, convert it to an array, and use array splicing functions to reorder things. Then, I convert it back to JSON and store it. It's worked extraordinarily well... It takes a fraction of the amount of time to do native data structure stuff than it does to touch the DB several times.
- wayne 18y agoThanks for sharing. That was very educational. We store data in a really similar way at Spock, pointing all our reads at a big MySQL table which essentially just has an id column and a really big text column containing all the values, JSON-encoded, w/roughly the same number of rows as the FriendFeed table. Our DBA wrote a blog post about it a while back: http://www.frankf.us/wp/?p=17 http://www.frankf.us/wp/?p=17 The way you guys create/delete indices and avoid all the replication nightmares sounds super cool. All of these solutions ultimately end up sounding like a poor man's Big Table.
- deleted 18y ago[deleted]
- hsiung 18y agoThat's reassuring, I thought I was the only crazy fool who was storing json objects in database columns =). We do something similar for some of our data models at thesixtyone.com. It's really nice for not having to bring down the site for schema upgrades.
- gaius 18y agoIt's really nice for not having to bring down the site for schema upgrades. All the other popular databases let you modify the schema online. This feature has been taken for granted for over a decade.
- bdr 18y agoWithout locking tables?
- gaius 18y agoYes.
- newt0311 18y agoIndeed. This is not a RDBMS problem. Its a MySQL problem and the correct solution is to use a mature DB.
- apgwoz 18y agoEven in Oracle, we've had to schedule downtime for a single column schema change and population for 45 minutes. I would call Oracle "mature." Note: I wasn't involved in doing the update, so it's possible there was a better way to do it. The table is used by about 50 different applications.
- fendale 18y agoAlmost all major oracle operations can be done online ... Index rebuilds, table reorgs etc. Depends how much hardware you have how much it affects things ...
- fauigerzigerk 18y agoWe're doing something very similar to store RDF data. Our reason for doing it this way isn't performance but rather RDF's pretty intricate schema requirements (and opportunities). The drawback of using this scheme is that it roughly doubles the amount of data stored. Contrary to Friendfeed, we have to use joins a lot because analysing data is the purpose of our application. We tried to do it with mysql, but mysql turns out to be completely unsuitable for the task due to its lack of merge or hash joins. I'm quite surprised that someone like Friendfeed would change their entire data model for performance reasons instead of considering a stronger RDBMS (of which there are many). Their problem with index maintainance isn't exactly new. It's a solved problem that needs no wheel reinventing and doesn't merit the increased complexity of asynchronous index updates in my view.
- paul 18y agoAnother interesting detail is that this is roughly the 4th iteration on the FriendFeed backend since we launched 17 months ago. If you look at the the graphs at the bottom of Bret's post, you can see that our previous system was about to die -- average pageview latency had increased from about 135ms to 260ms in less than a month! (not a good trend) This new design also accommodates some important upcoming features that would have been problematic in the old system. This experience reinforces my belief that it's better to be quick than brilliant. If we had wasted a lot of time trying to build some really smart, super-scalable system right from the start, it would have inevitably been over-optimized for the wrong things, since the product and requirements have changed quite a bit since launch. By continually rebuilding the system, it stays relatively simple and close to our actual needs (plus it incorporates everything we learned from the previous iterations).
- jbert 18y agoHi, is there any chance you could have a look at this comment: http://news.ycombinator.com/item?id=497070 http://news.ycombinator.com/item?id=497070 and let me know how you resolve this problem in practice? (Or correct my understanding if there is no problem really).
- paul 18y agoIncreasing the number of shards is similar to changing the backend infrastructure, but simpler. Downtime obviously isn't acceptable, so when switching from one system to the next, we have a period during which we write to both so that it is safe to read from either one. Other schemes could be used for resharding, but this is simple enough and also works for other changes, and in practice we've changed the schema more often than the number of shards. Also, keep in mind that it is ok to have more shards than you really need (multiple shards can run on the same machine, for example), so resharding needn't be a common operation.
- deleted 18y ago[deleted]
- abstractbill 18y agoThis experience reinforces my belief that it's better to be quick than brilliant... I've come to the same conclusion during the past year and a half of working on Justin.TV. If I was writing a list of pieces of startup advice, this would be #1.
- DavidMcLaughlin 18y agoExcellent article. I work in an environment where we have serious vendor lock-in and the people in charge of infrastructure have a real fear of change. I have free reign to implement in any improvements in our performance and code so long as I don't make things difficult for them. Thus, the idea of a MySQL cache system is something I've been planning to look at for a while as it plays with the existing infrastructure. This (seemingly proven) system will make things a lot easier, so thanks for sharing.
- deleted 18y ago[deleted]
- antirez 18y ago"However, none of them seemed widely-used enough by large sites to inspire confidence. In the tests we read about and ran ourselves, none of the projects were stable or battle-tested enough for our needs" Ok, just some hour ago I released the beta-3 of Redis (http://code.google.com/p/redis/ http://code.google.com/p/redis/ if you care) and I'm near to feature-freeze with exactly with this goal. To make it rock solid (I'm going to use it in my startup's web stuff with a lot of users/month, so I care about stability). The question is: what's in your opinion the right path to make a system like Redis stable and reliable for the real world usage? What to publish on the site in order to inspire a good feeling about stability? Thanks
- richcollins 18y agoHow is redis different from TokyoTyrant?
- antirez 18y agoit's higher level. Not a plain key value stuff. For instance as value you can have a list or a set, push/pop elements, ask the server for all the keys matching a given glob style pattern and so on. Most of this operations are atomic in order to make sure there are no race conditions. You can read more about the difference between Redis and other key-value stores here: http://code.google.com/p/redis/wiki/FAQ http://code.google.com/p/redis/wiki/FAQ Basically the long term goal is to have something between a relational DB and a key-value DB. Not all the higher level features must be killed in order to be scalable.
- zandorg 18y agoHas anyone here got TokyoTyrant working under Windows? I found a static library binary for Windows, but the header files need to compile are either not there, or the code references some bizarre POSIX stuff which isn't easy to hack into working under Windows.
- wayne 18y agoNot to be a naysayer, but I don't know that there's a lot you can do except run it yourself on a large, popular site that people have heard of. Companies like FriendFeed will use memcached cause LiveJournal/Facebook use it, they'll use MySQL because just about every web startup uses it, but no matter how awesome a project is, they're not going to use something complex that a few developers or some other startup wrote that hasn't been battle-tested on a large, well-known site. It's too risky compared to writing another one yourself that you understand.
- yesimahuman 18y agoReading this makes me realize how naive my DB setup is for my startup.
- easp 18y agoDid you read the part where they said this was the third or 4th iteration of their DB backend? Or maybe I read that somewhere else. Point being, experience will come.
- d13hard 18y agodon't go too gaga over this hash-on-the-db appraoch, or its non-rdbms based solutions at all the major web companies. you get lots of scaling, great performance, but you have zero features. you can't even really query. these models have superficial appeal until you realize that all the querying you would do in the db model now has to be done out-of-band into some sort of materialized view...e.g. if you want to have a group of rows that meet some criteria, you need to store it somewhere else out of band...the database can't help you with realtime queries because there is nothing to query on in general i would avoid this model unless you have a huge scaling issue
- rads 18y agoI love this key-value store trend. Looking at CouchDB in particular has made databases are fun again.
- joshu 18y agoThis is great. I sketched out a similar design for the Delicious backend, but the team that built it went in a completely different and stupid direction. Oh well. Mine also had: - some way to do server locality (I don't think FF needs this) - some way to do table locality (I don't think FF needs this either) - per blob versioning and type - a virtual shard layer, so new machines can be added inexpensively Sorry for any inadvertent whining, incidentally.
- d13hard 18y agogiven that you were at y, i'm wondering if you were proposing a udb fork plus some features....
- dmaclay 18y agoThis looks better suited to the B-Tree version of Berkeley-db than MySQL.
- zafarali 18y agocool. very interesting.