aboutsummaryrefslogtreecommitdiff
path: root/src/test/cuckoocache_tests.cpp
blob: c7c34cc8c968149ab428bf0bcb9bd1f8878e2b5e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
// Copyright (c) 2012-2021 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include <cuckoocache.h>
#include <random.h>
#include <script/sigcache.h>
#include <test/util/setup_common.h>

#include <boost/test/unit_test.hpp>

#include <deque>
#include <mutex>
#include <shared_mutex>
#include <thread>
#include <vector>

/** Test Suite for CuckooCache
 *
 *  1. All tests should have a deterministic result (using insecure rand
 *  with deterministic seeds)
 *  2. Some test methods are templated to allow for easier testing
 *  against new versions / comparing
 *  3. Results should be treated as a regression test, i.e., did the behavior
 *  change significantly from what was expected. This can be OK, depending on
 *  the nature of the change, but requires updating the tests to reflect the new
 *  expected behavior. For example improving the hit rate may cause some tests
 *  using BOOST_CHECK_CLOSE to fail.
 *
 */
BOOST_AUTO_TEST_SUITE(cuckoocache_tests);

/* Test that no values not inserted into the cache are read out of it.
 *
 * There are no repeats in the first 200000 insecure_GetRandHash calls
 */
BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes)
{
    SeedInsecureRand(SeedRand::ZEROS);
    CuckooCache::cache<uint256, SignatureCacheHasher> cc{};
    size_t megabytes = 4;
    cc.setup_bytes(megabytes << 20);
    for (int x = 0; x < 100000; ++x) {
        cc.insert(InsecureRand256());
    }
    for (int x = 0; x < 100000; ++x) {
        BOOST_CHECK(!cc.contains(InsecureRand256(), false));
    }
};

/** This helper returns the hit rate when megabytes*load worth of entries are
 * inserted into a megabytes sized cache
 */
template <typename Cache>
static double test_cache(size_t megabytes, double load)
{
    SeedInsecureRand(SeedRand::ZEROS);
    std::vector<uint256> hashes;
    Cache set{};
    size_t bytes = megabytes * (1 << 20);
    set.setup_bytes(bytes);
    uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
    hashes.resize(n_insert);
    for (uint32_t i = 0; i < n_insert; ++i) {
        uint32_t* ptr = (uint32_t*)hashes[i].begin();
        for (uint8_t j = 0; j < 8; ++j)
            *(ptr++) = InsecureRand32();
    }
    /** We make a copy of the hashes because future optimizations of the
     * cuckoocache may overwrite the inserted element, so the test is
     * "future proofed".
     */
    std::vector<uint256> hashes_insert_copy = hashes;
    /** Do the insert */
    for (const uint256& h : hashes_insert_copy)
        set.insert(h);
    /** Count the hits */
    uint32_t count = 0;
    for (const uint256& h : hashes)
        count += set.contains(h, false);
    double hit_rate = ((double)count) / ((double)n_insert);
    return hit_rate;
}

/** The normalized hit rate for a given load.
 *
 * The semantics are a little confusing, so please see the below
 * explanation.
 *
 * Examples:
 *
 * 1. at load 0.5, we expect a perfect hit rate, so we multiply by
 * 1.0
 * 2. at load 2.0, we expect to see half the entries, so a perfect hit rate
 * would be 0.5. Therefore, if we see a hit rate of 0.4, 0.4*2.0 = 0.8 is the
 * normalized hit rate.
 *
 * This is basically the right semantics, but has a bit of a glitch depending on
 * how you measure around load 1.0 as after load 1.0 your normalized hit rate
 * becomes effectively perfect, ignoring freshness.
 */
static double normalize_hit_rate(double hits, double load)
{
    return hits * std::max(load, 1.0);
}

/** Check the hit rate on loads ranging from 0.1 to 1.6 */
BOOST_AUTO_TEST_CASE(cuckoocache_hit_rate_ok)
{
    /** Arbitrarily selected Hit Rate threshold that happens to work for this test
     * as a lower bound on performance.
     */
    double HitRateThresh = 0.98;
    size_t megabytes = 4;
    for (double load = 0.1; load < 2; load *= 2) {
        double hits = test_cache<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes, load);
        BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh);
    }
}


/** This helper checks that erased elements are preferentially inserted onto and
 * that the hit rate of "fresher" keys is reasonable*/
