You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by yo...@apache.org on 2024/03/17 06:47:12 UTC
(iotdb) 01/01: Finish but no pass test
This is an automated email from the ASF dual-hosted git repository.
yongzao pushed a commit to branch multi-db-gcr
in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit 48e3dd1e5a41ddb4f0fb66029ff9be5f13272db4
Author: YongzaoDan <53...@qq.com>
AuthorDate: Sun Mar 17 14:47:01 2024 +0800
Finish but no pass test
---
.../manager/load/balancer/RegionBalancer.java | 5 +
.../region/GreedyCopySetRegionGroupAllocator.java | 105 +++++++++++++------
.../region/GreedyRegionGroupAllocator.java | 40 +++----
.../balancer/region/IRegionGroupAllocator.java | 3 +
.../manager/partition/PartitionManager.java | 24 +++++
.../persistence/partition/PartitionInfo.java | 36 +++++++
.../region/AllocatorScatterWidthManualTest.java | 5 +
.../GreedyCopySetRegionGroupAllocatorTest.java | 115 +++++++++++++++------
.../region/GreedyRegionGroupAllocatorTest.java | 4 +
9 files changed, 251 insertions(+), 86 deletions(-)
diff --git a/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/RegionBalancer.java b/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/RegionBalancer.java
index 32f47a81812..2588edaf578 100644
--- a/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/RegionBalancer.java
+++ b/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/RegionBalancer.java
@@ -100,6 +100,9 @@ public class RegionBalancer {
int allotment = entry.getValue();
int replicationFactor =
getClusterSchemaManager().getReplicationFactor(database, consensusGroupType);
+ // Only considering the specified Database when doing allocation
+ List<TRegionReplicaSet> databaseAllocatedRegionGroups =
+ getPartitionManager().getAllReplicaSets(database, consensusGroupType);
for (int i = 0; i < allotment; i++) {
// Prepare input data
@@ -119,6 +122,7 @@ public class RegionBalancer {
availableDataNodeMap,
freeDiskSpaceMap,
allocatedRegionGroups,
+ databaseAllocatedRegionGroups,
replicationFactor,
new TConsensusGroupId(
consensusGroupType, getPartitionManager().generateNextRegionGroupId()));
@@ -126,6 +130,7 @@ public class RegionBalancer {
// Mark the new RegionGroup as allocated
allocatedRegionGroups.add(newRegionGroup);
+ databaseAllocatedRegionGroups.add(newRegionGroup);
}
}
diff --git a/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyCopySetRegionGroupAllocator.java b/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyCopySetRegionGroupAllocator.java
index 0fbb7dea071..676e7a503dd 100644
--- a/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyCopySetRegionGroupAllocator.java
+++ b/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyCopySetRegionGroupAllocator.java
@@ -39,51 +39,54 @@ import static java.util.Map.Entry.comparingByValue;
public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator {
private static final Random RANDOM = new Random();
+ private static final int GCR_MAX_OPTIMAL_PLAN_NUM = 100;
private int replicationFactor;
// Sorted available DataNodeIds
private int[] dataNodeIds;
// The number of allocated Regions in each DataNode
private int[] regionCounter;
+ // The number of allocated Regions in each DataNode within the same Database
+ private int[] databaseRegionCounter;
// The number of 2-Region combinations in current cluster
private int[][] combinationCounter;
- // First Key: the sum of Regions at the DataNodes in the allocation result is minimal
+ // First Key: the sum of Regions at the DataNodes within the same Database in the allocation
+ // result is minimal
+ int optimalDatabaseRegionSum;
+ // Second Key: the sum of Regions at the DataNodes in the allocation result is minimal
int optimalRegionSum;
- // Second Key: the sum of overlapped 2-Region combination Regions with other allocated
+ // Third Key: the sum of overlapped 2-Region combination Regions with other allocated
// RegionGroups is minimal
int optimalCombinationSum;
List<int[]> optimalReplicaSets;
- private static final int MAX_OPTIMAL_PLAN_NUM = 10;
private static class DataNodeEntry {
- private final int dataNodeId;
-
- // First key: the number of Regions in the DataNode
+ // First key: the number of Regions in the DataNode within the same Database
+ private final int databaseRegionCount;
+ // Second key: the number of Regions in the DataNode
private final int regionCount;
- // Second key: the scatter width of the DataNode
+ // Third key: the scatter width of the DataNode
private final int scatterWidth;
- // Third key: a random weight
+ // Forth key: a random weight
private final int randomWeight;
- public DataNodeEntry(int dataNodeId, int regionCount, int scatterWidth) {
- this.dataNodeId = dataNodeId;
+ public DataNodeEntry(int databaseRegionCount, int regionCount, int scatterWidth) {
+ this.databaseRegionCount = databaseRegionCount;
this.regionCount = regionCount;
this.scatterWidth = scatterWidth;
this.randomWeight = RANDOM.nextInt();
}
- public int getDataNodeId() {
- return dataNodeId;
- }
-
public int compare(DataNodeEntry e) {
- return regionCount != e.regionCount
- ? Integer.compare(regionCount, e.regionCount)
- : scatterWidth != e.scatterWidth
- ? Integer.compare(scatterWidth, e.scatterWidth)
- : Integer.compare(randomWeight, e.randomWeight);
+ return databaseRegionCount != e.databaseRegionCount
+ ? Integer.compare(databaseRegionCount, e.databaseRegionCount)
+ : regionCount != e.regionCount
+ ? Integer.compare(regionCount, e.regionCount)
+ : scatterWidth != e.scatterWidth
+ ? Integer.compare(scatterWidth, e.scatterWidth)
+ : Integer.compare(randomWeight, e.randomWeight);
}
}
@@ -96,11 +99,16 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
Map<Integer, TDataNodeConfiguration> availableDataNodeMap,
Map<Integer, Double> freeDiskSpaceMap,
List<TRegionReplicaSet> allocatedRegionGroups,
+ List<TRegionReplicaSet> databaseAllocatedRegionGroups,
int replicationFactor,
TConsensusGroupId consensusGroupId) {
try {
- prepare(replicationFactor, availableDataNodeMap, allocatedRegionGroups);
- dfs(-1, 0, new int[replicationFactor], 0);
+ prepare(
+ replicationFactor,
+ availableDataNodeMap,
+ allocatedRegionGroups,
+ databaseAllocatedRegionGroups);
+ dfs(-1, 0, new int[replicationFactor], 0, 0);
// Randomly pick one optimal plan as result
Collections.shuffle(optimalReplicaSets);
@@ -110,6 +118,7 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
for (int i = 0; i < replicationFactor; i++) {
result.addToDataNodeLocations(availableDataNodeMap.get(optimalReplicaSet[i]).getLocation());
}
+
return result;
} finally {
clear();
@@ -122,11 +131,13 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
* @param replicationFactor replication factor in the cluster
* @param availableDataNodeMap currently available DataNodes, ensure size() >= replicationFactor
* @param allocatedRegionGroups already allocated RegionGroups in the cluster
+ * @param databaseAllocatedRegionGroups already allocated RegionGroups in the same Database
*/
private void prepare(
int replicationFactor,
Map<Integer, TDataNodeConfiguration> availableDataNodeMap,
- List<TRegionReplicaSet> allocatedRegionGroups) {
+ List<TRegionReplicaSet> allocatedRegionGroups,
+ List<TRegionReplicaSet> databaseAllocatedRegionGroups) {
this.replicationFactor = replicationFactor;
// Store the maximum DataNodeId
@@ -139,9 +150,11 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
.max()
.orElse(0));
- // Compute regionCounter and combinationCounter
+ // Compute regionCounter, databaseRegionCounter and combinationCounter
regionCounter = new int[maxDataNodeId + 1];
Arrays.fill(regionCounter, 0);
+ databaseRegionCounter = new int[maxDataNodeId + 1];
+ Arrays.fill(databaseRegionCounter, 0);
combinationCounter = new int[maxDataNodeId + 1][maxDataNodeId + 1];
for (int i = 0; i <= maxDataNodeId; i++) {
Arrays.fill(combinationCounter[i], 0);
@@ -158,6 +171,12 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
}
}
}
+ for (TRegionReplicaSet regionReplicaSet : databaseAllocatedRegionGroups) {
+ List<TDataNodeLocation> dataNodeLocations = regionReplicaSet.getDataNodeLocations();
+ for (TDataNodeLocation dataNodeLocation : dataNodeLocations) {
+ databaseRegionCounter[dataNodeLocation.getDataNodeId()]++;
+ }
+ }
// Compute the DataNodeIds through sorting the DataNodeEntryMap
Map<Integer, DataNodeEntry> dataNodeEntryMap = new HashMap<>(maxDataNodeId + 1);
@@ -175,7 +194,8 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
}
dataNodeEntryMap.put(
dataNodeId,
- new DataNodeEntry(dataNodeId, regionCounter[dataNodeId], scatterWidth));
+ new DataNodeEntry(
+ databaseRegionCounter[dataNodeId], regionCounter[dataNodeId], scatterWidth));
});
dataNodeIds =
dataNodeEntryMap.entrySet().stream()
@@ -187,6 +207,7 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
.toArray();
// Reset the optimal result
+ optimalDatabaseRegionSum = Integer.MAX_VALUE;
optimalRegionSum = Integer.MAX_VALUE;
optimalCombinationSum = Integer.MAX_VALUE;
optimalReplicaSets = new ArrayList<>();
@@ -200,14 +221,27 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
* @param lastIndex last decided index in dataNodeIds
* @param currentReplica current replica index
* @param currentReplicaSet current allocation plan
+ * @param databaseRegionSum the sum of Regions at the DataNodes within the same Database in the
+ * current allocation plan
* @param regionSum the sum of Regions at the DataNodes in the current allocation plan
*/
- private void dfs(int lastIndex, int currentReplica, int[] currentReplicaSet, int regionSum) {
- if (regionSum > optimalRegionSum) {
+ private void dfs(
+ int lastIndex,
+ int currentReplica,
+ int[] currentReplicaSet,
+ int databaseRegionSum,
+ int regionSum) {
+ if (databaseRegionSum > optimalDatabaseRegionSum) {
// Pruning: no needs for further searching when the first key
// is bigger than the historical optimal result
return;
}
+ if (databaseRegionSum == optimalDatabaseRegionSum && regionSum > optimalRegionSum) {
+ // Pruning: no needs for further searching when the first key is equal to the historical
+ // optimal result
+ // and the second key is bigger than the historical optimal result
+ return;
+ }
if (currentReplica == replicationFactor) {
// A complete allocation plan is found
@@ -217,9 +251,17 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
combinationSum += combinationCounter[currentReplicaSet[i]][currentReplicaSet[j]];
}
}
+ if (databaseRegionSum == optimalDatabaseRegionSum
+ && regionSum == optimalRegionSum
+ && combinationSum > optimalCombinationSum) {
+ return;
+ }
- if (regionSum < optimalRegionSum || combinationSum < optimalCombinationSum) {
+ if (databaseRegionSum < optimalDatabaseRegionSum
+ || regionSum < optimalRegionSum
+ || combinationSum < optimalCombinationSum) {
// Reset the optimal result when a better one is found
+ optimalDatabaseRegionSum = databaseRegionSum;
optimalRegionSum = regionSum;
optimalCombinationSum = combinationSum;
optimalReplicaSets.clear();
@@ -231,8 +273,13 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
for (int i = lastIndex + 1; i < dataNodeIds.length; i++) {
// Decide the next DataNodeId in the allocation plan
currentReplicaSet[currentReplica] = dataNodeIds[i];
- dfs(i, currentReplica + 1, currentReplicaSet, regionSum + regionCounter[dataNodeIds[i]]);
- if (optimalReplicaSets.size() == MAX_OPTIMAL_PLAN_NUM) {
+ dfs(
+ i,
+ currentReplica + 1,
+ currentReplicaSet,
+ databaseRegionSum + databaseRegionCounter[dataNodeIds[i]],
+ regionSum + regionCounter[dataNodeIds[i]]);
+ if (optimalReplicaSets.size() == GCR_MAX_OPTIMAL_PLAN_NUM) {
// Pruning: no needs for further searching when
// the number of optimal plans reaches the limitation
return;
diff --git a/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyRegionGroupAllocator.java b/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyRegionGroupAllocator.java
index c01c94a4e60..65388b9e998 100644
--- a/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyRegionGroupAllocator.java
+++ b/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyRegionGroupAllocator.java
@@ -25,9 +25,6 @@ import org.apache.iotdb.common.rpc.thrift.TDataNodeLocation;
import org.apache.iotdb.common.rpc.thrift.TRegionReplicaSet;
import org.apache.iotdb.tsfile.utils.Pair;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
import java.util.HashMap;
import java.util.List;
import java.util.Map;
@@ -39,8 +36,6 @@ import static java.util.Map.Entry.comparingByValue;
/** Allocate Region Greedily */
public class GreedyRegionGroupAllocator implements IRegionGroupAllocator {
- private static final Logger LOGGER = LoggerFactory.getLogger(GreedyRegionGroupAllocator.class);
-
public GreedyRegionGroupAllocator() {
// Empty constructor
}
@@ -50,6 +45,7 @@ public class GreedyRegionGroupAllocator implements IRegionGroupAllocator {
Map<Integer, TDataNodeConfiguration> availableDataNodeMap,
Map<Integer, Double> freeDiskSpaceMap,
List<TRegionReplicaSet> allocatedRegionGroups,
+ List<TRegionReplicaSet> databaseAllocatedRegionGroups,
int replicationFactor,
TConsensusGroupId consensusGroupId) {
// Build weightList order by number of regions allocated asc
@@ -87,28 +83,16 @@ public class GreedyRegionGroupAllocator implements IRegionGroupAllocator {
freeDiskSpaceMap.getOrDefault(datanodeId, 0d))));
// Sort weightList
- List<TDataNodeLocation> result =
- priorityMap.entrySet().stream()
- .sorted(
- comparingByValue(
- (o1, o2) ->
- !Objects.equals(o1.getLeft(), o2.getLeft())
- // Compare the first key(The number of Regions) by ascending order
- ? o1.getLeft() - o2.getLeft()
- // Compare the second key(The free disk space) by descending order
- : (int) (o2.getRight() - o1.getRight())))
- .map(entry -> entry.getKey().deepCopy())
- .collect(Collectors.toList());
-
- // Record weightList
- for (TDataNodeLocation dataNodeLocation : result) {
- LOGGER.info(
- "[RegionGroupWeightList] DataNodeId: {}, RegionCount: {}, FreeDiskSpace: {}",
- dataNodeLocation.getDataNodeId(),
- priorityMap.get(dataNodeLocation).getLeft(),
- priorityMap.get(dataNodeLocation).getRight());
- }
-
- return result;
+ return priorityMap.entrySet().stream()
+ .sorted(
+ comparingByValue(
+ (o1, o2) ->
+ !Objects.equals(o1.getLeft(), o2.getLeft())
+ // Compare the first key(The number of Regions) by ascending order
+ ? o1.getLeft() - o2.getLeft()
+ // Compare the second key(The free disk space) by descending order
+ : (int) (o2.getRight() - o1.getRight())))
+ .map(entry -> entry.getKey().deepCopy())
+ .collect(Collectors.toList());
}
}
diff --git a/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/IRegionGroupAllocator.java b/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/IRegionGroupAllocator.java
index 25a61b00ea0..554168d8497 100644
--- a/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/IRegionGroupAllocator.java
+++ b/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/IRegionGroupAllocator.java
@@ -34,6 +34,8 @@ public interface IRegionGroupAllocator {
* @param availableDataNodeMap DataNodes that can be used for allocation
* @param freeDiskSpaceMap The free disk space of the DataNodes
* @param allocatedRegionGroups Allocated RegionGroups
+ * @param databaseAllocatedRegionGroups Allocated RegionGroups within the same Database with the
+ * result
* @param replicationFactor Replication factor of TRegionReplicaSet
* @param consensusGroupId TConsensusGroupId of result TRegionReplicaSet
* @return The optimal TRegionReplicaSet derived by the specified algorithm
@@ -42,6 +44,7 @@ public interface IRegionGroupAllocator {
Map<Integer, TDataNodeConfiguration> availableDataNodeMap,
Map<Integer, Double> freeDiskSpaceMap,
List<TRegionReplicaSet> allocatedRegionGroups,
+ List<TRegionReplicaSet> databaseAllocatedRegionGroups,
int replicationFactor,
TConsensusGroupId consensusGroupId);
}
diff --git a/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/partition/PartitionManager.java b/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/partition/PartitionManager.java
index c61f13043a1..613b881cd0f 100644
--- a/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/partition/PartitionManager.java
+++ b/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/partition/PartitionManager.java
@@ -710,6 +710,18 @@ public class PartitionManager {
return partitionInfo.getAllReplicaSets(database);
}
+ /**
+ * Only leader use this interface.
+ *
+ * @param database The specified Database
+ * @param type SchemaRegion or DataRegion
+ * @return Deep copy of all Regions' RegionReplicaSet with the specified Database and
+ * TConsensusGroupType
+ */
+ public List<TRegionReplicaSet> getAllReplicaSets(String database, TConsensusGroupType type) {
+ return partitionInfo.getAllReplicaSets(database, type);
+ }
+
/**
* Get all RegionGroups currently owned by the specified Database.
*
@@ -776,6 +788,18 @@ public class PartitionManager {
return partitionInfo.getRegionGroupCount(database, type);
}
+ /**
+ * Only leader use this interface.
+ *
+ * <p>Get the all RegionGroups currently in the cluster
+ *
+ * @param type SchemaRegion or DataRegion
+ * @return Map<Database, List<RegionGroupIds>>
+ */
+ public Map<String, List<TConsensusGroupId>> getAllRegionGroupIdMap(TConsensusGroupType type) {
+ return partitionInfo.getAllRegionGroupIdMap(type);
+ }
+
/**
* Only leader use this interface.
*
diff --git a/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/persistence/partition/PartitionInfo.java b/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/persistence/partition/PartitionInfo.java
index 16317152dee..2105071f933 100644
--- a/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/persistence/partition/PartitionInfo.java
+++ b/iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/persistence/partition/PartitionInfo.java
@@ -88,6 +88,7 @@ import java.util.Map;
import java.util.Objects;
import java.util.Optional;
import java.util.Set;
+import java.util.TreeMap;
import java.util.UUID;
import java.util.Vector;
import java.util.concurrent.ConcurrentHashMap;
@@ -691,6 +692,22 @@ public class PartitionInfo implements SnapshotProcessor {
}
}
+ /**
+ * Only leader use this interface.
+ *
+ * @param database The specified Database
+ * @param type SchemaRegion or DataRegion
+ * @return Deep copy of all Regions' RegionReplicaSet with the specified Database and
+ * TConsensusGroupType
+ */
+ public List<TRegionReplicaSet> getAllReplicaSets(String database, TConsensusGroupType type) {
+ if (databasePartitionTables.containsKey(database)) {
+ return databasePartitionTables.get(database).getAllReplicaSets(type);
+ } else {
+ return new ArrayList<>();
+ }
+ }
+
/**
* Get all RegionGroups currently owned by the specified Database.
*
@@ -785,6 +802,25 @@ public class PartitionInfo implements SnapshotProcessor {
return databasePartitionTables.get(database).getRegionGroupCount(type);
}
+ /**
+ * Only leader use this interface.
+ *
+ * <p>Get the all RegionGroups currently in the cluster
+ *
+ * @param type SchemaRegion or DataRegion
+ * @return Map<Database, List<RegionGroupIds>>
+ */
+ public Map<String, List<TConsensusGroupId>> getAllRegionGroupIdMap(TConsensusGroupType type) {
+ Map<String, List<TConsensusGroupId>> result = new TreeMap<>();
+ databasePartitionTables.forEach(
+ (database, databasePartitionTable) -> {
+ if (databasePartitionTable.isNotPreDeleted()) {
+ result.put(database, databasePartitionTable.getAllRegionGroupIds(type));
+ }
+ });
+ return result;
+ }
+
/**
* Only leader use this interface.
*
diff --git a/iotdb-core/confignode/src/test/java/org/apache/iotdb/confignode/manager/load/balancer/region/AllocatorScatterWidthManualTest.java b/iotdb-core/confignode/src/test/java/org/apache/iotdb/confignode/manager/load/balancer/region/AllocatorScatterWidthManualTest.java
index d211b979034..b159525268f 100644
--- a/iotdb-core/confignode/src/test/java/org/apache/iotdb/confignode/manager/load/balancer/region/AllocatorScatterWidthManualTest.java
+++ b/iotdb-core/confignode/src/test/java/org/apache/iotdb/confignode/manager/load/balancer/region/AllocatorScatterWidthManualTest.java
@@ -39,6 +39,10 @@ import java.util.List;
import java.util.Map;
import java.util.Random;
+/**
+ * Assign an allocator than run this test manually. This test will show the scatter width
+ * distribution of the specified allocator
+ */
public class AllocatorScatterWidthManualTest {
private static final Logger LOGGER =
@@ -80,6 +84,7 @@ public class AllocatorScatterWidthManualTest {
AVAILABLE_DATA_NODE_MAP,
FREE_SPACE_MAP,
allocateResult,
+ allocateResult,
DATA_REPLICATION_FACTOR,
new TConsensusGroupId(TConsensusGroupType.DataRegion, index)));
}
diff --git a/iotdb-core/confignode/src/test/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyCopySetRegionGroupAllocatorTest.java b/iotdb-core/confignode/src/test/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyCopySetRegionGroupAllocatorTest.java
index 623f8c2b2c3..95a23ab3e64 100644
--- a/iotdb-core/confignode/src/test/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyCopySetRegionGroupAllocatorTest.java
+++ b/iotdb-core/confignode/src/test/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyCopySetRegionGroupAllocatorTest.java
@@ -38,6 +38,8 @@ import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
+import java.util.TreeMap;
+import java.util.stream.Collectors;
public class GreedyCopySetRegionGroupAllocatorTest {
@@ -49,6 +51,8 @@ public class GreedyCopySetRegionGroupAllocatorTest {
private static final GreedyCopySetRegionGroupAllocator GREEDY_COPY_SET_ALLOCATOR =
new GreedyCopySetRegionGroupAllocator();
+ private static final Random RANDOM = new Random();
+ private static final int TEST_DATABASE_NUM = 3;
private static final int TEST_DATA_NODE_NUM = 21;
private static final int DATA_REGION_PER_DATA_NODE =
(int) ConfigNodeDescriptor.getInstance().getConf().getDataRegionPerDataNode();
@@ -78,45 +82,81 @@ public class GreedyCopySetRegionGroupAllocatorTest {
}
private void testRegionDistributionAndScatterWidth(int replicationFactor) {
- final int dataRegionGroupNum =
+ final int dataRegionGroupAllotment =
DATA_REGION_PER_DATA_NODE * TEST_DATA_NODE_NUM / replicationFactor;
+ final int dataRegionGroupPerDatabase = dataRegionGroupAllotment / TEST_DATABASE_NUM;
/* Allocate DataRegionGroups */
List<TRegionReplicaSet> greedyResult = new ArrayList<>();
List<TRegionReplicaSet> greedyCopySetResult = new ArrayList<>();
- for (int index = 0; index < dataRegionGroupNum; index++) {
- greedyResult.add(
+ Map<Integer, List<TRegionReplicaSet>> greedyCopySetDatabaseResult = new TreeMap<>();
+ // Map<DataNodeId, RegionGroup Count> for greedy algorithm
+ Map<Integer, Integer> greedyRegionCounter = new TreeMap<>();
+ // Map<DataNodeId, RegionGroup Count> for greedy-copy-set algorithm
+ Map<Integer, Integer> greedyCopySetRegionCounter = new TreeMap<>();
+ // Map<DatabaseId, Map<DataNodeId, RegionGroup Count>>
+ Map<Integer, Map<Integer, Integer>> greedyCopySetDatabaseRegionCounter = new TreeMap<>();
+ for (int i = 0; i < TEST_DATABASE_NUM; i++) {
+ greedyCopySetDatabaseResult.put(i, new ArrayList<>());
+ }
+ for (int index = 0; index < dataRegionGroupPerDatabase * TEST_DATABASE_NUM; index++) {
+ TRegionReplicaSet greedyRegionGroup =
GREEDY_ALLOCATOR.generateOptimalRegionReplicasDistribution(
AVAILABLE_DATA_NODE_MAP,
FREE_SPACE_MAP,
greedyResult,
+ greedyResult,
replicationFactor,
- new TConsensusGroupId(TConsensusGroupType.DataRegion, index)));
- greedyCopySetResult.add(
+ new TConsensusGroupId(TConsensusGroupType.DataRegion, index));
+ greedyResult.add(greedyRegionGroup);
+ greedyRegionGroup
+ .getDataNodeLocations()
+ .forEach(
+ dataNodeLocation ->
+ greedyRegionCounter.merge(dataNodeLocation.getDataNodeId(), 1, Integer::sum));
+ int databaseId = RANDOM.nextInt(TEST_DATABASE_NUM);
+ TRegionReplicaSet greedyCopySetRegionGroup =
GREEDY_COPY_SET_ALLOCATOR.generateOptimalRegionReplicasDistribution(
AVAILABLE_DATA_NODE_MAP,
FREE_SPACE_MAP,
greedyCopySetResult,
+ greedyCopySetDatabaseResult.get(databaseId),
replicationFactor,
- new TConsensusGroupId(TConsensusGroupType.DataRegion, index)));
+ new TConsensusGroupId(TConsensusGroupType.DataRegion, index));
+ greedyCopySetResult.add(greedyCopySetRegionGroup);
+ greedyCopySetDatabaseResult.get(databaseId).add(greedyCopySetRegionGroup);
+ greedyCopySetRegionGroup
+ .getDataNodeLocations()
+ .forEach(
+ dataNodeLocation -> {
+ greedyCopySetRegionCounter.merge(dataNodeLocation.getDataNodeId(), 1, Integer::sum);
+ greedyCopySetDatabaseRegionCounter
+ .computeIfAbsent(databaseId, empty -> new TreeMap<>())
+ .merge(dataNodeLocation.getDataNodeId(), 1, Integer::sum);
+ });
+ LOGGER.info(
+ "After allocate RegionGroup: {}, Database: {}, plan: {}",
+ index,
+ databaseId,
+ greedyCopySetRegionGroup.getDataNodeLocations().stream()
+ .map(TDataNodeLocation::getDataNodeId)
+ .collect(Collectors.toList()));
+ for (int i = 0; i < TEST_DATABASE_NUM; i++) {
+ LOGGER.info("Database {}: {}", i, greedyCopySetDatabaseRegionCounter.get(i));
+ }
+ LOGGER.info("Cluster : {}", greedyCopySetRegionCounter);
+ for (int i = 1; i <= TEST_DATA_NODE_NUM; i++) {
+ Assert.assertTrue(
+ greedyCopySetRegionCounter.getOrDefault(i, 0) <= DATA_REGION_PER_DATA_NODE);
+ }
}
/* Statistics result */
- // Map<DataNodeId, RegionGroup Count> for greedy algorithm
- Map<Integer, Integer> greedyRegionCounter = new HashMap<>();
- greedyResult.forEach(
- regionReplicaSet ->
- regionReplicaSet
- .getDataNodeLocations()
- .forEach(
- dataNodeLocation ->
- greedyRegionCounter.merge(
- dataNodeLocation.getDataNodeId(), 1, Integer::sum)));
// Map<DataNodeId, ScatterWidth> for greedy algorithm
// where a true in the bitset denotes the corresponding DataNode can help the DataNode in
// Map-Key to share the RegionGroup-leader and restore data when restarting.
// The more true in the bitset, the more safety the cluster DataNode in Map-Key is.
- Map<Integer, BitSet> greedyScatterWidth = new HashMap<>();
+ Map<Integer, BitSet> greedyScatterWidth = new TreeMap<>();
for (TRegionReplicaSet replicaSet : greedyResult) {
for (int i = 0; i < replicationFactor; i++) {
for (int j = i + 1; j < replicationFactor; j++) {
@@ -127,19 +167,8 @@ public class GreedyCopySetRegionGroupAllocatorTest {
}
}
}
-
- // Map<DataNodeId, RegionGroup Count> for greedy-copy-set algorithm
- Map<Integer, Integer> greedyCopySetRegionCounter = new HashMap<>();
- greedyCopySetResult.forEach(
- regionReplicaSet ->
- regionReplicaSet
- .getDataNodeLocations()
- .forEach(
- dataNodeLocation ->
- greedyCopySetRegionCounter.merge(
- dataNodeLocation.getDataNodeId(), 1, Integer::sum)));
// Map<DataNodeId, ScatterWidth> for greedy-copy-set algorithm, ditto
- Map<Integer, BitSet> greedyCopySetScatterWidth = new HashMap<>();
+ Map<Integer, BitSet> greedyCopySetScatterWidth = new TreeMap<>();
for (TRegionReplicaSet replicaSet : greedyCopySetResult) {
for (int i = 0; i < replicationFactor; i++) {
for (int j = i + 1; j < replicationFactor; j++) {
@@ -162,9 +191,15 @@ public class GreedyCopySetRegionGroupAllocatorTest {
int greedyCopySetScatterWidthSum = 0;
int greedyCopySetMinScatterWidth = Integer.MAX_VALUE;
int greedyCopySetMaxScatterWidth = Integer.MIN_VALUE;
+ int greedyCopySetMaxRegionCount = 0;
+ int greedyCopySetMinRegionCount = Integer.MAX_VALUE;
for (int i = 1; i <= TEST_DATA_NODE_NUM; i++) {
Assert.assertTrue(greedyRegionCounter.get(i) <= DATA_REGION_PER_DATA_NODE);
Assert.assertTrue(greedyCopySetRegionCounter.get(i) <= DATA_REGION_PER_DATA_NODE);
+ greedyCopySetMinRegionCount =
+ Math.min(greedyCopySetMinRegionCount, greedyCopySetRegionCounter.get(i));
+ greedyCopySetMaxRegionCount =
+ Math.max(greedyCopySetMaxRegionCount, greedyCopySetRegionCounter.get(i));
int scatterWidth = greedyScatterWidth.get(i).cardinality();
greedyScatterWidthSum += scatterWidth;
@@ -176,6 +211,28 @@ public class GreedyCopySetRegionGroupAllocatorTest {
greedyCopySetMinScatterWidth = Math.min(greedyCopySetMinScatterWidth, scatterWidth);
greedyCopySetMaxScatterWidth = Math.max(greedyCopySetMaxScatterWidth, scatterWidth);
}
+ // The maximal Region count - minimal Region count should be less than or equal to 1
+ Assert.assertTrue(greedyCopySetMaxRegionCount - greedyCopySetMinRegionCount <= 1);
+ for (int i = 0; i < TEST_DATABASE_NUM; i++) {
+ greedyCopySetMaxRegionCount = 0;
+ greedyCopySetMinRegionCount = Integer.MAX_VALUE;
+ if (greedyCopySetDatabaseRegionCounter.containsKey(i)) {
+ continue;
+ }
+ for (int j = 1; j <= TEST_DATA_NODE_NUM; j++) {
+ if (greedyCopySetDatabaseRegionCounter.get(i).containsKey(j)) {
+ greedyCopySetMinRegionCount =
+ Math.min(
+ greedyCopySetMinRegionCount, greedyCopySetDatabaseRegionCounter.get(i).get(j));
+ greedyCopySetMaxRegionCount =
+ Math.max(
+ greedyCopySetMaxRegionCount, greedyCopySetDatabaseRegionCounter.get(i).get(j));
+ }
+ }
+ // The maximal Region count - minimal Region count should be less than or equal to 1 for each
+ // database
+ Assert.assertTrue(greedyCopySetMaxRegionCount - greedyCopySetMinRegionCount <= 1);
+ }
LOGGER.info(
"replicationFactor: {}, Scatter width for greedy: avg={}, min={}, max={}",
diff --git a/iotdb-core/confignode/src/test/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyRegionGroupAllocatorTest.java b/iotdb-core/confignode/src/test/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyRegionGroupAllocatorTest.java
index 67aebe6ba6e..b0dd6769f2e 100644
--- a/iotdb-core/confignode/src/test/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyRegionGroupAllocatorTest.java
+++ b/iotdb-core/confignode/src/test/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyRegionGroupAllocatorTest.java
@@ -16,6 +16,7 @@
* specific language governing permissions and limitations
* under the License.
*/
+
package org.apache.iotdb.confignode.manager.load.balancer.region;
import org.apache.iotdb.common.rpc.thrift.TConsensusGroupId;
@@ -62,6 +63,7 @@ public class GreedyRegionGroupAllocatorTest {
availableDataNodeMap,
freeSpaceMap,
allocatedRegionGroups,
+ allocatedRegionGroups,
TEST_REPLICATION_FACTOR,
new TConsensusGroupId(TConsensusGroupType.DataRegion, index));
allocatedRegionGroups.add(newRegionGroup);
@@ -107,6 +109,7 @@ public class GreedyRegionGroupAllocatorTest {
availableDataNodeMap,
freeSpaceMap,
allocatedRegionGroups,
+ allocatedRegionGroups,
TEST_REPLICATION_FACTOR,
new TConsensusGroupId(TConsensusGroupType.SchemaRegion, 0));
allocatedRegionGroups.add(newRegionGroup);
@@ -126,6 +129,7 @@ public class GreedyRegionGroupAllocatorTest {
availableDataNodeMap,
freeSpaceMap,
allocatedRegionGroups,
+ allocatedRegionGroups,
TEST_REPLICATION_FACTOR,
new TConsensusGroupId(TConsensusGroupType.SchemaRegion, 1));
newRegionGroup