helix-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kisho...@apache.org
Subject git commit: Adding Api support to build custom state machine with constraints
Date Thu, 01 Nov 2012 23:12:33 GMT
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.kishore@gmail.com>
Authored: Thu Nov 1 16:05:51 2012 -0700
Committer: Kishore Gopalakrishna <g.kishore@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);
+  }
+}


Mime
View raw message