Merge pull request #26 from basho/rdb-slides-squash
Add a sliding window sample types for histograms
diff --git a/include/folsom.hrl b/include/folsom.hrl
index 8b32fee..d0cc8ec 100644
--- a/include/folsom.hrl
+++ b/include/folsom.hrl
@@ -9,10 +9,26 @@
-define(DEFAULT_LIMIT, 5).
-define(DEFAULT_SIZE, 1028). % mimic codahale's metrics
+-define(DEFAULT_SLIDING_WINDOW, 60). % sixty second sliding window
-define(DEFAULT_ALPHA, 0.015). % mimic codahale's metrics
-define(DEFAULT_INTERVAL, 5000).
-define(DEFAULT_SAMPLE_TYPE, uniform).
+-record(slide, {
+ window = ?DEFAULT_SLIDING_WINDOW,
+ reservoir = folsom_metrics_histogram_ets:new(folsom_slide,
+ [duplicate_bag, {write_concurrency, true}, public]),
+ server
+ }).
+
+-record(slide_uniform, {
+ window = ?DEFAULT_SLIDING_WINDOW,
+ size = ?DEFAULT_SIZE,
+ reservoir = folsom_metrics_histogram_ets:new(folsom_slide_uniform,[ordered_set, {write_concurrency, true}, public]),
+ seed = now(),
+ server
+ }).
+
-record(uniform, {
size = ?DEFAULT_SIZE,
n = 1,
diff --git a/rebar.config b/rebar.config
index 1728cb5..479ba7b 100644
--- a/rebar.config
+++ b/rebar.config
@@ -1,7 +1,8 @@
{sub_dirs, ["deps"]}.
{deps, [
- {'bear', ".*", {git, "git://github.com/boundary/bear.git", "master"}}
+ {'bear', ".*", {git, "git://github.com/boundary/bear.git", "master"}},
+ {meck, ".*", {git, "git://github.com/eproxus/meck", "master"}}
]}.
{erl_opts, [debug_info]}.
diff --git a/src/folsom_ets.erl b/src/folsom_ets.erl
index a17e195..44fdd9b 100644
--- a/src/folsom_ets.erl
+++ b/src/folsom_ets.erl
@@ -266,6 +266,18 @@
delete_histogram(Name, #histogram{type = exdec}) ->
true = ets:delete(?HISTOGRAM_TABLE, Name),
true = ets:delete(?FOLSOM_TABLE, Name),
+ ok;
+delete_histogram(Name, #histogram{type = slide, sample = #slide{reservoir = Reservoir, server=Pid}}) ->
+ folsom_sample_slide_server:stop(Pid),
+ true = ets:delete(?HISTOGRAM_TABLE, Name),
+ true = ets:delete(?FOLSOM_TABLE, Name),
+ true = ets:delete(Reservoir),
+ ok;
+delete_histogram(Name, #histogram{type = slide_uniform, sample = #slide_uniform{reservoir = Reservoir, server=Pid}}) ->
+ folsom_sample_slide_server:stop(Pid),
+ true = ets:delete(?HISTOGRAM_TABLE, Name),
+ true = ets:delete(?FOLSOM_TABLE, Name),
+ true = ets:delete(Reservoir),
ok.
delete_history(Name, #history{tid = Tid}) ->
diff --git a/src/folsom_metrics_histogram.erl b/src/folsom_metrics_histogram.erl
index 8cd9117..401e29f 100644
--- a/src/folsom_metrics_histogram.erl
+++ b/src/folsom_metrics_histogram.erl
@@ -38,6 +38,10 @@
new(Name) ->
new(Name, uniform).
+new(Name, slide) ->
+ new(Name, slide, ?DEFAULT_SLIDING_WINDOW);
+new(Name, slide_uniform) ->
+ new(Name, slide_uniform, {?DEFAULT_SLIDING_WINDOW, ?DEFAULT_SIZE});
new(Name, SampleType) ->
new(Name, SampleType, ?DEFAULT_SIZE).
diff --git a/src/folsom_sample.erl b/src/folsom_sample.erl
index fe5a05f..f08d233 100644
--- a/src/folsom_sample.erl
+++ b/src/folsom_sample.erl
@@ -36,12 +36,20 @@
%% API
+new(slide) ->
+ new(slide, ?DEFAULT_SLIDING_WINDOW);
+new(slide_uniform) ->
+ new(slide_uniform, {?DEFAULT_SLIDING_WINDOW, ?DEFAULT_SIZE});
new(Type) ->
new(Type, ?DEFAULT_SIZE, ?DEFAULT_ALPHA).
new(Type, Size) ->
new(Type, Size, ?DEFAULT_ALPHA).
+new(slide, Size, _) ->
+ folsom_sample_slide:new(Size);
+new(slide_uniform, Sizes, _) ->
+ folsom_sample_slide_uniform:new(Sizes);
new(uniform, Size, _) ->
folsom_sample_uniform:new(Size);
new(none, Size, _) ->
@@ -54,11 +62,20 @@
update(none, Sample, Value) ->
folsom_sample_none:update(Sample, Value);
update(exdec, Sample, Value) ->
- folsom_sample_exdec:update(Sample, Value).
+ folsom_sample_exdec:update(Sample, Value);
+update(slide, Sample, Value) ->
+ folsom_sample_slide:update(Sample, Value);
+update(slide_uniform, Sample, Value) ->
+ folsom_sample_slide_uniform:update(Sample, Value).
+
get_values(uniform, Sample) ->
folsom_sample_uniform:get_values(Sample);
get_values(none, Sample) ->
folsom_sample_none:get_values(Sample);
get_values(exdec, Sample) ->
- folsom_sample_exdec:get_values(Sample).
+ folsom_sample_exdec:get_values(Sample);
+get_values(slide, Sample) ->
+ folsom_sample_slide:get_values(Sample);
+get_values(slide_uniform, Sample) ->
+ folsom_sample_slide_uniform:get_values(Sample).
diff --git a/src/folsom_sample_slide.erl b/src/folsom_sample_slide.erl
new file mode 100644
index 0000000..4b13a36
--- /dev/null
+++ b/src/folsom_sample_slide.erl
@@ -0,0 +1,55 @@
+%%%
+%%% Copyright 2012, Basho Technologies, Inc. All Rights Reserved.
+%%%
+%%% 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.
+%%%
+%%%-------------------------------------------------------------------
+%%% File: folsom_sample_slide.erl
+%%% @author Russell Brown <russelldb@basho.com>
+%%% @doc
+%%% Sliding window sample. Last Window seconds readings are recorded.
+%%% @end
+%%%-----------------------------------------------------------------
+
+-module(folsom_sample_slide).
+
+-export([
+ new/1,
+ update/2,
+ get_values/1,
+ moment/0,
+ trim/2
+ ]).
+
+-include("folsom.hrl").
+
+new(Size) ->
+ Sample = #slide{window = Size},
+ Pid = folsom_sample_slide_sup:start_slide_server(?MODULE, Sample#slide.reservoir, Sample#slide.window),
+ Sample#slide{server=Pid}.
+
+update(#slide{reservoir = Reservoir} = Sample, Value) ->
+ Moment = moment(),
+ ets:insert(Reservoir, {Moment, Value}),
+ Sample.
+
+get_values(#slide{window = Window, reservoir = Reservoir}) ->
+ Oldest = moment() - Window,
+ ets:select(Reservoir, [{{'$1','$2'},[{'>=', '$1', Oldest}],['$2']}]).
+
+moment() ->
+ folsom_utils:now_epoch().
+
+trim(Reservoir, Window) ->
+ Oldest = moment() - Window,
+ ets:select_delete(Reservoir, [{{'$1','_'},[{'<', '$1', Oldest}],['true']}]).
diff --git a/src/folsom_sample_slide_server.erl b/src/folsom_sample_slide_server.erl
new file mode 100644
index 0000000..5986918
--- /dev/null
+++ b/src/folsom_sample_slide_server.erl
@@ -0,0 +1,73 @@
+%% -------------------------------------------------------------------
+%%
+%% Copyright (c) 2011 Basho Technologies, Inc.
+%%
+%% This file is provided to you 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.
+%%
+%% -------------------------------------------------------------------
+%%%-------------------------------------------------------------------
+%%% File: folsom_sample_slide_server.erl
+%%% @author Russell Brown <russelldb@basho.com>
+%%% @doc
+%%% Serialization point for folsom_sample_slide. Handles
+%%% pruning of older smaples. One started per histogram.
+%%% See folsom.hrl, folsom_sample_slide, folsom_sample_slide_sup
+%%% @end
+%%%-----------------------------------------------------------------
+-module(folsom_sample_slide_server).
+
+-behaviour(gen_server).
+
+%% API
+-export([start_link/3, stop/1]).
+
+-record(state, {sample_mod, reservoir, window}).
+
+%% gen_server callbacks
+-export([init/1, handle_call/3, handle_cast/2, handle_info/2,
+ terminate/2, code_change/3]).
+
+start_link(SampleMod, Reservoir, Window) ->
+ gen_server:start_link(?MODULE, [SampleMod, Reservoir, Window], []).
+
+stop(Pid) ->
+ gen_server:cast(Pid, stop).
+
+init([SampleMod, Reservoir, Window]) ->
+ {ok, #state{sample_mod = SampleMod, reservoir = Reservoir, window = Window}, timeout(Window)}.
+
+handle_call(_Request, _From, State) ->
+ Reply = ok,
+ {reply, Reply, State}.
+
+handle_cast(stop, State) ->
+ {stop, normal, State};
+handle_cast(_Msg, State) ->
+ {noreply, State}.
+
+handle_info(timeout, State=#state{sample_mod = SampleMod, reservoir = Reservoir, window = Window}) ->
+ SampleMod:trim(Reservoir, Window),
+ {noreply, State, timeout(Window)};
+handle_info(_Info, State) ->
+ {noreply, State}.
+
+terminate(_Reason, _State) ->
+ ok.
+
+code_change(_OldVsn, State, _Extra) ->
+ {ok, State}.
+
+timeout(Window) ->
+ timer:seconds(Window) div 2.
diff --git a/src/folsom_sample_slide_sup.erl b/src/folsom_sample_slide_sup.erl
new file mode 100644
index 0000000..c8929d1
--- /dev/null
+++ b/src/folsom_sample_slide_sup.erl
@@ -0,0 +1,51 @@
+%% -------------------------------------------------------------------
+%%
+%% Copyright (c) 2011 Basho Technologies, Inc.
+%%
+%% This file is provided to you 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.
+%%
+%% -------------------------------------------------------------------
+%%%-------------------------------------------------------------------
+%%% File: folsom_sample_slide_sup.erl
+%%% @author Russell Brown <russelldb@basho.com>
+%%% @doc
+%%% Starts simple_one_for_one children per slide sample
+%%% @end
+%%%-----------------------------------------------------------------
+-module(folsom_sample_slide_sup).
+-behaviour(supervisor).
+
+%% beahvior functions
+-export([start_link/0,
+ init/1
+ ]).
+
+%% public functions
+-export([start_slide_server/3]).
+
+start_link () ->
+ supervisor:start_link({local,?MODULE},?MODULE,[]).
+
+start_slide_server(SampleMod, Reservoir, Window) ->
+ {ok, Pid} = supervisor:start_child(?MODULE, [SampleMod, Reservoir, Window]),
+ Pid.
+
+%% @private
+init ([]) ->
+ {ok,{{simple_one_for_one,10,10},
+ [
+ {undefined, {folsom_sample_slide_server, start_link, []},
+ transient, brutal_kill, worker, [folsom_sample_slide_server]}
+ ]}}.
diff --git a/src/folsom_sample_slide_uniform.erl b/src/folsom_sample_slide_uniform.erl
new file mode 100644
index 0000000..7e7b5eb
--- /dev/null
+++ b/src/folsom_sample_slide_uniform.erl
@@ -0,0 +1,72 @@
+%%%
+%%% Copyright 2012, Basho Technologies, Inc. All Rights Reserved.
+%%%
+%%% 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.
+%%%
+%%%-------------------------------------------------------------------
+%%% File: folsom_sample_slide.erl
+%%% @author Russell Brown <russelldb@basho.com>
+%%% @doc
+%%% Sliding window sample. Last Window seconds readings are recorded.
+%%% @end
+%%%-----------------------------------------------------------------
+
+-module(folsom_sample_slide_uniform).
+
+-export([
+ new/1,
+ update/2,
+ get_values/1,
+ moment/0,
+ trim/2
+ ]).
+
+-include("folsom.hrl").
+
+new({Window, SampleSize}) ->
+ Sample = #slide_uniform{window = Window, size = SampleSize},
+ Pid = folsom_sample_slide_sup:start_slide_server(?MODULE, Sample#slide_uniform.reservoir, Sample#slide_uniform.window),
+ Sample#slide_uniform{server=Pid}.
+
+update(#slide_uniform{reservoir = Reservoir, size = Size, seed = Seed} = Sample0, Value) ->
+ Moment = moment(),
+ ets:insert_new(Reservoir, {Moment, 0}),
+ MCnt = ets:update_counter(Reservoir, Moment, 1),
+ Sample = case MCnt > Size of
+ true ->
+ {Rnd, NewSeed} = random:uniform_s(Size, Seed),
+ maybe_update(Reservoir, {{Moment, Rnd}, Value}, Size),
+ Sample0#slide_uniform{seed = NewSeed};
+ false ->
+ ets:insert(Reservoir, {{Moment, MCnt}, Value}),
+ Sample0
+ end,
+ Sample.
+
+maybe_update(Reservoir, {{_Moment, Rnd}, _Value}=Obj, Size) when Rnd =< Size ->
+ ets:insert(Reservoir, Obj);
+maybe_update(_Reservoir, _Obj, _Size) ->
+ ok.
+
+get_values(#slide_uniform{window = Window, reservoir = Reservoir}) ->
+ Oldest = moment() - Window,
+ ets:select(Reservoir, [{{{'$1', '_'},'$2'},[{'>=', '$1', Oldest}],['$2']}]).
+
+moment() ->
+ folsom_utils:now_epoch().
+
+trim(Reservoir, Window) ->
+ Oldest = moment() - Window,
+ ets:select_delete(Reservoir, [{{{'$1', '_'},'_'},[{'<', '$1', Oldest}],['true']}]),
+ %% and trim the counters
+ ets:select_delete(Reservoir, [{{'$1','_'},[{is_integer, '$1'}, {'<', '$1', Oldest}],['true']}]).
diff --git a/src/folsom_sup.erl b/src/folsom_sup.erl
index 5d0da83..3d30704 100644
--- a/src/folsom_sup.erl
+++ b/src/folsom_sup.erl
@@ -89,7 +89,10 @@
{folsom_metrics_histogram_ets, start_link, []},
Restart, Shutdown, Type, [folsom_metrics_histogram_ets]},
- {ok, {SupFlags, [TimerServer, HistETSServer]}}.
+ SlideSup = {folsom_sample_slide_sup, {folsom_sample_slide_sup, start_link, []},
+ permanent, 5000, supervisor, [folsom_sample_slide_sup]},
+
+ {ok, {SupFlags, [SlideSup, TimerServer, HistETSServer]}}.
%%%===================================================================
%%% Internal functions
diff --git a/src/folsom_utils.erl b/src/folsom_utils.erl
index 0faa9a8..d6192cd 100644
--- a/src/folsom_utils.erl
+++ b/src/folsom_utils.erl
@@ -50,4 +50,3 @@
get_ets_size(Tab) ->
ets:info(Tab, size).
-
diff --git a/test/folsom_sample_slide_test.erl b/test/folsom_sample_slide_test.erl
new file mode 100644
index 0000000..b1a0fd5
--- /dev/null
+++ b/test/folsom_sample_slide_test.erl
@@ -0,0 +1,105 @@
+%%%
+%%% Copyright 2012 - Basho Technologies, Inc. All Rights Reserved.
+%%%
+%%% 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.
+%%%
+
+%%%-------------------------------------------------------------------
+%%% File: folsom_sample_slide.erl
+%%% @author Russell Brown <russelldb@basho.com>
+%%% @doc eunit test for folsom_sample_slide.erl
+%%% @end
+%%%------------------------------------------------------------------
+
+-module(folsom_sample_slide_test).
+
+-include_lib("eunit/include/eunit.hrl").
+-include("folsom.hrl").
+
+-define(HISTO, test_slide).
+-define(WINDOW, 30).
+-define(RUNTIME, 90).
+-define(READINGS, 10).
+
+slide_test_() ->
+ {setup,
+ fun () -> folsom:start(),
+ meck:new(folsom_utils)
+ end,
+ fun (_) -> meck:unload(folsom_utils),
+ folsom:stop() end,
+ [{"Create sliding window",
+ fun create/0},
+ {"test sliding window",
+ {timeout, 30, fun exercise/0}}
+ ]}.
+
+create() ->
+ ok = folsom_metrics:new_histogram(?HISTO, slide, ?WINDOW),
+ #histogram{sample=Slide} = folsom_metrics_histogram:get_value(?HISTO),
+ ?assert(is_pid(Slide#slide.server)),
+ ?assertEqual(?WINDOW, Slide#slide.window),
+ ?assertEqual(0, ets:info(Slide#slide.reservoir, size)).
+
+exercise() ->
+ %% don't want a trim to happen
+ %% unless we call trim
+ %% so kill the trim server process
+ #histogram{sample=Slide} = folsom_metrics_histogram:get_value(?HISTO),
+ ok = folsom_sample_slide_server:stop(Slide#slide.server),
+ Moments = lists:seq(1, ?RUNTIME),
+ %% pump in 90 seconds worth of readings
+ Moment = lists:foldl(fun(_X, Tick) ->
+ Tock = tick(Tick),
+ [folsom_sample_slide:update(Slide, N) ||
+ N <- lists:duplicate(?READINGS, Tock)],
+ Tock end,
+ 0,
+ Moments),
+ %% are all readings in the table?
+ check_table(Slide, Moments),
+ %% get values only returns last ?WINDOW seconds
+ ExpectedValues = lists:sort(lists:flatten([lists:duplicate(?READINGS, N) ||
+ N <- lists:seq(?RUNTIME - ?WINDOW, ?RUNTIME)])),
+ Values = lists:sort(folsom_sample_slide:get_values(Slide)),
+ ?assertEqual(ExpectedValues, Values),
+ %% trim the table
+ Trimmed = folsom_sample_slide:trim(Slide#slide.reservoir, ?WINDOW),
+ ?assertEqual((?RUNTIME - ?WINDOW - 1) * ?READINGS, Trimmed),
+ check_table(Slide, lists:seq(?RUNTIME - ?WINDOW, ?RUNTIME)),
+ %% increment the clock past the window
+ tick(Moment, ?WINDOW * 2),
+ %% get values should be empty
+ ?assertEqual([], folsom_sample_slide:get_values(Slide)),
+ %% trim, and table should be empty
+ Trimmed2 = folsom_sample_slide:trim(Slide#slide.reservoir, ?WINDOW),
+ ?assertEqual((?RUNTIME * ?READINGS) - ((?RUNTIME - ?WINDOW - 1) * ?READINGS), Trimmed2),
+ check_table(Slide, []),
+ ok.
+
+tick(Moment0, IncrBy) ->
+ Moment = Moment0 + IncrBy,
+ meck:expect(folsom_utils, now_epoch, fun() ->
+ Moment end),
+ Moment.
+
+tick(Moment) ->
+ tick(Moment, 1).
+
+check_table(Slide, Moments) ->
+ Tab = lists:sort(ets:tab2list(Slide#slide.reservoir)),
+ {Ks, Vs} = lists:unzip(Tab),
+ ExpectedVs = lists:sort(lists:flatten([lists:duplicate(10, N) || N <- Moments])),
+ Keys = lists:usort(Ks),
+ ?assertEqual(Moments, Keys),
+ ?assertEqual(ExpectedVs, lists:sort(Vs)).
diff --git a/test/slide_statem_eqc.erl b/test/slide_statem_eqc.erl
new file mode 100644
index 0000000..a3fddd9
--- /dev/null
+++ b/test/slide_statem_eqc.erl
@@ -0,0 +1,164 @@
+%%%
+%%% Copyright 2012 - Basho Technologies, Inc. All Rights Reserved.
+%%%
+%%% 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.
+%%%
+
+%%%-------------------------------------------------------------------
+%%% File: slide_statem_eqc.erl
+%%% @author Russell Brown <russelldb@basho.com>
+%%% @doc quickcheck test for the folsom_sample_slide.erl
+%%% @end
+%%%------------------------------------------------------------------
+
+-module(slide_statem_eqc).
+
+-compile(export_all).
+
+-ifdef(TEST).
+-ifdef(EQC).
+
+-include("folsom.hrl").
+
+-include_lib("eqc/include/eqc.hrl").
+-include_lib("eqc/include/eqc_statem.hrl").
+-include_lib("eunit/include/eunit.hrl").
+
+
+
+-define(NUMTESTS, 200).
+-define(QC_OUT(P),
+ eqc:on_output(fun(Str, Args) ->
+ io:format(user, Str, Args) end, P)).
+
+-define(WINDOW, 60).
+
+-record(state, {moment=1000,
+ sample,
+ name,
+ values=[]}).
+
+initial_state() ->
+ meck:expect(folsom_utils, now_epoch, fun() -> 1000 end),
+ #state{}.
+
+command(S) ->
+ oneof(
+ [{call, ?MODULE, new_histo, []} || S#state.sample == undefined] ++
+ [{call, ?MODULE, tick, [S#state.moment]} || S#state.sample /= undefined] ++
+ [{call, ?MODULE, update, [S#state.sample, int()]} || S#state.sample /= undefined] ++
+ [{call, ?MODULE, trim, [S#state.sample, ?WINDOW]} || S#state.sample /= undefined] ++
+ [{call, ?MODULE, get_values, [S#state.sample]} || S#state.sample /= undefined]
+ ).
+
+%% Next state transformation, S is the current state
+next_state(S, V, {call, ?MODULE, new_histo, []}) ->
+ S#state{name={call, erlang, element, [1, V]}, sample={call, erlang, element, [2, V]}};
+next_state(S, V, {call, ?MODULE, tick, [_Moment]}) ->
+ S#state{moment=V};
+next_state(#state{moment=Moment, values=Values0}=S, V, {call, ?MODULE, update, [_, _Val]}) ->
+ S#state{values=Values0 ++ [{Moment, V}]};
+next_state(#state{values=Values, moment=Moment}=S, _V, {call, ?MODULE, trim, _}) ->
+ %% trim the model
+ S#state{values = trim(Values, Moment, ?WINDOW)};
+next_state(S,_V,{call, ?MODULE, _, _}) ->
+ S.
+
+%% Precondition, checked before command is added to the command sequence
+precondition(S, {call, _, new_histo, _}) ->
+ S#state.sample == undefined;
+precondition(S, _) when S#state.sample == undefined ->
+ false;
+precondition(_S, {call, _, _, _}) ->
+ true.
+
+%% Postcondition, checked after command has been evaluated
+%% OBS: S is the state before next_state(S,_,<command>)
+postcondition(#state{values=Values0, moment=Moment}, {call, ?MODULE, get_values, _}, Res) ->
+ Values = [V || {K, V} <- Values0, K >= Moment - ?WINDOW],
+ case lists:sort(Values) == lists:sort(Res) of
+ true ->
+ true;
+ _ ->
+ {"get values", {"model", lists:sort(Values)},
+ {"smaple", lists:sort(Res)}}
+ end;
+postcondition(#state{values=Values, sample=Sample, moment=Moment}, {call, ?MODULE, trim, _}, _TrimCnt) ->
+ %% check that values and the actual table contents are the same after a trim
+ Table = ets:tab2list(Sample#slide.reservoir),
+ Model = lists:sort(trim(Values, Moment, ?WINDOW)),
+ case Model == lists:sort(Table) of
+ true ->
+ true;
+ _ ->
+ {"after trim", {"model", Model}, {"sample", lists:sort(Table)}}
+ end;
+postcondition(_S, {call, ?MODULE, _, _}, _Res) ->
+ true.
+
+prop_window_test_() ->
+ {setup, fun() -> ok end, fun(_X) -> (catch meck:unload(folsom_utils)), folsom:stop() end,
+ fun(_X) ->
+ ?_assert(eqc:quickcheck(eqc:numtests(?NUMTESTS, ?QC_OUT(prop_window())))) end}.
+
+prop_window() ->
+ folsom:start(),
+ (catch meck:new(folsom_utils)),
+ ?FORALL(Cmds, commands(?MODULE),
+ aggregate(command_names(Cmds),
+ begin
+ {H, S, Res} = run_commands(?MODULE, Cmds),
+ {Actual, Expected} = case S#state.sample of
+ undefined ->
+ {S#state.values, []};
+ Sample ->
+ A = folsom_metrics:get_metric_value(S#state.name),
+ E = [V || {K, V} <- S#state.values, K >= S#state.moment - ?WINDOW],
+ folsom_metrics:delete_metric(S#state.name),
+ {A, E}
+ end,
+ ?WHENFAIL(
+ io:format("History: ~p~nState: ~p~nActual: ~p~nExpected: ~p~nRes: ~p~n", [H, S, Actual, Expected, Res]),
+ conjunction([{total, equals(lists:sort(Actual), lists:sort(Expected))},
+ {eq, equals(Res, ok)}]))
+ end)).
+
+%% Commands
+new_histo() ->
+ Ref = make_ref(),
+ folsom_metrics:new_histogram(Ref, slide, ?WINDOW),
+ #histogram{sample=Slide} = folsom_metrics_histogram:get_value(Ref),
+ ok = folsom_sample_slide_server:stop(Slide#slide.server),
+ {Ref, Slide}.
+
+tick(Moment) ->
+ IncrBy = trunc(random:uniform(10)),
+ meck:expect(folsom_utils, now_epoch, fun() -> Moment + IncrBy end),
+ Moment+IncrBy.
+
+update(Sample, Val) ->
+ Sample = folsom_sample_slide:update(Sample, Val),
+ Val.
+
+trim(Sample, Window) ->
+ folsom_sample_slide:trim(Sample#slide.reservoir, Window).
+
+get_values(Sample) ->
+ folsom_sample_slide:get_values(Sample).
+
+%% private
+trim(L, Moment, Window) ->
+ [{K, V} || {K, V} <- L, K >= Moment - Window].
+
+-endif.
+-endif.
diff --git a/test/slide_uniform_eqc.erl b/test/slide_uniform_eqc.erl
new file mode 100644
index 0000000..99deb90
--- /dev/null
+++ b/test/slide_uniform_eqc.erl
@@ -0,0 +1,175 @@
+%%%
+%%% Copyright 2012 - Basho Technologies, Inc. All Rights Reserved.
+%%%
+%%% 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.
+%%%
+
+%%%-------------------------------------------------------------------
+%%% File: slide_uniform_eqc.erl
+%%% @author Russell Brown <russelldb@basho.com>
+%%% @doc quickcheck test for the folsom_sample_slide.erl
+%%% @end
+%%%------------------------------------------------------------------
+
+-module(slide_uniform_eqc).
+
+-compile(export_all).
+
+-ifdef(TEST).
+-ifdef(EQC).
+-include("folsom.hrl").
+
+-include_lib("eqc/include/eqc.hrl").
+-include_lib("eqc/include/eqc_statem.hrl").
+-include_lib("eunit/include/eunit.hrl").
+
+-define(NUMTESTS, 200).
+-define(QC_OUT(P),
+ eqc:on_output(fun(Str, Args) ->
+ io:format(user, Str, Args) end, P)).
+
+-define(WINDOW, 60).
+-define(SIZE, 5).
+
+-record(state, {moment=1000,
+ sample,
+ name,
+ values=[]}).
+
+initial_state() ->
+ meck:expect(folsom_utils, now_epoch, fun() -> 1000 end),
+ #state{}.
+
+command(S) ->
+ oneof(
+ [{call, ?MODULE, new_histo, []} || S#state.sample == undefined] ++
+ [{call, ?MODULE, tick, [S#state.moment]} || S#state.sample /= undefined] ++
+ [{call, ?MODULE, update, [S#state.sample, int()]} || S#state.sample /= undefined] ++
+ [{call, ?MODULE, trim, [S#state.sample, ?WINDOW]} || S#state.sample /= undefined] ++
+ [{call, ?MODULE, get_values, [S#state.sample]} || S#state.sample /= undefined]
+ ).
+
+%% Next state transformation, S is the current state
+next_state(S, V, {call, ?MODULE, new_histo, []}) ->
+ S#state{name={call, erlang, element, [1, V]}, sample={call, erlang, element, [2, V]}};
+next_state(S, V, {call, ?MODULE, tick, [_Moment]}) ->
+ S#state{moment=V};
+next_state(#state{moment=Moment, values=Values0, sample=Sample}=S, NewSample, {call, ?MODULE, update, [_, Val]}) ->
+ S#state{values={call, slide_uniform_eqc, new_state_values, [Sample, Moment, Values0, Val]},
+ sample=NewSample};
+next_state(#state{values=Values, moment=Moment}=S, _V, {call, ?MODULE, trim, _}) ->
+ %% trim the model
+ S#state{values={call, ?MODULE, trim, [Values, Moment, ?WINDOW]}};
+next_state(S,_V,{call, ?MODULE, _, _}) ->
+ S.
+
+%% Precondition, checked before command is added to the command sequence
+precondition(S, {call, _, new_histo, _}) ->
+ S#state.sample == undefined;
+precondition(S, _) when S#state.sample == undefined ->
+ false;
+precondition(_S, {call, _, _, _}) ->
+ true.
+
+%% Postcondition, checked after command has been evaluated
+%% OBS: S is the state before next_state(S,_,<command>)
+postcondition(#state{values=Values0, moment=Moment}, {call, ?MODULE, get_values, _}, Res) ->
+ Values = [V || {{M, _C}, V} <- Values0, M >= Moment - ?WINDOW],
+ case lists:sort(Values) == lists:sort(Res) of
+ true ->
+ true;
+ _ ->
+ {"get values", {"model", lists:sort(Values)}, {"sample", lists:sort(Res)}}
+ end;
+postcondition(#state{values=Values, sample=Sample, moment=Moment}, {call, ?MODULE, trim, _}, _TrimCnt) ->
+ %% check that values and the actual table contents are the same after a trim
+ Table = [ Elem || {K, _V}=Elem <- ets:tab2list(Sample#slide_uniform.reservoir)
+ , is_tuple(K)], %% filter out counter,
+ case lists:sort(trim(Values, Moment, ?WINDOW)) == lists:sort(Table) of
+ true ->
+ true;
+ _ ->
+ {"after trim", {"model", lists:sort(trim(Values, Moment, ?WINDOW))}, {"sample", lists:sort(Table)}}
+ end;
+postcondition(_S, {call, ?MODULE, _, _}, _Res) ->
+ true.
+
+prop_window_test_() ->
+ {setup, fun() -> ok end, fun(_X) -> (catch meck:unload(folsom_utils)), folsom:stop() end,
+ fun(_X) ->
+ ?_assert(eqc:quickcheck(eqc:numtests(?NUMTESTS, ?QC_OUT(prop_window())))) end}.
+
+prop_window() ->
+ folsom:start(),
+ (catch meck:new(folsom_utils)),
+ ?FORALL(Cmds, commands(?MODULE),
+ aggregate(command_names(Cmds),
+ begin
+ {H, S, Res} = run_commands(?MODULE, Cmds),
+ {Actual, Expected, Tab} = case S#state.sample of
+ undefined ->
+ {S#state.values, [], []};
+ Sample ->
+ A = folsom_metrics:get_metric_value(S#state.name),
+ E = [V || {{M, _C}, V} <- S#state.values, M >= S#state.moment - ?WINDOW],
+ T = ets:tab2list(Sample#slide_uniform.reservoir),
+ folsom_metrics:delete_metric(S#state.name),
+ {A, E, T}
+ end,
+ ?WHENFAIL(
+ io:format("History: ~p~nState: ~p~nActual: ~p~nExpected: ~p~nRes: ~p~nTab: ~p~n",
+ [H, S, Actual, Expected, Res, Tab]),
+ conjunction([{total, equals(lists:sort(Actual), lists:sort(Expected))},
+ {eq, equals(Res, ok)}]))
+ end)).
+
+%% Commands
+new_histo() ->
+ Ref = make_ref(),
+ folsom_metrics:new_histogram(Ref, slide_uniform, {?WINDOW, ?SIZE}),
+ #histogram{sample=Slide} = folsom_metrics_histogram:get_value(Ref),
+ ok = folsom_sample_slide_server:stop(Slide#slide_uniform.server),
+ {Ref, Slide}.
+
+tick(Moment) ->
+ IncrBy = trunc(random:uniform(10)),
+ meck:expect(folsom_utils, now_epoch, fun() -> Moment + IncrBy end),
+ Moment+IncrBy.
+
+update(Sample, Val) ->
+ folsom_sample_slide_uniform:update(Sample, Val).
+
+trim(Sample, Window) ->
+ folsom_sample_slide_uniform:trim(Sample#slide_uniform.reservoir, Window).
+
+get_values(Sample) ->
+ folsom_sample_slide_uniform:get_values(Sample).
+
+%% private
+trim(L, Moment, Window) ->
+ [{K, V} || {{M, _C}=K, V} <- L, M >= Moment - Window].
+
+new_state_values(Sample, Moment, Values, Val) ->
+ Cnt = length([true || {{M, _C}, _V} <- Values, M == Moment]),
+ case Cnt >= ?SIZE of
+ true ->
+ %% replace
+ {Rnd, _} = random:uniform_s(?SIZE, Sample#slide_uniform.seed),
+ lists:keyreplace({Moment, Rnd}, 1, Values, {{Moment, Rnd}, Val});
+ false ->
+ %% insert
+ Values ++ [{{Moment, Cnt+1}, Val}]
+ end.
+
+-endif.
+-endif.
