HyperDex: A Searchable Distributed Key-Value Store • Hacker News Board

Re: HyperDex: A Searchable Distributed Key-Value Store

#81

Post by lobster_johnson » Thu, Feb 23, 2012, 3:15 PM UTC

Craiggybear wrote: post #71

wickedchicken wrote: post #53

Earlier quoted context omitted.

* 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…

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 a…

SQL is a very, very poor implementation of relational algebra. For example, the output of an SQL query is not even a valid relation variable (in E. F. Codd's terminology).

If you want to look at how SQL might have looked if it had been relational, take a look at "Tutorial D", the language proposed in a book called The Third Manifesto, by Hugh Darwen and C. J. Date: http://thethirdmanifesto.com/. There are several experimental implementations.

Re: HyperDex: A Searchable Distributed Key-Value Store

#82

Post by rescrv » Thu, Feb 23, 2012, 4:03 PM UTC

jdf wrote: post #34

rescrv wrote: post #26

Earlier quoted context omitted.

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 opera…

What happens if a crash happens part way through the acknowledgement chain? For example, in your insert, if the node containing "x" crashes before it receives the ACK from the node containing "y" - do the dangling "y" and "z" insertions ever need to be cleaned up?

The chains heal in a similar fashion to chain replication (http://www.cs.cornell.edu/home/rvr/papers/osdi04.pdf).

There will be no dangling insertions.

Re: HyperDex: A Searchable Distributed Key-Value Store

#83

Post by xijhing » Thu, Feb 23, 2012, 7:40 PM UTC

ericmoritz wrote: post #4

From the FAQ " rel="nofollow">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 gue…

PACELC[1] helps distinguish just the kind of CAP sacrifice this makes.

[1] http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-an...

Re: HyperDex: A Searchable Distributed Key-Value Store

#84

Post by the_paul » Thu, Feb 23, 2012, 8:00 PM UTC

rbranson wrote: post #58

snewman wrote: post #35

Earlier quoted context omitted.

To be precise, I would argue this is actually a CA system. "C" because there are consistency guarantees, which are upheld even in the face of failures / partition. "A" because the system will continue making progress even after a node failure. What I called a "hiccup" can be made arbitrarily short, in principle at least. The system can work around failed nodes, it does not need to wait for them to be repaired. Not "P…

There is no CA. You cannot guarantee consistency and availability simultaneously in the face of network partitions. Once the line of communications is cut or overloaded (slow enough = a partition), you have to pick one or the other. It's basic physics. If two entities can't communicate, they can't synchronize state, so one (or both) of them have to quit acting like they have a consistent view of the data.

It's not exactly clear from the paper what CA should mean.

I've seen people claim it means "you guarantee both consistency and availability, as long as there are no network partitions (you don't have to handle those because you haven't chosen P)". That's a supportable claim. So you can do that, but it's kind of a useless choice, because as long as there are no network partitions, both CP and AP systems can also guarantee full consistency and availability.

I lay the CAP family out thus:

* CP: on network partition, lose availability

* AP: on network partition, lose consistency

* CA: on network partition, lose both

It seems to be a common thread among distributed systems engineers who claim to have beaten CAP: "network partitions don't matter for whatever reason, so therefore I can always guarantee both availability and consistency and so CAP must be wrong yaaay!!"

Sorry, no, nice try.

Re: HyperDex: A Searchable Distributed Key-Value Store

#85

Post by rescrv » Thu, Feb 23, 2012, 8:11 PM UTC

jfager wrote: post #77

rescrv wrote: post #73

Earlier quoted context omitted.

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.

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.

It's the former. I'd rather not sacrifice our strong consistency by using replicas to serve GET requests.

Re: HyperDex: A Searchable Distributed Key-Value Store

#86

Post by otterley » Thu, Feb 23, 2012, 8:57 PM UTC

lobster_johnson wrote: post #79

otterley wrote: post #68

Earlier quoted context omitted.

> 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…

> 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…

Did you read my entire comment? I specifically said, "when the working set is larger than RAM."

Your observations, while true in the abstract, don't reflect real-world behavior under these conditions.

Re: HyperDex: A Searchable Distributed Key-Value Store

#87

Post by Cloven » Fri, Feb 24, 2012, 2:07 AM UTC

foobarbazetc wrote: post #47

nirvana wrote: post #42

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…

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 ben…

Have you looked at YCSB? It's a pathologically poorly designed benchmark. It essentially tests how good a developer is at implementing a Java wrapper around a toy object model and interfacing that with a database.

A proper benchmark would hold constant things which are reasonably expected to be constant: the use case scenario, the data, the warmup requirements, the concurrency, and the count. If feeling frisky, the hardware, operating system and networking environment. And then step back.

For example, "On an EC2 Extra Large instance running Ubuntu 11.10 with whatever tuning the package recommends, what is the transactions per second when 50 vendor-provided clients on the same LAN are attempting to write and read random records out of a pool of 10mm 5k records?"

Re: HyperDex: A Searchable Distributed Key-Value Store

#88

Post by icanhazdata » Sat, Mar 03, 2012, 5:54 AM UTC

otterley wrote: post #86

lobster_johnson wrote: post #79

Earlier quoted context omitted.

> 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…

Did you read my entire comment? I specifically said, "when the working set is larger than RAM." Your observations, while true in the abstract, don't reflect real-world behavior under these conditions.

Working set larger than ram doesn't imply thrashing. It all depends on the page replacement algorithm employed by the OS, and the applications that are running.

Re: HyperDex: A Searchable Distributed Key-Value Store

#89

Post by icanhazdata » Sat, Mar 03, 2012, 1:10 PM UTC

antirez wrote: post #59

rescrv wrote: post #39

Earlier quoted context omitted.

Both systems were single process per host. I agree that Redis does not have good support for "E", so anyone looking at the results should look at A-D,F. Both systems performed entirely out of main memory to avoid touching disk. The Redis benchmark results only came in last night. We'll be writing up the methodology soon. We used the YCSB Redis binding from branch master. I'd be interested in your opinion on how well…

Redis uses a single thread, not just a single process, so if Hyperdex is multi-threaded you are comparing single core vs multiple cores. As you can see with memcached that instead is able to use multiple cores (a feature that Redis is going to implement soon) this leads to a big performance improvement in this kind of benchmarks. EDIT: (I checked that Hyperdex actually uses threads and multiple cores) If you want a f…

I think YCSB is meant so that experts in each technology can tweak it for their system. So, it looks to me like you're in a great place to make that happen, and I'd love to see it!

Also, It's extremely difficult to get speedup of 4x on 4 cores, so I'll believe that argument when I see it. It seems to me that with the current implementation of Redis, you'd run into some serious problems with memory management if you run 4 redis nodes on one 4 core machine.

Also, you say: "This is a possible use case of Redis but not a very idiomatic / representative one." Can you elaborate? What is idiomatic? From the front page of the Redis site: "Redis is an open source, advanced key-value store."

Also, on a slightly different topic, I can't seem to find any real documentation about the consistency guarantees of Redis, so I thought you might be able to point me in the right direction. It appears that the master/slave replication scheme in Redis just backs up onto the slaves eventually, but the master immediately returns. Is that true? If a master goes down (disk and all), could a write have been confirmed to the client which is missing on a slave? What replication protocol does it use? I find the documentation lacking in this regard and it'd be great if you could point me to some actual technical specifications. Thanks!