Papers exploring distributed P2P network.

Abridged version of John's mail.

The main concern for a simple implementation of range partitioned index is load
skew and rebalancing, there are a couple of papers on P2P network for
supporting range query on top of balanced distribution. The design space for
P2P is slightly different from us, but they are largely relevant. For example:
  fault tolerance,
  load balancing
  network configuration tolerance – when add/delete a node, only a few
    neighboring nodes need to be affected
  congestion tolerance – avoid certain nodes being hot spot during
    search (e.g. Root node of a binary search tree)

The committed papers are similar in the sense that data (or range of data) is
hash partitioned to achieve load balancing. An separate data structure, called
"overlay network", can be used to maintain the ordering of the data range query.
In our case, the overlay network can be used to maintain the order of
pages/slices. Each page/slice is fixed size and contain a ordered collection
of keys/values. A range, therefore, is made up of an ordered collection of
pages/slices, and an index is made up of a ordered collection of ranges.
The page size is a tunable parameter that specifies the degree of data
locality, and therefore, it would affect query performance to some degree.

Prefix Hash Table (PHT) uses a Trie as the overlay network.  Skip Graph
uses multi-tier linked list.    Skip Net is similar to Skip Graph, but it
uses multi-tier circular linked list.   Both SkipGraph and SkipNet are
enhancement over SkipList.   SkipList has some advantages over PHT in the
sense that there are a lot of researches conducted over that, and it
offers congestion tolerance and network configuration tolerance.  There
are tons of variations on SkipList and SkipGraph as well.

Obviously, as an alternative, we could also keep a centralized structure
(e.g. b-tree) in each node, as to maintain the ordering of slices/pages.
But we have to make sure that whenever a page/slice is added/removed, each
b-tree will need to be updated, since index can return wrong result if the
b-tree is not updated properly (e.g. loss messages).   By distributing the
overlay network itself among the nodes, then only the neighboring nodes
need to be updated.

We can discuss more options.  The basic point is that we can achieve load
balancing in expense of higher cost of range query.   With a
strict-forward and naïve range-based index-clustering, it maximizes data
locality, but complicates load balancing and therefore data skew.
Alternatively, if we use hash partitioning on index pages/slices, it can
yield more predictable DGM ratio per node, with the expense of extra
messaging overhead during range scan.   Assume intra-cluster network
latency is low, it can be an attractive alternative.