How FriendFeed uses MySQL to store schema-less data

http://bret.appspot.com/entry/how-friendfeed-uses-mysql

by paul • 17 years ago

347 84 17 years ago

bret.appspot.com

derwiki• 17 years ago

I 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?

gaius6• 17 years ago

Pretty 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_nyc6• 17 years ago

Excuse my ignorance, but what's the Postgres solution to sharding?

paul3• 17 years ago

Actually, they do, e.g. 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).

sam_in_nyc6• 17 years ago

Really 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• 17 years ago

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

gaius6• 17 years ago

But would you, if MySQL could do hash joins?

nostrademons4• 17 years ago

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

sam_in_nyc6• 17 years ago

When they say it's sharded on "user_id" what they mean is that's the field that decides which database the record is stored. It might go something like: if the user starts with 0-8, store in DB1, otherwise, store in DB2. This is up to their Datastore controller to decide how to hash based on the user_id and the number of databases.

nostrademons4• 17 years ago

This 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_nyc6• 17 years ago

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

bk• 17 years ago

> It takes a fraction of the amount of time to do native data structure stuff than it does to touch the DB several times.

And app processes are much easier to scale than a database. Even in "slow" languages (Ruby in my case) array operations are extremely fast, definitely "fast enough".

jsrn3• 17 years ago

While your approach to do this in JSON is cool, I think you have overlooked the 'direct' solution to do this in a RDBMS - with a linked list. Here is a quick suggestion (works in Postgres):

    create table l (
           id char primary key references l(prev) deferrable initially deferred,
           prev char unique not null references l(id) deferrable initially deferred,
           mydata text not null
    );

then I populate the table with your example items:

    insert into l (id, prev, mydata) values ('A', 'F', 'dA'),
                                            ('B', 'A', 'dB'),
                                            ('C', 'B', 'dC'),
                                            ('D', 'C', 'dD'),
                                            ('E', 'D', 'dE'),
                                            ('F', 'E', 'dF');

let's see how that looks like:

    test=# select * from l;
    select * from l;
     id | prev | mydata 
    ----+------+--------
     A  | F    | dA
     B  | A    | dB
     C  | B    | dC
     D  | C    | dD
     E  | D    | dE
     F  | E    | dF
     (6 rows)

to insert a new item into the list, you would do:

    begin;
    update l set prev='G' where prev='C';
    insert into l (id, prev, mydata) values ('G', 'C', 'data for G');
    commit;

so that's one update, one insert for an insertion into the list. Note that the two commands have to be in one transaction, because inside the transaction the foreign key constraint is violated (as allowed by the deferrable initially deferred modifier).

Let's inspect our list again:

    test=# select * from l;
    select * from l;
     id | prev |   mydata   
    ----+------+------------
     A  | F    | dA
     B  | A    | dB
     C  | B    | dC
     E  | D    | dE
     F  | E    | dF
     D  | G    | dD
     G  | C    | data for G

so the predecessor of G is C, and the predecessor of D is G, like specified.

Of course, you loose the ability to sort with 'order by', but that's no big deal: you know the predecessor and successor of each item, so it's easy to traverse the list in either order. This could be done on the client side [probably the best solution in your case], in the application code, or inside the database with a stored procedure or with a recursive query (coming in PostgreSQL 8.4), in Oracle it could probably be done with 'connect by'.

In reality, you would of course choose other datatypes for id and prev (probably integer), but I wanted to translate your example as literally as possible. Another problem that's easily solved: how do I get all elements of one list? Solution: Either give me one 'starting element' and the list is traversed and returned. Or introduce a listId attribute and select by that, which is probably faster but without sort order.

ryanwaggoner• 17 years ago

This is really interesting...could you do the same thing using S3 instead of MogileFS? The advantage would be cost and simple scalability, especially if you're running on EC2 so you don't have to pay for all the back and forth transfer from EC2 to S3. Concerns might be latency issues and whether this would scale to billions of objects. Other than that, it would seem like you could run a pretty huge site off of just a couple beefy servers.

nostrademons4• 17 years ago

Absolutely. It'd work with any sort of distributed filestorage. It wouldn't be too hard to wrap the S3 methods so that the API is consistent (the MogileFS API is basically a dict), so app code wouldn't even have to change.

We used Mogile over S3 mostly because I didn't realize there was no minimum monthly fee for S3.

wayne2• 17 years ago

Thanks 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

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.

hsiung3• 17 years ago

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

gaius6• 17 years ago

It'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• 17 years ago

Without locking tables?

newt0311• 17 years ago

Indeed. This is not a RDBMS problem. Its a MySQL problem and the correct solution is to use a mature DB.

hsiung3• 17 years ago

Actually we're on postgres... It just makes me nervous when the migration is taking upwards of 10 minutes to complete since some of our tables have millions of rows and lots of concurrent read/writes are happening.

bmj• 17 years ago

I find this interesting because for a previous project, we had to manage separate database instances for each client (regulations). Even though we had a database management tool that allowed us to push schema changes out to the various DBs automatically, it would be better to not have to push those changes out at all.

fauigerzigerk• 17 years ago

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

paul3• 17 years ago

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

jbert4• 17 years ago

Hi, is there any chance you could have a look at this comment:

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

paul3• 17 years ago

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

abstractbill• 17 years ago

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

pxlpshr• 17 years ago

After reflecting of my own experience with a failed B2C product, I definitely agree with the statement in your second paragraph. We spent a significant amount of time worrying about 'scaling' on a lot of fronts, not just technical, but the highest CCU we ever hit was a couple hundred users over the course of a year and a half.

From a design standpoint, I think its perfectly acceptable to keep said objectives a high priority... but from an execution standpoint, its more important to be as nimble and flexible as possible. Re-writes shouldn't be feared too much, they take less and less time if the team is applying what they've learned.

breck• 17 years ago

I tried something like this before but thought it was a "naive way to do things".

I love the advice that sometimes doing what may seem like a naive thing is good enough.

DavidMcLaughlin• 17 years ago

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

antirez5• 17 years 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/ 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• 17 years ago

How is redis different from TokyoTyrant?

antirez5• 17 years ago

it'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

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• 17 years ago

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

wayne2• 17 years ago

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

antirez5• 17 years ago

ok this sounds like I can have this goals:

1) Take Redis simple enough so that a single developer can understand the implementation in little time.

2) Run Redis on my own large sites. The problem is that while this sites are really large they are famous only in Italy. One example is http://oknotizie.alice.it

3) In the future when Redis will be stable and some little startup will start using it for real work try to collect success stories and write it in the front page of the project.

ezmobius• 17 years ago

I added consistent ring hashing and a rediscloud class to the ruby client library today. so you can now use a cluster of redis servers and have the client use ring hashing to determine the server for a given key.

yesimahuman• 17 years ago

Reading this makes me realize how naive my DB setup is for my startup.

easp2• 17 years ago

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

rads• 17 years ago

I love this key-value store trend. Looking at CouchDB in particular has made databases are fun again.

joshu2• 17 years ago

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

dmaclay• 17 years ago

This looks better suited to the B-Tree version of Berkeley-db than MySQL.

zafarali• 17 years ago

cool. very interesting.

How FriendFeed uses MySQL to store schema-less data

Related Stories