Giter Club home page Giter Club logo

leveled's Introduction

Leveled - An Erlang Key-Value Store

Introduction

Leveled is a work-in-progress prototype of a simple Key-Value store based on the concept of Log-Structured Merge Trees, with the following characteristics:

  • Optimised for workloads with larger values (e.g. > 4KB).

  • Explicitly supports HEAD requests in addition to GET requests.

    • Splits the storage of value between keys/metadata and body,
    • Stores keys/metadata in a merge tree and the full object in a journal of CDB files
    • allowing for HEAD requests which have lower overheads than GET requests, and
    • queries which traverse keys/metadatas to be supported with fewer side effects on the page cache.

  • Support for tagging of object types and the implementation of alternative store behaviour based on type.

    • Potentially usable for objects with special retention or merge properties.

  • Support for low-cost clones without locking to provide for scanning queries (e.g. secondary indexes).

    • Low cost specifically where there is a need to scan across keys and metadata (not values).

  • Written in Erlang as a message passing system between Actors.

The store has been developed with a focus on being a potential backend to a Riak KV database, rather than as a generic store. It is intended to be a fully-featured backend - including support for secondary indexes, multiple fold types and auto-expiry of objects.

An optimised version of Riak KV has been produced in parallel which will exploit the availability of HEAD requests (to access object metadata including version vectors), where a full GET is not required. This, along with reduced write amplification when compared to leveldb, is expected to offer significant improvement in the volume and predictability of throughput for workloads with larger (> 4KB) object sizes, as well as reduced tail latency.

More Details

For more details on the store:

  • An introduction to Leveled covers some context to the factors motivating design trade-offs in the store.

  • The design overview explains the actor model used and the basic flow of requests through the store.

  • Future work covers new features being implemented at present, and improvements necessary to make the system production ready.

  • There is also a "Why" section looking at lower level design choices and the rationale that supports them.

Is this interesting?

Making a positive contribution to this space is hard - given the superior brainpower and experience of those that have contributed to the KV store problem space in general, and the Riak backend space in particular.

The target at inception was to do something interesting, to re-think certain key assumptions and trade-offs, and prove through working software the potential for improvements to be realised.

Initial volume tests indicate that it is at least interesting. With improvements in throughput for multiple configurations, with this improvement becoming more marked as the test progresses (and the base data volume becomes more realistic).

The delta in the table below is the comparison in Riak throughput between the identical test run with a leveled backend in comparison to leveldb. The realism of the tests increase as the test progresses - so focus is given to the throughput delta in the last hour of the test.

Test Description Hardware Duration Avg TPS TPS Delta (Overall) TPS Delta (Last Hour)
8KB value, 60 workers, sync 5 x i2.2x 4 hr 12,679.91 + 70.81% + 63.99%
8KB value, 100 workers, no_sync 5 x i2.2x 6 hr 14,100.19 + 16.15% + 35.92%
8KB value, 50 workers, no_sync 5 x d2.2x 4 hr 10,400.29 + 8.37% + 23.51%
4KB value, 100 workers, no_sync 5 x i2.2x 6 hr 14,993.95 - 10.44% - 4.48%
16KB value, 60 workers, no_sync 5 x i2.2x 6 hr 11,167.44 + 80.48% + 113.55%
8KB value, 80 workers, no_sync, 2i queries 5 x i2.2x 6 hr 9,855.96 + 4.48% + 22.36%

Tests generally show a 5:1 improvement in tail latency for leveled.

All tests have in common:

  • Target Key volume - 200M with pareto distribution of load
  • 5 GETs per 1 update
  • RAID 10 (software) drives
  • allow_mult=false, lww=false
  • modified riak optimised for leveled used in leveled tests

The throughput in leveled is generally CPU-bound, whereas in comparative tests for leveledb the throughput was disk bound. This potentially makes capacity planning simpler, and opens up the possibility of scaling out to equivalent throughput at much lower cost (as CPU is relatively low cost when compared to disk space at high I/O) - offering better alignment between resource constraints and the cost of resource.

More information can be found in the volume testing section.

As a general rule though, the most interesting thing is the potential to enable new features. The tagging of different object types, with an ability to set different rules for both compaction and metadata creation by tag, is a potential enabler for further change. Further, having a separate key/metadata store which can be scanned without breaking the page cache or working against mitigation for write amplifications, is also potentially an enabler to offer features to both the developer and the operator.

Next Steps

Further volume test scenarios are the immediate priority, in particular volume test scenarios with:

  • Significant use of secondary indexes;

  • Use of newly available EC2 hardware which potentially is a significant changes to assumptions about hardware efficiency and cost.

  • Create riak_test tests for new Riak features enabled by leveled.

However a number of other changes are planned in the next month to (my branch of) riak_kv to better use leveled:

  • Support for rapid rebuild of hashtrees

  • Fixes to priority issues

  • Experiments with flexible sync on write settings

  • A cleaner and easier build of Riak with leveled included, including cuttlefish configuration support

More information can be found in the future section.

Feedback

Please create an issue if you have any suggestions. You can ping me @masleeds if you wish

Running Leveled

Unit and current tests in leveled should run with rebar3. Leveled has been tested in OTP18, but it can be started with OTP16 to support Riak (although tests will not work as expected).

A new database can be started by running

{ok, Bookie} = leveled_bookie:book_start(RootPath, LedgerCacheSize, JournalSize, SyncStrategy)

This will start a new Bookie. It will start and look for existing data files, under the RootPath, and start empty if none exist. A LedgerCacheSize of 2000, a JournalSize of 500000000 (500MB) and a SyncStrategy of none should work OK. Further information on startup options can be found here.

The book_start method should respond once startup is complete. The leveled_bookie module includes the full API for external use of the store.

It should run anywhere that OTP will run - it has been tested on Ubuntu 14, MAC OS X and Windows 10.

Running in Riak requires one of the branches of riak_kv referenced here. There is a Riak branch intended to support the automatic build of this, and the configuration via cuttlefish. However, the auto-build fails due to other dependencies (e.g. riak_search) bringing in an alternative version of riak_kv, and the configuration via cuttlefish is broken for reasons unknown.

Building this from source as part of Riak will require a bit of fiddling around.

To help with the breakdown of cuttlefish, leveled parameters can be set via riak_kv/include/riak_kv_leveled.hrl - although a new make will be required for these changes to take effect.

Contributing

In order to contribute to leveled, fork the repository, make a branch for your changes, and open a pull request. The acceptance criteria for updating leveled is that it passes rebar3 dialyzer, xref, eunit, and ct with 100% coverage.

To have rebar3 execute the full set of tests, run:

rebar3 as test do cover --reset, eunit --cover, ct --cover, cover --verbose

leveled's People

Contributors

deadzen avatar licenser avatar martinsumner avatar russelldb avatar russelldb-bet365 avatar

Watchers

avatar avatar avatar avatar avatar

leveled's Issues

push_mem failure

I can upload the 8000 lines error message on request.

In an attempt to see what happens when overloading journal size I used a super small journal size in my test case. This is probably unrealistic and the documentation states "go not below 100MB", which in a test report I would stick to... but it might ot might not be interesting for you to see that the system crashes when a too low value is used:

leveled_eqc:init_backend(o_rkv,
    [{root_path, Dir}, {compression_point, on_compact},
     {max_journalsize, 100}],
    sut) ->
  <0.8673.0>
