incubator-cassandra-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jonathan Ellis <jbel...@gmail.com>
Subject Re: Write placement questions: ringIterator() and firstTokenIndex()
Date Tue, 12 Jul 2011 19:32:12 GMT
You're going to be mad at how simple the answer turns out to be. :)

Nodes "own" the range from (previous, token], NOT from [token, next).
So, the last node will get from (50, 75] and the first will get from
(75, 0].

On Tue, Jul 12, 2011 at 9:38 AM, Eric tamme <etamme@gmail.com> wrote:
> I have been reading through some code in TokenMetadata.java,
> specifically with ringIterator() and firstTokenIndex().  I am trying
> to get a very firm grasp on how nodes are collected for writes.
>
> I have run into a bit of confusion about what happens when the data's
> token is larger than than the largest initial token. It looks to me
> like there is no way for the largest token node to get a write.  I
> know this can't be correct, and that I must be missing some thing.  If
> any one can help to fill in what I am missing I would appreciate it.
>
> Lets say I have a hypothetical token range of 0-100 (for simplicity
> sake) and 4 nodes using RandomPartitioner and SimpleStrategy.  My
> nodes are configured with initial tokens: 0,25,50,75.
>
> If I receive a write for data whose token is 85 (or any number > 75)
> this is the code path as far as I can tell:
>
> SimpleStrategy will create a ringIterator and pass it in a list of all
> the initial tokens [0,25,50,75]
>
> The ringIterator will in turn call firstTokenIndex and pass it the
> token list, and token we are trying to insert
>
> final int startIndex = firstTokenIndex(ring, start, insertMin);.
>
> firstTokenIndex will then do a Collections.binarySearch to try to find
> the index of where the token should be inserted
>
> int i = Collections.binarySearch(list, token);
>
> Here is the JavaDoc on Collections.binarySearch:
>
> "Returns:
>    index of the search key, if it is contained in the list;
> otherwise, (-(insertion point) - 1). The insertion point is defined as
> the point at which the key would be inserted into the list: the index
> of the first element greater than the key, or list.size(), if all
> elements in the list are less than the specified key. Note that this
> guarantees that the return value will be >= 0 if and only if the key
> is found. "
>
> So in this example, 85 is larger than any of the available tokens so
> (-(list.size())-1) or (-(4)-1) = -5 will be returned.
>
> From there, firstTokenIndex does some processing on the return value:
>
> if (i < 0)
> {
>  i = (i + 1) * (-1);        // i is now 4
>  if (i >= ring.size())      // evaluates true
>    i = insertMin ? -1 : 0;  // 0 is returned
> }
> return i;
>
> So we return index 0 to the ringIterator... which will try to execute
> a ring.get(0) for the first next() based on our return value.
>
> here is the calling, and processing code for ringIterator:
>
>        return new AbstractIterator<Token>()
>        {
>            int j = startIndex;
>            protected Token computeNext()
>            {
>                if (j < -1)
>                    return endOfData();
>                try
>                {
>                    // return minimum for index == -1
>                    if (j == -1)
>                        return
> StorageService.getPartitioner().getMinimumToken();
>                    // return ring token for other indexes
>                    return ring.get(j);
>                }
>                finally
>                {
>                    j++;
>                    if (j == ring.size())
>                        j = insertMin ? -1 : 0;
>                    if (j == startIndex)
>                        // end iteration
>                        j = -2;
>                }
>            }
>        };
>
> Thanks,
> Eric
>



-- 
Jonathan Ellis
Project Chair, Apache Cassandra
co-founder of DataStax, the source for professional Cassandra support
http://www.datastax.com

Mime
View raw message