choice of uuid algos for better insert perf. Closes COUCHDB-465. Thanks rnewson, bitdiddle

git-svn-id: https://svn.apache.org/repos/asf/couchdb/trunk@813051 13f79535-47bb-0310-9956-ffa450edef68

6 files changed, 127 insertions, 9 deletions

diff --git a/test/etap/040-util.t b/test/etap/040-util.t
index c23dc97f..35fae20d 100755
--- a/test/etap/040-util.t
+++ b/test/etap/040-util.t
@@ -17,7 +17,7 @@ main(_) ->
     code:add_pathz("src/couchdb"),
     application:start(crypto),
 
-    etap:plan(11),
+    etap:plan(10),
     case (catch test()) of
         ok ->
             etap:end_tests();
@@ -47,10 +47,6 @@ test() ->
             etap:ok(not is_process_alive(Pid), "why wont this work?")
     end,
 
-    % new_uuid
-    etap:isnt(couch_util:new_uuid(), couch_util:new_uuid(),
-        "A guid ought to be unique."),
-
     % implode
     etap:is([1, 38, 2, 38, 3], couch_util:implode([1,2,3],"&"),
         "use & as separator in list."),
diff --git a/test/etap/041-uuid-gen-seq.ini b/test/etap/041-uuid-gen-seq.ini
new file mode 100644
index 00000000..005048cc
--- /dev/null
+++ b/test/etap/041-uuid-gen-seq.ini
@@ -0,0 +1,2 @@
+[uuids]
+algorithm = sequential
diff --git a/test/etap/041-uuid-gen-utc.ini b/test/etap/041-uuid-gen-utc.ini
new file mode 100644
index 00000000..2d1ce1b1
--- /dev/null
+++ b/test/etap/041-uuid-gen-utc.ini
@@ -0,0 +1,2 @@
+[uuids]
+algorithm = utc_random
diff --git a/test/etap/041-uuid-gen.t b/test/etap/041-uuid-gen.t
new file mode 100644
index 00000000..45cc7f59
--- /dev/null
+++ b/test/etap/041-uuid-gen.t
@@ -0,0 +1,118 @@
+#!/usr/bin/env escript
+%% -*- erlang -*-
+
+% 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.
+
+default_config() ->
+    "etc/couchdb/default_dev.ini".
+
+seq_alg_config() ->
+    "test/etap/041-uuid-gen-seq.ini".
+
+utc_alg_config() ->
+    "test/etap/041-uuid-gen-utc.ini".
+
+% Run tests and wait for the gen_servers to shutdown
+run_test(IniFiles, Test) ->
+    {ok, Pid} = couch_config:start_link(IniFiles),
+    erlang:monitor(process, Pid),
+    couch_uuids:start(),
+    Test(),
+    couch_uuids:stop(),
+    couch_config:stop(),
+    receive
+        {'DOWN', _, _, Pid, _} -> ok;
+        _Other -> etap:diag("OTHER: ~p~n", [_Other])
+    after
+        1000 -> throw({timeout_error, config_stop})
+    end.
+
+main(_) ->
+    code:add_pathz("src/couchdb"),
+    application:start(crypto),
+    etap:plan(unknown),
+
+    case (catch test()) of
+        ok ->
+            etap:end_tests();
+        Other ->
+            etap:diag(io_lib:format("Test died abnormally: ~p", [Other])),
+            etap:bail(Other)
+    end,
+    ok.
+
+test() ->
+
+    TestUnique = fun() ->
+        etap:is(
+            test_unique(10000, couch_uuids:new()),
+            true,
+            "Can generate 10K unique IDs"
+        )
+    end,
+    run_test([default_config()], TestUnique),
+    run_test([default_config(), seq_alg_config()], TestUnique),
+    run_test([default_config(), utc_alg_config()], TestUnique),
+
+    TestMonotonic = fun () ->
+        etap:is(
+            couch_uuids:new() < couch_uuids:new(),
+            true,
+            "should produce monotonically increasing ids"
+        )
+    end,
+    run_test([default_config(), seq_alg_config()], TestMonotonic),
+    run_test([default_config(), utc_alg_config()], TestMonotonic),
+
+    % Pretty sure that the average of a uniform distribution is the
+    % midpoint of the range. Thus, to exceed a threshold, we need
+    % approximately Total / (Range/2 + RangeMin) samples.
+    %
+    % In our case this works out to be 8194. (0xFFF000 / 0x7FF)
+    % These tests just fudge the limits for a good generator at 25%
+    % in either direction. Technically it should be possible to generate
+    % bounds that will show if your random number generator is not
+    % sufficiently random but I hated statistics in school.
+    TestRollOver = fun() ->
+        UUID = binary_to_list(couch_uuids:new()),
+        Prefix = element(1, lists:split(26, UUID)),
+        N = gen_until_pref_change(Prefix,0),
+        etap:diag("N is: ~p~n",[N]),                           
+        etap:is(
+            N >= 5000 andalso N =< 11000,
+            true,
+            "should roll over every so often."
+        )
+    end,
+    run_test([default_config(), seq_alg_config()], TestRollOver).
+
+test_unique(0, _) ->
+    true;
+test_unique(N, UUID) ->
+    case couch_uuids:new() of
+        UUID ->
+            etap:diag("N: ~p~n", [N]),
+            false;
+        Else -> test_unique(N-1, Else)
+    end.
+
+get_prefix(UUID) ->
+    element(1, lists:split(26, binary_to_list(UUID))).
+
+gen_until_pref_change(_, Count) when Count > 8251 ->
+    Count;
+gen_until_pref_change(Prefix, N) ->
+    case get_prefix(couch_uuids:new()) of
+        Prefix -> gen_until_pref_change(Prefix, N+1);
+        _ -> N
+    end.
diff --git a/test/etap/111-replication-changes-feed.t b/test/etap/111-replication-changes-feed.t
index dcbd500e..4045a28d 100755
--- a/test/etap/111-replication-changes-feed.t
+++ b/test/etap/111-replication-changes-feed.t
@@ -195,7 +195,7 @@ get_all_changes(Pid, Acc) ->
     end.
 
 generate_change() ->
