Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

HyperDex: A Searchable Distributed Key-Value Store

hyperdex.org

Post reply on HN
Print view View original

21–30 of 89 posts

Re: HyperDex: A Searchable Distributed Key-Value Store

#21

Post by ericmoritz »

nicktelford wrote: post #11
snewman wrote: post #6

Earlier quoted context omitted.

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

This sounds like a CP system to me. There's nothing wrong with that btw, I don't know why people are so reluctant to admit this. AP systems have some useful properties, but they're also (typically) more difficult to reason about. The "hiccups" you describe are periods of unavailability. The increased latency is caused by an element of the system waiting for the data to become available again, a totally valid strategy…

That's what I was getting at. It's appears to be a CP system. I wish all new distributed databases would have a nice little badge that says, "CP", "AP" or "CA".

Whenever they claim to be distributed but not subject to CAP, I automatically become skeptical.

There's nothing wrong with a CP database; HBase is a CP database and it's quite popular.

Re: HyperDex: A Searchable Distributed Key-Value Store

#22

Post by jandrewrogers »

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.

Re: HyperDex: A Searchable Distributed Key-Value Store

#23

Post by tlb »

rescrv wrote: post #16
tlb wrote: post #13

Earlier quoted context omitted.

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

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

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.

Re: HyperDex: A Searchable Distributed Key-Value Store

#26

Post by rescrv »

tlb wrote: post #23
rescrv wrote: post #16

Earlier quoted context omitted.

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

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.

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.

Re: HyperDex: A Searchable Distributed Key-Value Store

#28

Post by jfager »

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?

Re: HyperDex: A Searchable Distributed Key-Value Store

#29

Post by DEinspanjer »

rescrv wrote: post #25
DEinspanjer wrote: post #24

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

The packages are built for Ubuntu 11.10. What version of Ubuntu are you running?

Thanks for letting me know the target version. I am running 10.4.4 LTS

Re: HyperDex: A Searchable Distributed Key-Value Store

#30

Post by jdf »

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."

Post reply on HN