leveled_eqc:put(<0.8673.0>, <<98, 117, 99, 107, 101, 116, 49>>,
    <<201, 65, 121, 200, 204, 229, 237, 123, 50, 88, 42, 13, 113, 1,
      27, 115>>,
    <<53, 1, 0, 0, 0, 19, 131, 108, 0, 0, 0, 1, 104, 2, 100, 0, 5,
      108, 101, 105, 108, 97, 97, 1, 106, 0, 0, 0, 1, 0, 0, 0, 33, 1, 
      14, 67, 103, 41, 170, 57, 184, 139, 134, 123, 24, 59, 163, 4,
      205, 141, 144, 49, 101, 206, 205, 238, 47, 181, 218, 201, 219,
      16, 129, 38, 156, 201, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 1, 101, 0>>,
    [], o_rkv) ->
  ok
leveled_eqc:get(<0.8673.0>, <<98, 117, 99, 107, 101, 116, 49>>,
    <<201, 65, 121, 200, 204, 229, 237, 123, 50, 88, 42, 13, 113, 1,
      27, 115>>,
    o_rkv) ->
  {ok,
     <<53, 1, 0, 0, 0, 19, 131, 108, 0, 0, 0, 1, 104, 2, 100, 0, 5,
       108, 101, 105, 108, 97, 97, 1, 106, 0, 0, 0, 1, 0, 0, 0, 33, 1,
       14, 67, 103, 41, 170, 57, 184, 139, 134, 123, 24, 59, 163, 4,
       205, 141, 144, 49, 101, 206, 205, 238, 47, 181, 218, 201, 219,
       16, 129, 38, 156, 201, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 1, 101, 0>>}
