You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@rocketmq.apache.org by Jaskey <gi...@git.apache.org> on 2017/02/20 07:14:47 UTC
[GitHub] incubator-rocketmq pull request #67: [ROCKETMQ-67] Consistent Hash allocate ...
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 <li...@gmail.com>
Date: 2017-02-20T07:13:09Z
ROCKETMQ-67 : Consistent Hash allocate strategy
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq pull request #67: [ROCKETMQ-67] Consistent Hash allocate ...
Posted by zhouxinyu <gi...@git.apache.org>.
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.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq issue #67: [ROCKETMQ-67] Consistent Hash allocate strateg...
Posted by Jaskey <gi...@git.apache.org>.
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
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq issue #67: [ROCKETMQ-67] Consistent Hash allocate strateg...
Posted by coveralls <gi...@git.apache.org>.
Github user coveralls commented on the issue:
https://github.com/apache/incubator-rocketmq/pull/67
[](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**.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq issue #67: [ROCKETMQ-67] Consistent Hash allocate strateg...
Posted by Jaskey <gi...@git.apache.org>.
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?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq issue #67: [ROCKETMQ-67] Consistent Hash allocate strateg...
Posted by Jaskey <gi...@git.apache.org>.
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.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq issue #67: [ROCKETMQ-67] Consistent Hash allocate strateg...
Posted by Jaskey <gi...@git.apache.org>.
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.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq issue #67: [ROCKETMQ-67] Consistent Hash allocate strateg...
Posted by shroman <gi...@git.apache.org>.
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?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq issue #67: [ROCKETMQ-67] Consistent Hash allocate strateg...
Posted by coveralls <gi...@git.apache.org>.
Github user coveralls commented on the issue:
https://github.com/apache/incubator-rocketmq/pull/67
[](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**.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq pull request #67: [ROCKETMQ-67] Consistent Hash allocate ...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/incubator-rocketmq/pull/67
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq pull request #67: [ROCKETMQ-67] Consistent Hash allocate ...
Posted by dhchao11 <gi...@git.apache.org>.
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
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq pull request #67: [ROCKETMQ-67] Consistent Hash allocate ...
Posted by Jaskey <gi...@git.apache.org>.
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
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq issue #67: [ROCKETMQ-67] Consistent Hash allocate strateg...
Posted by coveralls <gi...@git.apache.org>.
Github user coveralls commented on the issue:
https://github.com/apache/incubator-rocketmq/pull/67
[](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**.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq issue #67: [ROCKETMQ-67] Consistent Hash allocate strateg...
Posted by coveralls <gi...@git.apache.org>.
Github user coveralls commented on the issue:
https://github.com/apache/incubator-rocketmq/pull/67
[](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**.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq issue #67: [ROCKETMQ-67] Consistent Hash allocate strateg...
Posted by shroman <gi...@git.apache.org>.
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.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-rocketmq issue #67: [ROCKETMQ-67] Consistent Hash allocate strateg...
Posted by coveralls <gi...@git.apache.org>.
Github user coveralls commented on the issue:
https://github.com/apache/incubator-rocketmq/pull/67
[](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**.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---