Tuesday, January 31, 2012

Deaths and confessions

Following up on an earlier note, let's look at the Carp package. It's a standard part of modern Perl, so all you need to do is just say

use Carp;

It provides the smarter ways to report the fatal errors found in the libraries. The problem with the simple die() is that it reports an error but prints only the location where it has been called, which may be ten layers deep inside a library,  not a full stack trace. The functions in Carp fix that. The most interesting one is confess(). It works just like die() but prints the whole stack trace.

The full description of Carp is available at http://perldoc.perl.org/Carp.html.It has more functions: for warnings, and to report only the location of the call from the user code to the library.  However I find a full stack trace more helpful in any case.

Monday, January 30, 2012

Tables and labels

A table does not have to be operated in a procedural way. It can be plugged into the the scheduler machinery. Whenever a table is created, two labels are created with it.

The input label is for sending the modification rowops to the table.  The table provides the handler for it that applies the incoming rowops to the table. The output label propagates the modifications done to the table.  It is a dummy label, and does nothing by itself. It's there for chaining the other labels to it. The output rowop comes quite handy to propagate the table's modifications to the rest of the state.

Note that the rowops coming through these two labels aren't necessarily the same. If a DELETE rowop comes to the input label, referring to a row that is not in the table, it will not propagate. If an INSERT rowop comes in and causes another row to be replaced, the replaced row will be sent to the output label as a DELETE rowop first.

Well, if you need to look up records from the table, the look-ups are still done in the procedural way by calling the table methods.

So, let's make a version of "Hello, table" example that passes the records through the labels. Since it will print the information about the updates to the table as they happen, there is no more use having a separate command for that. But for another demonstration let's add a command that would clear the counter. And, without further introduction, here is the code:

my $hwunit = Triceps::Unit->new("hwunit") or die "$!";
my $rtCount = Triceps::RowType->new(
  address => "string",
  count => "int32",
) or die "$!";

my $ttCount = Triceps::TableType->new($rtCount)
  ->addSubIndex("byAddress",
    Triceps::IndexType->newHashed(key => [ "address" ])
  )
or die "$!";
$ttCount->initialize() or die "$!";

my $tCount = $hwunit->makeTable($ttCount, &Triceps::EM_CALL, "tCount") or die "$!";

my $lbPrintCount = $hwunit->makeLabel($tCount->getRowType(),
  "lbPrintCount", undef, sub { # (label, rowop)
    my ($label, $rowop) = @_;
    my $row = $rowop->getRow();
    print(&Triceps::opcodeString($rowop->getOpcode), " '",
      $row->get("address"), "', count ", $row->get("count"), "\n");
  } ) or die "$!";
$tCount->getOutputLabel()->chain($lbPrintCount) or die "$!";

# the updates will be sent here, for the tables to process
my $lbTableInput = $tCount->getInputLabel();

while(<STDIN>) {
  chomp;
  my @data = split(/\W+/);

  # the common part: find if there already is a count for this address
  my $pattern = $rtCount->makeRowHash(
    address => $data[1]
  ) or die "$!";
  my $rhFound = $tCount->find($pattern) or die "$!";
  my $cnt = 0;
  if (!$rhFound->isNull()) {
    $cnt = $rhFound->getRow()->get("count");
  }

  if ($data[0] =~ /^hello$/i) {
    $hwunit->schedule($lbTableInput->makeRowop(&Triceps::OP_INSERT,
      $lbTableInput->getType()->makeRowHash(
        address => $data[1],
        count => $cnt+1,
      ))
    ) or die "$!";
  } elsif ($data[0] =~ /^clear$/i) {
    $hwunit->schedule($lbTableInput->makeRowop(&Triceps::OP_DELETE,
      $lbTableInput->getType()->makeRowHash(address => $data[1]))
    ) or die "$!";
  } else {
    print("Unknown command '$data[0]'\n");
  }
  $hwunit->drainFrame();
}

Here is an example of input (in cursive) and output:

Hello, table!
OP_INSERT 'table', count 1
Hello, world!
OP_INSERT 'world', count 1
Hello, table!
OP_DELETE 'table', count 1
OP_INSERT 'table', count 2
clear, table
OP_DELETE 'table', count 2
Hello, table!
OP_INSERT 'table', count 1

The references to the input and output labels of a table are gotten with:

$label = $table->getInputLabel();
$label = $table->getOutputLabel();

The output label in this example then gets another label chained to it, the one that prints what is coming to it. The input label receives a translation of the commands coming from the user.

The inserts work in a fairly straightforward way. The deletes require only the key to be populated. Internally a delete really translates to a find, followed by the removal of the record if it was found (more on the details of that later).

As you can see in the  example output, when the first record for a key is inserted, it's just an insert. But when the second "hello" is received, the insert causes the old row to be deleted first, and produces a delete followed by the new insert on the table's output. Now, depending on what you want, just sending the consequent inserts of rows with the same keys, and relying on the table's internal consistency to turn them into updates, might be a good thing or not. Overall it's a dirty way to write but sometimes it comes convenient. The clean way is to do the explicit deletes first.

For the closing thought, creating these rowops through all the nested calls is fairly annoying, and could use some simplification like find() had with findBy().

Sunday, January 29, 2012

CEP: why bother?

So far I've been writing largely in assumption that the readers would have an idea of what the Complex Event Processing is, and comparing to the other existing systems. It's a decent assumption for a quick start: if people have found Triceps, they've likely come through some CEP-related links, and know, what they are looking for.

But hopefully there will be novices as well, so let me have a go at describing the basics too.

If you look at Wikipedia, it has separate articles for the Event Stream Processing and the Complex Event Processing. In reality it's all the same thing, with the naming driven by the marketing. I would not be surprised if someone invents yet another name, and everyone will start jumping on that bandwagon too.

In general a CEP system can be thought of as a black box, where the input events come in, propagate in some way through that black box, and come out as the processed output events. There is also an idea that the processing should happen fast, though the definitions of "fast" vary widely.


If we open the lid on the box, there are at least three ways to think of its contents:
  • a spreadsheet on steroids
  • a data flow machine 
  • a database driven by triggers

Hopefully you've seen a spreadsheet before. The cells in it are tied together by formulas. You change one cell, and the machine goes and recalculates everything that depends on it. So does a CEP system. If we look closer, we can discern the CEP engine (which is like the spreadsheet software), the CEP model (like the formulas in the spreadheet) and the state (like the current values in the spreadsheet).  An incoming event is like a change in an input cell, and the outgoing events are the updates of the values in the spreadsheet. Only a CEP system hand handle some very complicated formulas and many millions of records. There actually are products that connect the Excel spreadsheets with the behind-the-curtain computations in a CEP system, with the results coming back to the spreadsheet cells.  Pretty much every commercial CEP provider has a product that does that through the Excel RT interface. The way these models are written are not exactly pretty, but the results are, combining the nice presentation of spreadsheets and the speed and power of CEP.

