From 1c66a277c9791984fab3b70f8e93d61795b2fe15 Mon Sep 17 00:00:00 2001 From: Moiz Raja Date: Sun, 11 Oct 2015 13:52:52 -0700 Subject: [PATCH] Implement LeastLoadedCandidateSelectionStrategy Change-Id: I09035505bcfa0ef5b2ac357217186ad98db7974c Signed-off-by: Moiz Raja --- .../entityownership/EntityOwnershipShard.java | 20 +++++-- .../EntityOwnershipStatistics.java | 5 +- .../EntityOwnerSelectionStrategy.java | 5 +- .../FirstCandidateSelectionStrategy.java | 3 +- ...LeastLoadedCandidateSelectionStrategy.java | 41 ++++++++++++++ .../LastCandidateSelectionStrategy.java | 3 +- ...tLoadedCandidateSelectionStrategyTest.java | 55 +++++++++++++++++++ 7 files changed, 123 insertions(+), 9 deletions(-) create mode 100644 opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/LeastLoadedCandidateSelectionStrategy.java create mode 100644 opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/LeastLoadedCandidateSelectionStrategyTest.java diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/EntityOwnershipShard.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/EntityOwnershipShard.java index 60fab39b8e..d104222b9c 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/EntityOwnershipShard.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/EntityOwnershipShard.java @@ -142,7 +142,9 @@ class EntityOwnershipShard extends Shard { private void onSelectOwner(SelectOwner selectOwner) { String currentOwner = getCurrentOwner(selectOwner.getEntityPath()); if(Strings.isNullOrEmpty(currentOwner)) { + String entityType = EntityOwnersModel.entityTypeFromEntityPath(selectOwner.getEntityPath()); writeNewOwner(selectOwner.getEntityPath(), newOwner(selectOwner.getAllCandidates(), + entityOwnershipStatistics.byEntityType(entityType), selectOwner.getOwnerSelectionStrategy())); Cancellable cancellable = entityToScheduledOwnershipTask.get(selectOwner.getEntityPath()); @@ -272,8 +274,10 @@ class EntityOwnershipShard extends Shard { if(isLeader()) { String currentOwner = getCurrentOwner(message.getEntityPath()); if(message.getRemovedCandidate().equals(currentOwner)){ + String entityType = EntityOwnersModel.entityTypeFromEntityPath(message.getEntityPath()); writeNewOwner(message.getEntityPath(), - newOwner(message.getRemainingCandidates(), getEntityOwnerElectionStrategy(message.getEntityPath()))); + newOwner(message.getRemainingCandidates(), entityOwnershipStatistics.byEntityType(entityType), + getEntityOwnerElectionStrategy(message.getEntityPath()))); } } else { // We're not the leader. If the removed candidate is our local member then check if we actually @@ -313,7 +317,9 @@ class EntityOwnershipShard extends Shard { EntityOwnerSelectionStrategy strategy = getEntityOwnerElectionStrategy(message.getEntityPath()); if(Strings.isNullOrEmpty(currentOwner)){ if(strategy.getSelectionDelayInMillis() == 0L) { - writeNewOwner(message.getEntityPath(), newOwner(message.getAllCandidates(), strategy)); + String entityType = EntityOwnersModel.entityTypeFromEntityPath(message.getEntityPath()); + writeNewOwner(message.getEntityPath(), newOwner(message.getAllCandidates(), + entityOwnershipStatistics.byEntityType(entityType), strategy)); } else { scheduleOwnerSelection(message.getEntityPath(), message.getAllCandidates(), strategy); } @@ -347,7 +353,11 @@ class EntityOwnershipShard extends Shard { node(entityTypeNode.getIdentifier()).node(ENTITY_NODE_ID).node(entityNode.getIdentifier()). node(ENTITY_OWNER_NODE_ID).build(); - Object newOwner = newOwner(getCandidateNames(entityNode), getEntityOwnerElectionStrategy(entityPath)); + String entityType = EntityOwnersModel.entityTypeFromEntityPath(entityPath); + + Object newOwner = newOwner(getCandidateNames(entityNode), + entityOwnershipStatistics.byEntityType(entityType), + getEntityOwnerElectionStrategy(entityPath)); LOG.debug("{}: Found entity {}, writing new owner {}", persistenceId(), entityPath, newOwner); @@ -462,12 +472,12 @@ class EntityOwnershipShard extends Shard { entityToScheduledOwnershipTask.put(entityPath, lastScheduledTask); } - private String newOwner(Collection candidates, EntityOwnerSelectionStrategy ownerSelectionStrategy) { + private String newOwner(Collection candidates, Map statistics, EntityOwnerSelectionStrategy ownerSelectionStrategy) { Collection viableCandidates = getViableCandidates(candidates); if(viableCandidates.size() == 0){ return ""; } - return ownerSelectionStrategy.newOwner(viableCandidates); + return ownerSelectionStrategy.newOwner(viableCandidates, statistics); } private Collection getViableCandidates(Collection candidates) { diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/EntityOwnershipStatistics.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/EntityOwnershipStatistics.java index 3ea4362ac9..02bd00bfb1 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/EntityOwnershipStatistics.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/EntityOwnershipStatistics.java @@ -65,7 +65,10 @@ class EntityOwnershipStatistics extends AbstractEntityOwnerChangeListener { } Map byEntityType(String entityType){ - return statistics.get(entityType).readOnlySnapshot(); + if(statistics.get(entityType) != null) { + return statistics.get(entityType).readOnlySnapshot(); + } + return new HashMap<>(); } private void updateStatistics(String entityType, String candidateName, long count){ diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/EntityOwnerSelectionStrategy.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/EntityOwnerSelectionStrategy.java index e86c3a1151..53b35f65c4 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/EntityOwnerSelectionStrategy.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/EntityOwnerSelectionStrategy.java @@ -9,6 +9,7 @@ package org.opendaylight.controller.cluster.datastore.entityownership.selectionstrategy; import java.util.Collection; +import java.util.Map; /** * An EntityOwnerSelectionStrategy is to be used by the EntityOwnershipShard to select a new owner from a collection @@ -25,7 +26,9 @@ public interface EntityOwnerSelectionStrategy { /** * * @param viableCandidates the available candidates from which to choose the new owner + * @param statistics contains a snapshot of a mapping between candidate names and the number of entities + * owned by that candidate * @return the new owner */ - String newOwner(Collection viableCandidates); + String newOwner(Collection viableCandidates, Map statistics); } diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/FirstCandidateSelectionStrategy.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/FirstCandidateSelectionStrategy.java index b009c3aff4..d86fcbd249 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/FirstCandidateSelectionStrategy.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/FirstCandidateSelectionStrategy.java @@ -10,6 +10,7 @@ package org.opendaylight.controller.cluster.datastore.entityownership.selections import com.google.common.base.Preconditions; import java.util.Collection; +import java.util.Map; /** * The FirstCandidateSelectionStrategy always selects the first viable candidate from the list of candidates @@ -23,7 +24,7 @@ public class FirstCandidateSelectionStrategy extends AbstractEntityOwnerSelectio } @Override - public String newOwner(Collection viableCandidates) { + public String newOwner(Collection viableCandidates, Map statistics) { Preconditions.checkArgument(viableCandidates.size() > 0, "No viable candidates provided"); return viableCandidates.iterator().next(); } diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/LeastLoadedCandidateSelectionStrategy.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/LeastLoadedCandidateSelectionStrategy.java new file mode 100644 index 0000000000..9ebf21cdce --- /dev/null +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/LeastLoadedCandidateSelectionStrategy.java @@ -0,0 +1,41 @@ +/* + * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ + +package org.opendaylight.controller.cluster.datastore.entityownership.selectionstrategy; + +import java.util.Collection; +import java.util.Map; + +/** + * The LeastLoadedCandidateSelectionStrategy assigns ownership for an entity to the candidate which owns the least + * number of entities. + */ +public class LeastLoadedCandidateSelectionStrategy extends AbstractEntityOwnerSelectionStrategy { + protected LeastLoadedCandidateSelectionStrategy(long selectionDelayInMillis) { + super(selectionDelayInMillis); + } + + @Override + public String newOwner(Collection viableCandidates, Map statistics) { + String leastLoadedCandidate = null; + long leastLoadedCount = Long.MAX_VALUE; + + for(String candidateName : viableCandidates){ + Long val = statistics.get(candidateName); + if(val != null && val < leastLoadedCount){ + leastLoadedCount = val; + leastLoadedCandidate = candidateName; + } + } + + if(leastLoadedCandidate == null){ + return viableCandidates.iterator().next(); + } + return leastLoadedCandidate; + } +} diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/LastCandidateSelectionStrategy.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/LastCandidateSelectionStrategy.java index 30c6277357..ea7deb5693 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/LastCandidateSelectionStrategy.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/LastCandidateSelectionStrategy.java @@ -11,6 +11,7 @@ package org.opendaylight.controller.cluster.datastore.entityownership.selections import java.util.ArrayList; import java.util.Collection; import java.util.List; +import java.util.Map; public class LastCandidateSelectionStrategy extends AbstractEntityOwnerSelectionStrategy { public LastCandidateSelectionStrategy(long selectionDelayInMillis) { @@ -18,7 +19,7 @@ public class LastCandidateSelectionStrategy extends AbstractEntityOwnerSelection } @Override - public String newOwner(Collection viableCandidates) { + public String newOwner(Collection viableCandidates, Map statistics) { List candidates = new ArrayList<>(viableCandidates); return candidates.get(candidates.size()-1); } diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/LeastLoadedCandidateSelectionStrategyTest.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/LeastLoadedCandidateSelectionStrategyTest.java new file mode 100644 index 0000000000..50db591a19 --- /dev/null +++ b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/entityownership/selectionstrategy/LeastLoadedCandidateSelectionStrategyTest.java @@ -0,0 +1,55 @@ +/* + * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.controller.cluster.datastore.entityownership.selectionstrategy; + +import static org.junit.Assert.assertEquals; +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.Map; +import org.junit.Test; + +public class LeastLoadedCandidateSelectionStrategyTest { + + @Test + public void testLeastLoadedStrategy(){ + LeastLoadedCandidateSelectionStrategy strategy = new LeastLoadedCandidateSelectionStrategy(0L); + + String owner = strategy.newOwner(prepareViableCandidates(3), new HashMap()); + assertEquals("member-1", owner); + + // member-2 has least load + owner = strategy.newOwner(prepareViableCandidates(3), prepareStatistics(5,2,4)); + assertEquals("member-2", owner); + + // member-3 has least load + owner = strategy.newOwner(prepareViableCandidates(3), prepareStatistics(5,7,4)); + assertEquals("member-3", owner); + + // member-1 has least load + owner = strategy.newOwner(prepareViableCandidates(3), prepareStatistics(1,7,4)); + assertEquals("member-1", owner); + + } + + private Map prepareStatistics(long... count){ + Map statistics = new HashMap<>(); + for(int i=0;i prepareViableCandidates(int count){ + Collection viableCandidates = new ArrayList<>(); + for(int i=0;i