Repository: trafficserver Updated Branches: refs/heads/master e37d0b0d1 -> 7bea92984
TS-4053: Add regression tests for hit rate and size for the RAM caches The upshot is that the two Ram caches use the correct amount of memory (within 2%) and that LRU works better for identically sized objects (because LRU is a very good proxy for hit rate and LRU has less memory overhead) and CLFUS works better for variable/mixed size objects (which is expected since that is what it is trying to do). Note that for large caches, the cost of CLFUS for fixed size approaches zero as the overhead has less effect but the benefit for variable size objects increases. The regression tests at 1MB 16MB and 256MB, but with relatively small objects (16KB) so the results should be applicable to more popular production size RAM caches in the GB(s) range. Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/7bea9298 Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/7bea9298 Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/7bea9298 Branch: refs/heads/master Commit: 7bea9298439e8de41ce9350c93754daefe6cc8d0 Parents: e37d0b0 Author: John Plevyak <[email protected]> Authored: Thu Dec 3 14:18:52 2015 -0800 Committer: James Peach <[email protected]> Committed: Sun Dec 6 10:41:04 2015 -0800 ---------------------------------------------------------------------- ci/regression | 3 +- iocore/cache/CacheTest.cc | 111 ++++++++++++++++++++++++++++++++++--- iocore/cache/P_RamCache.h | 1 + iocore/cache/RamCacheCLFUS.cc | 56 +++++++++++++++---- iocore/cache/RamCacheLRU.cc | 14 +++++ 5 files changed, 167 insertions(+), 18 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/7bea9298/ci/regression ---------------------------------------------------------------------- diff --git a/ci/regression b/ci/regression index 9f635f5..49e51a6 100755 --- a/ci/regression +++ b/ci/regression @@ -102,9 +102,10 @@ build() { ( cd $OBJROOT && $MAKE install ) } +# Run extended (level 3) regressions. regress() { ( cd $OBJROOT && $MAKE check ) && \ - $DSTROOT/bin/traffic_server -R 1 + $DSTROOT/bin/traffic_server -R 3 } CC=${CC:-$(prog cc)} http://git-wip-us.apache.org/repos/asf/trafficserver/blob/7bea9298/iocore/cache/CacheTest.cc ---------------------------------------------------------------------- diff --git a/iocore/cache/CacheTest.cc b/iocore/cache/CacheTest.cc index 096f5c9..832ac8d 100644 --- a/iocore/cache/CacheTest.cc +++ b/iocore/cache/CacheTest.cc @@ -469,15 +469,55 @@ REGRESSION_TEST(cache_disk_replacement_stability)(RegressionTest *t, int level, hr2.vols = 0; } -bool -test_RamCache(RegressionTest *t, RamCache *cache) +static double zipf_alpha = 1.2; +static int64_t zipf_bucket_size = 1; + +#define ZIPF_SIZE (1 << 20) + +static double *zipf_table = NULL; + +static void +build_zipf() +{ + if (zipf_table) + return; + zipf_table = (double *)ats_malloc(ZIPF_SIZE * sizeof(double)); + for (int i = 0; i < ZIPF_SIZE; i++) + zipf_table[i] = 1.0 / pow(i + 2, zipf_alpha); + for (int i = 1; i < ZIPF_SIZE; i++) + zipf_table[i] = zipf_table[i - 1] + zipf_table[i]; + double x = zipf_table[ZIPF_SIZE - 1]; + for (int i = 0; i < ZIPF_SIZE; i++) + zipf_table[i] = zipf_table[i] / x; +} + +static int +get_zipf(double v) +{ + int l = 0, r = ZIPF_SIZE - 1, m; + do { + m = (r + l) / 2; + if (v < zipf_table[m]) + r = m - 1; + else + l = m + 1; + } while (l < r); + if (zipf_bucket_size == 1) + return m; + double x = zipf_table[m], y = zipf_table[m + 1]; + m += static_cast<int>((v - x) / (y - x)); + return m; +} + +static bool +test_RamCache(RegressionTest *t, RamCache *cache, const char *name, int64_t cache_size) { bool pass = true; CacheKey key; Vol *vol = theCache->key_to_vol(&key, "example.com", sizeof("example.com") - 1); vector<Ptr<IOBufferData> > data; - cache->init(1 << 20, vol); + cache->init(cache_size, vol); for (int l = 0; l < 10; l++) { for (int i = 0; i < 200; i++) { @@ -511,7 +551,62 @@ test_RamCache(RegressionTest *t, RamCache *cache) pass = false; } } - rprintf(t, "RamCache Test Done"); + + int sample_size = cache_size >> 6; + build_zipf(); + srand48(13); + int *r = (int *)ats_malloc(sample_size * sizeof(int)); + for (int i = 0; i < sample_size; i++) + r[i] = get_zipf(drand48()); + data.clear(); + int misses = 0; + for (int i = 0; i < sample_size; i++) { + INK_MD5 md5; + md5.u64[0] = ((uint64_t)r[i] << 32) + r[i]; + md5.u64[1] = ((uint64_t)r[i] << 32) + r[i]; + Ptr<IOBufferData> get_data; + if (!cache->get(&md5, &get_data)) { + IOBufferData *d = THREAD_ALLOC(ioDataAllocator, this_thread()); + d->alloc(BUFFER_SIZE_INDEX_16K); + data.push_back(make_ptr(d)); + cache->put(&md5, data.back(), 1 << 15); + if (i >= sample_size / 2) + misses++; // Sample last half of the gets. + } + } + double fixed_hit_rate = 1.0 - (((double)(misses)) / (sample_size / 2)); + rprintf(t, "RamCache %s Fixed Size Hit Rate %f\n", name, fixed_hit_rate); + + data.clear(); + misses = 0; + for (int i = 0; i < sample_size; i++) { + INK_MD5 md5; + md5.u64[0] = ((uint64_t)r[i] << 32) + r[i]; + md5.u64[1] = ((uint64_t)r[i] << 32) + r[i]; + Ptr<IOBufferData> get_data; + if (!cache->get(&md5, &get_data)) { + IOBufferData *d = THREAD_ALLOC(ioDataAllocator, this_thread()); + d->alloc(BUFFER_SIZE_INDEX_8K + (r[i] % 3)); + data.push_back(make_ptr(d)); + cache->put(&md5, data.back(), d->block_size()); + if (i >= sample_size / 2) + misses++; // Sample last half of the gets. + } + } + double variable_hit_rate = 1.0 - (((double)(misses)) / (sample_size / 2)); + rprintf(t, "RamCache %s Variable Size Hit Rate %f\n", name, variable_hit_rate); + + rprintf(t, "RamCache %s Nominal Size %lld Size %lld\n", name, cache_size, cache->size()); + + if (fixed_hit_rate < 0.55 || variable_hit_rate < 0.55) + return false; + if (abs(cache_size - cache->size()) > 0.02 * cache_size) + return false; + + ats_free(r); + + rprintf(t, "RamCache %s Test Done\r", name); + return pass; } @@ -522,8 +617,10 @@ REGRESSION_TEST(ram_cache)(RegressionTest *t, int /* level ATS_UNUSED */, int *p *pstatus = REGRESSION_TEST_FAILED; return; } - if (!test_RamCache(t, new_RamCacheLRU()) || !test_RamCache(t, new_RamCacheCLFUS())) - *pstatus = REGRESSION_TEST_FAILED; - else + for (int s = 20; s <= 28; s += 4) { + int64_t cache_size = 1LL << s; *pstatus = REGRESSION_TEST_PASSED; + if (!test_RamCache(t, new_RamCacheLRU(), "LRU", cache_size) || !test_RamCache(t, new_RamCacheCLFUS(), "CLFUS", cache_size)) + *pstatus = REGRESSION_TEST_FAILED; + } } http://git-wip-us.apache.org/repos/asf/trafficserver/blob/7bea9298/iocore/cache/P_RamCache.h ---------------------------------------------------------------------- diff --git a/iocore/cache/P_RamCache.h b/iocore/cache/P_RamCache.h index 6bd4270..ae653a4 100644 --- a/iocore/cache/P_RamCache.h +++ b/iocore/cache/P_RamCache.h @@ -34,6 +34,7 @@ struct RamCache { virtual int put(INK_MD5 *key, IOBufferData *data, uint32_t len, bool copy = false, uint32_t auxkey1 = 0, uint32_t auxkey2 = 0) = 0; virtual int fixup(const INK_MD5 *key, uint32_t old_auxkey1, uint32_t old_auxkey2, uint32_t new_auxkey1, uint32_t new_auxkey2) = 0; + virtual int64_t size() const = 0; virtual void init(int64_t max_bytes, Vol *vol) = 0; virtual ~RamCache(){}; http://git-wip-us.apache.org/repos/asf/trafficserver/blob/7bea9298/iocore/cache/RamCacheCLFUS.cc ---------------------------------------------------------------------- diff --git a/iocore/cache/RamCacheCLFUS.cc b/iocore/cache/RamCacheCLFUS.cc index db44527..58ee38e 100644 --- a/iocore/cache/RamCacheCLFUS.cc +++ b/iocore/cache/RamCacheCLFUS.cc @@ -41,10 +41,13 @@ #define LZMA_BASE_MEMLIMIT (64 * 1024 * 1024) //#define CHECK_ACOUNTING 1 // very expensive double checking of all sizes -#define REQUEUE_HITS(_h) ((_h) ? 1 : 0) +#define REQUEUE_HITS(_h) ((_h) ? ((_h)-1) : 0) #define CACHE_VALUE_HITS_SIZE(_h, _s) ((float)((_h) + 1) / ((_s) + ENTRY_OVERHEAD)) #define CACHE_VALUE(_x) CACHE_VALUE_HITS_SIZE((_x)->hits, (_x)->size) +#define AVERAGE_VALUE_OVER 100 +#define REQUEUE_LIMIT 100 + struct RamCacheCLFUSEntry { INK_MD5 key; uint32_t auxkey1; @@ -76,11 +79,13 @@ struct RamCacheCLFUS : public RamCache { int get(INK_MD5 *key, Ptr<IOBufferData> *ret_data, uint32_t auxkey1 = 0, uint32_t auxkey2 = 0); int put(INK_MD5 *key, IOBufferData *data, uint32_t len, bool copy = false, uint32_t auxkey1 = 0, uint32_t auxkey2 = 0); int fixup(const INK_MD5 *key, uint32_t old_auxkey1, uint32_t old_auxkey2, uint32_t new_auxkey1, uint32_t new_auxkey2); + int64_t size() const; void init(int64_t max_bytes, Vol *vol); // private Vol *vol; // for stats + double average_value; int64_t history; int ibuckets; int nbuckets; @@ -97,12 +102,29 @@ struct RamCacheCLFUS : public RamCache { void requeue_victims(Que(RamCacheCLFUSEntry, lru_link) & victims); void tick(); // move CLOCK on history RamCacheCLFUS() - : max_bytes(0), bytes(0), objects(0), vol(0), history(0), ibuckets(0), nbuckets(0), bucket(0), seen(0), ncompressed(0), - compressed(0) + : max_bytes(0), bytes(0), objects(0), vol(0), average_value(0), history(0), ibuckets(0), nbuckets(0), bucket(0), seen(0), + ncompressed(0), compressed(0) { } }; +int64_t +RamCacheCLFUS::size() const +{ + int64_t s = 0; + for (int i = 0; i < 2; i++) { + forl_LL(RamCacheCLFUSEntry, e, lru[i]) + { + s += sizeof(e); + if (e->data) { + s += sizeof(*e->data); + s += e->data->block_size(); + } + } + } + return s; +} + class RamCacheCLFUSCompressor : public Continuation { public: @@ -217,11 +239,13 @@ RamCacheCLFUS::get(INK_MD5 *key, Ptr<IOBufferData> *ret_data, uint32_t auxkey1, while (e) { if (e->key == *key && e->auxkey1 == auxkey1 && e->auxkey2 == auxkey2) { move_compressed(e); - lru[e->flag_bits.lru].remove(e); - lru[e->flag_bits.lru].enqueue(e); if (!e->flag_bits.lru) { // in memory - uint32_t ram_hit_state = RAM_HIT_COMPRESS_NONE; + if (CACHE_VALUE(e) > average_value) { + lru[e->flag_bits.lru].remove(e); + lru[e->flag_bits.lru].enqueue(e); + } e->hits++; + uint32_t ram_hit_state = RAM_HIT_COMPRESS_NONE; if (e->flag_bits.compressed) { b = (char *)ats_malloc(e->len); switch (e->flag_bits.compressed) { @@ -528,6 +552,7 @@ RamCacheCLFUS::put(INK_MD5 *key, IOBufferData *data, uint32_t len, bool copy, ui uint32_t i = key->slice32(3) % nbuckets; RamCacheCLFUSEntry *e = bucket[i].head; uint32_t size = copy ? len : data->block_size(); + double victim_value = 0; while (e) { if (e->key == *key) { if (e->auxkey1 == auxkey1 && e->auxkey2 == auxkey2) @@ -563,11 +588,17 @@ RamCacheCLFUS::put(INK_MD5 *key, IOBufferData *data, uint32_t len, bool copy, ui e->flag_bits.compressed = 0; DDebug("ram_cache", "put %X %d %d size %d HIT", key->slice32(3), auxkey1, auxkey2, e->size); return 1; - } else + } else { lru[1].remove(e); + if (CACHE_VALUE(e) < average_value) { + lru[1].enqueue(e); + return 0; + } + } } Que(RamCacheCLFUSEntry, lru_link) victims; RamCacheCLFUSEntry *victim = 0; + int requeue_limit = REQUEUE_LIMIT; if (!lru[1].head) // initial fill if (bytes + size <= max_bytes) goto Linsert; @@ -592,6 +623,11 @@ RamCacheCLFUS::put(INK_MD5 *key, IOBufferData *data, uint32_t len, bool copy, ui DDebug("ram_cache", "put %X %d %d NO VICTIM", key->slice32(3), auxkey1, auxkey2); return 0; } + average_value = (CACHE_VALUE(victim) + (average_value * (AVERAGE_VALUE_OVER - 1))) / AVERAGE_VALUE_OVER; + if (CACHE_VALUE(victim) > average_value && requeue_limit-- > 0) { + lru[0].enqueue(victim); + continue; + } bytes -= victim->size + ENTRY_OVERHEAD; CACHE_SUM_DYN_STAT_THREAD(cache_ram_cache_bytes_stat, -(int64_t)victim->size); victims.enqueue(victim); @@ -599,13 +635,13 @@ RamCacheCLFUS::put(INK_MD5 *key, IOBufferData *data, uint32_t len, bool copy, ui compressed = 0; else ncompressed--; - victim->hits >>= 1; + victim_value += CACHE_VALUE(victim); tick(); if (!e) goto Lhistory; else { // e from history - DDebug("ram_cache_compare", "put %f %f", CACHE_VALUE(victim), CACHE_VALUE(e)); - if (bytes + victim->size + size > max_bytes && CACHE_VALUE(victim) > CACHE_VALUE(e)) { + DDebug("ram_cache_compare", "put %f %f", victim_value, CACHE_VALUE(e)); + if (bytes + victim->size + size > max_bytes && victim_value > CACHE_VALUE(e)) { requeue_victims(victims); lru[1].enqueue(e); DDebug("ram_cache", "put %X %d %d size %d INC %" PRId64 " HISTORY", key->slice32(3), auxkey1, auxkey2, e->size, e->hits); http://git-wip-us.apache.org/repos/asf/trafficserver/blob/7bea9298/iocore/cache/RamCacheLRU.cc ---------------------------------------------------------------------- diff --git a/iocore/cache/RamCacheLRU.cc b/iocore/cache/RamCacheLRU.cc index b947ef0..5a6f3a9 100644 --- a/iocore/cache/RamCacheLRU.cc +++ b/iocore/cache/RamCacheLRU.cc @@ -43,6 +43,7 @@ struct RamCacheLRU : public RamCache { int get(INK_MD5 *key, Ptr<IOBufferData> *ret_data, uint32_t auxkey1 = 0, uint32_t auxkey2 = 0); int put(INK_MD5 *key, IOBufferData *data, uint32_t len, bool copy = false, uint32_t auxkey1 = 0, uint32_t auxkey2 = 0); int fixup(const INK_MD5 *key, uint32_t old_auxkey1, uint32_t old_auxkey2, uint32_t new_auxkey1, uint32_t new_auxkey2); + int64_t size() const; void init(int64_t max_bytes, Vol *vol); @@ -60,6 +61,19 @@ struct RamCacheLRU : public RamCache { RamCacheLRU() : bytes(0), objects(0), seen(0), bucket(0), nbuckets(0), ibuckets(0), vol(NULL) {} }; +int64_t +RamCacheLRU::size() const +{ + int64_t s = 0; + forl_LL(RamCacheLRUEntry, e, lru) + { + s += sizeof(e); + s += sizeof(*e->data); + s += e->data->block_size(); + } + return s; +} + ClassAllocator<RamCacheLRUEntry> ramCacheLRUEntryAllocator("RamCacheLRUEntry"); static const int bucket_sizes[] = {127, 251, 509, 1021, 2039, 4093, 8191, 16381,
