crdt-event-fold-1.4.0.0: Garbage collected event folding CRDT.

Data.CRDT.EventFold

Description

Synopsis

# 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

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.

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

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.

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.

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 Source #

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 FieldsurEventFold :: EventFold o p eThe new EventFold value urOutputs :: Map (EventId p) (Output e)Any consistent outputs resulting from the update.urNeedsPropagation :: BoolTrue 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 Source #

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

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 Source #

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

Instances details
 (Show (Output e), Show o, Show p, Show e, Show (State e)) => Show (MergeError o p e) Source # Instance detailsDefined in Data.CRDT.EventFold MethodsshowsPrec :: Int -> MergeError o p e -> ShowS #show :: MergeError o p e -> String #showList :: [MergeError o p e] -> ShowS # Generic (MergeError o p e) Source # Instance detailsDefined in Data.CRDT.EventFold Associated Typestype Rep (MergeError o p e) :: Type -> Type # Methodsfrom :: 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) Source # Instance detailsDefined in Data.CRDT.EventFold MethodstoJSON :: 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) Source # Instance detailsDefined in Data.CRDT.EventFold MethodsparseJSON :: Value -> Parser (MergeError o p e) #parseJSONList :: Value -> Parser [MergeError o p e] # type Rep (MergeError o p e) Source # Instance detailsDefined in Data.CRDT.EventFold type Rep (MergeError o p e) = D1 ('MetaData "MergeError" "Data.CRDT.EventFold" "crdt-event-fold-1.4.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

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

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 Source #

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 Source #

type State e Source #

Methods

apply :: e -> State e -> EventResult e Source #

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

#### Instances

Instances details
 Event () Source # The most trivial event type. Instance detailsDefined in Data.CRDT.EventFold Associated Typestype Output () Source #type State () Source # Methodsapply :: () -> State () -> EventResult () Source # (Event a, Event b) => Event (Either a b) Source # The union of two event types. Instance detailsDefined in Data.CRDT.EventFold Associated Typestype Output (Either a b) Source #type State (Either a b) Source # Methodsapply :: Either a b -> State (Either a b) -> EventResult (Either a b) Source #

data EventResult e Source #

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 Source #

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 Source #

Return the current projected value of the EventFold.

infimumValue :: EventFold o p e -> State e Source #

Return the current infimum value of the EventFold.

infimumId :: EventFold o p e -> EventId p Source #

Return the EventId of the infimum value.

infimumParticipants :: EventFold o p e -> Set p Source #

Gets the known participants at the infimum.

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

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

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

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

origin :: EventFold o p e -> o Source #

Return the origin value of the EventFold.

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

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 Source #

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

Instances details
 (Eq o, Eq p, Eq e, Eq (Output e)) => Eq (EventFold o p e) Source # Instance detailsDefined 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) Source # Instance detailsDefined in Data.CRDT.EventFold MethodsshowsPrec :: 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) Source # Instance detailsDefined in Data.CRDT.EventFold MethodstoJSON :: 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) Source # Instance detailsDefined in Data.CRDT.EventFold MethodsparseJSON :: 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) Source # Instance detailsDefined in Data.CRDT.EventFold Methodsput :: EventFold o p e -> Put #get :: Get (EventFold o p e) #putList :: [EventFold o p e] -> Put #

data EventId p Source #

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

Instances details
 Eq p => Eq (EventId p) Source # Instance detailsDefined in Data.CRDT.EventFold Methods(==) :: EventId p -> EventId p -> Bool #(/=) :: EventId p -> EventId p -> Bool # Ord p => Ord (EventId p) Source # Instance detailsDefined in Data.CRDT.EventFold Methodscompare :: 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) Source # Instance detailsDefined in Data.CRDT.EventFold MethodsshowsPrec :: Int -> EventId p -> ShowS #show :: EventId p -> String #showList :: [EventId p] -> ShowS # Source # Instance detailsDefined in Data.CRDT.EventFold Associated Typestype Rep (EventId p) :: Type -> Type # Methodsfrom :: EventId p -> Rep (EventId p) x #to :: Rep (EventId p) x -> EventId p # ToJSON p => ToJSON (EventId p) Source # Instance detailsDefined in Data.CRDT.EventFold MethodstoJSON :: EventId p -> Value #toJSONList :: [EventId p] -> Value #toEncodingList :: [EventId p] -> Encoding # ToJSON p => ToJSONKey (EventId p) Source # Instance detailsDefined in Data.CRDT.EventFold Methods FromJSON p => FromJSON (EventId p) Source # Instance detailsDefined in Data.CRDT.EventFold MethodsparseJSON :: Value -> Parser (EventId p) # FromJSON p => FromJSONKey (EventId p) Source # Instance detailsDefined in Data.CRDT.EventFold Methods Binary p => Binary (EventId p) Source # Instance detailsDefined in Data.CRDT.EventFold Methodsput :: EventId p -> Put #get :: Get (EventId p) #putList :: [EventId p] -> Put # Source # Instance detailsDefined in Data.CRDT.EventFold Methodsdef :: EventId p # type Rep (EventId p) Source # Instance detailsDefined in Data.CRDT.EventFold type Rep (EventId p)

data Diff o p e Source #

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

#### Instances

Instances details
 (Show o, Show p, Show e, Show (Output e)) => Show (Diff o p e) Source # Instance detailsDefined in Data.CRDT.EventFold MethodsshowsPrec :: Int -> Diff o p e -> ShowS #show :: Diff o p e -> String #showList :: [Diff o p e] -> ShowS # Generic (Diff o p e) Source # Instance detailsDefined in Data.CRDT.EventFold Associated Typestype Rep (Diff o p e) :: Type -> Type # Methodsfrom :: 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) Source # Instance detailsDefined in Data.CRDT.EventFold MethodstoJSON :: 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) Source # Instance detailsDefined in Data.CRDT.EventFold MethodsparseJSON :: 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) Source # Instance detailsDefined in Data.CRDT.EventFold Methodsput :: Diff o p e -> Put #get :: Get (Diff o p e) #putList :: [Diff o p e] -> Put # type Rep (Diff o p e) Source # Instance detailsDefined in Data.CRDT.EventFold type Rep (Diff o p e)