SpeQTr Language Syntax
This document provides detailed information about the syntax and capabilities of the SpeQTr language.
# Table of Contents
# Event Patterns
Event patterns are the building blocks for the SpeQTr language. Each of the blocks in a specification contains an event pattern. Queries are essentially just made up of event patterns, with the additional ability to calculate aggregates.
This section covers the basics of event patterns. For further functionality covering more complex scenarios see the advanced features.
# Basic Structure
An event pattern describes the events it should match, and how those events are connected.
event@timeline AS a FOLLOWED BY event@timeline FOLLOWED BY event@timeline
Each event is described using the event name and the timeline where it should occur. Event and timeline name are patterns which can include *
or ?
as wildcards in the style of glob. Additionally, the event and timeline ids may be directly used, in case you don't have the name or the id is more convenient.
The event may be optionally labeled using AS
, for use elsewhere. It may also specify additional constraints beyond the event and timeline; see below for details.
Events are joined using relationship connectives, such as ->
or FOLLOWED BY
(which are synonyms). These may also be further modified, for example to require the two events to occur within a given time window. See below for details.
# Example Pattern
Here's an example event pattern:
12@* AS ev1 FOLLOWED BY my_event@*(_.payload > 12) AS ev2
In this example, 12@*
is used to identify all nodes in the causal graph where an event with id 12 was logged. Similarly, my_event@*
is used to identify nodes where the logged event has the specified name. It has an additional predicate which restricts it to only events with a payload greater than 12. These matched nodes are associated with their respective labels, ev1
and ev2
.
# Event Relationships (Paths)
A pattern can specify multiple events, constraining the matches using structural constraints between them. All relationship constraints are based on these basic causal relationships:
FOLLOWED BY
(or->
)PRECEDED BY
(or<-
)
These operate on labeled events to constrain the query results to those where the events occur in the given causal order. For example:
event1@timeline FOLLOWED BY event2@timeline
# Time-Limited Relationships
If you have added wall-clock time information to your events, you can use that in a relationship constraint. Constraints can be specified as WITHIN <time>
or AFTER <time>
, immediately following the causal relationship (i.e. ->
). The time-based relationship constraints are:
FOLLOWED BY WITHIN <time>
(or-> WITHIN <time>
)FOLLOWED BY AFTER <time>
(or-> AFTER <time>
)PRECEDED BY WITHIN <time>
(or<- WITHIN <time>
)PRECEDED BY AFTER <time>
(or<- AFTER <time>
)
Here is a simple example of a time-based relationship constraint:
ev1@timeline FOLLOWED BY WITHIN 1 ms ev2@timeline
The supported time units are:
MINUTES
orm
SECONDS
ors
MILLISECONDS
orms
MICROSECONDS
orus
NANOSECONDS
orns
Note
Time-limited relationships only consider events with the timestamp
attribute. In addition, they only work for events which share a common time domain, which is specified when you initialize the timeline. Events on the same timeline always share a common time domain. Time-limited relationships can work across timelines if you have made special accommodations for time synchronization between them (in a way that meets your system requirements) and have appropriately initialized the relevant timelines with the same time domain id.
Alternatively, you can use the --with-lax-causality
option to override this limitation and trust all timestamps in specification or query evaluation. Use caution—using this option without synchronizing your system clocks can lead to unstable results due to clock drift.
# Step Limits
You can limit the distance between matches in the causal graph using WITHIN <n> STEPS
and AFTER <n> STEPS
. These combine with the basic relationship constraint in the same way as time-based constraints. The full list is:
FOLLOWED BY WITHIN <n> STEPS
(or-> WITHIN <n> STEPS
)FOLLOWED BY AFTER <n> STEPS
(or-> AFTER <n> STEPS
)PRECEDED BY WITHIN <n> STEPS
(or<- WITHIN <n> STEPS
)PRECEDED BY AFTER <n> STEPS
(or<- AFTER <n> STEPS
)
For example, this will match any two causally connected events within three steps of each other:
ev1@timeline FOLLOWED BY WITHIN 3 STEPS ev2@timeline
Note
While step limits are useful for narrowing down a query during debugging, they are inherently somewhat fragile. When you add additional instrumentation you could easily invalidate the structural assumptions made by some query using step limits. As such, you should avoid using step limits for specifications or systems whose instrumentation is likely to change.
# Event Predicates
When matching an event, an additional predicate may be provided to further restrict the matches beyond just the event name/id and timeline.
event@timeline(<predicate>)
An event predicate is an expression that is evaluated against a candidate event in the causal graph to determine if it should be included as a match to the relevant event pattern. It should evaluate to a boolean value; true
means the event is included, while false
means it is not. In the event predicate, the symbol _
is bound to each candidate event; the various attributes are available using object-style .
notation, such as _.payload
. Predicates can use any attribute defined on an event or its timeline. Timeline attributes are accessed with the prefix _.timeline.
, e.g. _.timeline.run_id
.
# Operators
Event predicates use typical operators:
- Boolean operators:
AND
,OR
,NOT
- Comparison:
=
,!=
,<
,>
,<=
,>=
- Arithmetic:
+
,-
,*
,/
,ABS
- Existence:
exists(_.some_attr)
to check the existence of an attribute
The equality operator =
is also used for glob-matching: all strings can be compared with a glob pattern that uses the *
and ?
characters as wildcards, such as "prefix*suffix"
. *
matches any number of wildcard characters, while ?
matches a single wildcard character.
# Specifications
Specifications in Conform use a syntax which naturally lends itself to describing system behavior and requirements. Each specification is made up of one or more behavior
s, and each behavior
contains one or more case
s, as well as a single optional when
block.
Here is an example of a complete specification. Each part is explained further below:
behavior "Example behavior"
when "A message is sent"
sent_message@worker AS sent
end
nominal case "The message is received"
sent FOLLOWED BY received_message@monitor
end
recovery case "Message retry"
sent FOLLOWED BY retry_message@worker FOLLOWED BY received_message@monitor
end
prohibited case "Connection lost"
connection_lost@monitor
end
end
Note
The examples below are extremely simple for demonstration purposes. The constituent parts of specifications are event patterns and can be arbitrarily complex, including the advanced features below. For more examples of common specifications see the cookbook.
# behavior
Behaviors are the outermost unit of a specification. A specification must have at least one behavior. There is no maximum number of behaviors for a specification. Like all blocks, a behavior must have a name after the opening keyword and is terminated with the keyword end
.
# nominal case
Each behavior can have any number of nominal case
blocks inside it. As the name suggests, a nominal case
is used to describe the expected behavior of the system when everything runs smoothly. If any nominal case is matched (and no prohibited cases match), the behavior passes.
The content inside a nominal case
block is simply an event pattern. This event pattern has access to variables assigned with AS
from other blocks. Like all blocks, a nominal case
must have a name after the opening keyword and is terminated with the keyword end
.
behavior "Nominal behavior"
nominal case "Observe success"
success@controller
end
end
# recovery case
Each behavior can have any number of recovery case
blocks inside it. A recovery case
is used to describe the expected behavior of the system for successful remediation of some condition. Since it represents correct handling of an adverse situation, if any recovery case is matched (and no prohibited cases match), the behavior passes.
The content inside a recovery case
block is simply an event pattern. This event pattern has access to variables assigned with AS
from other blocks. Like all blocks, a recovery case
must have a name after the opening keyword and is terminated with the keyword end
.
behavior "Recovery behavior"
recovery case "Handle error"
error_corrected@controller
end
end
The ability to access variables assigned from other blocks is particularly useful in recovery cases. For nominal cases which contain a sequence of events, it allows you to essentially describe "escape hatch" behavior at various points of the sequence. Note that, since the variable name refers to the specific matched instance of the event where the name is assigned, whatever preconditions were specified for the variable still apply when it is used later.
behavior "Escape hatch recovery cases"
when "Sequence begins"
begin@controller AS Begin
end
nominal case "Sequence proceeds normally"
Begin FOLLOWED BY
second@controller AS Second FOLLOWED BY
third@subsystem AS Third FOLLOWED BY
fourth@controller AS Fourth
end
recovery case "Begin escape hatch"
Begin FOLLOWED BY begin_remediation@controller
end
recovery case "Second event escape hatch"
Second FOLLOWED BY second_remediation@controller
end
recovery case "Third event escape hatch"
Third FOLLOWED BY remediation@subsystem FOLLOWED BY fourth@controller
end
end
# prohibited case
Each behavior can have any number of prohibited case
blocks inside it. A prohibited case
is used to describe system behavior that should never happen. If any prohibited case is matched, even if a nominal case
or recovery case
is also matched, the behavior fails.
The content inside a prohibited case
block is simply an event pattern. This event pattern has access to variables assigned with AS
from other blocks. Like all blocks, a prohibited case
must have a name after the opening keyword and is terminated with the keyword end
.
behavior "Failure behavior"
prohibited case "Failure"
failure@controller
end
end
# when
Each behavior can optionally have a single when
block. The when
block changes the semantics of a behavior so that its case
s are evaluated each time the pattern in the when
block occurs. If a behavior does not have a when
block, it only needs to find a match to a single nominal or recovery case in the entire set of data under consideration to pass. Thus, having a when
block in a behavior is like changing it from checking whether a matching case exists anywhere to checking for a matching case for each occurrence of the when
pattern.
Another way to think about the effect of a when
block is that it creates sub-regions of data for which the behavior is evaluated. If you evaluate a behavior against a single segment, one match to a nominal or recovery case anywhere in that segment (and no matches to prohibited cases) will cause that behavior to succeed. If that behavior has a when
block, however, a match to a nominal or recovery case is required in each region delimited by the when
for the behavior to pass.
A when
block can only contain either a single event (e.g. event@timeline
) or a path matching exactly two events (e.g. event1@timeline FOLLOWED BY event2@timeline
). For a single event, the cases are evaluated for each region beginning at that event and ending at the next occurrence of that event. For a path between two events, the cases are evaluated for each region beginning at the first event and ending at the second event.
Like all blocks, a when
must have a name after the opening keyword and is terminated with the keyword end
.
behavior "When behavior"
when "Landing command is sent"
initiate_landing@commander AS init_land
end
nominal case "Landing succeeds"
init_land FOLLOWED BY landing@flight_control FOLLOWED BY landing_succeeded@commander
end
recovery case "Emergency landing"
init_land FOLLOWED BY emergency_landing@flight_control FOLLOWED BY landing_succeeded@commander
end
end
# Comments
You can use the #
character to write single line comments.
# Metadata
Specifications can optionally include doxygen-like key-value metadata to help you organize and manage them. The key space is free-form. You can put metadata at the very top of a specification document to apply to the entire specification. You can also put metadata on individual behaviors or cases.
# @author = "phil"
# @project = "documentation"
# @type = "example"
behavior "Example behavior"
when "A message is sent"
sent_message@worker AS sent
end
# @requirement_id = 3
nominal case "The message is received"
sent FOLLOWED BY received_message@monitor
end
# @requirement_id = 7
# @category = "remediation"
recovery case "Message retry"
sent FOLLOWED BY retry_message@worker FOLLOWED BY received_message@monitor
end
# @requirement_id = 9
# @category = "failure"
prohibited case "Connection lost"
connection_lost@monitor
end
end
# Evaluating Specifications
Evaluating specifications generates a pass or fail result, either for the entire set of data under consideration or for each region delimited by the when
block. For a specification to pass the region under consideration must contain at least one match to either a nominal case
or a recovery case
, and there must be no matches to any prohibited case
. If there are no matches to a case of any kind, the specification fails, since this represents unspecified behavior.
# Queries
For the most part, queries are nothing more than event patterns describing the events of interest. Patterns can be given directly to the modality query
(opens new window) command, which will find events which match the pattern. For example:
*@timeline1 AS a FOLLOWED BY *@timeline2 AS b AND a.payload = b.payload
This query will find all instances of an event on timeline1 followed by an event on timeline2 with the same payload. The advanced features discussed below supplement the basic event patterns section above.
When writing a query, you also have access to the aggregation facilities using the AGGREGATE
keyword:
*@* AS a
AGGREGATE std_dev(a.payload) AS payload_stddev
See the aggregation section for details.
# Advanced Features
The discussion of event patterns above covers the most commonly used features. This section covers further considerations in building event patterns.
# Negative Lookahead
A negative relationship with nothing else after it behaves like a lookahead operator. For example, suppose you want to identify errors which are not followed by a remediation event inside a suitable time window:
*@*(_.tag='error') NOT FOLLOWED BY WITHIN 5 ms *@*(_.tag='remediation')
The negative relationship operators are:
NOT FOLLOWED BY
(or!->
)NOT PRECEDED BY
(or<-!
)
Note that the event matched by the right-hand side of the relationship may not be labeled; there's actually nothing there to find, since this is specifying what should not be present.
# Negative Path Constraints
You can similarly specify a negative constraint to be applied on the path between two events. For example, you might want to look for pairs of startup and shutdown events that don't have an error signaled on the path between them:
startup@p AS a NOT FOLLOWED BY *@*(_.tag='error') FOLLOWED BY shutdown@p AS b
The syntax is similar to negative lookahead, but the subsequent FOLLOWED BY
means that it will apply to any nodes found between the events a
and b
. There don't have to be any events there: this query will match even if a
is directly followed by b
, with nothing in between.
# CROSSING ANY
By default, each relationship matches only the nearest events in either direction. More precisely, it will not match a pair of events if any of the events on the path between them could have been a match. This is the most intuitive behavior most of the time; we refer to it as local reasoning.
There may be times when you want to indicate all possible pairs of matching events regardless of the events on the path between them. This is done using CROSSING ANY
.
For example, if you want to match ALL the possible b
s for every a
, you could write:
a@timeline AS a FOLLOWED BY CROSSING ANY b@timeline AS b
# Adding Multi-Event Predicates
Additional predicate expressions may be added to an event pattern to further constrain matches, especially based on some predicate involving multiple matched events. These expressions use the label assigned to the event using AS
, instead of the _
character.
This gives the filter expression access to multiple events at the same time. For example, you might want to find causal pairs of events with the same payload as each other:
*@* AS a FOLLOWED BY *@* AS b
AND a.payload = b.payload
# External Predicates With Local Reasoning
When using AND
to add additional predicates to an event pattern, you should be aware of the local reasoning that is used for all relationships by default (see the crossing any section). You can use this with external predicates to express some unique queries.
This is best explained by example. Suppose you wanted to find ground_contact
events where the most recent accelerometer reading is above a certain threshold:
ground_contact@control AS a <- acceleration@control AS b
AND b.payload > 12.0
This will first match pairs of ground_contact
and acceleration
events as described, and then limit those matches to only the pairs where the acceleration
event has the correct payload.
If the payload constraint was inside the event predicate for acceleration
this would have an entirely different meaning:
ground_contact@control AS a <- acceleration@control(_.payload > 12.0) AS b
This would match the most recent acceleration
event with the desired payload, with respect to the ground contact event, but there could be other more recent acceleration events (with payload <= 12) on the path between them.
# CONCURRENT Paths
Events and relationships alone are sufficient to match trace-like patterns, which consist of a single path through the causal graph. But many systems have behaviors which cannot be described this simply.
A very common kind of complex system behavior is parallel execution with synchronization points. Events logged by such systems can be matched using CONCURRENT WITH
event patterns.
This is best described by example:
start@common FOLLOWED BY (a1@a FOLLOWED BY a2@a CONCURRENT WITH b1@b FOLLOWED BY b2@b) FOLLOWED BY end@common
In this example, the two event patterns a1@a FOLLOWED BY a2@a
and b1@b FOLLOWED BY b2@b
are causally independent of each other. But they must both be causally preceded by a single event which matches start@common
, and followed by a single event which matches end@common
.
If you want to add additional restrictions to the edges going into or out of the CONCURRENT WITH
block, you can do so by adding labels and using AND
:
start@common as common_start FOLLOWED BY (a1@a as a_start FOLLOWED BY a2@a CONCURRENT WITH b1@b FOLLOWED BY b2@b) FOLLOWED BY end@common
AND common_start FOLLOWED BY WITHIN 10 ms a_start
# Combining Paths
If you want to match complex patterns which do not fit the CONCURRENT WITH
model, you can do so by describing them as multiple paths which AND
with each other, using common labels to indicate intersection points. For example:
source_1@p1 FOLLOWED BY meet@center AS meet
AND source_2@p2 FOLLOWED BY meet
Note that the meet
label is used in both paths: this means that the two matches are unified. meet
has to be the same event in both paths; graphically it's a "V" pattern. Modality will search for ways to choose three events such that ALL the given relationships are satisfied.
Note
One common misinterpretation of this is to view them as 'shortcuts' to match multiple events using the same condition. This is not correct. Each time you reuse an event label you're applying a new constraint to the same event. So each time you talk about event a
, it's always the same a
within a single match for the event pattern.
# Aggregation
The SpeQTr language has aggregation functionality to allow you to calculate aggregate functions over matched event patterns.
Aggregation works very similarly to aggregation in other query languages. You can specify aggregations over previous results, do some computations with them, and give them names.
For example:
*@* AS a
AGGREGATE std_dev(a.payload) AS payload_stddev
This will compute the standard deviation of the payload value for all events, naming it payload_stddev
in the aggregation result. Any events that do not have a payload will be skipped when computing the aggregation.
The parameter to each aggregate function is an expression with access to all matched events.
*@* AS a FOLLOWED BY *@* AS b
AGGREGATE std_dev(a.payload - b.payload) AS payload_diff_stddev
You can also do computations with the results of multiple aggregations:
*@* AS a FOLLOWED BY *@* AS b
AGGREGATE (min(a.payload) - min(b.payload)) / 2 AS min_payload_avg
# Aggregate Functions
count()
: Count the number of results. Unlike the other aggregates, this one doesn't have an expression argument.min(...)
,max(...)
: Compute the minimum or maximum value of the expression.sum(...)
,mean(...)
: Compute the sum or mean of the expression.distinct(...)
: Return the set of distinct values taken on by the expression.count_distinct(...)
: Return the number of distinct values taken on by the expression.variance(...)
,std_dev(...)
: Calculate the variance or standard deviation of the expression.