Methods and apparatus for systems providing distributed expression evaluation over streams

Patent metadata

Field	Value
Publication number	US-9934326-B1
Application number	US-201514674087-A
Country	US
Kind code	B1
Filing date	Mar 31, 2015
Priority date	Mar 31, 2015
Publication date	Apr 3, 2018
Grant date	Apr 3, 2018

Abstract

Methods and apparatus for distributed evaluation of expressions defined by a domain model including classes with attributes and relationships among the classes. Messages containing attribute updates are sent and processed using vertex-centric graph processing technique to evaluate expressions and determine a state of the system.

First claim

What is claimed is:

1. A method, comprising:
processing a domain model of a system, the domain model including classes having attributes including relationship, external, and computed, wherein vertices for the system correspond to a respective one of the classes;
generating a semantic model as an instantiation of the domain model;
loading topology information based on the instantiation of the domain model and the relationship attributes;
processing updates of the attributes;
sending messages to a target vertex based on the processing of the updates of the attributes;
determining the node in the semantic model that corresponds to the class of the target vertex;
for each message for the target vertex;
determining a semantic model node that corresponds to the expression described in the message as a first expression;
updating the first expression;
finding expressions that depend on the first expression;
for each dependent expression;
 determining whether the found dependent expression is in the same class as the first expression;
 creating a new output message for a dependent vertex when the found dependent expression is not in the same class as the first expression;
 for the found dependent expression in the same class as the first expression:
 re-evaluating the found dependent expression;
 adding to a list of messages to be processed for a vertex corresponding to where the re-evaluated found dependent expression changes value; and
 generating a new external message if the found dependent expression is marked for export; and

processing further attribute updates,
wherein at least one of the relationships includes a hint as to whether first and second ones of the classes on either end of an associate relationship should share a vertex representation.

2. The method according to claim 1 , wherein at least one of the relationships includes a cardinality comprising an expected size of the relationship and classes on either end of the relationship are combined when the cardinality is one on one end of the relationships and is less than a fixed threshold on the other side of the relationships.

3. The method according to claim 1 , wherein an output message for a dependent vertex is sent as a difference between the old and new values of an attribute.

4. The method according to claim 1 , wherein the classes include storage devices, volumes, and storage pools.

5. The method according to claim 1 , wherein the data storage system comprises a data center environment having elastic converged storage.

6. The method according to claim 1 , further including optimizing the domain model.

7. The method according to claim 1 , wherein the classes include storage device having an external input as read bandwidth.

8. The method according to claim 1 , further including sending in a message a difference value for an attribute update.

9. A system, comprising:
components coupled via a at least one network, the components including a memory and a processor configured to:
process a domain model of a data storage system, the domain model including classes having attributes including relationship, external, and computed, wherein vertices for the data storage system correspond to a respective one of the classes;
generate a semantic model from an instantiation of the domain model based upon a topology of the data storage system to determine the vertices;
load topology information from the instantiation of the domain model and the relationships;
process updates of the attributes;
send messages to a target vertex based on the processing of the updates of the attributes;
determine a semantic model for a class of the target vertex;
for each message for the target vertex;
determine a semantic model for the target vertex for the message, wherein the semantic model has a first expression;
update the first expression;
find expressions that depend on the first expression;
determine whether the found dependent expressions are in the same class as the first expression;
create a new output message for a dependent vertex when the found dependent expressions are not in the same class as the first expression;
for the found dependent expressions in the same class as the first expression:

re-evaluate the found dependent expressions;
add to a list of messages to be processed for a vertex corresponding to where the re-evaluated found dependent expressions changes value;
generate a new external message if the found dependent expressions are marked for export; and

process further attribute updates,
wherein at least one of the relationships includes a cardinality comprising an expected size of the relationship and classes on either end of the relationship are combined when the cardinality is 1 on one end of the relationships and is less than a fixed threshold on the other side of the relationships.

10. The system according to claim 9 , wherein at least one of the relationships includes a hint as to whether first and second ones of the classes on either end of an associate relationship should share a vertex representation.

11. The system according to claim 9 , wherein data for the relationships are fed in as external input.

12. The system according to claim 9 , wherein the classes include storage devices, volumes, and storage pools.

13. The system according to claim 9 , wherein the data storage system comprises a data center environment having elastic converged storage.

14. An article, comprising
a non-transitory storage medium having stored instructions that enable a machine to:
process a domain model of a data storage system, the domain model including classes having attributes including relationship, external, and computed, wherein vertices for the data storage system correspond to a respective one of the classes;
generate a semantic model from an instantiation of the domain model based upon a topology of the data storage system to determine the vertices;
load topology information from the instantiation of the domain model and the relationships;
process updates of the attributes;
send messages to a target vertex based on the processing of the updates of the attributes;
determine a semantic model for a class of the target vertex;
for each message for the target vertex;
determine a semantic model for the target vertex for the message, wherein the semantic model has a first expression;
update the first expression;
find expressions that depend on the first expression;
determine whether the found dependent expressions are in the same class as the first expression;
create a new output message for a dependent vertex when the found dependent expressions are not in the same class as the first expression;
for the found dependent expressions in the same class as the first expression:

re-evaluate the found dependent expressions;
add to a list of messages to be processed for a vertex corresponding to where the re-evaluated found dependent expressions changes value;
generate a new external message if the found dependent expressions are marked for export; and

process further attribute updates,
wherein an output message for a dependent vertex is sent as a difference between the old and new values of an attribute.

15. The article according to claim 14 , wherein at least one of the relationships includes a cardinality comprising an expected size of the relationship.

16. The article according to claim 14 , wherein at least one of the relationships includes a hint as to whether first and second ones of the classes on either end of an associate relationship should share a vertex re

Assignees

• Emc Corp
• Emc Ip Holding Co Llc

Inventors

• Ohsie David
• Lam Cheuk

Classifications

• H04L43/0888

  Throughput · CPC title

• G06F17/30091

  Physics · mapped topic

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• G06F17/30958 Primary

  Physics · mapped topic

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title