Trigger Logic and Regex Overlapping

In our last posts, we have talked about that we are interested in if the possible output is able to trigger the input condition.

The expected output and input condition are key-value pairs connected with logical operators (&&, ||, !). We define the output expression as A, and input as B, and we are wondering of their is an implication between them (A->B).

On a high perspective view, we have 4 possibilities between A and B

Complete Trigger. If A happens, B must happen (A->B)

Possible Trigger. If a set of certain cases of A happens (A can be A1||A2||A3…), B must happen in any environment (A-?>B)

Partial Trigger. If a set of certain cases of A happens, B can happen under a certain environment (A–>B), which means A is not enough to trigger B alone but it does contribute.

Irrelevant. A and B are completely irrelevant. (A-!>B)

To prove A->B, Automated Theorem Proving is applied. However, a simple deduction (A->B) can only help distinguish the complete trigger from the rest. To differentiate the possible trigger from the last two, we have to transform the output expression to a Disjunctive Normal Form (A1|A2|…|Ai), if any Ai -> B, then it satisfies the definition of a possible trigger. To tell apart a partial trigger from irrelevant needs even more computation, my method is to transfer the input condition into a Conjunctive Normal Form (B1&B2…&Bj), if any Ai->Bj, we know it is a partial trigger. Otherwise the output and input are irrelevant.

In order to create Axioms for theorem proving, we have to compare the values belongs to the same keys, the values can be either a constant string or a regular expression. And the challenge is to find out the overlaps between two regular expressions.

As a solution, we can transfer regular expressions to Deterministic Finite Automatons (DFAs) and derive their intersections.

A DFA is a five tuple (Q, Σ, ð, q0, F)

Q is a finite set called the state

Σ is a finite set called the alphabet

ð is the transition function

q0 is the start state and

F is the set of accept state

Here is a concrete example explains how it works.

regex 1 : [ch]at, regex 2: [^b]at

Obviously there are only two words matches both expression, they are hat and cat.

If we transfer the two regex to DFA, they will become

DFA 1 :

initial state: 3
state 0 [reject]:
t -> 1
state 1 [accept]:
state 2 [reject]:
a -> 0
state 3 [reject]:
c -> 2
h -> 2

DFA 2 :

initial state: 3
state 0 [accept]:
state 1 [reject]:
t -> 0
state 2 [reject]:
a -> 1
state 3 [reject]:
\u0000-a -> 2
c-\uffff -> 2

We can see that DFA 1 is enclosed by DFA 2. So the intersection is DFA 1.

Leave a comment

UI, Programming Model Design

UI

The latest choice to create an interactive UI is DOT Language + Grappa Applet + JSP + Jersey Framework. However, Grappa doesn’t support automatically layout a DOT file, the graph formatting relies on the external invoking of GraphViz tool, which could be a potential issue for our cloud server. In the worst case we have to revert back to a static/non-interactive UI. We keep it as simple as possible temporarily.

Graph design can be more specific, e.g. the node shape and line style should follow the workflow description model.

Programming Model Design (3 layers)

Layer 1:

Storlet Code, provides the basic functionality/template of the storlet, which is created by programmer. As a user, the hard coded part is a black box and immutable.

Layer 2:

Trigger Evaluator, which specifies the trigger condition in a special logical operation. This part defines both the input and output logic expression. It is not required for a end-user to understand the logic, but a user can always add extra conditions for strengthen the constraints.

Layer 3:

Variable, which expose the interfaces from layer 2. A common user just need to know what is this storlet used for, and simply specify those variables. Basically, the variables are inputkey, inputvalue, outputkey, outputvalue.

Somehow, there might be multiple outputkey and outputvalue for a single storlet, in that case, we assume the output can be any combination of these keys and values.

 

Next Step:

Create  well designed use cases (cover most cases), and plot them with my UI

Study workflow description model, and apply it to my UI.

Leave a comment

Visualization Tool, Graph Design & User Interaction

DOT Language Specification

DOT supports subgraphs clustering, all nodes in the same subgraph could have the same node and edge attributes. additionally they can be clustered in one group. These two features facilitates the representing of multiple handlers belongs to a single storlet. I will explain it in the following graph design part.

DOT language also support HTML like attribute, and flexible syntax.

Grappa

Since the original web service framework is in Java, I switched to Grappa, a java graph visualization framework, which support DOT language and user interaction.

