Data.CRDT.EventFold

Overview

This module provides a CRDT data structure that collects and applies operations (called "events") that mutate an underlying data structure.

It is "Garbage Collected" in the sense that the number of operations accumulated in the structure will not grow unbounded, assuming that participants manage to sync their data once in a while. The size of the data (as measured by the number of operations we have to store) is allowed to shrink.

In addition to mutating the underlying data, each operation can also produce an output that can be obtained by the client. The output can be either totally consistent across all replicas (which is slower), or it can be returned immediately and possibly reflect an inconsistent state.

Garbage Collection

Unlike many traditional CRDTs which always grow and never shrink, EventFold has a mechanism for determining what consensus has been reached by all of the participants, which allows us to "garbage collect" events that achieved total consensus. Perhaps more importantly, this allows us to produce the totally consistent output for events for which total consensus has been achieved.

But there are trade offs. The big downside is that participation in the distributed replication of the EventFold must be strictly managed.

• The process of participating itself involves registering with an existing participant, using participate. You can't just send the data off to some other computer and expect that now that computer is participating in the CRDT. It isn't.
• Participants can not "restore from backup". Once they have incorporated data received from other participants or generated new data themselves, and that data has been transmitted to any other participant, they are committed to using that result going forward. Doing anything that looks like "restoring from an older version" would destroy the idea that participants have reached consensus on anything, and the results would be undefined and almost certainly completely wrong. This library is written with some limited capability to detect this situation, but it is not always possible to detect it all cases. Many times you will just end up with undefined behavior.

A Belabored Analogy

The EventFold name derives from a loose analogy to folding over a list of events using plain old foldl. The component parts of foldl are:

• A binary operator, analogous to apply.
• An accumulator value, analogous to infimumValue.
• A list of values to fold over, loosely analogous to "the list of all future calls to event".
• A return value. There is no real analogy for the "return value". Similarly to how you never actually obtain a return value if you try to foldl over an infinite list, EventFolds are meant to be long-lived objects that accommodate an infinite number of calls to event. What you can do is inspect the current value of the accumulator using infimumValue, or the "projected" value of the accumulator using projectedValue (where "projected" means "taking into account all of the currently known calls to event that have not yet been folded into the accumulator, and which may yet turn out to to have other events inserted into the middle or beginning of the list").

The EventFold value itself can be thought of as an intermediate, replicated, current state of the fold of an infinite list of events that has not yet been fully generated. So you can, for instance, check the current accumulator value.

In a little more detail, consider the type signature of foldl (for lists).

foldl
  :: (b -> a -> b) -- Analogous to 'apply', where 'a' is your 'Event'
                   -- instance, and 'b' is 'State a'.

  -> b             -- Loosely analogous to 'infimumValue' where
                   -- progressive applications are accumulated.

  -> [a]           -- Analogous to all outstanding or future calls to
                   -- 'event'.

  -> b             

Basic API

Creating new CRDTs

new

Arguments

:: (Default (State e), Ord p)

=> o

The "origin", identifying the historical lineage of this CRDT.

-> p

The initial participant.

-> EventFold o p e

Construct a new EventFold with the given origin and initial participant.

Adding new events

event :: (Ord p, Event e) => p -> e -> EventFold o p e -> (Output e, EventId p, UpdateResult o p e)

Introduce a change to the EventFold on behalf of the participant. Return the new EventFold, along with the projected output of the event, along with an EventId which can be used to get the fully consistent event output at a later time.

Coordinating replica updates

Functions in this section are used to help merge foreign copies of the CRDT, and transmit our own copy. (This library does not provide any kind of transport support, except that all the relevant types have Binary instances. Actually arranging for these things to get shipped across a wire is left to the user.)

In principal, the only function you need is fullMerge. Everything else in this section is an optimization. You can ship the full EventFold value to a remote participant and it can incorporate any changes using fullMerge, and vice versa. You can receive an EventFold value from another participant and incorporate its changes locally using fullMerge.

