search

basho / riak_dt

Convergent replicated datatypes in Erlang
Apache License 2.0
353 stars 71 forks source link

Add LWW-Element-Set with Add-Wins semantic for equal timestamp #102

Open russelldb opened 10 years ago

russelldb commented 10 years ago

An LWW-Element-Set similar to Roshi/The Shapiro Tech Report. When an add and remove on the same element have the same timestamp, the add wins. Why? Makes sense to me that you only remove a element you've seen in the set, and if you remove a at time 1 then the a you saw must have been added at some time <1. Therefore an add of a at 1 is not the same a the remove wants to remove.

If there is a need for a remove wins version, we could tweak this impl to provide either based on some setup param, I guess.

Despite what the Roshi docs say, there is no GC, and there are in fact tombstones. Once an element is added it will always take up space in the datastructure.

Also, "doomstones" allowed (you can remove {a, 100000} when a is not present, and no add of a less than 100000 will work.)

cmeiklejohn commented 10 years ago

Two dialyzer errors:

riak_dt_lwwset.erl:109: Invalid type specification for function riak_dt_lwwset:add_elem/3. The success typing is (_,_,[{_,_}]) -> [{_,_}]
riak_dt_lwwset.erl:123: Invalid type specification for function riak_dt_lwwset:remove_elem/3. The success typing is (_,_,[{_,_}]) -> [{_,_}]
peterbourgon commented 10 years ago

Despite what the Roshi docs say, there is no GC, and there are in fact tombstones.

I'll update Roshi's docs to clarify my (perhaps eccentric) use of the term GC, and explicitly mention the possibility of doomstones (hehe). Thanks for writing!

russelldb commented 6 years ago

Re-based on develop. Brought up to date.

make test passes (including eqc) dialyzer passes

Just needs a friendly lil' +1 from someone out there…