resource-assignment/provider/src/main/java/org/openecomp/sdnc/rm/util/LimitUtil.java

   1 /*-
   2  * ============LICENSE_START=======================================================
   3  * openECOMP : SDN-C
   4  * ================================================================================
   5  * Copyright (C) 2017 ONAP Intellectual Property. All rights
   6  *                                              reserved.
   7  * ================================================================================
   8  * Licensed under the Apache License, Version 2.0 (the "License");
   9  * you may not use this file except in compliance with the License.
  10  * You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  * ============LICENSE_END=========================================================
  20  */
  21
  22 package org.openecomp.sdnc.rm.util;
  23
  24 import java.util.ArrayList;
  25 import java.util.Date;
  26 import java.util.HashMap;
  27 import java.util.List;
  28 import java.util.Map;
  29 import java.util.Set;
  30
  31 import org.openecomp.sdnc.rm.data.AllocationItem;
  32 import org.openecomp.sdnc.rm.data.LimitAllocationItem;
  33 import org.openecomp.sdnc.rm.data.LimitAllocationRequest;
  34 import org.openecomp.sdnc.rm.data.LimitResource;
  35 import org.openecomp.sdnc.rm.data.ResourceKey;
  36 import org.openecomp.sdnc.rm.data.ResourceType;
  37 import org.slf4j.Logger;
  38 import org.slf4j.LoggerFactory;
  39
  40 public class LimitUtil {
  41
  42         private static final Logger log = LoggerFactory.getLogger(LimitUtil.class);
  43
  44         public static boolean checkLimit(LimitResource l, LimitAllocationRequest req) {
  45                 if (req.checkCount <= 0)
  46                         return true;
  47
  48                 long checkCount = req.checkCount;
  49                 long currentUsage = 0;
  50                 if (req.resourceSetId != null) {
  51                         LimitAllocationItem lai = (LimitAllocationItem) ResourceUtil.getAllocationItem(l, req.resourceSetId);
  52                         if (lai != null)
  53                                 currentUsage = lai.used;
  54                 }
  55                 if (!req.replace)
  56                         checkCount += currentUsage;
  57
  58                 long used = calculateLimitUsage(l, 0, null, null);
  59                 long wouldUse = calculateLimitUsage(l, checkCount, req.resourceUnionId, req.resourceShareGroupList);
  60
  61                 // If usage is not increasing by this request, only check the limit if
  62                 // strictCheck is true.
  63                 if (wouldUse <= used && !req.strict)
  64                         return true;
  65
  66                 return wouldUse <= req.checkLimit;
  67         }
  68
  69         private static long calculateLimitUsage(
  70                 LimitResource l,
  71                 long checkCount,
  72                 String resourceUnionId,
  73                 Set<String> resourceShareGroupList) {
  74                 if ((l.allocationItems == null || l.allocationItems.isEmpty()) &&
  75                         (resourceUnionId == null || resourceUnionId.length() == 0))
  76                         return 0;
  77
  78                 long t1 = System.currentTimeMillis();
  79                 boolean logit = false;
  80                 String rn = "Resource: " + l.resourceKey.resourceName + " - " + l.resourceKey.assetId;
  81
  82                 // In order to best utilize the resource, we need to take not the sum of all allocation items, but
  83                 // instead the maximum usage that could happen at any moment of time (given not all allocation items are active
  84                 // at the same time), also taking into account possible resource sharing.
  85                 // Thus we need to find all combinations of allocation items that can be active at the same time (allocation
  86                 // items with the same first union cannot be active at the same time), compute the usage for each (again,
  87                 // taking into account resource sharing), and take the maximum.
  88                 //
  89                 // Example:
  90                 // Let's have the following allocation items:
  91                 // ai1: sdid1, vrf1 - usage 5
  92                 // ai2: sdid2, vrf1 - usage 10
  93                 // ai3: sdid3, vrf2 - usage 15
  94                 // ai4: sdid1, vrf3 - usage 20
  95                 // ai5: sdid3, vrf1 - usage 25
  96                 // The following combinations of active allocation items are possible:
  97                 // 1) ai1, ai2, ai3
  98                 // 2) ai1, ai2, ai5
  99                 // 3) ai2, ai3, ai4
 100                 // 4) ai2, ai3, ai5
 101                 // Here is how we calculate the usage for combination 1:
 102                 // ai1 and ai2 contain the same resource union vrf1, so they share the resource - we take the max of usage,
 103                 // so we have:
 104                 // max(5, 10) + 15 = 25
 105                 // Similarly, we calculate the usage of the other combinations:
 106                 // 2) max(5, 10, 25) = 25
 107                 // 3) 10 + 15 + 20 = 45
 108                 // 4) max(10, 25) + 15 = 40
 109                 // So, the result in this case is:
 110                 // max(25, 25, 45, 40) = 45
 111                 //
 112                 // We might have a problem with this approach, if we have a lot of combinations. Assuming we have at most 2
 113                 // allocation items with the same resource union (sdid), the number of combinations would be
 114                 // 2 ^ n
 115                 // where n is the number of allocation items that have the same resource union (sdid). That would be
 116                 // the number of change orders currently in progress.
 117                 //
 118                 // Here is one optimization that we can do:
 119                 // If we have allocation items that have all resource unions the same, we don't need to generate combinations
 120                 // with each of them, we can just take the one of them with the maximum usage, as it is clear that the others
 121                 // will not lead to a bigger usage.
 122                 // For example, if we had the following allocation items:
 123                 // ai1: sdid1, vrf1 - usage 10
 124                 // ai2: sdid1, vrf1 - usage 20
 125                 // We only need to take the combinations with ai2, as they will always lead to bigger usage than the remaining
 126                 // combinations with ai1.
 127
 128                 // First, group the allocation items by the first resource union, using the LimitUsage structure
 129                 int regularChangeCount = 0;
 130                 Map<String/* resourceUnionId */, List<LimitUsage>> limitUsageMap = new HashMap<String, List<LimitUsage>>();
 131                 if (l.allocationItems != null)
 132                         for (AllocationItem ai : l.allocationItems) {
 133                                 LimitAllocationItem lai = (LimitAllocationItem) ai;
 134                                 boolean regularChange =
 135                                         addLimitUsage(limitUsageMap, lai.resourceUnionId, lai.resourceShareGroupList, lai.used);
 136                                 if (regularChange)
 137                                         regularChangeCount++;
 138                         }
 139                 if (checkCount > 0 && resourceUnionId != null) {
 140                         boolean regularChange = addLimitUsage(limitUsageMap, resourceUnionId, resourceShareGroupList, checkCount);
 141                         if (regularChange)
 142                                 regularChangeCount++;
 143                 }
 144
 145                 // Generate all the combinations, containing one LimitUsage object for each firstResourceUnion
 146                 int significantChangeCount = 0;
 147                 List<List<LimitUsage>> allCombinations = new ArrayList<List<LimitUsage>>();
 148                 for (String firstResourceUnion : limitUsageMap.keySet()) {
 149                         List<LimitUsage> limitUsageList = limitUsageMap.get(firstResourceUnion);
 150                         if (limitUsageList.size() > 1)
 151                                 significantChangeCount++;
 152                         if (allCombinations.isEmpty()) {
 153                                 for (LimitUsage limitUsage : limitUsageList) {
 154                                         List<LimitUsage> newCombination = new ArrayList<LimitUsage>();
 155                                         newCombination.add(limitUsage);
 156                                         allCombinations.add(newCombination);
 157                                 }
 158                         } else {
 159                                 if (limitUsageList.size() == 1) {
 160                                         // No new combinations are generated - just add this one to all combinations we have until now
 161                                         for (List<LimitUsage> combination : allCombinations)
 162                                                 combination.add(limitUsageList.get(0));
 163                                 } else {
 164                                         // We have to duplicate each of the current combinations for each element of limitUsageList
 165                                         List<List<LimitUsage>> newAllCombinations = new ArrayList<List<LimitUsage>>();
 166                                         for (List<LimitUsage> combination : allCombinations)
 167                                                 for (LimitUsage limitUsage : limitUsageList) {
 168                                                         List<LimitUsage> newCombination = new ArrayList<LimitUsage>(combination);
 169                                                         newCombination.add(limitUsage);
 170                                                         newAllCombinations.add(newCombination);
 171                                                 }
 172                                         allCombinations = newAllCombinations;
 173                                 }
 174                         }
 175                 }
 176
 177                 // Now, go through all combinations and calculate its usage, get the maximum
 178                 long maxUsage = 0;
 179                 for (List<LimitUsage> combination : allCombinations) {
 180                         long usage = calculateUsage(combination);
 181                         if (usage > maxUsage)
 182                                 maxUsage = usage;
 183                 }
 184
 185                 long t2 = System.currentTimeMillis();
 186                 if (logit) {
 187                         log.debug(rn + ": Calculating usage completed:");
 188                         log.debug(rn + ":     Regular changes: " + regularChangeCount);
 189                         log.debug(rn + ":     Significant changes: " + significantChangeCount);
 190                         log.debug(rn + ":     Combinations: " + allCombinations.size());
 191                         log.debug(rn + ":     Usage: " + maxUsage);
 192                         log.debug(rn + ":     Time: " + (t2 - t1));
 193                 }
 194
 195                 return maxUsage;
 196         }
 197
 198         private static boolean addLimitUsage(
 199                 Map<String/* resourceUnionId */, List<LimitUsage>> limitUsageMap,
 200                 String resourceUnionId,
 201                 Set<String> resourceShareGroupList,
 202                 long used) {
 203                 List<LimitUsage> limitUsageList = limitUsageMap.get(resourceUnionId);
 204                 if (limitUsageList == null) {
 205                         limitUsageList = new ArrayList<LimitUsage>();
 206                         limitUsageMap.put(resourceUnionId, limitUsageList);
 207                 }
 208                 // See if we already have the same shareResourceUnionSet in the list. In such case just update the usage
 209                 // to the bigger value.
 210                 LimitUsage limitUsage = null;
 211                 for (LimitUsage limitUsage1 : limitUsageList) {
 212                         if ((limitUsage1.resourceShareGroupList == null || limitUsage1.resourceShareGroupList.isEmpty()) &&
 213                                 (resourceShareGroupList == null || resourceShareGroupList.isEmpty())) {
 214                                 limitUsage = limitUsage1;
 215                                 break;
 216                         }
 217                         if (limitUsage1.resourceShareGroupList != null &&
 218                                 limitUsage1.resourceShareGroupList.equals(resourceShareGroupList)) {
 219                                 limitUsage = limitUsage1;
 220                                 break;
 221                         }
 222                 }
 223                 if (limitUsage != null) {
 224                         if (limitUsage.usage < used)
 225                                 limitUsage.usage = used;
 226                         return true;
 227                 }
 228
 229                 limitUsage = new LimitUsage();
 230                 limitUsage.resourceUnion = resourceUnionId;
 231                 limitUsage.resourceShareGroupList = resourceShareGroupList;
 232                 limitUsage.usage = used;
 233                 limitUsageList.add(limitUsage);
 234                 return false;
 235         }
 236
 237         private static class LimitUsage {
 238
 239                 @SuppressWarnings("unused")
 240                 public String resourceUnion;
 241                 public Set<String> resourceShareGroupList;
 242                 public long usage;
 243         }
 244
 245         private static boolean hasCommonSharedResource(LimitUsage limitUsage1, LimitUsage limitUsage2) {
 246                 if (limitUsage1.resourceShareGroupList == null || limitUsage1.resourceShareGroupList.isEmpty())
 247                         return false;
 248                 if (limitUsage2.resourceShareGroupList == null || limitUsage2.resourceShareGroupList.isEmpty())
 249                         return false;
 250
 251                 for (String resourceUnion : limitUsage1.resourceShareGroupList)
 252                         if (limitUsage2.resourceShareGroupList.contains(resourceUnion))
 253                                 return true;
 254
 255                 return false;
 256         }
 257
 258         private static long calculateUsage(List<LimitUsage> combination) {
 259                 // All LimitUsage objects that have a common value in their sharedResourceUnionSet reuse the resource, so
 260                 // split the combination in sets that have common value. Then the usage of each set will be the maximum of
 261                 // the usages of the LimitUsage objects in the set. The usage of the combination will be the sum of the usages
 262                 // of all sets.
 263                 List<List<LimitUsage>> sharedSets = new ArrayList<List<LimitUsage>>();
 264                 for (LimitUsage limitUsage : combination) {
 265                         // See if we can put limitUsage in any of the existing sets - is it has a common resource union with
 266                         // any of the LimitUsage objects in a set.
 267                         boolean found = false;
 268                         for (List<LimitUsage> sharedSet : sharedSets) {
 269                                 for (LimitUsage limitUsage1 : sharedSet) {
 270                                         if (hasCommonSharedResource(limitUsage, limitUsage1)) {
 271                                                 found = true;
 272                                                 break;
 273                                         }
 274                                 }
 275                                 if (found) {
 276                                         sharedSet.add(limitUsage);
 277                                         break;
 278                                 }
 279                         }
 280                         if (!found) {
 281                                 // Start a new set
 282                                 List<LimitUsage> newSharedSet = new ArrayList<LimitUsage>();
 283                                 newSharedSet.add(limitUsage);
 284                                 sharedSets.add(newSharedSet);
 285                         }
 286                 }
 287
 288                 long sum = 0;
 289                 for (List<LimitUsage> sharedSet : sharedSets) {
 290                         float max = 0;
 291                         for (LimitUsage limitUsage : sharedSet)
 292                                 if (max < limitUsage.usage)
 293                                         max = limitUsage.usage;
 294                         sum += max;
 295                 }
 296
 297                 return sum;
 298         }
 299
 300         public static long allocateLimit(LimitResource l, LimitAllocationRequest req, String applicationId) {
 301                 if (req.allocateCount <= 0)
 302                         return 0;
 303                 long uu = l.used;
 304
 305                 LimitAllocationItem lai = (LimitAllocationItem) ResourceUtil.getAllocationItem(l, req.resourceSetId);
 306                 if (lai == null) {
 307                         lai = new LimitAllocationItem();
 308                         lai.resourceType = ResourceType.Limit;
 309                         lai.resourceKey = new ResourceKey();
 310                         lai.resourceKey.assetId = req.assetId;
 311                         lai.resourceKey.resourceName = req.resourceName;
 312                         lai.applicationId = applicationId;
 313                         lai.resourceSetId = req.resourceSetId;
 314                         lai.resourceUnionId = req.resourceUnionId;
 315                         lai.resourceShareGroupList = req.resourceShareGroupList;
 316                         lai.used = req.allocateCount;
 317
 318                         if (l.allocationItems == null)
 319                                 l.allocationItems = new ArrayList<AllocationItem>();
 320                         l.allocationItems.add(lai);
 321                 } else
 322                         lai.used = req.replace ? req.allocateCount : lai.used + req.allocateCount;
 323
 324                 lai.allocationTime = new Date();
 325
 326                 recalculate(l);
 327
 328                 return l.used - uu;
 329         }
 330
 331         public static void recalculate(LimitResource l) {
 332                 l.used = calculateLimitUsage(l, 0, null, null);
 333         }
 334 }