3 ms·

On Building A Stupidly Fast Graph Database

159 points by wheels 18y ago

wheels 18y 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 18y ago
  This is great stuff - many thanks!
- moe 18y 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 18y 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.
    - moe 18y ago
      Well, a business model that pays 50 cent a page view sounds nice for sure - I fear most of us don't share that luxury. 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.
      - aaronblohowiak 18y ago
        I don't believe you'd put all of your information in this kind of custom db. The author remarks that they are running with memory-mapped disk back-end, which means a single machine should be able to take you pretty darn far.
  - gnaritas 18y 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.
    - moe 18y ago
      Actually it's well understood how to scale a RDBMS horizontally (sharding and partitioning). I simply asked whether there is a comparable strategy for this graph db. 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.
      - aaronblohowiak 18y ago
        So, assuming by "scaling" in the web space, you mean "be able to quickly respond to many reads and writes as my app generates" and not "handle large volumes of data", then you can do what LinkedIn does, which is to just copy the exact same graph to multiple machines, and rely on the fact that eventual consistency is good enough. You make things immediate for the user most concerned with immediate feedback (make them sticky to the graph their write updated) and for everybody else, a couple minutes of lag is no biggie. This is even more true in retail and other applications.
        moe 18y ago
        Scaling in the web space usually means both; many reads/writes and large volumes of data. 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.
  - wheels 18y 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 18y ago
    What are the odds that you'll become bigger than plentyoffish without having an influx of money that will let you rebuild?
- ralph 18y ago
  Thanks for taking the effort. Are tags implemented as just references from a tag "foo" node to the tagged item?
  - wheels 18y 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.
    - ralph 18y ago
      Thanks for the detailed answer. I've a start-up idea that needs a big dag offline for the production of a smaller (in bytes, not nodes) one used online. My intention was to use Berkeley DB. It's good to see you say it's the fastest of the off the shelf options, but it only reaches 5% of your own code! Any thoughts on what BDB is doing "wrong"? Were you using hash or B-tree with BDB?
      - wheels 18y ago
        We used hashes with BDB. I didn't dig down deep to see what was going on since we weren't really considering using BDB because of its licensing -- GPL, and applications link directly to it, unlike, say, MySQL, and while we're currently only offering access as a web-service, we'd like to have the option open to licensing the recommendations engine in other ways down the line. So mostly we were trying it out to have another data-point to see how our implementation stacked up.
        ralph 18y ago
- ntoshev 18y ago
  This kind of storage should work very well with SSDs instead of disks. Is this the case?
  - wheels 18y 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 18y ago
Did you investigate any other network DBMSes? If so why did you find them inadequate? http://en.wikipedia.org/wiki/Network_model http://en.wikipedia.org/wiki/Network_model
- wheels 18y 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 18y 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 18y 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
deleted 18y ago
[deleted]
tptacek 18y 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?
- wheels 18y 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.
jonmc12 18y 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?
- wheels 18y 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 18y 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.
- nkurz 18y 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-June/050133.html http://lists.freebsd.org/pipermail/freebsd-questions/2004-Ju... Do you have know of any updated articles about it's performance tradeoffs?

159 points by wheels 18y 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 18y ago
This is great stuff - many thanks!
moe 18y 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 18y 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.
  - moe 18y ago
    Well, a business model that pays 50 cent a page view sounds nice for sure - I fear most of us don't share that luxury. 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.
    - aaronblohowiak 18y ago
      I don't believe you'd put all of your information in this kind of custom db. The author remarks that they are running with memory-mapped disk back-end, which means a single machine should be able to take you pretty darn far.
- gnaritas 18y 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.
  - moe 18y ago
    Actually it's well understood how to scale a RDBMS horizontally (sharding and partitioning). I simply asked whether there is a comparable strategy for this graph db. 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.
    - aaronblohowiak 18y ago
      So, assuming by "scaling" in the web space, you mean "be able to quickly respond to many reads and writes as my app generates" and not "handle large volumes of data", then you can do what LinkedIn does, which is to just copy the exact same graph to multiple machines, and rely on the fact that eventual consistency is good enough. You make things immediate for the user most concerned with immediate feedback (make them sticky to the graph their write updated) and for everybody else, a couple minutes of lag is no biggie. This is even more true in retail and other applications.
      - moe 18y ago
        Scaling in the web space usually means both; many reads/writes and large volumes of data. 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.
- wheels 18y 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 18y ago
  What are the odds that you'll become bigger than plentyoffish without having an influx of money that will let you rebuild?
ralph 18y ago
Thanks for taking the effort. Are tags implemented as just references from a tag "foo" node to the tagged item?
- wheels 18y 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.
  - ralph 18y ago
    Thanks for the detailed answer. I've a start-up idea that needs a big dag offline for the production of a smaller (in bytes, not nodes) one used online. My intention was to use Berkeley DB. It's good to see you say it's the fastest of the off the shelf options, but it only reaches 5% of your own code! Any thoughts on what BDB is doing "wrong"? Were you using hash or B-tree with BDB?
    - wheels 18y ago
      We used hashes with BDB. I didn't dig down deep to see what was going on since we weren't really considering using BDB because of its licensing -- GPL, and applications link directly to it, unlike, say, MySQL, and while we're currently only offering access as a web-service, we'd like to have the option open to licensing the recommendations engine in other ways down the line. So mostly we were trying it out to have another data-point to see how our implementation stacked up.
      - ralph 18y ago
ntoshev 18y ago
This kind of storage should work very well with SSDs instead of disks. Is this the case?
- wheels 18y 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 18y ago

Did you investigate any other network DBMSes? If so why did you find them inadequate? http://en.wikipedia.org/wiki/Network_model http://en.wikipedia.org/wiki/Network_model

wheels 18y 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 18y 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 18y 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

deleted 18y ago

[deleted]

tptacek 18y 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?

wheels 18y 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.

jonmc12 18y 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?

wheels 18y 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 18y 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.

nkurz 18y 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-June/050133.html http://lists.freebsd.org/pipermail/freebsd-questions/2004-Ju... Do you have know of any updated articles about it's performance tradeoffs?