Comment by nostrademons | Hacker News Reader

Comment by nostrademons | Hacker News Reader

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.

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.

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

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.

Aha! I did forget the linked list approach. So essentially, each item on the list stores what is before (or) after it. I'm assuming it's an arbitrary choice that you're using "prev" instead of "next," correct?

The use of deferred, I've never heard of, but it makes perfect sense in this case. Unless, of course, you want to insert the record first and then modify the update to exclude the item you just inserted.

Right now, I'm using MySQL.. I only have 4 tables, and product is not launched. Would you advise switching to Postgres?

> I'm assuming it's an arbitrary choice that you're using "prev" instead of "next," correct?

yes, in effect it's a doubly linked list (circularly doubly linked), so you could remember the id of the first element of the list and then traverse in any order as long as this id does not reappear.

> Unless, of course, you want to insert the record first and then modify the update to exclude the item you just inserted.

yes - in this case you would get a violation of the unique constraint:

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

this would violate the unique constraint for prev, because after the insert (but before the update!), both the new element and the element not yet updated have prev set to 'C' - the transaction will then be rolled back.

In standard SQL this would be possible because it allows to declare unique constraints (and I think other constraints, such as check clauses) as deferrable, too - PostgreSQL doesn't implement this, it allows deferrable only for foreign key constraints. But usually it's no problem to order the commands in a way that only foreign key constraints get violated during a transaction.

> Right now, I'm using MySQL.. I only have 4 tables, and product is not launched. Would you advise switching to Postgres?

as an entrepreneur, you should probably do what's best for your customers - and they will likely not care which RDBMS you use:-) Perhaps you could play around a little bit with PostgreSQL on the side and (perhaps) make the switch once you are comfortable with it. And keep your JSON-based lists - if the system works, why bother with a rewrite / schema change (for now?).

Considering momentum, I think PostgreSQL is gaining steam while MySQL is losing momentum (some key developers left after the aquisition by Sun) - of course, that's my subjective impression.

Technically, of course I think that PostgreSQL is better - here is a good comparison: http://www.wikivs.com/wiki/MySQL_vs_PostgreSQL for amusement, read the discussion here: http://www.reddit.com/r/programming/comments/764fp/mysql_vs_...

There's one more thing I forgot to mention...

The data I'm having the user order is not only order-specific, but is recursive. That is, one of the items on the list, rather than be a letter like "B" can be a list in and of itself. It's basically like "files and folders"

A major problem isn't only the UI, which took me days to make (drag and drop for files/folders ... anybody seen anything like this done before in HTML+JS?), but mostly is in the updating/validation. I receive information, like "moved item: /path/to/item to before /some/other/path" and I now need to make sure this is a valid action (eg: can't put a folder into one of its own subfolders, can't put a file in a file, etc), and also update the database to reflect this.

I chose to use JSON to encode objects in the DB, then decode them into an array, and do some easy/fast array stuff to perform the action they requested. Just judging on the array code, which does several "isset()" calls and splices, I'd imagine doing this with a DB would be a major heartache... but I have no doubt you'd be able to come up with some brilliant way to do it.

To each their own :)

> To each their own :)

yeah, of course! And if it works, then, by definition, it's good for your customers and thus for you! Also, your approach is probably more flexible (no fixed schema for the recursive list structure), which makes it easier and faster for you to iterate and react to customer feedback.

If at some time you want to have a more fixed structure or let the database do some of the server-side validation work of your tree-like structure, here is a good writeup by Phil Greenspun showing how to model and query tree-like datastructures with an RDBMS: http://philip.greenspun.com/sql/trees.html (the rest of the document 'SQL for Web Nerds' is also quite good stuff: http://philip.greenspun.com/sql )

he uses 'connect by', which is a non-standard Oracle extension, the same thing can be achieved with 'with recursive'-queries, which is standard SQL (1999) and part of PostgreSQL 8.4 Also, Joe Celko's Book 'SQL for Smarties' has a good chapter covering hierarchical data structures in SQL (he also has a separate book about 'trees and hierarchies' in SQL).

Oh, and good luck and much success with your startup!

A tree widget with DD? http://extjs.com/deploy/dev/examples/tree/reorder.html

I bet there are lots of others too. This doesn't sound like something you'd ever want to write yourself (unless the widget IS your project).

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.

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.

Reply on news.ycombinator.com