However, if your underlying data structure is large, it may be more efficient to just ship a sort of diff containing the information that the local participant thinks the remote participant might be missing. That is what events and diffMerge are for.

fullMerge

Arguments

:: (Eq (Output e), Eq e, Eq o, Event e, Ord p)

=> p

The "local" participant doing the merge.

-> EventFold o p e

The local copy of the EventFold.

-> EventFold o p e

The remote copy of the Eventfold.

-> Either (MergeError o p e) (UpdateResult o p e)

Monotonically merge the information in two EventFolds. The resulting EventFold may have a higher infimum value, but it will never have a lower one (where "higher" and "lower" are measured by infimumId value, not the value of the underlying data structure). Only EventFolds that originated from the same new call can be merged. If the origins are mismatched, or if there is some other programming error detected, then an error will be returned.

Returns the new EventFold value, along with the output for all of the events that can now be considered "fully consistent".

data UpdateResult o p e

The result updating the EventFold, which contains:

• The new EventFold value,
• The outputs of events that have reached the infimum as a result of the update (i.e. "totally consistent outputs"),
• And a flag indicating whether the other participants need to hear about the changes.

Constructors

UpdateResult

Fields

• urEventFold :: EventFold o p e

  The new EventFold value

• urOutputs :: Map (EventId p) (Output e)

  Any consistent outputs resulting from the update.

• urNeedsPropagation :: Bool

  True if any new information was added to the EventFold which might need propagating to other participants.

events :: Ord p => p -> EventFold o p e -> Diff o p e

Get the outstanding events that need to be propagated to a particular participant.

diffMerge

Arguments

:: (Eq (Output e), Eq e, Eq o, Event e, Ord p)

=> p

The "local" participant doing the merge.

-> EventFold o p e

The local copy of the EventFold.

-> Diff o p e

The Diff provided by the remote participant.

-> Either (MergeError o p e) (UpdateResult o p e)

Like fullMerge, but merge a remote Diff instead of a full remote EventFold.

data MergeError o p e

This is the exception type for illegal merges. These errors indicate serious programming bugs.

Constructors

DifferentOrigins o o

The EventFolds do not have the same origin. It makes no sense to merge EventFolds that have different origins because they do not share a common history.

DiffTooNew (EventFold o p e) (Diff o p e)

The Diff's infimum is greater than any event known to EventFold into which it is being merged. This should be impossible and indicates that either the local EventFold has rolled back an event that it had previously acknowledged, or else the source of the Diff moved the infimum forward without a full acknowledgement from all participants. Both of these conditions should be regarded as serious bugs.

DiffTooSparse (EventFold o p e) (Diff o p e)

The Diff assumes we know about events that we do not in fact know about. This is only possible if we rolled back our copy of the state somehow and "forgot" about state that we had previous acknowledged, or else some other participant erroneously acknowledged some events on our behalf.

Instances

(Show (Output e), Show o, Show p, Show e, Show (State e)) => Show (MergeError o p e)

Defined in Data.CRDT.EventFold

Methods

showsPrec :: Int -> MergeError o p e -> ShowS

show :: MergeError o p e -> String

showList :: [MergeError o p e] -> ShowS

Generic (MergeError o p e)

Defined in Data.CRDT.EventFold

Associated Types

type Rep (MergeError o p e) :: Type -> Type

Methods

from :: MergeError o p e -> Rep (MergeError o p e) x

to :: Rep (MergeError o p e) x -> MergeError o p e

(ToJSON o, ToJSON p, ToJSON e, ToJSON (Output e), ToJSON (State e)) => ToJSON (MergeError o p e)

Defined in Data.CRDT.EventFold

Methods

toJSON :: MergeError o p e -> Value

toEncoding :: MergeError o p e -> Encoding

toJSONList :: [MergeError o p e] -> Value

toEncodingList :: [MergeError o p e] -> Encoding

(Ord p, FromJSON o, FromJSON p, FromJSON e, FromJSON (State e), FromJSON (Output e)) => FromJSON (MergeError o p e)

