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!

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
| _ -> 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)

â€¦

Â

Â

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 !

Â

Â