incubator-cassandra-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jun Rao <jun...@almaden.ibm.com>
Subject Re: OPHF
Date Thu, 02 Apr 2009 16:38:31 GMT

Johnathan,

Could you explain a bit more how the pluggable partitioner (that provides
String-> EndPoint mapping) works?

In particular,
1. How does the partitioner obtain the list of EndPoints in the system?
2. What happens when EndPoints are added/removed from the system? Does the
partitioner have to remember the history of the EndPoints?
3. How does the partitioner coordinate with the load-balancer? Suppose some
rows are moved from one EndPoint to another. How is that information
communicated and used by the partitioner so that routing remains correct?

The answers may be found from your code. However, it will be helpful if you
can provide a high-level description here.

Jun
IBM Almaden Research Center
K55/B1, 650 Harry Road, San Jose, CA  95120-6099

junrao@almaden.ibm.com


Jonathan Ellis <jbellis@gmail.com> wrote on 04/01/2009 02:31:58 PM:

>
> Avinash already commited his new order-preserving hash function and I
> missed it.  It's in OrderPreservingHashPartitioner.  It takes the
> approach that Todd and I discussed back in January: turn the string
> into a base-Char.MAX_VALUE number.
> (http://groups.google.com/group/cassandra-
> dev/browse_thread/thread/6bda8518466210e7/f53b79c19010a9ed).
>  I chatted with Avinash a little on IM but we didn't finish, so I'm
> picking it up here.
>
> There are two problems with this approach.  One is that the hashes
> will only be order-preserving for a subset of unicode (all of UCS-2,
> but not all of UTF-16; see http://en.wikipedia.org/wiki/UTF-16/UCS-2).
>  The other is that this only gives you a naive ordering by code point
> value, which for unicode is not what you want and even for ascii
> sometimes you want another collation.  (see
> http://www.unicode.org/reports/tr10/ and
> http://java.sun.com/javase/6/docs/api/java/text/Collator.html).
>
> Say for instance you have inserted keys ['a', 'b', '--a', '--b'] and
> you are going to do range queries on them.  The correct
> collation-aware sort is ['a', '--a', 'b', '--b'].  But ordering by
> char value gives ['--a', '--b', 'a', 'b'].
>
> Switching to a more flexibile system like the one I wrote for
> CASSANDRA-3 will let use use Token<BigInteger> for random distribution
> or Token<String> for order-preserving, with user-defined collation.  I
> don't see a way to get this kind of flexibility from an approach that
> insists on turning everything into BigInteger.
>
> -Jonathan
>
> On Mon, Mar 30, 2009 at 2:16 PM, Jonathan Ellis <jbellis@gmail.com>
wrote:
> > Avinash,
> >
> > You mentioned that you have a new order-preserving hash function that
> > you think will be more generally useful.  Can you post it?
> >
> > thanks,
> >
> > -Jonathan
> >
Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message