UUID ordered token for Cassandra

UUIDOrderPartitioner.java

package org.apache.cassandra.dht;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.nio.charset.CharacterCodingException;
import java.util.*;

import org.apache.cassandra.config.*;
import org.apache.cassandra.config.ConfigurationException;
import org.apache.cassandra.service.StorageService;
import org.apache.cassandra.db.DecoratedKey;
import org.apache.cassandra.utils.ByteBufferUtil;
import org.apache.cassandra.utils.FBUtilities;
import org.apache.cassandra.utils.GuidGenerator;
import org.apache.cassandra.utils.Pair;

import java.util.UUID;
import org.apache.cassandra.utils.UUIDGen;

import org.apache.log4j.Level;
import org.apache.commons.lang.StringUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class UUIDOrderPartitioner extends AbstractPartitioner<UUIDToken>
{
    private static final long START_EPOCH = -12219292800000L;
    private static final long END_EPOCH = 12219292800000L;
    public static final UUIDToken ZERO = new UUIDToken(ByteBuffer.wrap(UUIDGen.getTimeUUIDBytes(START_EPOCH)));
    public static final UUIDToken MINIMUM = ZERO;
    public static final UUIDToken MAXIMUM = new UUIDToken(ByteBuffer.wrap(UUIDGen.getTimeUUIDBytes(END_EPOCH)));

    private String byteArrayToString(byte[] in) {
        char out[] = new char[in.length * 2];
        for (int i = 0; i < in.length; i++) {
            out[i * 2] = "0123456789ABCDEF".charAt((in[i] >> 4) & 15);
            out[i * 2 + 1] = "0123456789ABCDEF".charAt(in[i] & 15);
        }
        return new String(out);
    }

    /**
     * Given a key in human readable format, obtain the key in machine format after
     * executing f(
     * @param key, a key
     * @return decoratedKey, the 
     */
    public DecoratedKey<UUIDToken> decorateKey(ByteBuffer key)
    {
        final byte[] bytes = new byte[key.remaining()];
        key.duplicate().get(bytes);

        ByteBuffer key_md5 = key.duplicate();
        final byte[] md5 = FBUtilities.hash(key_md5);
        ByteBuffer ret = ByteBuffer.wrap(new byte[md5.length]);
        ret.put(md5);

        return new DecoratedKey<UUIDToken>(getToken(ret), key);
    }

    public DecoratedKey<UUIDToken> convertFromDiskFormat(ByteBuffer key)
    {
        Logger logger_ = LoggerFactory.getLogger(UUIDOrderPartitioner.class);
        logger_.info("Calling convertFromDiskFormat");
        return new DecoratedKey<UUIDToken>(new UUIDToken(key), key);
    }

    public UUID midpoint(UUID l, UUID r)
    {
        long lt = UUIDGen.getAdjustedTimestamp((UUID)l);
        long rt = UUIDGen.getAdjustedTimestamp((UUID)r);
        long medio = 0L;
        long distance = 0L;
        if (l.compareTo(r) < 0)
        {
            distance = (rt - lt);
            medio = distance >> 1;
        }
        else
        {
            // wrapping case
            BigInteger left = BigInteger.valueOf(lt);
            BigInteger right = BigInteger.valueOf(rt);
            BigInteger max = BigInteger.valueOf(END_EPOCH);
            BigInteger bigdistance = max.add(right).subtract(left);
            BigInteger midpoint = bigdistance.shiftRight(1).add(left).mod(max);
            medio = midpoint.longValue();
        }
        
        Logger logger_ = LoggerFactory.getLogger(UUIDOrderPartitioner.class);
        logger_.info("Obtaining midpoint");
        logger_.info("left UUID is : "+l.toString());
        logger_.info("right UUID is : "+r.toString());
        logger_.info("middle point in millis is : "+medio);
        UUID middle_uuid = UUIDGen.getUUID(ByteBuffer.wrap(UUIDGen.getTimeUUIDBytes(medio)));
        logger_.info("UUID for middle point is is : "+middle_uuid.toString());
        return middle_uuid;
        //return UUIDGen.getUUID(ByteBuffer.wrap(UUIDGen.getTimeUUIDBytes(medio)));
    }

    public Token midpoint(Token ltoken, Token rtoken)
    {
        UUID left, right;
        // the symbolic MINIMUM token should act as ZERO: the empty bit array
        if (ltoken.equals(MINIMUM)){
            left =  ZERO.token;
        }
        else{
            left = ((UUIDToken)ltoken).token;
        }
        if (rtoken.equals(MINIMUM)){
            right =  ZERO.token;
        }
        else{
            right = ((UUIDToken)rtoken).token;
        }
        return new UUIDToken(midpoint(left, right));
    }

	public UUIDToken getMinimumToken()
    {
        return MINIMUM;
    }

    public UUIDToken getRandomToken()
    {
        Random r = new Random();
        byte[] bytes = new byte[16];
        r.nextBytes(bytes);
        ByteBuffer ret = ByteBuffer.wrap(new byte[16]);
        ret.put(bytes);
        UUIDToken t = getToken(ret);

        Logger logger_ = LoggerFactory.getLogger(UUIDOrderPartitioner.class);
        logger_.info("generated token is : "+t.toString());

        return t;
        //return new UUIDToken(ByteBuffer.wrap(UUIDGen.getTimeUUIDBytes(i)));
    }

    private final Token.TokenFactory<UUID> tokenFactory = new Token.TokenFactory<UUID>() {
        public ByteBuffer toByteArray(Token<UUID> token)
        {
            return ByteBuffer.wrap(UUIDGen.decompose(token.token));
        }

        public Token<UUID> fromByteArray(ByteBuffer bytes)
        {
            return new UUIDToken(bytes);
        }

        public String toString(Token<UUID> t)
        {
            return t.token.toString();
        }

        public void validate(String token) throws ConfigurationException
        {
            try
            {
                UUIDToken i = new UUIDToken(token);
                if (i.compareTo(ZERO) < 0)
                    throw new ConfigurationException("Token must be >= 00:00:00.000 15 Oct 1582. but "+i.toString()+" and ZERO: "+ZERO.toString());
                if (i.compareTo(MAXIMUM) > 0)
                    throw new ConfigurationException("Token must be <= 2 * 00:00:00.000 15 Oct 1582. but "+i.toString());
            }
            catch (NumberFormatException e)
            {
                throw new ConfigurationException(e.getMessage());
            }
        }

        public Token<UUID> fromString(String string)
        {
            return new UUIDToken(string);
        }
    };

    public Token.TokenFactory<UUID> getTokenFactory()
    {
        return tokenFactory;
    }

    public boolean preservesOrder()
    {
        return true;
    }

    public UUIDToken getToken(ByteBuffer key)
    {
        if (key.remaining() == 0)
            return MINIMUM;
        return new UUIDToken(key);
    }

    public Map<Token, Float> describeOwnership(List<Token> sortedTokens)
    {
        // allTokens will contain the count and be returned, sorted_ranges is shorthand for token<->token math.
        Map<Token, Float> allTokens = new HashMap<Token, Float>();
        List<Range<Token>> sortedRanges = new ArrayList<Range<Token>>(sortedTokens.size());

        // this initializes the counts to 0 and calcs the ranges in order.
        Token lastToken = sortedTokens.get(sortedTokens.size() - 1);
        for (Token node : sortedTokens)
        {
            allTokens.put(node, new Float(0.0));
            sortedRanges.add(new Range<Token>(lastToken, node));
            lastToken = node;
        }

        for (String ks : Schema.instance.getTables())
        {
            for (CFMetaData cfmd : Schema.instance.getKSMetaData(ks).cfMetaData().values())
            {
                for (Range<Token> r : sortedRanges)
                {
                    // Looping over every KS:CF:Range, get the splits size and add it to the count
                    allTokens.put(r.right, allTokens.get(r.right) + StorageService.instance.getSplits(ks, cfmd.cfName, r, 1).size());
                }
            }
        }

        // Sum every count up and divide count/total for the fractional ownership.
        Float total = new Float(0.0);
        for (Float f : allTokens.values())
            total += f;
        for (Map.Entry<Token, Float> row : allTokens.entrySet())
            allTokens.put(row.getKey(), row.getValue() / total);

        return allTokens;
    }
}

UUIDToken.java

package org.apache.cassandra.dht;

import java.nio.ByteBuffer;
import java.util.UUID;
import org.apache.cassandra.utils.UUIDGen;

import org.apache.log4j.Level;
import org.apache.commons.lang.StringUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;


public class UUIDToken extends Token<UUID>
{
    static final long serialVersionUID = 1L;

    public UUIDToken(ByteBuffer token)
    {
        this(UUIDGen.getUUID(token));
    }

    public UUIDToken(UUID token)
    {
        super(token);
    }

    // convenience method for testing
    public UUIDToken(String token) {
        this((UUID)UUID.fromString(token));
    }

    @Override
    public int hashCode()
    {
        return token.hashCode();
    }

    @Override
    public boolean equals(Object obj)
    {
        if (this == obj)
            return true;
        if (!(obj instanceof UUIDToken))
            return false;
        UUIDToken other = (UUIDToken) obj;

        return (token == other.token);
    }

    public int compareTo(Token<UUID> o)
    {
        int res = this.token.compareTo(o.token);
        return res;
    }
}