template <typename Cache>
static void test_cache_erase(size_t megabytes)
{
    double load = 1;
    SeedInsecureRand(SeedRand::ZEROS);
    std::vector<uint256> hashes;
    Cache set{};
    size_t bytes = megabytes * (1 << 20);
    set.setup_bytes(bytes);
    uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
    hashes.resize(n_insert);
    for (uint32_t i = 0; i < n_insert; ++i) {
        uint32_t* ptr = (uint32_t*)hashes[i].begin();
        for (uint8_t j = 0; j < 8; ++j)
            *(ptr++) = InsecureRand32();
    }
    /** We make a copy of the hashes because future optimizations of the
     * cuckoocache may overwrite the inserted element, so the test is
     * "future proofed".
     */
    std::vector<uint256> hashes_insert_copy = hashes;

    /** Insert the first half */
    for (uint32_t i = 0; i < (n_insert / 2); ++i)
        set.insert(hashes_insert_copy[i]);
    /** Erase the first quarter */
    for (uint32_t i = 0; i < (n_insert / 4); ++i)
        BOOST_CHECK(set.contains(hashes[i], true));
    /** Insert the second half */
    for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
        set.insert(hashes_insert_copy[i]);

    /** elements that we marked as erased but are still there */
    size_t count_erased_but_contained = 0;
    /** elements that we did not erase but are older */
    size_t count_stale = 0;
    /** elements that were most recently inserted */
    size_t count_fresh = 0;

    for (uint32_t i = 0; i < (n_insert / 4); ++i)
        count_erased_but_contained += set.contains(hashes[i], false);
    for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i)
        count_stale += set.contains(hashes[i], false);
    for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
        count_fresh += set.contains(hashes[i], false);

    double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0);
    double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0);
    double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0);

    // Check that our hit_rate_fresh is perfect
    BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0);
    // Check that we have a more than 2x better hit rate on stale elements than
    // erased elements.
    BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained);
}

BOOST_AUTO_TEST_CASE(cuckoocache_erase_ok)
{
    size_t megabytes = 4;
    test_cache_erase<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes);
}

template <typename Cache>
static void test_cache_erase_parallel(size_t megabytes)
{
    double load = 1;
    SeedInsecureRand(SeedRand::ZEROS);
    std::vector<uint256> hashes;
    Cache set{};
    size_t bytes = megabytes * (1 << 20);
    set.setup_bytes(bytes);
    uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
    hashes.resize(n_insert);
    for (uint32_t i = 0; i < n_insert; ++i) {
        uint32_t* ptr = (uint32_t*)hashes[i].begin();
        for (uint8_t j = 0; j < 8; ++j)
            *(ptr++) = InsecureRand32();
    }
    /** We make a copy of the hashes because future optimizations of the
     * cuckoocache may overwrite the inserted element, so the test is
     * "future proofed".
     */
    std::vector<uint256> hashes_insert_copy = hashes;
    std::shared_mutex mtx;

    {
        /** Grab lock to make sure we release inserts */
        std::unique_lock<std::shared_mutex> l(mtx);
        /** Insert the first half */
        for (uint32_t i = 0; i < (n_insert / 2); ++i)
            set.insert(hashes_insert_copy[i]);
    }

    /** Spin up 3 threads to run contains with erase.
     */
    std::vector<std::thread> threads;
    /** Erase the first quarter */
    for (uint32_t x = 0; x < 3; ++x)
        /** Each thread is emplaced with x copy-by-value
        */
        threads.emplace_back([&, x] {
            std::shared_lock<std::shared_mutex> l(mtx);
            size_t ntodo = (n_insert/4)/3;
            size_t start = ntodo*x;
            size_t end = ntodo*(x+1);
            for (uint32_t i = start; i < end; ++i) {
                bool contains = set.contains(hashes[i], true);
                assert(contains);
            }
        });

    /** Wait for all threads to finish
     */
    for (std::thread& t : threads)
        t.join();
    /** Grab lock to make sure we observe erases */
    std::unique_lock<std::shared_mutex> l(mtx);
    /** Insert the second half */
    for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
        set.insert(hashes_insert_copy[i]);

    /** elements that we marked erased but that are still there */
    size_t count_erased_but_contained = 0;
    /** elements that we did not erase but are older */
    size_t count_stale = 0;
    /** elements that were most recently inserted */
    size_t count_fresh = 0;

    for (uint32_t i = 0; i < (n_insert / 4); ++i)
        count_erased_but_contained += set.contains(hashes[i], false);
    for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i)
        count_stale += set.contains(hashes[i], false);
    for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
        count_fresh += set.contains(hashes[i], false);

    double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0);
    double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0);
    double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0);

    // Check that our hit_rate_fresh is perfect
    BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0);
    // Check that we have a more than 2x better hit rate on stale elements than
    // erased elements.
    BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained);
}
BOOST_AUTO_TEST_CASE(cuckoocache_erase_parallel_ok)
{
    size_t megabytes = 4;
    test_cache_erase_parallel<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes);
}


