Skip to content

Software Development Blogs: Programming, Software Testing, Agile Project Management

Methods & Tools

Subscribe to Methods & Tools
if you are not afraid to read more than one page to be a smarter software developer, software tester or project manager!

Think Before Coding - Jérémie Chassaing
Syndicate content
Updated: 1 hour 2 min ago

Monoidal Event Sourcing Examples

Sun, 04/27/2014 - 01:16

Last time we tried to imagine how we could change usual event sourcing definition$ to get a monoidal approach.

 

Here are some examples to make it work in real life.

Monoids properties

We'll try to do it properly, and test that the proposed solutions are proper monoids.

 

Let's recap what defines a monoid:

  • closure of operation
  • associativity
  • neutral element
How to test it

the closure of operation is given by the signature of the operation. In F# it should have a signature like 'a -> 'a –> 'a which represents a function that takes to arguments of type 'a and return a result of the same type 'a.

 

For associativity, we'll use the following test function:

1: 
2: 
let isAssociative (*) x y z =
   ((x * y) * z) = (x * (y * z))

It take a function that will be called '' and three values x y z. It will then test the associativity of '' using FsCheck, a F# port of QuickCheck.

 

FsCheck test the given property for a wide range of values. We'll just have to provide the operator, and FsCheck will check it the associativity holds for a lot of values.

 

For the neutral element, will use the following test function:

1: 
2: 
let isNeutralElement (*) neutral x =
    x * neutral = neutral * x

 

Here we'll have to provide the the operator - called '*' inside the function - and the neutral element.

Trivial cases

There are some obvious trivial cases.

 

Let's try to follow the number of occurrences of a specific event in state. The number of time a user did

something.

 

The map function is simply:

1: 
2: 
3: 
let map = function
    | TheUserDidSomething -> 1
    | _ -> 0

 

The combine operation is then really simple:

1: 
let combine acc v = acc + v

and the neutral element is obviously 0.

 

No need to check it with FsCheck, (N, +, 0) is a monoid..

 

Another a bit less obvious is when an event sets a value while others don't.

 

For instance, let's keep track of the last user address when a user moves.

 

For combination, we'll use the 'right' function, which always takes it's rightmost argument:

1: 
let right x y = y

 

The adress should, of course, not change on other events, and for that, we'll use an option:

1: 
2: 
3: 
let map' = function
    | UserMoved (user, newAddress) -> Some newAddress
    | _ -> None

 

The right function can then be tweaked to take the right argument only when it has a value:

1: 
2: 
3: 
4: 
let right' x y =
    match x,y with
    | x, None -> x
    | _, y -> y

right' has a signature of 'a option -> 'a option -> 'a option, so it's closed on operation.

 

It's associative since, whatever x y z, (x right' y right' z) return the last defined term, however composed.

 

None is the neutral element. Added to the left, it keeps what's on the right, added to the right, it keeps what's on the left.

 

We can check it with FsCheck:

