1    Introduction

defrule and defclause allow users to define logic that defines applications. These macros actually define rule functions, which are Clojure functions with metadata, intended to process facts and create new facts based on them. See core for more details.

The cloudlog.events package provides functions for applying rule functions on events. An event is a Clojure map, containing a single change in the state of the application. This change can be an addition of a fact, a removal of a fact, or the effect of such event on the internal state of a rule. Each event contains the following fields:

• :kind: Either :fact, if this event represent a change to a fact, or :rule if it represents a change to a rule.
• :name: A string representing the name of the stream this event belongs to. See fact-table for details.
• :key: The key of the fact or the rule. See here for more details.
• :ts: The time (in milliseconds since EPOCH) in which this event was created (for facts. See below for rules).
• :data: The data tuple representing a fact, or the state of a rule, excluding the key.
• :change: A number representing the change. Typically, 1 represents addition, and -1 represents removal.
• :writers: The event's writer-set, represented as an interset.
• :readers: The event's reader-set, represented as an interset.
• :removed (optional): If exists, account for an additional event that is identical to the original one, but with :data = :removed, and :change = -:change.

For the examples of this package we will use the following convenience function:

1.1    Rules

In this module we base our examples on the following rules defined here:

2    emitter: Create an Event-Emitting Function

Rules start by matching a single fact. An emitter function takes an event representing such a fact and applies the rule function associated with the event.

For a simple rule, the result is a sequence of derived fact.

For a join, the result is an event representing the rule produced from the fact.

Here some explanation is in order. Our notion of facts and rules come from mathematical logic. Facts are what mathematical logic calls atoms – a combination of a name with some arguments, and rules are logic formulas of the form a->b, where the -> operator represents logical inference. In the subset of mathematical logic we adopted, the left-hand-side of the -> operator must be an atom (a fact). However, the right-hand side can be any kind of axiom – fact or rule. With this we can create compound rules such as a->b->c->d, that should be read as a->(b->(c->d)). This means that the fact a implies the rule b->c->d, which in turn means that the fact b implies c->d, which in turn means that c implies d. In cloudlog.clj, rule functions take whatever matches the left-hand side of the rule, and emit whatever is on the right-hand side, be it a (derived) fact or a rule. Our implementation does not emit the rule syntactically. Instead it provides a tuple that contains its underlying data. But we still treat it as a rule.

The :name component in the produced events is derived from the name of the rule, a 'bang' (!) and the index of the link that emitted this event in the overall rule. An emitter always represents the first link in a rule, so this value is always 0.

2.1    Readers and Writers