template <typename Cache>
static void test_cache_generations()
{
    // This test checks that for a simulation of network activity, the fresh hit
    // rate is never below 99%, and the number of times that it is worse than
    // 99.9% are less than 1% of the time.
    double min_hit_rate = 0.99;
    double tight_hit_rate = 0.999;
    double max_rate_less_than_tight_hit_rate = 0.01;
    // A cache that meets this specification is therefore shown to have a hit
    // rate of at least tight_hit_rate * (1 - max_rate_less_than_tight_hit_rate) +
    // min_hit_rate*max_rate_less_than_tight_hit_rate = 0.999*99%+0.99*1% == 99.89%
    // hit rate with low variance.

    // We use deterministic values, but this test has also passed on many
    // iterations with non-deterministic values, so it isn't "overfit" to the
    // specific entropy in FastRandomContext(true) and implementation of the
    // cache.
    SeedInsecureRand(SeedRand::ZEROS);

    // block_activity models a chunk of network activity. n_insert elements are
    // added to the cache. The first and last n/4 are stored for removal later
    // and the middle n/2 are not stored. This models a network which uses half
    // the signatures of recently (since the last block) added transactions
    // immediately and never uses the other half.
    struct block_activity {
        std::vector<uint256> reads;
        block_activity(uint32_t n_insert, Cache& c) : reads()
        {
            std::vector<uint256> inserts;
            inserts.resize(n_insert);
            reads.reserve(n_insert / 2);
            for (uint32_t i = 0; i < n_insert; ++i) {
                uint32_t* ptr = (uint32_t*)inserts[i].begin();
                for (uint8_t j = 0; j < 8; ++j)
                    *(ptr++) = InsecureRand32();
            }
            for (uint32_t i = 0; i < n_insert / 4; ++i)
                reads.push_back(inserts[i]);
            for (uint32_t i = n_insert - (n_insert / 4); i < n_insert; ++i)
                reads.push_back(inserts[i]);
            for (const auto& h : inserts)
                c.insert(h);
        }
    };

    const uint32_t BLOCK_SIZE = 1000;
    // We expect window size 60 to perform reasonably given that each epoch
    // stores 45% of the cache size (~472k).
    const uint32_t WINDOW_SIZE = 60;
    const uint32_t POP_AMOUNT = (BLOCK_SIZE / WINDOW_SIZE) / 2;
    const double load = 10;
    const size_t megabytes = 4;
    const size_t bytes = megabytes * (1 << 20);
    const uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));

    std::vector<block_activity> hashes;
    Cache set{};
    set.setup_bytes(bytes);
    hashes.reserve(n_insert / BLOCK_SIZE);
    std::deque<block_activity> last_few;
    uint32_t out_of_tight_tolerance = 0;
    uint32_t total = n_insert / BLOCK_SIZE;
    // we use the deque last_few to model a sliding window of blocks. at each
    // step, each of the last WINDOW_SIZE block_activities checks the cache for
    // POP_AMOUNT of the hashes that they inserted, and marks these erased.
    for (uint32_t i = 0; i < total; ++i) {
        if (last_few.size() == WINDOW_SIZE)
            last_few.pop_front();
        last_few.emplace_back(BLOCK_SIZE, set);
        uint32_t count = 0;
        for (auto& act : last_few)
            for (uint32_t k = 0; k < POP_AMOUNT; ++k) {
                count += set.contains(act.reads.back(), true);
                act.reads.pop_back();
            }
        // We use last_few.size() rather than WINDOW_SIZE for the correct
        // behavior on the first WINDOW_SIZE iterations where the deque is not
        // full yet.
        double hit = (double(count)) / (last_few.size() * POP_AMOUNT);
        // Loose Check that hit rate is above min_hit_rate
        BOOST_CHECK(hit > min_hit_rate);
        // Tighter check, count number of times we are less than tight_hit_rate
        // (and implicitly, greater than min_hit_rate)
        out_of_tight_tolerance += hit < tight_hit_rate;
    }
    // Check that being out of tolerance happens less than
    // max_rate_less_than_tight_hit_rate of the time
    BOOST_CHECK(double(out_of_tight_tolerance) / double(total) < max_rate_less_than_tight_hit_rate);
}
BOOST_AUTO_TEST_CASE(cuckoocache_generations)
{
    test_cache_generations<CuckooCache::cache<uint256, SignatureCacheHasher>>();
}

BOOST_AUTO_TEST_SUITE_END();