This is an automated email from the ASF dual-hosted git repository. yongzao pushed a commit to branch region-multi-database in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit 177d2c60a71ab7f707697ee171c94bf1d113d03e Author: YongzaoDan <[email protected]> AuthorDate: Mon Mar 4 20:35:35 2024 +0800 stash --- .../manager/load/balancer/RegionBalancer.java | 5 + .../region/GreedyCopySetRegionGroupAllocator.java | 94 ++++++++++++++---- .../region/GreedyRegionGroupAllocator.java | 15 +-- .../balancer/region/IRegionGroupAllocator.java | 3 + .../manager/partition/PartitionManager.java | 12 +++ .../persistence/partition/PartitionInfo.java | 16 +++ .../region/AllocatorScatterWidthManualTest.java | 5 + .../GreedyCopySetRegionGroupAllocatorTest.java | 109 ++++++++++++++------- .../region/GreedyRegionGroupAllocatorTest.java | 3 + 9 files changed, 194 insertions(+), 68 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 9c91c862845..edb46050ea2 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 @@ -98,6 +98,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 @@ -117,6 +120,7 @@ public class RegionBalancer { availableDataNodeMap, freeDiskSpaceMap, allocatedRegionGroups, + databaseAllocatedRegionGroups, replicationFactor, new TConsensusGroupId( consensusGroupType, getPartitionManager().generateNextRegionGroupId())); @@ -124,6 +128,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..2f0afa0065f 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 @@ -45,30 +45,39 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator 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 final int MAX_OPTIMAL_PLAN_NUM = 100; 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) { + public DataNodeEntry( + int dataNodeId, int databaseRegionCount, int regionCount, int scatterWidth) { this.dataNodeId = dataNodeId; + this.databaseRegionCount = databaseRegionCount; this.regionCount = regionCount; this.scatterWidth = scatterWidth; this.randomWeight = RANDOM.nextInt(); @@ -79,11 +88,13 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator } 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 +107,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); @@ -122,11 +138,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 +157,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 +178,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 +201,11 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator } dataNodeEntryMap.put( dataNodeId, - new DataNodeEntry(dataNodeId, regionCounter[dataNodeId], scatterWidth)); + new DataNodeEntry( + dataNodeId, + databaseRegionCounter[dataNodeId], + regionCounter[dataNodeId], + scatterWidth)); }); dataNodeIds = dataNodeEntryMap.entrySet().stream() @@ -187,6 +217,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 +231,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 @@ -218,8 +262,11 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator } } - 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,7 +278,12 @@ 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]]); + dfs( + i, + currentReplica + 1, + currentReplicaSet, + databaseRegionSum + databaseRegionCounter[dataNodeIds[i]], + regionSum + regionCounter[dataNodeIds[i]]); if (optimalReplicaSets.size() == MAX_OPTIMAL_PLAN_NUM) { // Pruning: no needs for further searching when // the number of optimal plans reaches the limitation 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..a689c727467 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 @@ -50,6 +50,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,8 +88,7 @@ public class GreedyRegionGroupAllocator implements IRegionGroupAllocator { freeDiskSpaceMap.getOrDefault(datanodeId, 0d)))); // Sort weightList - List<TDataNodeLocation> result = - priorityMap.entrySet().stream() + return priorityMap.entrySet().stream() .sorted( comparingByValue( (o1, o2) -> @@ -99,16 +99,5 @@ public class GreedyRegionGroupAllocator implements IRegionGroupAllocator { : (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; } } 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..cf3bdc1c8d9 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. * 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..cdb3e902df5 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 @@ -691,6 +691,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. * 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..b3c7eb3c0a1 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,7 @@ import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Random; +import java.util.TreeMap; public class GreedyCopySetRegionGroupAllocatorTest { @@ -49,6 +50,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 +81,68 @@ 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( - GREEDY_ALLOCATOR.generateOptimalRegionReplicasDistribution( - AVAILABLE_DATA_NODE_MAP, - FREE_SPACE_MAP, - greedyResult, - replicationFactor, - new TConsensusGroupId(TConsensusGroupType.DataRegion, index))); - greedyCopySetResult.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)); + 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: {}", index); + 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 +153,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 +177,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 +197,26 @@ 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..5a0dbcc4837 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 @@ -62,6 +62,7 @@ public class GreedyRegionGroupAllocatorTest { availableDataNodeMap, freeSpaceMap, allocatedRegionGroups, + allocatedRegionGroups, TEST_REPLICATION_FACTOR, new TConsensusGroupId(TConsensusGroupType.DataRegion, index)); allocatedRegionGroups.add(newRegionGroup); @@ -107,6 +108,7 @@ public class GreedyRegionGroupAllocatorTest { availableDataNodeMap, freeSpaceMap, allocatedRegionGroups, + allocatedRegionGroups, TEST_REPLICATION_FACTOR, new TConsensusGroupId(TConsensusGroupType.SchemaRegion, 0)); allocatedRegionGroups.add(newRegionGroup); @@ -126,6 +128,7 @@ public class GreedyRegionGroupAllocatorTest { availableDataNodeMap, freeSpaceMap, allocatedRegionGroups, + allocatedRegionGroups, TEST_REPLICATION_FACTOR, new TConsensusGroupId(TConsensusGroupType.SchemaRegion, 1)); newRegionGroup
