lasp-lang / lasp Goto Github PK

Implement an active anti-entropy strategy to repair variables which didn't get updated during quorum operations because of partial failure.

Add support for using the observed-removed set.

The threshold read test for EQC never generates a value that's greater than the current value; only the same. This lack of coverage prevented discovery of a bug where a the current values binding name Value was used in a receive block preventing the receipt of a message from a value greater than the threshold. See commit cmeiklejohn/derflow@79f142e.

Try to replace the server in the ad counter with a new primitive operation for performing the change.

Partial binds are not implemented for applications running at a single replica which have been transformed via the derflow_transform. Implement.

These are missing, as they weren't needed for an evaluation of the model.

Correctly supervise operations such as map, fold, etc., to ensure they are restarted correctly. This is inter-replica and intra-replica.

Read with no threshold is broken because it assumes bottom is undefined, which is not true for lattices such as the riak_dt_gset.

Add full support for the ORSWOT.

Right now, only part of the derflow_vnode uses the derflow_ets backend. We need to ensure all operations in the derflow_vnode code uses the implementation in derflow_ets. This cuts down on code duplication, and increases level of testing, given derflow_ets is QuickCheck'd.

Graph with one line total for all nodes with three lines: state AAE, state AAE + tree, delta AAE.

Trying to follow along with http://christophermeiklejohn.com/derflow/erlang/2014/09/28/try-derflow.html
Used kerl to install different versions of Erlang, including R16B02 (and activated it).
Followed the steps in the article and everything seems to work until the last bit below.
Can you tell anything from that? Outside of installing Erlang haven't done anything else besides the steps mentioned in the article and perhaps have failed with some of those (like the config paths).

CrimsonTide-2:derflow cricketgeek$ make riak-test
/Users/cricketgeek/software/derflow/rebar get-deps
==> goldrush (get-deps)
==> lager (get-deps)
==> poolboy (get-deps)
==> basho_stats (get-deps)
==> getopt (get-deps)
==> neotoma (get-deps)
==> cuttlefish (get-deps)
==> riak_sysmon (get-deps)
==> bear (get-deps)
==> meck (get-deps)
==> folsom (get-deps)
==> eleveldb (get-deps)
==> riak_ensemble (get-deps)
==> pbkdf2 (get-deps)
==> riak_core (get-deps)
==> riak_dt (get-deps)
==> druuid (get-deps)
==> rel (get-deps)
==> derflow (get-deps)
/Users/cricketgeek/software/derflow/rebar compile
==> goldrush (compile)
==> lager (compile)
==> poolboy (compile)
==> basho_stats (compile)
==> getopt (compile)
==> neotoma (compile)
==> cuttlefish (compile)
==> getopt (escriptize)
==> goldrush (escriptize)
==> lager (escriptize)
==> neotoma (escriptize)
==> cuttlefish (escriptize)
==> riak_sysmon (compile)
==> bear (compile)
==> meck (compile)
==> folsom (compile)
==> eleveldb (compile)
/Applications/Xcode.app/Contents/Developer/usr/bin/make all-am
make[2]: Nothing to be done for `all-am'.
test -z "/Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/lib" || ./install-sh -c -d "/Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/lib"
/bin/sh ./libtool --mode=install /usr/bin/install -c libsnappy.la '/Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/lib'
libtool: install: /usr/bin/install -c .libs/libsnappy.1.dylib /Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/lib/libsnappy.1.dylib
libtool: install: (cd /Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/lib && { ln -s -f libsnappy.1.dylib libsnappy.dylib || { rm -f libsnappy.dylib && ln -s libsnappy.1.dylib libsnappy.dylib; }; })
libtool: install: /usr/bin/install -c .libs/libsnappy.lai /Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/lib/libsnappy.la
libtool: install: /usr/bin/install -c .libs/libsnappy.a /Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/lib/libsnappy.a
libtool: install: chmod 644 /Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/lib/libsnappy.a

libtool: install: ranlib /Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/lib/libsnappy.a

Libraries have been installed in:
/Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/lib

If you ever happen to want to link against installed libraries
in a given directory, LIBDIR, you must either use libtool, and
specify the full pathname of the library, or use the `-LLIBDIR'
flag during linking and do at least one of the following:

• add LIBDIR to the `DYLD_LIBRARY_PATH' environment variable
  during execution

See any operating system documentation about shared libraries for

more information, such as the ld(1) and ld.so(8) manual pages.

test -z "/Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/share/doc/snappy" || ./install-sh -c -d "/Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/share/doc/snappy"
/usr/bin/install -c -m 644 ChangeLog COPYING INSTALL NEWS README format_description.txt '/Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/share/doc/snappy'
test -z "/Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/include" || ./install-sh -c -d "/Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/include"
/usr/bin/install -c -m 644 snappy.h snappy-sinksource.h snappy-stubs-public.h snappy-c.h '/Users/cricketgeek/software/derflow/deps/eleveldb/c_src/system/include'
make[1]: Nothing to be done for `all'.
==> riak_ensemble (compile)
==> pbkdf2 (compile)
==> riak_core (compile)
==> riak_dt (compile)
==> druuid (compile)
~/software/derflow/deps/druuid/c_src ~/software/derflow/deps/druuid
==> rel (compile)
==> derflow (compile)
/Users/cricketgeek/software/derflow/rebar skip_deps=true riak_test_compile
==> rel (riak_test_compile)
==> derflow (riak_test_compile)
../riak_test/riak_test -v -c derflow -t riak_test/derflow_adcounter_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_bind_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_bounded_buffer_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_get_minimum_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_global_programs_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_lattice_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_map_reduce_failure_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_monitor_ports_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_producer_consumer_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_programs_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_sieve_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_threshold_read_test.erl; ../riak_test/riak_test -v -c derflow -t riak_test/derflow_video_display_test.erl;
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
escript: exception error: no function clause matching
rt_config:'-load_dot_config/2-lc$^1/1-1-'(undefined) (src/rt_config.erl, line 71)
in function rt_config:load_dot_config/2 (src/rt_config.erl, line 71)
in call from riak_test_escript:main/1 (src/riak_test_escript.erl, line 91)
in call from escript:run/2 (escript.erl, line 747)
in call from escript:start/1 (escript.erl, line 277)
in call from init:start_it/1
in call from init:start_em/1
make: *** [riak-test] Error 127

Right now, if X is declared on partition 1, Y declared on partition 2 and bound to X, and Z is declared on partition 1 and bound to Y; during bind operations we create a deadlock given the cycle in the graph.

When binding to a variable, it should bind to it's transitive dependency -- when Z is bound to Y, it should be bound to X instead, because of it's transitive dependency.

Remove pid from the return value of calls, given these calls assume there will only ever be one pid.

Ensure conversion of the remainder of the examples to use the riak_test style of testing.

Add the immutable record structure we discussed at UCL two weeks ago.

Finish the prototype of the eqc_temporal test.

Implement the connect operation for variables, so we can integrate with Riak.

Rename the threshold read operation to be monotonic read, given it's not the same thing.

Implement a strategy for anti-entropy.

The most basic anti-entropy mechanism would read-repair across all values in the cluster, which might be sufficient for the prototype. The most advanced anti-entropy strategy would use the merkle tree based approach used by both yokozuna and riak_kv.

EQC should cover the partial bind scenario.

Add support for the riak_dt_map.

When a variable is partially bound, the inflation only triggers the value to bind once.

The wait_needed operator doesn't work correctly with monotonic reads. It will unblock immediately, instead of waiting until the threshold has been met.

Implement a single-assignment lattice, to reduce the complexity of the code, allowing us to remove the mirror code path for just single-assignment operations.

Implement garbage collection for the delta-based anti-entropy strategy.

When we moved to running code at the replicas, we pulled out the finite state machines for the core API, so things assume a N value of 1. We need to get these finite state machines back in.

The advertisement counter example is generating errors at the virtual node, which are not crashing the application. It's unclear if the example is working correctly or not. Investigate.

Handoff for derflow_vnode does not work correctly. We decided to not merge the last implementation because it was not correct.

Here's a rough outline of what needs to happen:

