Cassandra
  1. Cassandra
  2. CASSANDRA-65

Support for non-hash based partitioners

    Details

    • Type: Improvement Improvement
    • Status: Resolved
    • Priority: Major Major
    • Resolution: Fixed
    • Fix Version/s: 0.3
    • Component/s: None
    • Labels:
      None

      Issue Links

        Activity

        Hide
        Jonathan Ellis added a comment -

        5 r/m StorageService.token in favor of explicitly passing a Partitioner object. this allows testing of components independent of the static SS.

        4 replace BigInteger tokens with BigIntegerToken and StringToken in RandomPartitioner and OrderPreservingPartitioner, respectively. (OrderPreservingHashPartitioner is no more.)

        Doing order preserving partitioning based on the raw string has a number of compellingadvantages:

        • there is no key length that all tokens must be padded to (which can be expensive ifthere is a range of key lengths) and which cannot be increased after deployment
        • it allows user-defined collations [sorting] rather than being limited to sorting bycode point value (which is useless in the unicode world, and not always what you want evenfor ascii keys)
        • it will work with all UTF-16 characters, not just the UCS-2 subset (this is a limitation of using as a base 2**16, i.e., assuming for your order preserving hash that all characters are two bytes).

        3 clean up partition strategies; in particular, implement getStorageEndPoints(String[] keys) in terms of getStorageEndPoints(BigInteger token), instead of copy/pasting code

        2 r/m unused code

        1 move *Partitioner from cassandra.service to cassandra.dht

        Show
        Jonathan Ellis added a comment - 5 r/m StorageService.token in favor of explicitly passing a Partitioner object. this allows testing of components independent of the static SS. 4 replace BigInteger tokens with BigIntegerToken and StringToken in RandomPartitioner and OrderPreservingPartitioner, respectively. (OrderPreservingHashPartitioner is no more.) Doing order preserving partitioning based on the raw string has a number of compellingadvantages: there is no key length that all tokens must be padded to (which can be expensive ifthere is a range of key lengths) and which cannot be increased after deployment it allows user-defined collations [sorting] rather than being limited to sorting bycode point value (which is useless in the unicode world, and not always what you want evenfor ascii keys) it will work with all UTF-16 characters, not just the UCS-2 subset (this is a limitation of using as a base 2**16, i.e., assuming for your order preserving hash that all characters are two bytes). 3 clean up partition strategies; in particular, implement getStorageEndPoints(String[] keys) in terms of getStorageEndPoints(BigInteger token), instead of copy/pasting code 2 r/m unused code 1 move *Partitioner from cassandra.service to cassandra.dht
        Hide
        Jonathan Ellis added a comment -

        oops, 0005 has errors. corrected version attached.

        Show
        Jonathan Ellis added a comment - oops, 0005 has errors. corrected version attached.
        Hide
        Jonathan Ellis added a comment -

        Got a bit farther into writing a test and found more static code I needed to clean out in 0005.

        Show
        Jonathan Ellis added a comment - Got a bit farther into writing a test and found more static code I needed to clean out in 0005.
        Hide
        Jonathan Ellis added a comment -

        removed 0005 until the test is finished.

        Show
        Jonathan Ellis added a comment - removed 0005 until the test is finished.
        Hide
        Jonathan Ellis added a comment -

        Attached strategy cleanup + test patches.

        Show
        Jonathan Ellis added a comment - Attached strategy cleanup + test patches.
        Hide
        Jun Rao added a comment -

        I looked at the patch. A few comments.

        1. I'd leave ServiceStorage.showTheRing() there. It seems to be useful for some future utility.

        2. Rename IPartitioner.getDefaultToken to getRandomToken, since it's not really the expected default behavior.

        3. Why use elipsis instead of array in the following function?
        public BootStrapper(EndPoint[] target, Token... token)

        4. I'd leave SystemTable.main for future unit test.

        5. This may be for future improvement. The new orderpreserving partitioner still has the problem that the cluster may not be balanced for arbitrary keys. One way to fix this is to let applications specify the initial token for each node. Then we need a way to initialize token from the conf file.

        Other than those, the patch looks fine and ant test passes. However, since this is a relative major change, I think either Avinash or Prashant should take another look at it.

        Show
        Jun Rao added a comment - I looked at the patch. A few comments. 1. I'd leave ServiceStorage.showTheRing() there. It seems to be useful for some future utility. 2. Rename IPartitioner.getDefaultToken to getRandomToken, since it's not really the expected default behavior. 3. Why use elipsis instead of array in the following function? public BootStrapper(EndPoint[] target, Token... token) 4. I'd leave SystemTable.main for future unit test. 5. This may be for future improvement. The new orderpreserving partitioner still has the problem that the cluster may not be balanced for arbitrary keys. One way to fix this is to let applications specify the initial token for each node. Then we need a way to initialize token from the conf file. Other than those, the patch looks fine and ant test passes. However, since this is a relative major change, I think either Avinash or Prashant should take another look at it.
        Hide
        Jun Rao added a comment -

        Another thing, I am not sure what the implication of changing BigInteger.ZERO.toString() to "" in StorageService.getToken() is. Did you verify?

        Show
        Jun Rao added a comment - Another thing, I am not sure what the implication of changing BigInteger.ZERO.toString() to "" in StorageService.getToken() is. Did you verify?
        Hide
        Jonathan Ellis added a comment -

        Argh, Jira let me throw away my reply when I clicked on a link to doublecheck something. Here goes again.

        1. If we need it later we can resurrect it from svn. Dead code is more confusing than useful.

        2. We probably need a better name here – the idea is "generate a token that can be assigned as the default for this node's endpoint if it starts up without having one configured." How about getInitialToken?

        3. It just allows passing a single Token w/o explicitly wrapping it in an array (the compiler does it for you). IIRC I made use of this somewhere.

        4. It's already in a unit test, in SystemTableTest. My bad for not removing the main() method earlier.

        5. Yes, that will be in another patch.

        6. Good question – that method is only used by the status tool. So the question is what value to display when there is no token matching the endpoint. "0" is potentially confusing since it's a legitimate token value. Empty string leaves no doubt that there is no token. I can add a comment to this effect.

        Show
        Jonathan Ellis added a comment - Argh, Jira let me throw away my reply when I clicked on a link to doublecheck something. Here goes again. 1. If we need it later we can resurrect it from svn. Dead code is more confusing than useful. 2. We probably need a better name here – the idea is "generate a token that can be assigned as the default for this node's endpoint if it starts up without having one configured." How about getInitialToken? 3. It just allows passing a single Token w/o explicitly wrapping it in an array (the compiler does it for you). IIRC I made use of this somewhere. 4. It's already in a unit test, in SystemTableTest. My bad for not removing the main() method earlier. 5. Yes, that will be in another patch. 6. Good question – that method is only used by the status tool. So the question is what value to display when there is no token matching the endpoint. "0" is potentially confusing since it's a legitimate token value. Empty string leaves no doubt that there is no token. I can add a comment to this effect.
        Hide
        Jonathan Ellis added a comment -

        > since this is a relative major change, I think either Avinash or Prashant should take another look at it.

        Yes, and Avinash said he wanted to review it. Assigning to him.

        Show
        Jonathan Ellis added a comment - > since this is a relative major change, I think either Avinash or Prashant should take another look at it. Yes, and Avinash said he wanted to review it. Assigning to him.
        Hide
        Jonathan Ellis added a comment -

        Rebase against current HEAD. Added changes requested by Jun.

        Show
        Jonathan Ellis added a comment - Rebase against current HEAD. Added changes requested by Jun.
        Hide
        Jonathan Ellis added a comment -

        rebase again.

        Show
        Jonathan Ellis added a comment - rebase again.
        Hide
        Jonathan Ellis added a comment -

        rebased, again

        Show
        Jonathan Ellis added a comment - rebased, again
        Hide
        Jonathan Ellis added a comment -

        It's been three weeks and no other reviews have been forthcoming. Committing.

        Show
        Jonathan Ellis added a comment - It's been three weeks and no other reviews have been forthcoming. Committing.
        Hide
        Hudson added a comment -

        Integrated in Cassandra #51 (See http://hudson.zones.apache.org/hudson/job/Cassandra/51/)
        rename getDefaultToken -> getInitialToken
        patch by jbellis; reviewed by Jun Rao for
        add test for ReplicaPlacementStrategy covering both Random and OrderPreserving partitioners
        patch by jbellis; reviewed by Jun Rao for
        r/m StorageService.token in favor of explicitly passing a Partitioner object. this allows testing of components independent of the static SS.
        patch by jbellis; reviewed by Jun Rao for
        replace BigInteger tokens with BigIntegerToken and StringToken in RandomPartitioner and OrderPreservingPartitioner, respectively. (OrderPreservingHashPartitioner is no more.)

        Doing order preserving partitioning based on the raw string has a number of compelling advantages:

        • there is no key length that all tokens must be padded to (which can be expensive if there is a range of key lengths) and which cannot be increased after deployment
        • it allows user-defined collations [sorting] rather than being limited to sorting by code point value (which is useless in the unicode world, and not always what you want even for ascii keys)
        • it will work with all UTF-16 characters, not just the UCS-2 subset (this is a limitation of using as a base 2**16, i.e., assuming for your order preserving hash that all characters are two bytes).

        patch by jbellis; reviewed by Jun Rao for
        clean up partition strategies; in particular, implement getStorageEndPoints(String[] keys) in terms of getStorageEndPoints(BigInteger token), instead of copy/pasting code
        patch by jbellis; reviewed by Jun Rao for
        r/m unused code
        patch by jbellis; reviewed by Jun Rao for
        move *Partitioner from cassandra.service to cassandra.dht.
        patch by jbellis; reviewed by Jun Rao for

        Show
        Hudson added a comment - Integrated in Cassandra #51 (See http://hudson.zones.apache.org/hudson/job/Cassandra/51/ ) rename getDefaultToken -> getInitialToken patch by jbellis; reviewed by Jun Rao for add test for ReplicaPlacementStrategy covering both Random and OrderPreserving partitioners patch by jbellis; reviewed by Jun Rao for r/m StorageService.token in favor of explicitly passing a Partitioner object. this allows testing of components independent of the static SS. patch by jbellis; reviewed by Jun Rao for replace BigInteger tokens with BigIntegerToken and StringToken in RandomPartitioner and OrderPreservingPartitioner, respectively. (OrderPreservingHashPartitioner is no more.) Doing order preserving partitioning based on the raw string has a number of compelling advantages: there is no key length that all tokens must be padded to (which can be expensive if there is a range of key lengths) and which cannot be increased after deployment it allows user-defined collations [sorting] rather than being limited to sorting by code point value (which is useless in the unicode world, and not always what you want even for ascii keys) it will work with all UTF-16 characters, not just the UCS-2 subset (this is a limitation of using as a base 2**16, i.e., assuming for your order preserving hash that all characters are two bytes). patch by jbellis; reviewed by Jun Rao for clean up partition strategies; in particular, implement getStorageEndPoints(String[] keys) in terms of getStorageEndPoints(BigInteger token), instead of copy/pasting code patch by jbellis; reviewed by Jun Rao for r/m unused code patch by jbellis; reviewed by Jun Rao for move *Partitioner from cassandra.service to cassandra.dht. patch by jbellis; reviewed by Jun Rao for

          People

          • Assignee:
            Jonathan Ellis
            Reporter:
            Jonathan Ellis
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development