Graph Design

Each node are created as a single handler of a storlet, it is good for cycle detection, because cycles are happened in handler level but not storlet. The annotations of a node may contain the information of storlet and handler. Edges between the handler may represent the satisfied condition of a trigger condition.

User Interaction

To design the UI and programming model, first step is to analyze the possible user interaction.

1. Visualize the storlets/handlers relations of a container

2. Add a storlet, specify the handler, specify the parameter, then the service will check if it connects to the target storlet hander

3. After a new storlet is created and just before injection, check if there is any possible cycles, shortcut duplication, overlapping

4. Take snapshot of a workflow and migrate to other containers

Currently investigating on Jersey web service framework, reading the existing APIs of the system, which is used to access to storlets information of a container.

Leave a comment

Graph Description Language and Programming Package

Currently we decided to use DOT Language as default. Two more formats, GML and GraphML are also popular languages. It is not a big problem to translate between other languages, since our graph is small in each container (30 nodes in general)

DOT

graph graphname {
// This attribute applies to the graph itself
size="1,1";
// The label attribute can be used to change the label of a node
a [label="Foo"];
// Here, the node shape is changed.
b [shape=box];
// These edges both have different line properties
a -- b -- c [color=blue];
b -- d [style=dotted];
}

  • Attributed and direct graphs
  • The language is straight forward, users could have a brief impression of the graph without plotting it out.
  • It is widely supported in graph programming packages

GML

graph [
comment "This is a sample graph"
directed 1
id 42
label "Hello, I am a graph"
node [
id 1
label "node 1"
thisIsASampleAttribute 42
]
node [
id 2
label "node 2"
thisIsASampleAttribute 43
]
edge [
source 1
target 2
label "Edge from node 1 to node 2"
]
]

  • ASCII for simplicity and portability
  • Attributed and direct graphs
  • Simple structure
  • Extensibility and flexibility
  • Representation of graphs

GraphML

<graphml xmlns="http://graphml.graphdrawing.org/xmlns"  
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns
     http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
  <graph id="G" edgedefault="undirected">
    <node id="n0"/>
    <node id="n1"/>
    <edge id="e1" source="n0" target="n1"/>
  </graph>
</graphml>
  • XML format, good for transforming
  • Attributed, direct, and hierarchical graphs
  • Graphical representation
  • Application specified attribute data

NetworkX is elected as the preliminary graph programming package, besides pygraph and graph-tool are also very powerful libraries. Network is chosen because it support all three languages mentioned above, it provides powerful graph statistic analysis algorithms, especially the cycle detection api greatly facilitate our work. Instead, pygraph only returns the first cycle it detects and graph-tool only support DOT language, which is a serious limit. NetworkX usually associates with mabplotlib or pygraphviz for plotting graphs, both of them provides python APIs. However, the interface of the existing system are generally in java. It would be great to have a java plotting tool supplies more graph annotation features.

A quick Demo of cycle detection and graph plotting here

Brain Storm

Keep workflow of storlets information as objects in VISION Cloud, for migration to other container and restoration from corrupt workflows.

However, I think if we can have all required annotations stored in the graph, migration and restoring can be done with the existing and snapshots of graphs.

Next Step:

  • Have a deeper look at LOG Language (some syntax are not very clear in the presentation 😦 )
  • Look for visualization tool satisfies:
    • Java API
    • Support Cycle Detection
    • Support interactive visualization
    • Support DOT and more language (at least Dot)
    • Good Annotation Functionality
  • Consider what kind of annotations to store
  • What to do with the graph

Leave a comment

Master Thesis Kick-off

It is my 3rd day at SICS to do my master thesis.

Let’s start from a description of my tasks and possible approaches.

My thesis is a part of the VISION Cloud project of SICS.

VISION Cloud is a powerful information and communication technology (ICT)
infrastructure, which efficiently supports data-intensive storage service. Additionally, it
facilitates the convergence of ICT, and supplies the on-demand storage service with a
competitive cost while the QoS and security are guaranteed.

My task is related to the “storlet”, which is the execution unit of the computational storage in VISION Cloud. These computations are typically data-centric, i.e., analyzing or transcoding newly uploaded or updated data objects in the cloud.