1: 
2: 
Check.Quick (isNeutralElement right' None)
Check.Quick (isAssociative right')
A less trivial case

But what about mixing both ? Some events change the value by increments, while some other set a specific value ? Like a stopwatch that increments with a button to reset it.

 

Can we model this kind of thing as a monoid ?

 

We have an increment or a reset value, let's model it as a discriminated union:

1: 
2: 
3: 
type ChangeReset<'T> =
    | Change of 'T
    | Reset of 'T

 

 

A map function, that map events to state change, would be something like:

1: 
2: 
3: 
4: 
let map'' = function
    | TimePassed duration -> Change duration
    | ButtonPushed -> Reset 0.
    | _ -> Change 0.

 

The first two cases are a direct mapping, for other events, we use the Change 0. values that actually use the neutral element of the underlying monoid. Adding 0 will not change the value.

 

We have here an underlying monoid, here, talking about duration, we use numbers, with addition and 0.

 

But imagine we want to add items to a list, but sometime, reset the list to a specific one like the empty list.

 

we can define a high order combine operation like this:

1: 
2: 
3: 
4: 
5: 
let combine' (*) x y =
    match x,y with
    | Change xi, Change yi -> Change (xi * yi)
    | Reset xv, Change yi -> Reset (xv * yi)
    | _ , Reset yv -> Reset yv

 

It combines to changes as a new change using the underlying monoid operation - called '*' here. It combines changes as a change.

 

The second line states, that a value (Reset) combined with a change will apply the change to the value.

 

But the third line says that when a Reset value is on the right of anything, it overrides what's on it's left.

This operation is by it's signature closed on the ChangeReset<'t> type.

 

It's associative, because while combining changes, it has the associativity of the underlying monoid, and when combining Reset values it has the associativity of the right operation.

 

The neutral element is a change with the value of the neutral element of the underlying monoid.

 

We can verify it with FsCheck:

1: 
2: 
Check.Quick (isNeutralElement (combine' (+)) (Change 0))
Check.Quick (isAssociative (combine' (+)))
General structure

I had some remarks that we needed it to be a group and not only a monoid. The right' and combine function clearly don't define a group because elements don't have a inverse/opposite.

 

What would be the opposite of Reset 5 ? It set the value 5 whatever is on its left.

 

The idea is to take the set of state values S.

 

Then take the set of changes from states in S to other states in S that are represented by the events.

 

Make the union of it. SC = S U C. SC will contain more that valid aggregate states. It will also contain things that are not state, like a value that indicate that the state did not change.

 

But we will ensure the following things: the function that convert to changes will return items of C:

1: 
map: Event -> C 

 

The combine operation will be closed on SC, so it can accept States from S and change from C, and it will be closed on SC: combine:

SC -> SC -> SC

 

But it will also ensure that when a state is given on the left, it will also return a state:

combine:  S -> SC -> S

 

The right' operation ensure this. The state need a value at its start, you can add as many None on the right, it'll still have it's value, and any new value will return this value.

 

For the ChangeReset type, the State is represented by the Reset values -that are actual values- it's S, while changes are represented by the Change values that define C.

 

As long as a Reset value is given at the outmost left, the result will be a Reset value that is part of S.

With this, we don't need a group, but we can do with something that is only slightly more restraint than a monoid, only to keep the semantic of state.

But we need more that a single value !

Of course aggregate state is usually composed of more than a single value.

 

Let's start small and consider a pair.

1: 
type State<'a,'b> = 'a * 'b

 

If 'a and 'b are monoids we can easily combine them :

1: 
let combine'' (+) (*) (xa,xb) (ya,yb) = (xa + ya, xb * yb)

where + is the operation on 'a and * the operation on 'b.

 

The neutral element is simply

1: 
let neutral neutrala neutralb = (neutrala, neutralb)

You can easily check that combine is closed on operation, associative, and that neutral is the neutral element.

 

recursively, you can build a triple as a pair of a pair with a single element (('a,'b), 'c), then a quadruple and any tuple.

 

Since a structure - a record - is just a tuple with names, any struct with monoidal members is also a monoid.

 

And since in Event Sourcing, all the tricky decisions are done before emitting an event, applying the event should just be setting values, incrementing / decrementing values, adding / removing items to sets or lists, all those operation are monoidal, hence almost all aggregates should be convertible to monoidal Event Sourcing.

 

Of course it doesn't mean you should do Event Sourcing this way, but it was rather funny to explore this !

 

Have fun !

Categories: Architecture, Requirements

Monoidal Event Sourcing

Fri, 04/11/2014 - 03:34

I Could not sleep… 3am and this idea…

 

Event sourcing is about fold but there is no monoid around !

 

What’s a monoid ?

 

First, for those that didn’t had a chance to see Cyrille Martaire’s  fabulous explanation with beer glasses, or read the great series of post on F# for fun and profit, here is a quick recap:

 

We need a set.

Let’s take a simple one, positive integers.

 

And an operation, let say + which takes two positive integers.

 

It returns… a positive integer. The operation is said to be closed on the set.

 

Something interesting is that 3 + 8 + 2 = 13 = (3 + 8) + 2 = 3 + (8 + 2).

This is associativity: (x + y) + z = x + (y + z)

 

Le last interesting thing is 0, the neutral element:

x + 0 = 0 + x = x

 

(N,+,0) is a monoid.

 

Let say it again:

(S, *, ø) is a monoid if

  • * is closed on S  (* : S –> S > S)
  • * is associative ( (x * y) * z = x * (y * z) )
  • ø is the neutral element of * ( x * ø = ø * x = x )

warning: it doesn’t need to be commutative so x * y can be different from y * x !

 

Some famous monoids:

(int, +, 0)

(int, *, 1)

(lists, concat, empty list)

(strings, concat, empty string)

 

The link with Event Sourcing

 

Event sourcing is based on an application function apply : State –> Event –> State, which returns the new state based on previous state and an event.

 

Current state is then:

fold apply emptyState events

 

(for those using C# Linq, fold is the same as .Aggregate)

 

Which is great because higher level functions and all…

 

But fold is event more powerful with monoids ! For integers, fold is called sum, and the cool thing is that it’s associative !

 

With a monoid you can fold subsets, then combine them together after (still in the right order). This is what give the full power of map reduce: move code to the data. Combine in place, then combine results. As long as you have monoids, it works.

 

But apply will not be part of a monoid. It’s not closed on a set.

 

To make it closed on a set it should have the following signature:

 

apply: State –> State –> State, so we should maybe rename the function combine.

 

Let’s dream

 

Let’s imagine we have a combine operation closed on State.

 

Now, event sourcing goes from:

 

decide: Command –> State –> Event list

apply: State –> Event –> State

 

to:

decide: Command –> State –> Event list

convert: Event –> State

combine: State –> State –> State

 

the previous apply function is then just:

apply state event = combine state (convert event)

 

and fold distribution gives:

 

fold apply emptyState events = fold combine emptyState (map convert events) 

 

(where map applies the convert fonction to each item of the events list, as does .Select in Linq)

 

The great advantage here is that we map then fold which is another name for reduce !

 

Application of events can be done in parallel by chuncks and then combined !

 

Is it just a dream ?

 

Surely not.

 

Most of the tricky decisions have been taken in the decide function which didn’t change. The apply function usually just set state members to values present in the event, or increment/decrement values, or add items to a list… No business decision is taken in the apply function, and most of the primitive types in state members are already monoids under there usual operations…

 

And a group (tuple, list..) of monoid is also a monoid under a simple composition:

if (N1,*,n1) and (N2,¤,n2) are monoids then N1 * N2 is a monoid with an operator <*> ( (x1,x2) <*> (y1,y2) = (x1*y1, x2¤y2)) and a neutral element (n1,n2)…

 

To view it more easily, the convert fonction converts an event to a Delta, a difference of the State.

 

Those delta can then be aggregated/folded to make a bigger delta.

It can then be applied to a initial value to get the result !

 

 

The idea seams quite interesting and I never read anything about this.. If anyone knows prior study of the subject, I’m interested.

 

Next time we’ll see how to make monoids for some common patterns we can find in the apply function, to use them in the convert function.

Categories: Architecture, Requirements