This is an automated email from the ASF dual-hosted git repository.
rohangarg pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/druid.git
The following commit(s) were added to refs/heads/master by this push:
new bf0886a8ab Fix hash calcuation in RendezvousHasher (#12817)
bf0886a8ab is described below
commit bf0886a8ab98ec5cf7b013b2e1811b1f6478da58
Author: Rohan Garg <[email protected]>
AuthorDate: Wed Jul 27 12:16:27 2022 +0530
Fix hash calcuation in RendezvousHasher (#12817)
---
.../druid/server/router/RendezvousHasher.java | 13 ++-
.../apache/druid/server/RendezvousHasherTest.java | 36 ++++++++
server/src/test/resources/random_uuid_100 | 100 +++++++++++++++++++++
3 files changed, 141 insertions(+), 8 deletions(-)
diff --git
a/server/src/main/java/org/apache/druid/server/router/RendezvousHasher.java
b/server/src/main/java/org/apache/druid/server/router/RendezvousHasher.java
index ffc16f14b3..3b4c121724 100644
--- a/server/src/main/java/org/apache/druid/server/router/RendezvousHasher.java
+++ b/server/src/main/java/org/apache/druid/server/router/RendezvousHasher.java
@@ -19,13 +19,10 @@
package org.apache.druid.server.router;
-import com.google.common.collect.Lists;
-import com.google.common.hash.HashCode;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import java.nio.charset.StandardCharsets;
-import java.util.List;
import java.util.Set;
/**
@@ -36,20 +33,20 @@ public class RendezvousHasher
{
private static final HashFunction HASH_FN = Hashing.murmur3_128();
- public <KeyType> String chooseNode(Set<String> nodeIds, byte[] key)
+ public String chooseNode(Set<String> nodeIds, byte[] key)
{
if (nodeIds.isEmpty()) {
return null;
}
- final HashCode keyHash = HASH_FN.hashBytes(key);
long maxHash = Long.MIN_VALUE;
String maxNode = null;
for (String nodeId : nodeIds) {
- HashCode nodeHash = HASH_FN.hashString(nodeId, StandardCharsets.UTF_8);
- List<HashCode> hashes = Lists.newArrayList(nodeHash, keyHash);
- long combinedHash = Hashing.combineOrdered(hashes).asLong();
+ long combinedHash = HASH_FN.newHasher()
+ .putString(nodeId, StandardCharsets.UTF_8)
+ .putBytes(key)
+ .hash().asLong();
if (maxNode == null) {
maxHash = combinedHash;
maxNode = nodeId;
diff --git
a/server/src/test/java/org/apache/druid/server/RendezvousHasherTest.java
b/server/src/test/java/org/apache/druid/server/RendezvousHasherTest.java
index 1d7ac1b859..5b16f52ba4 100644
--- a/server/src/test/java/org/apache/druid/server/RendezvousHasherTest.java
+++ b/server/src/test/java/org/apache/druid/server/RendezvousHasherTest.java
@@ -19,15 +19,20 @@
package org.apache.druid.server;
+import com.google.common.collect.ImmutableMap;
+import org.apache.commons.io.IOUtils;
import org.apache.druid.java.util.common.StringUtils;
import org.apache.druid.java.util.common.logger.Logger;
import org.apache.druid.server.router.RendezvousHasher;
import org.junit.Assert;
import org.junit.Test;
+import java.io.IOException;
+import java.nio.charset.StandardCharsets;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
+import java.util.Objects;
import java.util.Set;
import java.util.UUID;
@@ -246,4 +251,35 @@ public class RendezvousHasherTest
Assert.assertTrue(actualDiffRatio <= expectedDiffRatio);
}
+
+ @Test
+ public void testDistribution() throws IOException
+ {
+ String[] uuids = IOUtils.toString(
+
Objects.requireNonNull(this.getClass().getClassLoader().getResourceAsStream("random_uuid_100")),
+ StandardCharsets.UTF_8
+ ).split("\n");
+ RendezvousHasher hasher = new RendezvousHasher();
+ Set<String> nodes = new HashSet<>();
+ for (int i = 0; i < 5; i++) {
+ nodes.add("localhost:" + i);
+ }
+
+ Map<String, Integer> brokerToConnectionCount = new HashMap<>();
+ for (String uuid : uuids) {
+ brokerToConnectionCount.merge(
+ hasher.chooseNode(nodes, uuid.getBytes(StandardCharsets.UTF_8)),
+ 1,
+ Integer::sum
+ );
+ }
+ Map<String, Integer> expectedDistribution = ImmutableMap.<String,
Integer>builder()
+
.put("localhost:0", 14)
+
.put("localhost:1", 22)
+
.put("localhost:2", 24)
+
.put("localhost:3", 25)
+
.put("localhost:4", 15)
+ .build();
+ Assert.assertEquals(expectedDistribution, brokerToConnectionCount);
+ }
}
diff --git a/server/src/test/resources/random_uuid_100
b/server/src/test/resources/random_uuid_100
new file mode 100644
index 0000000000..ed85ba21da
--- /dev/null
+++ b/server/src/test/resources/random_uuid_100
@@ -0,0 +1,100 @@
+e2ad35e9-9dc5-45c5-adf5-02d09982b22e
+4cf329b9-2101-4711-992c-eeea27583426
+24fd81a0-3c31-4d0e-a567-4abf238a87d3
+7e1cb256-4488-4c19-a530-63f54e1e0853
+762bcf3e-c5d9-4c8c-9058-19901b69da21
+03ba7e04-7bf9-47dc-bf55-a790caa7e66e
+350f07d9-6759-4f86-85c9-1159c4731ec9
+ec5171df-3afc-42cc-9fdc-837ee519ddb7
+d1972680-8b7b-453f-a838-8b2d5bd5d57d
+c570b1c8-5a4d-43a2-926a-db0f2387ff15
+f002501a-5350-4edb-ba00-2e2879127117
+d5606367-a720-4003-9d51-66591a67ee9d
+e74e0204-f1fd-4d3d-b044-f096e0251906
+98b11cf5-c861-4db9-af0a-f9778b7ed61c
+8885ed89-854e-4cbd-91f2-507bb836c50d
+98b0f0e1-45ed-4d66-8bb4-2836442b11ef
+dff79392-8d04-4fa0-94d4-8900444fd5f3
+75a96139-7d71-4b33-bd2f-0a776c20b7f0
+145f5aad-3aae-426d-928b-db4fa003f3f5
+98dd2c6d-4190-4316-b946-59754430f3ec
+9389a530-3e07-4a6a-9b82-a3eb4a122c93
+77814e55-286e-4aac-bc62-110a2f411246
+a30f8d10-81f8-4970-a148-5e880e88d0f7
+2d109095-663d-44f5-a7c2-5a6a59206baa
+c52d9a18-c087-4152-af2e-bfe928218a2c
+86095849-00f5-44d0-bd78-482b274d67db
+d0026070-b058-4540-b33c-becd77219309
+632bd6db-72a3-48a3-8db4-cd8632e34559
+27e347f6-83b4-425c-9ca6-27758a2119ea
+954a9450-2581-411f-8baf-1102e322d40c
+e61227d0-fb77-4aed-88b8-3b22ae7e28c3
+00e89bac-4e44-4bb1-9a56-d30dc2254584
+5e25c0d7-f632-49b0-a629-e6de4afd4a6b
+d4ec540f-0ec2-40ee-b059-0ed292f53c45
+5e198a14-c0a4-462a-b518-905434ef070f
+89de90bc-88d3-4044-ab87-7edcca1bacb0
+56f96342-70fe-4cb1-baea-7470a8380a42
+dafbfd02-67e2-4a2c-bf64-940240bc0def
+2d810b79-8b1b-4a9e-9d02-410ea291d2d8
+233c6e49-5487-4de6-ba82-7357c6cdaec6
+7d204def-cb79-4ea9-b379-fbd2668f1af9
+11a47295-378d-4977-b79d-b0a962639a7e
+0e4c97f6-2893-4233-bf28-d072417475f9
+b9232e98-43fc-4476-b622-29861fd535bb
+3ac8b6ce-f993-4eb6-b9e4-a5e775d0e708
+8e404497-e8e2-44ef-b893-e87f0e91c64b
+185a8e1e-a2e7-45d5-86de-35f147f9d340
+676134f3-cd68-4b93-9780-1f0d22d98ffe
+b02ee859-8f35-4262-abec-0b70d33e7e84
+a38eb02a-aed7-4577-86c1-e5639e93d562
+0bb7f26c-9288-46c3-aaa6-ba644cc73aed
+4f005983-deba-433a-84ea-002d5d7dad12
+370b7d68-466c-4c48-944a-dce5e4b2e240
+817fcc49-a6cf-4d08-9b7f-6f066a698ad6
+a5291242-c79b-4f1b-abcd-ae3e8d7209eb
+3faa8e15-64db-4a9f-ad4f-41784a988dea
+5469ce15-8de1-487e-8386-cb86af49a0b2
+d1f57413-6bbd-414e-a2f4-941623baff7f
+f2c37839-ec83-4149-a0d9-fdbcfd9671ef
+f9c9ffde-b46b-4e81-addb-8e18d7078648
+a6d9472b-1b09-45a1-bd82-5a521d600db5
+899b25c8-aa42-4d7c-8d24-af52a75ab2f1
+a0cb3f37-327c-497d-8dde-4b999509a527
+8a736d30-7b6d-45bd-b3d9-919bc39fd9e5
+d33453bc-8b0a-461e-829d-955ec6b5b845
+51c377e4-251f-4ace-a0c0-aec1f3fdd73f
+e67f6a99-b655-4413-839e-d6bbe63d5b7a
+fb619dfb-ee7d-41f9-8146-439521e28b12
+2006cc9d-d502-4c63-8086-72a9a9399c68
+3d2161b3-e13f-448a-86aa-665687876520
+f84efb52-0494-47fd-bdce-508a8075d5bb
+df2f1c51-ee20-4429-8185-232d0213069e
+34b97b0e-ee13-4ced-a6d3-ddb5bce4e454
+117462d5-d4e7-4c23-bf2a-1b2955fbfb83
+28a6be15-ee4d-4e69-9649-76b0413db837
+47eff212-5ec0-40d8-b370-7be47dbd48c8
+ceda5fe6-7f48-44bb-a534-174bd7467ef1
+a9d71235-9a7b-42af-b9d8-d0d7d7f9cde0
+9cfbb914-f2b8-45a5-a9af-6d2fd1171f8c
+4d671283-9e0f-4d0f-a7e9-24754c585bfa
+9285713f-1d25-45a8-a99d-5463dbae51c6
+c2d392a0-1b0c-4001-8d9b-129ede6e7500
+2027c8a5-38e3-4aa3-86b3-b225e1d8dbaf
+dee643e0-2035-419f-b99d-369a350f0976
+42f13296-5ebd-4597-827a-ad1dae0251b4
+0edb70c0-d1b1-477d-8214-5b730ef445ed
+1c9e8cff-4ec9-40db-92d3-5712736b09c8
+89c1feaf-fa84-4bb9-be52-c195aba3f352
+6286bbc4-9bb5-4220-8868-de15e3b91de3
+93239ccd-1b91-4380-a1be-b900849096f2
+c2aa1cd6-0af9-4429-b61b-7721f7c2e3c1
+e0432eb5-e0e9-47ec-bdf7-349f18250627
+542c2246-5e47-46c3-9589-da8cac0acaa8
+f28f6715-2009-420d-9baa-2fdb919efb98
+28c44b1f-31c2-41c9-a30b-a465fb6127b6
+651f951b-b424-4d2c-a5b6-4222dc211bd4
+377a3101-8e3a-4ff2-9c42-80226b9d52be
+31fca9a0-5315-45b9-ba14-f94cc0a14506
+53c0867e-ecc8-47bb-8151-43bae783b04e
+76442794-8d01-4c56-9125-6de413057620
\ No newline at end of file
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