leveled_eqc:objectfold(<0.8673.0>, o_rkv, {#Fun<eqc_fun.30.3766061>, [-20]}, false,
    0) ->
  #Fun<leveled_runner.12.26567823>
leveled_eqc:put(<0.8673.0>, <<98, 117, 99, 107, 101, 116, 49>>,
    <<201, 65, 121, 200, 204, 229, 237, 123, 50, 88, 42, 13, 113, 1,
      27, 115>>,
    <<53, 1, 0, 0, 0, 20, 131, 108, 0, 0, 0, 1, 104, 2, 100, 0, 6,
      103, 101, 111, 114, 103, 101, 97, 1, 106, 0, 0, 0, 1, 0, 0, 0,
      33, 1, 123, 60, 87, 239, 65, 182, 169, 80, 32, 153, 34, 71, 229,
      26, 139, 204, 163, 224, 155, 254, 235, 90, 253, 30, 58, 254, 3,
      138, 80, 3, 107, 191, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 1, 101, 0>>,
    [{add, dep, "s"}, {add, lib, "r"}], o_rkv) ->
  ok
leveled_eqc:stop(<0.8673.0>) -> ok
leveled_eqc:init_backend(o_rkv,
    [{root_path, Dir}, {compression_point, on_compact},
     {max_journalsize, 100}],
    sut) ->
  <0.8682.0>

=ERROR REPORT==== 28-Sep-2018::11:08:36 ===
** Generic server <0.11790.0> terminating 
** Last message in was {push_mem,
                        {{skpl,3,
                          [{{o_rkv,<<"bucket1">>,
                             <<236,194,245,87,4,207,117,144,47,229,201,106,106,
                               87,153,146>>,
                             null},

How to create correct index fields in Riak objects

Calling indexfold with the 'wrong' parameters returns an empty set of results:

leveled_eqc:init_backend(o_rkv, [{root_path, Dir}]) -> <0.669.0>
leveled_eqc:put(<0.669.0>, <<98, 117, 99, 107, 101, 116, 49>>,
    <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>,
    <<53, 1, 0, 0, 0, 44, 131, 108, 0, 0, 0, 3, 104, 2, 100, 0, 6,
      97, 108, 98, 101, 114, 116, 97, 1, 104, 2, 100, 0, 5, 108, 101,
      105, 108, 97, 97, 2, 104, 2, 100, 0, 5, 99, 108, 97, 114, 97, 97,
      3, 106, 0, 0, 0, 1, 0, 0, 0, 33, 1, 188, 209, 79, 102, 144, 93,
      252, 224, 238, 140, 79, 222, 113, 86, 179, 177, 91, 91, 22, 85,
      135, 2, 125, 198, 183, 239, 39, 219, 227, 111, 160, 28, 0, 0, 0,
      15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 101, 0>>,
    [], o_rkv) ->
  ok
leveled_eqc:indexfold(<0.669.0>,
    {<<98, 117, 99, 107, 101, 116, 51>>,
     <<150, 102, 157, 36, 213, 187, 216, 240, 27, 221, 28, 243, 131,
       76, 124, 45>>},
    fold_collect, {range, 1, 10}, {false, undefined}, 0) ->
  #Fun<leveled_runner.4.80344816>
leveled_eqc:fold_run(0, #Fun<leveled_runner.4.80344816>) -> []

But where can I find the correct way of IndexFields to be provided to Riak objects?

Parameter cache_size

The cache_size parameter supplied as option to leveled_bookie:book_start(Options) cannot be less than 4!

The code in leveled_bookie.erl reads like:

            CacheJitter = 
                proplists:get_value(cache_size, Opts) 
                    div (100 div ?CACHE_SIZE_JITTER),
            CacheSize = 
                proplists:get_value(cache_size, Opts)
                    + erlang:phash2(self()) rem CacheJitter,

Since CASHE_SIZE_JITTERis hard coded 25, we div the provided cache size by 4.
This is fine, but results for cache size 0, 1, 2, and 3 in CacheJitterto be zero. The next line divides by zero in that case.

Either clearly document this minimum cache size or improve the computation to be never dividing by zero. (A cache size of 0 may be conceptually perfectly fine as "no cache").

Max journal size crash

Branch https://github.com/Quviq/leveled/tree/bug-issue-4

When we set max journal size, we can crash the system with:

=ERROR REPORT==== 13-Sep-2018::15:11:21 ===
** Generic server <0.4465.0> terminating 
** Last message in was {'$gen_cast',
                           {hashtable_calc,
                               #Ref<0.3525012007.3535142913.63594>,2312,
                               <0.4460.0>}}
** When Server state == {state,undefined,8,
                            {cdb_options,undefined,undefined,undefined,false,
                                sync},
                            undefined,undefined,[],50.0,75.0,native}
** Reason for termination == 
** {{killed,
        {gen_fsm,sync_send_event,
            [<0.4460.0>,
             {return_hashtable,
....
             infinity]}},
    [{gen_fsm,sync_send_event,3,[{file,"gen_fsm.erl"},{line,252}]},
     {leveled_iclerk,handle_cast,2,
         [{file,
              "/Users/thomas/Quviq/Customers/NHS/leveled/_build/eqc/lib/leveled/src/leveled_iclerk.erl"},
          {line,274}]},

But the QuickCheck tests don't stop, so most likely this process is not linked to leveled

What does `first` bucket stand for?

Leveled comes with: A fast "list bucket" capability, borrowing from the HanoiDB implementation, to allow for safe bucket listing in production.

This seems to be implemented as: leveled_bookie:book_bucketlist(Pid, Tag, FoldAccT, Constraint), where Constraint is either allor frist.

First seems not well defined. It is clearly not the first key one puts in the store:

eveled_eqc:init_backend(o_rkv, [{root_path, Dir}]) -> <0.936.0>
leveled_eqc:bucketlistfold(<0.936.0>, o, {#Fun<leveled_eqc.20.95195180>, []}, first,
    0) ->
  #Fun<leveled_runner.1.80344816>
leveled_eqc:put(<0.936.0>, <<"bucket1">>,
    <<249, 60, 87, 251, 204, 206, 223, 66, 111, 136, 118, 68, 110,
      14, 103, 236>>,
    <<30, 199, 203, 190, 52, 119, 54, 137, 44, 79, 84, 199, 68, 107,
      228, 189, 5, 13, 124, 23, 162, 179, 199, 221, 89, 104, 72, 101,
      110, 226, 91, 92>>,
    [], none) ->
  ok
leveled_eqc:put(<0.936.0>, <<"bucket3">>,
    <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>,
    <<231, 14, 254, 178, 239, 24, 25, 21, 171, 196, 233, 227, 79,
      125, 156, 75, 90, 182, 250, 125, 189, 80, 107, 51, 146, 202, 249,
      80, 128, 25, 26, 89>>,
    [], none) ->
  ok
leveled_eqc:fold_run(0, #Fun<leveled_runner.1.80344816>) ->
  [<<"bucket3">>]

Nor is it the first in the list that is obtained when we supply the argument all:

leveled_eqc:init_backend(o_rkv, [{root_path, Dir}]) -> <0.1167.0>
leveled_eqc:bucketlistfold(<0.1167.0>, o, {#Fun<leveled_eqc.20.95195180>, []}, all,
    0) ->
  #Fun<leveled_runner.1.80344816>
leveled_eqc:put(<0.1167.0>, <<"bucket3">>,
    <<249, 60, 87, 251, 204, 206, 223, 66, 111, 136, 118, 68, 110,
      14, 103, 236>>,
    <<30, 199, 203, 190, 52, 119, 54, 137, 44, 79, 84, 199, 68, 107,
      228, 189, 5, 13, 124, 23, 162, 179, 199, 221, 89, 104, 72, 101,
      110, 226, 91, 92>>,
    [], none) ->
  ok
leveled_eqc:put(<0.1167.0>, <<"bucket1">>,
    <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>,
    <<231, 14, 254, 178, 239, 24, 25, 21, 171, 196, 233, 227, 79,
      125, 156, 75, 90, 182, 250, 125, 189, 80, 107, 51, 146, 202, 249,
      80, 128, 25, 26, 89>>,
    [], none) ->
  ok
leveled_eqc:fold_run(0, #Fun<leveled_runner.1.80344816>) ->
  [<<"bucket1">>,
   <<"bucket3">>]

Cretaed a manual test for this in branch: https://github.com/Quviq/leveled/tree/bug-issue-9
Run test

bucketlist_test:map_to_int().
First 1
All [0,1]
** exception error: no match of right hand side value 0
     in function  bucketlist_test:map_to_int/0 (/leveled/test/bucketlist_test.erl, line 56)

Snapshot not recognized for sqn_order fold?

The following test case is suspicious, because even though we fold with snapshot true we don't seem to get the keys from only the snapshot.

leveledjc_eqc:init_backend(o_rkv,
    [{root_path, Dir}, {log_level, error}, {max_sstslots, 2},
     {cache_size, 10}, {max_pencillercachesize, 40},
     {max_journalsize, 20000}],
    sut) ->
  <0.2667.0>
leveledjc_eqc:put(<0.2667.0>, <<98, 117, 99, 107, 101, 116, 51>>,
    <<227, 142, 0, 237, 130, 199, 37, 238, 62, 225, 139, 160, 158,
      68, 105, 142>>,
    <<53, 1, 0, 0, 0, 43, 131,....>>,
    [], o_rkv) ->
  ok

Normal start, putting 1 object. Note that object has 43 and 131 in it to distinguish it later on.
Then:

leveledjc_eqc:objectfold(<0.2667.0>, o_rkv, {#Fun<leveledjc_eqc.30.5533705>, []},
    true, sqn_order, 4) ->
  #Fun<leveled_runner.10.98249213>
leveledjc_eqc:put(<0.2667.0>, <<98, 117, 99, 107, 101, 116, 51>>,
    <<227, 142, 0, 237, 130, 199, 37, 238, 62, 225, 139, 160, 158,
      68, 105, 142>>,
    <<53, 1, 0, 0, 0, 78, 131,...>>, [], o_rkv) -> ok

Start an object fold in sequence order with SNAPSHOT true! After that, with same bucket and key add a new object. Note the 78, 131 there.
If we now run the fold, the implementation returns:

leveledjc_eqc:fold_run(4, #Fun<leveled_runner.10.98249213>) ->
  [{<<98, 117, 99, 107, 101, 116, 51>>,
    <<227, 142, 0, 237, 130, 199, 37, 238, 62, 225, 139, 160, 158,
      68, 105, 142>>,
    <<53, 1, 0, 0, 0, 78, 131,...>>},
    {<<98, 117, 99, 107, 101, 116, 51>>,
    <<227, 142, 0, 237, 130, 199, 37, 238, 62, 225, 139, 160, 158,
      68, 105, 142>>,
    <<53, 1, 0, 0, 0, 43, 131, ...>>}]

Thus both objects. This surprises me a bit, I had expected to only get the object back from the snapshot moment.

Index values need to be strings (or binaries) when using RegExp matching

Probably "obvious", but when I used integers as indexes to make it simple to say in which range the indexfold should be, everything worked fine until using RegExp matching:

leveled_eqc:init_backend(o_rkv, [{root_path, Dir}, {cache_size, 7}]) -> <0.3321.0>
leveled_eqc:indexfold(<0.3321.0>, <<98, 117, 99, 107, 101, 116, 51>>,
    {#Fun<leveled_eqc.22.101590978>, []}, {dep, 0, 2},
    {false, <<15>>}, 7) ->
  #Fun<leveled_runner.4.26787583>
leveled_eqc:put(<0.3321.0>, <<98, 117, 99, 107, 101, 116, 51>>,
    <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>,
    <<53, 1, 0, 0, 0, 77, 131, 108, 0, 0, 0, 6, 104, 2, 100, 0, 4,
      100, 97, 118, 101, 97, 1, 104, 2, 100, 0, 5, 101, 108, 116, 111,
      110, 97, 2, 104, 2, 100, 0, 5, 99, 108, 97, 114, 97, 97, 3, 104,
      2, 100, 0, 4, 100, 97, 118, 101, 97, 4, 104, 2, 100, 0, 5, 105,
      115, 97, 97, 99, 97, 5, 104, 2, 100, 0, 5, 104, 97, 114, 114,
      121, 97, 6, 106, 0, 0, 0, 1, 0, 0, 0, 33, 1, 1, 44, 80, 107, 181,
      113, 86, 30, 141, 176, 51, 8, 2, 208, 218, 45, 67, 128, 2, 32,
      16, 155, 93, 14, 128, 36, 86, 193, 190, 209, 144, 211, 0, 0, 0,
      15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 101, 0>>,
    [{add, dep, 1}], o_rkv) ->
  ok
leveled_eqc:fold_run(7, #Fun<leveled_runner.4.26787583>) ->
  {'EXIT',
     {{badarg,
         [{re, run,
             [1,
              {re_pattern, 0, 0, 0,
                 <<69, 82, 67, 80, 73, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 0, 255,
                   255, 255, 255, 255, 255, 255, 255, 15, 0, 0, 0, 0, 0, 0, 0,
                   0, 0, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 131, 0, 5, 29, 15, 120,
                   0, 5, 0>>}],
             []},

Order expectation of indexfold

Similar to bucket list, the user may have an expectation when it comes to the index items returned by leveled_bookie:book_indexfold. It seems that the implementation returns them in reverse order of what the model does...

leveled_eqc:init_backend(o_rkv, [{root_path, Dir}, {cache_size, 12}]) -> <0.26534.0>
leveled_eqc:put(<0.26534.0>, <<98, 117, 99, 107, 101, 116, 49>>,
    <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>,
    <<53, 1, 0, 0, 0, 105, 131, 108, 0, 0, 0, 8, 104, 2, 100, 0, 6,
      103, 101, 111, 114, 103, 101, 97, 1, 104, 2, 100, 0, 4, 102, 114,
      101, 100, 97, 2, 104, 2, 100, 0, 5, 99, 108, 97, 114, 97, 97, 3,
      104, 2, 100, 0, 5, 105, 115, 97, 97, 99, 97, 4, 104, 2, 100, 0,
      5, 108, 101, 105, 108, 97, 97, 5, 104, 2, 100, 0, 6, 103, 101,
      111, 114, 103, 101, 97, 6, 104, 2, 100, 0, 6, 98, 101, 114, 116,
      105, 101, 97, 7, 104, 2, 100, 0, 5, 104, 97, 114, 114, 121, 97,
      8, 106, 0, 0, 0, 1, 0, 0, 0, 33, 1, 254, 207, 219, 207, 115, 129,
      158, 140, 249, 163, 59, 148, 113, 205, 89, 162, 151, 236, 62,
      206, 126, 69, 60, 89, 219, 93, 109, 223, 132, 187, 81, 39, 0, 0,
      0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 101, 0>>,
    [{add, lib, 1}], o_rkv) ->
  ok
leveled_eqc:indexfold(<0.26534.0>, <<98, 117, 99, 107, 101, 116, 49>>,
    {#Fun<leveled_eqc.22.42128747>, []}, {lib, 0, 2},
    {true, undefined}, 2) ->
  #Fun<leveled_runner.4.80344816>
leveled_eqc:put(<0.26534.0>, <<98, 117, 99, 107, 101, 116, 49>>,
    <<214, 123, 205, 45, 25, 84, 175, 214, 88, 211, 207, 138, 157,
      181, 226, 129>>,
    <<53, 1, 0, 0, 0, 20, 131, 108, 0, 0, 0, 1, 104, 2, 100, 0, 6,
      103, 101, 111, 114, 103, 101, 97, 1, 106, 0, 0, 0, 1, 0, 0, 0,
      33, 1, 247, 96, 47, 66, 114, 22, 11, 236, 225, 43, 184, 218, 178,
      200, 16, 213, 44, 252, 173, 245, 205, 169, 44, 81, 26, 205, 174,
      203, 85, 208, 211, 202, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 1, 101, 0>>,
    [{add, lib, 1}], o_rkv) ->
  ok
leveled_eqc:fold_run(2, #Fun<leveled_runner.4.80344816>) ->
  [{<<98, 117, 99, 107, 101, 116, 49>>,
    {1,
     <<214, 123, 205, 45, 25, 84, 175, 214, 88, 211, 207, 138, 157,
       181, 226, 129>>}},
   {<<98, 117, 99, 107, 101, 116, 49>>,
    {1, <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>}}]

Sequence folding in parallel case

An unexpeced effect in book_objectfold/5

In a sequential prefix, we put an element in the store and then define a sqn_order object fold over this store with snapshot false. Then in parallel we run the fold and put one more oject in the store. That new object has the same bucket and key, but other value.

Now, I would expect to see as outcome of the fold either the first or the second put for that key. But I see both. And worst, I see the one put in first as last in the outcome of the fold!

Sequential prefix:

   leveledjc_eqc:init_backend(o_rkv,
       [{root_path, Dir}, {log_level, error}, {max_sstslots, 2},
        {cache_size, 10}, {max_pencillercachesize, 40},
        {max_journalsize, 20000}],
       sut) ->
     <0.8007.0>
   leveledjc_eqc:put(<0.8007.0>, <<98, 117, 99, 107, 101, 116, 49>>,
       <<2, 201, 141, 204, 220, 59, 44, 47, 23, 186, 96, 213, 119, 114,
         228, 125>>, 
       <<53, 1, 0, 0, 0, 95, 131, 108, 0, 0, 0, 7, 104, 2, 100, 0, 5,
         99, 108, 97, 114, 97, 97, 1, 104, 2, 100, 0, 6, 103, 101, 111,
         114, 103, 101, 97, 2, 104, 2, 100, 0, 5, 105, 115, 97, 97, 99,
         97, 3, 104, 2, 100, 0, 6, 103, 101, 111, 114, 103, 101, 97, 4,
         104, 2, 100, 0, 5, 105, 115, 97, 97, 99, 97, 5, 104, 2, 100, 0,
         6, 98, 101, 114, 116, 105, 101, 97, 6, 104, 2, 100, 0, 6, 98,
         101, 114, 116, 105, 101, 97, 7, 106, 0, 0, 0, 1, 0, 0, 1, 1, 1,
         102, 36, 5, 193, 191, 22, 53, 85, 105, 9, 89, 22, 207, 140, 34,
         144, 26, 113, 202, 213, 62, 36, 201, 186, 215, 182, 172, 163,
         168, 32, 169, 143, 244, 224, 244, 47, 8, 241, 201, 191, 3, 204,
         240, 248, 81, 29, 117, 128, 186, 180, 245, 171, 195, 63, 193, 13,
         91, 149, 200, 208, 128, 134, 245, 55, 171, 68, 159, 232, 243,
         169, 26, 45, 218, 179, 52, 49, 64, 133, 46, 134, 137, 117, 161,
         84, 146, 174, 66, 134, 42, 113, 221, 75, 57, 180, 187, 228, 174,
         30, 162, 89, 161, 26, 69, 230, 47, 144, 108, 47, 252, 212, 25,
         106, 48, 169, 204, 252, 98, 182, 21, 70, 179, 123, 132, 232, 103,
         66, 168, 91, 20, 69, 118, 109, 104, 170, 251, 52, 234, 164, 214,
         255, 228, 149, 213, 41, 225, 205, 3, 161, 242, 249, 233, 30, 43,
         54, 66, 123, 244, 61, 139, 43, 190, 192, 24, 244, 126, 245, 131,
         15, 29, 146, 230, 223, 194, 133, 35, 52, 166, 116, 107, 0, 12,
         119, 142, 221, 64, 90, 110, 6, 38, 17, 57, 66, 212, 80, 82, 35,
         123, 184, 31, 107, 35, 105, 125, 181, 82, 27, 215, 109, 232, 86,
         47, 13, 74, 126, 254, 199, 239, 128, 87, 79, 145, 123, 19, 162,
         111, 93, 191, 111, 187, 29, 243, 68, 205, 72, 140, 41, 228, 145,
         69, 122, 124, 24, 61, 106, 57, 136, 166, 97, 189, 213, 98, 147,
         189, 86, 56, 182, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 1, 101, 0>>,
       [], o_rkv) ->
     ok
   leveledjc_eqc:objectfold(<0.8007.0>, o_rkv, {#Fun<leveledjc_eqc.30.115929979>, []},
       false, sqn_order, 1) ->
     #Fun<leveled_runner.10.81953218>

Parallel:

1. leveledjc_eqc:fold_run(1, #Fun<leveled_runner.10.81953218>) ->
  [{<<98, 117, 99, 107, 101, 116, 49>>,
    <<2, 201, 141, 204, 220, 59, 44, 47, 23, 186, 96, 213, 119, 114,
      228, 125>>,
    <<53, 1, 0, 0, 0, 19, 131, 108, 0, 0, 0, 1, 104, 2, 100, 0, 5,
      105, 115, 97, 97, 99, 97, 1, 106, 0, 0, 0, 1, 0, 0, 1, 1, 1, 72,
      91, 51, 204, 93, 141, 134, 68, 135, 44, 79, 97, 32, 185, 231,
      207, 84, 127, 250, 100, 210, 95, 245, 171, 156, 134, 222, 162,
      47, 129, 81, 120, 132, 168, 55, 144, 18, 85, 77, 170, 49, 126,
      18, 189, 102, 97, 237, 249, 94, 128, 210, 250, 229, 70, 105, 152,
      31, 252, 224, 41, 145, 232, 23, 60, 58, 72, 178, 225, 10, 115,
      245, 230, 237, 114, 135, 88, 208, 125, 180, 210, 250, 76, 207,
      188, 96, 14, 32, 63, 88, 2, 254, 127, 79, 103, 22, 52, 250, 194,
      153, 168, 48, 166, 102, 210, 76, 247, 226, 137, 221, 24, 65, 76,
      66, 201, 130, 119, 55, 12, 129, 93, 131, 104, 83, 15, 233, 183,
      114, 223, 41, 229, 237, 12, 50, 219, 192, 184, 172, 77, 110, 176,
      103, 118, 10, 156, 113, 126, 52, 106, 144, 128, 125, 116, 115,
      11, 93, 149, 30, 180, 182, 68, 61, 186, 235, 113, 157, 211, 85,
      50, 78, 24, 184, 222, 14, 147, 172, 232, 100, 98, 252, 201, 22,
      83, 174, 16, 79, 30, 151, 164, 144, 17, 132, 172, 44, 41, 222,
      216, 235, 108, 160, 84, 83, 201, 212, 42, 176, 140, 202, 50, 236,
      14, 222, 111, 143, 44, 54, 98, 7, 122, 164, 21, 218, 195, 45,
      189, 97, 70, 17, 194, 53, 12, 248, 115, 166, 82, 5, 7, 76, 145,
      169, 253, 120, 219, 239, 105, 76, 9, 152, 34, 25, 198, 253, 50,
      132, 12, 94, 55, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      1, 101, 0>>},
   {<<98, 117, 99, 107, 101, 116, 49>>,
    <<2, 201, 141, 204, 220, 59, 44, 47, 23, 186, 96, 213, 119, 114,
      228, 125>>,
    <<53, 1, 0, 0, 0, 95, 131, 108, 0, 0, 0, 7, 104, 2, 100, 0, 5,
      99, 108, 97, 114, 97, 97, 1, 104, 2, 100, 0, 6, 103, 101, 111,
      114, 103, 101, 97, 2, 104, 2, 100, 0, 5, 105, 115, 97, 97, 99,
      97, 3, 104, 2, 100, 0, 6, 103, 101, 111, 114, 103, 101, 97, 4,
      104, 2, 100, 0, 5, 105, 115, 97, 97, 99, 97, 5, 104, 2, 100, 0,
      6, 98, 101, 114, 116, 105, 101, 97, 6, 104, 2, 100, 0, 6, 98,
      101, 114, 116, 105, 101, 97, 7, 106, 0, 0, 0, 1, 0, 0, 1, 1, 1,
      102, 36, 5, 193, 191, 22, 53, 85, 105, 9, 89, 22, 207, 140, 34,
      144, 26, 113, 202, 213, 62, 36, 201, 186, 215, 182, 172, 163,
      168, 32, 169, 143, 244, 224, 244, 47, 8, 241, 201, 191, 3, 204,
      240, 248, 81, 29, 117, 128, 186, 180, 245, 171, 195, 63, 193, 13,
      91, 149, 200, 208, 128, 134, 245, 55, 171, 68, 159, 232, 243,
      169, 26, 45, 218, 179, 52, 49, 64, 133, 46, 134, 137, 117, 161,
      84, 146, 174, 66, 134, 42, 113, 221, 75, 57, 180, 187, 228, 174,
      30, 162, 89, 161, 26, 69, 230, 47, 144, 108, 47, 252, 212, 25,
      106, 48, 169, 204, 252, 98, 182, 21, 70, 179, 123, 132, 232, 103,
      66, 168, 91, 20, 69, 118, 109, 104, 170, 251, 52, 234, 164, 214,
      255, 228, 149, 213, 41, 225, 205, 3, 161, 242, 249, 233, 30, 43,
      54, 66, 123, 244, 61, 139, 43, 190, 192, 24, 244, 126, 245, 131,
      15, 29, 146, 230, 223, 194, 133, 35, 52, 166, 116, 107, 0, 12,
      119, 142, 221, 64, 90, 110, 6, 38, 17, 57, 66, 212, 80, 82, 35,
      123, 184, 31, 107, 35, 105, 125, 181, 82, 27, 215, 109, 232, 86,
      47, 13, 74, 126, 254, 199, 239, 128, 87, 79, 145, 123, 19, 162,
      111, 93, 191, 111, 187, 29, 243, 68, 205, 72, 140, 41, 228, 145,
      69, 122, 124, 24, 61, 106, 57, 136, 166, 97, 189, 213, 98, 147,
      189, 86, 56, 182, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 1, 101, 0>>}]
2. leveledjc_eqc:put(<0.8007.0>, <<98, 117, 99, 107, 101, 116, 49>>,
    <<2, 201, 141, 204, 220, 59, 44, 47, 23, 186, 96, 213, 119, 114,
      228, 125>>,
    <<53, 1, 0, 0, 0, 19, 131, 108, 0, 0, 0, 1, 104, 2, 100, 0, 5,
      105, 115, 97, 97, 99, 97, 1, 106, 0, 0, 0, 1, 0, 0, 1, 1, 1, 72,
      91, 51, 204, 93, 141, 134, 68, 135, 44, 79, 97, 32, 185, 231,
      207, 84, 127, 250, 100, 210, 95, 245, 171, 156, 134, 222, 162,
      47, 129, 81, 120, 132, 168, 55, 144, 18, 85, 77, 170, 49, 126,
      18, 189, 102, 97, 237, 249, 94, 128, 210, 250, 229, 70, 105, 152,
      31, 252, 224, 41, 145, 232, 23, 60, 58, 72, 178, 225, 10, 115,
      245, 230, 237, 114, 135, 88, 208, 125, 180, 210, 250, 76, 207,
      188, 96, 14, 32, 63, 88, 2, 254, 127, 79, 103, 22, 52, 250, 194,
      153, 168, 48, 166, 102, 210, 76, 247, 226, 137, 221, 24, 65, 76,
      66, 201, 130, 119, 55, 12, 129, 93, 131, 104, 83, 15, 233, 183,
      114, 223, 41, 229, 237, 12, 50, 219, 192, 184, 172, 77, 110, 176,
      103, 118, 10, 156, 113, 126, 52, 106, 144, 128, 125, 116, 115,
      11, 93, 149, 30, 180, 182, 68, 61, 186, 235, 113, 157, 211, 85, 
      50, 78, 24, 184, 222, 14, 147, 172, 232, 100, 98, 252, 201, 22,
      83, 174, 16, 79, 30, 151, 164, 144, 17, 132, 172, 44, 41, 222,
      216, 235, 108, 160, 84, 83, 201, 212, 42, 176, 140, 202, 50, 236,
      14, 222, 111, 143, 44, 54, 98, 7, 122, 164, 21, 218, 195, 45,
      189, 97, 70, 17, 194, 53, 12, 248, 115, 166, 82, 5, 7, 76, 145,
      169, 253, 120, 219, 239, 105, 76, 9, 152, 34, 25, 198, 253, 50,
      132, 12, 94, 55, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      1, 101, 0>>,
    [], o_rkv) ->
  ok

Arbitrary fold functions in indexfold

This is one of the more confusing things, the user provides a weird fold function to indexfold:

fun(<<98, 117, 99, 107, 101, 116, 50>>,
    {4,
     <<81, 123, 207, 191, 210, 220, 49, 254, 255, 121, 189, 250, 9,
       66, 204, 140>>},
    []) ->
     [0];
   (_, _, _) -> [] end

In other words for bucket <<"bucket2">> and key {4, <<81, 123, ...>>} (which is arguably an illegal key, it returns [0] is the accumulator is [] otherwise it always returns [].

With this weird fold function we get:

leveled_eqc:init_backend(o_rkv, [{root_path, Dir}, {cache_size, 2048}]) -> <0.12848.0>
leveled_eqc:put(<0.12848.0>, <<98, 117, 99, 107, 101, 116, 50>>,
    <<81, 123, 207, 191, 210, 220, 49, 254, 255, 121, 189, 250, 9,
      66, 204, 140>>,
    <<53, 1, 0, 0, 0, 18, 131, 108, 0, 0, 0, 1, 104, 2, 100, 0, 4,
      100, 97, 118, 101, 97, 1, 106, 0, 0, 0, 1, 0, 0, 0, 33, 1, 91,
      171, 234, 119, 74, 136, 4, 227, 121, 110, 105, 133, 7, 206, 115,
      102, 149, 19, 191, 57, 60, 51, 230, 68, 51, 4, 207, 250, 69, 154,
      0, 163, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 101,
      0>>,
    [{add, dep, 2}], o_rkv) ->
  ok
leveled_eqc:put(<0.12848.0>, <<98, 117, 99, 107, 101, 116, 50>>,
    <<81, 123, 207, 191, 210, 220, 49, 254, 255, 121, 189, 250, 9,
      66, 204, 140>>,
    <<53, 1, 0, 0, 0, 57, 131, 108, 0, 0, 0, 4, 104, 2, 100, 0, 6,
      103, 101, 111, 114, 103, 101, 97, 1, 104, 2, 100, 0, 5, 105, 115,
      97, 97, 99, 97, 2, 104, 2, 100, 0, 5, 104, 97, 114, 114, 121, 97,
      3, 104, 2, 100, 0, 6, 98, 101, 114, 116, 105, 101, 97, 4, 106, 0,
      0, 0, 1, 0, 0, 0, 33, 1, 162, 232, 176, 101, 230, 234, 196, 223,
      12, 23, 2, 152, 49, 15, 20, 12, 132, 212, 179, 189, 243, 200,
      217, 26, 73, 112, 120, 222, 101, 14, 102, 218, 0, 0, 0, 15, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 101, 0>>,
    [{add, dep, 4}], o_rkv) ->
  ok
leveled_eqc:indexfold(<0.12848.0>,
    {<<98, 117, 99, 107, 101, 116, 50>>,
     <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>},
    {#Fun<eqc_fun.29.3766061>, []}, {dep, 2, 4}, {true, undefined},
    9) ->
  #Fun<leveled_runner.4.80344816>
leveled_eqc:fold_run(9, #Fun<leveled_runner.4.80344816>) -> [0]

Whereas the model expects the empty list. This again may be a fact that the order in which things are processes is reversed.

indexfold update

If we provide an IndexSpec of [{add, dep, 1}] to a specific key in a specific bucket and then overwrite with the same bucket and same key, but a different IndexSpec, viz [], then the previous IndexSpec is preserved. I interpret this as that IndexSpecs are updated according to the principle as joining the new spec with the old. If there is an add operation it is added, it there is a remove it is removed.

Is that meant to be so? It seems to work that way.

Exception when journal size too small

Branch https://github.com/Quviq/leveled/tree/bug-issue-8

When the max_journalsize is set too low, trying to put something in the store raises an exception:
{badmatch, roll}. The issue is to be able to know what the minimum max_journalsize is.

leveled_eqc:init_backend(o_rkv,
    [{root_path, Dir}, {compression_method, native},
     {max_journalsize, 1000}]) ->
  <0.616.0>
leveled_eqc:put(<0.616.0>, <<98, 117, 99, 107, 101, 116, 49>>,
    <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>,
    <<53, 1, 0, 0, 0, 56, 131, 108, 0, 0, 0, 4, 104, 2, 100, 0, 6,
      97, 108, 98, 101, 114, 116, 97, 1, 104, 2, 100, 0, 5, 101, 108,
      116, 111, 110, 97, 2, 104, 2, 100, 0, 4, 102, 114, 101, 100, 97,
      3, 104, 2, 100, 0, 6, 97, 108, 98, 101, 114, 116, 97, 4, 106, 0,
      0, 0, 1, 0, 0, 0, 33, 1, 58, 189, 235, 35, 231, 147, 94, 161,
      254, 104, 15, 93, 116, 36, 142, 204, 75, 51, 55, 108, 76, 11, 85,
      226, 62, 62, 186, 55, 9, 212, 210, 27, 0, 0, 0, 15, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 1, 101, 0>>,
    [], o_rkv) ->
  !!! {exception,
         {'EXIT',
            {{{badmatch, roll},
              [{leveled_inker, put_object, 4,
                  [{file,
                      "/Users/thomas/Quviq/Customers/NHS/leveled/_build/eqc/lib/leveled/src/leveled_inker.erl"},
                   {line, 826}]},
               {leveled_inker, handle_call, 3,
                  [{file,
                      "/Users/thomas/Quviq/Customers/NHS/leveled/_build/eqc/lib/leveled/src/leveled_inker.erl"},
                   {line, 464}]},

Index element still found after deletion

This might well be intentional. It seems that deleting an element does not remove the bucket and key from the index fold. That is, even though the element itself is deleted, the index fold returns its bucket and key:

leveled_eqc:init_backend(o_rkv, [{root_path, Dir}, {cache_size, 5000}]) -> <0.28980.0>
leveled_eqc:put(<0.28980.0>, <<98, 117, 99, 107, 101, 116, 50>>,
    <<244, 29, 74, 158, 197, 49, 213, 94, 154, 12, 235, 103, 51, 70,
      180, 212>>,
    <<53, 1, 0, 0, 0, 104, 131, 108, 0, 0, 0, 8, 104, 2, 100, 0, 6,
      98, 101, 114, 116, 105, 101, 97, 1, 104, 2, 100, 0, 4, 100, 97,
      118, 101, 97, 2, 104, 2, 100, 0, 6, 103, 101, 111, 114, 103, 101,
      97, 3, 104, 2, 100, 0, 5, 105, 115, 97, 97, 99, 97, 4, 104, 2,
      100, 0, 5, 104, 97, 114, 114, 121, 97, 5, 104, 2, 100, 0, 5, 101,
      108, 116, 111, 110, 97, 6, 104, 2, 100, 0, 4, 102, 114, 101, 100,
      97, 7, 104, 2, 100, 0, 6, 103, 101, 111, 114, 103, 101, 97, 8,
      106, 0, 0, 0, 1, 0, 0, 0, 33, 1, 154, 91, 200, 34, 30, 167, 224,
      109, 236, 76, 117, 69, 213, 47, 81, 134, 245, 94, 175, 109, 245,
      190, 197, 132, 207, 12, 135, 43, 63, 218, 76, 41, 0, 0, 0, 15, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 101, 0>>, 
    [{add, dep, 1}], o_rkv) ->
  ok
leveled_eqc:delete(<0.28980.0>, <<98, 117, 99, 107, 101, 116, 50>>,
    <<244, 29, 74, 158, 197, 49, 213, 94, 154, 12, 235, 103, 51, 70,
      180, 212>>,
    [], o_rkv) ->
  ok
leveled_eqc:indexfold(<0.28980.0>, <<98, 117, 99, 107, 101, 116, 50>>,
    {#Fun<leveled_eqc.22.33392231>, []}, {dep, 0, 2},
    {true, undefined}, 14) ->
  #Fun<leveled_runner.4.80344816>
leveled_eqc:fold_run(14, #Fun<leveled_runner.4.80344816>) ->
  [{<<98, 117, 99, 107, 101, 116, 50>>,
    {1,
     <<244, 29, 74, 158, 197, 49, 213, 94, 154, 12, 235, 103, 51, 70,
       180, 212>>}}]

Error badarg caught when safe reading a file to length ...

I have a reproducible counter example for this error message:
2018-09-27T11:21:55.885 CDB20 <0.1878.0> Error badarg caught when safe reading a file to length 0

The test case consistently producing this log message is:

leveled_eqc:init_backend(o,
    [{root_path, Dir}, {compression_point, on_compact},
     {max_journalsize, 1000}, {cache_size, 2060}],
    sut) ->
  <0.1866.0>
leveled_eqc:put(<0.1866.0>, <<98, 117, 99, 107, 101, 116, 51>>,
    <<38, 50, 201, 47, 167, 125, 57, 232, 84, 38, 14, 114, 24, 62,
      12, 74>>,
    <<87, 150, 217, 230, 4, 81, 170, 68, 181, 224, 60, 232, 4, 74,
      159, 12, 156, 56, 194, 181, 18, 158, 195, 207, 106, 191, 80, 111,
      100, 81, 252, 248>>,
    [], none) ->
  ok
leveled_eqc:put(<0.1866.0>, <<98, 117, 99, 107, 101, 116, 51>>,
    <<38, 50, 201, 47, 167, 125, 57, 232, 84, 38, 14, 114, 24, 62,
      12, 74>>,
    <<86, 201, 253, 149, 213, 10, 32, 166, 33, 136, 42, 79, 103, 250,
      139, 95, 42, 143, 161, 3, 185, 74, 149, 226, 232, 214, 183, 64,
      69, 56, 167, 78>>,
    [], none) ->
  ok
leveled_eqc:kill(<0.1866.0>) -> ok
leveled_eqc:init_backend(o,
    [{root_path, Dir}, {compression_point, on_compact},
     {max_journalsize, 1000}, {cache_size, 2060}],
    sut) ->
  error

index folding mixing up keys and indices ?

I got this weird error:

We define an index fold over range {lib, "t", "t"}, just buckets.
We put 2 objects in that bucket, one with object key <<0, 0, ...>>that has index {lib, "t"} and one with object key <<174, 4,...>> that has index {dep, "a"}.

I do not expect to get any {"t", <<174, 4,...>>} as input to the fold function, but we seem to do, since a 1 is returned

leveled_eqc:init_backend(o_rkv, [{root_path, Dir}]) -> <0.28017.0>
leveled_eqc:indexfold(<0.28017.0>, <<98, 117, 99, 107, 101, 116, 50>>,
    {#Fun<eqc_fun.29.3766061>, 0}, {lib, "t", "t"},
    {true, undefined}, 12) ->
  #Fun<leveled_runner.4.26787583>
leveled_eqc:put(<0.28017.0>, <<98, 117, 99, 107, 101, 116, 50>>,
    <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>,
    <<53, 1, 0, 0, 0, 64, 131, 108, 0, 0, 0, 5, 104, 2, 100, 0, 4,
      102, 114, 101, 100, 97, 1, 104, 2, 100, 0, 4, 102, 114, 101, 100,
      97, 2, 104, 2, 100, 0, 4, 100, 97, 118, 101, 97, 3, 104, 2, 100,
      0, 4, 102, 114, 101, 100, 97, 4, 104, 2, 100, 0, 6, 98, 101, 114,
      116, 105, 101, 97, 5, 106, 0, 0, 0, 1, 0, 0, 0, 33, 1, 122, 239,
      237, 60, 83, 129, 62, 166, 119, 34, 7, 125, 92, 243, 140, 142,
      225, 201, 9, 51, 167, 254, 212, 12, 32, 5, 202, 218, 136, 108,
      182, 217, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
      101, 0>>,
    [{add, lib, "t"}], o_rkv) ->
  ok
leveled_eqc:put(<0.28017.0>, <<98, 117, 99, 107, 101, 116, 50>>,
    <<174, 4, 133, 28, 214, 136, 15, 67, 23, 82, 97, 70, 30, 173, 5,
      176>>,
    <<53, 1, 0, 0, 0, 30, 131, 108, 0, 0, 0, 2, 104, 2, 100, 0, 5,
      105, 115, 97, 97, 99, 97, 1, 104, 2, 100, 0, 4, 102, 114, 101,
      100, 97, 2, 106, 0, 0, 0, 1, 0, 0, 0, 33, 1, 87, 14, 55, 206, 7,
      154, 13, 201, 47, 41, 233, 152, 1, 240, 246, 193, 117, 74, 128,
      150, 29, 63, 237, 84, 34, 63, 36, 38, 21, 57, 234, 213, 0, 0, 0,
      15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 101, 0>>,
    [{add, dep, "a"}, {add, lib, "t"}], o_rkv) ->
  ok
leveled_eqc:fold_run(12, #Fun<leveled_runner.4.26787583>) -> 1

Reason:
  Post-condition failed:
  1 /= 0
result: failed
#Fun<eqc_fun.29.3766061> with acc 0:
fun(<<98, 117, 99, 107, 101, 116, 50>>,
    {"t",
     <<174, 4, 133, 28, 214, 136, 15, 67, 23, 82, 97, 70, 30, 173, 5,
       176>>},
    0) ->
     1;
   (_, _, _) -> 0 end

Indexfold in the case of ReturnTerm == false

The indexfold now works for returning terms, but I do have a hard time to get the relationship with not returning terms right.

We put two elements in the same bucket, one with a large key and 2 index terms (note that this is important for the outcome, that there are 2 index terms) and one with key <<0,0,...>>and one index term. For my feeling I get the elements returned in the wrong order.

The RegExp seems not the key here, a second example below is without regexp.

leveled_eqc:init_backend(o_rkv,
    [{root_path, Dir}, {compression_point, on_compact}]) ->
  <0.15385.0>
leveled_eqc:put(<0.15385.0>, <<98, 117, 99, 107, 101, 116, 49>>,
    <<47, 4, 150, 100, 61, 203, 85, 17, 245, 160, 34, 168, 3, 123,
      132, 161>>,
    <<53, 1, 0, 0, 0, 68, 131, 108, 0, 0, 0, 5, 104, 2, 100, 0, 4,
      102, 114, 101, 100, 97, 1, 104, 2, 100, 0, 5, 99, 108, 97, 114,
      97, 97, 2, 104, 2, 100, 0, 5, 99, 108, 97, 114, 97, 97, 3, 104,
      2, 100, 0, 6, 98, 101, 114, 116, 105, 101, 97, 4, 104, 2, 100, 0,
      6, 97, 108, 98, 101, 114, 116, 97, 5, 106, 0, 0, 0, 1, 0, 0, 0,
      33, 1, 66, 79, 75, 160, 84, 237, 18, 198, 107, 191, 114, 106,
      160, 255, 227, 70, 10, 247, 245, 247, 89, 72, 154, 120, 6, 107,
      193, 202, 169, 17, 139, 64, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 1, 101, 0>>,
    [{add, dep, "a"}, {add, lib, "a"}], o_rkv) ->
  ok
leveled_eqc:put(<0.15385.0>, <<98, 117, 99, 107, 101, 116, 49>>,
    <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>,
    <<53, 1, 0, 0, 0, 93, 131, 108, 0, 0, 0, 7, 104, 2, 100, 0, 5,
      101, 108, 116, 111, 110, 97, 1, 104, 2, 100, 0, 5, 105, 115, 97,
      97, 99, 97, 2, 104, 2, 100, 0, 5, 101, 108, 116, 111, 110, 97, 3,
      104, 2, 100, 0, 5, 105, 115, 97, 97, 99, 97, 4, 104, 2, 100, 0,
      6, 98, 101, 114, 116, 105, 101, 97, 5, 104, 2, 100, 0, 6, 103,
      101, 111, 114, 103, 101, 97, 6, 104, 2, 100, 0, 5, 99, 108, 97,
      114, 97, 97, 7, 106, 0, 0, 0, 1, 0, 0, 0, 33, 1, 27, 36, 34, 17,
      240, 38, 231, 134, 36, 248, 69, 98, 175, 87, 23, 232, 181, 199,
      147, 196, 202, 7, 115, 7, 171, 161, 104, 152, 35, 150, 191, 173,
      0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 101, 0>>,
    [{add, lib, "a"}], o_rkv) ->
  ok
leveled_eqc:indexfold(<0.15385.0>,
    {<<98, 117, 99, 107, 101, 116, 49>>,
     <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>},
    {#Fun<leveled_eqc.24.51589482>, []}, {lib, "a", "a"},
    {false, "a"}, 11) ->
  #Fun<leveled_runner.4.26787583>
leveled_eqc:fold_run(11, #Fun<leveled_runner.4.26787583>) ->
  [{<<98, 117, 99, 107, 101, 116, 49>>,
    <<47, 4, 150, 100, 61, 203, 85, 17, 245, 160, 34, 168, 3, 123,
      132, 161>>},
   {<<98, 117, 99, 107, 101, 116, 49>>,
    <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>}]

Also when I provide an object key to start with, I would expect the result to have that key first and not return the larger key first.

leveled_eqc:init_backend(o_rkv,
    [{root_path, Dir}, {compression_point, on_receipt}]) ->
  <0.11741.0>
leveled_eqc:indexfold(<0.11741.0>,
    {<<98, 117, 99, 107, 101, 116, 51>>,
     <<196, 11, 24, 8, 213, 120, 140, 5, 67, 245, 203, 42, 93, 201,
       189, 23>>},
    {#Fun<leveled_eqc.24.51589482>, []}, {lib, "r", "r"},
    {false, undefined}, 3) ->
  #Fun<leveled_runner.4.26787583>
leveled_eqc:put(<0.11741.0>, <<98, 117, 99, 107, 101, 116, 51>>,
    <<196, 11, 24, 8, 213, 120, 140, 5, 67, 245, 203, 42, 93, 201,
      189, 23>>,
    <<53, 1, 0, 0, 0, 44, 131, 108, 0, 0, 0, 3, 104, 2, 100, 0, 6,
      97, 108, 98, 101, 114, 116, 97, 1, 104, 2, 100, 0, 6, 98, 101,
      114, 116, 105, 101, 97, 2, 104, 2, 100, 0, 4, 102, 114, 101, 100,
      97, 3, 106, 0, 0, 0, 1, 0, 0, 0, 33, 1, 110, 93, 158, 105, 64,
      247, 16, 129, 79, 248, 187, 190, 228, 95, 41, 176, 102, 89, 14,
      26, 128, 102, 151, 51, 222, 217, 207, 84, 22, 75, 200, 75, 0, 0,
      0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 101, 0>>,
    [{add, lib, "r"}], o_rkv) ->
  ok
leveled_eqc:put(<0.11741.0>, <<98, 117, 99, 107, 101, 116, 51>>,
    <<196, 11, 24, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>,
    <<53, 1, 0, 0, 0, 56, 131, 108, 0, 0, 0, 4, 104, 2, 100, 0, 6,
      98, 101, 114, 116, 105, 101, 97, 1, 104, 2, 100, 0, 5, 101, 108,
      116, 111, 110, 97, 2, 104, 2, 100, 0, 5, 99, 108, 97, 114, 97,
      97, 3, 104, 2, 100, 0, 5, 108, 101, 105, 108, 97, 97, 4, 106, 0,
      0, 0, 1, 0, 0, 0, 33, 1, 56, 141, 56, 152, 158, 197, 224, 65, 17,
      139, 147, 156, 111, 56, 147, 72, 79, 168, 173, 225, 186, 113, 21,
      26, 146, 65, 90, 222, 75, 201, 72, 55, 0, 0, 0, 15, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 1, 101, 0>>,
    [{add, lib, "r"}], o_rkv) ->
  ok
leveled_eqc:fold_run(3, #Fun<leveled_runner.4.26787583>) ->
  [{<<98, 117, 99, 107, 101, 116, 51>>,
    <<196, 11, 24, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>>},
   {<<98, 117, 99, 107, 101, 116, 51>>,
    <<196, 11, 24, 8, 213, 120, 140, 5, 67, 245, 203, 42, 93, 201,
      189, 23>>}]

indexfold starts at Key unclear

Branch https://github.com/Quviq/leveled/tree/bug-issue-13
hits this issue quite often

In the documentatio it states:
%% If Constraint' is a tuple of {Bucket, Key}' the fold
%% starts at `Key' (this is useful for implementing pagination, for
%% example.)

I interpreted this as: when the constraint is {<<"bucket1">>, StartKey} then only objects in bucket1 are considered that have a Key >= StartKey, where the keys are binary ordered. This was the wrong interpretation:

leveled_eqc:init_backend(o_rkv, [{root_path, Dir}, {cache_size, 2060}]) -> <0.3595.0>
leveled_eqc:put(<0.3595.0>, <<98, 117, 99, 107, 101, 116, 49>>,
    <<20, 91, 241, 215, 146, 237, 19, 70, 125, 119, 111, 60, 18, 235,
      218, 55>>,
    <<53, 1, 0, 0, 0, 20, 131, 108, 0, 0, 0, 1, 104, 2, 100, 0, 6,
      97, 108, 98, 101, 114, 116, 97, 1, 106, 0, 0, 0, 1, 0, 0, 0, 33,
      1, 63, 110, 133, 143, 1, 210, 101, 209, 98, 11, 195, 118, 33,
      204, 81, 160, 79, 107, 22, 159, 124, 84, 28, 243, 92, 129, 53,
      193, 19, 103, 50, 5, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 1, 101, 0>>,
    [{add, dep, 1}], o_rkv) ->
  ok
leveled_eqc:indexfold(<0.3595.0>,
    {<<98, 117, 99, 107, 101, 116, 49>>,
     <<212, 48, 34, 141, 50, 118, 171, 255, 204, 57, 122, 115, 20, 61,
       243, 141>>},
    {#Fun<leveled_eqc.22.13296593>, []}, {dep, 0, 2},
    {true, undefined}, 8) ->
  #Fun<leveled_runner.4.80344816>
leveled_eqc:fold_run(8, #Fun<leveled_runner.4.80344816>) ->
  [{<<98, 117, 99, 107, 101, 116, 49>>,
    {1,
     <<20, 91, 241, 215, 146, 237, 19, 70, 125, 119, 111, 60, 18, 235,
       218, 55>>}}]

The element is stored with key <<20, 91, ...>> and we use as start key <<212, 48,...>>, but we find it nevertheless.

How can I correctly interpret the specification?

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.