Neat. From a very cursory glance at the HyperDex paper, it looks like a distributed kd-tree with the addition of a single-dimensional key subspace (to use their terminology). The real clever part, I believe, is the value-dependent chaining for the deterministic propagation of changes/deletion of objects.
Thanks! Unlike a kd-tree or b-tree variants, HyperDex does not build an auxiliary data structure. It turns out that keeping aux data structures in sync with the data is very difficult if you want to provide strong consistency guarantees. Hyperspace hashing is purely a mapping trick, not a distributed data-structure trick.
Agreed with you fully that value-dependent chains are neat. They allow the system to replicate and relocate data, without any need for background processes. VDCs are the key to HyperDex's strong consistency guarantees.
Comments
Neat. From a very cursory glance at the HyperDex paper, it looks like a distributed kd-tree with the addition of a single-dimensional key subspace (to use their terminology). The real clever part, I believe, is the value-dependent chaining for the deterministic propagation of changes/deletion of objects.
Very cool.
Thanks! Unlike a kd-tree or b-tree variants, HyperDex does not build an auxiliary data structure. It turns out that keeping aux data structures in sync with the data is very difficult if you want to provide strong consistency guarantees. Hyperspace hashing is purely a mapping trick, not a distributed data-structure trick.
Agreed with you fully that value-dependent chains are neat. They allow the system to replicate and relocate data, without any need for background processes. VDCs are the key to HyperDex's strong consistency guarantees.