How to do CRDTs about cloudstate HOT 4 CLOSED

By the way, one reason why it would be difficult if not impossible to offer the high level version of the protocol, is for example, let's say you're implementing a GSet. You might offer an operation to add an element. That element gets serialized to protobuf, and sent to Akka as part of an "add to gset" operation. But to add it to the set, there needs to be an equality function defined for it. But, how do you compare a serialized protobuf byte string to another serialized protobuf byte string to know if they are equal or not? Is the serialization stable? Will the order of fields always be the same? Is a missing value, and a default value, the same thing? My research indicates that you can't just compare the bytes, and there are a few problems that could occur if you try to do things more intelligently. So, I think data types themselves have to be managed in the user functions, where things like equality can be well defined.

from cloudstate.

That said, equality could be defined by a user function defined, so as long as the user function ensured that the hash was unique (enough), and stable, then that would work.

from cloudstate.

Thinking further, maybe we could simply expose the higher level protocol.

Some questions. How do state updates get to the entity?

• We could, on every command for an entity, do a local read, serialise the whole state, and send it to the function. That's fine for something like a PNCounter, not so fine, for example, for an ORSet which might be used as a presence indicator for all connected users.
• Another option might be to have long lived streams (as we do for event sourced entities) per CRDT. These might be established when the first command for the entity comes in, and might also have a configurable passivation timeout. The CRDT could be either updated by doing a local read each time a command comes in, and sending deltas across then, or by subscribing to changes and sending deltas as they arrive. The challenge here I think is calculating the deltas. For registers, flags and counters, we can just not use deltas, send the whole state each time it changes. For sets and maps, we would need to only send changed elements. Note that we don't have to send the full CRDT state - the user function isn't participating in the CRDT directly, we can locally in the Akka sidecar know what state we have sent it, calculate deltas, and send it the changes. So for a GCounter, we only have to send the total, we don't have to send the total for each node. For an ORSet, we only need to synchronous the current contents of the set, we don't need to worry about version vectors or anything like that.

Calculating deltas could be expensive if the map/set is large, and unfortunately, I don't think Akka ddata makes it easy to get just deltas from its public API, the subscriptions give the full state, not what's changed. For a set, you'd do a filter of both to calculate elements added and removed. For a map, you'd have to also compare all the values of the map. In both instances, I think the complexity is n. For frequently updated large CRDTs, that's likely to be expensive. I wonder whether there's a way we could make ddata expose change info?

For updates, we would expose operations similar to what the CRDT types themselves expose. For ORMap, it would be interesting, you would have a recursive structure of operations.

from cloudstate.

Implemented in 0.4.3

from cloudstate.