On Building A Stupidly Fast Graph Database

http://blog.directededge.com/2009/02/27/on-building-a-stupidly-fast-graph-database/

by wheels • 17 years ago

159 43 17 years ago

blog.directededge.com

wheels10• 17 years ago

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.

phildawes• 17 years ago

This is great stuff - many thanks!

moe7• 17 years ago

My first question whenever I read about a new database system: Does it scale horizontally, by throwing more machines at it?

That's the one basic requirement for use in a website backend these days.

patio11• 17 years ago

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.

gnaritas• 17 years ago

No it isn't, it's a nice to have but in no way is that a requirement. Most websites still run on standard RDBMs that don't scale well across many machines and frankly, most websites won't ever need to scale beyond one big beefy box. Stop drinking the cool-aid, it's killing your perspective.

wheels10• 17 years ago

At this point no, but that's a hurdle we'll cross when we get there. In theory it would be fairly easy to split things using one machine to do the hashing from name to indexes and then segmenting items across multiple machines.

anamax• 17 years ago

What are the odds that you'll become bigger than plentyoffish without having an influx of money that will let you rebuild?

ralph3• 17 years ago

Thanks for taking the effort. Are tags implemented as just references from a tag "foo" node to the tagged item?

wheels10• 17 years ago

Yes and no. This is the "small lie" mentioned in there where I said that there's only one sort of rows. The StringListColumn maintains a separate row of string values and each reference to a tag just gets an index to the tag, but tags are not "first-class" nodes in that they're not a separate node in the database.

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.

ntoshev• 17 years ago

This kind of storage should work very well with SSDs instead of disks. Is this the case?

wheels10• 17 years ago

I'm curious about this too, but the gap between now and being able to order SSDs on non-co-lo boxes means that we're not thinking about that too much just yet.

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.

finnw• 17 years ago

Did you investigate any other network DBMSes? If so why did you find them inadequate?

http://en.wikipedia.org/wiki/Network_model

wheels10• 17 years ago

Nope, or at least none that called themselves such. We tried neo4j, which exploded trying to import data on the order that we're working with and a couple of RDF databases, which survived the import, but were a couple of orders of magnitude off from the performance we were hoping for.

After writing some 8 different backends for our store class and none being within an order of magnitude of our own prototype for the sorts of applications we're doing, it seemed more fruitful to round out our own application rather than continuing the seemingly endless recurse of possible data backends which ranged from mildly to amazingly disappointing.

If you've got something specific that you've worked with in the past that you think would be worth our while to evaluate, I'd consider investing the time to try it out. But just that there exist more options that we could evaluate at the moment doesn't necessarily imply that it's reasonable to keep writing new backends, which sometimes take a non-trivial amount of effort.

ieatpaste• 17 years ago

I'm assuming this is a proprietary, so any other comments regarding RDF databases would be helpful. I've used ARC (arc.semsol.org) before, and it works adequately. Though I haven't run performance tests personally, ARC is based on PHP so it probably gets blown away by this C++ version.

emileifrem• 17 years ago

I'm part of the Neo4j team and I'm puzzled about the import problem. I don't know about the size requirements you have but you mention 2.5M nodes and 60M edges and we run systems in production with a LOT more data (billions range). So it definitely shouldn't blow up. Maybe you ran into some bug in an older release or something else was wrong.

It's also important to note that Neo4j through the normal API is optimized for the most common use cases: reading data and transactional updates. Those operations are executed all the time during normal operation, whereas an import is typically done once at system bootstrap and then never again.

To ease migration, as part of our 1.0 release (June time frame) we will expose a new "batch injection" API that is faster for one-time imports of data sets. This is currently being developed. If you have feedback on how an API like that should behave, feel free to join the discussions on the list:

   http://neo4j.org

Cheers,

-EE

tptacek4• 17 years ago

This is a great article, and I don't doubt you have a stupidly fast graph database, and I am jealous that you get to spend all day working on graph-theoretic problems. That said:

I'm not so sure of your policework on mmap() vs. read():

* The "extra copies" you make with read happen in the L1/L2 cache, making them comparable to register spills. Buffer copying just isn't expensive.

* (and here I start paraphrasing Matt Dillon) On the other hand, you are absolutely going to take extra page faults and blow your TLB if you address a huge file using mmap, which is not only going to slow down I/O but also hurt performance elsewhere.

It seems to me like you did mmap() so you could easily externalize vectors and maps. Which actually leads me to a second question:

Isn't the reason people use things like B-Trees that they are optimized to touch the disk a minimal number of times? Isn't that kind of not the case with a C++ container "ported" to the disk?

wheels10• 17 years ago

To be honest, that rationale was applied after the fact. One of the many backend iterations that I wrote, prior to the mmap backend, was using read() and friends and after porting the code to mmap-based I/O the output was faster on both warm and cold disk buffers.