A data flow machine, where the processing elements are exchanging messages, is your typical academical look at CEP. The events represented as data rows are the messages, and the CEP model describes the connections between the processing elements and their internal logic. This approach naturally maps to the multiprocessing, with each processing element becoming a separate thread. The hiccup is that the research in the dataflow machines tends to prefer the non-looped topologies. The loops in the connections complicate the things.

And many real-world relational databases already work very similarly to the CEP systems. They have constraints and triggers propagating the constraints. A trigger propagates an update on one table to an update on another table. It's like a formula in a spreasheet or a logical connection in a dataflow graph. Yet the databases usually miss two things: the propagation of the output events and the notion of "fast". The lack of propagation of the output events is totally baffling to me: the RDBMS engines already write the output event stream as the redo log. Why not send them also in some generalized format, XML or something? Then people realize that yes, they do want to get the output events and start writing some strange add-ons and aftermarket solutions like the log scrubbers. This has been a mystery to me for some 15 years. I mean, how more obvious can it be? But nobody budges. Well, with the CEP systems gaining popularity and the need to connect them to the databases, I think it will eventually grow on the database vendors that a decent event feed is a compatitive advantage, and I think it will happen somewhere soon. The felling of "fast" or lack thereof has to do with the databases being stored on disks. The growth of CEP has concided with the growth in RAM sizes, and the data is usually kept completely in memory. People who deploy CEP tend to want the performance not of hundreds or thousands but hundreds of thousands events per second. The second part of "fast" is connected with the transactions. In a traditional RDBMS a single event with all its downstream effects is one transaction. Which is safe but may cause lots of conflicts. The CEP systems usually allow to break up the logic into multiple loosely-dependent layers, thus cutting on the overhead.

How are the CEP systems used?

Despite what Wikipedia says, the pattern detection is NOT your typical usage, by a wide, wide margin. The typical usage is for the data aggregation: lots and lots of individual events come in, and you want to aggregate them to keep a concise and consistent picture for the decision-making.  The actual decision making can be done by humans or again by the CEP systems. The usages in the uses I know of vary from ad-click aggregation to the decisions to make a market trade, or watching whether the bank's end-of-day balance falls within the regulations.

A related use would be for the general alert consoles. The data aggregation is what they do too. The last time I looked up close (around 2006), the processing in the BMC Patrol and Nagios was just plain inadequate for anything useful, and I had to hand-code the data collection and console logic. But the CEP would have been just the ticket. I think, the only reaosn why it has not been widespread yet is that the commercial CEP licenses had cost a lot. But with the all-you-can-eat pricing of Sybase, and with the OpenSource systems, this is gradually changing.

Well, and there is also the pattern matching. It has been lagging behind the aggregation but growing too.

the Hungarian notation

The Hungarian notation is the idea that the name of each variable should be prefixed with some abbreviation of its type. It has probably become most widely known from the Microsoft operating systems.

Overall it's a complete abomination and brain damage. But you can see me using it widely in the examples. Why? The problem is that there usually too many components for one logical purpose. For a table, there would be a row type, a table type, and the table itself. Rather than inventing separate names for them, it's easier to have a common name and an uniform prefix. Eventually something better would have to be done but for now I've fallen back on the Hungarian notation. Hm, would a suffix be better than prefix? Perhaps it might.

Among the CEP systems, Triceps is not unique in this department. Coral8/Sybase CCL has this mess of lots of schemas, input streams, windows and output streams, with the same naming problems. The uniform naming prefixes or suffixes help making this mess more navigable. I haven't actually used StreamBase but from reading the documentation I get the feeling that the Hungarian notation is probably useful for its SQL as well.

a simple extension for a table

When I wrote the example for the last post, I've got a bit annoyed that to look up a row in a table I had to make a pattern row manually and then search for it. It looked easy to fix: just add a method findBy() that would take the (fieldNam, fieldValue) pairs for the keys, create the row and call find(). Then the code in "Hello, table" example

my $pattern = $rtCount->makeRowHash(
  address => $data[1]
) or die "$!";
my $rhFound = $tCount->find($pattern) or die "$!";

becomes

my $rhFound = $tCount->findBy(
  address => $data[1]
) or die "$!";

Naturally, it's not in version 0.99 but will be available in 1.00. The implementation is fairly simple. There is no reason why a class can't mix the XS methods and plain Perl methods. So I've added the file lib/Triceps/Table.pm, added it to be imported in lib/Triceps.pm, and put the Perl method in there:

package Triceps::Table;
use Carp;

sub findBy # (self, fieldName => fieldValue, ...)
{
  my $self = shift;
  my $row = $self->getRowType()->makeRowHash(@_) or Carp::confess "$!";
  return $self->find($row);
}

Carp::confess() is a better kind of die(), I'll will discuss it in more detail later. Fairly simple and straightforward. If you see something missing, you can also always extend Triceps in the same way.

However if you change the Triceps code directly like I did, you'll have an issue with the next Triceps release: it woudl overwrite your file and your change would be lost. This can be solved in one of two ways. The first way is to write me an e-mail, describe your new useful change, and send me a context diff with its code. If I like it, I'll include it into the Triceps code base.

The second way comes useful if you want to keep the change to yourself, or if you sent it to me and I didn't like it: just make your own wrapper of the Table class and add the new method there. Then use your class instead of Triceps::Table. For example:

package MyTable;
our @ISA = qw(Triceps::Table);

sub new # (class, unit, args of makeTable...)
{
  my $class = shift;
  my $unit = shift;
  my $self = $unit->makeTable(@_);
  return undef unless defined $self;
  bless $self, $class;
  return $self;
}

sub myFindBy { ... }

package main;
...
my $tCount = MyTable->new(
  $hwunit, $ttCount, &Triceps::EM_CALL, "tCount") or die "$!";

That's also a simplest template: a modifying wrapper for one class.

Saturday, January 28, 2012

Hello, tables!

The tables are the basic units of statekeeping in Triceps. Let's start with a basic example.

use Triceps;

my $hwunit = Triceps::Unit->new("hwunit") or die "$!";
my $rtCount = Triceps::RowType->new(
  address => "string",
  count => "int32",
) or die "$!";

my $ttCount = Triceps::TableType->new($rtCount)
  ->addSubIndex("byAddress", 
    Triceps::IndexType->newHashed(key => [ "address" ])
  ) 
or die "$!";
$ttCount->initialize() or die "$!";

my $tCount = $hwunit->makeTable($ttCount, &Triceps::EM_CALL, "tCount") or die "$!";

while(<STDIN>) {
  chomp;
  my @data = split(/\W+/);

  # the common part: find if there already is a count for this address
  my $pattern = $rtCount->makeRowHash(
    address => $data[1]
  ) or die "$!";
  my $rhFound = $tCount->find($pattern) or die "$!";
  my $cnt = 0;
  if (!$rhFound->isNull()) { 
    $cnt = $rhFound->getRow()->get("count");
  } 

  if ($data[0] =~ /^hello$/i) { 
    my $new = $rtCount->makeRowHash(
      address => $data[1],
      count => $cnt+1,
    ) or die "$!";
    $tCount->insert($new) or die "$!";
  } elsif ($data[0] =~ /^count$/i) { 
    print("Received '", $data[1], "' ", $cnt + 0, " times\n");
  } else { 
    print("Unknown command '$data[0]'\n");
  } 
}

