You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@couchdb.apache.org by da...@apache.org on 2020/03/05 18:16:42 UTC

[couchdb] branch prototype/fdb-layer-couch-views-size-tests updated (983c4fa -> 3baaef6)

This is an automated email from the ASF dual-hosted git repository.

davisp pushed a change to branch prototype/fdb-layer-couch-views-size-tests
in repository https://gitbox.apache.org/repos/asf/couchdb.git.


 discard 983c4fa  WIP: All tests passing
 discard 02bae27  Don't store `{0,0,[]}` for views with new results
 discard 59f950a  Fix handling of duplicate keys
 discard ef62cb5  WIP: validating indexes
 discard 87e307f  WIP: New permute added
 discard 010c88d  WIP: trying permute
 discard 685481f  WIP: generating test cases
 discard b8742a7  WIP: Test generation
 discard de409f2  Refactor view index layout
     add c9175af  Fix couch_views type in wait_for_job
     add ee150f4  standardize couch_views_indexer_tests
     add 4bd68d1  Add Key/Value size limit for map indexes
     add 735b3f6  Enable fdb feature
     add 2fe1666  Clean up view size limit enforcement
     new 49aec4b  Refactor view index layout
     new 20e5e44  Fix handling of duplicate keys
     new 77f031f  Don't store `{0,0,[]}` for views with new results
     new 3baaef6  Test size calculations for view rows

This update added new revisions after undoing existing revisions.
That is to say, some revisions that were in the old version of the
branch are not in the new version.  This situation occurs
when a user --force pushes a change and generates a repository
containing something like this:

 * -- * -- B -- O -- O -- O   (983c4fa)
            \
             N -- N -- N   refs/heads/prototype/fdb-layer-couch-views-size-tests (3baaef6)

You should already have received notification emails for all of the O
revisions, and so the following emails describe only the N revisions
from the common base, B.

Any revisions marked "omit" are not gone; other references still
refer to them.  Any revisions marked "discard" are gone forever.

The 4 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.


Summary of changes:
 rel/overlay/etc/default.ini                       |   4 +
 src/couch_views/src/couch_views_fdb.erl           |  28 +--
 src/couch_views/src/couch_views_indexer.erl       |  57 ++++-
 src/couch_views/src/couch_views_jobs.erl          |   2 +-
 src/couch_views/test/couch_views_indexer_test.erl | 243 ++++++++++++++++++++--
 src/couch_views/test/couch_views_size_test.erl    | 124 ++++++-----
 src/fabric/src/fabric2_sup.erl                    |   1 +
 7 files changed, 372 insertions(+), 87 deletions(-)


[couchdb] 03/04: Don't store `{0,0,[]}` for views with new results

Posted by da...@apache.org.
This is an automated email from the ASF dual-hosted git repository.

davisp pushed a commit to branch prototype/fdb-layer-couch-views-size-tests
in repository https://gitbox.apache.org/repos/asf/couchdb.git

commit 77f031f0b858829fb60c6509ea90a848c78c9230
Author: Paul J. Davis <pa...@gmail.com>
AuthorDate: Wed Mar 4 13:10:02 2020 -0600

    Don't store `{0,0,[]}` for views with new results
    
    This saves us a key/value pair for any document that is not included as
    part of a view.
---
 src/couch_views/src/couch_views_fdb.erl           | 8 ++++++++
 src/couch_views/test/couch_views_indexer_test.erl | 4 ++--
 2 files changed, 10 insertions(+), 2 deletions(-)

diff --git a/src/couch_views/src/couch_views_fdb.erl b/src/couch_views/src/couch_views_fdb.erl
index 98257f3..a0224b2 100644
--- a/src/couch_views/src/couch_views_fdb.erl
+++ b/src/couch_views/src/couch_views_fdb.erl
@@ -205,6 +205,14 @@ clear_map_idx(TxDb, Sig, ViewId, DocId, ViewKeys) ->
     end, ViewKeys).
 
 
+update_id_idx(TxDb, Sig, ViewId, DocId, [], _KVSize) ->
+    #{
+        tx := Tx,
+        db_prefix := DbPrefix
+    } = TxDb,
+    Key = id_idx_key(DbPrefix, Sig, DocId, ViewId),
+    ok = erlfdb:clear(Tx, Key);
+
 update_id_idx(TxDb, Sig, ViewId, DocId, NewRows, KVSize) ->
     #{
         tx := Tx,
diff --git a/src/couch_views/test/couch_views_indexer_test.erl b/src/couch_views/test/couch_views_indexer_test.erl
index 9b12af6..d941d93 100644
--- a/src/couch_views/test/couch_views_indexer_test.erl
+++ b/src/couch_views/test/couch_views_indexer_test.erl
@@ -161,7 +161,7 @@ updated_docs_are_reindexed(Db) ->
     Sig = Mrst#mrst.sig,
     fabric2_fdb:transactional(Db, fun(TxDb) ->
         ?assertMatch(
-                [{0, 1, _, [1]}, {1, 0, 0, []}],
+                [{0, 1, _, [1]}],
                 couch_views_fdb:get_view_keys(TxDb, Sig, <<"0">>)
             )
     end).