A storlet is created by the tenant and stored in the storlet library as a wrapped component. Whenever a user performs computations in the cloud, he fetches the appropriate storlets, specifies the trigger conditions and injects them into the cloud storage. The trigger event could be any state change of the storage state, which is reflected by the update of data object metadata. A storlet might remain in passive state until it is triggered by certain event, then it becomes active and starts operation. Eventually, when the operation is completed, it turns to passive again.

Image

storlet life cycle

There are many use cases relies on the storlets mentioned above, e.g. media transcoding, Telco and health care. Most of the use case requirements expect an interface allowing to inject a chain/workflow of storlets automatically. However, the current implementation of this computational storage doesn’t support this feature. The only chance to connect two storlets is to predict the output of the first storlet manually and set an appropriate trigger condition for the second. Additionally, even connected storlets might form cycles, overlaps or starving.

Before discussing about the approaches, it is better to have a brief view of the logical storlet runtime

storlet runtime

storlet runtime

Whenever a new storlet is injected into the cloud, its trigger information is extracted and registered in the Notification Service (NS). When a state change of a data object happens, the Object Service (ObS) sends the event to the NS. The NS then check its registration, if some trigger conditions match the event, the registered storlet is triggered to become active.

Since the output of a storlet might trigger another one, we treat the storlets distributed as a graph. However, the triggers between storlets are indirect, some mechanism is required to generate the graph.

Static Method:

Produce an algorithm to extract and predict the input and output information based on the storlet programming model (a new model with the properties is by design right now), analyze all possible connections and definitely not possible connections, then generate a potential graph.

Advantage:

  • All potential issues would be discovered before new storlets injected.
  • Definitely not possible connection information is useful when isolating storlets.
  • Helps to exclude the possibility of cycling for failure detection.

Disadvantages:

  • Big overhead, analyze possible input and output is expensive.
  • Change the programming model is a challenge.

Dynamic Method:

Use a machine learning algorithm to generate graph dynamically with trigger event logs.

Advantage:

  • Efficient problem detector, able to kill storlets while cycling is noticed.
  • policies of injecting storlets can be learned heuristically by cycles are observed under certain situations.
  • Verification for static analysis

Disadvantage:

  • Rare completely secure injection of storlet.
  • Not friendly to user when storlets killed automatically.

Comment:

Two approaches are complementary, it is possible to have both. However, it depends on the discussion result of new storlet programming model next Monday. :p

TO BE CONTINUED…

, ,

Leave a comment

FTS project update – Estimate RRT

The round trip time is estimated roughly in this version of my program.

I use GeoIP APIs to tell if the source and destination pair are from the same country, same continent or different continent.

And set a specific RRT to each case.

Globus APIs doesn’t return RRT for each underlying command, and only RETR command is interacted between source and destination servers, the rest are all about client and servers.

From the experiment, I tested this approach with several different rough RRT, and they all converge to a good result eventuality.

Since in half to one year, the RRT of third party transfer monitoring mechanism will be implemented in FTS, we can obtain more accurate optimal result at that time.

,

Leave a comment

FTS Optimization Update

Most time spent on looking for a possible source-destination pair accept third party transfervia globus-url-copy, and support a big number of parallel TCP streams. Finally it is solved 🙂

Here comes to the update of my program

1.

Last version: Default input parameters are Bandwidth and RRT (Round Trip Time)

New version: Default input parameters are RRT, TCP Socket Buffer Size, Number of streams.

Reason: It is more intuitive since bandwidth is not easy to estimate at very beginning without any information. Choose a more proper default configuration avoids exceeding.

2.

Last version: New estimated bandwidth is derived by current goodput * number of streams

New version: Bandwidth equals current goodput (unit changed)

Reason: It was a mistake, the goodput is already a sum of all streams.

Expectation of the algorithm, the derived number of streams and buffer size converge to an optimal domain, regardless of the first guess of bandwidth, but a relatively closed RRT is required. (ex. If the best number of streams is 50, it drifting between 40 – 60).

Furthermore, to experiment with multiple default RRT and choose the best one is a good approach to me, because the current infrastructure doesn’t provide RRT in a 3rd party transfer. But if the default RRT is too far from the real RRT, the algorithm makes result converge to another domain because of the inaccurate RRT.

In terms of simultaneous transfer, it highly depands on the memory management of the system. My task is to figure out if the optimal number of streams (connections) is 100, what is the best combination of simultaneous transfers and number of streams.

simultaneous transfers * number of streams = 100

Now, have a nice weekend to Lausanne !!!!

,

Leave a comment