• Need to hand off ETS table values, merge with remote state, and trigger any notifications for bound variables during the handoff process.
• Programs need to be handed off, recompiled, and restarted based on local state.
• Tests to cover these cases.
• Support for restarting select and join operations.

At the end of the 'lasp_advertisement_counter_SUITE' tests, there are some errors (the results of tests are successful):

2016-04-06 12:10:12.773 [info] <0.825.0>@lasp_simulation:run:87 Waiting for event generation to complete!
2016-04-06 12:10:12.781 [info] <0.825.0>@lasp_advertisement_counter:wait:212 Events all processed!
2016-04-06 12:10:12.783 [info] <0.825.0>@lasp_simulation:run:91 Terminating clients!
2016-04-06 12:10:12.783 [info] <0.825.0>@lasp_process_sup:terminate:46 Terminating: [{undefined,<0.828.0>,worker,[gen_flow]},{undefined,<0.829.0>,worker,[gen_flow]},{undefined,<0.830.0>,worker,[gen_flow]}]
2016-04-06 12:10:17.800 [error] <0.508.0> Supervisor lasp_process_sup had child undefined started with gen_flow:start_link(lasp_process) at <0.828.0> exit with reason killed in context shutdown_error
2016-04-06 12:10:22.813 [error] <0.508.0> Supervisor lasp_process_sup had child undefined started with gen_flow:start_link(lasp_process) at <0.829.0> exit with reason killed in context shutdown_error
2016-04-06 12:10:27.871 [error] <0.508.0> Supervisor lasp_process_sup had child undefined started with gen_flow:start_link(lasp_process) at <0.830.0> exit with reason killed in context shutdown_error
2016-04-06 12:10:27.903 [info] <0.511.0>@lasp_divergence_instrumentation:handle_call:117 Total events seen: 79342
2016-04-06 12:10:27.903 [info] <0.511.0>@lasp_divergence_instrumentation:handle_call:118 Total decrements seen: 78498
2016-04-06 12:10:27.904 [info] <0.509.0>@lasp_transmission_instrumentation:handle_call:107 Instrumentation timer for client disabled!
2016-04-06 12:10:27.940 [info] <0.510.0>@lasp_transmission_instrumentation:handle_call:107 Instrumentation timer for server disabled!

With 0eb357a, the project doesn't build from a clean checkout. If you check out the preceding commit, build once, then go back to HEAD and build that, it builds fine.

The error is

==> derflow (compile)
src/riak_dt_sum.erl:148: can't find include file "riak_dt_tags.hrl"
ERROR: compile failed while processing /Users/iain/Code/derflow: rebar_abort
make: *** [compile] Error 1

Extract out a behavior for derflow_ets, responsible for controlling the underlying storage layer and execution model.

Change identifiers to include the type information in them, so out of order deliveries of bind and declare calls can use the bottom value for the lattice.

Resolve problems with the documentation generation not working correctly.

It's clear that when running the simulations the biggest bottleneck is the synchronous call to the Plumtree backend to broadcast a particular value.

Instead, we should asynchronously accept the values to broadcast and only transmit every X seconds, batching updates -- this is especially true because any delay doesn't sacrifice the correctness of the application -- and, successive incrementing of the advertisement counter shouldn't result in a single broadcast for every value -- we can basically just sent the last value.

This is because of the use of Creator in the record for tracking it.

Ensure correct operation under a higher N value -- this is most likely currently broken given that we never merge values or supervise all processes spawned.

Implement the join operation.

Currently, the EQC model only generates read threshold and bind operations given one operation applied to the data type -- this means counters are usually one item and sets only contain one item. Modify the threshold and value generation code to use an arbitrary number of operations.

Right now, the plumtree is using custom ?READ and ?BIND macros that do the same as the
macros defined in lasp_core.

test

Each partition assumes it will only ever receive requests for variables it knows about -- if two partitions occur during subsequent declare and bind operations, the declare and bind, given quorum operations, might happen on disjoint sets. In this case, a subsequent read or bind will fail and crash with a badmatch because the code retrieving the variable from ets will assume a successful match.

Make the code resilient to this case and either fail with an error, or retry.