-    generate_change(couch_util:new_uuid()).
+    generate_change(couch_uuids:random()).
 
 generate_change(Id) ->
     generate_change(Id, {[]}).
@@ -212,7 +212,7 @@ generate_change(Id, EJson) ->
     ]}.
 
 generate_conflict() ->
-    Id = couch_util:new_uuid(),
+    Id = couch_uuids:random(),
     Db = get_db(),
     Doc1 = (couch_doc:from_json_obj({[<<"foo">>, <<"bar">>]}))#doc{id = Id},
     Doc2 = (couch_doc:from_json_obj({[<<"foo">>, <<"baz">>]}))#doc{id = Id},
diff --git a/test/etap/112-replication-missing-revs.t b/test/etap/112-replication-missing-revs.t
index 07b9a8de..e42c185e 100755
--- a/test/etap/112-replication-missing-revs.t
+++ b/test/etap/112-replication-missing-revs.t
@@ -112,7 +112,7 @@ test_multiple_changes(SrcType, TgtType) ->
 
 test_changes_not_missing(SrcType, TgtType) ->
     %% put identical changes on source and target
-    Id = couch_util:new_uuid(),
+    Id = couch_uuids:random(),
     {Id, _Seq, [Rev]} = Expect = generate_change(Id, {[]}, get_db(source)),
     {Id, _, [Rev]} = generate_change(Id, {[]}, get_db(target)),
 
@@ -131,7 +131,7 @@ test_changes_not_missing(SrcType, TgtType) ->
     ).
 
 generate_change() ->
-    generate_change(couch_util:new_uuid()).
+    generate_change(couch_uuids:random()).
 
 generate_change(Id) ->
     generate_change(Id, {[]}).