The only parts of the event that are not easy to understand are the :readers and :writers keys. The values associated with these keys are conceptually sets of users. :writers represents the set of users who may have created the event. Each user in this set has permission to create a similar event that, e.g., can cancel the effect of this one (e.g., by creating an event with the same :key, :data :readers and writers but with a complement :change value) and to replace the underlying datum with another one (e.g., by creating an event with the same :key, :readers and :writers but different :data. The :writers set is key to how Clojure applications manage integrity.

When a rule is applied to a fact, the resulting event carries the :writers set associated with the rule, which is its namespace, for reasons we discuss in our discussion of integrity for derived facts.

:readers represents a set of users allowed to read an axiom. We will revisit :readers when discussing multiplier.

Rules may pose requirements for :writers and :readers. To support this, we pass them as metadata on the data.

2.2    Atomic Updates

When an event contains a :removed key, it is considered an atomic update. The reason is that this is a single event that flows through the system, and removes one piece of data and at the same time (:ts) also adds another piece or data.

If the :removed field exists, two events will be emitted, one for :data and one for :removed.

3    multiplier: Create a Function Applying Rules to Facts

The lowest level of event processing is taking two corresponding events (i.e., an event for a fact and a rule with the same key) and producing a collection of events that are produced from this combination.

A multiplier is constructed based on a rule function, and a number (>0) representing the link in the rule.

The returned function takes two arguments: a rule event and a matching fact event. It returns a sequence of events created by this combination.

We call this unit a multiplier, because it multiplies the :change field of the rule and the fact event. Imagine we have n facts and m rules with a certain key. In order to have all possible derived events we should invoke the multiplier function n*m times, once for each combination. Now imagine these n facts are actually the same fact, just added n times, and the m rules are the same rule added m times. The state of the application can therefore be represented using two events, one for the fact, with :change value of n, and one for the rule with :change value of m. Now if we introduce these two events to the multiplier function, we would like to get the same result as before, that is, applying the rule to the fact n*m times. To achieve this, the multiplier function multiplies the :change values, so that every event it returns has a :change value of n*m.

Multiplies can handle atomic updates given in the fact:

... or in the rule.

3.1    Confidentiality

A multiplier is a meeting place of facts with rules, which in turn are derived from other facts. Such a meeting place is where the confidentiality of the system is put to the test.

Consider a dating service, where users can open tickets with their personal details, set up a watch for tickets that match certain criteria (for simplicity, let's say, gender, location, and age-range). A rule for creating search results can look like this:

ticket-by-gender-and-location is an indexing of raw :test/ticket, performed by the following rule:

People openning tickets on dating services often wish their tickets to be limited to a certain set of users. Similarly, people setting up a watch often wish to keep their preferences secret. These preferences are recorded in the :readers set of each fact. :readers is an interset specifying who can read this fact. Each element in :readers represents a named set of users, and the readers set for the event is an intersection of all these named sets.

In Cloudlog, rules are not responsible for confidentiality; the Cloudlog implementation is. Imagine a Alice openning a ticket in the dating service, willing to make it visible only to :male :long-time-users (i.e., to members of the intersection of the :male and :long-time-users named sets). The event will look like this:

The emitter applying the ticket-by-gender-and-location rule will keep the :readers set as-is:

When Bob looks for dates like Alice, he creates :test/watch with an event looking like this:

He places only himself in the :readers set, so no one else will know he's looking, or what he's looking for. Bob can be seen as an intersection of all the named sets he's a member of. One such set is [:user= "bob"], a partition set that contains only him, but Bob is also a member of the :male set. Note that Bob is not a member of the :long-time-users set, since he's new to the service.

Here too, the emitter function does not change the :readers set.

Now is where things get interesting. When the second link of the dating-matches rule kicks in, taking both dating-matches-event as the rule-event and ticket-by-gender-and-location-event as its fact event. What shall the :reader set of the result be? That of the rule, conveying Bob's wishes, or that of the fact, conveying Alice's wishes?

The :readers set of the resulting events will be an intersection of both :readers sets, (which is actually a union of the Clojure sets).

The resulting :readers set is an intersection of :male and [:user= "bob"], which Bob is a member of, with :long-time-users, which Bob is not a member of. This places Bob outside the intersection, and therefore unable to see the resulting fact (which is what we expect).

3.2    Integrity

Since rules take ownership over the resulting events, the :writers set of events coming out of a multiplier must come from the rule event:

3.3    Timestamps

Events are stored with a primary key that combines :key and :ts. Out of these, :key is used for sharding, and :ts is used for sorting. Typically, we will want to query events that share :name and :key values together, so it makes sense to store all of them together. The :ts provides an additional key, so we can refer to specific events that share :name and :key.

Some event processing systems like Apache Storm guarantee at least once semantics. The advantage of this approach is that they guarantee that everything that needs to be processed gets processed, and do this at relatively low cost. The disadvantage is that if we use such a mechanism we need to be able to cope with processing being done more than once. We cope with this in two ways:

1. All computation is declarative, meaning that if you call a rule function twice with the same input you are guaranteed to get the same output.
2. We use a consistent unique key for each result, so that if we get the same result a second time, the new result gets "swallowed" by the old result.

The unique ID we use is the timestamp – :ts. Timestamps are given to fact events when they are created. An emitter function simply moves the :ts attribute from its input event to its output.

For rule events and derived facts we use a consistent manipulation of the timestamps in the original facts being used. This makes the :ts lose its value as timestamp, but remain consistent and specific, so no matter when a fact and rule met, the :ts of their mutual products only depends on the combination of their :ts.

A multiplier therefore needs to compute a function of the fact and rule :ts values. This function needs to be specific, so that the chance for a collision, (i.e., two fact/rule pairs with different :ts values multiplying into rules or derived facts with the same :ts values), is minimized. The + operator will not do a good job here, because, for example, the pairs [1000 2000] and [1001 1999] have the same sum. The * operator will do a better job, given that all our timestamps are within the same order of magnitude, but the result will be out of that range, and as we apply more multipliers the result will grow to be unnecessarily large or overflow (if bigint is not used). We therefore use a modular multiplication as our operation.

Why? because we need to keep the value unique per :key. Consider the above example. If we take the rule :ts value, the :ts for each entry in Alice's timeline will be the :ts of the rule that was applied, which takes its :ts from the :test/follows fact. This means that every tweet made by Bob will appear in Alice's timeline with the same :ts value, and hence tweets will overrun one another.

But what guarantee do we have that if we take the fact's :ts we do not get into such a situation? There is no hard guarantee for that. Hoever, the whole point of using rules it to denormalize the data so that it is searchable with different keys. It is pointless to have a rule that keeps the same :key. Such rules can be easily converted to clauses, which do not require redundant information to be stored.

4    matcher: Matches Rules and Facts

multipliers apply rules to facts, and expect to be given both as parameters. However, in most cases we are only given one – a rule or a fact, and we need to apply that rule or that fact to all matching rules and facts. These matching rule and fact events are typically stored in some database. The database can provide all events that match a combination of :kind, :name and :key.

As we wish to decouple Cloudlog's implementation from any particular database, we use core.async channels to interact with the database. We provide the event to be matched on a channel, along with a channel for the output, and in return someone provides us with the matching events on the channel we provided, and closes the channel. On the other side of the channel there could be an interface to a cloud database, an in-memory cache or a combination of the two. We don't care as long as we get what we need from the other side of the channel.

A matcher instance is constructed by the matcher function, which is given a rule function, a link number and a channel to the database.

4.1    Matching Rules for Facts

The returned matcher is a function that takes an event and an output channel for the resulting events.

The matcher will emit a query to the db-chan, specifying what it is looking for

The request consists of a pair [req chan], where req is a partial event that matches what we are looking for:

And chan is the channel on which the database is expected to provide the reply

Next, the database emits matching rules on the reply channel, and closes it.

For each such event the matcher will emit the events obtained by multiplying the fact and the rules.

Finally, the channel needs to be closed.

4.2    Matching Facts for Rules

A matcher function can accept either a fact event or a rule event.

For a rule, the matcher will query the database for matching facts.

Now the database replies fact events.

The results are emitted on the res-chan:

5    Accumulating Events

emitters multipliers and matchers treat each event individually. This approach is consistent with the practice of Event Sourcing. However, sometimes we wish to see the complete picture and accumulate events. The following functions support event accumulation.

5.1    accumulate

accumulate is a reducing function that accumulates events into a map for which the keys are the events themselves, excluding their :change and :ts fields, and the values are tuples, containing the sums of the :change and the maximum :ts for each entry.

With arity 0, accumulate returns and empty map.

With arity 2, it will take a map and an event, and if the event is not already a key in the map, it will be added so that the :change and :ts fields move from the key to the value.

If the event exists as a key in the map (possibly with a different :change and :ts values), the entry is updated to include the sum of the existing value and the event's :change, and the latest :ts.

Atomic update events are accumulated as two different events. In the following example the first event sets the value of k1 to [1 2], and the second event is an atomic update, updating its value to [2 3]. The accumulation shows only a single event with the updated value. (The old value is still present, but with value of 0).

5.2    accumulated-events

With an accumulated map at hand, we can get a sequence of the underlying accumulated events by calling accumulated-events.

Events for which the accumulated :change value is zero or negative are ignored.

5.3    accumulate-db-chan

Given a database-chan, such as the one provided for DynamoDB, and the one consumed by matchers, accumulate-db-chan returns a new channel which implements the same protocol but accumulates the events coming from the given database interface.

Consider for example the following mock database, which will answer each request with the same three events:

Please note that the first and third events cancel each other. Now we use accumulate-db-chan to create a new channel.

When sending a request to my-db-chan, we should get the events provided on mock-db-chan, but accumulated.

This should work multiple times...

6    Under the Hood

6.1    split-atomic-update

The function split-atomic-update takes an event that may or may not have a :changed field (an atomic update), and returns a sequence of one or two events.

For events without a :changed field, split-atomic-update returns the event as-is.

For events that do have a :changed field, split-atomic-update returns two events, one based on :data and the other based on :removed.

6.2    join-atomic-updates

Given a collection of events, join-atomic-updates returns a possibly smaller collection of events where all events that form atomic updates are unified into single events.

If no events match, the function returns a collection with all original events

If some events match, join-atomic-updates joins them into a single event

6.3    find-atomic-update

The key to implementing join-atomic-updates is being able to find, for a given event, a matching event within a given collection. find-atomic-update takes an event and a collection of other events, and returns a pair: [match rest], where match is an event or nil, and rest is a collection of events.

If the collection of events does not contain a match for the given event, nil and the original collection are returned.

If the collection of events contains a match, that match is returned, and the collection is returned with the match removed.

6.4    matching?

matching? takes two events and returns whether they can be unified to a single atomic update. Two events are considered to match if they share all fields except :data and :change, and the values of :change are the negation of one another.