18 ms·

HyperDex: A Searchable Distributed Key-Value Store

139 points by lpgauth 15y ago

pixelcort 15y ago
This reminds me of http://xanadu.com/zigzag/ http://xanadu.com/zigzag/ .
- rescrv 15y ago
  HyperDex is different. ZigZag focuses on data visualization. HyperDex provides you the same key-value interface of other systems, while also providing an efficient search primitive. Check out http://hyperdex.org/tutorial/ http://hyperdex.org/tutorial/ for examples of the Python API.
ericmoritz 15y ago
From the FAQ <http://hyperdex.org/faq/> http://hyperdex.org/faq/>: "So, the CAP Theorem says that you can only have one of C, A, and P. Which are you sacrificing? HyperDex is designed to operate within a single datacenter. The CAP Theorem holds only for asynchronous environments, and well-administered datacenters enable us to sidestep this tradeoff entirely." I'd like to see how they pull that off when a node goes down. I guess in "well-administered" data centers, nodes don't go down. Sounds like they're sacrificing "A" to me because they're doing synchronous replication.
- rescrv 15y ago
  HyperDex uses value-dependent chaining, which offers fault tolerance properties similar to those provided by chain replication (http://www.cs.cornell.edu/home/rvr/papers/osdi04.pdf http://www.cs.cornell.edu/home/rvr/papers/osdi04.pdf). A single node failure will be recovered from quickly without issue. Multiple concurrent failures are handled the same as the single failure case, so long as our failure assumptions are not violated (e.g., every node in the datacenter fails simultaneously).
  - tlb 15y ago
    That can work if the server process is killed so that the master is immediately notified. But what about other failure modes? For example, if the disk has soft errors and writes start taking several seconds to complete, the system can't decide in a small amount of time that the node is dead.
    - rescrv 15y ago
      In this case,the node should report its own failure. It must be able to do so, otherwise it will be deemed faulty by the entity it reports to.
- snewman 15y ago
  It's a bit of a middle ground. Yes, the replication is synchronous, which impacts availability. However, the master can remove a failed replica from the chain fairly quickly. In principle, with proper tuning, a node failure would merely cause a brief hiccup. This would feel more like a period of increased latency than a full-blown outage. So there really needn't be much sacrifice of availability. However, there's also a sacrifice of partition tolerance. If the master is unable to communicate with any replica, the system can't serve requests. Also, the master is implemented as a collection of Paxos nodes; if these nodes are partitioned from one another, the entire system would grind to a halt. Since this is intended for intra-datacenter use, one could argue that a full network partition might be unlikely. (Depending on what sort of data center you hang out in.) But in CAP terms, it's possible, of course. (I base all this on the value-dependent chaining paper cited below.)
  - rescrv 15y ago
    What you said was right on. I just wanted to add a few things. The coordinator is only involved for recovering from failures, so the cluster can still serve requests until server (non-coordinator) nodes start failing too. I would also add that if there is a intra-datacenter partition so severe as to violate HyperDex's failure assumptions, it will likely impact applications built on top of HyperDex as well. It would be necessary to survive such failures with an inter-datacenter system (which could be built on top of HyperDex).
    - ypcx 15y ago
      Well first Thank you for providing another data storage possibility, and a great one at that. I'd just like to ask - the benchmarks where HyperDex beats even Redis - these are strictly clustered benchmarks - is that true? Or is the way HyperDex stores data so efficient, that it beats Redis even on a single core / single thread? Thanks!
      - gizzlon 15y ago
        Without more context graphs like that is pretty useless.. For all we know they just invented those numbers. I'm not saying they did, but you get my point.. Those numbers seem way to low for running on the same machine, and if not shouldn't the network be the bottleneck and show similar results for both? I'm sure there's a reasonable explanation, just as I'm sure they picket benchmarks that makes themselves look good.
- tlb 15y ago
  When a node dies, the master reconfigures all the servers and clients with a new topology excluding the failed node. "Operations which are interrupted by reconfiguration exhibit at-most-once semantics." So while the system is reconfiguring after a node failure, updates can be lost. Time windows of "at most once semantics" mean the system has none of C, A, or P. Which doesn't mean it's not a good database for many purposes.
  - rescrv 15y ago
    The only scenario in which the operation has "at most once semantics" is when the node the client is directly communicating with fails. No other failure is visible to the clients. Furthermore, every failure scenario provides the following guarantees: * If the result of an operation is visible by one client, it is visible by all clients, always and immediately * Updates to the same key are always applied in the same order on all servers. The presence of "at most once semantics" do not harm our consistency guarantee. In the database world, this would be equivalent to a client sending the final "commit" message, and then losing internet connectivity. In such a scenario, the operation may or may not happen, but the client will not know one way or the other. Edit: Formatting of the list
    - tlb 15y ago
      The only scenario. In essentially every case of a node failing in an active database, clients will be communicating with it. When talking about durability, you have to assume things are failing in operation.
      - rescrv 15y ago
        HyperDex utilizes value-dependent chains for replication. Updates move forward in the chains, while acknowledgements flow in reverse. To issue a PUT or a GET, the client contacts the head of the chain responsible for the object it is modifying/accessing. If other nodes in the chain fail, the chain will transparently recover. If the point leader fails (the head of the chain), then the client does not know if the operation completed. This is analogous to a database library opening a socket and sending "BEGIN; INSERT INTO data ("x", "y", "z"); COMMIT" and then the client losing connection (or crashing entirely). There is always some point at which the server may complete, and then the client may immediately crash before receiving notification that the operation is complete. Even if this happens, however, HyperDex's GET and PUT operations are linearizable.
- reitblatt 15y ago
  "I'd like to see how they pull that off when a node goes down. I guess in "well-administered" data centers, nodes don't go down." They offer f-fault tolerance. They can have f nodes go down in a single "zone" and keep chugging as long as no more nodes in the same zone go down before the master reconfigures. Note that the f faults are per-zone, not per-system, so in fact many more than f nodes can be down in a single system without a problem. But, more importantly, you seem to be confusing partition tolerance and fault tolerance. CAP is about partition tolerance: offering "CA" in the presence of arbitrary partitions. They offer a specific form of fault tolerance: "CA" in the presence of any failure or partition that affects less than f nodes.
- lobster_johnson 15y ago
  > "So, the CAP Theorem says that you can only have one of C, A, and P. Which are you sacrificing? Which is wrong. You can only have two of the three at the same time: CA, CP or AP. If they get something as fundamental as this wrong, you have to wonder about the rest of the project.
  - mononcqc 15y ago
    Technically you can have at most two of the three of the same time. It's well possible for some stores to provide only one or no property at all!
    - lobster_johnson 15y ago
      Well, yes. But that's not what the FAQ says; it says you can have at most one. The distinction is significant.
  - reitblatt 15y ago
    Or it could just be a typo on the brand new webpage of a brand new project. Which it obviously is if you look at their explanation of CAP.
  - rescrv 15y ago
    Just a simple typo. I've fixed it. Thanks for pointing this out.
- xijhing 15y ago
  PACELC[1] helps distinguish just the kind of CAP sacrifice this makes. [1] http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-an...
simonw 15y ago
Is it open source? I browses around the site and FAQ and didn't spot a mention of the license.
- rescrv 15y ago
  Yes! We've released HyperDex under the 3-clause BSD license. You can get binaries and source from the downloads page (http://hyperdex.org/download/ http://hyperdex.org/download/).
  - DennisP 15y ago
    Any comment on the patent application that jandrewrogers pointed out?
- jandrewrogers 15y ago
  The code is open source. However, they applied for patents on the algorithm: http://www.wipo.int/patentscope/search/en/WO2011137189 http://www.wipo.int/patentscope/search/en/WO2011137189
  - ypcx 15y ago
    While waiting for the answer, what does this generally means if the patent is granted? Since the code is open-sourced under BSD, can the algorithm be used in other open-source BSD-licensed products, and can corporations then use these products to store data, without needing to pay the royalties on the patent?
    - bryanlarsen 15y ago
      The BSD license does not contain a patent grant, so it's technically possible that you'll have to pay to use this software in the future even though it's under the BSD license. I'd really like to see a switch to the Apache license, which does contain a patent grant.
      - 15y ago
stevelosh 15y ago
For those that want to take a quick look at the source code without physically cloning it, there's a GitHub link buried somewhere in the site (I forget where I found it): https://github.com/rescrv/HyperDex https://github.com/rescrv/HyperDex Their Python client seems to be using Cython for extra speed: https://github.com/rescrv/HyperDex/blob/master/hyperclient/python/hyperclient.pyx https://github.com/rescrv/HyperDex/blob/master/hyperclient/p...
jbverschoor 15y ago
Interesting.. keep it coming. We need a unified nosql language.. Basically what SQL is.
- bickfordb 15y ago
  What's wrong with SQL?
  - statictype 15y ago
    Nothing really. When people talk about the nosql movement, they're mostly referring to the 'non-relational database' movement. The fact that they all implement SQL as their dsl is after the fact.
  - wickedchicken 15y ago
    * COBOL-inspired syntax that is neither human or machine parseable (easily). * Strange nested query rules * Language encourages Cartesian products for virtually every non-trivial calculation. This makes join order crucial for reasoning about performance. * Humans don't have the brain capacity to reason about these joins, forcing the logic onto the query planner. * Humans don't have the brain capacity to reason about the query planner reasoning about the joins. * End result: bizarro-english syntax that's supremely hacked-up to twerk the query planner to do your bidding.
    - Craiggybear 15y ago
      What? SQL is virtually plain English and is efficient across a range of database architectures for moderate-to-complex join situations. Its just an implementation of Boolean Algebra with a thin abstraction layer that uses words like SELECT, JOIN, FROM, WHERE, etc. If you have performance issues, its invariably because the structure of your data is less than optimal or you have many linked external tables. Or -- you are really bad at efficient query design. Even highly experienced SQL-ers always look at old queries and realise that they could be three times faster and half as big, and if there is a performance issue then that's the first thing they'll review. Humans have been 'understanding' SQL very well for nearly forty years -- without modern refinements like graphical query designers, either. Not all data is a suitable candidate for an RDBMS solution, I am the first to agree, but there's not actually much wrong with SQL when what you need is a relational table store. There are a few bad implementations of it, though, it is true, and a lot of people who can't seem to grasp SQL for what it is. Edit: I am myself a huge fan of NoSQL solutions and always seek to rationally justify a non-relational datastore solution where practical or possible. NoSQL isn't a replacement for SQL (with all its imperfections) for the kind of slicing and dicing where it is needed.
jsavimbi 15y ago
Has it been proven in a pr0n environment? If not, I'll wait and see.
PanMan 15y ago
Since they compare it with redis, I wonder if this can handle data bigger than memory. The other properties seem nice :)
- rescrv 15y ago
  We compared it to Redis as it is one of the many key-value/document-database systems that provide the high throughput and low latency properties that make it comparable to HyperDex. We are expanding the systems we benchmark against, aiming to compare against as many systems as possible. HyperDex is designed for bigger-than-memory data.
  - antirez 15y ago
    The comparison with Redis is a bit strange at a first glance, what I mean is, if in Redis I replace the actual fetching of data with "return 'foo'" at every query it still returns 150k/requests per second for every operation. The same will do memcached per single core. So either in your code there is some good trick to improve speed in the networking layer, or you are comparing multiple cores/nodes to single core/node. About benchmark "E", this is a primitive that Redis lacks, so it is in my opinion a bit misleading. Another question is, in the benchmarks with Redis, does the data set fits inside Ram also in HyperDex DB (or OS cache)? In such a case you are comparing two in memory databases in practical terms, but at the same time you say that HyperDex is suitable for datasets bigger than RAM (in a portion of text near the Redis benchmark), but the numbers that the users will experiment in actual production setups will be different if the data set does not fit in RAM. Finally, in the benchmark it is not clear that Redis can perform a lot of work in a single operation, for example a variadic LPUSH can insert 10 elements inside a list in the same time an LPUSH does this with 1 elmenet, more or less. If you multiply this for N cores in a stand alone Linux box you get 1 billion operations per second or alike, but I would be not comfortable with writing this in the Redis home page. I mean, if you don't specify very well the methodology this unfortunately is just marketing material without real interest for the field.
    - rescrv 15y ago