@@ -217,7 +217,7 @@ updated_docs_without_changes_are_reindexed(Db) ->
     Sig = Mrst#mrst.sig,
     fabric2_fdb:transactional(Db, fun(TxDb) ->
         ?assertMatch(
-                [{0, 1, _, [0]}, {1, 0, 0, []}],
+                [{0, 1, _, [0]}],
                 couch_views_fdb:get_view_keys(TxDb, Sig, <<"0">>)
             )
     end).


[couchdb] 01/04: Refactor view index layout

Posted by da...@apache.org.
This is an automated email from the ASF dual-hosted git repository.

davisp pushed a commit to branch prototype/fdb-layer-couch-views-size-tests
in repository https://gitbox.apache.org/repos/asf/couchdb.git

commit 49aec4bb3ef72cca06b91ead6343cb2ed2f4c959
Author: Paul J. Davis <pa...@gmail.com>
AuthorDate: Mon Mar 2 13:39:00 2020 -0600

    Refactor view index layout
    
    This moves index meta information to its own key space so that we can
    scan all existing indexes efficiently.
---
 src/couch_views/include/couch_views.hrl | 16 ++++++++++------
 src/couch_views/src/couch_views_fdb.erl | 23 +++++++++++++++--------
 2 files changed, 25 insertions(+), 14 deletions(-)

diff --git a/src/couch_views/include/couch_views.hrl b/src/couch_views/include/couch_views.hrl
index 642431d..c40bb02 100644
--- a/src/couch_views/include/couch_views.hrl
+++ b/src/couch_views/include/couch_views.hrl
@@ -10,14 +10,18 @@
 % License for the specific language governing permissions and limitations under
 % the License.
 
-% indexing
+% Index info/data subspaces
+-define(VIEW_INFO, 0).
+-define(VIEW_DATA, 1).
+
+% Index info keys
 -define(VIEW_UPDATE_SEQ, 0).
--define(VIEW_ID_INFO, 1).
--define(VIEW_ID_RANGE, 2).
--define(VIEW_MAP_RANGE, 3).
+-define(VIEW_ROW_COUNT, 1).
+-define(VIEW_KV_SIZE, 2).
 
--define(VIEW_ROW_COUNT, 0).
--define(VIEW_KV_SIZE, 1).
+% Data keys
+-define(VIEW_ID_RANGE, 0).
+-define(VIEW_MAP_RANGE, 1).
 
 % jobs api
 -define(INDEX_JOB_TYPE, <<"views">>).
diff --git a/src/couch_views/src/couch_views_fdb.erl b/src/couch_views/src/couch_views_fdb.erl
index f68dafc..f2ac01b 100644
--- a/src/couch_views/src/couch_views_fdb.erl
+++ b/src/couch_views/src/couch_views_fdb.erl
@@ -249,7 +249,7 @@ get_view_keys(TxDb, Sig, DocId) ->
     } = TxDb,
     {Start, End} = id_idx_range(DbPrefix, Sig, DocId),
     lists:map(fun({K, V}) ->
-        {?DB_VIEWS, Sig, ?VIEW_ID_RANGE, DocId, ViewId} =
+        {?DB_VIEWS, ?VIEW_DATA, Sig, ?VIEW_ID_RANGE, DocId, ViewId} =
                 erlfdb_tuple:unpack(K, DbPrefix),
         [TotalKeys, TotalSize, UniqueKeys] = couch_views_encoding:decode(V),
         {ViewId, TotalKeys, TotalSize, UniqueKeys}
@@ -283,17 +283,17 @@ update_kv_size(TxDb, Sig, ViewId, Increment) ->
 
 
 seq_key(DbPrefix, Sig) ->
-    Key = {?DB_VIEWS, Sig, ?VIEW_UPDATE_SEQ},
+    Key = {?DB_VIEWS, ?VIEW_INFO, ?VIEW_UPDATE_SEQ, Sig},
     erlfdb_tuple:pack(Key, DbPrefix).
 
 
 row_count_key(DbPrefix, Sig, ViewId) ->
-    Key = {?DB_VIEWS, Sig, ?VIEW_ID_INFO, ViewId, ?VIEW_ROW_COUNT},
+    Key = {?DB_VIEWS, ?VIEW_INFO, ?VIEW_ROW_COUNT, Sig, ViewId},
     erlfdb_tuple:pack(Key, DbPrefix).
 
 
 kv_size_key(DbPrefix, Sig, ViewId) ->
-    Key = {?DB_VIEWS, Sig, ?VIEW_ID_INFO, ViewId, ?VIEW_KV_SIZE},
+    Key = {?DB_VIEWS, ?VIEW_INFO, ?VIEW_KV_SIZE, Sig, ViewId},
     erlfdb_tuple:pack(Key, DbPrefix).
 
 
@@ -303,17 +303,17 @@ db_kv_size_key(DbPrefix) ->
 
 
 id_idx_key(DbPrefix, Sig, DocId, ViewId) ->
-    Key = {?DB_VIEWS, Sig, ?VIEW_ID_RANGE, DocId, ViewId},
+    Key = {?DB_VIEWS, ?VIEW_DATA, Sig, ?VIEW_ID_RANGE, DocId, ViewId},
     erlfdb_tuple:pack(Key, DbPrefix).
 
 
 id_idx_range(DbPrefix, Sig, DocId) ->
-    Key = {?DB_VIEWS, Sig, ?VIEW_ID_RANGE, DocId},
+    Key = {?DB_VIEWS, ?VIEW_DATA, Sig, ?VIEW_ID_RANGE, DocId},
     erlfdb_tuple:range(Key, DbPrefix).
 
 
 map_idx_prefix(DbPrefix, Sig, ViewId) ->
-    Key = {?DB_VIEWS, Sig, ?VIEW_MAP_RANGE, ViewId},
+    Key = {?DB_VIEWS, ?VIEW_DATA, Sig, ?VIEW_MAP_RANGE, ViewId},
     erlfdb_tuple:pack(Key, DbPrefix).
 
 
@@ -324,7 +324,14 @@ map_idx_key(MapIdxPrefix, MapKey, DupeId) ->
 
 map_idx_range(DbPrefix, Sig, ViewId, MapKey, DocId) ->
     Encoded = couch_views_encoding:encode(MapKey, key),
-    Key = {?DB_VIEWS, Sig, ?VIEW_MAP_RANGE, ViewId, {Encoded, DocId}},
+    Key = {
+        ?DB_VIEWS,
+        ?VIEW_DATA,
+        Sig,
+        ?VIEW_MAP_RANGE,
+        ViewId,
+        {Encoded, DocId}
+    },
     erlfdb_tuple:range(Key, DbPrefix).
 
 


[couchdb] 04/04: Test size calculations for view rows

Posted by da...@apache.org.
This is an automated email from the ASF dual-hosted git repository.

davisp pushed a commit to branch prototype/fdb-layer-couch-views-size-tests
in repository https://gitbox.apache.org/repos/asf/couchdb.git

commit 3baaef6c9dcaa7a2a0f437d9c48e3e94cc824cc4
Author: Paul J. Davis <pa...@gmail.com>
AuthorDate: Mon Mar 2 16:53:18 2020 -0600

    Test size calculations for view rows
    
    These tests exercise that logic when updating rows in a map index. It
    works by generating two states and a transition between those states.
    That is, the set of rows that exist in the index, and the set of rows
    that exist after an update along with how many rows should be kept in
    common.
    
    This is a fairly exhaustive search of the state space in these
    transitions. A full run takes approximately 60s on my laptop so I have
    limited the set of tests to a random selection of 100 single and multi
    transition tests (i.e., updating either one or five documents in a
    single view build iteration).
---
 src/couch_views/src/couch_views_indexer.erl    |   5 +
 src/couch_views/test/couch_views_size_test.erl | 564 +++++++++++++++++++++++++
 2 files changed, 569 insertions(+)

diff --git a/src/couch_views/src/couch_views_indexer.erl b/src/couch_views/src/couch_views_indexer.erl
index 83f7e28..fb732a6 100644
--- a/src/couch_views/src/couch_views_indexer.erl
+++ b/src/couch_views/src/couch_views_indexer.erl
@@ -21,6 +21,11 @@
     init/0
 ]).
 