What happens here? The code reads the lines from standard input, uses the first word as a command and the second work as a key. It counts, how many times each key has been hello-ed, and prints this count back on the command "count".

Here the table is read and modified using the direct procedural calls. As you can see, there isn't even any need for unit scheduling and such.  There is a scheduler-based interface too, it will be shown later.  But in many cases the direct access is easier. Indeed, this particular example could have been implemented with the plain Perl hashes. Nothing wrong with that either. Well, at some future point the tables will be supporting the on-disk persistence, but no reason to bother much about that now: things are likely to change a dozen times yet before that happens. Feel free to just use the Perl data structures if they make the code easier.

A table is created through a table type. This allows to stamp out duplicate tables of the same type, which can get handy when the multithreading will be added. A table is local to a thread. A table type can be shared between threads. So the only way to look up something directly in another thread's table is to keep its local copy, which can be easily done by creating a copy table from the same type.


In reality, right now all the business with table types separated from the tables is more pain than gain. It not only adds extra steps but also makes difficult to define a template that acts on a table by defining extra features on it. Something will be done about it, I have a few ideas.

The table type gets first created and configured, then initialized. After a table type is initialized, it can not be changed any more. That's the point of the initialization call: tell the table that all the configuration has been done, and it can go immutable now. A table type must be fully initialized in one thread before it can be shared with other threads. The historic reason for this API is that it mirrors the C++ API, which has turned out not to look that good in Perl. It's another candidate for a change.

A table type gets the row type and at least one index. Here it's a hashed index by the field address. The table is then created from the table type, enqueueing mode (just use EM_CALL always, this argument will be removed in the future), and given a name.

The rows can then be inserted into the table (and removed, not shown in this example). The default behavior of the hashed index is to replace the old row if a new row with the same key is inserted.

The search in the table is done by creating a sample row with the key fields set, and then calling find() on it. Which returns a RowHandle object. A RowHandle is essentially an iterator in the table. Even if the row is not found, a RowHandle will be still returned but it will be null, which is checked for by $rh->isNull().

This is just the tip of the iceberg. The tables in Triceps have a lot more features.

Tuesday, January 24, 2012

Yes bundling

Even though Triceps does no bundling in scheduling, there still is a need to store the sequences of row operations. This is an important distinction, since the stored sequences are to be scheduled somewhere in the future (or maybe not scheduled at all, but iterated through manually). If and when they get scheduled, they will be unbundled. The ordered storage only provides the order for that future scheduling or iteration.

The easiest way to store rowops is to put them into the Perl arrays, like:

my @ops = ($rowop1, $rowop2);
push @ops, $rowop3;

However the C++ internals of Triceps do not know about the Perl arrays. And some of them work directly with the sequences of rowops. So Triceps defines an internal sort-of-equivalent of Perl array for rowops, called a Tray.

The trays have first been used to "catch" the side effects of operations on the stateful elements, so the name "tray" came from the metaphor "put a tray under it to catch the drippings".

The trays get created as:

$tray = $unit->makeTray($rowop, ...) or die "$!";

A tray always stores rowops for only one unit. It can be only used in one thread.  A tray can be used in all the scheduling functions, just like the direct rowops:

$unit->call($tray);
$unit->fork($tray);
$unit->schedule($tray);
$unit->loopAt($mark, $tray);

Moreover, the single rowops and  trays can be mixed in the multiple arguments of these functions, like:

$unit->call($rowopStartPkg, $tray, $rowopEndPkg);

In this example nothing really stops you from placing the start and end rows into the tray too. A tray may contain the rowops of any types mixed in any order. This is by design, and it's an important feature that allows to build the protocol blocks out of rowops and perform an orderly data exchange. This feature is an absolute necessity for proper inter-process and inter-thread communication.

The ability to send the rows of multiple types through the same channel in order is a must, and its lack makes the communication with some other CEP systems exceedingly difficult. Coral8 supports only one stream per connection. Aleri (and I believe Sybase R5) allows to send multiple streams through the same connection but has no guarantees of order between them. I don't know about the others, check yourself.

To iterate on a tray, it can be converted to a Perl array:

@array = $tray->toArray();

The size of the tray (the count of rowops in it) can be read directly without a conversion, and the unit can be read back too:

$size = $tray->size();
$traysUnit = $tray->getUnit();

Another way to create a tray is by copying an existing one:

$tray2 = $tray1->copy();

This copies the contents (which is the references to the rowops) and does not create any ties between the trays. The copying is really just a more efficient way to do

$tray2 = $tray1->getUnit()->makeTray($tray1->toArray());

The tray references can be checked, whether they point to the same tray object:

$result = $tray1->same($tray2);

The contents of a tray may be cleared. Which is convenient and more efficient than discarding a tray and creating another one:

$tray->clear();

The data may be added to any tray:

$tray->push($rowop, ...);

Multiple rowops can be pushed in a single call. There are no other Perl-like operations on a tray: it's either create from a set of rowops, push, or convert to Perl array.

Note that the trays are mutable, unlike the rows and rowops. Multiple references to a tray will see the same contents. If a rowop is added to a tray through one reference, it will be visible through all the others.

A Perl tracer example

For an example of what can be done with a Perl tracer, let's make a tracer function that works like UnitTracerStringName but prints the whole rowop contents too. In a "proper" way that would be an object, but to reduce the amount of code let's just make it a standalone function. It can be then used as a method of an object as well.

Note: this code has not been tested, so it might work or not work at the moment. I'll test and fix it later.

The function would take 3 extra arguments:
  • boolean: verbosity
  • reference to a variable where to append the text of the trace
  • reference to a variable that would be used to keep the chaining level

The code is as follows:

sub traceStringRowop
{
  my ($unit, $label, $fromLabel, $rowop, $when, $verbose, $rlog, $rnest) = @_;
  return if (!$verbose && $when != &Triceps::TW_BEFORE);
  ${$rnest}-- if ($when != &Triceps::TW_BEFORE);
  my $msg =  "unit '" . $unit->getName() . "' " 
    . Triceps::tracerWhenHumanString($when) . " label '"
    . $label->getName() . "' ";
  if (defined $fromLabel) {
    $msg .= "(chain '" . $fromLabel->getName() . "') ";
  }
  ${$rlog} .=  ("  " x $rnest) . $msg . "op " . $rowop->printP() . "\n";
  if ($verbose) {
    if ($when != &Triceps::TW_AFTER) {
      ${$rnest}++;
    } else {
      ${$rnest}--;
    }
  }
}

It is then supposed to be used like:

my ($traceLog, $traceNest);
$tracer = Ticeps::UnitTracerPerl->new(
  1, \&tracerStringRowop, \$traceLog, \$traceNest);

And produce the nicely formatted nested traces. For the previous example the nesting would be:

unit 'u' before label 'lab1' op ...
  unit 'u' drain label 'lab1' op ...
  unit 'u' before-chained label 'lab1' op ...
    unit 'u' before label 'lab2' (chain 'lab1') op ...
      unit 'u' drain label 'lab2' (chain 'lab1') op ...
      unit 'u' before-chained label 'lab2' (chain 'lab1') op ...
        unit 'u' before label 'lab3' (chain 'lab2') op ...
          unit 'u' drain label 'lab3' (chain 'lab2') op ...
          unit 'u' after label 'lab3' (chain 'lab2') op ...
      unit 'u' after label 'lab2' (chain 'lab1') op ...
    unit 'u' before label 'lab3' (chain 'lab1') op ...
      unit 'u' drain label 'lab3' (chain 'lab1') op ...
      unit 'u' after label 'lab3' (chain 'lab1') op ...
  unit 'u' after label 'lab1' op ...
unit 'u' before label 'lab1' op ...
  unit 'u' drain label 'lab1' op ...
  unit 'u' before-chained label 'lab1' op ...
    unit 'u' before label 'lab2' (chain 'lab1') op ...
      unit 'u' drain label 'lab2' (chain 'lab1') op ...
      unit 'u' before-chained label 'lab2' (chain 'lab1') op ...
        unit 'u' before label 'lab3' (chain 'lab2') op ...
          unit 'u' drain label 'lab3' (chain 'lab2') op ...
          unit 'u' after label 'lab3' (chain 'lab2') op ...
      unit 'u' after label 'lab2' (chain 'lab1') op ...
    unit 'u' before label 'lab3' (chain 'lab1') op ...
      unit 'u' drain label 'lab3' (chain 'lab1') op ...
      unit 'u' after label 'lab3' (chain 'lab1') op ...
  unit 'u' after label 'lab1' op ...

Each label produces two levels of nesting: one for everything after "before", another one for the nested labels. In reality this nested idea might be not that great because when a label calls another one, that will be nested, and the long call sequences may produce some very deep and unreadable nesting.

Monday, January 23, 2012

Tracing the unit execution

When developing the CEP models, there always comes the question: WTF has just happened? How did it manage get this result? Followed by subscribing to many intermediate results and trying to piece together the execution order.

Triceps provides two solutions for this situation: First, the procedural approach should make the logic much easier to follow. Second, it has a ready way to trace the execution and then read the trace in one piece. It can also be used to analyze any variables on the fly, and possibly stop the execution and enter some manual mode.

The idea here is simple: provide the Unit with a method that will be called:
  • before a label executes
  • after the label executes but before draining its frame
  • after the frame is drained but before the chained labels execute
  • after all the execution caused by a label is completed
By the way, this is a correction to the previously described execution order: it was incorrect, the chained labels are executed after draining the frame of the original label, not before it.  And this applies recursively.

For the simple tracing, there is a small simple tracer provided. It actually executes directly as compiled in C++, so it's fairly efficient:

$tracer = Triceps::UnitTracerStringName(option => value) or die "$!";

The only option supported is "verbose", which may be 0 (default) or non-0. If it's 0 (false), the tracer will record a message only before executing each label. If true, it will record a message after each stage. The class is named UnitTracerStringName because it records the execution trace in the string format, including the names of the labels. The tracer is set into the unit:

$unit->setTracer($tracer); die "$!" if ($! ne "");
$oldTracer = $unit->getTracer();

If no tracer was previously set, getTracer() will return undef. And undef can also be used as an argument of setTracer(), to cancel any previously set tracing. setTracer() is actually not done very cleanly now, because it may return an error, yet it always returns an undef. So the only way to check for an error is to check whether the string value of "$!" is empty. This will be fixed in the future.

As the unit runs, the tracing information gets collected in the tracer object. It can be extracted back with:

$data = $tracer->print();

This does not reset the trace. To reset it, use:

$tracer->clearBuffer();

Here is an example of a fairly involved verbose trace:

unit 'u' before label 'lab1' op OP_INSERT
unit 'u' drain label 'lab1' op OP_INSERT
unit 'u' before-chained label 'lab1' op OP_INSERT
unit 'u' before label 'lab2' (chain 'lab1') op OP_INSERT
unit 'u' drain label 'lab2' (chain 'lab1') op OP_INSERT
unit 'u' before-chained label 'lab2' (chain 'lab1') op OP_INSERT
unit 'u' before label 'lab3' (chain 'lab2') op OP_INSERT
unit 'u' drain label 'lab3' (chain 'lab2') op OP_INSERT
unit 'u' after label 'lab3' (chain 'lab2') op OP_INSERT
unit 'u' after label 'lab2' (chain 'lab1') op OP_INSERT
unit 'u' before label 'lab3' (chain 'lab1') op OP_INSERT
unit 'u' drain label 'lab3' (chain 'lab1') op OP_INSERT
unit 'u' after label 'lab3' (chain 'lab1') op OP_INSERT
unit 'u' after label 'lab1' op OP_INSERT
unit 'u' before label 'lab1' op OP_DELETE
unit 'u' drain label 'lab1' op OP_DELETE
unit 'u' before-chained label 'lab1' op OP_DELETE
unit 'u' before label 'lab2' (chain 'lab1') op OP_DELETE
unit 'u' drain label 'lab2' (chain 'lab1') op OP_DELETE
unit 'u' before-chained label 'lab2' (chain 'lab1') op OP_DELETE
unit 'u' before label 'lab3' (chain 'lab2') op OP_DELETE
unit 'u' drain label 'lab3' (chain 'lab2') op OP_DELETE
unit 'u' after label 'lab3' (chain 'lab2') op OP_DELETE
unit 'u' after label 'lab2' (chain 'lab1') op OP_DELETE
unit 'u' before label 'lab3' (chain 'lab1') op OP_DELETE
unit 'u' drain label 'lab3' (chain 'lab1') op OP_DELETE
unit 'u' after label 'lab3' (chain 'lab1') op OP_DELETE

In non-verbose mode the same trace would be:

unit 'u' before label 'lab1' op OP_INSERT
unit 'u' before label 'lab2' (chain 'lab1') op OP_INSERT
unit 'u' before label 'lab3' (chain 'lab2') op OP_INSERT
unit 'u' before label 'lab3' (chain 'lab1') op OP_INSERT
unit 'u' before label 'lab1' op OP_DELETE
unit 'u' before label 'lab2' (chain 'lab1') op OP_DELETE
unit 'u' before label 'lab3' (chain 'lab2') op OP_DELETE
unit 'u' before label 'lab3' (chain 'lab1') op OP_DELETE

The actual contents of the records is not printed in either case. This is basically because the tracer is implemented in C++, and I've been trying to keep the knowledge of the meaning of the simple data types out of the C++ code as much as possible for now. But it can be implemented with a Perl tracer.

A Perl tracer is created with:

$tracer = Triceps::UnitTracerPerl->new($sub, args...) or die "$!";

The arguments are a reference to a function, and optionally arguments for it. The resulting tracer can be used in the unit's setTracer() as usual.