Defined in Data.CRDT.EventFold

Methods

parseJSON :: Value -> Parser (MergeError o p e)

parseJSONList :: Value -> Parser [MergeError o p e]

type Rep (MergeError o p e)

Defined in Data.CRDT.EventFold

type Rep (MergeError o p e) = D1 ('MetaData "MergeError" "Data.CRDT.EventFold" "crdt-event-fold-1.3.0.0-inplace" 'False) (C1 ('MetaCons "DifferentOrigins" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 o) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 o)) :+: (C1 ('MetaCons "DiffTooNew" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (EventFold o p e)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Diff o p e))) :+: C1 ('MetaCons "DiffTooSparse" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (EventFold o p e)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Diff o p e)))))

Participation

participate

Arguments

:: forall o p e. (Ord p, Event e)

=> p

The local participant.

-> p

The participant being added.

-> EventFold o p e

-> (EventId p, UpdateResult o p e)

Allow a participant to join in the distributed nature of the EventFold. Return the EventId at which the participation is recorded, and the resulting EventFold. The purpose of returning the EventId is so that you can use it to tell when the participation event has reached the infimum. See also: infimumId

disassociate

Arguments

:: forall o p e. (Event e, Ord p)

=> p

The peer removing itself from participation.

-> EventFold o p e

-> (EventId p, UpdateResult o p e)

Indicate that a participant is removing itself from participating in the distributed EventFold.

Defining your state and events

class Event e where

Instances of this class define the particular "events" being "folded" over in a distributed fashion. In addition to the event type itself, there are a couple of type families which define the State into which folded events are accumulated, and the Output which application of a particular event can generate.

TL;DR: This is how users define their own custom operations.

Associated Types

type Output e

type State e

Methods

apply :: e -> State e -> EventResult e

Apply an event to a state value. **This function MUST be total!!!**

Instances

Event ()

The most trivial event type.

Defined in Data.CRDT.EventFold

Associated Types

type Output ()

type State ()

Methods

apply :: () -> State () -> EventResult ()

(Event a, Event b) => Event (Either a b)

The union of two event types.

Defined in Data.CRDT.EventFold

Associated Types

type Output (Either a b)

type State (Either a b)

Methods

apply :: Either a b -> State (Either a b) -> EventResult (Either a b)

data EventResult e

The result of applying an event.

Morally speaking, events are always pure functions. However, mundane issues like finite memory constraints and finite execution time can cause referentially opaque behavior. In a normal Haskell program, this usually leads to a crash or an exception, and the crash or exception can itself, in a way, be thought of as being referentially transparent, because there is no way for it to both happen and, simultaneously, not happen.

However, in our case we are replicating computations across many different pieces of hardware, so there most definitely is a way for these aberrant system failures to both happen and not happen simultaneously. What happens if the computation of the event runs out of memory on one machine, but not on another?

There exists a strategy for dealing with these problems: if the computation of an event experiences a failure on every participant, then the event is pushed into the infimum as a failure (i.e. a no-op), but if any single participant successfully computes the event then all other participants can (somehow) request a "Full Merge" from the successful participant. The Full Merge will include the infimum value computed by the successful participant, which will include the successful application of the problematic event. The error participants can thus bypass computation of the problem event altogether, and can simply overwrite their infimum with the infimum provided by the Full Merge.

Doing a full merge can be much more expensive than doing a simple Diff merge, because it requires transmitting the full value of the EventFold instead of just the outstanding operations.

This type represents how computation of the event finished; with either a pure result, or some kind of system error.

TL;DR:

In general SystemError is probably only ever useful for when your event type somehow executes untrusted code (for instance when your event type is a Turing-complete DSL that allows users to submit their own custom-programmed "events") and you want to limit the resources that can be consumed by such untrusted code. It is much less useful when you are encoding some well defined business logic directly in Haskell.

Constructors

SystemError (Output e)

Pure (Output e) (State e)

Inspecting the EventFold

isBlockedOnError :: EventFold o p e -> Bool

Return True if progress on the EventFold is blocked on a SystemError.

The implication here is that if the local copy is blocked on a SystemError, it needs to somehow arrange for remote copies to send full EventFolds, not just Diffs. A diffMerge is not sufficient to get past the block. Only a fullMerge will suffice.

If your system is not using SystemError or else not using Diffs, then you don't ever need to worry about this function.

projectedValue :: Event e => EventFold o p e -> State e

Return the current projected value of the EventFold.

infimumValue :: EventFold o p e -> State e

Return the current infimum value of the EventFold.

infimumId :: EventFold o p e -> EventId p

Return the EventId of the infimum value.

infimumParticipants :: EventFold o p e -> Set p

Gets the known participants at the infimum.

allParticipants :: Ord p => EventFold o p e -> Set p

Get all known participants. This includes participants that are projected for removal.

projParticipants :: Ord p => EventFold o p e -> Set p

Get all the projected participants. This does not include participants that are projected for removal.

origin :: EventFold o p e -> o

Return the origin value of the EventFold.

divergent :: forall o p e. Ord p => EventFold o p e -> Map p (EventId p)

Returns the participants that we think might be diverging. In this context, a participant is "diverging" if there is an event that the participant has not acknowledged but we are expecting it to acknowledge. Along with the participant, return the last known EventId which that participant has acknowledged.

Underlying Types

data EventFold o p e

This type is a CRDT into which participants can add Events that are folded into a base State. You can also think of the "events" as operations that mutate the base state, and the point of this CRDT is to coordinate the application of the operations across all participants so that they are applied consistently even if the operations themselves are not commutative, idempotent, or monotonic.

Variables are:

• o - Origin
• p - Participant
• e - Event

The Origin is a value that is more or less meant to identify the "thing" being replicated, and in particular identify the historical lineage of the EventFold. The idea is that it is meaningless to try and merge two EventFolds that do not share a common history (identified by the origin value) and doing so is a programming error. It is only used to try and check for this type of programming error and throw an exception if it happens instead of producing undefined (and difficult to detect) behavior.

Instances

(Eq o, Eq p, Eq e, Eq (Output e)) => Eq (EventFold o p e)

Defined in Data.CRDT.EventFold

Methods

(==) :: EventFold o p e -> EventFold o p e -> Bool

(/=) :: EventFold o p e -> EventFold o p e -> Bool

(Show o, Show p, Show e, Show (Output e), Show (State e)) => Show (EventFold o p e)

Defined in Data.CRDT.EventFold

Methods

showsPrec :: Int -> EventFold o p e -> ShowS

show :: EventFold o p e -> String

showList :: [EventFold o p e] -> ShowS

(ToJSON o, ToJSON p, ToJSON e, ToJSON (Output e), ToJSON (State e)) => ToJSON (EventFold o p e)

Defined in Data.CRDT.EventFold

Methods

toJSON :: EventFold o p e -> Value

toEncoding :: EventFold o p e -> Encoding

toJSONList :: [EventFold o p e] -> Value

toEncodingList :: [EventFold o p e] -> Encoding

(Ord p, FromJSON o, FromJSON p, FromJSON e, FromJSON (Output e), FromJSON (State e)) => FromJSON (EventFold o p e)

Defined in Data.CRDT.EventFold

Methods

parseJSON :: Value -> Parser (EventFold o p e)

parseJSONList :: Value -> Parser [EventFold o p e]

(Binary o, Binary p, Binary e, Binary (Output e), Binary (State e)) => Binary (EventFold o p e)

Defined in Data.CRDT.EventFold

Methods

put :: EventFold o p e -> Put

get :: Get (EventFold o p e)

putList :: [EventFold o p e] -> Put

data EventId p

EventId is a monotonically increasing, totally ordered identification value which allows us to lend the attribute of monotonicity to event application operations which would not naturally be monotonic.

Instances

Eq p => Eq (EventId p)

Defined in Data.CRDT.EventFold

Methods

(==) :: EventId p -> EventId p -> Bool

(/=) :: EventId p -> EventId p -> Bool

Ord p => Ord (EventId p)

Defined in Data.CRDT.EventFold

Methods

compare :: EventId p -> EventId p -> Ordering

(<) :: EventId p -> EventId p -> Bool

(<=) :: EventId p -> EventId p -> Bool

(>) :: EventId p -> EventId p -> Bool

(>=) :: EventId p -> EventId p -> Bool

max :: EventId p -> EventId p -> EventId p

min :: EventId p -> EventId p -> EventId p

Show p => Show (EventId p)

Defined in Data.CRDT.EventFold

Methods

showsPrec :: Int -> EventId p -> ShowS

show :: EventId p -> String

showList :: [EventId p] -> ShowS

Generic (EventId p)

Defined in Data.CRDT.EventFold

Associated Types

type Rep (EventId p) :: Type -> Type

Methods

from :: EventId p -> Rep (EventId p) x

to :: Rep (EventId p) x -> EventId p

ToJSON p => ToJSON (EventId p)

Defined in Data.CRDT.EventFold

Methods

toJSON :: EventId p -> Value

toEncoding :: EventId p -> Encoding

toJSONList :: [EventId p] -> Value

toEncodingList :: [EventId p] -> Encoding

ToJSON p => ToJSONKey (EventId p)

Defined in Data.CRDT.EventFold

Methods

toJSONKey :: ToJSONKeyFunction (EventId p)

toJSONKeyList :: ToJSONKeyFunction [EventId p]

FromJSON p => FromJSON (EventId p)

Defined in Data.CRDT.EventFold

Methods

parseJSON :: Value -> Parser (EventId p)

parseJSONList :: Value -> Parser [EventId p]

FromJSON p => FromJSONKey (EventId p)

Defined in Data.CRDT.EventFold

Methods

fromJSONKey :: FromJSONKeyFunction (EventId p)

fromJSONKeyList :: FromJSONKeyFunction [EventId p]

Binary p => Binary (EventId p)

Defined in Data.CRDT.EventFold

Methods

put :: EventId p -> Put

get :: Get (EventId p)

putList :: [EventId p] -> Put

Default (EventId p)

Defined in Data.CRDT.EventFold

Methods

def :: EventId p

type Rep (EventId p)

Defined in Data.CRDT.EventFold

type Rep (EventId p)

data Diff o p e

A package containing events that can be merged into an event fold.

Instances

(Show o, Show p, Show e, Show (Output e)) => Show (Diff o p e)

Defined in Data.CRDT.EventFold

Methods

showsPrec :: Int -> Diff o p e -> ShowS

show :: Diff o p e -> String

showList :: [Diff o p e] -> ShowS

Generic (Diff o p e)

Defined in Data.CRDT.EventFold

Associated Types

type Rep (Diff o p e) :: Type -> Type

Methods

from :: Diff o p e -> Rep (Diff o p e) x

to :: Rep (Diff o p e) x -> Diff o p e

(ToJSON o, ToJSON p, ToJSON e, ToJSON (Output e)) => ToJSON (Diff o p e)

Defined in Data.CRDT.EventFold

Methods

toJSON :: Diff o p e -> Value

toEncoding :: Diff o p e -> Encoding

toJSONList :: [Diff o p e] -> Value

toEncodingList :: [Diff o p e] -> Encoding

(Ord p, FromJSON o, FromJSON p, FromJSON e, FromJSON (Output e)) => FromJSON (Diff o p e)

Defined in Data.CRDT.EventFold

Methods

parseJSON :: Value -> Parser (Diff o p e)

parseJSONList :: Value -> Parser [Diff o p e]

(Binary o, Binary p, Binary e, Binary (Output e)) => Binary (Diff o p e)

Defined in Data.CRDT.EventFold

Methods

put :: Diff o p e -> Put

get :: Get (Diff o p e)

putList :: [Diff o p e] -> Put

type Rep (Diff o p e)

Defined in Data.CRDT.EventFold

type Rep (Diff o p e)