jandrewrogers 15y ago
This is a pretty nice implementation of an old design concept that has merit for modern distributed problems. It is worth studying as a model for distributed systems. I am aware of a couple commercial distributed systems that use it (not this implementation but the underlying algorithm). Several organizations seem to have reinvented it over the last five years. Organizing data in this way was studied in the 1980s but was poorly suited to the computing systems of the time. Relatively little was written about it because it was viewed as a dead end and modern literature has all but forgotten about it. Most of the research was done by companies rather than academics. Designs like this have fallen into the blackhole of "if it is not on the Internet then it doesn't exist". Back when I was studying these models I found more crusty old patents related to these types of models than relevant papers on the Internet. It will be valuable to have some modern literature pertaining to these designs.
DEinspanjer 15y ago
I think maybe only certain versions of Ubuntu are supported? It won't install because I don't have a repo that provides libgoogle-glog0
- rescrv 15y ago
  The packages are built for Ubuntu 11.10. What version of Ubuntu are you running?
  - DEinspanjer 15y ago
    Thanks for letting me know the target version. I am running 10.4.4 LTS
jfager 15y ago
I'm reading through the paper, and I'm curious if I understand the implications of key subspacing and value dependent chaining correctly - do all reads and writes for a given key get forced to a single node? I understand how the replication that's described allows for failover when the point-leader fails, but does it also allow for scaling writes and key lookups?
- rescrv 15y ago
  Reads and writes for a given key always go to a single node. As you add more machines with the same workload, you are handling fewer keys per machine. The flip side is, if the number of keys per machine stays constant, more machines directly translates into the ability to handle more keys. HyperDex scales linearly as you can see in our scalability graph.
  - jfager 15y ago
    I think you're missing the point of the question. I'm not asking how you scale in general, I'm asking whether your replication scheme is only for failover or if it contributes to your scaling story - i.e., if a given key goes hot, does everything have to run through the point leader, or can each replica take writes/serve requests? It sounds like the former, which is fine, just wanted to clarify.
    - rescrv 15y ago
      It's the former. I'd rather not sacrifice our strong consistency by using replicas to serve GET requests.