Also the tracer references support the call same():

$result = $tracer1->same($tracer2);

They can be caller safely for either kind of tracer, including mixing them together. Of course, the tracers of different kinds definitely would not be the same tracer object.

The function of the Perl tracer gets called as:

sub($unit, $label, $fromLabel, $rowop, $when, args...)

The arguments are:
  • $unit is the usual unit reference
  • $label is the current label being traced
  • $fromLabel is the parent label in the chaining (would be undef if the current label is called directly, without chaining from anything)
  • $rowop is the current row operation
  • TW_BEFORE, Triceps::TW_BEFORE_DRAIN, Triceps::TW_BEFORE_CHAINED, Triceps::TW_AFTER), the prefix TW stands for "tracer when"
  • args are the extra arguments passed from the tracer creation
The TW constants can as usual be converted to and from strings with the calls

$string = &Triceps::tracerWhenString($value);
$value = &Triceps::stringTracerWhen($string);

There also are the conversion functions with strings more suitable for the human-readable messages: "before", "drain", "before-chained", "drain". These are actually the conversions used in the UnitTracerStringName. The functions for them are:

$string = &Triceps::tracerWhenHumanString($value);
$value = &Triceps::humanStringTracerWhen($string);

The Perl tracers allow to execute any arbitrary actions when tracing.

Wednesday, January 18, 2012

Execution Unit

After discussing the principles of scheduling in Triceps, let's get down to the nuts and bolts.

An execution unit represents one logical thread of Triceps. In some special cases more that one unit per actual thread may be useful, but never one unit shared between threads.

A unit is created as:

$myUnit = Triceps::Unit->new("name") or die "$!";

The name argument as usual is used for later debugging, and by convention should be the same as the name of the unite variable ("myUnit" in this case). The name can also be changed later:

$myUnit->setName("newName");

It returns no value. Though in practice there is no good reason for it, and this call will likely be removed in the future. The name can be received back:

$name = $myUnit->getName();

Also, as usual, the variable $myName here contains a reference to the actual unit object, and two references can be compared, whether they refer to the same object:

$result = $unit1->same($unit2);

The rowops are enqueued with the calls:

$unit->call($rowop, ...) or die "$!";
$unit->fork($rowop, ...) or die "$!";
$unit->schedule($rowop, ...) or die "$!"; 

Also there is a call that selects the enqueueing mode by argument:

$unit->enqueque($mode, $rowop, ...) or die "$!";

Multiple rowops can be specified as arguments. Calling these functions with multiple arguments produces the same result as doing multiple calls with one argument at a time. Not only rowops but also trays (to be discussed later) of rowops can be used as arguments.

The mode for enqueue() is one of either Triceps constants

&Triceps::EM_CALL
&Triceps::EM_FORK
&Triceps::EM_SCHEDULE

or the matching strings "EM_CALL", "EM_FORK", "EM_SCHEDULE". As usual, the constant form is more efficient. There are calls to convert between the constant and string representations:

$string = &Triceps::emString($value);
$value = &Triceps::stringEm($string);

As usual, if the value can not be translated they return undef.

The frame marks for looping are created as their own class:

$mark = Triceps::FrameMark->new("name") or die "$!";

The name can be received back from the mark:

$name = $mark->getName();

Other than that, the frame marks are completely opaque, and can be used only for the loop scheduling. Not even the same() method is supported for them at the moment, though it probably will be in the future. The mark gets set and used as:

$unit->setMark($mark);
$unit->loopAt($mark, $rowop, ...) or die "$!";

The rowop arguments of the loopAt() are the same as for the other enqueueing functions.

The methods for creation of labels have been already discussed. There also are similar methods for creation of tables and trays that will be discussed later:

$label = $unit->makeDummyLabel($rowType, "name") or die "$!";
$label = $unit->makeLabel($rowType, "name",
  $clearSub, $execSub, @args) or die "$!";
$table = $unit->makeTable($tableType, $endMode, "name") or die "$!";
$tray = $unit->makeTray(@rowops) or die "$!"; 

The unit can be checked for the emptiness of its queues:

$result = $unit->empty();

The functions for execution are:

$unit->callNext();
$unit->drainFrame();

The callNext() takes one label from the top stack frame queue and calls it. If the innermost frame happens to be empty, it does nothing. The drainFrame() calls the rowops from the top stack frame until it becomes empty. This includes any rowops that may be created and enqueued as part of the execution of the previous rowops.

A typical way of processing the incoming rowops in a loop is:

$stop = 0; 
while (!$stop) {
  $rowop = readRowop(); # some user-defined function
  $unit->schedule($rowop);
  $unit->drainFrame();
} 

All the unit's labels get cleared with the call

$unit->clearLabels();

To not forget calling it, a separate clearing trigger object can be created:

my $clearUnit = $unit->makeClearingTrigger();

The variable $clearUnit would normally be a global (in a thread) variable. Don't copy the reference to the other variables! Then when the thread completes and the global variables get destroyed, the trigger object will be also destroyed, and will trigger the clearing of the unit's labels, thus breaking up any reference loops and allowing to destroy the bits and pieces.

The only item left is the tracers, and they will be described in a separate post.

Tuesday, January 17, 2012

Issues with Triceps scheduling

Some of the issues have been already mentioned in the description of the loop scheduling: it's a bit confusing that the frame mark is placed on the next outer scheduling stack frame and not on the current one. This leads to the interesting effects in execution order.

But there are issues with the basic execution too:

The schedule() call, when used from inside the scheduled code, introduces unpredictability in the execution order: it puts the rowop after the last rowop in the outermost stack frame. But the outermost stack frame contains the queue of rowops that come from the outside. This means that the exact order of execution will depend on the timing of the rowops arriving from outside. Because of this, if the repeatable execution order is important, schedule() should be used only for the rowops coming from the outside.

The same issue happens with the loops that have been temporarily stopped and then resumed on arrival of more data from outside. The mark of such a loop will be unset when the loop continues, and looping at this mark will be equivalent to schedule(), having the same repeatability problem.

The call fork() is not exactly useful. Its main purpose was when I've thought that it's the solution to the problem of the loops. Which it has turned out to not solve, and another solution had to be devised. Now it really doesn't have much use, and will probably be removed in the future.

I have a few ideas for solutions of these issues, but they will need a bit more experimentation. Just keep in mind that the scheduling will be reformed in the future. It will still have the same general shape but differ in detail.

Sunday, January 15, 2012

loop scheduling

The easiest way to schedule the loops is to do it procedurally, something like this:

foreach my $row (@rowset) {
  $unit->call($lbA->makeRowop(&Triceps::OP_INSERT, $row)); 
}

However the labels topologically connected into a loop can come handy as well. Some logic may be easier to express this way. Suppose the model contains the labels connected in a loop:

X->A->B->C->Y
   ^     |
   +-----+


Suppose a rowop X1 is scheduled for label X, and causes the loop executed twice, with rowops X1, A2, B3, C4, A5, B6, C7, Y8. If each operation is done as a CALL, the stack grows like this: It starts with X1 scheduled.

