Details

    • Type: New Feature
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 4.1.0-incubating
    • Component/s: rocketmq-client
    • Labels:
      None

      Description

      For now, the average allocate strategy is very sensitive when clients register and unrigister.

      A Consistent Hash allocate strategy option is valueable for the developers who care more about latency stabilization and messages duplication.

      Intentions:
      The default AllocateMessageQueueStrategy is averaging strategy which allocate queue to consumer as evenly as possible. Whenever queues numbers or consumer numbers changed, say a new consumer starts or an old consumer shutdowns, a rehashing will be triggered then almost all consumer suffered from this that they will rebalance to drop old queues and get new queues.

      And that will cause

      message latency from producer to consumer increases at the moment when consumer/queue numbers change, even when they scale up.

      messages will be duplicated significantly since the offset may not be persisted to broker and that queue is assigned to another consumer to pull messages from.

      This is especially significant when they have tens of consumer instances and scale-up or deployment is often.

      Consistent Hash strategy to allocate queue is a good choice for these users.

        Issue Links

          Activity

          Hide
          githubbot ASF GitHub Bot added a comment -

          GitHub user Jaskey opened a pull request:

          https://github.com/apache/incubator-rocketmq/pull/67

          ROCKETMQ-67 Consistent Hash allocate strategy

          JIRA: https://issues.apache.org/jira/browse/ROCKETMQ-67

          suport virtual nodes and custom hash algorithm

          You can merge this pull request into a Git repository by running:

          $ git pull https://github.com/Jaskey/incubator-rocketmq ROCKETMQ-67-Consistent-Hash

          Alternatively you can review and apply these changes as the patch at:

          https://github.com/apache/incubator-rocketmq/pull/67.patch

          To close this pull request, make a commit to your master/trunk branch
          with (at least) the following in the commit message:

          This closes #67


          commit a56df6a703a4e4474ec401244b0343c1fe29f324
          Author: Jaskey <linjunjie1103@gmail.com>
          Date: 2017-02-20T07:13:09Z

          ROCKETMQ-67 : Consistent Hash allocate strategy


          Show
          githubbot ASF GitHub Bot added a comment - GitHub user Jaskey opened a pull request: https://github.com/apache/incubator-rocketmq/pull/67 ROCKETMQ-67 Consistent Hash allocate strategy JIRA: https://issues.apache.org/jira/browse/ROCKETMQ-67 suport virtual nodes and custom hash algorithm You can merge this pull request into a Git repository by running: $ git pull https://github.com/Jaskey/incubator-rocketmq ROCKETMQ-67 -Consistent-Hash Alternatively you can review and apply these changes as the patch at: https://github.com/apache/incubator-rocketmq/pull/67.patch To close this pull request, make a commit to your master/trunk branch with (at least) the following in the commit message: This closes #67 commit a56df6a703a4e4474ec401244b0343c1fe29f324 Author: Jaskey <linjunjie1103@gmail.com> Date: 2017-02-20T07:13:09Z ROCKETMQ-67 : Consistent Hash allocate strategy
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user coveralls commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          [![Coverage Status](https://coveralls.io/builds/10230561/badge)](https://coveralls.io/builds/10230561)

          Coverage increased (+0.08%) to 31.603% when pulling *a56df6a703a4e4474ec401244b0343c1fe29f324 on Jaskey:ROCKETMQ-67-Consistent-Hash* into *573b22c37806a21543b90707bcce6022243a62da on apache:master*.

          Show
          githubbot ASF GitHub Bot added a comment - Github user coveralls commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 [! [Coverage Status] ( https://coveralls.io/builds/10230561/badge)](https://coveralls.io/builds/10230561 ) Coverage increased (+0.08%) to 31.603% when pulling * a56df6a703a4e4474ec401244b0343c1fe29f324 on Jaskey: ROCKETMQ-67 -Consistent-Hash * into * 573b22c37806a21543b90707bcce6022243a62da on apache:master *.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user coveralls commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          [![Coverage Status](https://coveralls.io/builds/10230561/badge)](https://coveralls.io/builds/10230561)

          Coverage increased (+0.08%) to 31.603% when pulling *a56df6a703a4e4474ec401244b0343c1fe29f324 on Jaskey:ROCKETMQ-67-Consistent-Hash* into *573b22c37806a21543b90707bcce6022243a62da on apache:master*.

          Show
          githubbot ASF GitHub Bot added a comment - Github user coveralls commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 [! [Coverage Status] ( https://coveralls.io/builds/10230561/badge)](https://coveralls.io/builds/10230561 ) Coverage increased (+0.08%) to 31.603% when pulling * a56df6a703a4e4474ec401244b0343c1fe29f324 on Jaskey: ROCKETMQ-67 -Consistent-Hash * into * 573b22c37806a21543b90707bcce6022243a62da on apache:master *.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user coveralls commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          [![Coverage Status](https://coveralls.io/builds/10230561/badge)](https://coveralls.io/builds/10230561)

          Coverage increased (+0.08%) to 31.603% when pulling *a56df6a703a4e4474ec401244b0343c1fe29f324 on Jaskey:ROCKETMQ-67-Consistent-Hash* into *573b22c37806a21543b90707bcce6022243a62da on apache:master*.

          Show
          githubbot ASF GitHub Bot added a comment - Github user coveralls commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 [! [Coverage Status] ( https://coveralls.io/builds/10230561/badge)](https://coveralls.io/builds/10230561 ) Coverage increased (+0.08%) to 31.603% when pulling * a56df6a703a4e4474ec401244b0343c1fe29f324 on Jaskey: ROCKETMQ-67 -Consistent-Hash * into * 573b22c37806a21543b90707bcce6022243a62da on apache:master *.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user zhouxinyu commented on a diff in the pull request:

          https://github.com/apache/incubator-rocketmq/pull/67#discussion_r102124935

          — Diff: common/src/main/java/org/apache/rocketmq/common/consistenthash/Node.java —
          @@ -0,0 +1,24 @@
          +/*
          + * Licensed to the Apache Software Foundation (ASF) under one or more
          + * contributor license agreements. See the NOTICE file distributed with
          + * this work for additional information regarding copyright ownership.
          + * The ASF licenses this file to You under the Apache License, Version 2.0
          + * (the "License"); you may not use this file except in compliance with
          + * the License. You may obtain a copy of the License at
          + *
          + * http://www.apache.org/licenses/LICENSE-2.0
          + *
          + * Unless required by applicable law or agreed to in writing, software
          + * distributed under the License is distributed on an "AS IS" BASIS,
          + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
          + * See the License for the specific language governing permissions and
          + * limitations under the License.
          + */
          +package org.apache.rocketmq.common.consistenthash;
          +
          +/**
          + * Created by jaskeylin on 2017/2/20.
          — End diff –

          Hi, please remove the author info.

          Show
          githubbot ASF GitHub Bot added a comment - Github user zhouxinyu commented on a diff in the pull request: https://github.com/apache/incubator-rocketmq/pull/67#discussion_r102124935 — Diff: common/src/main/java/org/apache/rocketmq/common/consistenthash/Node.java — @@ -0,0 +1,24 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.rocketmq.common.consistenthash; + +/** + * Created by jaskeylin on 2017/2/20. — End diff – Hi, please remove the author info.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user Jaskey commented on a diff in the pull request:

          https://github.com/apache/incubator-rocketmq/pull/67#discussion_r102125928

          — Diff: common/src/main/java/org/apache/rocketmq/common/consistenthash/Node.java —
          @@ -0,0 +1,24 @@
          +/*
          + * Licensed to the Apache Software Foundation (ASF) under one or more
          + * contributor license agreements. See the NOTICE file distributed with
          + * this work for additional information regarding copyright ownership.
          + * The ASF licenses this file to You under the Apache License, Version 2.0
          + * (the "License"); you may not use this file except in compliance with
          + * the License. You may obtain a copy of the License at
          + *
          + * http://www.apache.org/licenses/LICENSE-2.0
          + *
          + * Unless required by applicable law or agreed to in writing, software
          + * distributed under the License is distributed on an "AS IS" BASIS,
          + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
          + * See the License for the specific language governing permissions and
          + * limitations under the License.
          + */
          +package org.apache.rocketmq.common.consistenthash;
          +
          +/**
          + * Created by jaskeylin on 2017/2/20.
          — End diff –

          Sorry , i didn'it notice that. Just a minute

          Show
          githubbot ASF GitHub Bot added a comment - Github user Jaskey commented on a diff in the pull request: https://github.com/apache/incubator-rocketmq/pull/67#discussion_r102125928 — Diff: common/src/main/java/org/apache/rocketmq/common/consistenthash/Node.java — @@ -0,0 +1,24 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.rocketmq.common.consistenthash; + +/** + * Created by jaskeylin on 2017/2/20. — End diff – Sorry , i didn'it notice that. Just a minute
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user coveralls commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          [![Coverage Status](https://coveralls.io/builds/10246847/badge)](https://coveralls.io/builds/10246847)

          Coverage increased (+0.2%) to 31.673% when pulling *fa0d936dd0b5a3dee482d97a11e0ea181e8b1f3a on Jaskey:ROCKETMQ-67-Consistent-Hash* into *573b22c37806a21543b90707bcce6022243a62da on apache:master*.

          Show
          githubbot ASF GitHub Bot added a comment - Github user coveralls commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 [! [Coverage Status] ( https://coveralls.io/builds/10246847/badge)](https://coveralls.io/builds/10246847 ) Coverage increased (+0.2%) to 31.673% when pulling * fa0d936dd0b5a3dee482d97a11e0ea181e8b1f3a on Jaskey: ROCKETMQ-67 -Consistent-Hash * into * 573b22c37806a21543b90707bcce6022243a62da on apache:master *.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user coveralls commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          [![Coverage Status](https://coveralls.io/builds/10246847/badge)](https://coveralls.io/builds/10246847)

          Coverage increased (+0.2%) to 31.673% when pulling *fa0d936dd0b5a3dee482d97a11e0ea181e8b1f3a on Jaskey:ROCKETMQ-67-Consistent-Hash* into *573b22c37806a21543b90707bcce6022243a62da on apache:master*.

          Show
          githubbot ASF GitHub Bot added a comment - Github user coveralls commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 [! [Coverage Status] ( https://coveralls.io/builds/10246847/badge)](https://coveralls.io/builds/10246847 ) Coverage increased (+0.2%) to 31.673% when pulling * fa0d936dd0b5a3dee482d97a11e0ea181e8b1f3a on Jaskey: ROCKETMQ-67 -Consistent-Hash * into * 573b22c37806a21543b90707bcce6022243a62da on apache:master *.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user coveralls commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          [![Coverage Status](https://coveralls.io/builds/10246847/badge)](https://coveralls.io/builds/10246847)

          Coverage increased (+0.2%) to 31.673% when pulling *fa0d936dd0b5a3dee482d97a11e0ea181e8b1f3a on Jaskey:ROCKETMQ-67-Consistent-Hash* into *573b22c37806a21543b90707bcce6022243a62da on apache:master*.

          Show
          githubbot ASF GitHub Bot added a comment - Github user coveralls commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 [! [Coverage Status] ( https://coveralls.io/builds/10246847/badge)](https://coveralls.io/builds/10246847 ) Coverage increased (+0.2%) to 31.673% when pulling * fa0d936dd0b5a3dee482d97a11e0ea181e8b1f3a on Jaskey: ROCKETMQ-67 -Consistent-Hash * into * 573b22c37806a21543b90707bcce6022243a62da on apache:master *.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user coveralls commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          [![Coverage Status](https://coveralls.io/builds/10246899/badge)](https://coveralls.io/builds/10246899)

          Coverage increased (+0.05%) to 31.571% when pulling *d96a23f50a70dd0eedef9e022fbacb567fc8923a on Jaskey:ROCKETMQ-67-Consistent-Hash* into *573b22c37806a21543b90707bcce6022243a62da on apache:master*.

          Show
          githubbot ASF GitHub Bot added a comment - Github user coveralls commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 [! [Coverage Status] ( https://coveralls.io/builds/10246899/badge)](https://coveralls.io/builds/10246899 ) Coverage increased (+0.05%) to 31.571% when pulling * d96a23f50a70dd0eedef9e022fbacb567fc8923a on Jaskey: ROCKETMQ-67 -Consistent-Hash * into * 573b22c37806a21543b90707bcce6022243a62da on apache:master *.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user coveralls commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          [![Coverage Status](https://coveralls.io/builds/10246899/badge)](https://coveralls.io/builds/10246899)

          Coverage increased (+0.05%) to 31.571% when pulling *d96a23f50a70dd0eedef9e022fbacb567fc8923a on Jaskey:ROCKETMQ-67-Consistent-Hash* into *573b22c37806a21543b90707bcce6022243a62da on apache:master*.

          Show
          githubbot ASF GitHub Bot added a comment - Github user coveralls commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 [! [Coverage Status] ( https://coveralls.io/builds/10246899/badge)](https://coveralls.io/builds/10246899 ) Coverage increased (+0.05%) to 31.571% when pulling * d96a23f50a70dd0eedef9e022fbacb567fc8923a on Jaskey: ROCKETMQ-67 -Consistent-Hash * into * 573b22c37806a21543b90707bcce6022243a62da on apache:master *.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user coveralls commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          [![Coverage Status](https://coveralls.io/builds/10246899/badge)](https://coveralls.io/builds/10246899)

          Coverage increased (+0.05%) to 31.571% when pulling *d96a23f50a70dd0eedef9e022fbacb567fc8923a on Jaskey:ROCKETMQ-67-Consistent-Hash* into *573b22c37806a21543b90707bcce6022243a62da on apache:master*.

          Show
          githubbot ASF GitHub Bot added a comment - Github user coveralls commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 [! [Coverage Status] ( https://coveralls.io/builds/10246899/badge)](https://coveralls.io/builds/10246899 ) Coverage increased (+0.05%) to 31.571% when pulling * d96a23f50a70dd0eedef9e022fbacb567fc8923a on Jaskey: ROCKETMQ-67 -Consistent-Hash * into * 573b22c37806a21543b90707bcce6022243a62da on apache:master *.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user coveralls commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          [![Coverage Status](https://coveralls.io/builds/10247299/badge)](https://coveralls.io/builds/10247299)

          Coverage increased (+0.2%) to 31.677% when pulling *17379ca81913f278020f28992eac86007bc7c191 on Jaskey:ROCKETMQ-67-Consistent-Hash* into *573b22c37806a21543b90707bcce6022243a62da on apache:master*.

          Show
          githubbot ASF GitHub Bot added a comment - Github user coveralls commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 [! [Coverage Status] ( https://coveralls.io/builds/10247299/badge)](https://coveralls.io/builds/10247299 ) Coverage increased (+0.2%) to 31.677% when pulling * 17379ca81913f278020f28992eac86007bc7c191 on Jaskey: ROCKETMQ-67 -Consistent-Hash * into * 573b22c37806a21543b90707bcce6022243a62da on apache:master *.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user coveralls commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          [![Coverage Status](https://coveralls.io/builds/10247299/badge)](https://coveralls.io/builds/10247299)

          Coverage increased (+0.2%) to 31.677% when pulling *17379ca81913f278020f28992eac86007bc7c191 on Jaskey:ROCKETMQ-67-Consistent-Hash* into *573b22c37806a21543b90707bcce6022243a62da on apache:master*.

          Show
          githubbot ASF GitHub Bot added a comment - Github user coveralls commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 [! [Coverage Status] ( https://coveralls.io/builds/10247299/badge)](https://coveralls.io/builds/10247299 ) Coverage increased (+0.2%) to 31.677% when pulling * 17379ca81913f278020f28992eac86007bc7c191 on Jaskey: ROCKETMQ-67 -Consistent-Hash * into * 573b22c37806a21543b90707bcce6022243a62da on apache:master *.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user coveralls commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          [![Coverage Status](https://coveralls.io/builds/10247299/badge)](https://coveralls.io/builds/10247299)

          Coverage increased (+0.2%) to 31.677% when pulling *17379ca81913f278020f28992eac86007bc7c191 on Jaskey:ROCKETMQ-67-Consistent-Hash* into *573b22c37806a21543b90707bcce6022243a62da on apache:master*.

          Show
          githubbot ASF GitHub Bot added a comment - Github user coveralls commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 [! [Coverage Status] ( https://coveralls.io/builds/10247299/badge)](https://coveralls.io/builds/10247299 ) Coverage increased (+0.2%) to 31.677% when pulling * 17379ca81913f278020f28992eac86007bc7c191 on Jaskey: ROCKETMQ-67 -Consistent-Hash * into * 573b22c37806a21543b90707bcce6022243a62da on apache:master *.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user Jaskey commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          @zhouxinyu @lizhanhui @shroman @vongosling
          any advice on this pr?

          Since I think consistent hash can be also applied to order message shading, the classes in this pr can be reused. I will submit a new pr for that sharding message queue selector after this pr is merged : https://issues.apache.org/jira/browse/ROCKETMQ-136?jql=project%20%3D%20ROCKETMQ

          Show
          githubbot ASF GitHub Bot added a comment - Github user Jaskey commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 @zhouxinyu @lizhanhui @shroman @vongosling any advice on this pr? Since I think consistent hash can be also applied to order message shading, the classes in this pr can be reused. I will submit a new pr for that sharding message queue selector after this pr is merged : https://issues.apache.org/jira/browse/ROCKETMQ-136?jql=project%20%3D%20ROCKETMQ
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user shroman commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          @Jaskey Can you explain more about this feature? Having a better description on JIRA would help a lot review this PR – especially for new functionalities. Since the description is very general, I have the following questions.

          What is the advantage of introducing this strategy?
          Consistent hashing could be useful if you have to move data between nodes on broker addition/removal. But since `AllocateMessageQueueStrategy` is used by consumers just to read from queues (if I get it right), on broker topology change a simple rehashing works well.
          Of course, consistent hashing will glue consumers to the queues they are already consuming from as much as possible, even if topology is changed. Is this your concern?

          Show
          githubbot ASF GitHub Bot added a comment - Github user shroman commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 @Jaskey Can you explain more about this feature? Having a better description on JIRA would help a lot review this PR – especially for new functionalities. Since the description is very general, I have the following questions. What is the advantage of introducing this strategy? Consistent hashing could be useful if you have to move data between nodes on broker addition/removal. But since `AllocateMessageQueueStrategy` is used by consumers just to read from queues (if I get it right), on broker topology change a simple rehashing works well. Of course, consistent hashing will glue consumers to the queues they are already consuming from as much as possible, even if topology is changed. Is this your concern?
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user Jaskey commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          @shroman

          This is feature to give choice to users who cares more about latency stabilization and messages duplication.

          As you know, the default `AllocateMessageQueueStrategy` is averaging strategy which allocate queue to consumer as evenly as possible. But as you states whenever queues numbers or consumer numbers changed, say a new consumer starts or an old consumer shutdown, a rehashing will be triggered and almost all consumer suffered from this and they rebalance to drop old queues and get new queue.

          This will cause
          1. message latency from producer to consumer increases at that moment
          2. messages will be duplicated significantly since the offset may not be persisted to broker and that queue is assigned to another consumer to pull messages from.

          This is especially significant when they have tens of consumer instances and scale-up or deployment is often.

          Consistent Hash strategy to allocate queue is a good choice for these users.

          Show
          githubbot ASF GitHub Bot added a comment - Github user Jaskey commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 @shroman This is feature to give choice to users who cares more about latency stabilization and messages duplication. As you know, the default `AllocateMessageQueueStrategy` is averaging strategy which allocate queue to consumer as evenly as possible. But as you states whenever queues numbers or consumer numbers changed, say a new consumer starts or an old consumer shutdown, a rehashing will be triggered and almost all consumer suffered from this and they rebalance to drop old queues and get new queue. This will cause 1. message latency from producer to consumer increases at that moment 2. messages will be duplicated significantly since the offset may not be persisted to broker and that queue is assigned to another consumer to pull messages from. This is especially significant when they have tens of consumer instances and scale-up or deployment is often. Consistent Hash strategy to allocate queue is a good choice for these users.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user shroman commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          @Jaskey This is a very good description, and now reviewers will understand well your intentions If you clearly state your intentions in JIRA, or discuss in the ml, it saves much time, and good for the record.

          Sorry, it's not a code review yet, just wanted understand your intentions.

          Show
          githubbot ASF GitHub Bot added a comment - Github user shroman commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 @Jaskey This is a very good description, and now reviewers will understand well your intentions If you clearly state your intentions in JIRA, or discuss in the ml, it saves much time, and good for the record. Sorry, it's not a code review yet, just wanted understand your intentions.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user Jaskey commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          @shroman
          The detail descriptions has been updated to JIRA. I will try described as detail as possible when I create an issue in JIRA in the future.

          Show
          githubbot ASF GitHub Bot added a comment - Github user Jaskey commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 @shroman The detail descriptions has been updated to JIRA. I will try described as detail as possible when I create an issue in JIRA in the future.
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user Jaskey commented on the issue:

          https://github.com/apache/incubator-rocketmq/pull/67

          @shroman @zhouxinyu @lizhanhui @vongosling

          I heard that consistent hash strategy will be accomplished in 4.1.x , while this pr has been open for months, can we accelerate it, please help review the implementations?

          Show
          githubbot ASF GitHub Bot added a comment - Github user Jaskey commented on the issue: https://github.com/apache/incubator-rocketmq/pull/67 @shroman @zhouxinyu @lizhanhui @vongosling I heard that consistent hash strategy will be accomplished in 4.1.x , while this pr has been open for months, can we accelerate it, please help review the implementations?
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user dhchao11 commented on a diff in the pull request:

          https://github.com/apache/incubator-rocketmq/pull/67#discussion_r116650808

          — Diff: common/src/main/java/org/apache/rocketmq/common/consistenthash/ConsistentHashRouter.java —
          @@ -0,0 +1,140 @@
          +/*
          + * Licensed to the Apache Software Foundation (ASF) under one or more
          + * contributor license agreements. See the NOTICE file distributed with
          + * this work for additional information regarding copyright ownership.
          + * The ASF licenses this file to You under the Apache License, Version 2.0
          + * (the "License"); you may not use this file except in compliance with
          + * the License. You may obtain a copy of the License at
          + *
          + * http://www.apache.org/licenses/LICENSE-2.0
          + *
          + * Unless required by applicable law or agreed to in writing, software
          + * distributed under the License is distributed on an "AS IS" BASIS,
          + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
          + * See the License for the specific language governing permissions and
          + * limitations under the License.
          + */
          +package org.apache.rocketmq.common.consistenthash;
          +
          +import java.security.MessageDigest;
          +import java.security.NoSuchAlgorithmException;
          +import java.util.Collection;
          +import java.util.Iterator;
          +import java.util.SortedMap;
          +import java.util.TreeMap;
          +
          +/**
          + * To hash Node objects to a hash ring with a certain amount of virtual node.
          + * Method routeNode will return a Node instance which the object key should be allocated to according to consistent hash algorithm
          + *
          + * @param <T>
          + */
          +public class ConsistentHashRouter<T extends Node> {
          + private final SortedMap<Long, VirtualNode<T>> ring = new TreeMap<>();
          + private final HashFunction hashFunction;
          +
          + public ConsistentHashRouter(Collection<T> pNodes, int vNodeCount)

          { + this(pNodes,vNodeCount, new MD5Hash()); + }

          +
          + /**
          + *
          + * @param pNodes collections of physical nodes
          + * @param vNodeCount amounts of virtual nodes
          + * @param hashFunction hash Function to hash Node instances
          + */
          + public ConsistentHashRouter(Collection<T> pNodes, int vNodeCount, HashFunction hashFunction) {
          + if (hashFunction == null)

          { + throw new NullPointerException("Hash Function is null"); + }

          + this.hashFunction = hashFunction;
          + if (pNodes != null) {
          + for (T pNode : pNodes)

          { + addNode(pNode, vNodeCount); + }

          + }
          + }
          +
          + /**
          + * add physic node to the hash ring with some virtual nodes
          + * @param pNode physical node needs added to hash ring
          + * @param vNodeCount the number of virtual node of the physical node. Value should be greater than or equals to 0
          + */
          + public void addNode(T pNode, int vNodeCount) {
          + if (vNodeCount < 0) throw new IllegalArgumentException("illegal virtual node counts :" + vNodeCount);
          + int existingReplicas = getExistingReplicas(pNode);
          + for (int i = 0; i < vNodeCount; i++)

          { + VirtualNode<T> vNode = new VirtualNode<>(pNode, i + existingReplicas); + ring.put(hashFunction.hash(vNode.getKey()), vNode); + }

          + }
          +
          + /**
          + * remove the physical node from the hash ring
          + * @param pNode
          + */
          + public void removeNode(T pNode) {
          + Iterator<Long> it = ring.keySet().iterator();
          + while (it.hasNext()) {
          + Long key = it.next();
          + VirtualNode<T> virtualNode = ring.get(key);
          + if (virtualNode.isVirtualNodeOf(pNode))

          { + it.remove(); + }

          + }
          + }
          +
          + /**
          + * with a specified key, route the nearest Node instance in the current hash ring
          + * @param objectKey the object key to find a nearest Node
          + * @return
          + */
          + public T routeNode(String objectKey) {
          + if (ring.isEmpty())

          { + return null; + }

          + Long hashVal = hashFunction.hash(objectKey);
          + SortedMap<Long,VirtualNode<T>> tailMap = ring.tailMap(hashVal);
          + Long nodeHashVal = !tailMap.isEmpty() ? tailMap.firstKey() : ring.firstKey();
          + return ring.get(nodeHashVal).getPhysicalNode();
          + }
          +
          +
          + public int getExistingReplicas(T pNode) {
          + int replicas = 0;
          + for (VirtualNode<T> vNode : ring.values()) {
          + if (vNode.isVirtualNodeOf(pNode))

          { + replicas++; + }

          + }
          + return replicas;
          + }
          +
          +
          + //default hash function
          + private static class MD5Hash implements HashFunction {
          + MessageDigest instance;
          +
          + public MD5Hash() {
          + try

          { + instance = MessageDigest.getInstance("MD5"); + }

          catch (NoSuchAlgorithmException e)

          { + }

          + }
          +
          + @Override
          + public long hash(String key) {
          + instance.reset();
          + instance.update(key.getBytes());
          + byte[] digest = instance.digest();
          +
          + long h = 0;
          + for (int i = 0; i < 4; i++)

          { + h <<= 8; + h |= ((int) digest[i]) & 0xFF; + }

          — End diff –

          digest is 128 bits, but the generated h only use 32 bits, other 96 bits are ignored, will it be better use ^ method

          Show
          githubbot ASF GitHub Bot added a comment - Github user dhchao11 commented on a diff in the pull request: https://github.com/apache/incubator-rocketmq/pull/67#discussion_r116650808 — Diff: common/src/main/java/org/apache/rocketmq/common/consistenthash/ConsistentHashRouter.java — @@ -0,0 +1,140 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.rocketmq.common.consistenthash; + +import java.security.MessageDigest; +import java.security.NoSuchAlgorithmException; +import java.util.Collection; +import java.util.Iterator; +import java.util.SortedMap; +import java.util.TreeMap; + +/** + * To hash Node objects to a hash ring with a certain amount of virtual node. + * Method routeNode will return a Node instance which the object key should be allocated to according to consistent hash algorithm + * + * @param <T> + */ +public class ConsistentHashRouter<T extends Node> { + private final SortedMap<Long, VirtualNode<T>> ring = new TreeMap<>(); + private final HashFunction hashFunction; + + public ConsistentHashRouter(Collection<T> pNodes, int vNodeCount) { + this(pNodes,vNodeCount, new MD5Hash()); + } + + /** + * + * @param pNodes collections of physical nodes + * @param vNodeCount amounts of virtual nodes + * @param hashFunction hash Function to hash Node instances + */ + public ConsistentHashRouter(Collection<T> pNodes, int vNodeCount, HashFunction hashFunction) { + if (hashFunction == null) { + throw new NullPointerException("Hash Function is null"); + } + this.hashFunction = hashFunction; + if (pNodes != null) { + for (T pNode : pNodes) { + addNode(pNode, vNodeCount); + } + } + } + + /** + * add physic node to the hash ring with some virtual nodes + * @param pNode physical node needs added to hash ring + * @param vNodeCount the number of virtual node of the physical node. Value should be greater than or equals to 0 + */ + public void addNode(T pNode, int vNodeCount) { + if (vNodeCount < 0) throw new IllegalArgumentException("illegal virtual node counts :" + vNodeCount); + int existingReplicas = getExistingReplicas(pNode); + for (int i = 0; i < vNodeCount; i++) { + VirtualNode<T> vNode = new VirtualNode<>(pNode, i + existingReplicas); + ring.put(hashFunction.hash(vNode.getKey()), vNode); + } + } + + /** + * remove the physical node from the hash ring + * @param pNode + */ + public void removeNode(T pNode) { + Iterator<Long> it = ring.keySet().iterator(); + while (it.hasNext()) { + Long key = it.next(); + VirtualNode<T> virtualNode = ring.get(key); + if (virtualNode.isVirtualNodeOf(pNode)) { + it.remove(); + } + } + } + + /** + * with a specified key, route the nearest Node instance in the current hash ring + * @param objectKey the object key to find a nearest Node + * @return + */ + public T routeNode(String objectKey) { + if (ring.isEmpty()) { + return null; + } + Long hashVal = hashFunction.hash(objectKey); + SortedMap<Long,VirtualNode<T>> tailMap = ring.tailMap(hashVal); + Long nodeHashVal = !tailMap.isEmpty() ? tailMap.firstKey() : ring.firstKey(); + return ring.get(nodeHashVal).getPhysicalNode(); + } + + + public int getExistingReplicas(T pNode) { + int replicas = 0; + for (VirtualNode<T> vNode : ring.values()) { + if (vNode.isVirtualNodeOf(pNode)) { + replicas++; + } + } + return replicas; + } + + + //default hash function + private static class MD5Hash implements HashFunction { + MessageDigest instance; + + public MD5Hash() { + try { + instance = MessageDigest.getInstance("MD5"); + } catch (NoSuchAlgorithmException e) { + } + } + + @Override + public long hash(String key) { + instance.reset(); + instance.update(key.getBytes()); + byte[] digest = instance.digest(); + + long h = 0; + for (int i = 0; i < 4; i++) { + h <<= 8; + h |= ((int) digest[i]) & 0xFF; + } — End diff – digest is 128 bits, but the generated h only use 32 bits, other 96 bits are ignored, will it be better use ^ method
          Hide
          jira-bot ASF subversion and git services added a comment -

          Commit adae1624d05346cd3632c778a656e4055de6bff3 in incubator-rocketmq's branch refs/heads/develop from Jaskey Lam
          [ https://git-wip-us.apache.org/repos/asf?p=incubator-rocketmq.git;h=adae162 ]

          ROCKETMQ-67 Consistent Hash allocate strategy closes apache/incubator-rocketmq#67

          Show
          jira-bot ASF subversion and git services added a comment - Commit adae1624d05346cd3632c778a656e4055de6bff3 in incubator-rocketmq's branch refs/heads/develop from Jaskey Lam [ https://git-wip-us.apache.org/repos/asf?p=incubator-rocketmq.git;h=adae162 ] ROCKETMQ-67 Consistent Hash allocate strategy closes apache/incubator-rocketmq#67
          Hide
          Jaskey Jaskey Lam added a comment -

          i wonder why this issue is marked as fixed and closed? is the related pr reviewed and merged?

          Show
          Jaskey Jaskey Lam added a comment - i wonder why this issue is marked as fixed and closed? is the related pr reviewed and merged?
          Hide
          zander dongeforever added a comment -

          Jaskey Lam yeah, it had been merged. you could check the comment upstairs

          Show
          zander dongeforever added a comment - Jaskey Lam yeah, it had been merged. you could check the comment upstairs
          Hide
          jira-bot ASF subversion and git services added a comment -

          Commit 787d128613d00a617be2f8ef943e9cfafcc07f85 in incubator-rocketmq's branch refs/heads/master from Jaskey Lam
          [ https://git-wip-us.apache.org/repos/asf?p=incubator-rocketmq.git;h=787d128 ]

          ROCKETMQ-67 Consistent Hash allocate strategy closes apache/incubator-rocketmq#67

          Show
          jira-bot ASF subversion and git services added a comment - Commit 787d128613d00a617be2f8ef943e9cfafcc07f85 in incubator-rocketmq's branch refs/heads/master from Jaskey Lam [ https://git-wip-us.apache.org/repos/asf?p=incubator-rocketmq.git;h=787d128 ] ROCKETMQ-67 Consistent Hash allocate strategy closes apache/incubator-rocketmq#67
          Hide
          githubbot ASF GitHub Bot added a comment -

          Github user asfgit closed the pull request at:

          https://github.com/apache/incubator-rocketmq/pull/67

          Show
          githubbot ASF GitHub Bot added a comment - Github user asfgit closed the pull request at: https://github.com/apache/incubator-rocketmq/pull/67

            People

            • Assignee:
              Jaskey Jaskey Lam
              Reporter:
              Jaskey Jaskey Lam
            • Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development