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:32 UTC

(iotdb) 01/01: new algorithm

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();
   }
 }