jdf 15y ago
It looks like they trade the ability to scan ranges of keys for the ability to get single objects via multiple attributes. The value-dependent stuff is also a neat way of solving the consistency issues with multiple node updates. Interesting stuff. If you were to swap this with your Cassandra cluster, you'd be losing multi-datacenter replication. Although partitions within a data center are pretty rare, you'd also lose some availability there as well. However, Cassandra is usually hash-partitioned so it needs to do broadcast for a scan (AFAICT, it even needs to do a broadcast for a lookup on a single secondary attribute), so you'd probably gain quite a bit of performance with HyperDex. I can't tell if it's possible to dynamically change the set of secondary attributes being indexed without rebuilding the entire data set. Or how value-chaining works with missing attributes. Also, apparently consistency has some... gaps... when you search via a secondary attribute: "The searches are not strongly consistent with concurrently modified objects because there is a small window of time during which a client may observe inconsistency."
NOD507 15y ago
How does it compare to elasticsearch?
- k-a-r 15y ago
  Elasticsearch is a Fulltext search solution not a K/V Database.
  - erickt 15y ago
    Technically yes, but you can use elasticsearch as a distributed key-value store. I use it in production and it works amazingly well for me. Yes, searches may return stale data (one second old by default) but that is not much of a problem in my app.
    - gregholmberg 15y ago
      That sounds both interesting and non-intuitive. Can you go into more detail about how you have been using ElasticSearch as a k/v store? EDIT: Color me surprised. I didn't see it mentioned at all in the ElasticSearch docs or in their Github repo, but apparently this is a fairly popular thing to do. "Elastic search as a database?" http://stackoverflow.com/questions/6636508/elastic-search-as-a-database http://stackoverflow.com/questions/6636508/elastic-search-as... "ElasticSearch, datastore for user and social data?" http://stackoverflow.com/questions/8190288/elasticsearch-datastore-for-user-and-social-data http://stackoverflow.com/questions/8190288/elasticsearch-dat... "Elasticsearch and NoSql database" http://stackoverflow.com/questions/8026880/elasticsearch-and-nosql-database http://stackoverflow.com/questions/8026880/elasticsearch-and...