+-ifdef(TEST).
+-compile(export_all).
+-compile(nowarn_export_all).
+-endif.
+
 -include("couch_views.hrl").
 -include_lib("couch/include/couch_db.hrl").
 -include_lib("couch_mrview/include/couch_mrview.hrl").
diff --git a/src/couch_views/test/couch_views_size_test.erl b/src/couch_views/test/couch_views_size_test.erl
new file mode 100644
index 0000000..2d85cdf
--- /dev/null
+++ b/src/couch_views/test/couch_views_size_test.erl
@@ -0,0 +1,564 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+%   http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+-module(couch_views_size_test).
+
+-include_lib("eunit/include/eunit.hrl").
+-include_lib("couch/include/couch_db.hrl").
+-include_lib("couch/include/couch_eunit.hrl").
+-include_lib("couch_mrview/include/couch_mrview.hrl").
+-include_lib("fabric/include/fabric2.hrl").
+-include_lib("couch_views/include/couch_views.hrl").
+
+% N.B., we should move to couch_ejson_size instead
+% of erlang:external_size
+%
+% to calculate view size:
+% total = 0
+% for (fdb_k, fdb_v) in VIEW_MAP_RANGE:
+%   {EncUserKey, EncUserval} = erlfdb_tuple:unpack(fdb_v),
+%   UserKey = couch_views_encoding:decode(EncUserKey),
+%   UserVal = couch_views_encoding:decode(EncUserVal),
+%   total += erlang:external_size(UserKey),
+%   total += erlang:external_size(UserVal)
+%
+% Our goal in checking the size calculations is that we cover
+% as much of the possible key mutation space as possible while
+% not relying on fuzzing out the edge cases. Conceptually we have
+% two sets of keys E and U. E is keys as currently exist in the
+% view, and U is the new set of keys corresponding to an update.
+%
+% Both sets E and U have the same possible set of state variables:
+%
+% 1. N unique keys, where 0 =< N =< infinity
+% 2. D keys with duplicates, where 0 =< D =< N,
+% 3. R repeats for each member of D, for 2 =< R =< infinity
+%
+% Given two sets S1 and S2, we then have a set of transition variables:
+%
+% 1. deltaN - shared unique keys, where 0 =< deltaN =< N
+% 2. deltaD - shared duplicates, where 0 =< deltaD =< N
+% 3. deltaR - shared repeats for each D, where 2 =< deltaR =< infinity
+%
+% To search our state transition space, we can create two functions to
+% first define our start and end states, and for each transition we have
+% a function that defines the shared overlap between states.
+%
+% Given a list of transitions are checks then become simple in that
+% we can iterate over each transition checking that our index is valid
+% after each one. Index validation will purely look at the existing
+% state of the index in fdb and validate correctness.
+
+-define(NUM_SINGLE_TESTS, 100).
+-define(NUM_MULTI_TESTS, 100).
+
+-define(N_DOMAIN, [0, 1, 2, 5]).
+-define(D_DOMAIN, [0, 1, 2, 5]).
+-define(R_DOMAIN, [2, 4]).
+
+-define(DELTA_N_DOMAIN, [0, 1, 2, 5]).
+-define(DELTA_D_DOMAIN, [0, 1, 2, 5]).
+-define(DELTA_R_DOMAIN, [1, 2, 4]).
+
+
+generate_sets() ->
+    permute(?N_DOMAIN, ?D_DOMAIN, ?R_DOMAIN, fun(N, D, R) ->
+        % We can't have more duplicates than total keys
+        case D > N of
+            true -> throw(skip);
+            false -> ok
+        end,
+
+        % Only include one of the repeat values
+        % for our zero sets
+        case D == 0 of
+            true when R == 2 -> ok;
+            true -> throw(skip);
+            false -> ok
+        end,
+
+        % Replace R with a sentinel value for sanity
+        % when there are no dupes to have repeats
+        ActualR = if D == 0 -> 0; true -> R end,
+
+        {N, D, ActualR}
+    end).
+
+
+generate_transitions() ->
+    Sets = generate_sets(),
+    %Pairs0 = [{Set1, Set2} || Set1 <- Sets, Set2 <- Sets],
+    %Pairs = lists:sublist(Pairs0, 3),
+    Pairs = [{Set1, Set2} || Set1 <- Sets, Set2 <- Sets],
+    lists:flatmap(fun({{N1, D1, _R1} = S1, {N2, D2, _R2} = S2}) ->
+        Filter = fun(DeltaN, DeltaD, DeltaR) ->
+            % Can't share more keys than the smaller of the
+            % two sets
+            case DeltaN > min(N1, N2) of
+                true -> throw(skip);
+                false -> ok
+            end,
+
+            % For DeltaD == 0, all combinations of DeltaD and
+            % DeltaR are equivalent tests
+            case DeltaN == 0 of
+                true when DeltaD == 0, DeltaR == 1 -> ok;
+                true -> throw(skip);
+                false -> ok
+            end,
+
+            % Can't share more dupes than exist in either set
+            % or the total number of shared keys
+            case DeltaD > min(D1, D2) orelse DeltaD > DeltaN of
+                true -> throw(skip);
+                false -> ok
+            end,
+
+            % For DeltaD == 0, all DeltaR correspond to the
+            % same test so only include one instance
+            case DeltaD == 0 of
+                true when DeltaR == 1 -> ok;
+                true -> throw(skip);
+                false -> ok
+            end,
+
+            % If we have more non-repeated keys in our
+            % transition than there's "room" for in the target
+            % set it isn't a valid test case.
+            TransitionNonRepeats = DeltaN - DeltaD,
+            TargetNonRepeats = N2 - D2,
+            case TransitionNonRepeats > TargetNonRepeats of
+                true -> throw(skip);
+                false -> ok
+            end,
+
+            {S1, S2, {DeltaN, DeltaD, DeltaR}}
+        end,
+        permute(?DELTA_N_DOMAIN, ?DELTA_D_DOMAIN, ?DELTA_R_DOMAIN, Filter)
+    end, Pairs).
+
+
+permute(NList, DList, RList, Filter) ->
+    % Technically we could call into Filter in each
+    % outer loops to conditionally skip inner loops.
+    % If someone comes along looking to speed up the
+    % fixture setup time, this would likely be an
+    % easy win.
+    lists:foldl(fun(N, NAcc) ->
+        lists:foldl(fun(D, DAcc) ->
+            lists:foldl(fun(R, RAcc) ->
+                try
+                    [Filter(N, D, R) | RAcc]
+                catch throw:skip ->
+                    RAcc
+                end
+            end, DAcc, RList)
+        end, NAcc, DList)
+    end, [], NList).
+
+
+row_transition_test_() ->
+    {
+        "Test view size tracking",
+        {
+            setup,
+            fun setup/0,
+            fun cleanup/1,
+            fun create_transition_tests/1
+        }
+    }.
+
+
+setup() ->
+    Ctx = test_util:start_couch([
+            fabric,
+            couch_jobs,
+            couch_js,
+            couch_views
+        ]),
+    {ok, Db} = fabric2_db:create(?tempdb(), [{user_ctx, ?ADMIN_USER}]),
+    {Ctx, Db}.
+
+
+cleanup({Ctx, Db}) ->
+    ok = fabric2_db:delete(fabric2_db:name(Db), []),
+    test_util:stop_couch(Ctx).
+
+
+create_transition_tests({_Ctx, Db}) ->
+    Transitions = generate_transitions(),
+    Single = lists:flatmap(fun(T) ->
+        Name = lists:flatten(io_lib:format("single ~s", [tname(T)])),
+        [{Name, fun() -> check_single_transition(Db, T) end}]
+    end, lists:sort(Transitions)),
+    Multi = lists:flatmap(fun(T) ->
+        Name = lists:flatten(io_lib:format("multi ~s", [tname(T)])),
+        [{Name, fun() -> check_multi_transition(Db, T) end}]
+    end, lists:sort(group(shuffle(Transitions)))),
+    subset(?NUM_SINGLE_TESTS, Single) ++ subset(?NUM_MULTI_TESTS, Multi).
+
+
+check_single_transition(Db, {Set1, Set2, Transition}) ->
+    clear_views(Db),
+    InitKVs = init_set(Set1, [a, b, c, d, e]),
+    CommonKVs = reduce_set(Transition, InitKVs),
+    FinalKVs = fill_set(Set2, CommonKVs, [v, w, x, y, z]),
+    {InitJSONKVs, Bindings} = unlabel(InitKVs, #{}),
+    {FinalJSONKVs, _} = unlabel(FinalKVs, Bindings),
+
+    Sig = couch_uuids:random(),
+    DocId = couch_uuids:random(),
+
+    fabric2_fdb:transactional(Db, fun(TxDb) ->
+        write_docs(TxDb, Sig, [make_doc(DocId, InitJSONKVs)])
+    end),
+
+    fabric2_fdb:transactional(Db, fun(TxDb) ->
+        write_docs(TxDb, Sig, [make_doc(DocId, FinalJSONKVs)])
+    end),
+
+    validate_index(Db, Sig, #{DocId => FinalJSONKVs}).
+
+
+check_multi_transition(Db, Transitions) ->
+    clear_views(Db),
+
+    {Docs, IdMap} = lists:mapfoldl(fun({Set1, Set2, Transition}, IdMapAcc) ->
+        DocId = couch_uuids:random(),
+        InitKVs = init_set(Set1, [a, b, c, d, e]),
+        CommonKVs = reduce_set(Transition, InitKVs),
+        FinalKVs = fill_set(Set2, CommonKVs, [v, w, x, y, z]),
+        {InitJSONKVs, Bindings} = unlabel(InitKVs, #{}),
+        {FinalJSONKVs, _} = unlabel(FinalKVs, Bindings),
+        InitDoc = make_doc(DocId, InitJSONKVs),
+        FinalDoc = make_doc(DocId, FinalJSONKVs),
+        {{InitDoc, FinalDoc}, maps:put(DocId, FinalJSONKVs, IdMapAcc)}
+    end, #{}, Transitions),
+
+    {InitDocs, FinalDocs} = lists:unzip(Docs),
+
+    Sig = couch_uuids:random(),
+
+    fabric2_fdb:transactional(Db, fun(TxDb) ->
+        write_docs(TxDb, Sig, InitDocs)
+    end),
+
+    fabric2_fdb:transactional(Db, fun(TxDb) ->
+        write_docs(TxDb, Sig, FinalDocs)
+    end),
+
+    validate_index(Db, Sig, IdMap).
+
+
+clear_views(Db) ->
+    fabric2_fdb:transactional(Db, fun(TxDb) ->
+        #{
+            tx := Tx,
+            db_prefix := DbPrefix
+        } = TxDb,
+        {Start, End} = erlfdb_tuple:range({?DB_VIEWS}, DbPrefix),
+        erlfdb:clear_range(Tx, Start, End),
+
+        GlobalKey = {?DB_STATS, <<"sizes">>, <<"views">>},
+        BinGlobalKey = erlfdb_tuple:pack(GlobalKey, DbPrefix),
+        erlfdb:set(Tx, BinGlobalKey, ?uint2bin(0))
+    end).
+
+
+write_docs(TxDb, Sig, Docs) ->
+    Mrst = #mrst{
+        sig = Sig,
+        views = [#mrview{
+            id_num = 1
+        }]
+    },
+    IdxState = #{
+        last_seq => <<"foo">>
+    },
+    couch_views_indexer:write_docs(TxDb, Mrst, Docs, IdxState).
+
+
+validate_index(Db, Sig, JSONRows) ->
+    #{
+        db_prefix := DbPrefix
+    } = Db,
+    Rows = fabric2_fdb:transactional(Db, fun(TxDb) ->
+        #{
+            tx := Tx
+        } = TxDb,
+        {Start, End} = erlfdb_tuple:range({?DB_VIEWS}, DbPrefix),
+        erlfdb:get_range(Tx, Start, End)
+    end),
+
+    InitAcc = #{
+        row_count => 0,
+        kv_size => 0,
+        ids => #{},
+        rows => []
+    },
+
+    MapData = lists:foldl(fun({Key, Value}, Acc) ->
+        case erlfdb_tuple:unpack(Key, DbPrefix) of
+            {?DB_VIEWS, ?VIEW_INFO, ?VIEW_UPDATE_SEQ, Sig} ->
+                ?assertEqual(<<"foo">>, Value),
+                Acc;
+            {?DB_VIEWS, ?VIEW_INFO, ?VIEW_ROW_COUNT, Sig, 1} ->
+                maps:put(row_count, ?bin2uint(Value), Acc);
+            {?DB_VIEWS, ?VIEW_INFO, ?VIEW_KV_SIZE, Sig, 1} ->
+                maps:put(kv_size, ?bin2uint(Value), Acc);
+            {?DB_VIEWS, ?VIEW_DATA, Sig, ?VIEW_ID_RANGE, DocId, 1} ->
+                [
+                    TotalKeys, TotalSize, UniqueKeys
+                ] = couch_views_encoding:decode(Value),
+                maps:update_with(ids, fun(Ids) ->
+                    false = maps:is_key(DocId, Ids),
+                    maps:put(DocId, {TotalKeys, TotalSize, UniqueKeys}, Ids)
+                end, Acc);
+            {?DB_VIEWS, ?VIEW_DATA, Sig, ?VIEW_MAP_RANGE, 1, MapKey, _DupeId} ->
+                {EncKey, DocId} = MapKey,
+                {UserKey, UserVal} = erlfdb_tuple:unpack(Value),
+
+                UserJsonKey = couch_views_encoding:decode(UserKey),
+                UserJsonVal = couch_views_encoding:decode(UserVal),
+
+                % Assert our encoded sort key is correct
+                EncKey = couch_views_encoding:encode(UserJsonKey, key),
+
+                maps:update_with(rows, fun(RAcc) ->
+                    [{DocId, UserJsonKey, UserJsonVal} | RAcc]
+                end, Acc)
+        end
+    end, InitAcc, Rows),
+
+    #{
+        row_count := RowCount,
+        kv_size := KVSize,
+        ids := MapIds,
+        rows := MapRows
+    } = MapData,
+
+    SumFun = fun(_DocId, {TotalKVs, TotalSize, _UniqueKeys}, {KVAcc, SAcc}) ->
+        {KVAcc + TotalKVs, SAcc + TotalSize}
+    end,
+    {SumKVCount, SumKVSize} = maps:fold(SumFun, {0, 0}, MapIds),
+    ?assertEqual(RowCount, length(MapRows)),
+    ?assertEqual(RowCount, SumKVCount),
+    ?assertEqual(KVSize, SumKVSize),
+    ?assert(KVSize >= 0),
+
+    fabric2_fdb:transactional(Db, fun(TxDb) ->
+        GlobalSize = get_global_size(TxDb),
+        ?assertEqual(KVSize, GlobalSize),
+
+        ViewSize = couch_views_fdb:get_kv_size(TxDb, #mrst{sig = Sig}, 1),
+        ?assertEqual(KVSize, ViewSize)
+    end),
+
+    % Compare our raw JSON rows to what was indexed
+    IdsFromJSONRows = maps:fold(fun(DocId, DocRows, IdAcc) ->
+        FinalAcc = lists:foldl(fun({JsonKey, JsonVal}, {CAcc, SAcc, UAcc}) ->
+            KeySize = erlang:external_size(JsonKey),
+            ValSize = erlang:external_size(JsonVal),
+            NewUnique = lists:usort([JsonKey | UAcc]),
+            {CAcc + 1, SAcc + KeySize + ValSize, NewUnique}
+        end, {0, 0, []}, DocRows),
+        if FinalAcc == {0, 0, []} -> IdAcc; true ->
+            maps:put(DocId, FinalAcc, IdAcc)
+        end
+    end, #{}, JSONRows),
+    ?assertEqual(MapIds, IdsFromJSONRows),
+
+    % Compare the found id entries to our row data
+    IdsFromMapRows = lists:foldl(fun({DocId, JsonKey, JsonVal}, Acc) ->
+        KeySize = erlang:external_size(JsonKey),
+        ValSize = erlang:external_size(JsonVal),
+        Default = {1, KeySize + ValSize, [JsonKey]},
+        maps:update_with(DocId, fun({TotalKVs, TotalSize, UniqueKeys}) ->
+            NewUnique = lists:usort([JsonKey | UniqueKeys]),
+            {TotalKVs + 1, TotalSize + KeySize + ValSize, NewUnique}
+        end, Default, Acc)
+    end, #{}, MapRows),
+    ?assertEqual(MapIds, IdsFromMapRows).
+
+
+make_doc(DocId, []) ->
+    case rand:uniform() < 0.5 of
+        true ->
+            #{
+                id => DocId,
+                deleted => true,
+                results => [[]]
+            };
+        false ->
+            #{
+                id => DocId,
+                deleted => false,
+                results => [[]]
+            }
+    end;
+make_doc(DocId, Results) ->
+    #{
+        id => DocId,
+        deleted => false,
+        results => [Results]
+    }.
+
+
+get_global_size(TxDb) ->
+    #{
+        tx := Tx,
+        db_prefix := DbPrefix
+    } = TxDb,
+    GlobalKey = {?DB_STATS, <<"sizes">>, <<"views">>},
+    BinGlobalKey = erlfdb_tuple:pack(GlobalKey, DbPrefix),
+    ?bin2uint(erlfdb:wait(erlfdb:get(Tx, BinGlobalKey))).
+
+
+init_set({N, D, R}, Labels) ->
+    {Dupes, RestLabels} = fill_keys(D, Labels, []),
+    {Unique, _} = fill_keys(N - D, RestLabels, []),
+    % Sanity assertions
+    N = length(Unique) + length(Dupes),
+    D = length(Dupes),
+    {Unique, [{Key, R} || Key <- Dupes]}.
+
+
+reduce_set({DeltaN, DeltaD, DeltaR}, {Unique, Dupes}) ->
+    NewDupes = lists:sublist(Dupes, DeltaD),
+    NewUnique = lists:sublist(Unique, DeltaN - DeltaD),
+    {NewUnique, [{Key, DeltaR} || {Key, _} <- NewDupes]}.
+
+
+fill_set({N, D, R}, {Unique, Dupes}, Labels) ->
+    AddDupes = D - length(Dupes),
+    {NewDupes, RestLabels} = fill_keys(AddDupes, Labels, Dupes),
+
+    AddUnique = N - length(Unique) - length(NewDupes),
+    {NewUnique, _} = fill_keys(AddUnique, RestLabels, Unique),
+    % Sanity assertions
+    N = length(NewUnique) + length(NewDupes),
+    D = length(NewDupes),
+    {NewUnique, lists:map(fun(Dupe) ->
+        case Dupe of
+            {_, _} -> Dupe;
+            A when is_atom(A) -> {A, R}
+        end
+    end, NewDupes)}.
+
+
+fill_keys(0, Labels, Acc) ->
+    {Acc, Labels};
+fill_keys(Count, [Label | RestLabels], Acc) when Count > 0 ->
+    fill_keys(Count - 1, RestLabels, [Label | Acc]).
+
+
+unlabel({Unique, Dupes}, Bindings) ->
+    lists:foldl(fun(Item, {KVAcc, BindingsAcc}) ->
+        {KVs, NewBindingsAcc} = unlabel_item(Item, BindingsAcc),
+        {KVs ++ KVAcc, NewBindingsAcc}
+    end, {[], Bindings}, Unique ++ Dupes).
+
+
+unlabel_item(Label, Bindings) when is_atom(Label) ->
+    NewBindings = maybe_bind(Label, Bindings),
+    KV = maps:get(Label, NewBindings),
+    {[KV], NewBindings};
+unlabel_item({Label, Count}, Bindings) when is_atom(Label), is_integer(Count) ->
+    NewBindings = maybe_bind(Label, Bindings),
+    {K, _} = KV = maps:get(Label, NewBindings),
+    ToAdd = lists:map(fun(_) ->
+        {K, gen_value()}
+    end,  lists:seq(1, Count - 1)),
+    {[KV | ToAdd], NewBindings}.
+
+
+maybe_bind(Label, Bindings) ->
+    case maps:is_key(Label, Bindings) of
+        true ->
+            case rand:uniform() < 0.5 of
+                true ->
+                    rebind(Label, Bindings);
+                false ->
+                    Bindings
+            end;
+        false ->
+            bind(Label, Bindings)
+    end.
+
+
+bind(Label, Bindings) ->
+    maps:put(Label, {gen_key(), gen_value()}, Bindings).
+
+
+rebind(Label, Bindings) ->
+    {Key, _} = maps:get(Label, Bindings),
+    maps:put(Label, {Key, gen_value()}, Bindings).
+
+
+gen_key() ->
+    Unique = couch_uuids:random(),
+    case rand:uniform() of
+        N when N < 0.2 ->
+            [Unique, true, rand:uniform()];
+        N when N < 0.4 ->
+            {[{Unique, true}, {<<"foo">>, [<<"bar">>, null, 1, {[]}]}]};
+        _ ->
+            Unique
+    end.
+
+
+gen_value() ->
+    case rand:uniform() of
+        N when N < 0.2 ->
+            [false, rand:uniform(), {[]}];
+        N when N < 0.4 ->
+            {[{<<"a">>, 1}, {<<"b">>, 2}]};
+        N when N < 0.6 ->
+            rand:uniform(100);
+        N when N < 0.8 ->
+            rand:uniform();
+        _ ->
+            1
+    end.
+
+
+group(Items) ->
+    case length(Items) > 5 of
+        true ->
+            {Group, Rest} = lists:split(5, Items),
+            [lists:sort(Group) | group(Rest)];
+        false when Items == [] ->
+            [];
+        false ->
+            [lists:sort(Items)]
+    end.
+
+
+shuffle(Items) ->
+    Tagged = [{rand:uniform(), I} || I <- Items],
+    Sorted = lists:sort(Tagged),
+    [I || {_T, I} <- Sorted].
+
+
+subset(Count, Items) ->
+    Random = shuffle(Items),
+    Take = lists:sublist(Random, Count),
+    lists:sort(Take).
+
+
+tname([]) ->
+    [];
+tname([Transition | RestTransitions]) ->
+    [tname(Transition) | tname(RestTransitions)];
+tname({{N1, D1, R1}, {N2, D2, R2}, {DN, DD, DR}}) ->
+    io_lib:format("~b~b~b~b~b~b~b~b~b", [N1, D1, R1, N2, D2, R2, DN, DD, DR]).
+


