Safe Haskell	None
Language	Haskell2010

Data.CRDT.EventFold

Contents

Overview
- Garbage Collection
- A Belabored Analogy
Basic API
Inspecting the EventFold
Underlying Types

Description

Synopsis

new :: forall o p e. (Default (State e), Event p e, Ord p) => o -> p -> EventFold o p e
event :: forall o p e. (Event p e, Ord p) => p -> e -> EventFold o p e -> (Output e, EventId p, UpdateResult o p e)
fullMerge :: (Eq (Output e), Eq e, Eq o, Event p e, Ord p) => p -> EventFold o p e -> EventFold o p e -> Either (MergeError o p e) (UpdateResult o p e)
fullMerge_ :: (Eq (Output e), Eq e, Eq o, Event p e, Ord p) => EventFold o p e -> EventFold o p e -> Either (MergeError o p e) (UpdateResult o p e)
data UpdateResult o p e = UpdateResult {
- urEventFold :: EventFold o p e
- urOutputs :: Map (EventId p) (Output e)
- urNeedsPropagation :: Bool
}
events :: forall o p e. Ord p => p -> EventFold o p e -> Maybe (Diff o p e)
diffMerge :: (Eq (Output e), Eq e, Eq o, Event p e, Ord p) => p -> EventFold o p e -> Diff o p e -> Either (MergeError o p e) (UpdateResult o p e)
diffMerge_ :: forall o p e. (Eq (Output e), Eq e, Eq o, Event p e, Ord p) => EventFold o p e -> Diff o p e -> Either (MergeError o p e) (UpdateResult o p e)
data MergeError o p e
- = DifferentOrigins o o
- | DiffTooNew (EventFold o p e) (Diff o p e)
- | DiffTooSparse (EventFold o p e) (Diff o p e)
acknowledge :: (Eq (Output e), Eq e, Eq o, Event p e, Ord p) => p -> EventFold o p e -> UpdateResult o p e
participate :: forall o p e. (Event p e, Ord p) => p -> p -> EventFold o p e -> (EventId p, UpdateResult o p e)
disassociate :: forall o p e. (Event p e, Ord p) => p -> EventFold o p e -> (EventId p, UpdateResult o p e)
class Event p e where
- type Output e
- type State e
- apply :: e -> State e -> EventResult e
- join :: p -> State e -> State e
- unjoin :: p -> State e -> State e
data EventResult e
- = SystemError (Output e)
- | Pure (Output e) (State e)
isBlockedOnError :: EventFold o p e -> Bool
projectedValue :: forall o p e. Event p e => EventFold o p e -> State e
infimumValue :: EventFold o p e -> State e
infimumId :: EventFold o p e -> EventId p
infimumParticipants :: EventFold o p e -> Set p
allParticipants :: Ord p => EventFold o p e -> Set p
projParticipants :: Ord p => EventFold o p e -> Set p
origin :: EventFold o p e -> o
divergent :: forall o p e. Ord p => EventFold o p e -> Map p (EventId p)
source :: EventId p -> Maybe p
data EventFold o p e
data EventId p
bottomEid :: EventId p
data Diff o p e

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

Arguments

:: forall o p e. (Default (State e), Event p 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 :: forall o p e. (Event p e, Ord p) => 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.

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

Arguments

:: (Eq (Output e), Eq e, Eq o, Event p 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".

fullMerge_ Source #

Arguments

:: (Eq (Output e), Eq e, Eq o, Event p e, Ord p)
=> 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)

Like fullMerge, but without the automatic acknowlegement.

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
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.

Instances

Instances details

(Show (Output e), Show (State e), Show e, Show o, Show p) => Show (UpdateResult o p e) Source #
Instance details Defined in Data.CRDT.EventFold Methods showsPrec :: Int -> UpdateResult o p e -> ShowS # show :: UpdateResult o p e -> String # showList :: [UpdateResult o p e] -> ShowS #

events Source #

Arguments

:: forall o p e. Ord p
=> p	The participant to which we are sending the `Diff`.
-> EventFold o p e	The EventFold being propagated.
-> Maybe (Diff o p e)	`Nothing` if the participant must perform a `fullMerge` in order to maintain consistency. `Just` if a less expensive `diffMerge` will suffice.

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

It isn't always the case that a less expensive diffMerge is sufficient to maintain consistency. For instance, if the initial participate for a participant hasn't reached the infimum yet then there is no way to guarantee that the target will receive every new event from every participant (because an old participant might not even know about the new participant, because being part of the infimum is the definition of all participants knowing a thing).

If the new participant doesn't receive every event, then it obviously can't apply the missing events. Therefore, until it's participate event is part of the infimum, it must receive infimum values that have the missing events pre-applied by some other participant.

diffMerge Source #

Arguments

:: (Eq (Output e), Eq e, Eq o, Event p 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.

diffMerge_ Source #

Arguments

:: forall o p e. (Eq (Output e), Eq e, Eq o, Event p e, Ord p)
=> 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 diffMerge, but without automatic acknowledgement.

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 `EventFold`s do not have the same origin. It makes no sense to merge `EventFold`s 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

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

Instance details

:: forall o p e. (Event p e, Ord p)
=> p	The local participant.
-> p	The participant being added.
-> EventFold o p e
-> (EventId p, UpdateResult o p e)

:: forall o p e. (Event p e, Ord p)
=> p	The peer removing itself from participation.
-> EventFold o p e
-> (EventId p, UpdateResult o p e)

Overview

Garbage Collection

A Belabored Analogy

Basic API

Creating new CRDTs

Adding new events

Coordinating replica updates

Instances

Instances

Participation

Defining your state and events

Instances

Inspecting the EventFold

Underlying Types

Instances

Instances

Instances

Inspecting the `EventFold`