xxqs 15y ago
Did you compare the performance with (local) BerkeleyDB? Also, is there a locking mechanism? I'm the author of Torrus (torrus.org), and BerkeleyDB stability and non-network nature are quite painful. But I'm relying on its speed, concurrent locking, and some ways to acquire an exclusive lock on a table. It would be interesting to offer an alternative backend for torrus.
- rescrv 15y ago
  I'm not sure exactly what you're looking for, but Berkeley DB is embedded in your application on a single host, while HyperDex is distributed. It sounds like that's exactly what you want. What do you use exclusive locks for?
  - xxqs 15y ago
    I use exclusive locks where multiple processes concur for data access, and these locks guarantee the data consistency. For example, the GUI engine may eventually start cleaning its old cache, and the exclusive lock prevents other GUI processes (which are mod_perl or fcgi processes) to do the same. another example is when the database is big enough, and when multiple collector processes start at the same time, I use the exclusive lock to let them initialize and slurp the data sequentially: this prevents from excessive disk seeks. but as you mentioned in another thread, your solution is locked to a single architecture, and I cannot afford that.
  - xxqs 15y ago
    and yes you're certainly right that BDB is embedded into the application process. Then any slight memory corruption may destroy the database and lockup the whole service. We've seen that, especially with graphics libraries. But BDB offers tremendous speed, so it won't be easy to decouple the DB engine from the application process.
xxqs 15y ago
the FAQ mentions that you target x86_64 architecture. Does the server work on i386? also, I hope it's doing proper memory alignment and endiannes independence? (because Mongo sucks on that)
- rescrv 15y ago
  We use many lock-free datastructures which rely heavily upon the x86_64 architecture. Further, the expanded virtual address space enables us to mmap everything. All network traffic is packed, and in network byte order.
  - otterley 15y ago
    > the expanded virtual address space enables us to mmap everything This sounds like a disaster waiting to happen when a node's working set is larger than RAM. Have you considered the impact on performance due to excessive I/O resulting from this kind of overcommit? Redis performance, for example, suffers tremendously when its database size exceeds the available RAM, which is why the authors advise implementors to cap its database size. The only real difference I can see here is that Redis allocates its storage anonymously, while Hyperdex uses file-backed pages; in either case, performance under memory pressure will largely be governed by how the VM chooses to move pages in and out of its backing store -- behavior the application has no control over. Optimizing the performance of working sets larger than RAM is hard. Redis had a (thankfully) aborted attempt to do so (the VM is gone in the most recent stable release); and the InnoDB buffer pool in MySQL has been refined for many years and is subject to quite a bit of tuning for specific workloads. (See also http://blog.kennejima.com/post/1226487020/thoughts-on-redis http://blog.kennejima.com/post/1226487020/thoughts-on-redis for some thoughtful discussion on the subject.) You claim on the one hand that Hyperdex was designed to work on data sets larger than RAM, but on the other hand you admit that all the benchmarks were performed with a working set smaller than RAM. I'd like to see comparative benchmarks where the working set is larger than RAM to be convinced.
    - lobster_johnson 15y ago
      > This sounds like a disaster waiting to happen Well, define "disaster". A memory-mapped dataset will cause pathological performance only when there is thrashing: If you are accessing a small percentage of the entire dataset, then unused data will be paged out and remain paged out. If the bulk of data being accessed exceeds the amount of available physical RAM, then you will get I/O trashing. Memory-mapping is a good alternative to static allocation or a home-grown paging system because it lets the kernel handle the dynamics of allocation, letting your application transparently and gracefully handle RAM tension situation by relinquishing memory space to other apps. Kernels (including Linux and Windows) and CPUs are extremely efficient at paging I/O, much more efficient than a hand-written paging system because there's no need for the application's code to check whether a page is in physical memory — that's handled by the CPU itself. Of course, any I/O incurred by a too-large dataset will drastically reduce performance compared to in-memory speed. But paging in itself does not necessarily lead to "disaster".