[couchdb] 02/04: Fix handling of duplicate keys

Posted by da...@apache.org.
This is an automated email from the ASF dual-hosted git repository.

davisp pushed a commit to branch prototype/fdb-layer-couch-views-size-tests
in repository https://gitbox.apache.org/repos/asf/couchdb.git

commit 20e5e443062b961d30233daffc42767c575cf64c
Author: Paul J. Davis <pa...@gmail.com>
AuthorDate: Wed Mar 4 09:54:53 2020 -0600

    Fix handling of duplicate keys
    
    If a map function emits duplicate keys for a document this stores
    multiple rows in the map index differentiated by a `DupeId` counter.
    Previously we were attempting to save some work avoiding clearing ranges
    for keys that would be overwritten. However, if a document update causes
    fewer duplicates to be emitted for the same key we left orphaned rows in
    the index.
---
 src/couch_views/src/couch_views_fdb.erl           |  5 +-
 src/couch_views/test/couch_views_indexer_test.erl | 76 +++++++++++++++++++++++
 2 files changed, 77 insertions(+), 4 deletions(-)

diff --git a/src/couch_views/src/couch_views_fdb.erl b/src/couch_views/src/couch_views_fdb.erl
index f2ac01b..98257f3 100644
--- a/src/couch_views/src/couch_views_fdb.erl
+++ b/src/couch_views/src/couch_views_fdb.erl
@@ -224,13 +224,10 @@ update_map_idx(TxDb, Sig, ViewId, DocId, ExistingKeys, NewRows) ->
         db_prefix := DbPrefix
     } = TxDb,
 
