I wrote this article pretty much for Hacker News since when there have been previous articles that have made it to the home page there have been questions about what exactly our graph database was.
That's the one basic requirement for use in a website backend these days.
There are plenty of quite profitable websites which do not have this requirement. It is almost peculiar to sites which are trying to show display advertising to groups of users larger than many nation-states.
You can make an awful lot of money with one commodity server if your business model supports it. I used to have an effective CPM of $80 and I know one which has in excess of $500. No, that is not a typo. (That is on six digits of pageviews per month.)
You know how much scaling you need when essentially get 50 cents a pageview? Not much at all.
FogCreek has, if I recall correctly, one database server. I haven't read how many total machines they're using recently but its a "count on your fingers and toes" number rather than a "zomg we need a colo facility to ourselves" number.
I figured that most sites who would be interested in such a database either fall into the retail (recommendation) or the community (social graph) category. Both operate mostly on volume and the last thing you want is a hard bottleneck just when you're at the verge of becoming successful.
But well, if your business model doesn't require scalability on the web-tier then yes, these concerns ofcourse don't apply.
Also most websites probably don't need a graph database. But the few who do will likely also need the scalability - at least I cannot imagine many interesting web-applications where your one beefy box could possibly scale to a significant userbase (unless you're talking the z-series category of beefy).
Ofcourse there are still many interesting applications outside the public interweb.
Yes, mirroring may work to a point but falls down eventually in write-heavy applications. Ideally you want something that you can just add machines to and it will scale near lineary. I'm not sure if that's entirely achievable for a graph search, but that's where my question was heading.
However, that is a lot of data to be writing into your graph, especially with how crazy fast writable media and storage is getting these days. YAGNI.
Now, on the theoretical side of things.. "How would you create a linearly scalable graph database across machines?" I don't know how I would make it so that I could maintain the same kinds of speeds for interesting graph traversals.
Splitting things is the relatively easy part -- it's building the consistency model for multi-node systems that's tricky.
For read-write partitioning it's pretty simple -- each item is largely independent; it has its columns of data and is handled by an index, so once you're just reading / writing / updating items, it's no problem to do the hashing from key to index then using that index to locate the appropriate node.
The devil is of course in the details. If we see that barrier approaching we'll plan ahead for scaling out this way.
However, just doing some quick calculations, looks like the English wikipedia gets 5.4 billion page views per month, which translates to about 2100 per second. On my MacBook I get an average query time on our profile dataset for wikipedia's graph of 2.5 ms per query -- meaning 400 requests per second, extrapolating from there, scaling that up to 6x that on a hefty server doesn't seem unreasonable, and that ignores the fact that we could go further in caching the results (since most of them would be duplicate requests) to push that number up even higher.
So, yeah, it's an issue that's in the back of our heads, but not one we're currently dreading.
Is the dataset changing (being written to) while you make those queries?
Still an untested assumption, but the system is architectured to hold up well in those situations and I think that it will reasonably scale there.
Granted the real question becomes storing data not handling that number of requests, but a database that knows where a bunch of dumb files scales really well. (If you look into things this is Facebook's basic approach.)
I'd venture the guess that you'd be talking quite a different budget than a bunch of pizzaboxes in a horizontal setup though. The SAN to handle 5k IOPS alone will set you back by an interesting amount (even more so when you consider mirroring, which you'd probably want to have at that scale). I'd also be worried about the network - GBit/s is probably not going to cut it at that rate anymore.
So, all in all this is precisely why I asked about horizontal scalability. A setup of 5 machines that handle 1000 reqs/sec each is usually cheaper than a single machine to handle all of the 5000/sec.
PS: Upgrading 10gb Ethernet is not really that expensive now days if he is only linking a few web servers to two databases.
EDIT: To give you some idea what flash can do http://advancedstorage.micronblogs.com/2008/11/iops-like-you... (Granted, it's a stupid video, but 150,000 Read IO's and 80,000 write IO's and 800MB/second of bandwidth on two PCie Cards in 09 / 10 with fusion IO doing the same type of thing today).
The SAN comes into play when a single box can't deliver the IOPS anymore - remember it's not just a matter of adding SSDs. At those rates you start touching the controller and bus limits. Likewise a saturated 10Gb ethernet link causes a significant interrupt-rate (older cards would bottleneck on a single core) that often exposes interesting corner-cases in your OS and hardware of choice.
I'm not saying it's not doable and I know what SSDs are capable of (we just fitted a server with X25's). I'm just saying that your estimate of $10.000 is very optimistic, add a zero and you'll be closer to home. That's because I still think you'd definately be talking an xfire 4600 class machine and a SAN.
Anyways, this is all speculation. Wheels made some reasonable statements that they have it on their radar and I'm definately looking forward to some real-world benchmarks with a concurrent write-load.
The first time that I implemented a system like this back in 2004 I did things that way. That's in theory more flexible, but since we had a specific class of applications in mind in this case it's for our uses faster to check if an item has a given tag just by having a list of tags associated with each item. The typical access patter for us means that we're already looking at an item and just want to know if it has a given tag.
The place that would be most relevant would be if we were considering bypassing the file system altogether and moving to doing raw-I/O on the disk itself and tried to account for disk geometry, which would be less useful with an SSD. But in practice that's not on the near term radar anyway.