Simplify the check for whether a metric matches
The old way was more efficient if there were few dimensions on the metric and lots of Alarm Definitions with different dimension sets for a given tenant id and metric name, but that is probably unlikely. The more common case will be one or two alarm definitions per tenant id and metric name and more dimensions on the metric. The new algorithm is faster for that case since it doesn't create every possible combinations of dimensions like the old algorithm Change-Id: I183570d52c61f0a2932cf37c5c659a6c529b4bbb
This commit is contained in:
Craig Bryant
parent
5b33c539bf
commit
9c4bd6cc99
|
|
@ -19,165 +19,100 @@ package monasca.thresh.domain.model;
|
|||
|
||||
import monasca.common.model.metric.MetricDefinition;
|
||||
|
||||
import java.util.Arrays;
|
||||
import java.util.Collections;
|
||||
import java.util.HashMap;
|
||||
import java.util.HashSet;
|
||||
import java.util.LinkedList;
|
||||
import java.util.List;
|
||||
import java.util.Map;
|
||||
import java.util.Set;
|
||||
import java.util.concurrent.ConcurrentHashMap;
|
||||
|
||||
/**
|
||||
* This class is used to find any matching MetricDefinitionAndTenantId instances that match a given
|
||||
* MetricDefinitionAndTenantId. This class has no way of handling duplicate
|
||||
* MetricDefinitionAndTenantIds so it assume some other handles that issue.
|
||||
*
|
||||
* The actual MetricDefinitionAndTenantId is not kept in the last Map in order to save heap space.
|
||||
* It is expected that possibly millions of metrics may be stored in the Matcher and so by only
|
||||
* storing the DiminsionPairs instead of the whole MetricDefinitionAndTenantId, a significant amount
|
||||
* of heap space will be saved thus reducing swapping. The MetricDefinitionAndTenantId is recreated
|
||||
* when returned but since it will be just sent on and then the reference dropped, the object will
|
||||
* be quickly and easily garbage collected. Testing shows that this algorithm is faster than keeping
|
||||
* the whole MetricDefinitionAndTenantId in the Map.
|
||||
* This class is used to find any matching MetricDefinitionAndTenantId instances that match the
|
||||
* MetricDefinitionAndTenantIds and their associated Alarm Definition IDs that have been loaded.
|
||||
*
|
||||
* The actual MetricDefinitionAndTenantId is not kept in the AlarmDefinitionDimensions in order to
|
||||
* save heap space. It is expected that possibly millions of metrics may be stored in the Matcher
|
||||
* and so by only storing the Dimensions instead of the whole MetricDefinitionAndTenantId, a
|
||||
* significant amount of heap space will be saved thus reducing swapping.
|
||||
*/
|
||||
public class MetricDefinitionAndTenantIdMatcher {
|
||||
final Map<String, Map<String, Map<DimensionSet, Set<String>>>> byTenantId = new ConcurrentHashMap<>();
|
||||
private final static DimensionSet EMPTY_DIMENSION_SET = new DimensionSet(new DimensionPair[0]);
|
||||
final Map<String, Map<String, List<AlarmDefinitionDimensions>>> byTenantId = new ConcurrentHashMap<>();
|
||||
@SuppressWarnings("unchecked")
|
||||
private final static Set<String> EMPTY_SET = Collections.EMPTY_SET;
|
||||
|
||||
public void add(MetricDefinitionAndTenantId metricDefinitionAndTenantId, String alarmDefinitionId) {
|
||||
Map<String, Map<DimensionSet, Set<String>>> byMetricName =
|
||||
Map<String, List<AlarmDefinitionDimensions>> byMetricName =
|
||||
byTenantId.get(metricDefinitionAndTenantId.tenantId);
|
||||
if (byMetricName == null) {
|
||||
byMetricName = new ConcurrentHashMap<>();
|
||||
byTenantId.put(metricDefinitionAndTenantId.tenantId, byMetricName);
|
||||
}
|
||||
Map<DimensionSet, Set<String>> byDimensionSet =
|
||||
List<AlarmDefinitionDimensions> alarmDefDimensions =
|
||||
byMetricName.get(metricDefinitionAndTenantId.metricDefinition.name);
|
||||
if (byDimensionSet == null) {
|
||||
byDimensionSet = new ConcurrentHashMap<>();
|
||||
byMetricName.put(metricDefinitionAndTenantId.metricDefinition.name, byDimensionSet);
|
||||
if (alarmDefDimensions == null) {
|
||||
alarmDefDimensions = new LinkedList<>();
|
||||
byMetricName.put(metricDefinitionAndTenantId.metricDefinition.name, alarmDefDimensions);
|
||||
}
|
||||
final DimensionSet dimensionSet =
|
||||
createDimensionSet(metricDefinitionAndTenantId.metricDefinition);
|
||||
Set<String> alarmDefIds = byDimensionSet.get(dimensionSet);
|
||||
if (alarmDefIds == null) {
|
||||
alarmDefIds = new HashSet<>();
|
||||
byDimensionSet.put(dimensionSet, alarmDefIds);
|
||||
}
|
||||
alarmDefIds.add(alarmDefinitionId);
|
||||
final AlarmDefinitionDimensions dimensionSet =
|
||||
createDimensionSet(metricDefinitionAndTenantId.metricDefinition, alarmDefinitionId);
|
||||
alarmDefDimensions.add(dimensionSet);
|
||||
}
|
||||
|
||||
private DimensionSet createDimensionSet(MetricDefinition metricDefinition) {
|
||||
return new DimensionSet(createPairs(metricDefinition));
|
||||
private AlarmDefinitionDimensions createDimensionSet(MetricDefinition metricDefinition,
|
||||
final String alarmDefinitionId) {
|
||||
return new AlarmDefinitionDimensions(metricDefinition.dimensions, alarmDefinitionId);
|
||||
}
|
||||
|
||||
public boolean remove(MetricDefinitionAndTenantId metricDefinitionAndTenantId,
|
||||
final String alarmDefinitionId) {
|
||||
final Map<String, Map<DimensionSet, Set<String>>> byMetricName =
|
||||
final Map<String, List<AlarmDefinitionDimensions>> byMetricName =
|
||||
byTenantId.get(metricDefinitionAndTenantId.tenantId);
|
||||
if (byMetricName == null) {
|
||||
return false;
|
||||
}
|
||||
|
||||
final Map<DimensionSet, Set<String>> byDimensionSet =
|
||||
final List<AlarmDefinitionDimensions> alarmDefDimensions =
|
||||
byMetricName.get(metricDefinitionAndTenantId.metricDefinition.name);
|
||||
if (byDimensionSet == null) {
|
||||
if (alarmDefDimensions == null) {
|
||||
return false;
|
||||
}
|
||||
|
||||
final DimensionSet dimensionSet =
|
||||
createDimensionSet(metricDefinitionAndTenantId.metricDefinition);
|
||||
final Set<String> alarmDefinitionIds = byDimensionSet.get(dimensionSet);
|
||||
boolean result = false;
|
||||
if (alarmDefinitionIds != null && !alarmDefinitionIds.isEmpty()) {
|
||||
if (alarmDefinitionIds.remove(alarmDefinitionId)) {
|
||||
result = true;
|
||||
if (alarmDefinitionIds.isEmpty()) {
|
||||
byDimensionSet.remove(dimensionSet);
|
||||
if (byDimensionSet.isEmpty()) {
|
||||
byMetricName.remove(metricDefinitionAndTenantId.metricDefinition.name);
|
||||
if (byMetricName.isEmpty()) {
|
||||
byTenantId.remove(metricDefinitionAndTenantId.tenantId);
|
||||
}
|
||||
}
|
||||
}
|
||||
final AlarmDefinitionDimensions toFind =
|
||||
createDimensionSet(metricDefinitionAndTenantId.metricDefinition, alarmDefinitionId);
|
||||
final boolean result = alarmDefDimensions.remove(toFind);
|
||||
if (result && alarmDefDimensions.isEmpty()) {
|
||||
byMetricName.remove(metricDefinitionAndTenantId.metricDefinition.name);
|
||||
if (byMetricName.isEmpty()) {
|
||||
byTenantId.remove(metricDefinitionAndTenantId.tenantId);
|
||||
}
|
||||
}
|
||||
return result;
|
||||
}
|
||||
|
||||
public Set<String> match(final MetricDefinitionAndTenantId toMatch) {
|
||||
final Map<String, Map<DimensionSet, Set<String>>> byMetricName = byTenantId.get(toMatch.tenantId);
|
||||
final Map<String, List<AlarmDefinitionDimensions>> byMetricName = byTenantId.get(toMatch.tenantId);
|
||||
if (byMetricName == null) {
|
||||
return EMPTY_SET;
|
||||
}
|
||||
|
||||
final Map<DimensionSet, Set<String>> byDimensionSet =
|
||||
byMetricName.get(toMatch.metricDefinition.name);
|
||||
if (byDimensionSet == null) {
|
||||
final List<AlarmDefinitionDimensions> alarmDefDimensions = byMetricName.get(toMatch.metricDefinition.name);
|
||||
if (alarmDefDimensions == null) {
|
||||
return EMPTY_SET;
|
||||
}
|
||||
final DimensionSet[] possibleDimensionSets =
|
||||
createPossibleDimensionPairs(toMatch.metricDefinition);
|
||||
Set<String> matches = null;
|
||||
for (final DimensionSet dimensionSet : possibleDimensionSets) {
|
||||
final Set<String> alarmDefinitionIds = byDimensionSet.get(dimensionSet);
|
||||
if (alarmDefinitionIds != null) {
|
||||
for (final AlarmDefinitionDimensions alarmDefDimension : alarmDefDimensions) {
|
||||
if (alarmDefDimension.isContainedIn(toMatch.metricDefinition.dimensions)) {
|
||||
if (matches == null) {
|
||||
matches = new HashSet<>();
|
||||
}
|
||||
matches.addAll(alarmDefinitionIds);
|
||||
matches.add(alarmDefDimension.alarmDefinitionId);
|
||||
}
|
||||
}
|
||||
return matches == null ? EMPTY_SET : matches;
|
||||
}
|
||||
|
||||
protected DimensionSet[] createPossibleDimensionPairs(MetricDefinition metricDefinition) {
|
||||
final int dimensionSize =
|
||||
metricDefinition.dimensions == null ? 0 : metricDefinition.dimensions.size();
|
||||
final int size = (int) Math.pow(2, dimensionSize);
|
||||
final DimensionSet[] result = new DimensionSet[size];
|
||||
int index = 0;
|
||||
result[index++] = EMPTY_DIMENSION_SET;
|
||||
if (dimensionSize == 0) {
|
||||
return result;
|
||||
}
|
||||
final DimensionPair[] pairs = createPairs(metricDefinition);
|
||||
for (int i = 0; i < pairs.length; i++) {
|
||||
index = addMore(pairs, i, EMPTY_DIMENSION_SET, result, index);
|
||||
}
|
||||
return result;
|
||||
}
|
||||
|
||||
private int addMore(DimensionPair[] pairs, int start, DimensionSet dimensionSet,
|
||||
DimensionSet[] result, int index) {
|
||||
final DimensionPair[] newPairs = new DimensionPair[dimensionSet.pairs.length + 1];
|
||||
if (dimensionSet.pairs.length > 0) {
|
||||
System.arraycopy(dimensionSet.pairs, 0, newPairs, 0, dimensionSet.pairs.length);
|
||||
}
|
||||
newPairs[dimensionSet.pairs.length] = pairs[start];
|
||||
final DimensionSet thisDimensionSet = new DimensionSet(newPairs);
|
||||
result[index++] = thisDimensionSet;
|
||||
for (int i = start + 1; i < pairs.length; i++) {
|
||||
index = addMore(pairs, i, thisDimensionSet, result, index);
|
||||
}
|
||||
return index;
|
||||
}
|
||||
|
||||
private DimensionPair[] createPairs(MetricDefinition metricDefinition) {
|
||||
final int dimensionSize =
|
||||
metricDefinition.dimensions == null ? 0 : metricDefinition.dimensions.size();
|
||||
final DimensionPair[] pairs = new DimensionPair[dimensionSize];
|
||||
if (dimensionSize > 0) { // metricDefinition.dimensions can be null
|
||||
int index = 0;
|
||||
for (final Map.Entry<String, String> entry : metricDefinition.dimensions.entrySet()) {
|
||||
pairs[index++] = new DimensionPair(entry.getKey(), entry.getValue());
|
||||
}
|
||||
}
|
||||
return pairs;
|
||||
}
|
||||
|
||||
public boolean isEmpty() {
|
||||
return byTenantId.isEmpty();
|
||||
}
|
||||
|
|
@ -186,80 +121,47 @@ public class MetricDefinitionAndTenantIdMatcher {
|
|||
byTenantId.clear();
|
||||
}
|
||||
|
||||
protected static class DimensionSet {
|
||||
final DimensionPair[] pairs;
|
||||
private static class AlarmDefinitionDimensions {
|
||||
final Map<String, String> dimensions;
|
||||
final String alarmDefinitionId;
|
||||
|
||||
public DimensionSet(DimensionPair... pairs) {
|
||||
Arrays.sort(pairs);
|
||||
this.pairs = pairs;
|
||||
public AlarmDefinitionDimensions(Map<String, String> dimensions, final String alarmDefinitionId) {
|
||||
if (dimensions != null) {
|
||||
this.dimensions = dimensions;
|
||||
}
|
||||
else {
|
||||
this.dimensions = new HashMap<>();
|
||||
}
|
||||
this.alarmDefinitionId = alarmDefinitionId;
|
||||
}
|
||||
|
||||
@Override
|
||||
public int hashCode() {
|
||||
int result = 1;
|
||||
final int prime = 31;
|
||||
for (DimensionPair pair : pairs) {
|
||||
result = result * prime + pair.hashCode();
|
||||
}
|
||||
return result;
|
||||
}
|
||||
|
||||
@Override
|
||||
public boolean equals(Object obj) {
|
||||
if (this == obj) {
|
||||
return true;
|
||||
}
|
||||
if (obj == null) {
|
||||
public boolean isContainedIn(Map<String, String> metricDimensions) {
|
||||
// All of the dimensions in this AlarmDefinitionDimensions must also be in the metric
|
||||
// dimensions
|
||||
if (metricDimensions.size() < this.dimensions.size()) {
|
||||
return false;
|
||||
}
|
||||
if (getClass() != obj.getClass()) {
|
||||
return false;
|
||||
}
|
||||
final DimensionSet other = (DimensionSet) obj;
|
||||
if (this.pairs.length != other.pairs.length) {
|
||||
return false;
|
||||
}
|
||||
for (int i = 0; i < this.pairs.length; i++) {
|
||||
if (!this.pairs[i].equals(other.pairs[i])) {
|
||||
return false;
|
||||
for (final Map.Entry<String, String> entry : this.dimensions.entrySet()) {
|
||||
final String value = metricDimensions.get(entry.getKey());
|
||||
if (entry.getValue() == null) {
|
||||
if (value != null) {
|
||||
return false;
|
||||
}
|
||||
} else {
|
||||
if (!entry.getValue().equals(value)) {
|
||||
return false;
|
||||
}
|
||||
}
|
||||
}
|
||||
return true;
|
||||
}
|
||||
|
||||
@Override
|
||||
public String toString() {
|
||||
final StringBuilder builder = new StringBuilder(256);
|
||||
builder.append("DimensionSet [");
|
||||
boolean first = true;
|
||||
for (DimensionPair pair : pairs) {
|
||||
if (!first) {
|
||||
builder.append(", ");
|
||||
}
|
||||
builder.append(pair.toString());
|
||||
first = false;
|
||||
}
|
||||
builder.append("]");
|
||||
|
||||
return builder.toString();
|
||||
}
|
||||
}
|
||||
|
||||
protected static class DimensionPair implements Comparable<DimensionPair> {
|
||||
private String key;
|
||||
private String value;
|
||||
|
||||
public DimensionPair(String key, String value) {
|
||||
this.key = key;
|
||||
this.value = value;
|
||||
}
|
||||
|
||||
@Override
|
||||
public int hashCode() {
|
||||
int result = 1;
|
||||
final int prime = 31;
|
||||
result = prime * result + key.hashCode();
|
||||
result = prime * result + ((value == null) ? 0 : value.hashCode());
|
||||
int result = 1;
|
||||
result = prime * result + alarmDefinitionId.hashCode();
|
||||
result = prime * result + dimensions.hashCode();
|
||||
return result;
|
||||
}
|
||||
|
||||
|
|
@ -274,36 +176,23 @@ public class MetricDefinitionAndTenantIdMatcher {
|
|||
if (getClass() != obj.getClass()) {
|
||||
return false;
|
||||
}
|
||||
DimensionPair other = (DimensionPair) obj;
|
||||
return compareStrings(key, other.key) && compareStrings(value, other.value);
|
||||
}
|
||||
|
||||
private boolean compareStrings(final String s1, final String s2) {
|
||||
if (s1 == s2) {
|
||||
return true;
|
||||
}
|
||||
if (s1 == null) {
|
||||
final AlarmDefinitionDimensions other = (AlarmDefinitionDimensions) obj;
|
||||
if (!this.alarmDefinitionId.equals(other.alarmDefinitionId)) {
|
||||
return false;
|
||||
}
|
||||
return s1.equals(s2);
|
||||
}
|
||||
|
||||
@Override
|
||||
public int compareTo(DimensionPair o) {
|
||||
int c = this.key.compareTo(o.key);
|
||||
if (c != 0) {
|
||||
return c;
|
||||
}
|
||||
// Handle possible null values. A actual value is bigger than a null
|
||||
if (this.value == null) {
|
||||
return o.value == null ? 0 : 1;
|
||||
}
|
||||
return this.value.compareTo(o.value);
|
||||
return this.dimensions.equals(other.dimensions);
|
||||
}
|
||||
|
||||
@Override
|
||||
public String toString() {
|
||||
return String.format("DimensionPair %s=%s", key, value);
|
||||
final StringBuilder builder = new StringBuilder(256);
|
||||
builder.append("AlarmDefinitionDimensions [alarmDefinitionId=");
|
||||
builder.append(alarmDefinitionId);
|
||||
builder.append(",dimensions=");
|
||||
builder.append(this.dimensions);
|
||||
builder.append("]");
|
||||
|
||||
return builder.toString();
|
||||
}
|
||||
}
|
||||
}
|
||||
|
|
|
|||
|
|
@ -22,9 +22,6 @@ import static org.testng.Assert.assertTrue;
|
|||
|
||||
import monasca.common.model.metric.MetricDefinition;
|
||||
|
||||
import monasca.thresh.domain.model.MetricDefinitionAndTenantIdMatcher.DimensionPair;
|
||||
import monasca.thresh.domain.model.MetricDefinitionAndTenantIdMatcher.DimensionSet;
|
||||
|
||||
import org.testng.annotations.BeforeMethod;
|
||||
import org.testng.annotations.Test;
|
||||
|
||||
|
|
@ -172,73 +169,6 @@ public class MetricDefinitionAndTenantIdMatcherTest {
|
|||
verifyNoMatch(toMatch);
|
||||
}
|
||||
|
||||
public void shouldCreatePossiblePairs() {
|
||||
final Map<String, String> dimensions = new HashMap<>();
|
||||
DimensionSet[] actual =
|
||||
matcher.createPossibleDimensionPairs(new MetricDefinition(CPU_METRIC_NAME, dimensions));
|
||||
DimensionSet[] expected = {new DimensionSet()};
|
||||
assertEqualsNoOrder(actual, expected);
|
||||
|
||||
dimensions.put("1", "a");
|
||||
actual =
|
||||
matcher.createPossibleDimensionPairs(new MetricDefinition(CPU_METRIC_NAME, dimensions));
|
||||
expected =
|
||||
new DimensionSet[] {new DimensionSet(), new DimensionSet(new DimensionPair("1", "a"))};
|
||||
assertEqualsNoOrder(actual, expected);
|
||||
|
||||
dimensions.put("2", "b");
|
||||
actual =
|
||||
matcher.createPossibleDimensionPairs(new MetricDefinition(CPU_METRIC_NAME, dimensions));
|
||||
expected =
|
||||
new DimensionSet[] {new DimensionSet(), new DimensionSet(new DimensionPair("1", "a")),
|
||||
new DimensionSet(new DimensionPair("2", "b")),
|
||||
new DimensionSet(new DimensionPair("1", "a"), new DimensionPair("2", "b"))};
|
||||
assertEqualsNoOrder(actual, expected);
|
||||
|
||||
dimensions.put("3", "c");
|
||||
actual =
|
||||
matcher.createPossibleDimensionPairs(new MetricDefinition(CPU_METRIC_NAME, dimensions));
|
||||
expected =
|
||||
new DimensionSet[] {
|
||||
new DimensionSet(),
|
||||
new DimensionSet(new DimensionPair("1", "a")),
|
||||
new DimensionSet(new DimensionPair("2", "b")),
|
||||
new DimensionSet(new DimensionPair("3", "c")),
|
||||
new DimensionSet(new DimensionPair("1", "a"), new DimensionPair("2", "b")),
|
||||
new DimensionSet(new DimensionPair("1", "a"), new DimensionPair("3", "c")),
|
||||
new DimensionSet(new DimensionPair("2", "b"), new DimensionPair("3", "c")),
|
||||
new DimensionSet(new DimensionPair("1", "a"), new DimensionPair("2", "b"),
|
||||
new DimensionPair("3", "c"))};
|
||||
|
||||
dimensions.put("4", "d");
|
||||
actual =
|
||||
matcher.createPossibleDimensionPairs(new MetricDefinition(CPU_METRIC_NAME, dimensions));
|
||||
expected =
|
||||
new DimensionSet[] {
|
||||
new DimensionSet(),
|
||||
new DimensionSet(new DimensionPair("1", "a")),
|
||||
new DimensionSet(new DimensionPair("2", "b")),
|
||||
new DimensionSet(new DimensionPair("3", "c")),
|
||||
new DimensionSet(new DimensionPair("4", "d")),
|
||||
new DimensionSet(new DimensionPair("1", "a"), new DimensionPair("2", "b")),
|
||||
new DimensionSet(new DimensionPair("1", "a"), new DimensionPair("3", "c")),
|
||||
new DimensionSet(new DimensionPair("1", "a"), new DimensionPair("4", "d")),
|
||||
new DimensionSet(new DimensionPair("2", "b"), new DimensionPair("3", "c")),
|
||||
new DimensionSet(new DimensionPair("2", "b"), new DimensionPair("4", "d")),
|
||||
new DimensionSet(new DimensionPair("3", "c"), new DimensionPair("4", "d")),
|
||||
new DimensionSet(new DimensionPair("1", "a"), new DimensionPair("2", "b"),
|
||||
new DimensionPair("3", "c")),
|
||||
new DimensionSet(new DimensionPair("1", "a"), new DimensionPair("2", "b"),
|
||||
new DimensionPair("4", "d")),
|
||||
new DimensionSet(new DimensionPair("1", "a"), new DimensionPair("3", "c"),
|
||||
new DimensionPair("4", "d")),
|
||||
new DimensionSet(new DimensionPair("2", "b"), new DimensionPair("3", "c"),
|
||||
new DimensionPair("4", "d")),
|
||||
new DimensionSet(new DimensionPair("1", "a"), new DimensionPair("2", "b"),
|
||||
new DimensionPair("3", "c"), new DimensionPair("4", "d"))};
|
||||
assertEqualsNoOrder(actual, expected);
|
||||
}
|
||||
|
||||
private String getNextId() {
|
||||
return String.valueOf(this.nextId++);
|
||||
}
|
||||
|
|
|
|||
Loading…
Reference in New Issue