-    Unique = lists:usort([K || {K, _V} <- NewRows]),
-
-    KeysToRem = ExistingKeys -- Unique,
     lists:foreach(fun(RemKey) ->
         {Start, End} = map_idx_range(DbPrefix, Sig, ViewId, RemKey, DocId),
         ok = erlfdb:clear_range(Tx, Start, End)
-    end, KeysToRem),
+    end, ExistingKeys),
 
     KVsToAdd = process_rows(NewRows),
     MapIdxPrefix = map_idx_prefix(DbPrefix, Sig, ViewId),
diff --git a/src/couch_views/test/couch_views_indexer_test.erl b/src/couch_views/test/couch_views_indexer_test.erl
index 9482fdd..9b12af6 100644
--- a/src/couch_views/test/couch_views_indexer_test.erl
+++ b/src/couch_views/test/couch_views_indexer_test.erl
@@ -39,6 +39,7 @@ indexer_test_() ->
                     ?TDEF_FE(multipe_docs_with_same_key),
                     ?TDEF_FE(multipe_keys_from_same_doc),
                     ?TDEF_FE(multipe_identical_keys_from_same_doc),
+                    ?TDEF_FE(fewer_multipe_identical_keys_from_same_doc),
                     ?TDEF_FE(handle_size_key_limits),
                     ?TDEF_FE(handle_size_value_limits)
                 ]
