corporate.fm
this repo has no description
garrison.corporate.fm
1defmodule Hobbes.VersionMapTest do
2 use ExUnit.Case, async: true
3
4 alias Hobbes.{VersionMap, TestVersionMap}
5
6 defmodule Fuzzer do
7 import Hobbes.Utils
8
9 @enforce_keys [
10 :version_map,
11 :test_version_map,
12
13 :version,
14 :cleared_version,
15
16 :seed,
17 ]
18 defstruct @enforce_keys
19
20 def new(seed) do
21 :rand.seed(:exsss, seed)
22
23 %Fuzzer{
24 version_map: VersionMap.new(),
25 test_version_map: TestVersionMap.new(),
26
27 version: 1,
28 cleared_version: 0,
29
30 seed: seed,
31 }
32 end
33
34 def run(%Fuzzer{} = fuzzer, op_count) when is_integer(op_count) do
35 Enum.reduce(1..op_count, fuzzer, fn i, fuzzer ->
36 try do
37 perform(random_op(), fuzzer)
38 rescue
39 e in [ExUnit.AssertionError] ->
40 e = Map.update!(e, :message, &(&1 <> " (at op #{i}, seed=#{inspect(fuzzer.seed)})"))
41 reraise e, __STACKTRACE__
42 e ->
43 require Logger
44 Logger.error("Error #{inspect(e)} at op=#{i}, seed=#{inspect(fuzzer.seed)}")
45 reraise e, __STACKTRACE__
46 end
47 end)
48 end
49
50 @ops [:add_writes, :check_read]
51 defp random_op do
52 case Enum.random(1..100) do
53 1 -> :clear_old
54 _ -> Enum.random(@ops)
55 end
56 end
57
58 defp inc_version(%Fuzzer{} = fuzzer) do
59 %{fuzzer | version: fuzzer.version + Enum.random(1..100)}
60 end
61
62 defp perform(:clear_old, %Fuzzer{} = fuzzer) do
63 up_to_version = Enum.random(fuzzer.cleared_version..fuzzer.version)
64
65 :ok = VersionMap.clear_old(fuzzer.version_map, up_to_version)
66 test_version_map = TestVersionMap.clear_old(fuzzer.test_version_map, up_to_version)
67
68 %{fuzzer | test_version_map: test_version_map}
69 end
70
71 defp perform(:add_writes, %Fuzzer{} = fuzzer) do
72 fuzzer = inc_version(fuzzer)
73
74 count = Enum.random(1..10)
75 # TODO: test single keys?
76 writes = Enum.map(1..count, fn _i -> random_range() end)
77 version = fuzzer.version
78
79 :ok = VersionMap.add_writes(fuzzer.version_map, version, writes)
80 test_version_map = TestVersionMap.add_writes(fuzzer.test_version_map, version, writes)
81
82 %{fuzzer | test_version_map: test_version_map}
83 end
84
85 defp perform(:check_read, %Fuzzer{} = fuzzer) do
86 range = random_range()
87 read_version = Enum.random(fuzzer.cleared_version..fuzzer.version)
88
89 vm_result = VersionMap.written_after?(fuzzer.version_map, read_version, range)
90 tvm_result = TestVersionMap.written_after?(fuzzer.test_version_map, read_version, range)
91
92 assert vm_result == tvm_result
93
94 fuzzer
95 end
96
97 defp random_range do
98 k1 = random_key()
99 k2 = random_key()
100 cond do
101 k1 < k2 -> {k1, k2}
102 k1 > k2 -> {k2, k1}
103 k1 == k2 -> {k1, next_key(k1)}
104 end
105 end
106
107 defp random_key do
108 case Enum.random(1..10) do
109 1 -> ""
110 2 -> "\xFF"
111 _ -> Enum.random(1..100) |> Integer.to_string() |> String.pad_leading(3, "0")
112 end
113 end
114 end
115
116 describe "fuzz" do
117 @tag :fuzz_vm
118 test "VersionMap" do
119 Fuzzer.new(100)
120 |> Fuzzer.run(10_000)
121 end
122
123 @tag :fuzz_vm_slow
124 @tag :disable
125 test "VersionMap (slow)" do
126 for i <- 1..300 do
127 Fuzzer.new(100 + i)
128 |> Fuzzer.run(10_000)
129 end
130 end
131 end
132
133 describe "VersionMap" do
134 @describetag :version_map
135 setup do
136 %{vm: VersionMap.new()}
137 end
138
139 test "checks versions for keys", %{vm: vm} do
140 assert :ok = VersionMap.add_writes(vm, 100, ["foo", "hello"])
141 assert :ok = VersionMap.add_writes(vm, 200, ["hello", "bar"])
142
143 assert VersionMap.written_after?(vm, 99, "foo") == true
144 assert VersionMap.written_after?(vm, 100, "foo") == false
145 assert VersionMap.written_after?(vm, 101, "foo") == false
146
147 assert VersionMap.written_after?(vm, 101, "hello") == true
148 end
149
150 test "checks versions for range", %{vm: vm} do
151 assert :ok = VersionMap.add_writes(vm, 100, ["key1", "key2", "key3"])
152
153 assert VersionMap.written_after?(vm, 99, {"key0", "key2"}) == true
154 assert VersionMap.written_after?(vm, 100, {"key0", "key2"}) == false
155 assert VersionMap.written_after?(vm, 101, {"key0", "key2"}) == false
156
157 assert VersionMap.written_after?(vm, 0, {"hello", "hello_world"}) == false
158 end
159
160 test "clears old versions", %{vm: vm} do
161 assert :ok = VersionMap.add_writes(vm, 1, ["a1", "b1", "c1"])
162 assert :ok = VersionMap.add_writes(vm, 2, ["a2", "b2", "c2"])
163 assert :ok = VersionMap.add_writes(vm, 3, ["a3", "b3", "c3"])
164
165 assert :ok = VersionMap.clear_old(vm, 1)
166 assert length(VersionMap.dump(vm)) == 6
167
168 assert :ok = VersionMap.clear_old(vm, 3)
169 assert length(VersionMap.dump(vm)) == 0
170 end
171 end
172
173 describe "benchmarks" do
174 @tag :bench_vm
175 @tag :disable
176 test "benchmark VersionMap" do
177 vm = VersionMap.new()
178
179 # This benchmark performs `batch_count` batches, with each batch consisting of
180 # a set of random writes and then random reads of past writes
181 #
182 # Old versions are cleared every so often to simulate the MVCC window
183 #
184 # Current results (1,000,000 batches)
185 # 50/50 (10r, 10w): 40.2s ( 24,800 TPS)
186 # 90/10 (10r, 1w): 9.1s (110,200 TPS)
187 # 10/90 ( 1r, 10w): 27.9s ( 35,800 TPS)
188 # 50/50 ( 1r, 1w): 2.5s (392,800 TPS)
189 #
190 # 10,000,000 batches
191 # 50/50 ( 1r, 1w): 27.9s (357,800 TPS)
192 batch_count = 1_000_000
193 writes_per_batch = 10
194 reads_per_batch = 10
195 clear_every = 50_000
196 clear_below = 250_000
197
198 hash_fn = fn i, j ->
199 {i, j} |> :erlang.phash2() |> Integer.to_string() |> String.duplicate(6)
200 end
201
202 {time, _} = :timer.tc(fn ->
203 Enum.each(1..batch_count, fn version ->
204 keys = Enum.map(1..writes_per_batch, fn k_i -> hash_fn.(version, k_i) end)
205 VersionMap.add_writes(vm, version, keys)
206
207 Enum.each(1..reads_per_batch, fn _i ->
208 k = hash_fn.(Enum.random(1..version), Enum.random(1..writes_per_batch))
209 VersionMap.written_after?(vm, version, k)
210 end)
211
212 if rem(version, clear_every) == 0 do
213 VersionMap.clear_old(vm, max(version - clear_below, 0))
214 end
215 end)
216 end)
217
218 require Logger
219 Logger.info """
220 Ran #{batch_count} batches (#{batch_count * writes_per_batch} writes, #{batch_count * reads_per_batch} reads) in #{time / 1000} ms
221 (#{batch_count / (time / 1_000_000)} batches / second)
222 """
223 end
224 end
225end