[X1]

Which then gets executed, with its own execution frame (marked as such for clarity:

[ ] of X1
[ ]

Which then calls A2:

[ ] of A2
[ ] of X1
[ ]

By the time the execution comes to Y8, the stack looks like:

[ ] of Y8
[ ] of C7
[ ] of B6
[ ] of A5
[ ] of C4
[ ] of B3
[ ] of A2
[ ] of X1
[ ]

The loop has been converted into recursion, and the whole length of execution is the deep of the recursion. If the loop executes a million times, the stack will be two million levels deep. Worse yet, it's not just the Triceps scheduler stack that grows, it's also the process (C++) stack.

Would things be better with FORK instead of CALL used throughout the loop? It starts the  same way:

[X1]

Then X1 executes, gets its own frame and forks A2:

[A2] of X1
[ ]

Then A2 executes, gets its own frame and forks B3:

[B3] of A2
[ ] of X1
[ ]

By the end of the loop the picture becomes exactly the same as with CALL. For a while I've thought that optimizing out the empty stack frames would solve the problem, but no, that doesn't work: the problem is that the C++ process stack keeps growing no matter what. The jump back in the loop needs to be placed into an earlier stack frame.

One way to do it would be to use the SCHEDULE operation in C to jump back to A, placing the rowop A5 back onto the outermost frame. The scheduler stack at the end of C4 would look like:

[ ] of C4
[ ] of B3
[ ] of A2
[ ] of X1
[A5]

Then the stack would unwind back to

[A5]

and the next iteration of the loop will start afresh. The problem here is that if X1 wanted to complete the loop and then do something, it can't. By the time the second iteration of the loop starts, X1 is completely gone. It would be better to be able to enqueue the next execution of the loop at the specific point of the stack.

Here the concept of the frame mark comes in: a frame mark is a token object, completely opaque to the program. It can be used only in two operations:

  • setMark() remembers the position in the frame stack, just outside the current frame
  • loopAt() enqueues a rowop at the marked frame

Then the loop wold have its mark object M. The label A will execute setMark(M), and the label C will execute loopAt(M, rowop(A)). The rest of the execution can as well use call().

When A2 calls setMark(M), the stack will look like this:

[ ] of A2
[ ] of X1 * mark M
[ ]

The mark M remembers the frame one outer to the current one. The stack at the end of C4, after it has called loopAt(M, A5), is:

[ ] of C4
[ ] of B3
[ ] of A2
[A5] of X1 * mark M
[ ]

The stack then unwinds until A5 starts its execution:

[ ] of A5
[ ] of X1 * mark M
[ ]

Each iteration starts with a fresh stack, and the stack depth is limited to one iteration. The nested loops can also be properly executed.

Now, why does the mark is placed on the frame that is one out from the current one? Suppose that it did remember the current frame. Then at the end of C4 the stack will be:

[ ] of C4
[ ] of B3
[A5] of A2 * mark M
[ ] of X1
[ ]

The stack will unwind until A5. Which would then have its own frame pushed onto the stack, and call setMark(M) again, moving the mark to its own frame:

[ ] of A5 * mark M
[ ] of A2
[ ] of X1
[ ]

So on each iteration of the loop one extra frame will be pushed onto the stack, and the mark moved by one level. A loop executing a million times will push a million frames, which is bad. Marking the next outer frame prevents this.  Another option would have been to put the mark in X, but that would mean that every loop must have a preceding label that just marks the frame (well, and potentially could do the other initializations too), which seems to be too annoying.

However as things are, another problem is that if X does call(A2), when it returns, the loop would not be completed yet, only the first iteration would be completed. To have the whole loop completed, there would have to be another label W, and when W does call(X1), the loop would be completed.

This is still messy, and I'm still thinking about the ways to improve the situation.

What happens after the stack unwinds past the mark? The mark gets unset. When someone calls loopAt() with an unset mark, the rowop is enqueued in the outermost frame, having the same effect as schedule().

rowop sets the condition, it would free that original row and make it continue through the loop.  Eventually the loop will come to the looping point, calling loopAt(). But the original mark will be long unset. Scheduling at the outermost frame seems to be a logical thing to do at this point.

What if setMark() is called when there is only one frame on the stack? Then there is no second frame outer to it. The mark will simply be left unset.

Sunday, January 8, 2012

Basic scheduling

The Triceps scheduler provides 3 basic ways of executing of a label:

  • Call: execute the label right now, including all the nested calls. All of this will be completed after the call returns.
  • Fork: execute the label after the current label returns but before anything else is done. Obviously, if multiple labels are forked, they will execute in order after the current label returns (but before its caller gets the control back).
  • Schedule: execute the label after everything else is done.
How it works inside:

A scheduler in the execution unit keeps a stack of queues. Each queue is essentially a stack frame. The stack always contains at least one queue, which is called the outermost stack frame. 

When the new rowops come from the outside world, they are added with schedule() to that stack frame. That's what schedule() does: always adds messages to the outermost stack frame. If rowops 1, 2 and 3 are added, the stack looks like this:

[1, 2, 3]

The unit method drainFrame() is then used to process the rowops. It makes the unit call each label on the innermost frame (which is at the moment the same as outermost frame) in order.

First it calls the rowop 1. It's removed from the queue, then a new frame is pushed onto the stack

[ ]
[2, 3]

Then the rowop 1 executes. If it calls rowop 4, another frame is pushed onto the stack

[ ]
[ ]
[2, 3]

then the rowop 4 executes. After it is finished (not calling any other rowops), the outermost empty frame is popped before the execution of rowop 1 continues.

[ ]
[2, 3]


Suppose then rowop 1 forks rowops 5 and 6. They are appended to the innermost frame.

[5, 6]
[2, 3]

If rowop 1 calls rowop 7, again a frame is pushed onto the stack before it executes

[ ]
[5, 6]
[2, 3]


Again, note that a call does not put the target rowop into any scheduler queue. The identity of rowop being processed is just kept in the call context. A call also involves a direct C++ call on the thread stack, and if any Perl code is involved, a Perl call too. Because of this, if you nest the calls too deeply, you may run out of the thread stack space.

Returning back to the sequence, after the call of rowop 7 completes, the scheduler stack returns to

[5, 6]
[2, 3]


Suppose now the execution of rowop 1 completes. But its call is not done yet, because its stack queue is not empty. The scheduler calls drainFrame() recursively, which picks the next rowop from the innermost queue (rowop 5), and calls it, pushing a new stack frame and executing the rowop 5 code:

[ ]
[6]
[2, 3]

If rowop 5 forks rowop 8, the stack becomes:

[8]
[6]
[2, 3]

When the execution of rowop 5 returns, its queue is also not empty. So the scheduler calls rowop 8. During its execution the stack is:

[ ]
[ ]
[6]
[2, 3]

Suppose the rowop 8 doesn't call or fork anything else and returns. Its innermost queue is empty, so the call completes and pops the stack frame.

[ ]
[6]
[2, 3]

Now the queue of rowop 5 is also empty, so its call completes and pops the stack frame.

[6]
[2, 3]

The call of rowop 6 begins.

[ ]
[ ]
[2, 3]

Suppose rowop 6 calls schedule() of rowop 9. Rowop 9 is then added to the outermost queue:

[ ]
[ ]
[2, 3, 9]

Rowop 6 then returns, its queue is empty, so it's popped and its call completes.

[ ]
[2, 3, 9]

Now the queue of rowop 1 has become empty, so it's popped from the stack and the call fo rowop 1 completes.

[2, 3, 9]

The unit method drainFrame() keeps running, now taking the rowop 2 and executing it, and so on, until the outermost queue becomes empty, and drainFrame() returns.

Saturday, January 7, 2012

No bundling

The most important principle of Triceps scheduling is: No Bundling. Every rowop is for itself. The bundling is what messes up the Coral8 scheduler the most.


What is a bundle? It's a set of records that go through the execution together. If you have two functional elements F1 and F2 arranged in a sequential fashion F1-> F2, and a few loose records R1, R2, R3, the normal execution order will be:


F1(R1), F2(R1),
F1(R2), F2(R2),
F1(R3), F2(R3)

If the same records are placed in a bundle, the execution order will be different:


F1(R1), F1(R2), F1(R3),
F2(R1), F2(R2), F2(R3)

That would not be a problem, and even could be occasionally useful, if the bundles were always created explicitly. In reality every time a statement produces multiple record from a single one (think of a join that picks multiple records from another side), it creates a bundle and messes up all the logic after it. Some logic gets affected so badly that a few statements in CCL (like ON UPDATE) had to be designated as always ignoring the bundles, otherwise they would not work at all. At DB I wrote a CCL pattern for breaking up the bundles. It's rather heavyweight and thus could not be used all over the place but provides a generic solution for the most unpleasant cases.

Worse yet, the bundles may get created in Coral8 absolutely accidentally: if two records happen to have the same timestamp, for all practical purposes they would act as a bundle. In models that were designed without the appropriate guards, this leads to the time-based bugs that are hard to catch and debug. Writing these guards correctly is hard, and testing them is even harder.

Another issue with bundles is that they make the large queries slower. Suppose you do a query from a window that returns a million records.  All of them will be collected in a bundle, then the bundle will be sent to the interface gateway that would build one huge protocol packet, which will then be sent to the client, which will receive the whole packet and then finally iterate on the records in it. Assuming that nothing runs out of memory along the way, it will be a long time until the client sees the first record.  Very, very annoying.

Aleri also has its own version of bundles, called transactions, but a more smart one. Aleri always relies on the primary keys. The condition for a transaction is that it must never contain multiple modification for the same primary key. Since there are no execution order guarantees between the functional elements, in this respect the transactions work in the same way as loose records, only with a more efficient communication between threads. Still, if the primary key changes in an element, the condition does not propagate through it. Such elements have to internally collapse the outgoing transactions along the new key, adding overhead.

Introduction to Triceps scheduling

The main point of an execution unit in Triceps is scheduling of the execution of the row operations. It keeps a queue of the operations and selects, which one to execute next. The scheduling is important for a predictable execution order within a single thread.

There are multiple approaches to scheduling. Aleri essentially doesn't have any, except for the flow control between threads, because each its element is a separate thread. Coral8 has an intricate scheduling algorithm. Sybase R5 has the same logic as Coral8 inside each thread. StreamBase presumably also has some.

The scheduling logic in Triceps is different from the other CEP systems. The Coral8 logic looks at first like the only reasonable way to go, but could not be used for three reasons: First, it's a trade secret, so it can't be simply reused. If I'd never seen it, that would not be an issue but I've worked on it and implemented its version for R5. Second, it relies on the properties that the compiler computes from the model graph analysis. Triceps has no compiler, and could not do this. Third, in reality it simply doesn't work that well. There are quite a few cases when the Coral8 scheduler comes up with a strange and troublesome execution order.

For a while I've hoped that Triceps would need no scheduler at all, and everything would be handled by the procedural calls.This has proved to have its own limitations, and thus the labels and their scheduling were born. The Triceps scheduling still has issues to resolve, but overall still feels much better than the Coral8 one.

Row operations

A row operation (also known as rowop) in Triceps is an unit of work for a label. It's always destined for a particular label (which could also pass it to its chained labels), and has a row to process and an opcode. The defined opcodes are:

Triceps::OP_NOP
Triceps::OP_INSERT
Triceps::OP_DELETE

A row operation is constructed as:

$rowop = $label->makeRowop($opcode, $row);

The opcode may be specified as a Triceps constant or as one of the strings "OP_NOP", "OP_INSERT", "OP_DELETE". Historically, there is also an optional extra argument for enqueuing mode but it's already obsolete.

Since the labels are single-threaded, the rowops are single-threaded too. The rowops are immutable, just as the rows are.

The references to rowops can be compared as usual

$rowop1->same($rowop2)

returns true if both point to the same rowop object.

The rowop data can be extracted back:

$label = $rowop->getLabel();
$opcode = $rowop->getOpcode();
$row = $rowop->getRow();

A copy of rowop (not just another reference but an honest separate copied object) can be created with

$rowop2 = $rowop1->copy();

However, since the rowops are immutable, a reference is just as good as a copy. This method is historic and will likely be removed or modified.

There also are calls to directly check the meaning of the opcode:

$rowop->isNop()
$rowop->isInsert()
$rowop->isDelete()

The typical idiom for handling a label is:

if ($rowop->isInsert()) {
  # handle the insert logic ...
} elsif($rowop->isDelete()) {
  # handle the delete logic...
}

:$
The NOPs get silently ignored in this idiom, as they should be. Generally there is no point in creation of the rowops with NOP opcode, unless you want to use them for some weird logic.

The main Triceps package also provides functions to check the extracted opcodes:

Triceps::isNop($opcode)
Triceps::isInsert($opcode)
Triceps::isDelete($opcode)

The same-named methods of Rowop are just the more convenient and efficient ways to say

Triceps::isNop($rowop->getOpcode())
Triceps::isInsert($rowop->getOpcode())
Triceps::isDelete($rowop->getOpcode())

The functions to convert between the opcode integer values and strings are

$opcode = &Triceps::stringOpcode($opcodeName);
$opcodeName = &Triceps::opcodeString($opcode); 

A Rowop can be printed (usually for debugging purposes) with

$string = $rowop->printP(); 

Just as with a row, printP() means that it's implemented in Perl. In the future a print() done right in C++ may be added, but for now I try to keep all the interpretation of the data on the Perl side. The following example gives an idea of the format in which the rowops get printed:

$lb = $unit->makeDummyLabel($rt, "lb");
$rowop = $lb->makeRowop(&Triceps::OP_INSERT, $row);
print $rowop->printP(), "\n";

would produce

lb OP_INSERT a="123" b="456" c="3000000000000000" d="3.14" e="text" 

The row contents is printed through Row::printP(), so it has the same format.

Labels, part 2

As a heads up, I've noticed that a few paragraphs were accidentally dropped from the part 1, so I've re-written them and updated that post. If you read it before, please re-read it Now, continuing.

The chaining of labels is done with the call:

$label1->chain($label2) or die "$!";

A label can not be chained to itself, neither directly nor through other intermediate labels. The row types of the labels must be equal (this is more strict than for queueing up the row operations for labels and might change one or the other way in the future).

A label's chainings can be cleared with

$label1->clearChained();

It returns nothing, and clears the chainings from this  label. There is no way to unchain some selected labels.

The whole label can be cleared with

$label1->clear();

This is fully equivalent to what happens when an execution unit clears the labels: it calls the clear function (if any) and clears the chainings. Note that the labels that used to be chained from this one do not get cleared themselves, they're only unchained from this one.

Labels have the usual way of comparing the references:

$label1->same($label2)

returns true if both references point to the same label object.

The labels introspection can be done with:

$rowType = $label->getType();
$unit = $label->getUnit();
$name = $label->getName();
@chainedLabels = $label->getChain();
$execSubRef = $label->getCode();

If the label has been cleared, getUnit() will return an undef. getChain() returns an array of references to the chained labels. getCode() is actually half-done because it returns just the Perl function reference to the execution handler but not its arguments, nor reference to the clearing function. It will be changed in the future to fix these issues.

There is also a way to change the label's name:

$label->setName($name);

It returns nothing, and there is probably no reason to call it. It will likely be removed in the future.

The label also provides a constructor method for row operations, which will be described in the next post.

Thursday, January 5, 2012

Labels, part 1

In each CEP engine there are two kinds of logic: One is to get some request, look up some state, maybe update some state, and return the result. The other has to do with the maintenance of the state: make sure that when one part of the state is changed, the change propagates consistently through the rest of it. If we take a common RDBMS for an analog, the first kind would be like the ad-hoc queries, the second kind will be like the triggers. The CEP engines are very much like database engines driven by triggers, so the second kind tends to account for a lot of code.

The first kind of logic is often very nicely accommodated by the procedural logic. The second kind often (but not always) can benefit for a more relational, SQLy definition. Also, when every every SQL statement executes, it gets compiled first into the procedural form, and only then executes as the procedural code.

The Triceps approach is tilted toward procedural execution. That is, the procedural definitions come out of the box, and then the high-level relational logic can be defined with templates and code generators.

These bits of code, especially where the first and second kind connect, need some way to pass the data and operations between them. In Triceps these connection points are called Labels.

The streaming data rows enter the procedural logic through a label. Each row causes one call on the label. From the functional standpoint they are the same as Coral8 Streams, as has been shown earlier in the introduction. Except that in Triceps the labels get not just rows but operations on rows, as in Aleri: a combination of a row and an operation code. The name is "labels" because Triceps has been built around the more procedural ideas, and when looked at from that side, the labels are targets of calls and GOTOs.

If the streaming model is defined as a data flow graph, each arrow in the graph is essentially a GOTO operation, and each node is a label.

A Triceps label is not quite a GOTO label, since the actual procedural control always returns back after executing the label's code. It can be thought of as a label of a function or procedure. But if the caller does nothing but immedially return after getting the control back, it works very much like a GOTO label.

Each label accepts operations on rows of a certain type.

Each label belongs to a certain execution unit, so a label can be used only strictly inside one thread and can not be shared between threads.

Each label may have some code to execute when it receives a row operation. The labels without code can be useful too.

A Triceps model contains the straightforward code and the mode complex stateful elements, such as tables, aggregators, joiners (which may be implemented in C++ or in Perl, or created as user templates). These stateful elements would have some input labels, where the actions may be sent to them (and the actions may also be done as direct method calls), and output labels, where they would produce the indications of the changed state and/or responses to the queries. The output labels are typically the ones without code ("dummy labels"). They do nothing by themselves, but can pass the data to the other labels. This passing of data is achieved by chaining the labels: when a label is called, it will first execute its own code (if it has any), and then call the same operation on whatever labels are chained from it. Which may have more labels chained from them in turn. So, to pass the data, chain the input label of the following element to the output label of the previous element.

The execution unit provides methods to construct labels. A dummy label is constructed as:

$label = $unit->makeDummyLabel($rowType, "name");

It takes as arguments the type of rows that the label will accept and the symbolic name of the label. The name can be any but for the ease of debugging it's better to give the same name as the label variable.

The label with Perl code is constructed as follows:

$label = $unit->makeLabel($rowType, "name", \&clearSub,
  \&execSub, args...);

The row type and name arguments are the same as for the dummy label. The following arguments provide the references to the Perl functions that perform the actions. execSub is the function that executes to handle the incoming rows. It gets the arguments:

execSub($label, $rowop, args...)

Here $label is this label, $rowop is the row operation, and args are the same as extra arguments specified at the label creation.

The row operation actually contains the label reference, so why pass it the second time? The reason lies in the chaining. The current label may be chained, possibly through multiple levels, to some original label, and the rowop will refer to that original label. So the extra argument lets the code find the current label.

The clearSub deals with the destruction. Remember that the Triceps memory management uses the reference counting, which does not like the reference loops. The reference loops cause the objects to be never freed. It's no big deal if the data structures exist until the program exit anyway but becomes a memory leak if they are created and deleted dynamically.

If the labels are arranged in a cyclic graph, they refear to each other and create a reference loop. So the execution unit keeps track of all its labels, and when it gets destoryed, clears them up, breaking up the loops.

The clearing of a label drops all the references to execSub, clearSub and arguments, and clears all the chainings. But before anything else is done, clearSub gets a chance to execute and clear any application-level data. It gets as argument the label reference all the args from the label constructor:

clearSub($label, args...) 

A typical case is  to keep the state of a stateful element in a hash:

package MyElement;

sub new # (class, unit, name...)
{
  my ($class, $unit, $name) = @_; 
  my $self = {};
  ... 
  $self->inLabel = $unit->makeLabel(..., \&clear, \&handle, $self);
  $self->outLabel = $unit->makeDummyLabel(...);
  ...
  bless $self, $class;
  return $self;
}

Then the clearing function can wipe out the whole state of the element by undefining its hash:

sub clear # (label, self)
{
  my ($label, $self) = @_;
  undef %$self;
}

Either of execSub and clearSub can be specified as undef. Though a label with an undefined execSub is essentially a dummy label, only more heavyweight.

Another potential for reference loops is between the  execution unit and the labels. A unit keeps a reference to all its labels. So the labels can not keep a reference to the unit. And they don't. Internally they have a plain pointer.  Note however that in the example shown the labels have a Perl reference to the object where they belong. If that object is to have a Perl reference to the unit, it would create a reference loop, and the object will never be destroyed and never clear the labels. So generally the objects should never keep references to the unit. The unit also provides another way around this situation: it has a way to force the label clearing when a helper object gets destroyed. It will be described later.

P.S. The original published version of this post had a few paragraphs lost, the updated version from 01/06/12 has them re-added.