Transcript IncQUERy-D: Distributed Incremental Model Queries

Incremental Model Queries for DSLs
Dániel Varró
Budapest University of Technology and Economics
Fault Tolerant Systems Research Group
Budapest University of Technology and Economics
Department of Measurement and Information Systems
Outline of the Talk
 Main Contributors
Motivation:
Validation of Design Rules
The EMF-IncQuery Project
Language
Execution
DSL Tools in an Avionics Project
View maintenance
Outlook
Distributed + incremental
Benchmarks
o
o
o
o
o
o
o
o
o
o
o
o
István Ráth
Ákos Horváth
Gábor Bergmann
Ábel Hegedüs
Zoltán Ujhelyi
Benedek Izsó
Zoltán Szatmári
Gábor Szárnyas
Dénes Harmath
Csaba Debreceni
Gergely Varró
And many more…
Motivation: Early validation of design rules
SystemSignalGroup design rule (from AUTOSAR)
o A SystemSignal and
its group must be in the same IPdu
AUTOSAR:
• standardized SW architecture
o Challenge: find violations
quickly in large models
of the automotive industry
o New difficulties • now supported by modern modeling tools
• reverse
navigation
• complex
manual
solution
Design Rule/Well-formedness constraint:
• each valid car architecture needs to respect
• designers are immediately notified if violated
Challenge:
• >500 design rules in AUTOSAR tools
• >1 million elements in AUTOSAR models
• models constantly evolve by designers
Application
Model size
System models
108
Sensor data
109
Geospatial models
1012
INCREMENTAL MODEL QUERIES:
THE EMF-INCQUERY PROJECT
EMF-IncQuery: An Open Source Eclipse Project
• Declarative graph query
language
• Transitive closure,
Negative cond., etc.
• Compositional, reusable
• Incremental evaluation
• Cache result set
• Maintain incrementally
upon model change
Definition
Execution
• Derived features,
• On-the-fly validation
• View generation,
Notifications, Soft links,
Databinding,
Features
http://eclipse.org/incquery
The IncQuery (IQ) Graph Query Language
ch: Channel
logSignal
phySignal
logical
ls: LogicalSignal
physical
m: Mapping
pattern invalidMapping(m: Mapping) = {
Mapping.logical(m, ls);
LogicalSignal(ls);
Channel.logSignal(ch,ls);
Channel(ch);
Mapping.physical(m,ps);
PhysicalSignal(ps);
neg find phySignal(ch, ps);
}
pattern phySignal(Ch, Ps) = {
Channel.phySignal(Ch, Pss);
}
ps: PhysicalSignal
 IQ: declarative query language
o
o
o
o
o
o
Attribute constraints
Local + global queries
Compositionality+Reusabilility
Recursion, Negation,
Transitive Closure
Syntax: DATALOG style
ModelQuery(A,B):
• tuples of model elements A, B
• satisfying the query condition
• enumerate 1 / all instances
• A,B can be input or output
EMF-INCQUERY
Pattern matcher (RETE algorithm)
• Stores partial results
Transaction
• Propagates changes
Pros
• Extremely fast query time
Rete
• Scales independently from
network
model size
Indexer
Change management
Model
In-memory storage
Cons
• Memory usage
when large result set?
• Large change set?
Incremental Query Evaluation by RETE
Communication
channel
antijoin
Logical signal
Mapping
Physical signal
join
Result set
join
Read the changes in the
Fill
the
worker
nodes
Propagate
Fill
thethe
input
the
changes
nodes
Read
Modify
the
result
model
set
result set (deltas)
Invalid model
Valid model
Performance of EMF-INCQUERY
 Incremental graph queries based on Rete
 Models in the Eclipse Modeling Framework
