You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@helix.apache.org by ki...@apache.org on 2012/11/02 00:12:33 UTC
git commit: Adding Api support to build custom state machine with
constraints
Updated Branches:
refs/heads/master 8569d9ee8 -> 2bf431507
Adding Api support to build custom state machine with constraints
Project: http://git-wip-us.apache.org/repos/asf/incubator-helix/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-helix/commit/2bf43150
Tree: http://git-wip-us.apache.org/repos/asf/incubator-helix/tree/2bf43150
Diff: http://git-wip-us.apache.org/repos/asf/incubator-helix/diff/2bf43150
Branch: refs/heads/master
Commit: 2bf431507a8451bdad6879a8ed2fd6318251940a
Parents: 8569d9e
Author: Kishore Gopalakrishna <g....@gmail.com>
Authored: Thu Nov 1 16:05:51 2012 -0700
Committer: Kishore Gopalakrishna <g....@gmail.com>
Committed: Thu Nov 1 16:05:51 2012 -0700
----------------------------------------------------------------------
.../controller/stages/MessageSelectionStage.java | 2 +-
.../java/org/apache/helix/model/IdealState.java | 3 +
.../org/apache/helix/model/NextStateFinder.java | 184 --------------
.../apache/helix/model/StateModelDefinition.java | 188 +++++++++++++--
.../java/org/apache/helix/model/Transition.java | 46 ++++
.../statemachine/StateTransitionTableBuilder.java | 179 ++++++++++++++
6 files changed, 398 insertions(+), 204 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-helix/blob/2bf43150/helix-core/src/main/java/org/apache/helix/controller/stages/MessageSelectionStage.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/stages/MessageSelectionStage.java b/helix-core/src/main/java/org/apache/helix/controller/stages/MessageSelectionStage.java
index dd864cc..00cbe17 100644
--- a/helix-core/src/main/java/org/apache/helix/controller/stages/MessageSelectionStage.java
+++ b/helix-core/src/main/java/org/apache/helix/controller/stages/MessageSelectionStage.java
@@ -41,7 +41,7 @@ public class MessageSelectionStage extends AbstractBaseStage
{
private static final Logger LOG = Logger.getLogger(MessageSelectionStage.class);
- static class Bounds
+ public static class Bounds
{
private int upper;
private int lower;
http://git-wip-us.apache.org/repos/asf/incubator-helix/blob/2bf43150/helix-core/src/main/java/org/apache/helix/model/IdealState.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/model/IdealState.java b/helix-core/src/main/java/org/apache/helix/model/IdealState.java
index ff74395..0cc0f01 100644
--- a/helix-core/src/main/java/org/apache/helix/model/IdealState.java
+++ b/helix-core/src/main/java/org/apache/helix/model/IdealState.java
@@ -313,4 +313,7 @@ public class IdealState extends HelixProperty
}
return true;
}
+ public static class Builder{
+
+ }
}
http://git-wip-us.apache.org/repos/asf/incubator-helix/blob/2bf43150/helix-core/src/main/java/org/apache/helix/model/NextStateFinder.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/model/NextStateFinder.java b/helix-core/src/main/java/org/apache/helix/model/NextStateFinder.java
deleted file mode 100644
index ea7952e..0000000
--- a/helix-core/src/main/java/org/apache/helix/model/NextStateFinder.java
+++ /dev/null
@@ -1,184 +0,0 @@
-package org.apache.helix.model;
-
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-
-public class NextStateFinder
-{
- public static class Transition
- {
- final String _fromState;
- final String _toState;
-
- public Transition(String fromState, String toState)
- {
- _fromState = fromState;
- _toState = toState;
- }
- }
-
- // for convenient get path value, in which non-exist means MAX
- static int getPathVal(Map<String, Map<String, Integer>> path, String fromState, String toState)
- {
- if (!path.containsKey(fromState))
- {
- return Integer.MAX_VALUE;
- }
-
- if (!(path.get(fromState).containsKey(toState)))
- {
- return Integer.MAX_VALUE;
- }
-
- return path.get(fromState).get(toState);
- }
-
- static void setPathVal(Map<String, Map<String, Integer>> path, String fromState, String toState,
- int val)
- {
- if (!path.containsKey(fromState))
- {
- path.put(fromState, new HashMap<String, Integer>());
- }
-
- path.get(fromState).put(toState, val);
- }
-
- static void setNext(Map<String, Map<String, String>> next, String fromState, String toState, String nextState)
- {
- if (!next.containsKey(fromState))
- {
- next.put(fromState, new HashMap<String, String>());
- }
-
- next.get(fromState).put(toState, nextState);
-
- }
-
- /**
- * auxiliary method to get next state based on next map
- *
- * @param next
- * @param fromState
- * @param toState
- * @return nextState or null if doesn't exist a path
- */
- public static String getNext(Map<String, Map<String, String>> next, String fromState, String toState)
- {
- if (!next.containsKey(fromState))
- {
- // no path
- return null;
- }
-
- return next.get(fromState).get(toState);
- }
-
- // debug
- static void printPath(List<String> states, Map<String, Map<String, String>> next)
- {
- for (String fromState : states)
- {
- for (String toState : states)
- {
- if (toState.equals(fromState))
- {
- // not print self-loop
- continue;
- }
-
- System.out.print(fromState);
- String nextState = getNext(next, fromState, toState);
- while (nextState != null && !nextState.equals(toState))
- {
- System.out.print("->" + nextState);
- nextState = getNext(next, nextState, toState);
- }
-
- if (nextState == null)
- {
- // no path between fromState -> toState
- System.out.println("->null" + toState + " (no path avaliable)");
- } else
- {
- System.out.println("->" + toState);
- }
- }
- }
- }
-
- /**
- * floyd-warshall
- *
- * @param states
- * @param transitions
- * @return next map
- */
- public static Map<String, Map<String, String>> findNextState(List<String> states,
- List<Transition> transitions)
- {
- // path distance value
- Map<String, Map<String, Integer>> path = new HashMap<String, Map<String, Integer>>();
-
- // next state
- Map<String, Map<String, String>> next = new HashMap<String, Map<String, String>>();
-
- // init path and next
- for (String state : states)
- {
- setPathVal(path, state, state, 0);
- setNext(next, state, state, state);
- }
-
- for (Transition transition : transitions)
- {
- String fromState = transition._fromState;
- String toState = transition._toState;
- setPathVal(path, fromState, toState, 1);
- setNext(next, fromState, toState, toState);
- }
-
- // iterate
- for (String intermediateState : states)
- {
- for (String fromState : states)
- {
- for (String toState : states)
- {
- int pathVal1 = getPathVal(path, fromState, intermediateState);
- int pathVal2 = getPathVal(path, intermediateState, toState);
- int pathValCur = getPathVal(path, fromState, toState);
-
- // should not overflow
- if (pathVal1 < Integer.MAX_VALUE && pathVal2 < Integer.MAX_VALUE
- && (pathVal1 + pathVal2) < pathValCur)
- {
- setPathVal(path, fromState, toState, pathVal1 + pathVal2);
- setNext(next, fromState, toState, intermediateState);
- }
- }
- }
- }
-
- return next;
- }
-
- public static void main(String[] args)
- {
- List<String> states = new ArrayList<String>();
- states.add("OFFLINE");
- states.add("SLAVE");
- states.add("MASTER");
-
- List<Transition> transitions = new ArrayList<Transition>();
- transitions.add(new Transition("OFFLINE", "SLAVE"));
- transitions.add(new Transition("SLAVE", "MASTER"));
- transitions.add(new Transition("MASTER", "SLAVE"));
- transitions.add(new Transition("SLAVE", "OFFLINE"));
-
- Map<String, Map<String, String>> next = findNextState(states, transitions);
- printPath(states, next);
- }
-}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-helix/blob/2bf43150/helix-core/src/main/java/org/apache/helix/model/StateModelDefinition.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/model/StateModelDefinition.java b/helix-core/src/main/java/org/apache/helix/model/StateModelDefinition.java
index 4f01aac..f10251c 100644
--- a/helix-core/src/main/java/org/apache/helix/model/StateModelDefinition.java
+++ b/helix-core/src/main/java/org/apache/helix/model/StateModelDefinition.java
@@ -19,15 +19,18 @@ package org.apache.helix.model;
* under the License.
*/
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import org.apache.helix.HelixProperty;
import org.apache.helix.ZNRecord;
+import org.apache.helix.participant.statemachine.StateTransitionTableBuilder;
import org.apache.log4j.Logger;
-
/**
* Describe the state model
*/
@@ -35,11 +38,11 @@ public class StateModelDefinition extends HelixProperty
{
public enum StateModelDefinitionProperty
{
- INITIAL_STATE,
- STATE_TRANSITION_PRIORITYLIST,
- STATE_PRIORITY_LIST
+ INITIAL_STATE, STATE_TRANSITION_PRIORITYLIST, STATE_PRIORITY_LIST
}
- private static final Logger _logger = Logger.getLogger(StateModelDefinition.class.getName());
+
+ private static final Logger _logger = Logger
+ .getLogger(StateModelDefinition.class.getName());
/**
* State Names in priority order. Indicates the order in which states are
* fulfilled
@@ -69,9 +72,12 @@ public class StateModelDefinition extends HelixProperty
{
super(record);
- _statesPriorityList = record.getListField(StateModelDefinitionProperty.STATE_PRIORITY_LIST.toString());
+ _statesPriorityList = record
+ .getListField(StateModelDefinitionProperty.STATE_PRIORITY_LIST
+ .toString());
_stateTransitionPriorityList = record
- .getListField(StateModelDefinitionProperty.STATE_TRANSITION_PRIORITYLIST.toString());
+ .getListField(StateModelDefinitionProperty.STATE_TRANSITION_PRIORITYLIST
+ .toString());
_stateTransitionTable = new HashMap<String, Map<String, String>>();
_statesCountMap = new HashMap<String, String>();
if (_statesPriorityList != null)
@@ -114,7 +120,8 @@ public class StateModelDefinition extends HelixProperty
public String getInitialState()
{
- return _record.getSimpleField(StateModelDefinitionProperty.INITIAL_STATE.toString());
+ return _record.getSimpleField(StateModelDefinitionProperty.INITIAL_STATE
+ .toString());
}
public String getNumInstancesPerState(String state)
@@ -125,23 +132,166 @@ public class StateModelDefinition extends HelixProperty
@Override
public boolean isValid()
{
- if(getInitialState() == null)
+ if (getInitialState() == null)
{
- _logger.error("State model does not contain init state, statemodel:" + _record.getId());
+ _logger.error("State model does not contain init state, statemodel:"
+ + _record.getId());
return false;
}
- if(_record.getListField(StateModelDefinitionProperty.STATE_PRIORITY_LIST.toString()) == null)
+ if (_record.getListField(StateModelDefinitionProperty.STATE_PRIORITY_LIST
+ .toString()) == null)
{
- _logger.error("CurrentState does not contain StatesPriorityList, state model : " + _record.getId());
+ _logger
+ .error("CurrentState does not contain StatesPriorityList, state model : "
+ + _record.getId());
return false;
}
-
- // STATE_TRANSITION_PRIORITYLIST is optional
-// if(_record.getListField(StateModelDefinitionProperty.STATE_TRANSITION_PRIORITYLIST.toString()) == null)
-// {
-// _logger.error("CurrentState does not contain StateTransitionPriorityList, state model : " + _record.getId());
-// return false;
-// }
return true;
}
+
+ /**
+ *
+ *
+ */
+ public static class Builder
+ {
+ private final String _statemodelName;
+ private String initialState;
+ Map<String, Integer> statesMap;
+ Map<Transition, Integer> transitionMap;
+ Map<String, String> stateConstraintMap;
+
+ public Builder(String name)
+ {
+ this._statemodelName = name;
+ statesMap = new HashMap<String, Integer>();
+ transitionMap = new HashMap<Transition, Integer>();
+ stateConstraintMap = new HashMap<String, String>();
+ }
+
+ /**
+ * initial state of a replica when it starts, most commonly used initial
+ * state is OFFLINE
+ *
+ * @param state
+ */
+ public void initialState(String initialState)
+ {
+ this.initialState = initialState;
+
+ }
+
+ /**
+ * Define all valid states using this method. Set the priority in which the
+ * constraints must be satisfied. Lets say STATE1 has a constraint of 1 and
+ * STATE2 has a constraint of 3 but only one node is up then Helix will uses
+ * the priority to see STATE constraint has to be given higher preference <br/>
+ * Use -1 to indicates states with no constraints, like OFFLINE
+ *
+ * @param states
+ */
+ public void addState(String state, int priority)
+ {
+ statesMap.put(state, priority);
+ }
+
+ /**
+ * Define all legal transitions between states using this method. Priority
+ * is used to order the transitions. Helix tries to maximize the number of
+ * transitions that can be fired in parallel without violating the
+ * constraint. The transitions are first sorted based on priority and
+ * transitions are selected in a greedy way until the constriants are not
+ * violated.
+ *
+ * @param fromState
+ * @param toState
+ * @param priority
+ */
+ public void addTransition(String fromState, String toState, int priority)
+ {
+ transitionMap.put(new Transition(fromState, toState), priority);
+ }
+
+ public void upperBound(String state, int upperBound)
+ {
+ stateConstraintMap.put(state, String.valueOf(upperBound));
+ }
+
+ /**
+ * You can use this to have the bounds dynamically change based on other
+ * parameters. Currently support 2 values R --> Refers to the number of
+ * replicas specified during resource creation. This allows having different
+ * replication factor for each resource without having to create a different
+ * state machine. N --> Refers to all nodes in the cluster. Useful for
+ * resources that need to exist on all nodes. This way one can add/remove
+ * nodes without having the change the bounds.
+ *
+ * @param state
+ * @param bound
+ */
+ public void dynamicUpperBound(String state, String bound)
+ {
+ stateConstraintMap.put(state, bound);
+ }
+
+ public StateModelDefinition build()
+ {
+ ZNRecord record = new ZNRecord(_statemodelName);
+ ArrayList<String> statePriorityList = new ArrayList<String>(
+ statesMap.keySet());
+ Comparator<? super String> c1 = new Comparator<String>()
+ {
+
+ @Override
+ public int compare(String o1, String o2)
+ {
+ return statesMap.get(o1).compareTo(statesMap.get(o2));
+ }
+ };
+ Collections.sort(statePriorityList, c1);
+ ArrayList<String> transitionPriorityList = new ArrayList<String>(
+ transitionMap.size());
+ for (Transition t : transitionMap.keySet())
+ {
+ transitionPriorityList.add(t.toString());
+ }
+ Comparator<? super String> c2 = new Comparator<String>()
+ {
+
+ @Override
+ public int compare(String o1, String o2)
+ {
+ return statesMap.get(o1).compareTo(statesMap.get(o2));
+ }
+ };
+ Collections.sort(transitionPriorityList, c2);
+
+ record.setSimpleField(
+ StateModelDefinitionProperty.INITIAL_STATE.toString(), initialState);
+ record.setListField(
+ StateModelDefinitionProperty.STATE_PRIORITY_LIST.toString(),
+ statePriorityList);
+ record
+ .setListField(
+ StateModelDefinitionProperty.STATE_TRANSITION_PRIORITYLIST
+ .toString(), transitionPriorityList);
+ StateTransitionTableBuilder stateTransitionTableBuilder = new StateTransitionTableBuilder();
+ Map<String, Map<String, String>> transitionTable = stateTransitionTableBuilder
+ .buildTransitionTable(statePriorityList, new ArrayList<Transition>(
+ transitionMap.keySet()));
+ for (String state : transitionTable.keySet())
+ {
+ record.setMapField(state + ".next", transitionTable.get(state));
+ }
+ for (String state : stateConstraintMap.keySet())
+ {
+ HashMap<String, String> metadata = new HashMap<String, String>();
+ metadata.put("count", stateConstraintMap.get(state));
+ record.setMapField(state + ".meta", metadata);
+ }
+ return new StateModelDefinition(record);
+ }
+
+ }
+
}
http://git-wip-us.apache.org/repos/asf/incubator-helix/blob/2bf43150/helix-core/src/main/java/org/apache/helix/model/Transition.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/model/Transition.java b/helix-core/src/main/java/org/apache/helix/model/Transition.java
new file mode 100644
index 0000000..ac2619c
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/model/Transition.java
@@ -0,0 +1,46 @@
+package org.apache.helix.model;
+
+public class Transition
+{
+ final private String _fromState;
+ final private String _toState;
+
+ public Transition(String fromState, String toState)
+ {
+ _fromState = fromState;
+ _toState = toState;
+ }
+
+ @Override
+ public String toString()
+ {
+ return _fromState + "-" + _toState;
+ }
+
+ @Override
+ public int hashCode()
+ {
+ return toString().hashCode();
+ }
+
+ @Override
+ public boolean equals(Object that)
+ {
+ if (that == null || !(that instanceof Transition))
+ {
+ return false;
+ }
+ return this.toString().equalsIgnoreCase(that.toString());
+ }
+
+ public String getFromState()
+ {
+ return _fromState;
+ }
+
+ public String getToState()
+ {
+ return _toState;
+ }
+
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-helix/blob/2bf43150/helix-core/src/main/java/org/apache/helix/participant/statemachine/StateTransitionTableBuilder.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/participant/statemachine/StateTransitionTableBuilder.java b/helix-core/src/main/java/org/apache/helix/participant/statemachine/StateTransitionTableBuilder.java
new file mode 100644
index 0000000..c731b40
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/participant/statemachine/StateTransitionTableBuilder.java
@@ -0,0 +1,179 @@
+package org.apache.helix.participant.statemachine;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.helix.model.Transition;
+
+public class StateTransitionTableBuilder
+{
+ // for convenient get path value, in which non-exist means MAX
+ static int getPathVal(Map<String, Map<String, Integer>> path,
+ String fromState, String toState)
+ {
+ if (!path.containsKey(fromState))
+ {
+ return Integer.MAX_VALUE;
+ }
+
+ if (!(path.get(fromState).containsKey(toState)))
+ {
+ return Integer.MAX_VALUE;
+ }
+
+ return path.get(fromState).get(toState);
+ }
+
+ static void setPathVal(Map<String, Map<String, Integer>> path,
+ String fromState, String toState, int val)
+ {
+ if (!path.containsKey(fromState))
+ {
+ path.put(fromState, new HashMap<String, Integer>());
+ }
+
+ path.get(fromState).put(toState, val);
+ }
+
+ static void setNext(Map<String, Map<String, String>> next, String fromState,
+ String toState, String nextState)
+ {
+ if (!next.containsKey(fromState))
+ {
+ next.put(fromState, new HashMap<String, String>());
+ }
+
+ next.get(fromState).put(toState, nextState);
+
+ }
+
+ /**
+ * auxiliary method to get next state based on next map
+ *
+ * @param next
+ * @param fromState
+ * @param toState
+ * @return nextState or null if doesn't exist a path
+ */
+ public static String getNext(Map<String, Map<String, String>> next,
+ String fromState, String toState)
+ {
+ if (!next.containsKey(fromState))
+ {
+ // no path
+ return null;
+ }
+
+ return next.get(fromState).get(toState);
+ }
+
+ // debug
+ static void printPath(List<String> states,
+ Map<String, Map<String, String>> next)
+ {
+ for (String fromState : states)
+ {
+ for (String toState : states)
+ {
+ if (toState.equals(fromState))
+ {
+ // not print self-loop
+ continue;
+ }
+
+ System.out.print(fromState);
+ String nextState = getNext(next, fromState, toState);
+ while (nextState != null && !nextState.equals(toState))
+ {
+ System.out.print("->" + nextState);
+ nextState = getNext(next, nextState, toState);
+ }
+
+ if (nextState == null)
+ {
+ // no path between fromState -> toState
+ System.out.println("->null" + toState + " (no path avaliable)");
+ } else
+ {
+ System.out.println("->" + toState);
+ }
+ }
+ }
+ }
+
+ /**
+ * Uses floyd-warshall algorithm, shortest distance for all pair of nodes
+ * Allows one to lookup nextState given fromState,toState <br/>
+ * map.get(fromState).get(toState) --> nextState
+ * @param states
+ * @param transitions
+ * @return next map
+ */
+ public Map<String, Map<String, String>> buildTransitionTable(List<String> states,
+ List<Transition> transitions)
+ {
+ // path distance value
+ Map<String, Map<String, Integer>> path = new HashMap<String, Map<String, Integer>>();
+
+ // next state
+ Map<String, Map<String, String>> next = new HashMap<String, Map<String, String>>();
+
+ // init path and next
+ for (String state : states)
+ {
+ setPathVal(path, state, state, 0);
+ setNext(next, state, state, state);
+ }
+
+ for (Transition transition : transitions)
+ {
+ String fromState = transition.getFromState();
+ String toState = transition.getToState();
+ setPathVal(path, fromState, toState, 1);
+ setNext(next, fromState, toState, toState);
+ }
+
+ // iterate
+ for (String intermediateState : states)
+ {
+ for (String fromState : states)
+ {
+ for (String toState : states)
+ {
+ int pathVal1 = getPathVal(path, fromState, intermediateState);
+ int pathVal2 = getPathVal(path, intermediateState, toState);
+ int pathValCur = getPathVal(path, fromState, toState);
+
+ // should not overflow
+ if (pathVal1 < Integer.MAX_VALUE && pathVal2 < Integer.MAX_VALUE
+ && (pathVal1 + pathVal2) < pathValCur)
+ {
+ setPathVal(path, fromState, toState, pathVal1 + pathVal2);
+ setNext(next, fromState, toState, intermediateState);
+ }
+ }
+ }
+ }
+
+ return next;
+ }
+
+ public static void main(String[] args)
+ {
+ List<String> states = new ArrayList<String>();
+ states.add("OFFLINE");
+ states.add("SLAVE");
+ states.add("MASTER");
+
+ List<Transition> transitions = new ArrayList<Transition>();
+ transitions.add(new Transition("OFFLINE", "SLAVE"));
+ transitions.add(new Transition("SLAVE", "MASTER"));
+ transitions.add(new Transition("MASTER", "SLAVE"));
+ transitions.add(new Transition("SLAVE", "OFFLINE"));
+ StateTransitionTableBuilder builder = new StateTransitionTableBuilder();
+ Map<String, Map<String, String>> next = builder.buildTransitionTable(states, transitions);
+ printPath(states, next);
+ }
+}