You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hbase.apache.org by zh...@apache.org on 2021/09/28 15:43:03 UTC
[hbase] branch branch-2 updated: HBASE-26293 Use reservoir sampling
when selecting bootstrap nodes (#3702)
This is an automated email from the ASF dual-hosted git repository.
zhangduo pushed a commit to branch branch-2
in repository https://gitbox.apache.org/repos/asf/hbase.git
The following commit(s) were added to refs/heads/branch-2 by this push:
new 08a2efd HBASE-26293 Use reservoir sampling when selecting bootstrap nodes (#3702)
08a2efd is described below
commit 08a2efde167130954dded2c679fc0a76995ce84e
Author: Duo Zhang <zh...@apache.org>
AuthorDate: Tue Sep 28 23:27:47 2021 +0800
HBASE-26293 Use reservoir sampling when selecting bootstrap nodes (#3702)
Signed-off-by: Xiaolin Ha <ha...@apache.org>
---
.../apache/hadoop/hbase/util/ReservoirSample.java | 72 +++++++++++++++++
.../hadoop/hbase/util/TestReservoirSample.java | 92 ++++++++++++++++++++++
.../org/apache/hadoop/hbase/master/HMaster.java | 6 +-
.../hadoop/hbase/regionserver/HRegionServer.java | 5 +-
.../hadoop/hbase/regionserver/RSRpcServices.java | 9 ++-
5 files changed, 175 insertions(+), 9 deletions(-)
diff --git a/hbase-common/src/main/java/org/apache/hadoop/hbase/util/ReservoirSample.java b/hbase-common/src/main/java/org/apache/hadoop/hbase/util/ReservoirSample.java
new file mode 100644
index 0000000..2cc502e
--- /dev/null
+++ b/hbase-common/src/main/java/org/apache/hadoop/hbase/util/ReservoirSample.java
@@ -0,0 +1,72 @@
+/**
+ * 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.hadoop.hbase.util;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.stream.Stream;
+import org.apache.yetus.audience.InterfaceAudience;
+
+import org.apache.hbase.thirdparty.com.google.common.base.Preconditions;
+
+/**
+ * The simple version of reservoir sampling implementation. It is enough for the usage in HBase.
+ * <p/>
+ * See https://en.wikipedia.org/wiki/Reservoir_sampling.
+ */
+@InterfaceAudience.Private
+public class ReservoirSample<T> {
+
+ private final List<T> r;
+
+ private final int k;
+
+ private int n;
+
+ public ReservoirSample(int k) {
+ Preconditions.checkArgument(k > 0, "negative sampling number(%d) is not allowed");
+ r = new ArrayList<>(k);
+ this.k = k;
+ }
+
+ public void add(T t) {
+ if (n < k) {
+ r.add(t);
+ } else {
+ int j = ThreadLocalRandom.current().nextInt(n + 1);
+ if (j < k) {
+ r.set(j, t);
+ }
+ }
+ n++;
+ }
+
+ public void add(Iterator<T> iter) {
+ iter.forEachRemaining(this::add);
+ }
+
+ public void add(Stream<T> s) {
+ s.forEachOrdered(this::add);
+ }
+
+ public List<T> getSamplingResult() {
+ return r;
+ }
+}
diff --git a/hbase-common/src/test/java/org/apache/hadoop/hbase/util/TestReservoirSample.java b/hbase-common/src/test/java/org/apache/hadoop/hbase/util/TestReservoirSample.java
new file mode 100644
index 0000000..a4d23d4
--- /dev/null
+++ b/hbase-common/src/test/java/org/apache/hadoop/hbase/util/TestReservoirSample.java
@@ -0,0 +1,92 @@
+/**
+ * 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.hadoop.hbase.util;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import java.util.stream.IntStream;
+import org.apache.hadoop.hbase.HBaseClassTestRule;
+import org.apache.hadoop.hbase.testclassification.MiscTests;
+import org.apache.hadoop.hbase.testclassification.SmallTests;
+import org.junit.ClassRule;
+import org.junit.Test;
+import org.junit.experimental.categories.Category;
+
+@Category({ MiscTests.class, SmallTests.class })
+public class TestReservoirSample {
+
+ @ClassRule
+ public static final HBaseClassTestRule CLASS_RULE =
+ HBaseClassTestRule.forClass(TestReservoirSample.class);
+
+ @Test
+ public void test() {
+ int round = 100000;
+ int containsOne = 0;
+ for (int i = 0; i < round; i++) {
+ ReservoirSample<Integer> rs = new ReservoirSample<>(10);
+ for (int j = 0; j < 100; j++) {
+ rs.add(j);
+ if (j < 10) {
+ assertEquals(j + 1, rs.getSamplingResult().size());
+ } else {
+ assertEquals(10, rs.getSamplingResult().size());
+ }
+ }
+ if (rs.getSamplingResult().contains(1)) {
+ containsOne++;
+ }
+ }
+ // we assume a 5% error rate
+ assertTrue(containsOne > round / 10 * 0.95);
+ assertTrue(containsOne < round / 10 * 1.05);
+ }
+
+ @Test
+ public void testIterator() {
+ int round = 100000;
+ int containsOne = 0;
+ for (int i = 0; i < round; i++) {
+ ReservoirSample<Integer> rs = new ReservoirSample<>(10);
+ rs.add(IntStream.range(0, 100).mapToObj(Integer::valueOf).iterator());
+ if (rs.getSamplingResult().contains(1)) {
+ containsOne++;
+ }
+ }
+ // we assume a 5% error rate
+ assertTrue(containsOne > round / 10 * 0.95);
+ assertTrue(containsOne < round / 10 * 1.05);
+ }
+
+ @Test
+ public void testStream() {
+ int round = 100000;
+ int containsOne = 0;
+ for (int i = 0; i < round; i++) {
+ ReservoirSample<Integer> rs = new ReservoirSample<>(10);
+ rs.add(IntStream.range(0, 100).mapToObj(Integer::valueOf));
+ if (rs.getSamplingResult().contains(1)) {
+ containsOne++;
+ }
+ }
+ // we assume a 5% error rate
+ assertTrue(containsOne > round / 10 * 0.95);
+ assertTrue(containsOne < round / 10 * 1.05);
+ }
+}
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/HMaster.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/HMaster.java
index 866e3fd..9c9c8d8 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/HMaster.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/HMaster.java
@@ -61,7 +61,6 @@ import org.apache.hadoop.fs.Path;
import org.apache.hadoop.hbase.Cell;
import org.apache.hadoop.hbase.CellBuilderFactory;
import org.apache.hadoop.hbase.CellBuilderType;
-import org.apache.hadoop.hbase.client.BalanceRequest;
import org.apache.hadoop.hbase.ClusterId;
import org.apache.hadoop.hbase.ClusterMetrics;
import org.apache.hadoop.hbase.ClusterMetrics.Option;
@@ -84,6 +83,7 @@ import org.apache.hadoop.hbase.TableName;
import org.apache.hadoop.hbase.TableNotDisabledException;
import org.apache.hadoop.hbase.TableNotFoundException;
import org.apache.hadoop.hbase.UnknownRegionException;
+import org.apache.hadoop.hbase.client.BalanceRequest;
import org.apache.hadoop.hbase.client.BalanceResponse;
import org.apache.hadoop.hbase.client.ColumnFamilyDescriptor;
import org.apache.hadoop.hbase.client.CompactionState;
@@ -2733,8 +2733,8 @@ public class HMaster extends HRegionServer implements MasterServices {
}
@Override
- public Collection<ServerName> getRegionServers() {
- return regionServerTracker.getRegionServers();
+ public Iterator<ServerName> getRegionServers() {
+ return regionServerTracker.getRegionServers().iterator();
}
/**
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java
index cac23d6..1221374 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java
@@ -37,6 +37,7 @@ import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
+import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
@@ -3983,8 +3984,8 @@ public class HRegionServer extends Thread implements
return masterAddressTracker.getBackupMasters();
}
- public Collection<ServerName> getRegionServers() {
- return regionServerAddressTracker.getRegionServers();
+ public Iterator<ServerName> getRegionServers() {
+ return regionServerAddressTracker.getRegionServers().iterator();
}
public MetaRegionLocationCache getMetaRegionLocationCache() {
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/RSRpcServices.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/RSRpcServices.java
index 7171134..18a8c52 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/RSRpcServices.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/RSRpcServices.java
@@ -41,7 +41,6 @@ import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
-import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicLong;
@@ -144,6 +143,7 @@ import org.apache.hadoop.hbase.util.Bytes;
import org.apache.hadoop.hbase.util.DNS;
import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
import org.apache.hadoop.hbase.util.Pair;
+import org.apache.hadoop.hbase.util.ReservoirSample;
import org.apache.hadoop.hbase.util.ServerRegionReplicaUtil;
import org.apache.hadoop.hbase.wal.WAL;
import org.apache.hadoop.hbase.wal.WALEdit;
@@ -4073,12 +4073,13 @@ public class RSRpcServices implements HBaseRPCErrorHandler,
@Override
public final GetBootstrapNodesResponse getBootstrapNodes(RpcController controller,
GetBootstrapNodesRequest request) throws ServiceException {
- List<ServerName> bootstrapNodes = new ArrayList<>(regionServer.getRegionServers());
- Collections.shuffle(bootstrapNodes, ThreadLocalRandom.current());
int maxNodeCount = regionServer.getConfiguration().getInt(CLIENT_BOOTSTRAP_NODE_LIMIT,
DEFAULT_CLIENT_BOOTSTRAP_NODE_LIMIT);
+ ReservoirSample<ServerName> sample = new ReservoirSample<>(maxNodeCount);
+ sample.add(regionServer.getRegionServers());
+
GetBootstrapNodesResponse.Builder builder = GetBootstrapNodesResponse.newBuilder();
- bootstrapNodes.stream().limit(maxNodeCount).map(ProtobufUtil::toServerName)
+ sample.getSamplingResult().stream().map(ProtobufUtil::toServerName)
.forEach(builder::addServerName);
return builder.build();
}