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 2023/12/24 07:19:31 UTC
(iotdb) branch optimize-greedy-copyset created (now e456b265cba)
This is an automated email from the ASF dual-hosted git repository.
yongzao pushed a change to branch optimize-greedy-copyset
in repository https://gitbox.apache.org/repos/asf/iotdb.git
at e456b265cba new algorithm
This branch includes the following new commits:
new e456b265cba new algorithm
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
(iotdb) 01/01: new algorithm
Posted by yo...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
yongzao pushed a commit to branch optimize-greedy-copyset
in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit e456b265cbac1af55bde022f11e74e63604d4e75
Author: YongzaoDan <53...@qq.com>
AuthorDate: Sun Dec 24 15:19:21 2023 +0800
new algorithm
---
...RegionGroupAllocator.java => DfsAllocator.java} | 9 +-
.../region/GreedyCopySetRegionGroupAllocator.java | 181 ++++++++++++++-------
2 files changed, 122 insertions(+), 68 deletions(-)
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/DfsAllocator.java
similarity index 97%
copy from iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/GreedyCopySetRegionGroupAllocator.java
copy to iotdb-core/confignode/src/main/java/org/apache/iotdb/confignode/manager/load/balancer/region/DfsAllocator.java
index f87e565653d..2566fa032ee 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/DfsAllocator.java
@@ -32,8 +32,7 @@ import java.util.HashMap;
import java.util.List;
import java.util.Map;
-/** Allocate Region through Greedy and CopySet Algorithm. */
-public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator {
+public class DfsAllocator implements IRegionGroupAllocator {
int replicationFactor;
// RegionGroup allocation BitSet
@@ -49,7 +48,7 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
int optimalIntersectionSum;
List<int[]> optimalReplicaSets;
- public GreedyCopySetRegionGroupAllocator() {
+ public DfsAllocator() {
// Empty constructor
}
@@ -149,7 +148,7 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
int[] currentReplicaSet,
int regionSum,
int intersectionSum) {
- if (regionSum > optimalRegionSum || intersectionSum > optimalRegionSum) {
+ if (regionSum > optimalRegionSum || intersectionSum > optimalIntersectionSum) {
// Pruning: no needs for further searching when either the first key or the second key
// is bigger than the historical optimal result
return;
@@ -157,7 +156,7 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
if (currentReplica == replicationFactor) {
// A complete allocation plan is found
- if (regionSum < optimalRegionSum || intersectionSum < optimalRegionSum) {
+ if (regionSum < optimalRegionSum || intersectionSum < optimalIntersectionSum) {
// Reset the optimal result when a better one is found
optimalRegionSum = regionSum;
optimalIntersectionSum = intersectionSum;
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 f87e565653d..5c3fbad554f 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
@@ -26,28 +26,66 @@ import org.apache.iotdb.common.rpc.thrift.TRegionReplicaSet;
import java.util.ArrayList;
import java.util.Arrays;
-import java.util.BitSet;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
+import java.util.Random;
+import java.util.stream.Collectors;
+
+import static java.util.Map.Entry.comparingByValue;
/** Allocate Region through Greedy and CopySet Algorithm. */
public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator {
- int replicationFactor;
- // RegionGroup allocation BitSet
- private List<BitSet> allocatedBitSets;
- // Map<DataNodeId, RegionGroup count>
- private Map<Integer, Integer> regionCounter;
- // Available DataNodeIds
- private Integer[] dataNodeIds;
+ private int replicationFactor;
+ // Sorted available DataNodeIds
+ private int[] dataNodeIds;
+ // The number of allocated Regions in each DataNode
+ private int[] regionCounter;
+ // 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
int optimalRegionSum;
- // Second Key: the sum of intersected Regions with other allocated RegionGroups is minimal
- int optimalIntersectionSum;
+ // Second 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 final Random random = new Random();
+
+ private class DataNodeEntry {
+
+ private final int dataNodeId;
+
+ // First key: the number of Regions in the DataNode
+ private final int regionCount;
+ // Second key: the scatter width of the DataNode
+ private final int scatterWidth;
+ // Third key: a random weight
+ private final int randomWeight;
+
+ public DataNodeEntry(int dataNodeId, int regionCount, int scatterWidth) {
+ this.dataNodeId = dataNodeId;
+ 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);
+ }
+ }
public GreedyCopySetRegionGroupAllocator() {
// Empty constructor
@@ -62,7 +100,7 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
TConsensusGroupId consensusGroupId) {
try {
prepare(replicationFactor, availableDataNodeMap, allocatedRegionGroups);
- dfs(-1, 0, new int[replicationFactor], 0, 0);
+ dfs(-1, 0, new int[replicationFactor], 0);
// Randomly pick one optimal plan as result
Collections.shuffle(optimalReplicaSets);
@@ -91,43 +129,66 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
List<TRegionReplicaSet> allocatedRegionGroups) {
this.replicationFactor = replicationFactor;
- int maxDataNodeId = availableDataNodeMap.keySet().stream().max(Integer::compareTo).orElse(0);
- for (TRegionReplicaSet regionReplicaSet : allocatedRegionGroups) {
- for (TDataNodeLocation dataNodeLocation : regionReplicaSet.getDataNodeLocations()) {
- // Store the maximum DataNodeId in this algorithm loop
- maxDataNodeId = Math.max(maxDataNodeId, dataNodeLocation.getDataNodeId());
- }
+ // Store the maximum DataNodeId
+ int maxDataNodeId =
+ Math.max(
+ availableDataNodeMap.keySet().stream().max(Integer::compareTo).orElse(0),
+ allocatedRegionGroups.stream()
+ .flatMap(regionGroup -> regionGroup.getDataNodeLocations().stream())
+ .mapToInt(TDataNodeLocation::getDataNodeId)
+ .max()
+ .orElse(0));
+
+ // Compute regionCounter and combinationCounter
+ regionCounter = new int[maxDataNodeId + 1];
+ Arrays.fill(regionCounter, 0);
+ combinationCounter = new int[maxDataNodeId + 1][maxDataNodeId + 1];
+ for (int i = 0; i <= maxDataNodeId; i++) {
+ Arrays.fill(combinationCounter[i], 0);
}
-
- // Convert the allocatedRegionGroups into allocatedBitSets,
- // where a true in BitSet corresponding to a DataNodeId in the RegionGroup
- allocatedBitSets = new ArrayList<>(allocatedRegionGroups.size());
for (TRegionReplicaSet regionReplicaSet : allocatedRegionGroups) {
- BitSet bitSet = new BitSet(maxDataNodeId + 1);
- for (TDataNodeLocation dataNodeLocation : regionReplicaSet.getDataNodeLocations()) {
- bitSet.set(dataNodeLocation.getDataNodeId());
+ List<TDataNodeLocation> dataNodeLocations = regionReplicaSet.getDataNodeLocations();
+ for (int i = 0; i < dataNodeLocations.size(); i++) {
+ regionCounter[dataNodeLocations.get(i).getDataNodeId()]++;
+ for (int j = i + 1; j < dataNodeLocations.size(); j++) {
+ combinationCounter[dataNodeLocations.get(i).getDataNodeId()][
+ dataNodeLocations.get(j).getDataNodeId()]++;
+ combinationCounter[dataNodeLocations.get(j).getDataNodeId()][
+ dataNodeLocations.get(i).getDataNodeId()]++;
+ }
}
- allocatedBitSets.add(bitSet);
}
- // Count the number of Regions in each DataNode
- regionCounter = new HashMap<>(maxDataNodeId + 1);
- for (int i = 0; i <= maxDataNodeId; i++) {
- regionCounter.put(i, 0);
- }
- allocatedRegionGroups.forEach(
- regionGroup ->
- regionGroup
- .getDataNodeLocations()
- .forEach(
- dataNodeLocation ->
- regionCounter.merge(dataNodeLocation.getDataNodeId(), 1, Integer::sum)));
+ // Compute the DataNodeIds through sorting the DataNodeEntryMap
+ Map<Integer, DataNodeEntry> dataNodeEntryMap = new HashMap<>(maxDataNodeId + 1);
+ availableDataNodeMap
+ .keySet()
+ .forEach(
+ dataNodeId -> {
+ int scatterWidth = 0;
+ for (int j = 0; j <= maxDataNodeId; j++) {
+ if (combinationCounter[dataNodeId][j] > 0) {
+ // Each exists 2-Region combination extends
+ // the scatter width of current DataNode by 1
+ scatterWidth++;
+ }
+ }
+ dataNodeEntryMap.put(
+ dataNodeId,
+ new DataNodeEntry(dataNodeId, regionCounter[dataNodeId], scatterWidth));
+ });
+ dataNodeIds =
+ dataNodeEntryMap.entrySet().stream()
+ .sorted(comparingByValue(DataNodeEntry::compare))
+ .map(Map.Entry::getKey)
+ .collect(Collectors.toList())
+ .stream()
+ .mapToInt(Integer::intValue)
+ .toArray();
// Reset the optimal result
- dataNodeIds = new Integer[availableDataNodeMap.size()];
- availableDataNodeMap.keySet().toArray(dataNodeIds);
optimalRegionSum = Integer.MAX_VALUE;
- optimalIntersectionSum = Integer.MAX_VALUE;
+ optimalCombinationSum = Integer.MAX_VALUE;
optimalReplicaSets = new ArrayList<>();
}
@@ -140,27 +201,27 @@ public class GreedyCopySetRegionGroupAllocator implements IRegionGroupAllocator
* @param currentReplica current replica index
* @param currentReplicaSet current allocation plan
* @param regionSum the sum of Regions at the DataNodes in the current allocation plan
- * @param intersectionSum the sum of intersected Regions with other allocated RegionGroups in
- * current allocation plan
*/
- private void dfs(
- int lastIndex,
- int currentReplica,
- int[] currentReplicaSet,
- int regionSum,
- int intersectionSum) {
- if (regionSum > optimalRegionSum || intersectionSum > optimalRegionSum) {
- // Pruning: no needs for further searching when either the first key or the second key
+ private void dfs(int lastIndex, int currentReplica, int[] currentReplicaSet, int regionSum) {
+ if (regionSum > optimalRegionSum) {
+ // Pruning: no needs for further searching when the first key
// is bigger than the historical optimal result
return;
}
if (currentReplica == replicationFactor) {
// A complete allocation plan is found
- if (regionSum < optimalRegionSum || intersectionSum < optimalRegionSum) {
+ int combinationSum = 0;
+ for (int i = 0; i < replicationFactor; i++) {
+ for (int j = i + 1; j < replicationFactor; j++) {
+ combinationSum += combinationCounter[currentReplicaSet[i]][currentReplicaSet[j]];
+ }
+ }
+
+ if (regionSum < optimalRegionSum || combinationSum < optimalCombinationSum) {
// Reset the optimal result when a better one is found
optimalRegionSum = regionSum;
- optimalIntersectionSum = intersectionSum;
+ optimalCombinationSum = combinationSum;
optimalReplicaSets.clear();
}
optimalReplicaSets.add(Arrays.copyOf(currentReplicaSet, replicationFactor));
@@ -170,22 +231,16 @@ 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];
- int intersectionDelta = 0;
- for (BitSet bitSet : allocatedBitSets) {
- intersectionDelta += bitSet.get(dataNodeIds[i]) ? 1 : 0;
+ dfs(i, currentReplica + 1, currentReplicaSet, 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
+ return;
}
- dfs(
- i,
- currentReplica + 1,
- currentReplicaSet,
- regionSum + regionCounter.get(dataNodeIds[i]),
- intersectionSum + intersectionDelta);
}
}
void clear() {
- allocatedBitSets.clear();
- regionCounter.clear();
optimalReplicaSets.clear();
}
}