@@ -388,6 +389,77 @@ multipe_identical_keys_from_same_doc(Db) ->
         ], Out).
 
 
+fewer_multipe_identical_keys_from_same_doc(Db) ->
+    DDoc = create_ddoc(multi_emit_same),
+
+    Doc0 = couch_doc:from_json_obj({[
+        {<<"_id">>, list_to_binary(integer_to_list(0))},
+        {<<"val">>, 1},
+        {<<"extra">>, 3}
+    ]}),
+
+    {ok, _} = fabric2_db:update_doc(Db, DDoc, []),
+    {ok, {Pos, Rev}} = fabric2_db:update_doc(Db, Doc0, []),
+
+    {ok, Out1} = couch_views:query(
+            Db,
+            DDoc,
+            <<"map_fun1">>,
+            fun fold_fun/2,
+            [],
+            #mrargs{}
+        ),
+
+    ?assertEqual([
+            {row, [
+                {id, <<"0">>},
+                {key, 1},
+                {value, 1}
+            ]},
+            {row, [
+                {id, <<"0">>},
+                {key, 1},
+                {value, 2}
+            ]},
+            {row, [
+                {id, <<"0">>},
+                {key, 1},
+                {value, 3}
+            ]}
+        ], Out1),
+
+    Doc1 = couch_doc:from_json_obj({[
+        {<<"_id">>, list_to_binary(integer_to_list(0))},
+        {<<"val">>, 1}
+    ]}),
+    Doc2 = Doc1#doc{
+        revs = {Pos, [Rev]}
+    },
+    {ok, _} = fabric2_db:update_doc(Db, Doc2, []),
+
+    {ok, Out2} = couch_views:query(
+            Db,
+            DDoc,
+            <<"map_fun1">>,
+            fun fold_fun/2,
+            [],
+            #mrargs{}
+        ),
+
+    ?assertEqual([
+            {row, [
+                {id, <<"0">>},
+                {key, 1},
+                {value, 1}
+            ]},
+            {row, [
+                {id, <<"0">>},
+                {key, 1},
+                {value, 2}
+            ]}
+        ], Out2).
+
+
 handle_size_key_limits(Db) ->
     ok = meck:new(config, [passthrough]),
     ok = meck:expect(config, get_integer, fun(Section, Key, Default) ->
@@ -495,6 +567,7 @@ row(Id, Key, Value) ->
         {value, Value}
     ]}.
 
+
 fold_fun({meta, _Meta}, Acc) ->
     {ok, Acc};
 fold_fun({row, _} = Row, Acc) ->
@@ -544,6 +617,9 @@ create_ddoc(multi_emit_same) ->
                 {<<"map">>, <<"function(doc) { "
                     "emit(doc.val, doc.val * 2); "
                     "emit(doc.val, doc.val); "
+                    "if(doc.extra) {"
+                    "  emit(doc.val, doc.extra);"
+                    "}"
                 "}">>}
             ]}},
             {<<"map_fun2">>, {[