nirvana 15y ago
If you're building a distributed KV stores, you should benchmark against other distributed KV stores. Mongo and Cassandra aren't really. But Riak is. Plus, since its "distributed" here's the benchmark I'd like to see: 1. Set up a cluster of 8 nodes. Set data replication to 3. 2. Load 3TB of data into the cluster, across 1M documents (or some data set of that order) 3. Run your tests. Optimize each of the DBs for the best way to access them (Eg: link walking vs. map reduce on Riak if that's faster, or secondary indexes if that's faster, or Riak Search if that's faster-- there are many ways to search Riak.) 4. Throw out the results of #3. 5. Pull the plug on 2 nodes. EG: Shut down completely, no longer on the net work at all. Poof, gone. Pick the two nodes by rolling the dice. If you have SPFs, and a bad role of the dice would have brought the whole cluster down, remove the word "distributed" from your marketing. 6. Let the cluster sit for 30 minutes. 7. Run your benchmarks. The benchmarks developed in #7 are the ones I want to see. I have no clue how HyperDex would perform in this situation. It could kick Riak's butt (but then, small cluster performance is just one of the criteria that is important to me). I just wish people did benchmarks like this (though I know its a PITA to do it this way.)
- foobarbazetc 15y ago
  Why would a competitor build this Riak benchmark? How are they supposed to know which Riak configuration performs best? That's the point of YCSB. Each vendor can submit the optimal configuration for their system, and they all run the same benchmark. At the end of the day, each vendor is going to publish benchmarks that show their system performing better than all others. It's your job, not theirs, to verify those benchmarks for your particular work load. Edit: Also, while Mongo wouldn't classify as a distributed store, Cassandra definitely would. In fact, it's more "distributed" than Riak, since you have to pay Basho for multiple DC support (unless that's in the open source version?), whereas Cassandra is completely free.
  - 3pt14159 15y ago
    If things haven't changed in the past year you are right about not being able to do replicated multiple DC support.
  - 15y ago
jcapote 15y ago
Is this better than hadoop?
ypcx 15y ago
I'm looking for a good paper or a book detailing patterns or strategies of storing complex data structures and relations, or designing complex schemas on top of key/value stores, possibly with real-world use cases / success stories. A bonus would be the same on top of key/value/range(search) stores, just like HyperDex is. Any suggestions HN? Technically, it should be even possible to implement SQL on top of a store like HyperDex (there's the Tenzing paper from Google). But I'm not looking specifically at SQL, but at more general scope.

139 points by lpgauth 15y ago

pixelcort 15y ago

This reminds me of http://xanadu.com/zigzag/ http://xanadu.com/zigzag/ .

rescrv 15y ago
HyperDex is different. ZigZag focuses on data visualization. HyperDex provides you the same key-value interface of other systems, while also providing an efficient search primitive. Check out http://hyperdex.org/tutorial/ http://hyperdex.org/tutorial/ for examples of the Python API.

ericmoritz 15y ago

From the FAQ <http://hyperdex.org/faq/> http://hyperdex.org/faq/>: "So, the CAP Theorem says that you can only have one of C, A, and P. Which are you sacrificing? HyperDex is designed to operate within a single datacenter. The CAP Theorem holds only for asynchronous environments, and well-administered datacenters enable us to sidestep this tradeoff entirely." I'd like to see how they pull that off when a node goes down. I guess in "well-administered" data centers, nodes don't go down. Sounds like they're sacrificing "A" to me because they're doing synchronous replication.

rescrv 15y ago
HyperDex uses value-dependent chaining, which offers fault tolerance properties similar to those provided by chain replication (http://www.cs.cornell.edu/home/rvr/papers/osdi04.pdf http://www.cs.cornell.edu/home/rvr/papers/osdi04.pdf). A single node failure will be recovered from quickly without issue. Multiple concurrent failures are handled the same as the single failure case, so long as our failure assumptions are not violated (e.g., every node in the datacenter fails simultaneously).
- tlb 15y ago
  That can work if the server process is killed so that the master is immediately notified. But what about other failure modes? For example, if the disk has soft errors and writes start taking several seconds to complete, the system can't decide in a small amount of time that the node is dead.
  - rescrv 15y ago
    In this case,the node should report its own failure. It must be able to do so, otherwise it will be deemed faulty by the entity it reports to.
snewman 15y ago
It's a bit of a middle ground. Yes, the replication is synchronous, which impacts availability. However, the master can remove a failed replica from the chain fairly quickly. In principle, with proper tuning, a node failure would merely cause a brief hiccup. This would feel more like a period of increased latency than a full-blown outage. So there really needn't be much sacrifice of availability. However, there's also a sacrifice of partition tolerance. If the master is unable to communicate with any replica, the system can't serve requests. Also, the master is implemented as a collection of Paxos nodes; if these nodes are partitioned from one another, the entire system would grind to a halt. Since this is intended for intra-datacenter use, one could argue that a full network partition might be unlikely. (Depending on what sort of data center you hang out in.) But in CAP terms, it's possible, of course. (I base all this on the value-dependent chaining paper cited below.)
- rescrv 15y ago
  What you said was right on. I just wanted to add a few things. The coordinator is only involved for recovering from failures, so the cluster can still serve requests until server (non-coordinator) nodes start failing too. I would also add that if there is a intra-datacenter partition so severe as to violate HyperDex's failure assumptions, it will likely impact applications built on top of HyperDex as well. It would be necessary to survive such failures with an inter-datacenter system (which could be built on top of HyperDex).
  - ypcx 15y ago
    Well first Thank you for providing another data storage possibility, and a great one at that. I'd just like to ask - the benchmarks where HyperDex beats even Redis - these are strictly clustered benchmarks - is that true? Or is the way HyperDex stores data so efficient, that it beats Redis even on a single core / single thread? Thanks!
    - gizzlon 15y ago
      Without more context graphs like that is pretty useless.. For all we know they just invented those numbers. I'm not saying they did, but you get my point.. Those numbers seem way to low for running on the same machine, and if not shouldn't the network be the bottleneck and show similar results for both? I'm sure there's a reasonable explanation, just as I'm sure they picket benchmarks that makes themselves look good.
tlb 15y ago
When a node dies, the master reconfigures all the servers and clients with a new topology excluding the failed node. "Operations which are interrupted by reconfiguration exhibit at-most-once semantics." So while the system is reconfiguring after a node failure, updates can be lost. Time windows of "at most once semantics" mean the system has none of C, A, or P. Which doesn't mean it's not a good database for many purposes.
- rescrv 15y ago
  The only scenario in which the operation has "at most once semantics" is when the node the client is directly communicating with fails. No other failure is visible to the clients. Furthermore, every failure scenario provides the following guarantees: * If the result of an operation is visible by one client, it is visible by all clients, always and immediately * Updates to the same key are always applied in the same order on all servers. The presence of "at most once semantics" do not harm our consistency guarantee. In the database world, this would be equivalent to a client sending the final "commit" message, and then losing internet connectivity. In such a scenario, the operation may or may not happen, but the client will not know one way or the other. Edit: Formatting of the list
  - tlb 15y ago
    The only scenario. In essentially every case of a node failing in an active database, clients will be communicating with it. When talking about durability, you have to assume things are failing in operation.
    - rescrv 15y ago
      HyperDex utilizes value-dependent chains for replication. Updates move forward in the chains, while acknowledgements flow in reverse. To issue a PUT or a GET, the client contacts the head of the chain responsible for the object it is modifying/accessing. If other nodes in the chain fail, the chain will transparently recover. If the point leader fails (the head of the chain), then the client does not know if the operation completed. This is analogous to a database library opening a socket and sending "BEGIN; INSERT INTO data ("x", "y", "z"); COMMIT" and then the client losing connection (or crashing entirely). There is always some point at which the server may complete, and then the client may immediately crash before receiving notification that the operation is complete. Even if this happens, however, HyperDex's GET and PUT operations are linearizable.
reitblatt 15y ago
"I'd like to see how they pull that off when a node goes down. I guess in "well-administered" data centers, nodes don't go down." They offer f-fault tolerance. They can have f nodes go down in a single "zone" and keep chugging as long as no more nodes in the same zone go down before the master reconfigures. Note that the f faults are per-zone, not per-system, so in fact many more than f nodes can be down in a single system without a problem. But, more importantly, you seem to be confusing partition tolerance and fault tolerance. CAP is about partition tolerance: offering "CA" in the presence of arbitrary partitions. They offer a specific form of fault tolerance: "CA" in the presence of any failure or partition that affects less than f nodes.
lobster_johnson 15y ago
> "So, the CAP Theorem says that you can only have one of C, A, and P. Which are you sacrificing? Which is wrong. You can only have two of the three at the same time: CA, CP or AP. If they get something as fundamental as this wrong, you have to wonder about the rest of the project.
- mononcqc 15y ago
  Technically you can have at most two of the three of the same time. It's well possible for some stores to provide only one or no property at all!
  - lobster_johnson 15y ago
    Well, yes. But that's not what the FAQ says; it says you can have at most one. The distinction is significant.
- reitblatt 15y ago
  Or it could just be a typo on the brand new webpage of a brand new project. Which it obviously is if you look at their explanation of CAP.
- rescrv 15y ago
  Just a simple typo. I've fixed it. Thanks for pointing this out.
xijhing 15y ago
PACELC[1] helps distinguish just the kind of CAP sacrifice this makes. [1] http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-an...

simonw 15y ago

Is it open source? I browses around the site and FAQ and didn't spot a mention of the license.

rescrv 15y ago
Yes! We've released HyperDex under the 3-clause BSD license. You can get binaries and source from the downloads page (http://hyperdex.org/download/ http://hyperdex.org/download/).
- DennisP 15y ago
  Any comment on the patent application that jandrewrogers pointed out?
jandrewrogers 15y ago
The code is open source. However, they applied for patents on the algorithm: http://www.wipo.int/patentscope/search/en/WO2011137189 http://www.wipo.int/patentscope/search/en/WO2011137189
- ypcx 15y ago
  While waiting for the answer, what does this generally means if the patent is granted? Since the code is open-sourced under BSD, can the algorithm be used in other open-source BSD-licensed products, and can corporations then use these products to store data, without needing to pay the royalties on the patent?
  - bryanlarsen 15y ago
    The BSD license does not contain a patent grant, so it's technically possible that you'll have to pay to use this software in the future even though it's under the BSD license. I'd really like to see a switch to the Apache license, which does contain a patent grant.
    - 15y ago

stevelosh 15y ago

For those that want to take a quick look at the source code without physically cloning it, there's a GitHub link buried somewhere in the site (I forget where I found it): https://github.com/rescrv/HyperDex https://github.com/rescrv/HyperDex Their Python client seems to be using Cython for extra speed: https://github.com/rescrv/HyperDex/blob/master/hyperclient/python/hyperclient.pyx https://github.com/rescrv/HyperDex/blob/master/hyperclient/p...

jbverschoor 15y ago

Interesting.. keep it coming. We need a unified nosql language.. Basically what SQL is.

bickfordb 15y ago
What's wrong with SQL?
- statictype 15y ago
  Nothing really. When people talk about the nosql movement, they're mostly referring to the 'non-relational database' movement. The fact that they all implement SQL as their dsl is after the fact.
- wickedchicken 15y ago
  * COBOL-inspired syntax that is neither human or machine parseable (easily). * Strange nested query rules * Language encourages Cartesian products for virtually every non-trivial calculation. This makes join order crucial for reasoning about performance. * Humans don't have the brain capacity to reason about these joins, forcing the logic onto the query planner. * Humans don't have the brain capacity to reason about the query planner reasoning about the joins. * End result: bizarro-english syntax that's supremely hacked-up to twerk the query planner to do your bidding.
  - Craiggybear 15y ago
    What? SQL is virtually plain English and is efficient across a range of database architectures for moderate-to-complex join situations. Its just an implementation of Boolean Algebra with a thin abstraction layer that uses words like SELECT, JOIN, FROM, WHERE, etc. If you have performance issues, its invariably because the structure of your data is less than optimal or you have many linked external tables. Or -- you are really bad at efficient query design. Even highly experienced SQL-ers always look at old queries and realise that they could be three times faster and half as big, and if there is a performance issue then that's the first thing they'll review. Humans have been 'understanding' SQL very well for nearly forty years -- without modern refinements like graphical query designers, either. Not all data is a suitable candidate for an RDBMS solution, I am the first to agree, but there's not actually much wrong with SQL when what you need is a relational table store. There are a few bad implementations of it, though, it is true, and a lot of people who can't seem to grasp SQL for what it is. Edit: I am myself a huge fan of NoSQL solutions and always seek to rationally justify a non-relational datastore solution where practical or possible. NoSQL isn't a replacement for SQL (with all its imperfections) for the kind of slicing and dicing where it is needed.

jsavimbi 15y ago

Has it been proven in a pr0n environment? If not, I'll wait and see.

PanMan 15y ago

Since they compare it with redis, I wonder if this can handle data bigger than memory. The other properties seem nice :)

rescrv 15y ago
We compared it to Redis as it is one of the many key-value/document-database systems that provide the high throughput and low latency properties that make it comparable to HyperDex. We are expanding the systems we benchmark against, aiming to compare against as many systems as possible. HyperDex is designed for bigger-than-memory data.
- antirez 15y ago
  The comparison with Redis is a bit strange at a first glance, what I mean is, if in Redis I replace the actual fetching of data with "return 'foo'" at every query it still returns 150k/requests per second for every operation. The same will do memcached per single core. So either in your code there is some good trick to improve speed in the networking layer, or you are comparing multiple cores/nodes to single core/node. About benchmark "E", this is a primitive that Redis lacks, so it is in my opinion a bit misleading. Another question is, in the benchmarks with Redis, does the data set fits inside Ram also in HyperDex DB (or OS cache)? In such a case you are comparing two in memory databases in practical terms, but at the same time you say that HyperDex is suitable for datasets bigger than RAM (in a portion of text near the Redis benchmark), but the numbers that the users will experiment in actual production setups will be different if the data set does not fit in RAM. Finally, in the benchmark it is not clear that Redis can perform a lot of work in a single operation, for example a variadic LPUSH can insert 10 elements inside a list in the same time an LPUSH does this with 1 elmenet, more or less. If you multiply this for N cores in a stand alone Linux box you get 1 billion operations per second or alike, but I would be not comfortable with writing this in the Redis home page. I mean, if you don't specify very well the methodology this unfortunately is just marketing material without real interest for the field.
  - rescrv 15y ago

jandrewrogers 15y ago

This is a pretty nice implementation of an old design concept that has merit for modern distributed problems. It is worth studying as a model for distributed systems. I am aware of a couple commercial distributed systems that use it (not this implementation but the underlying algorithm). Several organizations seem to have reinvented it over the last five years. Organizing data in this way was studied in the 1980s but was poorly suited to the computing systems of the time. Relatively little was written about it because it was viewed as a dead end and modern literature has all but forgotten about it. Most of the research was done by companies rather than academics. Designs like this have fallen into the blackhole of "if it is not on the Internet then it doesn't exist". Back when I was studying these models I found more crusty old patents related to these types of models than relevant papers on the Internet. It will be valuable to have some modern literature pertaining to these designs.

DEinspanjer 15y ago

I think maybe only certain versions of Ubuntu are supported? It won't install because I don't have a repo that provides libgoogle-glog0

rescrv 15y ago
The packages are built for Ubuntu 11.10. What version of Ubuntu are you running?
- DEinspanjer 15y ago
  Thanks for letting me know the target version. I am running 10.4.4 LTS

jfager 15y ago

I'm reading through the paper, and I'm curious if I understand the implications of key subspacing and value dependent chaining correctly - do all reads and writes for a given key get forced to a single node? I understand how the replication that's described allows for failover when the point-leader fails, but does it also allow for scaling writes and key lookups?

rescrv 15y ago
Reads and writes for a given key always go to a single node. As you add more machines with the same workload, you are handling fewer keys per machine. The flip side is, if the number of keys per machine stays constant, more machines directly translates into the ability to handle more keys. HyperDex scales linearly as you can see in our scalability graph.
- jfager 15y ago
  I think you're missing the point of the question. I'm not asking how you scale in general, I'm asking whether your replication scheme is only for failover or if it contributes to your scaling story - i.e., if a given key goes hot, does everything have to run through the point leader, or can each replica take writes/serve requests? It sounds like the former, which is fine, just wanted to clarify.
  - rescrv 15y ago
    It's the former. I'd rather not sacrifice our strong consistency by using replicas to serve GET requests.

jdf 15y ago

It looks like they trade the ability to scan ranges of keys for the ability to get single objects via multiple attributes. The value-dependent stuff is also a neat way of solving the consistency issues with multiple node updates. Interesting stuff. If you were to swap this with your Cassandra cluster, you'd be losing multi-datacenter replication. Although partitions within a data center are pretty rare, you'd also lose some availability there as well. However, Cassandra is usually hash-partitioned so it needs to do broadcast for a scan (AFAICT, it even needs to do a broadcast for a lookup on a single secondary attribute), so you'd probably gain quite a bit of performance with HyperDex. I can't tell if it's possible to dynamically change the set of secondary attributes being indexed without rebuilding the entire data set. Or how value-chaining works with missing attributes. Also, apparently consistency has some... gaps... when you search via a secondary attribute: "The searches are not strongly consistent with concurrently modified objects because there is a small window of time during which a client may observe inconsistency."

NOD507 15y ago

How does it compare to elasticsearch?

k-a-r 15y ago
Elasticsearch is a Fulltext search solution not a K/V Database.
- erickt 15y ago
  Technically yes, but you can use elasticsearch as a distributed key-value store. I use it in production and it works amazingly well for me. Yes, searches may return stale data (one second old by default) but that is not much of a problem in my app.
  - gregholmberg 15y ago
    That sounds both interesting and non-intuitive. Can you go into more detail about how you have been using ElasticSearch as a k/v store? EDIT: Color me surprised. I didn't see it mentioned at all in the ElasticSearch docs or in their Github repo, but apparently this is a fairly popular thing to do. "Elastic search as a database?" http://stackoverflow.com/questions/6636508/elastic-search-as-a-database http://stackoverflow.com/questions/6636508/elastic-search-as... "ElasticSearch, datastore for user and social data?" http://stackoverflow.com/questions/8190288/elasticsearch-datastore-for-user-and-social-data http://stackoverflow.com/questions/8190288/elasticsearch-dat... "Elasticsearch and NoSql database" http://stackoverflow.com/questions/8026880/elasticsearch-and-nosql-database http://stackoverflow.com/questions/8026880/elasticsearch-and...

xxqs 15y ago

Did you compare the performance with (local) BerkeleyDB? Also, is there a locking mechanism? I'm the author of Torrus (torrus.org), and BerkeleyDB stability and non-network nature are quite painful. But I'm relying on its speed, concurrent locking, and some ways to acquire an exclusive lock on a table. It would be interesting to offer an alternative backend for torrus.

rescrv 15y ago
I'm not sure exactly what you're looking for, but Berkeley DB is embedded in your application on a single host, while HyperDex is distributed. It sounds like that's exactly what you want. What do you use exclusive locks for?
- xxqs 15y ago
  I use exclusive locks where multiple processes concur for data access, and these locks guarantee the data consistency. For example, the GUI engine may eventually start cleaning its old cache, and the exclusive lock prevents other GUI processes (which are mod_perl or fcgi processes) to do the same. another example is when the database is big enough, and when multiple collector processes start at the same time, I use the exclusive lock to let them initialize and slurp the data sequentially: this prevents from excessive disk seeks. but as you mentioned in another thread, your solution is locked to a single architecture, and I cannot afford that.
- xxqs 15y ago
  and yes you're certainly right that BDB is embedded into the application process. Then any slight memory corruption may destroy the database and lockup the whole service. We've seen that, especially with graphics libraries. But BDB offers tremendous speed, so it won't be easy to decouple the DB engine from the application process.

xxqs 15y ago

the FAQ mentions that you target x86_64 architecture. Does the server work on i386? also, I hope it's doing proper memory alignment and endiannes independence? (because Mongo sucks on that)

rescrv 15y ago
We use many lock-free datastructures which rely heavily upon the x86_64 architecture. Further, the expanded virtual address space enables us to mmap everything. All network traffic is packed, and in network byte order.
- otterley 15y ago
  > the expanded virtual address space enables us to mmap everything This sounds like a disaster waiting to happen when a node's working set is larger than RAM. Have you considered the impact on performance due to excessive I/O resulting from this kind of overcommit? Redis performance, for example, suffers tremendously when its database size exceeds the available RAM, which is why the authors advise implementors to cap its database size. The only real difference I can see here is that Redis allocates its storage anonymously, while Hyperdex uses file-backed pages; in either case, performance under memory pressure will largely be governed by how the VM chooses to move pages in and out of its backing store -- behavior the application has no control over. Optimizing the performance of working sets larger than RAM is hard. Redis had a (thankfully) aborted attempt to do so (the VM is gone in the most recent stable release); and the InnoDB buffer pool in MySQL has been refined for many years and is subject to quite a bit of tuning for specific workloads. (See also http://blog.kennejima.com/post/1226487020/thoughts-on-redis http://blog.kennejima.com/post/1226487020/thoughts-on-redis for some thoughtful discussion on the subject.) You claim on the one hand that Hyperdex was designed to work on data sets larger than RAM, but on the other hand you admit that all the benchmarks were performed with a working set smaller than RAM. I'd like to see comparative benchmarks where the working set is larger than RAM to be convinced.
  - lobster_johnson 15y ago
    > This sounds like a disaster waiting to happen Well, define "disaster". A memory-mapped dataset will cause pathological performance only when there is thrashing: If you are accessing a small percentage of the entire dataset, then unused data will be paged out and remain paged out. If the bulk of data being accessed exceeds the amount of available physical RAM, then you will get I/O trashing. Memory-mapping is a good alternative to static allocation or a home-grown paging system because it lets the kernel handle the dynamics of allocation, letting your application transparently and gracefully handle RAM tension situation by relinquishing memory space to other apps. Kernels (including Linux and Windows) and CPUs are extremely efficient at paging I/O, much more efficient than a hand-written paging system because there's no need for the application's code to check whether a page is in physical memory — that's handled by the CPU itself. Of course, any I/O incurred by a too-large dataset will drastically reduce performance compared to in-memory speed. But paging in itself does not necessarily lead to "disaster".

nirvana 15y ago

If you're building a distributed KV stores, you should benchmark against other distributed KV stores. Mongo and Cassandra aren't really. But Riak is. Plus, since its "distributed" here's the benchmark I'd like to see: 1. Set up a cluster of 8 nodes. Set data replication to 3. 2. Load 3TB of data into the cluster, across 1M documents (or some data set of that order) 3. Run your tests. Optimize each of the DBs for the best way to access them (Eg: link walking vs. map reduce on Riak if that's faster, or secondary indexes if that's faster, or Riak Search if that's faster-- there are many ways to search Riak.) 4. Throw out the results of #3. 5. Pull the plug on 2 nodes. EG: Shut down completely, no longer on the net work at all. Poof, gone. Pick the two nodes by rolling the dice. If you have SPFs, and a bad role of the dice would have brought the whole cluster down, remove the word "distributed" from your marketing. 6. Let the cluster sit for 30 minutes. 7. Run your benchmarks. The benchmarks developed in #7 are the ones I want to see. I have no clue how HyperDex would perform in this situation. It could kick Riak's butt (but then, small cluster performance is just one of the criteria that is important to me). I just wish people did benchmarks like this (though I know its a PITA to do it this way.)

foobarbazetc 15y ago
Why would a competitor build this Riak benchmark? How are they supposed to know which Riak configuration performs best? That's the point of YCSB. Each vendor can submit the optimal configuration for their system, and they all run the same benchmark. At the end of the day, each vendor is going to publish benchmarks that show their system performing better than all others. It's your job, not theirs, to verify those benchmarks for your particular work load. Edit: Also, while Mongo wouldn't classify as a distributed store, Cassandra definitely would. In fact, it's more "distributed" than Riak, since you have to pay Basho for multiple DC support (unless that's in the open source version?), whereas Cassandra is completely free.
- 3pt14159 15y ago
  If things haven't changed in the past year you are right about not being able to do replicated multiple DC support.
- 15y ago

jcapote 15y ago

Is this better than hadoop?

ypcx 15y ago

I'm looking for a good paper or a book detailing patterns or strategies of storing complex data structures and relations, or designing complex schemas on top of key/value stores, possibly with real-world use cases / success stories. A bonus would be the same on top of key/value/range(search) stores, just like HyperDex is. Any suggestions HN? Technically, it should be even possible to implement SQL on top of a store like HyperDex (there's the Tenzing paper from Google). But I'm not looking specifically at SQL, but at more general scope.