1 /** 2 * Licensed to the Apache Software Foundation (ASF) under one 3 * or more contributor license agreements. See the NOTICE file 4 * distributed with this work for additional information 5 * regarding copyright ownership. The ASF licenses this file 6 * to you under the Apache License, Version 2.0 (the 7 * "License"); you may not use this file except in compliance 8 * with the License. You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 */ 18 package org.apache.hadoop.yarn.util.resource; 19 20 import org.apache.hadoop.classification.InterfaceAudience.Private; 21 import org.apache.hadoop.classification.InterfaceStability.Unstable; 22 import org.apache.hadoop.yarn.api.records.Resource; 23 24 /** 25 * A {@link ResourceCalculator} which uses the concept of 26 * <em>dominant resource</em> to compare multi-dimensional resources. 27 * 28 * Essentially the idea is that the in a multi-resource environment, 29 * the resource allocation should be determined by the dominant share 30 * of an entity (user or queue), which is the maximum share that the 31 * entity has been allocated of any resource. 32 * 33 * In a nutshell, it seeks to maximize the minimum dominant share across 34 * all entities. 35 * 36 * For example, if user A runs CPU-heavy tasks and user B runs 37 * memory-heavy tasks, it attempts to equalize CPU share of user A 38 * with Memory-share of user B. 39 * 40 * In the single resource case, it reduces to max-min fairness for that resource. 41 * 42 * See the Dominant Resource Fairness paper for more details: 43 * www.cs.berkeley.edu/~matei/papers/2011/nsdi_drf.pdf 44 */ 45 @Private 46 @Unstable 47 public class DominantResourceCalculator extends ResourceCalculator { 48 49 @Override compare(Resource clusterResource, Resource lhs, Resource rhs)50 public int compare(Resource clusterResource, Resource lhs, Resource rhs) { 51 52 if (lhs.equals(rhs)) { 53 return 0; 54 } 55 56 if (isInvalidDivisor(clusterResource)) { 57 if ((lhs.getMemory() < rhs.getMemory() && lhs.getVirtualCores() > rhs 58 .getVirtualCores()) 59 || (lhs.getMemory() > rhs.getMemory() && lhs.getVirtualCores() < rhs 60 .getVirtualCores())) { 61 return 0; 62 } else if (lhs.getMemory() > rhs.getMemory() 63 || lhs.getVirtualCores() > rhs.getVirtualCores()) { 64 return 1; 65 } else if (lhs.getMemory() < rhs.getMemory() 66 || lhs.getVirtualCores() < rhs.getVirtualCores()) { 67 return -1; 68 } 69 } 70 71 float l = getResourceAsValue(clusterResource, lhs, true); 72 float r = getResourceAsValue(clusterResource, rhs, true); 73 74 if (l < r) { 75 return -1; 76 } else if (l > r) { 77 return 1; 78 } else { 79 l = getResourceAsValue(clusterResource, lhs, false); 80 r = getResourceAsValue(clusterResource, rhs, false); 81 if (l < r) { 82 return -1; 83 } else if (l > r) { 84 return 1; 85 } 86 } 87 88 return 0; 89 } 90 91 /** 92 * Use 'dominant' for now since we only have 2 resources - gives us a slight 93 * performance boost. 94 * 95 * Once we add more resources, we'll need a more complicated (and slightly 96 * less performant algorithm). 97 */ getResourceAsValue( Resource clusterResource, Resource resource, boolean dominant)98 protected float getResourceAsValue( 99 Resource clusterResource, Resource resource, boolean dominant) { 100 // Just use 'dominant' resource 101 return (dominant) ? 102 Math.max( 103 (float)resource.getMemory() / clusterResource.getMemory(), 104 (float)resource.getVirtualCores() / clusterResource.getVirtualCores() 105 ) 106 : 107 Math.min( 108 (float)resource.getMemory() / clusterResource.getMemory(), 109 (float)resource.getVirtualCores() / clusterResource.getVirtualCores() 110 ); 111 } 112 113 @Override computeAvailableContainers(Resource available, Resource required)114 public int computeAvailableContainers(Resource available, Resource required) { 115 return Math.min( 116 available.getMemory() / required.getMemory(), 117 available.getVirtualCores() / required.getVirtualCores()); 118 } 119 120 @Override divide(Resource clusterResource, Resource numerator, Resource denominator)121 public float divide(Resource clusterResource, 122 Resource numerator, Resource denominator) { 123 return 124 getResourceAsValue(clusterResource, numerator, true) / 125 getResourceAsValue(clusterResource, denominator, true); 126 } 127 128 @Override isInvalidDivisor(Resource r)129 public boolean isInvalidDivisor(Resource r) { 130 if (r.getMemory() == 0.0f || r.getVirtualCores() == 0.0f) { 131 return true; 132 } 133 return false; 134 } 135 136 @Override ratio(Resource a, Resource b)137 public float ratio(Resource a, Resource b) { 138 return Math.max( 139 (float)a.getMemory()/b.getMemory(), 140 (float)a.getVirtualCores()/b.getVirtualCores() 141 ); 142 } 143 144 @Override divideAndCeil(Resource numerator, int denominator)145 public Resource divideAndCeil(Resource numerator, int denominator) { 146 return Resources.createResource( 147 divideAndCeil(numerator.getMemory(), denominator), 148 divideAndCeil(numerator.getVirtualCores(), denominator) 149 ); 150 } 151 152 @Override normalize(Resource r, Resource minimumResource, Resource maximumResource, Resource stepFactor)153 public Resource normalize(Resource r, Resource minimumResource, 154 Resource maximumResource, Resource stepFactor) { 155 int normalizedMemory = Math.min( 156 roundUp( 157 Math.max(r.getMemory(), minimumResource.getMemory()), 158 stepFactor.getMemory()), 159 maximumResource.getMemory()); 160 int normalizedCores = Math.min( 161 roundUp( 162 Math.max(r.getVirtualCores(), minimumResource.getVirtualCores()), 163 stepFactor.getVirtualCores()), 164 maximumResource.getVirtualCores()); 165 return Resources.createResource(normalizedMemory, 166 normalizedCores); 167 } 168 169 @Override roundUp(Resource r, Resource stepFactor)170 public Resource roundUp(Resource r, Resource stepFactor) { 171 return Resources.createResource( 172 roundUp(r.getMemory(), stepFactor.getMemory()), 173 roundUp(r.getVirtualCores(), stepFactor.getVirtualCores()) 174 ); 175 } 176 177 @Override roundDown(Resource r, Resource stepFactor)178 public Resource roundDown(Resource r, Resource stepFactor) { 179 return Resources.createResource( 180 roundDown(r.getMemory(), stepFactor.getMemory()), 181 roundDown(r.getVirtualCores(), stepFactor.getVirtualCores()) 182 ); 183 } 184 185 @Override multiplyAndNormalizeUp(Resource r, double by, Resource stepFactor)186 public Resource multiplyAndNormalizeUp(Resource r, double by, 187 Resource stepFactor) { 188 return Resources.createResource( 189 roundUp( 190 (int)Math.ceil(r.getMemory() * by), stepFactor.getMemory()), 191 roundUp( 192 (int)Math.ceil(r.getVirtualCores() * by), 193 stepFactor.getVirtualCores()) 194 ); 195 } 196 197 @Override multiplyAndNormalizeDown(Resource r, double by, Resource stepFactor)198 public Resource multiplyAndNormalizeDown(Resource r, double by, 199 Resource stepFactor) { 200 return Resources.createResource( 201 roundDown( 202 (int)(r.getMemory() * by), 203 stepFactor.getMemory() 204 ), 205 roundDown( 206 (int)(r.getVirtualCores() * by), 207 stepFactor.getVirtualCores() 208 ) 209 ); 210 } 211 212 } 213