I was planning a big blog entry just on the backend options that we used since I tried several combinations of I/O backends with different numbers of reader threads in our profiling dataset with different I/O elevator scheduling algorithms (switching the algorithms, disappointingly, had a negligible effect on performance and I/O throughput degraded when increasing the number of reader threads to more than twice the number of active cores) -- but that kind of slipped into the background as we started filling out the bits of the database to give it an acceptable level of robustness.

The hashing scheme that we're using is optimized for keeping a tight memory profile -- and hence disk profile. Again, much of the rationale was applied after the fact to try to explain the results of profiling. At first we tried things with B-trees and with the combination of the VM's paging and our access patterns the hashes were faster. It's possible that if we were using the direct I/O APIs that many databases use and doing all of our own caching internally that we'd be able to achieve higher throughput with B-trees.

In our case, letting the OS handle our caching and keeping identical C++ structures to our disk structures simplified the code enough to merit leaving things this way for the time being. At the end of the day, our product is a recommendation engine, not a database, so we'd like to keep the codebase relatively lean.

So, yeah, a lot of the explanations are applied after the fact from what I know of systems programming, but the results were validated through actual test runs through multiple competing backend implementations. The one we described gave the best overall results.

nkurz4• 17 years ago

> I'm not so sure of your policework on mmap() vs. read()

Scott's conclusions agree with my experiences very well: if you design around mmap(), and let the system handle the caching, you can end up with something several times faster than the traditional alternatives. This isn't to say that your criticisms are completely wrong, just that they don't match up with the actual testing.

* "extra copies" [are cheap]

True, but the real cost is the greater memory footprint. Less application buffering means more room for cached pages. And this cache is transparent across multiple processes.

* extra page faults

I think the opposite turns out to be true. Letting the system handle the buffering results in more cache hits, since the memory is used more efficiently.

* blow your TLB

Theoretically a problem, but in practice one doesn't linearly access the entire file. The beauty of mmap() is that it allows for brilliantly efficient non-sequential access.

* B-trees vs C++ containers

While it's true that you have to think closely about the memory layout of your containers, if you do so the access patterns can be even better than a B-Tree. If the container has been designed for efficient memory-access with regard to cache-lines and cache-sizes, it tends to have great disk-access as well.

What's really beautiful about the mmap() approach is the simplicity it offers. In this model, RAM can be viewed as a 16 Gig L4 cache, and disk as a multi-Terabyte L5. Just as one currently writes code that doesn't distinguish between a fetch from L1 and a fetch from main memory, mmap() allows extending this syntax all the way to a fetch from disk.

Now, this doesn't mean that one can just substitute mmap() for fread() and get any significant improvement. One needs to re-optimize the data structures as well. But the nice part is that these techniques are the same techniques used to optimize existing cache accesses, and certain 'cache-oblivious' algorithms already work out of the box.

Anyway, thanks to Scott for the writeup!

tptacek4• 17 years ago

When you say "fread()", I wonder whether you're considering that fread() does stdio buffering in userland above and beyond the small window of memory you reuse on every read (and that is going to stay in-cache) when you use the read(2) syscall directly.

jonmc12• 17 years ago

Excellent article.. I was wondering if you could help me understand why Franz's Allegrograph or Aduna's Sesame were not sufficient for you needs. Have you had the opportunity to perform any benchmarks against these graph DB's?

wheels10• 17 years ago

Tried Sesame, it was one of the graph DBs that I mentioned not being up to snuff. Also looked at Franz's DB, but based on the benchmarks they publish on their site (they've also imported a smaller Wikipedia dumb) it looked like it's about 5x slower than ours.

kmavm• 17 years ago

You don't really get into why mmap is an unpopular choice. It's not as if other programmers just forgot to read the man page. Traditional RDBMSs dislike the OS's buffer cache because the dbms has information that could better drive those algorithms; e.g., streaming data should not be cached, and should not compete with useful items in the cache. The page replacement algorithm is similarly blind; yeah, madvise exists, but it rarely has teeth. mmap is convenient, and performant enough. But if you found yourself driving hard to get the last 1% of performance out of this system, I would argue that you'd end up doing explicit file I/O and manual management of memory; e.g., the only way to use large pages to reduce TLB misses on popular OS'es is to use funky APIs like hugetlbfs on Linux.

Also, a pet peeve: mmap != "memory-mapped I/O." The latter refers to a style of hardware/software interface where device registers are accessed via loads and stores, rather than magical instructions. If you're not writing a device driver, you don't know or care whether you're using "memory-mapped I/O". mmap is ... just mmap.

nkurz4• 17 years ago

I'd be interested in knowing more about why it's unpopular. I'm a fan of mmap() because I like the way it can simplify my code, and so far I've been pleased with the speed as well. But if there are subtle downsides I'd love to be aware of them. My instinct was that mmap() isn't used much because it's relatively new, and because it's traditionally had poor support on Windows.

I'm primarily a Linux user, but the best discussion I was able to find with a quick search was this exchange on freebsd-questions from several years ago: http://lists.freebsd.org/pipermail/freebsd-questions/2004-Ju...

Do you have know of any updated articles about it's performance tradeoffs?

On Building A Stupidly Fast Graph Database

Related Stories