runtimeLargest real model
(Eclipse 4.0 source code)
• 8.6M nodes+26.2M edges
• revalidation: <20 ms
(except for 1 query)
Largest synthetic model
batch (TrainBenchmark)
• 2.8 million nodes
queries • 11.2 million edges
• revalidation time: 1 ms
Exec. time is proportional to
the size of the modification.
incremental
queries
model size
Performance of EMF-INCQUERY
memory
consumption
Storing partial
results
incremental
queries
memory
limit
batch
queries
model size
Selected Applications (EMF-IncQuery)
• Complex traceability
• Query driven views
• Abstract models by
derived objects
• Connect to Matlab
Simulink model
• Export: Matlab2EMF
• Change model in EMF
• Re-import:
EMF2Matlab
• Live models
(refreshed 25
frame/s)
• Complex event
processing
Toolchain for
IMA configs
MATLAB-EMF
Bridge
Gesture
recognition
• Experiments on open
source Java projects
• Local search vs.
Incremental vs.
Native Java code
• Rules for operations
• Complex structural
constraints (as GP)
• Hints and guidance
• Potentially infinite
state space
• Itemis (developer)
• Ericsson
• Embraer, Thales
• ThyssenKrupp, ARTOP
• CERN
Detection of
bad code smells
Design Space
Exploration
Known Users
MODEL DRIVEN DEVELOPMENT OF
ARINC 653 CONFIGURATION TABLES
Recent Project
Goal: Allocate SW components to
ARINC653 compliant IMA platform
Component
database
Functional
Architecture
Platform
description
Allocation
Integrated
System
Model
13
Model Driven Development of IMA Configs
Inputs:
• Platform Independent Model (PIM)
(functional + nonfunc. reqs; Simulink)
• Platform Description Model (PDM)
for ARINC 653 (DSML)
Component
database
Functional
Architecture
Platform
description
Allocation
Output:
• Integrated system model
• Ready for simulation
• End-to-end traceability
Integrated
System
Model
Model Driven Development of IMA Configs
Model transformation chains:
• Designer-guided manual steps
• Automated steps
• design space exploration
• optimization
• code generators
• incremental view maintenance
• Continuous validation of design rules
Capture
constraints
Automate
consequences
Explore
alternatives
Human
decision
Component
database
Functional
Architecture
Platform
description
Allocation
Integrated
System
Model
Incremental View Maintenance
 Avionics R&D project
o Model-driven toolchain
o Allocate SWs onto platform
 Chaining of views
PilotControl
Simulink
tag: func
SubS1
SubS2
Navigation
tag: func
Id
Other SubSystem without tag
Port Blocks
InPort/OutPort
FAM_EMS
: Function
consumer
FAM_Navigation
: Function
tag: func
provider
nav2ems
:InformationLink
View
tag: func
Function SubSystem with "func" tag)
FAM
subFunctions
EMS
FMS
Id
FAM_PilotControl
: Function
consumer
FAM_FMS
: Function
id:Function
provider
id:InformationLink
EMS: Engine Management System
FMS: Flight Management System
16
nav2fms
:InformationLink
Maintanence
Maintenance:
• Incrementally
• Immediately
INCQUERY-D: DISTRIBUTED
INCREMENTAL MODEL QUERIES
From EMF-INCQUERY to INCQUERY-D
EMF-INCQUERY
Production network
• Stores intermediate query results
• Propagates changes
Transaction
Rete net
Indexer
layer
Indexing
In-memory
EMF model
In-memory storage
INCQUERY-D Architecture
INCQUERY-D
Distributed production network
• Each intermediate node can be allocated
to a different host
• Remote internode communication
Transaction
Rete net
Indexer
layer
Database
shard 0
Server 0
Distributed query evaluation network
Distributed indexer
Database
shard 1
Server
1
Distributed
persistent
storage
Model access adapter
Database
shard 2
Server 2
Distributed indexing,
Database
notification
shard 3
Server 3
Conclusions
PERFORMANCE BENCHMARKS
Model Validation: The Train Benchmark
 Model validation workload:
 Models:
o User edits the model
o Instant validation of
well-formedness constraints
o Model is repaired accordingly
 Scenario:
o
o
o
o
o
o
o
o
o
Randomly generated
Close to real world instances
Following different metrics
Customized distributions
Low number of violations
 Queries:
Load
Check
Edit
Re-Check
o Two simple queries
(<2 objects, attributes)
o Two complex queries
(4-7 joins, negation, etc.)
o Validated match sets
Batch validation
Instance
model
Read
Check
Incremental validation
!
Edit

ReCheck
100x

What Tools are Compared?
Re-validation time (complex queries)
Characteristic
difference
(note the log scale)
http://incquery.net/publications/trainbenchmark for more details